數(shù)據(jù)結(jié)構(gòu)試題樣題及答案

1、數(shù)據(jù)結(jié)構(gòu)試題樣題及答案一、單項選擇題每題 2分，共30分1. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。A. 邏輯 B. 物理 C. 存儲 D.邏輯與物理2. 下述各類表中可以隨機(jī)訪問的是。A.單向鏈表B. 雙向鏈表 C.單向循環(huán)鏈表D.順序表3. 在一個長度為n的順序表中為了刪除第5個元素，從前到后依次移動了15個元素。那么原順序表的長度為。A. 21 B.20 C. 19 D. 254. 元素2，4，6按順序依次進(jìn)棧，那么該棧的不可能的輸出序列是。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45. 一個隊列的入隊序列是 5，6，7，8,那么隊列的輸出序列是。A

2、. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多種情況6. 串函數(shù) StrCmp “d，“D'的值為。A . 0B. 1C . -1D. 37. 在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要刪除q所指結(jié)點(diǎn)，可用語句。A. p=q nextB. p next=qC. p next=q next D. q next=NULL8. 設(shè)一棵哈夫曼樹共有n個非葉結(jié)點(diǎn)，那么該樹一共有個結(jié)點(diǎn)。A. 2*n-1 B. 2*n +1 C. 2*n D. 2* n-19. 對如圖1所示二叉樹進(jìn)行中序遍歷，結(jié)果是。A. dfebagc B.

3、 defbagc C. defbacg D.dbaefcg圖110 .任何一個無向連通圖的最小生成樹。A.至少有一棵 B.只有一棵C. 一定有多棵 D. 可能不存在11. 設(shè)有一個10階的對稱矩陣 A，采用壓縮存儲的方式，將其下三角局部以行序為主 序存儲到一維數(shù)組 B中數(shù)組下標(biāo)從1開始，那么矩陣中元素 A8,5在一維數(shù)組B中的下標(biāo)是 。A. 33B . 32C. 85D . 4112 . 一組記錄的關(guān)鍵字序列為37, 70, 47, 29, 31, 85,利用快速排序，以第一個 關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為。A. 31, 29, 37, 85, 47, 70B. 29, 31, 37

4、, 47, 70, 85C. 31, 29, 37, 70, 47, 85D. 31, 29, 37, 47, 70, 8513 .對n個元素進(jìn)行冒泡排序，要求按升序排列，程序中設(shè)定某一趟冒泡沒有出現(xiàn)元 素交換，就結(jié)束排序過程。對某n個元素的排序共進(jìn)行了3n-6次元素間的比擬就完成了排序，那么。A. 原序列是升序排列B. 原序列是降序排列C. 對序列只進(jìn)行了 2趟冒泡D. 對序列只進(jìn)行了 3趟冒泡14. 在一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行 °A.x=top->data;top=top->n ext;B. top=top->ne

5、xt ; x=top;C.x=top;top=top->n ext ;D. x=top->data;15. 串函數(shù)StrCat a,b的功能是進(jìn)行串°A .比擬B .復(fù)制C.賦值D .連接二、填空題每題2分，共24分1 .在一個單向鏈表中p所指結(jié)點(diǎn)之后插入一個s所指的新結(jié)點(diǎn)，應(yīng)執(zhí)行 s->n ext=p->n ext ;禾口操作。2根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常可分為 、四類根本結(jié)構(gòu)。3. 在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，那么刪除一個結(jié)點(diǎn)的操作為 °結(jié)點(diǎn)的指針域為n ext4. 遍歷二叉排序樹可得到一個有序序列。5. 一棵有2n-1個

6、結(jié)點(diǎn)的二叉樹，其每一個非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹共有 個葉結(jié)點(diǎn)。6. 如圖1所示的二叉樹，其中序遍歷序列為_一。7. 對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素所對應(yīng)的三元組包括該元素的 、禾廿三項信息。8 .有一個有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值為82的結(jié)點(diǎn)，經(jīng)次比擬后查找成功。9 .圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不是唯一的。此斷言是 的。答復(fù)正確或不正確)10. 哈希法既是一種存儲方法，又是一種 。11. 44.在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時，當(dāng)把第7個記錄65

7、插入到有序表時，為尋找插入位置需比擬 次。12. 棧和隊列的操作特點(diǎn)分別是 和 。三、綜合題(每題10分，共30分)1. 序列11 , 19, 5, 4, 7, 13, 2, 10,(1) 試給出用歸并排序法對該序列作升序排序時的每一趟的結(jié)果。(2) 對上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉樹描述建堆過程)。2. 設(shè)有序表為(13, 19, 25, 36, 48, 51, 63, 84, 91, 116, 135, 200),元素的下標(biāo)依次為1,2,12.(1) 說出有哪幾個元素需要經(jīng)過3次元素間的比擬才能成功查到(2) 畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹(樹結(jié)點(diǎn)用下標(biāo)表

8、示)(3) 設(shè)查找元素5,需要進(jìn)行多少次元素間的比擬才能確定不能查到3.(1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(2) 說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序 遍歷的結(jié)果四、程序填空題(每空 2分，共16分)1. 以下冒泡法程序?qū)Υ娣旁赼1 , a2,an中的序列進(jìn)行冒泡排序，完成程序中的空格局部，其中n是元素個數(shù)，程序按升序排列。Void bsort (NODE a , i nt) NODE temp;int i,j,flag;for(j=1; (1);j+);flag=0;for(i=1;(2);i+

9、)if(ai.key>ai+1.key) flag=1;temp=ai;(3) ;(4) ;if(flag= =0)break;程序中flag 的功能是 7.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格局部 (樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域為data,其數(shù)據(jù)類型為字符型，BT指向根結(jié)點(diǎn))。Void Postorder (struct BTree Node *BT) if(BT!=NULL)(1) ;(2) ;(3) ;試題答案；一、單項選擇題每題 2分，共30分10 . A1. A 2 . D 3 . B 4 . B 5 . A 6 . C11. A

10、12 . D 13 .D 14 . A 15 . D2分，共24分二、填空題每題1. p->n ext=s;圖狀2. 集合、線性、樹形、3. f=f->next;4. 中序5. n6. dgbaechhif7. 行號、列號、元素值8.4次9. 正確10. 查找方法11. 3 次12. 先進(jìn)后出先進(jìn)先出三、綜合題每題 10分，共30 分 1 .1初始第一趟第二趟第三趟11, 19, 5, 4, 7, 13, 2, 10 11 , 194 , 57 ,4, 5,2, 4,11, 192 ,5, 7,10,132 , 107, 10, 1311, 13, 1919111013(1)13,36,63,135(3)3 次(1)11191315102中序遍歷中序 2，3， 4，5，6