全國自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題02331試題及答案

1、第 第24頁2011 1 數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題（本大題共 15 小題，每小題 2 分，共 30 分）選均無分。下列選項中與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的術(shù)語是（D）P3C.鏈隊列D.棧將兩個各有n 個元素的有序表歸并成一個有序表，最少的比較次數(shù)是（B）A.n-1C.2n-1B.n D.2n已知循環(huán)隊列的存儲空間大小為front rear 向隊列中插入新元素時，修改指針的操作是（D）A.rear=(rear-1)%m; C.front=(front-1)%m;B.front=(front+1)%m; D.rear=(rear+1)%m;遞歸實現(xiàn)或函數(shù)調(diào)用時，處理參數(shù)及返回地址，應(yīng)采

2、用的數(shù)據(jù)結(jié)構(gòu)是（A）C.隊列D.線性表設(shè)有兩個串p 和q，其中q 是p 的子串，則求q 在p 中首次出現(xiàn)位置的算法稱為（C）C.串匹配串聯(lián)接D.對于廣義表A，若head(A)等于tail(A)，則表A 為（B）P67A.( ) C.( ),( B.( )D.( ),( ),( )若一棵具有n(n0)個結(jié)點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是（C）C.高度為n 的二叉樹結(jié)點均無右孩子的二叉樹 D.2 若一棵二叉樹中度為l 的結(jié)點個數(shù)是3，度為2 的結(jié)點個數(shù)是4，則該二叉樹葉子結(jié)點的個數(shù)是（B）P73A.4C.7下列敘述中錯誤的是（C）B.5D.8圖的遍歷是從給定的源點出發(fā)對每一

3、個頂點訪問且僅訪問一次B.圖的遍歷可以采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷C.圖的廣度優(yōu)先遍歷只適用于無向圖D.圖的深度優(yōu)先遍歷是一個遞歸過程10.已知有向圖其中 V4，圖G 的拓?fù)湫蛄惺牵ǎ〢.V1,V2,V3,V4C.V1,V3,V4,V2B.V1,V3,V2,V4D.V1,V2,V4,V3平均時間復(fù)雜度為O(n log 的穩(wěn)定排序算法是（C）P136 P164 8-2C.歸并排序堆排序 D.(51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關(guān)鍵字序列是（D）A.(18,22,30,46,51,68,75,83)C.(46,30,22,18,51,75,68

4、,83)B.(30,18,22,46,51,75,83,68)D.(30,22,18,46,51,75,68,83)某索引順序表共有元素395 個，平均分成5 塊。若先對索引表采用順序查找，再對塊中元素進行順序查找，則等概率情況下，分塊查找成功的平均查找長度是（A）A.43 C.198B.79 D.200在含有10個關(guān)鍵字的3階B-樹中進行查找，至多訪問的結(jié)點個數(shù)為（B即B-樹的高度A.2B.3C.4D.5ISAM 文件系統(tǒng)中采用多級索引的目的是（A）P213提高檢索效率 C.提高存儲效率 D.二、填空題（本大題共 10 小題，每小題 2 分，共 20 分）請在每小題的空格中填上正確答案。錯填

5、、不填均無分。數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算三部分組成。在單鏈表中某結(jié)點后插入一個新結(jié)點，需要修2個結(jié)點指針域的值。設(shè)棧S 的初始狀態(tài)為空，若元素、c、f 依次進棧，得到的出棧序列是、c、e、a，則棧S 的容量至少3。長度為零的串稱空。廣義表G=(a,b，(c，d，(e，f)，G)的長度4。一棵樹 T 采用孩子兄弟鏈表存儲，如果樹T 中某個結(jié)點為葉子結(jié)點，則該結(jié)點在二叉鏈表中所對應(yīng)的結(jié)點一是左右指針域均為。一個有n 個頂點的無向連通圖，最少n-1條邊。當(dāng)待排關(guān)鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是 直接插入排。在一棵深度為h 的具

6、有n 個結(jié)點的二叉排序樹中，查找任一結(jié)點的最多比較次數(shù)h。不定長文件指的是文件記錄含有的信息長大小不固定。三、解答題（本大題共 4 小題，每小題 5 分，共 20 分）已知一棵二叉排序樹（結(jié)點值大小按字母順序）的前序遍歷序列為請回答下列問題：畫出此二叉排序樹；若將此二叉排序樹看作森林的二叉鏈表存儲，請畫出對應(yīng)的森林。(1)給出該圖的鄰接矩陣；(2)從結(jié)點A 出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。(1畫出堆排序的初始堆（大根堆；(2)畫出第二次重建堆之后的堆。29.已知關(guān)鍵字序列為(56，23，41，79，38，62，18)，用散列函數(shù)H(key)=key%11 將其散列到散列表HT0.10中， 采

7、用線性探測法處理沖突。請回答下列問題：畫出散列存儲后的散列表：求在等概率情況下查找成功的平均查找長度。四、算法閱讀題（4 5 20 分30.閱讀下列程序。voidf30(intA， intn)inti,j,m;for(i=1；in；i+)for(j=0；jlchild;if(!StackEmpty(S)T=Pop(S);printf(“%c”,T-data);T=T-rchild;回答下列問題：已知以T 請寫出執(zhí)行f31(T)的輸出結(jié)果：簡述算法f31的功能。閱讀下列程序。voidf32(intA,intn)inti,j,m=l,t；for(i=0;in-l&m;i+)for(j=0； jn；

8、 j+) printf(“%d printf(“n”); m=0：for(j=1;jAj)t=Aj-l;Aj-1=Aj；Aj=t； m=1；回答問題：已知整型數(shù)組A =34,26,15,89,42，寫出執(zhí)行函數(shù)調(diào)用f32(A,5)后的輸出結(jié)果。#define MAXLEN 100typedef int KeyType;typedef struct KeyType key; InfoType otherinfo; NodeType；typedef NodeTypeSqListMAXLEN;閱讀下列程序。Intf33(SqListR，NodeTypeX,intp,intq)intm;if(pq)r

9、eturnm=(p+q)2；if(Rm.key=X.key)returnm;if(Rm.keyX.key)return elsereturn f33(R,X,m+l,q);請回答下列問題：若有序的順序表 R (2,5，13,26,55,80,105)，分別寫出 X.key=18 和 X.key=26 時，執(zhí)行函數(shù)調(diào)用f33(R,X,0,6)的函數(shù)返回值。(2)簡述算法f33 的功能。五、算法設(shè)計題（本題 10 分）typedef struct node int data;struct node*next;LinkNode，*LinkList;head 的單循環(huán)鏈表中data 域值為正整數(shù)的結(jié)點

10、個數(shù)占結(jié)點總數(shù)的比例并給出所寫算法的時間復(fù)雜度。函數(shù)原型為：floatf34(LinkListhead):2010 10 月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題（本大題共15小題，每小題2分，共30分）選均無分。數(shù)據(jù)的四種存儲結(jié)構(gòu)(A)順序存儲結(jié)構(gòu)、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu) B.C.D.順序存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)若對某線性表最常用的操作是在最后一個結(jié)點之后插入一個新結(jié)點或刪除最后一個結(jié)點，要使操作時間最少，列選項中，應(yīng)選擇的存儲結(jié)構(gòu)(C)無頭結(jié)點的單向鏈表 O(N) C.帶頭結(jié)點的單向鏈表 O(N) D.若帶頭結(jié)點的單鏈表的頭指針h

11、ead，則判斷鏈表是否為空的條件(BA.head=NULLB.head-next=NULLC.head!=NULLD.head-next!=head若元素的入棧順序1，2，3，n，如果個出棧的元素n，則輸出的i(1=i=n)個元素(D)A.n-iB.n-i+lC.n-i+25.串匹配算法的本質(zhì)是( A.串復(fù)制C.子串定位CD.無法確定)B.串比較 D.設(shè)有一10階的對稱矩A，采用行優(yōu)先壓縮存儲方式為第一個元素，其存儲地址1，每個元素占一個字節(jié)11空間，a的地址(C)85A.13B.18C.33D.40若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀(BA.樹中沒有度的結(jié)點B.

12、樹中只有一個根結(jié)點C.樹中非葉結(jié)點均只有左子樹D.樹中非葉結(jié)點均只有右子8.若根結(jié)點的層數(shù)1，則具個結(jié)點的二叉樹的最大高度(A) A.nB. C. +1完全二叉樹)D.n/2在G中求兩個結(jié)點之間的最短路徑可以采用的算法(A)A.迪杰斯特拉（Dijkstra）算法B.克魯斯卡爾算C.普里(Prim)算法D.廣度優(yōu)先遍(BFS)算法（BC為求最小生成樹）下G=(V,E)是一個帶權(quán)連通圖的最小生成樹的權(quán)(DA.15B.16 C.17 D.18在下圖中，從頂1出發(fā)進行深度優(yōu)先遍歷可得到的序列(BA.1 2 3 4 5 6 7B.1 4 2 6 3 7 5C.1 4 2 5 3 6 7D.1 2 4 6

13、 5 3 7如果在排序過程中不改變關(guān)鍵字相同元素的相對位置，則認(rèn)為該排序方法(B)不穩(wěn)定的 C.穩(wěn)定的D.基于選擇的13.設(shè)有一組關(guān)鍵(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 用散列函H(key)=key%13構(gòu)造散列表，用拉鏈法解決沖突，散列地址1的鏈中記錄個數(shù)(C)A.1B.2C.3D.4已知二叉樹結(jié)點關(guān)鍵字類型為字符，下列二叉樹中符合二叉排序樹性質(zhì)的(D)若需高效地查詢多關(guān)鍵字文件，可以采用的文件組織方式(DA.順序文件B.索引文件C.散列文件D.倒排文件二、填空題（本大題共10小題，每小題2分，共20分）請每小題的空格中填上正確答案。錯填、不填均無分。下

14、面程序段的時間復(fù)雜度sum=1；for（i=0；sumn;i+） sum+=1；已知鏈表結(jié)點定義如下typedefstructnodechardata16； struct node LinkStrNode；如果每個字符1個字節(jié)，指針4個字節(jié)，則該鏈表的存儲密度。使用一100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，定隊頭指front等于隊尾指rear時表示隊空。若front=8，rear=7，則隊列中的元素個數(shù)。19.3個結(jié)點可以組種不同樹型的二叉樹。用個權(quán)3, 2，4，5，1構(gòu)造的哈夫(Huffman)樹的帶權(quán)路徑長度。若無向G中n個頂條邊，采用鄰接

15、矩陣存儲，則該矩陣中元素的個數(shù)。影響排序效率的兩個因素是關(guān)鍵字次數(shù)和記錄的移動次數(shù)。對任階B樹，每個結(jié)點中最多包個關(guān)鍵字。若兩個關(guān)鍵字通過散列函數(shù)映射到同一個散列地址，這種現(xiàn)象稱。如果要為文件中的每個記錄建立一個索引項，則這樣建立的索引表稱。三、解答題（本大題共4小題，每小題5分，共20分）stackl和stack2(1)應(yīng)該如何設(shè)計這兩個棧才能充分利用整個向量空間？的棧頂指針top2，如果需要充分利用整個向量空間，則棧stackl空的條件是；棧stack2空的條件是；棧stackl和棧stack2滿的條件是。A=(B,y)B=(x，L)L=(a，b)要求：寫出下列操作的結(jié)果tail(A)=.

16、 head(B)=A對應(yīng)的圖形表示。已知二叉樹如下：請畫出該二叉樹對應(yīng)的森林。請回答下列問題：DAG的中文含義是什么？DAG圖的全部拓?fù)渑判?。四、算法閱讀題（本大題共4小題，每小題5分，共20分）00(x,x,-x,-x,x,x,-x)，變換后數(shù)組中保存的序列是(-x,-x,-x,x,x,x,x)。請在程序處填入合適的內(nèi)容，使其成為完整的算法。f30(int a，int n)intm=(1)while(am0 m=(2)；k=m;while(kn)k=(3)；if(kn)temp=ak； ak=am； am=(4)m=(5)；(1)(2)閱讀下列程序，并回答問題： #include subst

17、r(char*t,char*s,int pos,int while（len0&*s）*t=*(s+pos-l);t+;s+;len-;*t=0;char*f31(char*s)chart100;ifreturns;substr(t,s,1,1); substr(s,s,2,strlen(s)-1); f31(s);return strcat(s,t);main( )char str100= String;printf(%sn,f31(str);(2)f31的功能。下面程序?qū)崿F(xiàn)插入排序算法typedefstructintkey;Infootherinfo;SeqList;voidInsertSo

18、rt(SeqListR,intn)/* 待排序列保存R1.n中SeqListx；intfor(1)；lo=1；hi=i-l;while(lox.key)elselo=mi+l;if(mi=lo)k=i - elsek=i - mi-1;for(j=0；jdataA&head-datanext;if(p !=NULL)printf(%dn,p-data);f33(h，5，8)之后的輸出結(jié)果；f33的功能。五、算法設(shè)計題（本題10分）已知二叉樹的定義如下typedefstructnodeintdata;structnode*lchild,*rchild;*Bitptr；編寫遞歸算法求二叉樹的高度。

19、函數(shù)原型為f34（Bitptrt）；2010 1 月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題(本大題共 15 小題，每小題 2 分，共 30 分)選均無分。若一個算法的時間復(fù)雜度用T(n)表示，其中n 的含義是（A ）問題規(guī)模語句條數(shù)C循環(huán)層數(shù)函數(shù)數(shù)量具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（C ）樹B圖C棧和隊列D廣義表將長度為n 的單鏈表連接在長度為m 的單鏈表之后，其算法的時間復(fù)雜度為（B ）AO(1)BO(m)CO(n)DO(m+n)在帶頭結(jié)點的雙向循環(huán)鏈表中插入一個新結(jié)點，需要修改的指針域數(shù)量是（C ）A2個B3個C4個D6個假設(shè)以數(shù)組 A60存放循環(huán)隊列的元素，其頭指針是 front

20、=47，當(dāng)前隊列有 50 個元素，則隊列的尾指針值為（B ）A3B37C50D97若棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則下列說法中正確的是（B A需要判斷棧滿且需要判斷?？?B不需要判斷棧滿但需要判斷?？?C需要判斷棧滿但不需要判斷?？?D不需要判斷棧滿也不需要判斷?？杖舸畇tr=”Software”，其子串的數(shù)目是（D ）A8B9C36D37設(shè)有一個10 階的下三角矩陣A， 為第一個元素，其存儲地址為1000，每個元素占ll一個地址單元，則a 的地址為（C ）85A1012B1017C1032D1039允許結(jié)點共享的廣義表稱為（ D）純表線性表C遞歸表再入表下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（A ）AB樹B

21、AVL樹C二叉排序樹D哈夫曼樹對下面有向圖給出了四種可能的拓?fù)湫蛄校渲械氖牵– ）A1，5，2，6，3，4B1，5，6，2，3，4C5，1，6，3，4，2D5，1，2，6，4，3以v1 為起始結(jié)點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（D ）Av1，v2，v3，v4，v5，v6，v7 Cv1，v2，v3，v4，v7，v5，v6 13下列排序算法中不穩(wěn)定的是（ A）A快速排序B歸并排序C冒泡排序D直接插入排序14一個有序表(1，3，9，12，32，41，45，62，75，77，82，95，100)，當(dāng)采用折半查找方法查找值 32 時， 查找成功需要的比較次數(shù)是（ B）A2B3C4D8采用IS

22、AM 組織文件的方式屬于（D ）A鏈組織順序組織C散列組織索引組織二、填空題(本大題共 10 小題，每小題 2 分，共 20 分)請在每小題的空格中填上正確答案。錯填、不填均無分。數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示稱數(shù)據(jù)的存儲結(jié)構(gòu)。長度為n 的線性表采用單鏈表結(jié)構(gòu)存儲時，在等概率情況下查找第i 個元素的時間復(fù)雜度。下面是在順序棧上實現(xiàn)的一個?；静僮鳎摬僮鞯墓δ苋ｍ斣豞typedef structDataType data100； int top；SeqStack；DataType f18(SeqStack*S)if(StackEmpty(S)Error(”Stack is empt

23、y”)；return S-dataS-top；在串匹配中，一般將主串稱為目標(biāo)串，將子串稱模式串。 20已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)=（c）用 6 個權(quán)值分別為 6、13、18、30、7 和 16 的結(jié)點構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長度為 219。已知有向圖如下所示，其中頂點A 到頂點C 的最短路徑長度35。對序進行基數(shù)排序第一趟排序后的結(jié)果42,13,94,55,05,46,17。高度為3的3階B-樹最少的關(guān)鍵字總數(shù)7。VSAM 通常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動態(tài)索引結(jié)構(gòu)采用的樹。三、解答題(本大題共 4 小題，每小題

24、 5 分，共 20 分)假設(shè)二叉樹的RNL 遍歷算法定義如下： (1)遍歷右子樹；(2)訪問根節(jié)點； (3)遍歷左子樹。已知一棵二叉樹如圖所示，請給出其RNL 遍歷的結(jié)果序列。（GCFABD）已知一個無向圖G=(V，E)，其中V=A，B，C，D，E，F(xiàn)，鄰接矩陣表示如下所示。請回答下列問題：請畫出對應(yīng)的圖G。畫出圖G(參考書 P104)28給出初始建堆后的序列。（12,15,14,18,16,36,18,60,25,85）請回答下列問題：2357（在二叉排序樹中對于插入元素，直接插入即可，刪除元素時是刪除其中序遍歷的后繼）四、算法閱讀題(本大題共 4 小題，每小題 5 分，共 20 分)Typ

25、edefstruct node DataType data; struct node * * LinkList;void f30( LinkList Ls )LinkList p, q;q = Ls-next;if ( q & q-next ) Ls-next = q-next; p=qwhile ( p-next ) p = p-next;p-next = q;q-next = NULL;請回答下列問題：當(dāng)Ls請簡述算法的功能。23451將單鏈表中第一個結(jié)點連接到原鏈表中最后一個結(jié)點已知字符串處理函數(shù)f31int f31(char*strl，char*str2) while(*strl=*s

26、tr2&(*strl!=0)strl+； str2+；return(*strl-*str2 ? l0)；請回答下列問題：f31(”abcde”abcdf)f31(”abcde”，”abcde”)，簡述該函數(shù)的功能。（1）1,0（2）比較兩個字符串，相等返回 0，不相等返回 1.數(shù)組A中存儲有nvoid f32(intA，int n) inti，j，k，x； k=n-l； while(k0)i=k； k=0； for(j=O；jAj+1)x=Aj； Aj=Aj+l； Aj+1=x； k=j；end of ifend of while return；請回答下列問題：(1)當(dāng) A=10，8，2，4，

27、6，7時，執(zhí)行f32(A，6)后，數(shù)組A 中存儲的結(jié)果是什么? (2)說明該算法的功能。（1）A【】=2,4,6,7,8,10（2）將數(shù)組中的數(shù)據(jù)按從小到大排列Typedef structKeyType InfoType SeqListN+1；int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n； while(1)if(2)return mid； if(RmidkeyK)high=mid-1； else(3)；return O； BinSearch請在空白處填寫適當(dāng)內(nèi)容，使該程序功能完整。(1)lowlchild)+ SumNOd

28、e (T-rchild)+1;2009 10 月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題（本大題共 15 小題，每小題 2 分，共 30 分）選均無分。按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是（ C）A靜態(tài)類型和動態(tài)類型C原子類型和結(jié)構(gòu)類型B原子類型和表類型D數(shù)組類型和指針類型2對于三個函數(shù) f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008 和 h(n)=8888nlogn+3n2 成立的是（ C）Af(n) 是 0(g(n) Ch(n)Bg(n)Dh(n)0(n2)指針q 和r 依次指向某循環(huán)鏈表中三個相鄰的結(jié)點交換結(jié)*q 和結(jié)*r 在表中次序的

29、程序段（ A）Ap-next=r； q-next=r-next； Bp-next=r； r-next=q； q-next=r-next； Cr-next=q； q-next=r-next； p-next=r； Dr-next=q； p-next=r； 若進棧次序為a，b，c，且進棧和出棧可以穿插進行，則可能出現(xiàn)的含3 個元素的出棧序列個數(shù)是（B）A3 C6B5 D75假設(shè)以數(shù)組 An存放循環(huán)隊列的元素，其頭指針front 指向隊頭元素的前一個位置、尾指針rear 指向隊尾素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為（D）Arear= =frontB(front+1)n=

30、=rearCrear+1= =front 6串的操作函數(shù)str intstr(char*s)char*p=s；while(*p！=0)p+；return p-s；D(rear+1)n= =front則str(abcde)的返回值是（C）A3 C5B4 D6二維數(shù)組16采用行優(yōu)先的存儲方法，若每個元素占4個存儲單元，已知元素34的存儲地為100，則元素A43的存儲地址為（A）A1020 C1036B1024 D1240對廣義表L= (a，()執(zhí)行操作tail(L)的結(jié)果是（ B）A()CaB()D(a)已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（ A）AFEDCBA

31、CFDECBAF=T ，T ，T BABCDEF DFBDCEA，T ，各棵樹 T (i=1，2，3，4，5)中所含結(jié)點的個數(shù)分別為 7，3，5，l，2，則12345i與F 對應(yīng)的二叉樹的右子樹中的結(jié)點個數(shù)為（D）A2C8B3D11若連通無向圖G 含有21 條邊，則G 的頂點個數(shù)至少為（B）AA7B8C21D2212如圖所示的有向圖的拓?fù)湫蛄惺牵˙）Ac，d，b，a，eBc，a，d，b，eCc，d，e，a，bDc，a，b，d，e13對關(guān)鍵字序進行快速排序時，以第1 個元素為基準(zhǔn)的一次劃分的結(jié)果為（ C）A(5，1，4，3，6，2，8，7)B(5，1，4，3，2，6，7，8)C(5，1，4，3，

32、2，6，8，7)14分塊查找方法將表分為多塊，并要求（ B）C各塊等長塊間有序D便于進行布爾查詢的文件組織方式是（D）C散列文件索 引 文 件 D二、填空題（10 2 1 20 分請在每個空格中填上正確答案。錯填、不填均無分。數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是借指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。如果需要對線性表頻繁進插入_刪除操作，則不宜采用順序存儲結(jié)構(gòu)。top1=02 為空的條件是top2=n-1，則“棧滿 top2+1=top1。同的棧。其中棧 1 為空的條的 判 定 條 件 是靜態(tài)存儲分配的順序串在進行插入、置換鏈接_等操作時可能發(fā)生越界。20廣義表L（，( ）的深度 3 。任意一棵完全二叉樹中，

33、度為1 的結(jié)點數(shù)最多_1。求最小生成樹的克魯斯卡(Kruskal)算法耗用的時間與圖邊的數(shù)目正相關(guān)。在5 階B-樹中，每個結(jié)點至多含4 個關(guān)鍵字，除根結(jié)點之外，其他結(jié)點至少2個關(guān)鍵字。若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法穩(wěn)定_的。常用的索引順序文件ISAM文件VSAM文件。三、解答題(本大題共 4 小題，每小題 5 分，共 20 分)如圖所示，在nn 矩陣A 中，所有下標(biāo)值滿足關(guān)系式i+jn+l 的元素a 0，現(xiàn)將A 中其它元素按行ij優(yōu)先順序依次存儲到長度為n(n+1)/2的一維數(shù)組sa中，其中元素a存儲在s。1，n設(shè)n=1，元素a存儲在s，寫出下標(biāo)p 的值；4，

34、9設(shè)元素a存儲在sak中，寫出由i,j 和n 計算k 的一般公式。i，j8aij=i(i-1)/2+i-n+j-1由字符集s，t，a，e，I及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進行譯碼，寫出原來的電文。eatst已知無向圖G 的鄰接表如圖所示，畫出該無向圖；畫出該圖的廣度優(yōu)先生成森林。29()后的序列狀態(tài)。初始堆：(96,55,63,48,22,31,50,37,11)1趟：(63,55,50,48,22,31,11,37,96)2趟：(55,48,50,37,22.31,11,63,96)4 5 20 分30閱讀下

35、列算法，并回答問題：第 25 頁無向圖G 第 25 頁第 第52頁簡述算法f30 的功能。#define MaxNum 20 int visitedMaxNum；void DFS(Graph *g，int i)；/*從頂點 v 出發(fā)進行深度優(yōu)先搜索，訪問頂點v 時置visitedj為 1*/ijint f30(Graph *g) int i，k；for(i=0； in； i+)*g-n為圖g visitedi=0；for(i=k=0； in;if(visitedi= =0)k+； return k；(1)3(2)返回圖中連通分量的個數(shù)假設(shè)學(xué)生成績按學(xué)號增序存儲在帶頭結(jié)點的單鏈表中，類型定義如下

36、typedefstructNodeintid;學(xué)號*/intscore；成績structNode*next；LNode， *LinkList； 閱讀算法f31設(shè)結(jié)點結(jié)構(gòu)為，成績鏈表A 和B 如圖所示，畫出執(zhí)行算法f31(A，B)后A 所指的鏈表；簡述算法f31的功能。voidf31(LinkList A,LinkList B)LinkListp, p=A-next; q=B-next;while(p & q)if(p-idid)p=p-next;elseif q=q-next;elseif(p-scorescorescore=q-score; else p-score=60;p=p-next;

37、 q=q-next;鏈 A 鏈 B 中相同學(xué)號的成績均小于 60 的把 B 的成績賦給 A，B 中大于 A 的將 A 中的成績改為 60閱讀下列算法，并回答問題：設(shè)串sOneWorldOneDreatOnpos是一維整型數(shù)組，寫出算法 f32(s，t，pos)執(zhí)行之后得到的返回值和pos 中的值；簡述算法f32 的功能。intstrlen(char*s)； 返回串s 的長intindex(char*st，char*t)；若串t 在串st 中出現(xiàn)，則返回在串st 中首次出現(xiàn)的下標(biāo)值，否則返intf32(char*s, char*t, int inti, j, k, ls, ls=strlen(s

38、); 1t=strlen(t);if(ls= =0|1t= =0)k=0;i=0;do j=index(s+i, if(j=0)posk+=i+j;i+=j+1t;while(i+1t1child, x);if (p!=NULL)return p; if (T-keyx)return T; return f33(T- rchild, （1）10（2）a 空樹 b 當(dāng)樹中所有值都小于 X 的時候（3）在二叉排序樹中找第一次出現(xiàn)比 X 大的結(jié)點，若沒有找到返回空指針。五、算法設(shè)計題（本題 10 分） 34#defineListSizetypedefstructintdataListSize;int

39、length;SeqList,*Table;編寫算法，將順序表L 中所有值為奇數(shù)的元素調(diào)整到表的前端。voil f34(Table L)int i=0,j=0,t; for(i=0;Llength;i+)if(L-datai%2=1)if(i!=j)t=L-dataiL-datai=L-dataj L-dataj=t j+;2009 1 月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題(本大題共 15 小題，每小題 2 分，共 30 分)選均無分。下列程序段的時間復(fù)雜度(Ds=0；for(i=1；in；i+) for(j=1；jnext=NULL；head!=NULL；D.head-n

40、ext=head；棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征(BA.先進先出 B.后進先出C.進優(yōu)于出 D.出優(yōu)于進假設(shè)以數(shù)組An存放循環(huán)隊列的元素，其頭、尾指針分別為front 和rear。若設(shè)定尾指針指向隊列中的隊元素，頭指針指向隊列中隊頭元素的前一個位置，則當(dāng)前存于隊列中的元素個數(shù)(D)A.(rear-front-1)n C.(front-rear+1)nB.(rear-front)n D.(rear-front+n)n判斷兩個串大小的基本準(zhǔn)則(D)A.兩個串長度的大小 B.兩個串中首字符的大小C.兩個串中大寫字母的多少D.對應(yīng)的第一個不等字符的大小二維數(shù)組A45按行優(yōu)先順序存儲若每個

41、元素占2 個存儲單元且第一個元素A00的存儲地址為則數(shù)組元素A32的存儲地址(C)A.1012B.1017 C.1034高度為5 的完全二叉樹中含有的結(jié)點數(shù)至少(A)A.16 C.31B.17 D.32已知在一棵度為3 的樹中度為2 的結(jié)點數(shù)為度為3 的結(jié)點數(shù)為則該樹中的葉子結(jié)點數(shù)(C)A.5 B.8 C.11D.18下列所示各圖中是中序線索化二叉樹的(A)6 (v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如圖所示，則從頂點v0 出發(fā)進行深度優(yōu)先遍歷可能得到的頂點訪問序列為(A)A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5

42、，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.如圖所示有向圖的一個拓?fù)湫蛄惺?A.ABCDEFB)B.FCBEADC.FEDCBAD.DAEBCF下列關(guān)鍵字序列中，構(gòu)成大根堆的(D)A.5，8，1，3，9，6，2，7 C.9，8，6，3，5，l，2，7B.9，8，1，7，5，6，2，33 D.9，8，6，7，5，1，2，315 的有序順序表進行二分查找，在各記錄的查找概率均相等的情況下，查找成功時所需進行的關(guān)鍵字比較次數(shù)的平均值(B)39A.1551C.1549B.1555D.15已知一個散列表如圖所示，其散列函數(shù)為 H(key)=key11，采用二次探查法處理沖突，則下

43、一個插入的鍵字49 的地址(D)數(shù)據(jù)庫文件是由大量帶有結(jié)構(gòu)(AA.記錄組成的集合B.字符組成的集合C.數(shù)據(jù)項組成的集合 D.數(shù)據(jù)結(jié)構(gòu)組成的集合二、填空題(本大題共 10 小題，每小題 2 分，共 20 分)請在每小題的空格中填上正確答案。錯填、不填均無分。估算算法時間復(fù)雜度時考慮的問題規(guī)模通常是指算法求解問題_規(guī)模函數(shù)_。在雙向循環(huán)鏈表中插入一個新的結(jié)點時，應(yīng)修4個指針域的值。若進棧序列為a，b，c，且進棧和出?？梢源┎暹M行，則可能出_5_個不同的出棧序列。鏈串的結(jié)點大小定義為結(jié)點_數(shù)據(jù)域中存放的字符個數(shù)。20.廣義(a，(d，(c)的深度_3。在含有3 個結(jié)點a，b，c 的二叉樹中，前序序列

44、為abc 且后序序列為cba 的二叉樹4棵。若用鄰接矩陣表示有向圖，則頂點i 的入度等于矩陣第i 列的非零個數(shù)_。23.對關(guān)鍵字序列 (1518111319，16121710，8)進行增量為 5 的一趟希爾排序的結(jié)果為_15,12,11,10,8,16,18,17,13,19。索引順序查找的索引表由各分塊中的最大關(guān)鍵字及各分塊起始地址構(gòu)成。VSAM 文件的實現(xiàn)依賴于操作系統(tǒng)中虛擬存取方法的功能三、解答(本大題共4小題，每小題5分，共20分)假設(shè)有一個形如的 88 矩陣，矩陣元素都是整型量(次對角線以上的元素都是 0)。若將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮存儲在一維數(shù)組B 中，請回答

45、下列問題： (1)B 數(shù)組的體積至少是多少?a18 B0中，a56 存儲在Bk中，則k值為多少(1)36(2)12(5，8，1，3，9，6，2，7)(1)寫出排序過程中前兩趟的劃分結(jié)果；(2)快速排序是否是穩(wěn)定的排序方法? (1)2,3,1,5,9,6,8,71,3,2,5,7,6,8,9,(2)不穩(wěn)定a，b，c，d，e，f，g，h28，13，10，3，11，試為這 8 個字符設(shè)計哈夫曼編碼。要求：()；0 1 的規(guī)則，分別寫出與每個字符對應(yīng)的編碼。(1)(2)f：000c：10000e：101h：001g：10001d：11b：01a：10013B樹如圖所示，6插入之后的B樹；(1)2 之后

46、的B(1)(2)做這個題的口訣是：中間往上走，兩邊要岔開。四、算法閱讀題(本大題共 4 小題，每小題 5 分，共 20 分)假設(shè)以帶頭結(jié)點的單鏈表表示線性表，單鏈表的類型定義如下：typedefinttypedef struct node DataType data; struct node * LinkNode, * LinkList;閱讀下列算法，并回答問題：已知初始鏈表如圖所示，畫出執(zhí)行f30(head)之后的鏈表；題 30 圖簡述算法f30 void f30( LinkList head)LinkListp,r, s; if (head - next) r = head - next;

47、 p = r-next;r - next = NULL;while (p) s =p;p = p-next;if ( s - data% 2 = = 0) s - next = head - next; head - next = s; else s - next = r - next; r-next = s;r =s; (1)8,2,5,7(2)將鏈表中的值偶數(shù)置前奇數(shù)置后。typedef struct node DataTypedata;struct node * lchild,* rchild;/左右孩子指針* BinTree ;閱讀下列算法，并回答問題：已知以T 寫出執(zhí)行f31(T)之

48、后的返回值；簡述算法f31 int f31 ( BinTree T)intd;if ( ! T) return 0;d = f31 ( T - lchild) + f31 ( T - rchild) ;(1)3if (T - lchild & T - rchild) returnd + 1 ;elsereturnd;(2)求二叉樹度為 2 的結(jié)點個數(shù)32.設(shè)有向圖鄰接表定義如下： typedef struct VertexNode adjlist MaxVertexNum ;int n，e；圖的當(dāng)前頂點數(shù)和弧數(shù)ALGraph；其中頂點表結(jié)點VertexNode邊表結(jié)點 EdgeNode 結(jié)構(gòu)為

49、： 閱讀下列算法，并回答問題：已知某有向圖存儲在如圖所示的鄰接 G 中，寫出執(zhí)行f32(G)簡述算法f32 int visited MaxNum ;void DFS(ALGraph * G, int i) EdgeNode * p;visited i = TRUE ;if (G - adjlist i. firstedge = = NULL) printf( % c , G - adjlist i. vertex)；else p = G - adjlist i. firstedge; while (p ! = NULL) if ( ! visitedp - adjvex ) DFS( G, p

50、 - adjvex) ;p = p-next;void f32 ( ALGraph * G) inti;for (i = 0; i n; i +) visited i = FALSE ;for (i = 0; i n; i+)if ( ! visitedi ) DFS(G, i) ;P108 (1)BD(2)輸出無鄰接點的頂點下列算法 f33 #define MAXLEN 100 typedef int KeyType; typedef struct KeyType key;InfoType otherinfo; NodeType ;typedef NodeType SqList MAXLEN

51、 ; void f33 ( SqList R, int n)int i,j,k;NodeType t;i =0;j =n-l;while (i Rk +l.key) t = Rk;Rk = Rk +1; Rk +1 = t; j-;for (k =j; k i; k - )if (2) t = Rk;Rk = Rk-1;Rk-1 = t;(3);(1)k=0;kj;k+(2)Rk.keyRk-1.key (3)i+五、算法設(shè)計題(本大題 10 分)typedef int DataType;typedef struct node DataType data; struct node * Link

52、Node, * LinkList;編寫算法，刪除線性表中最大元素(假設(shè)最大值唯一存在)。函數(shù)原型為：voidf34(LinkList head) ;2008 10 月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項選擇題(本大題共 15 小題，每小題 2 分，共 30 分)未選均無分。如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（ C）A. 棧C. 樹B. 隊列D. 圖下面程序段的時間復(fù)雜度為（ C）for (i=0; im; i+) for (j=0; jnext=head B. p-next-next=headC. p-next=NULLD. p=he

53、ad若以S 和X 分別表示進棧和退棧操作，則對初始狀態(tài)為空的棧可以進行的棧操作系列是（ D）A. SXSSXXXXB. SXXSXSSXC. SXSXXSSXD. SSSXXSXX兩個字符串相等的條件是（D ）A. B. 含有相同的字符集C. 都是非空串 D. 串的長度相等且對應(yīng)的字符相同An n L ,an1),( a12,a22,an2)a1n,a2n,ann),并且可以通過求表頭head和求表尾tail矩陣中的每一個元素，則求得a21的運算是（ A ）head (tail (head (L)B. head (head(head(L)C. tail (head (tail (L) D. h

54、ead (head (tail (L)已知一棵含50 個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1 的結(jié)點個數(shù)為（D ）A. 0 B. 1C. 48D. 49在一個具有n 個頂點的有向圖中，所有頂點的出度之和為Dout ，則所有頂點的入度之和為（A ）A. Dout B. Dout-1C. Dout+1D. n如圖所示的有向無環(huán)圖可以得到的拓?fù)湫蛄械膫€數(shù)是（ C）A. 3 B. 4C. 5 D. 6如圖所示的帶權(quán)無向圖的最小生成樹的權(quán)為（ C）51C. 54B. 52D. 56對長度為n的關(guān)鍵字序列進行堆排序的空間復(fù)雜度為（ B）O（log2n）B. O（1）C. O（n）D. O（n*l

55、og2n）12.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結(jié)果為（35，51，24，13，68，56，42，77，93）所采用的排序方法是（ B）A. B. 冒泡排序C. D. 歸并排序已知散列表的存儲空間為T0.18，散列函數(shù)H（key）=key%17,并用二次探測法處理沖突。散列表中已入下列關(guān)鍵字：T5=39，T6=57 和T7=7，則下一個關(guān)鍵字23 插入的位置是（ D）A. T2B. T4C. T8D. T10適宜進行批量處理的文件類型是（ A）B. 索引順序文件C. D. 多關(guān)鍵字文件VSAM 文件的索引結(jié)構(gòu)為（A

56、）B+B. 二叉排序樹C. 樹 D. 最優(yōu)二叉樹二、填空題(本大題共 10 小題，每小題 2 分，共 20 分)請在每小題的空格中填上正確答案。錯填、不填均無分。如果某算法對于規(guī)模為n 的問題的時間耗費為T（n）=3n3，在一臺計算機上運行時間為t 秒，則在另一臺運行速度是其64 倍的機器上，用同樣的時間能解決的問題規(guī)模是原問題規(guī)模的4倍。17.將兩個長度分別為m 和n 的遞增有序單鏈表，歸并成一個按元素遞減有序的單鏈表，可能達到的最好的間復(fù)雜度是 O(m+n)。已知循環(huán)隊列的存儲空間大小為，隊頭指針front 指向隊頭元素，隊尾指針rear 指向隊尾元素的下一個位置，則在隊列不滿的情況下，隊

57、列的長度是（rear-front+m）%m。字符串“sgabacbadfgbacst” 中存在有3個與字符串“ba”相同的子串。假設(shè)以列優(yōu)先順序存儲二維數(shù)組A58，其中元素A00的存儲地址為且每個元素占4 個儲單元，則數(shù)組元素Aij的存儲地址為Loca00+4*(5j+i)。x,y表示樹的邊（其中x 是y的雙親，已知一棵樹的邊集為,，該樹的度是3。22.n 個頂點且含有環(huán)路的無向連通圖中，至少含有n條邊。在一般情況下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數(shù)最少的是選擇序。和二分查找相比，順序查找的優(yōu)點是除了不要求表中數(shù)據(jù)元素有序之外，對 存儲結(jié)構(gòu)也無特殊要求。順序文件中記錄

58、存放的物理順序和邏輯順序一致三、解答(本大題共4小題，每小題5分，共20分)由森林轉(zhuǎn)換得到的對應(yīng)二叉樹如圖所示，寫出原森林中第三棵樹的前序序列和后序序列。前序序列：GHIJ 后序序列：HJIG圖的鄰接表的類型定義如下所示#define MaxVertexNum50typedef struct node int adjvex;structnode*next;EdgeNode; typedef structVertexTypevertex;EdgeNodeVertexNode;typedefVertexNodetypedefstruct AdjListint n, e;ALGraph;所示，請寫出

59、重新定義的類型說明。27 圖2 位數(shù)字（0.9）組成，形如E32對下列物品編號序列進行按字典序的排序，寫出每一趟（分配和收集）后的結(jié)果。E13，A37，F(xiàn)43，B32，B47，E12，F(xiàn)37，B12第一趟：書第二趟：P161第三趟：29.（1）畫出對表長為 13 的有序順序表進行二分查找的判定樹；（2）已知關(guān)鍵字序列為12141621242835435677849937 時所需進行的比較次數(shù)。（1）P172（2）3 次四、算法閱讀題（本大題共 4 小題，每小題 5 分，共 20 分）已知線性表的存儲結(jié)構(gòu)為順序表，閱讀下列算法，并回答問題：（1）設(shè)線性表L（21-，-，19，0，-1，34，30

60、，-1，寫出執(zhí)行f30(&L后的L狀態(tài)；（2）簡述算法f30 的功能。voidf30 (SeqList*L) inti,j;for (i=j=0;ilength; i+) if(L-datai=0)if(i!=j)L-dataj=L-datai; j+；L-length=j; (1)L=（21,19,0,34,30）(2)刪除順序表中負(fù)值元素閱讀下列算法，并回答問題：（1Q1和Q2Q（0-2-9其中1f31 (&Q,&Q1,&Q2)之后隊列 Q、Q1 和 Q2 的狀態(tài)；（2）簡述算法f31 的功能。（注：lnitQueue、EnQueue、DeQueue 和QueueEmpty分別是隊列初始化