一、單項選擇題1某算法的時間復雜度是O(n2)，表明該算法()。A問題規模是n2 B問題規模與n2成正比C執行時間等于n2 D執行時間與n2成正比2、關于數據結構的描述，不正確的是()。A數據結構相同，對應的存儲結構也相同。B數據結構涉及數據的邏輯結構、存儲結構和施加其上的操作等三個方面。C數據結構操作的實現與存儲結構有關。D定義邏輯結構時可不考慮存儲結構。3、按排序策略分來，起泡排序屬于()。A插入排序B選擇排序C交換排序D歸并排序4、利用雙向鏈表作線性表的存儲結構的優點是()。A便于進行插入和刪除的操作B提高按關系查找數據元素的速度C節省空間D便于銷毀結構釋放空間5、一個隊列的進隊順序為1,2,3,4，則該隊列可能的輸出序列是()。A1,2,3,4B1,3,2,4C1,4,2,3D4,3,2,16、Dijkstra算法是按()方法求出圖中從某頂點到其余頂點最短路徑的。A按長度遞減的順序求出圖的某頂點到其余頂點的最短路徑B按長度遞增的順序求出圖的某頂點到其余頂點的最短路徑C通過深度優先遍歷求出圖中從某頂點到其余頂點的所有路徑D通過廣度優先遍歷求出圖的某頂點到其余頂點的最短路徑7、 字符串可定義為n(n20)個字符的有限()。其中，n是字符串的長度，表明字符串中字符的個數。A集合B數列C序列D聚合8、 在二維數組A[9][10]中，每個數組元素占用3個存儲單元，從首地址SA開始按行連續存放。在這種情況下，元素A[8][5]的起始地址為()。ASA+141 BSA+144CSA+222DSA+2559、 已知廣義表為L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),則它的長度是()。TOC\o"1-5"\h\zA2 B3 C4 D510、 對于具有n(n>1)個頂點的強連通圖，其有向邊條數至少有 。A.n+1B.n C.n-1D.n-211、 一個遞歸算法必須包括 。A.遞歸部分B.結束條件和遞歸部分C.迭代部分D.結束條件和迭代部分12、 從邏輯上看可以把數據結構分為 兩大類。A.動態結構、靜態結構 B.順序結構、鏈式結構C.線性結構、非線性結構 D.初等結構、構造型結構13、 若在長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為()。AO(n) BO(1) CO(n2) DO(logn)采用順序搜素方式搜索長度為n的線性表時，在等概率情況下，搜索成功時的平均搜索長度為 。A.n B.n/2 C.(n+1)/2 D.(n-1)/215、 非空的循環單鏈表first的鏈尾結點(由p所指向)滿足()。Ap->link==NULL; BP==NULL;

Cp->link==first;Dp==first;16、 用S表示進棧操作，用X表示出棧操作，若元素的進棧順序是1234，為了得到1342的出棧順序，相應的S和X的操作序列為()。ASXSXSSXX BSSSXXSXXCSXSSXXSX DSXSSXSXX17、 含有129個葉結點的完全二叉樹，最少有()個結點。A254 B255 C257 D25818、一個有向圖G的鄰接表存儲如圖(1)所示，現按深度優先搜索方式從頂點A出發執行一次遍歷，所得的頂點序列是()。A1,2,3,4,5 B1,2,3,5,4 C1,2,4,5,3 D1,2,5,3,419、 樹最合適用來表示()。A有序數據元素 B元素之間具有分支層次關系的數據C無序數據元素 D元素之間無聯系的數據20、 一棵有124個葉結點的完全二叉樹最少有()個結點。A247 B248 C249 D25021、 圖(1)給出的一棵二叉搜索樹，對應的二叉判定樹如圖(2)所示，它的搜索成功的平均長度是()。A21/7B28/7CA21/7B28/7C15/6D16/6圖(1圖(1)二叉搜索樹圖(2)二叉判定樹23、對5個不同的數據元素進行直接插入排序，最大需要進行()次比較。A8 B10 C15 D2524、將一個nXn的對稱矩陣A的下三角部分按行存放在一個一維數組B中，A[0][0]存放在B[0]中，那么第i行的對角元素A[i][i]在B中的存放位置是()。A(i+3)*i/2B(i+1)*i/2 C(2n-i+1)*i/2D(2n-i-1)*i/225、已知廣義表為L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),則它的深度是()。A2 B3 C426、 順序搜索法適合于存儲結構為()的線性表。A散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲27、 采用折半搜索方式搜索一個長度為n的有序順序表時，其平均搜索長度為()。AO(n)BO(logn)CO(n2) DO(nlogn)28、n個結點的線索二叉樹中，線索的數目是()。 2An-1 Bn+1 C2n D2n-129、 若數據元素序列｛11,12,13,7,8,9,23,4,5｝是采用下列排序方法之一得到的第二趟排序后的結果，則該排序方法只能是()。A插入排序B選擇排序C交換排序D歸并排序

30、為了增加內存空間的利用率和減少溢出的可能，在兩個棧共享一片連續的存儲空間時，應將兩個棧的棧頂分別設在這片存儲空間的兩端，當()時才產生上溢。A兩個棧的棧頂同時到達?？臻g的中心點B其中一個棧的棧頂到達?？臻g的中心點C兩個棧的棧頂在棧空間的某一位置相遇D兩個棧的棧頂相加超過了棧空間的最大容量31、設一棵二叉樹的中序序列為badce,后序遍歷為bdeca,則該二叉樹前序遍歷的順序是()。Aadbec Bdecab Cdebac Dabcde32、 圖的簡單路徑是指()不重復的路徑。A權值B頂點C邊D邊與頂點均不重復33、 用n個權值構造出來的Huffman樹共有()個結點。A2n-1 B2n C2n+1 Dn+134、在如圖(2)所示的AVL樹中插入關鍵碼48,得到了一棵新的AVL樹，在這棵新的AVL樹中,關鍵碼3734、在如圖(2)所示的AVL樹中插入關鍵碼48,得到了一棵新的AVL樹，在這棵新的AVL樹中,關鍵碼37所在結點的左右子女結點中保存的關鍵碼分別是(A13,48 B24,48）。D24,90C24,53圖(1)14小題的鄰接表15小題的AVL樹圖2)ABCDE251\3141\二、填空題1、算法效率的度量分為事后測量和事前估兩種。2、 算法是一個有窮的指令集,它為解決某一特定任務規定了一個運算序列。它應當具有輸入、輸出、確定性、 有窮性 可行性等特性。3、一個抽象數據類型ADT包括. 數據操作 和對象 兩個部分。4、隊列的插入操作是在隊尾進行，刪除操作是在 隊頭進行。5、棧又稱為 先進后岀 的線性表，隊列又稱為 先進先岀線性表。6、對稱矩陣的行數和列數 相等 且以主對角線為對稱軸，因此只要存儲它的上三角部分或者下三角部分即可。7、 利用三元組表存放稀疏矩陣中的非零元素,則在三元組表中每個三元組中應記錄相應非TOC\o"1-5"\h\z零元的行號、列號和非零元素的—值 。8、廣義表A((a,b,c),(d,e,f))的表頭是 (a,b,c) 。9、廣義表A((a,b,c),(d,e,f))的表尾是 ((d,e,f))10、 在一棵有n個結點的二叉樹中，若度為2的結點數為n2,度為1的結點數為n1,度為0的結點數為n0,則樹的最小高度為—^先“」+1 ，其葉節點數為—n2+1 。11、 在一棵有n個結點的二叉樹中，若度為2的結點數為n2,度為1的結點數為n1,度為0的結點數為n0,則樹的最大高度為 n ，其葉節點數為 1 。12、 已知有序順序表(13,18,24,35,47,50,62,83,90,115,134)，當用折半搜索法搜索值18TOC\o"1-5"\h\z的元素時，搜索成功的數據比較次數為4 。13、采用順序搜索方式搜索長度為n的線性表時，平均搜索長度為 （n+l）/2 。14、 對于一個具有n個頂點和e條邊的無向圖進行遍歷，若采用鄰接矩陣表示，則時間復雜度為 0（e），若采用鄰接表表示，則時間復雜度為O（n+e）。15、 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接矩陣表示，則該矩陣大小是—n2 ,矩陣中的非零元個數為 2e。16、 每次從無序表中挑選一個最小或者最大兀素，把它交換到有序表的一端，此種排序方法叫彳 排序。17、 對n個元素的序列進行排序時，如果待排序元素序列的初始排列完全逆序，則起泡排序過程中需要進行n（n-1）/2 次元素值的比較， n（n-1）/2次元素值的交換。18、 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做插入插入排序。19、 對n個元素的序列進行排序時，如果待排序元素序列的初始排列已經全部有序，則起泡排序過程中需要進行n-1 次元素值的比較， 0次元素值的交換。三、判斷題1、 數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶按照使用需要建立的。錯2、 數據結構是指相互之間存在一種或多種關系的數據元素的全體。對3、 根據隊列的先進先出的特性，最后進隊列的元素最后出隊列。對4、 在順序棧中元素是按照其值的大小有序存放的。錯5、 棧底元素是不能刪除的。錯6、 在隊列中，n個元素的進隊列順序和出隊列順序總是一致的。對7、 數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的。錯8、 廣義表是線性表的推廣，但它不是一種線性結構。對9、 二維數組可以視為數組元素為一維數組的一維數組。因此，二維數組是線性結構。錯10、 有n個整數存放在一維數組A[n]中，在進行順序搜索時，無論這n個整數的排列是否有序，其平均搜索長度都相同。錯11、 鄰接矩陣適用于稠密圖（邊數接近于頂點數的平方），鄰接表適用于稀疏圖（邊數遠小于頂點數的平方）。對12、 對n個頂點的連通圖G來說，如果其中的某個子圖有n個頂點，n-1條邊，則該子圖一定是G的生成樹。錯13、 希爾排序、簡單選擇排序都是不穩定的排序方法。錯14、 如果一個二叉樹的結點，或者兩棵子樹都空，或者兩棵子樹都非空，則此二叉樹稱為完全二叉樹。錯15、 在二叉搜索樹中，任一結點所具有的關鍵碼值都大于它的左子女（如果存在）的關鍵碼值，同時小于其右子女（如果存在）的關鍵碼值。對16、 具有n個頂點的無向圖最多有n（n-1）條邊，最少有n-1條邊。錯17、 最小生成樹是指邊數最少的生成樹。錯四、簡答與計算題1、 什么是數據結構？有關數據結構的討論涉及哪三個方面？2、 什么是算法，算法的5個特性是什么？3、 已知如圖（3）所示的有向圖，請利用Kruskal算法求出最小生成樹。

圖（3）4、如圖（3）所示的有向圖，請給出該圖的鄰接矩陣和鄰接表。圖（3）5、已知一棵二叉樹的前序遍歷結果是ABECDFGHIJ,中序遍歷結果是EBCDAFHIGJ,試畫出這6、給定權值集合｛15,03,14,02,06,09,16,17｝，構造相應的huffman樹，并計算它的帶權外部路徑長度。7、設串s為“abcabaa”，試計算其next數組的值。j0123456rabcabaanext[j]-10001218、利用廣義表的head和tail操作寫出函數表達式，把以下各題中單元素banana從廣義表中分離出來。L1(apple,pear,banana,orange)L2((apple,pear),(banana,orange))L3(((apple),(pear),(banana),(orange)))L4((((apple),pear),banana),orange)L5(apple,(pear,(banana),orange))Head(Tail(Tail(Ll)))(l分)Head(Head(Tail(L2)))(1分)Head(Head(Tail(Tail(Head(L3)))))(1分)Head(Tail(Head(L4)))(1分)Head(Head(Tail(Head(Tail(L6)))))(1分)9、 設有序順序表中的元素依次為17,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對其進行折半搜索時的判定樹，并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。搜索成功的平均搜索長度為45/14（1分）搜索不成功的平均搜索長度為59/14（1分）10、已知一個待排序的關鍵字序列為｛56，36，22，86，72，10，28，48｝，請寫出快速排序每一趟排序的結果（寫出過程）。（5分）第1趟排序結果：48,36,22,28,10,56,72,86第2趟排序結果：10,36,22,28,48,56,72,86第3趟排序結果：10,36,22,28,48,56,72,86第4趟排序結果：10,22,28,36,48,56,72,86第5趟排序結果：10,22,28,36,48,56,72,8611、已知一個有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數組a[12]中，根據折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94,50時的比較次數。元素值345658639450比較次數21344412、已知一