1、15 小題，每小題 2分，共 30分）B.鏈表D.棧）B.n D.2n m，隊頭指針 front 指向隊頭元素，隊尾指針）B.front=(front+1)%m; D.rear=(rear+1)%m; ）B.多維數(shù)組D.線性表）B.串聯(lián)接D.求串長）B.( ) D.( ),( ),( ) ）B.結(jié)點均無右孩子的二叉樹15 小題，每小題 2分，共 30分）B.鏈表D.棧）B.n D.2n m，隊頭指針 front 指向隊頭元素，隊尾指針）B.front=(front+1)%m; D.rear=(rear+1)%m; ）B.多維數(shù)組D.線性表）B.串聯(lián)接D.求串長）B.( ) D.( ),( ),

2、( ) ）B.結(jié)點均無右孩子的二叉樹D.存在度為 2的結(jié)點的二叉樹l 的結(jié)點個數(shù)是）B.5 D.8 rear 指向隊尾元素的3，度為 2 的結(jié)點個數(shù)是4，則該二叉樹葉子結(jié)點的個數(shù)是匯總一、單項選擇題（本大題共在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列選項中與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的術(shù)語是（A.順序表C.鏈隊列2.將兩個各有 n 個元素的有序表歸并成一個有序表，最少的比較次數(shù)是（A.n-1 C.2n-1 3.已知循環(huán)隊列的存儲空間大小為下一個位置，則向隊列中插入新元素時，修改指針的操作是（A.rear=(rear-1)%m; C.

3、front=(front-1)%m; 4.遞歸實現(xiàn)或函數(shù)調(diào)用時，處理參數(shù)及返回地址，應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是（A.堆棧C.隊列5.設(shè)有兩個串 p和 q，其中 q 是p的子串，則求 q 在p中首次出現(xiàn)位置的算法稱為（A.求子串C.串匹配6.對于廣義表 A，若 head(A)等于 tail(A) ，則表 A為（A.( ) C.( ),( ) 7.若一棵具有 n(n0)個結(jié)點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是（A.結(jié)點均無左孩子的二叉樹C.高度為 n的二叉樹8.若一棵二叉樹中度為（A.4 C.7 ）B.V1,V3,V2,V4 D.V1,V2,V4,V3 O(n log n)的穩(wěn)定排序算

4、法是（B.堆排序D.冒泡排序）B.(30,18,22,46,51,75,83,68) D.(30,22,18,46,51,75,68,83) 395個，平均分成 5塊。若先對索引表采用順序查找，再對塊中元素進行）B.79 D.200 ）B.3 D.5 ）B.提高存儲效率D.方便文件的修改10 ）B.V1,V3,V2,V4 D.V1,V2,V4,V3 O(n log n)的穩(wěn)定排序算法是（B.堆排序D.冒泡排序）B.(30,18,22,46,51,75,83,68) D.(30,22,18,46,51,75,68,83) 395個，平均分成 5塊。若先對索引表采用順序查找，再對塊中元素進行）B.

5、79 D.200 ）B.3 D.5 ）B.提高存儲效率D.方便文件的修改10 小題，每小題 2分，共 20分）_三部分組成。_個結(jié)點指針域的值。a、b、c、d、e、f 依次進棧，得到的出棧序列是）b、d、c、f、e、A.圖的遍歷是從給定的源點出發(fā)對每一個頂點訪問且僅訪問一次B.圖的遍歷可以采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷C.圖的廣度優(yōu)先遍歷只適用于無向圖D.圖的深度優(yōu)先遍歷是一個遞歸過程10.已知有向圖 G=(V，E)，其中 V=V1 ，V2，V3，V4，E=， ，圖 G 的拓撲序列是（A.V1,V2,V3,V4 C.V1,V3,V4,V2 11.平均時間復(fù)雜度為A.快速排序C.歸并排序12.已

6、知關(guān)鍵字序列為 (51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關(guān)鍵字序列是（A.(18,22,30,46,51,68,75,83) C.(46,30,22,18,51,75,68,83) 13.某索引順序表共有元素順序查找，則在等概率情況下，分塊查找成功的平均查找長度是（A.43 C.198 14.在含有 10個關(guān)鍵字的 3階 B-樹中進行查找，至多訪問的結(jié)點個數(shù)為（A.2 C.4 15.ISAM 文件系統(tǒng)中采用多級索引的目的是（A.提高檢索效率C.減少數(shù)據(jù)的冗余二、填空題（本大題共請在每小題的空格中填上正確答案。錯填、不填均無分。16.數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)

7、的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的17.在單鏈表中某結(jié)點后插入一個新結(jié)點，需要修改18.設(shè)棧 S的初始狀態(tài)為空，若元素a，則棧 S的容量至少是 _。19.長度為零的串稱為 _。20.廣義表 G=(a,b，(c，d，(e，f)，G)的長度為 _。如果樹 T 中某個結(jié)點為葉子結(jié)點，_條邊。_大小不固定。4小題，每小題 5分，共 20分）EBACDFHG 如果樹 T 中某個結(jié)點為葉子結(jié)點，_條邊。_大小不固定。4小題，每小題 5分，共 20分）EBACDFHG ，25，96，11，63，57，78，44，請回答下列問題：；H(key)=key%11 將其散列到散列4 小題，每小題 5分，共 20分）f30

8、(int i,j,m; (i=1；in；i+) 則該結(jié)點在二叉鏈表中所對A， int n) 應(yīng)的結(jié)點一定是 _。22.一個有 n個頂點的無向連通圖，最少有23.當(dāng)待排關(guān)鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是 _。24.在一棵深度為 h 的具有 n 個結(jié)點 的二叉排序樹中，查找任一結(jié)點 的最多比較次數(shù)是_。25.不定長文件指的是文件的三、解答題（本大題共26.已知一棵二叉排序樹（結(jié)點值大小按字母順序）的前序遍歷序列為請回答下列問題：(1)畫出此二叉排序樹；(2)若將此二叉排序樹看作森林的二叉鏈表存儲，請畫出對應(yīng)的森林。27.已知有向圖的鄰接表如圖

9、所示，請回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點 A 出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。28.已知待排記錄的關(guān)鍵字序列為(1)畫出堆排序的初始堆（大根堆）(2)畫出第二次重建堆之后的堆。29.已知關(guān)鍵字序列為 (56，23，41，79，38，62，18)，用散列函數(shù)表 HT0.10 中，采用線性探測法處理沖突。請回答下列問題：(1)畫出散列存儲后的散列表：(2)求在等概率情況下查找成功的平均查找長度。四、算法閱讀題（本大題共30.閱讀下列程序。void int for for (j=0；jlchild; (!StackEmpty(S) printf( “%c”,T-data); 3

10、59|T=T-rchild; 6!StackEmpty(S) ，將其按行優(yōu)先存于一維數(shù)組A；248左右孩子指針*BinTree；S (T (T) T=T-lchild; (!StackEmpty(S) printf( “%c”,T-data); 359|T=T-rchild; 6!StackEmpty(S) ，將其按行優(yōu)先存于一維數(shù)組A 中，給出執(zhí)行函數(shù)調(diào)Aj*n+i=m ； 回答下列問題：1(1)已知矩陣 B=7用 f30(A，3)后矩陣 B的值；(2)簡述函數(shù) f30 的功能。31.假設(shè)以二叉鏈表表示二叉樹，其類型定義如下：typedef struct node char data; st

11、ruct node*Ichild, *rchild; 閱讀下列程序。void f31(BinTree T) InitStack(S); 初始化一個堆棧while while Push(S,T); if T=Pop(S); 回答下列問題：(1)已知以 T 為根指針的二叉樹如圖所示，請寫出執(zhí)行 f31(T)的輸出結(jié)果：f32(int i,j,m=l,t ；(i=0; (j=0； jAj) A =34,26,15,89,42 ，寫出執(zhí)行函數(shù)調(diào)用SqListMAXLEN; f33(SqList int m; return -1; f32(int i,j,m=l,t ；(i=0; (j=0； jAj)

12、A =34,26,15,89,42 ，寫出執(zhí)行函數(shù)調(diào)用SqListMAXLEN; f33(SqList int m; return -1; A,int in-l&m; jq) return m; return f33(R,X,p,m-l); R 的關(guān)鍵字序列為 (2,5，13,26,55,80,105)，分別寫出 X.key=18 和 X.key=26return m; return f33(R,X,p,m-l); R 的關(guān)鍵字序列為 (2,5，13,26,55,80,105)，分別寫出 X.key=18 和 X.key=26 時，f33(R,X,0,6) 的函數(shù)返回值。10 分）head的單

13、循環(huán)鏈表中0，并給出所寫算法的時間復(fù)雜度。函數(shù)原型為：f34(LinkList 15小題，每小題 2分，共30分）( ( B.帶頭結(jié)點的單向鏈表D.帶頭結(jié)點的單循環(huán)鏈表data域值為正整數(shù)的結(jié)點個數(shù)占結(jié)點總數(shù)的比例，head): ) ) if (Rm.key=X.key) if (Rm.keyX.key) else return f33(R,X,m+l,q); 請回答下列問題：(1)若有序的順序表執(zhí)行函數(shù)調(diào)用(2)簡述算法 f33 的功能。五、算法設(shè)計題（本題34.假設(shè)用帶頭結(jié)點的單循環(huán)鏈表表示線性表，單鏈表的類型定義如下：typedef struct node int data; struc

14、t node*next; LinkNode ，*LinkList; 編寫程序，求頭指針為若為空表輸出float 全國 2010年 10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331 一、單項選擇題（本大題共在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.數(shù)據(jù)的四種存儲結(jié)構(gòu)是A.順序存儲結(jié)構(gòu)、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)B.線性存儲結(jié)構(gòu)、非線性存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)和圖型存儲結(jié)構(gòu)C.集合存儲結(jié)構(gòu)、一對一存儲結(jié)構(gòu)、一對多存儲結(jié)構(gòu)和多對多存儲結(jié)構(gòu)D.順序存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)2.若對某線性表最

15、常用的操作是在最后一個結(jié)點之后插入一個新結(jié)點或刪除最后一個結(jié)點，要使操作時間最少，下列選項中，應(yīng)選擇的存儲結(jié)構(gòu)是A.無頭結(jié)點的單向鏈表C.帶頭結(jié)點的雙循環(huán)鏈表head，則判斷鏈表是否為空的條件是B.head-next=NULL D.head-next!=head 1，2，3.，n，如果第 2個出棧的元素是 n，則輸出的第 i(1=inext=NULL D.head-next!=head 1，2，3.，n，如果第 2個出棧的元素是 n，則輸出的第 i(1=i=n) 個元素是) B.n-i+l D.無法確定( B.串比較D.子串鏈接a11為第一個元素，其存儲地址為a85的地址為 ( B.18 D.

16、40 ( B.樹中只有一個根結(jié)點D.樹中非葉結(jié)點均只有右子樹( B. +1 ( B.克魯斯卡爾（ Kruskal）算法D.廣度優(yōu)先遍歷 (BFS)算法G的最小生成樹的權(quán)為( ( ) 1，每個) ) ) D.n/2 ) ( ) ) ) A.head=NULL C.head!=NULL 4.若元素的入棧順序為( A.n-i C.n-i+2 5.串匹配算法的本質(zhì)是A.串復(fù)制C.子串定位6.設(shè)有一個 10階的對稱矩陣 A，采用行優(yōu)先壓縮存儲方式，元素占一個字節(jié)空間，則A.13 C.33 7.若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是A.樹中沒有度為 2的結(jié)點C.樹中非葉結(jié)點均

17、只有左子樹8.若根結(jié)點的層數(shù)為 1，則具有 n個結(jié)點的二叉樹的最大高度是A.n C. 9.在圖G中求兩個結(jié)點之間的最短路徑可以采用的算法是A.迪杰斯特拉（ Dijkstra ）算法C.普里姆 (Prim)算法10.下圖G=(V,E) 是一個帶權(quán)連通圖，A.15 B.16 C.17 D.18 11.在下圖中，從頂點 1出發(fā)進行深度優(yōu)先遍歷可得到的序列是A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 ( B.穩(wěn)定的D.基于選擇的1的鏈中記錄個數(shù)為 ( B.2 D.4 ( ( B.索引文件D.倒排文件10小題，每小題 2

18、分，共 20分）_。( B.穩(wěn)定的D.基于選擇的1的鏈中記錄個數(shù)為 ( B.2 D.4 ( ( B.索引文件D.倒排文件10小題，每小題 2分，共 20分）_。node *next; ) ) ) ) A.不穩(wěn)定的C.基于交換的13.設(shè)有一組關(guān)鍵字 (19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函數(shù) H(key)=key%13 構(gòu)造散列表，用拉鏈法解決沖突，散列地址為A.1 C.3 14.已知二叉樹結(jié)點關(guān)鍵字類型為字符，下列二叉樹中符合二叉排序樹性質(zhì)的是15.若需高效地查詢多關(guān)鍵字文件，可以采用的文件組織方式為A.順序文件C.散列文件二、填空題（本大題共請

19、每小題的空格中填上正確答案。錯填、不填均無分。16.下面程序段的時間復(fù)雜度為sum=1；for（i=0；sumn;i+）sum+=1；17.已知鏈表結(jié)點定義如下：typedef struct char data16；struct node LinkStrNode ；_。front等于隊尾指針 rear時表示隊空。若為_。0元素的個數(shù)為 _。_次數(shù)和記錄的移動次數(shù)。_個關(guān)鍵字。_。_。4小題，每小題 5分，共20分）_。front等于隊尾指針 rear時表示隊空。若為_。0元素的個數(shù)為 _。_次數(shù)和記錄的移動次數(shù)。_個關(guān)鍵字。_。_。4小題，每小題 5分，共20分）stackl和stack2，請

20、回答：front=8，rear=7，則隊列中的18.使用一個 100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針元素個數(shù)為 _。19.3個結(jié)點可以組成 _種不同樹型的二叉樹。20.用5個權(quán)值 3, 2，4，5，1構(gòu)造的哈夫曼 (Huffman) 樹的帶權(quán)路徑長度是21.若無向圖 G中有n個頂點m條邊，采用鄰接矩陣存儲，則該矩陣中非22.影響排序效率的兩個因素是關(guān)鍵字的23.對任一m階的B樹，每個結(jié)點中最多包含24.若兩個關(guān)鍵字通過散列函數(shù)映射到同一個散列地址，這種現(xiàn)象稱為25.如果要為文件中的每個記錄建立一個索引項，則這樣建立的索引表稱為三、解答題（本大題共26.要在0.n-l的向量空間中建立兩個棧(1)應(yīng)該如何設(shè)計這兩個棧才能充分利用整個向量空間？(2)若stackl的棧頂指針為 topl,stack2的棧頂指針為 top2，如果需要充分利用整個向量空間，則：棧stackl空的條件是： _；棧stack2空的條