期末復(fù)習(xí)題_數(shù)據(jù)結(jié)構(gòu)

1、中國石油大學(xué)（北京）遠(yuǎn)程教育學(xué)院 期 末 復(fù)習(xí)題一、選擇題（本大題共15小題，每小題2分，共30分）1. 以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ）A、循環(huán)隊列 B、鏈表C、哈希表 D、棧2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）A、110 B、108C、100 D、1203. 假設(shè)帶頭結(jié)點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（ ）A、head= =NULL B、head>next= =NULL C、head>next= =head D、head!=NULL4. 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源?/p>

2、插進(jìn)行，則不可能出現(xiàn)的出棧序列是（ ） A、2，4，3，1，5，6B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，3，5，1，6，45. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是（ ）A、12，21，49，33，81，56，69，41 B、81，69，56，49，41，33，21，12 C、81，49，69，41，21，56，12，33 D、12，21，49，33，81，41，56，696. 下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ ）A、B樹 B、AVL樹 C、二叉排序樹 D、哈夫曼樹7. 用順序存儲的方法來存儲一棵二叉樹，存放在一維數(shù)組A1.N中，若結(jié)點Ai有右孩子，則其右孩子是（ ）。A、

3、A2i B、A2i-1 C、A2i+1 D、Ai/28. 設(shè)樹T的高度為4，其中度為1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1，則T中葉子數(shù)為（ ）A、 5 B、 6 C、7 D、 89. 有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應(yīng)選擇下面哪個序列輸入（ ）A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，5310. 對下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯誤的是（ ）A、1，5，2，6，3，4B、

4、1，5，6，2，3，4C、5，1，6，3，4，2 D、5，1，2，6，4，311. m階B-樹中所有非終端（除根之外）結(jié)點中的關(guān)鍵字個數(shù)必須大于或等于( ) A、 m/2+1 B、m/2-1 C、m/2 D、m12. 散列文件也稱為( ) A、順序文件 B 、索引文件C、直接存取文件 D、間接存取文件13. 數(shù)據(jù)結(jié)構(gòu)是（ ）A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲結(jié)構(gòu)C、一組性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合14. 從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（ ）A、線性結(jié)構(gòu)B、樹形結(jié)構(gòu)C、線性結(jié)構(gòu)和樹型結(jié)構(gòu) D、線性結(jié)構(gòu)和圖狀結(jié)構(gòu)15. 設(shè)p

5、為指向雙向循環(huán)鏈表中某個結(jié)點的指針，p所指向的結(jié)點的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針?biāo)赶蚪Y(jié)點的表達(dá)式是（ ）A、pllink B、prlinkC、pllinkllink D、pllinkrlink16. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ ）A、 |top2-top1|=0 B、 top1+1=top2 C、 top1+top2=m D、 top1=top217. 若一棵二叉樹有11個葉子結(jié)點，則該二叉樹中度為2的結(jié)點個數(shù)是（ ）A、10 B、11C、12

6、D、不確定的18. 樹的先根序列等同于與該樹對應(yīng)的二叉樹的（ ）A、先序序列B、中序序列C、后序序列 D、層序序列19. 下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是( )A、哈希函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機(jī)性好，沖突小B、除留余數(shù)法是所有哈希函數(shù)中最好的 C、不存在特別好與壞的哈希函數(shù)，要視情況而定D、若需在哈希表中刪去一個元素，解決沖突都只要簡單的將該元素刪去即可20. 下列序列中，（ ）是執(zhí)行第一趟快速排序后所得的序列。 A、 68，11，18，69 23，93，73 B、 68，11，69，23 18，93，73 C、 93，73 68，11，69，23，18 D、 68，1

7、1，69，23，18 93，7321. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是( )A、 (84，46，62，41，28，58，15，37) B、 (84，62，58，46，41，37，28，15)C、 (15，28，46，37，84，41，58，62) D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件屬于( ) A、索引非順序文件 B、順序文件C、索引順序文件 D、散列文件23. 下面程序段的時間復(fù)雜度為（ ）for (i=0; i<m; i+)for (j=0; j<n; j+)Aij=i*j;A、O(m2) B、 O(n2) C、O(m*n

8、) D、O(m+n)24. 已知指針p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應(yīng)執(zhí)行的語句為（ ）A、q->next=s->next；s->next=p； B、s->next=p；q->next=s->next；C、p->next=s->next；s->next=q； D、s->next=q；p->next=s->next；25. 為便于判別有向圖中是否存在回路，可借助于（ ）A、廣度優(yōu)先搜索算法 B、最小生成樹算法 C、最短路徑算法 D、拓?fù)渑判?/p>

9、算法26. 若以S和X分別表示進(jìn)棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（ ）A、SXSSXXXX B、SXXSXSSXC、SXSXXSSX D、SSSXXSXX27. 設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是( )A、2 B、3 C、5 D、628. 假設(shè)以數(shù)組Am存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位 置為（ ）。A、(rear-length+m+1)%m B、(rear-length+m)%m

10、C、(rear-length+m-1)%m D、(rear-length)%m29. 在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點s的操作為（ ）。A、s->next=rear;rear=s; B、front=front->next;C、s->next=front;front=s; D、rear->next=s;rear=s;30. 對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是（ ）A、35和41 B、 23和39 C、15和44 D、25和5131. 采用二叉鏈表存儲的n個結(jié)點的二叉樹，共有空指針（ ）個。A、n+1 B、

11、n C、n-1 D、2n-132. 連通網(wǎng)的最小生成樹是其所有生成樹中（ ）A、頂點集最小的生成樹 B、邊集最小的生成樹C、頂點權(quán)值之和最小的生成樹 D、邊的權(quán)值之和最小的生成樹33. 對記錄序列(314，298，508，123，486，145)依次按個位和十位進(jìn)行兩趟基數(shù)排序之后所得結(jié)果為（ ）A、123，145，298，314，486，508 B、508，314，123，145，486，298C、486，314，123，145，508，298 D、298，123，508，486，145，31434. 任何一個無向連通圖的最小生成樹( )。A、一定有多棵 B、可能不存在 C、一棵或多棵 D、

12、只有一棵35. 無向圖的鄰接矩陣是一個( )A、對角矩陣 B、上三角矩陣 C、對稱矩陣 D、零矩陣36. 設(shè)無向圖G-=(V,E)和G=(V,E),如G為G的生成樹，則下列說法中不正確的是( )。A、G為G的無環(huán)子圖 B、G為G 連通分量C、G為G極小連通子圖且V=V D、G為G的子圖37. 以v1為起始結(jié)點對下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7 B、 v1，v2，v5，v4，v3，v7，v6C、 v1，v2，v3，v4，v7，v5，v6 D、 v1，v2，v5，v6，v7，v3，v438. 下面幾個符號串編碼集合中，不是前綴編碼的是（ ）

13、A、0,10,110,1111 B、0,1,00,11C、00,010,0110,1000 D、b,c,aa,ac,aba,abb,abc39. 希爾排序的增量序列必須是（ ）。A、 遞增的 B、遞減的 C、隨機(jī)的 D、非遞減的40. 采用起泡排序法對n個關(guān)鍵字進(jìn)行升序排序，若要使排序過程中比較關(guān)鍵字的次數(shù)最多，則初始時的序列應(yīng)滿足條件（ ）A、關(guān)鍵字完全無序 B、關(guān)鍵字基本有序C、關(guān)鍵字從小到大排列 D、關(guān)鍵字從大到小排列41. 在下列內(nèi)部排序中( )是不穩(wěn)定的。A、希爾排序 B、起泡排序 C、直接插入排序 D、歸并排序42. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的

14、是( )。A、（100，80， 90， 60， 120，110，130） B、（100，120，110，130，80， 60， 90）C、（100，60， 80， 90， 120，110，130） D、(100，80， 60， 90， 120，130，110)43. 在查找過程中，沖突指的是（ ）。A、兩個元素具有相同序號 B、兩個元素的鍵值不同C、不同鍵值對應(yīng)相同的存儲地址 D、兩個元素的鍵值相同44. 對有14個元素的有序表A1.14作二分查找，查找元素A4時的被比較元素依次為（ ）。A、A1，A2，A3，A4 B、A1，A14，A7，A4 C、A7，A5，A3，A4 D、A7，A3，A5

15、，A445. 以v1為起始結(jié)點對下圖進(jìn)行廣度度優(yōu)先遍歷，正確的遍歷序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7B、v1，v2，v5，v6，v7，v3，v4C、 v1，v2，v5，v6，v7，v3，v4D、 v1，v4，v5，v7，v6，v2，v3二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)包括 的存儲和 的存儲。2. 若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復(fù)雜度為 。 3. 下面程序段的時間復(fù)雜度是 。 i=1； while (i<=n) i=i*3；4. 循環(huán)隊列用數(shù)組A0.m-

16、1存放其元素值，已知其頭尾指針分別是front和rear ，則當(dāng)前隊列的元素個數(shù)是 。5. 在單鏈表中設(shè)置頭結(jié)點的作用是 _。6. 線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_ 。7. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是 遍歷方法。8. 如果排序過程不改變 之間的相對次序，則稱該排序方法是穩(wěn)定的。9. 從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需 一個位置

17、。 10. 當(dāng)問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的 。11. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的 。12. 一棵含999個結(jié)點的完全二叉樹的深度為 。13. 假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為 。14. .如圖所示的有向無環(huán)圖可以排出 種不同的拓?fù)湫蛄小?5. 從空樹起，依次插入關(guān)鍵字1l，27，35，48，52，66和73構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時的平均查找長度為 。16.

18、帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是 。 17. 求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中 的數(shù)目正相關(guān)。18. 已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。19. 實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點外，還需要 存放被訪問的結(jié)點以實現(xiàn)遍歷。20. Prim（普里姆）算法適用于求 的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求 的網(wǎng)的最小生成樹。21. 對長度為20的有序表進(jìn)行二分查找的判定樹的高度為 。22. 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為 ，有_ 個葉子結(jié)點。23. 高度為h的完全

19、二叉樹中最少有 個結(jié)點，最多有 個結(jié)點。24. 設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有 條邊。25. 構(gòu)造n個結(jié)點的強(qiáng)連通圖，至少有 條弧。26. 表達(dá)式求值是 應(yīng)用的一個典型例子。27. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是 。28. 快速排序算法在最差的情況下其時間復(fù)雜度是 。29. 對序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是 。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）1. 已知

20、二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。2. 如圖請給出鄰接表、鄰接矩陣及逆鄰接表。V1V3V2V43. 由字符集s，t，a，e，I及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。4. 請畫出下圖所示的樹所對應(yīng)的二叉樹，并寫出對應(yīng)二叉樹的先序遍歷和中序遍歷。123456785. 設(shè)散列表為HT13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36

21、 造表。采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度。6. 已知帶權(quán)圖G如圖所示，畫出圖G的一棵最小生成樹。7. 假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，請為這8個字母設(shè)計哈夫曼編碼。8. 試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。9. 畫出與如圖所示森林對應(yīng)的二叉樹。10. 已知一個散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11

22、 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)=key%11+1回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進(jìn)行查找時，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？11. 請畫出與下列二叉樹對應(yīng)的森林。12. 對于給定結(jié)點的關(guān)鍵字集合K=5，7，3，1，9，6，4，8，2，10，（1）試構(gòu)造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL。13. 給出下圖對應(yīng)的鄰接矩陣，并給出A，B，C三個頂點的出度與入度

23、 14. 已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）543223356abdfce15. 閱讀下列算法，并回答問題：（1）假設(shè)串由合法的英文字母和空格組成，并以0作結(jié)束符。設(shè)串s=”Iamastudent”(表示空格符)，寫出f30（s）的返回值；（2）簡述算法f30的功能。int f30 (char*s)int i, n, inword;n=inword=0;for (i=0;si!=0;i+)if (si!=&& inword=0)inword=1;n+; else if (si=&& inword=1) inword=0;r

24、eturn n;16. 閱讀下列函數(shù),并回答問題：（1）假設(shè)隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用Conv(&q)后的隊列q；（2）簡述算法Conv的功能。void Conv (Queue *Q) Stack S; InitStack(&S); while (!QueueEmpty(Q) Push(&S, DeQueue(Q); while (! StackEmpty(&S) nQueue(Q,Pop(&S);17. 閱讀下列函數(shù),并回答問題：已知整形數(shù)組L1.8中的元素依次為（19，18，15，17，16，13，

25、12，10），閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L, 8)時，對L進(jìn)行的頭兩趟（pass分別為0和1）處理結(jié)果。 void sort (int R,int n) int pass = 0, k, exchange, x; do k=pass%2+1; exchange = 0; while (k<n) if (Rk>Rk+1) x = Rk; Rk = Rk+1; Rk+1 = x; exchange =1; K+=2; pass +;while (exchange = = 1| pass <=1);keynext18. 已知帶頭結(jié)點的單鏈表中的關(guān)鍵字為整數(shù)，為提高查

26、找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點結(jié)構(gòu)為： 。請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算法。void f33 (LinkList L, LinkList H, int m)/由帶頭結(jié)點的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j; LinkList p,q; for (i=0;i<m;i+) Hi= (1) ; p=L->next; while(p) q=p->next; j=p->key%m; (2) ; Hj=p; (3) ; free(L); 19. 下列

27、函數(shù)的功能是，對以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內(nèi)容，使其成為一個完整的算法。 void union (LinkList La, LinkList Lb)/本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點插入到La表中LinkList pre = La, q;LinkList pa = La -> next;LinkList pb = Lb -> next;free (Lb);while (pa &&

28、amp; pb)if (pa -> data <pb -> data) pre = pa; pa = pa -> next;else if (pa -> data > pb ->data) (1) ;pre = pb;pb = pb -> next; (2) ;elseq = pb; pb = pb -> next; free (q);if (pb) (3) ;20. 閱讀算法f30，并回答問題：下列算法為有向圖拓?fù)渑判?請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。void f30 (hdnodes graph ,int n) int

29、 i,j,k,top; node_pointer ptr ; top=-1; for (i=0; i<n; i+) if (!graphi.count)graphi.count=top; top=i; for (i=0; i<n; i+) if_ (1)_ fprintf(stderr, "ngraph has a cycle n"); exit(1); else j=top; _ (2)_; printf( "v%d, " ,j) ; for (ptr=graphj.link; ptr; ptr=ptr->link) k=ptr-&g

30、t;vertex; graphk.count-; if( (3) ) graphk.count=top; top=k; 21. 閱讀算法f31，并回答問題：下列算法功能為在數(shù)組a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設(shè)數(shù)組a中各元素的值都不相同。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。#define MAXN 100int aMAXN,n,k;int f31(int a, int n, int k)int low, high, i, j, m, t; k-,;low=0 ;high=n-1; do i=low; j=high ; t=al

31、ow; do while (i<j && t<aj) j-; if (i<j) ai+=aj; while (i<j && t>=ai) i+ if (i<j) aj-=ai; while (i<j);ai=t;if (1) ; if (i<k) low= (2) ; else high= (3) ;while （i!=k）;return(ak); 22. 閱讀算法f33，并回答問題：下列算法功能為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將ai和ai+1進(jìn)行比較,第二趟對所有偶數(shù)的i,將ai和ai+1進(jìn)行比較,每次比較時若ai>ai+1,將二者交換;以后重復(fù)上