數(shù)據(jù)結(jié)構(gòu)試題庫(kù)

1、Test 1一、單項(xiàng)選擇題(每題 2 分，共 30 分)1. 假設(shè)某線性表中最常用的操作是取第 存儲(chǔ)方式最節(jié)省時(shí)間。A) 單鏈表 表 D) 順序表2. 串是任意有限個(gè)(A) 符號(hào)構(gòu)成的序列C) 字符構(gòu)成的序列3. 設(shè)矩陣A的任一元素aij( 1w i,jaij 工 0; (i >j,1 w i,j w 10) aij=0 ；(i<j,1 wi,j w10)現(xiàn)將A的所有非0元素以行序?yàn)橹餍虼娣旁谑椎刂窞?個(gè)單元，那么元素 A9,5 的首地址為( )。A) 2340B) 23362164 D) 21604. 如果以鏈表作為棧的存儲(chǔ)結(jié)果，那么出棧操作時(shí)(A) 必須判別棧是否為滿C) 必須

2、判別棧是否為空5. 設(shè)數(shù)組DataO.m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間， 那么執(zhí)行出隊(duì)操作的語(yǔ)句為( )。A) front = front+1mC) rear = (rear+1) %m6. 深度為 6(根的層次為 1)的二叉樹至多有( )A) 64B) 3231D) 637. 將含 100 個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始， 的編號(hào)為 1 。編號(hào)為 49 的結(jié)點(diǎn) X 的雙親的編號(hào)為(A) 24B) 2523D) 無(wú)法確定8. 設(shè)有一個(gè)無(wú)向圖 和 ，如果 為 的生成樹，那么下面不正確的說法是(A)為 的子圖C)為 的極小連通子圖且D) 為 的一個(gè)無(wú)環(huán)子圖9. 用線性探測(cè)法查找閉散列表，可能要探測(cè)多

3、個(gè)散列地址，這些位置上的鍵值(A) 一定都是同義詞B)C) 多相同 都是同義詞10. 二分查找要求被查找的表是(A) 鍵值有序的鏈接表有序C) 鍵值有序的順序表有序11. 當(dāng)初始序列已經(jīng)按鍵值有序， 用直接插入算法對(duì)其進(jìn)行排序， 需要循環(huán)的次數(shù)為 (i 個(gè)元素和找第B) 雙鏈表元素)。w 10)滿足:)。i 個(gè)元素的前趨元素，那么采用(C) 單向循環(huán)鏈B) 符號(hào)構(gòu)成的集合D) 字符構(gòu)成的集合2000 的存儲(chǔ)區(qū)域中，每個(gè)元素占有)。front結(jié)點(diǎn)。C)對(duì)棧不作任何判別 判別棧元素的類型 為隊(duì)頭指針， rear 為隊(duì)尾指針B)D)B) front = (front+1)D) front = (fr

4、ont+1) %(m+1)C)每層上從左到右依次堆結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn))。C)B)。為 的連通分量)。定都不是同義詞D) 不一定B) 鏈接表但鍵值不一定D) 順序表但鍵值不一定)。D) n 112. 堆是一個(gè)鍵值序列 , 對(duì) ，滿足()。A)B)C) 且 ( ) D) 或 ( )13. 使用雙向鏈表存儲(chǔ)數(shù)據(jù)，其優(yōu)點(diǎn)是可以()。A) 提高檢索速度B)很方便地插入和刪除數(shù)據(jù)C) 節(jié)約存儲(chǔ)空間D)很快回收存儲(chǔ)空間14. 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)地算法，采用()數(shù)據(jù)結(jié)構(gòu)最正確。A) 線性表地順序存儲(chǔ)結(jié)構(gòu)B) 棧C) 隊(duì)列D) 線性表A)B)C)達(dá)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)15. 設(shè)深度為 k 的二叉樹

5、上只有度為 0 和 2 的結(jié)點(diǎn)，那么此類二叉樹中所含的結(jié)點(diǎn)數(shù)至少為 ( )。B) 2kD) 2k + 1C) 2k -A) k + 11二、填空題(每空 2分，共 28 分)1. 設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是 r=s;r->next=NULL 。2. 在單鏈表中，指針 p 所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 。3. 設(shè)一個(gè)鏈棧的棧頂指針是 ls ，棧中結(jié)點(diǎn)格式為，棧空的條件為 。如果棧不為空，那么出棧操作為 p=ls;free(p) 。4. 一棵度為 3 的樹有 2 個(gè)度為 1 的結(jié)點(diǎn)， 3個(gè)度為 2的結(jié)點(diǎn)， 4個(gè)度為 3的結(jié)點(diǎn)，那么

6、該樹有 個(gè)葉子結(jié)點(diǎn)。5. 樹有三種常用的存儲(chǔ)結(jié)構(gòu)，即孩子鏈表法，孩子兄弟鏈表法和。6. n 個(gè)頂點(diǎn)的連通圖的生成樹有 條邊。7. 一個(gè)有向圖G中假設(shè)有弧、和，那么在圖G的拓?fù)湫蛄兄?，頂點(diǎn) 的相對(duì)位置為 8. 設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、 快速排序、 冒泡排序和歸并排序方法對(duì)其進(jìn)行排序 (按遞增順序 ) ， 最省時(shí)間， 最費(fèi)時(shí)間。9. 下面是將鍵值為 x 的結(jié)點(diǎn)插入到二叉排序樹中的算法，請(qǐng)?jiān)趧澗€處填上適當(dāng)?shù)膬?nèi)容。 Typedef struct pnode int key;struct node * left, * right;Void searchinsert (int x

7、; pnode t )/* t 為二叉排序樹根結(jié)點(diǎn)的指針 */ if ()p = malloc (size); p->key=x;p->left=NULL; p->right=NULL; t=p;elseif x<t->key searchinsert x,t->leftelse 10. 線性表的 的主要優(yōu)點(diǎn)是從表中任意結(jié)點(diǎn)出發(fā)都能訪問到所有結(jié)點(diǎn)。而使用，可根據(jù)需要在前后兩個(gè)方向上方便地進(jìn)行查找。三、應(yīng)用題每題 10分，共 30 分1. 在雙鏈表中，要在指針變量P所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，請(qǐng)按順序?qū)懗霰匾乃惴ú襟E。設(shè)：P所指結(jié)點(diǎn)不是鏈表的首尾結(jié)點(diǎn)，q是與

8、p同類型的指針變量2. 待排序文件各記錄的排序碼順序如下：72 73 71 23 94 16 05 68 請(qǐng)列出快速排序過程中每一趟的排序結(jié)果。四、算法題 共 12 分 編寫算法，實(shí)現(xiàn)單鏈表上的逆置運(yùn)算 說明：即將單鏈表中的元素次序反轉(zhuǎn) ?數(shù)據(jù)結(jié)構(gòu)? 2004 學(xué)年面授試卷答案一、單項(xiàng)選擇題每題 2 分，共 30 分1. D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C11. D 12.C 13.A 14.B 15.C二、填空題每空 2分，共 28 分1. r->next=s; 2. p->next=NULL;3. ls = = NULL; ls=ls-

9、>link 。 4. 125. 雙親表示法6. n-17. i,j,k8. 冒泡排序，快速排序9. t= =NULL ， searchinsert x,t->right ；10. 循環(huán)鏈表，雙向鏈表三、應(yīng)用題每題 10分，共 30 分1 new(q) ；qf.llinkJ P ；qf.rlinkJ p f .rlink ;pf.rlinkf .llink J q ；Pf.rlinkJ q。評(píng)分細(xì)那么：按順序每對(duì)一個(gè)給2分，全對(duì)計(jì) 10 分。2各趟結(jié)果如下：68 05 71 23 1672947316 05 23 68 7172947305 16 23 68 7172947305 1

10、6 23 68 7172947305 16 23 68 7172947305 16 23 68 717273 9405 16 23 68 71727394四算法題 共 12 分void invert ( pointer head )p=NULL;while ( head<>NULL)u=head;head=head->next;u->next=p;p=u;head=p;六、編寫算法 10 分。寫出向二叉排序樹中插入一個(gè)元素的非遞歸算法。Void insert(BtreeNode * BST, const ElemType & item) BtreeNode *t

11、=BST, *parent=NULL;While(t!=NULL)Parent=t;If(item<t->data) t=t->left; Else t=t->right;BtreeNode *p=newBtreeNode; p->data=item; p->left=p->right=NULL; if(parent= =NULL) BST=p; else if(item<parent->data) else parent->right=p; 閱讀算法，答復(fù)以下問題(每題1. Void MADE(Lnode * & H1)Ln

12、ode *p;p=H1;H1=NULL;while(p!=NULL)lnode *q=p;p=p->next;parent->left=p;8 分，共 16 分)2. Void AE(Stack& S) InitStack(S);Push(S,30);Push(S,40);Push(S,50);int x=Pop(S)+2*Pop(S); Push(S,x);int i,a4=5,8,12,15;q->next=h1;H1=q;該算法的功能為：將原鏈表逆序5 130 30 Test 2 北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試題 A 卷 for(i=0;i<4;i+)Pu

13、sh(S,ai);while(!StackEmpty(S)cout<<Pop(S)<< ' '該算法被調(diào)用后得到的輸出結(jié)果為：15 12 81A.23415 B.541322設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是為 D。A.r-f B.r-f+1C.312451n,其頭尾指針分別為D.14253f 和 r ，那么其元素個(gè)數(shù)C.(r-f) mod n +1D.單項(xiàng)選擇題 2 分/ 題一個(gè)棧的輸入序列為 12345，那么以下序列中是棧的輸出序列的是A。(r-f+n) mod n3二叉樹在線索化后，仍不能有效求解的問題是D。A. 先序線索二叉樹中求先序后繼 B. 中序線

14、索二叉樹中求中序后繼 C. 中序線索二叉樹中求中序前驅(qū) D. 后序線索二叉樹中求后序后繼4. 求最短路徑的FLOYD算法的時(shí)間復(fù)雜度為D。A. OnB.On+eC.On2D.On35. 一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為B。A. 0B.1C.2D. 不確定6. 數(shù)組 A1.5,1.6的每個(gè)元素占 5 個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址為 1000 的連續(xù)的內(nèi)存單元中，那么元素 A5,5 的地址為 A。A.1140B.1145C.1120D.11257. 在以下排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是 A。A.快速排序B.希爾排序C.冒泡排序D.堆排

15、序8. 對(duì)有 18 個(gè)元素的有序表做折半查找，那么查找 A3 的比擬序列的下標(biāo)依次為 C。A.1-2-3B.9-5-2-3C.9-5-3D. 9-4-2-39. 以下排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是D)。A.堆排序B.冒泡排序C.快速排序D.直接插入排序10. 在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡點(diǎn)為A,并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為 0，那么做B型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR二. 判斷題 1 分/ 題1. 線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。F2. 雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏

16、輯后繼。F3. 在對(duì)鏈隊(duì)列做出隊(duì)操作時(shí)，不會(huì)改變 front 指針的值。 F4. 如果兩個(gè)串含有相同的字符，那么說它們相等。 F5. 如果二叉樹中某結(jié)點(diǎn)的度為 1，那么說該結(jié)點(diǎn)只有一棵子樹。 T6. 一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。F7. 圖G的一棵最小代價(jià)生成樹的代價(jià)未必小于G的其它任何一棵生成樹的代價(jià)。T8. 圖G的拓?fù)湫蛄形ㄒ唬敲雌浠?shù)必為n-1 其中n為頂點(diǎn)數(shù)。F9. 對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。 T10. 直接選擇排序算法滿足：其時(shí)間復(fù)雜度不受數(shù)據(jù)的初始特性影響，為On2 。 T三. 填空題 2 分/ 空1. 完全二叉樹的第8層有 8個(gè)結(jié)點(diǎn)，那么其葉

17、子結(jié)點(diǎn)數(shù)是68。 68+8-42. 將下三角矩陣 A1.8,1.8的下三角局部逐行地存儲(chǔ)到起始地址為 1000的內(nèi)存單元中， 每個(gè)元素占 4 個(gè)單元，那么 A7,5 的地址是 1100。3. 有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有n條弧。4. 有n個(gè)結(jié)點(diǎn)并且其高度為 n的二叉樹的數(shù)目是2A n-1 。5. 高度為 8 的平衡二叉樹的結(jié)點(diǎn)數(shù)至少是54。6. 3 個(gè)結(jié)點(diǎn)可構(gòu)成 5棵不同形態(tài)的樹。7. 給出冒泡排序和快速排序的最好情況、平均情況和最壞情況下的時(shí)間復(fù)雜度。四、設(shè)計(jì)一個(gè)算法， 判斷一個(gè)算術(shù)表達(dá)式中的括號(hào)是否配對(duì)。 算術(shù)表達(dá)式保存在帶表頭結(jié)點(diǎn) 的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：ch和link ,

18、其中ch域?yàn)樽址愋?。南開大學(xué) 98 考研題一、8分 給出數(shù)組 A : ARRAY3.8,2.6 of INTEGER;當(dāng)它內(nèi)存中按行存放和按列存放 時(shí)，分寫出數(shù)組元素 Ai,j 地址計(jì)算公式設(shè)每個(gè)元素站兩個(gè)存儲(chǔ)單元 。二、 12 分于對(duì)于有向無(wú)環(huán)圖 表達(dá)求拓?fù)溆行蛐蛄械牟襟E；對(duì)于以下的圖，寫出它的四個(gè)不同的拓?fù)溆行蛐蛄腥?12 分一棵二叉樹按中序遍歷時(shí)個(gè)結(jié)點(diǎn)被訪問的次序和這棵二叉樹按后序遍歷時(shí)各 結(jié)點(diǎn)被訪問的次序，是否唯一確定這棵二叉樹的結(jié)構(gòu)？為什么？假設(shè)一棵叉樹按先序遍 歷時(shí)各結(jié)點(diǎn)被訪問的次序和這棵按后序遍歷時(shí)各結(jié)點(diǎn)訪問的次序，能否唯一確定這棵二叉 樹的結(jié)構(gòu)？為什么？七、寫出在二叉排序樹

19、中刪除一個(gè)結(jié)點(diǎn)的數(shù)法，使刪除后仍為二叉排序樹。設(shè)刪除結(jié)點(diǎn)由指針P所指，其雙親結(jié)點(diǎn)由指針f所指，并假設(shè)被刪除結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子。用類PASCAL或C語(yǔ)言將上述算法寫為過程形式。南開考研題八、給出一組關(guān)鍵字：29， 18， 25， 47， 58， 12， 51， 10，分別寫出以下各種排序方法進(jìn)行排序時(shí)的變化過程： 南開考研題1 .歸并排序 每歸并一次書寫一個(gè)次序。2 快速排序3 堆排序Test 3每規(guī)劃一次書寫一個(gè)次序。先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次選擇題(單項(xiàng)選擇，每題 2分，共計(jì)20分)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是 。A.存儲(chǔ)結(jié)構(gòu)B.物理結(jié)構(gòu)C.物理和

20、存儲(chǔ)結(jié)構(gòu)線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址是 。A.必須是連續(xù)的B. 一定是不連續(xù)的C.局部地址必須是連續(xù)的D.連續(xù)與否均可以在以下鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是A.單鏈表B.單循環(huán)鏈表C.雙向鏈表4、 設(shè)一個(gè)棧的進(jìn)棧序列是a ,b,c,d,進(jìn)棧的過程中可以出棧,A.d， c， b， a B.c ， d， b，a C.d ， c， a ,5、 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0N-1 ,其頭尾指針分別為A. r - f串是。A.不少于一個(gè)字母的序列C.不少于一個(gè)字符的序列 對(duì)稀疏矩陣采用壓縮存儲(chǔ)，其缺點(diǎn)之一A. 無(wú)法判斷矩陣有多少行和多少列B. 無(wú)法根據(jù)行列號(hào)查找某個(gè)矩陣元素C. 無(wú)法根據(jù)

21、行列號(hào)計(jì)算矩陣元素的存儲(chǔ)地址D. 使矩陣元素之間的邏輯關(guān)系更加復(fù)雜以下說法錯(cuò)誤的選項(xiàng)是_A. 般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近B. 哈夫曼樹中沒有度數(shù)為C. 假設(shè)初始森林中共有D. 假設(shè)初始森林中共有任何一個(gè)無(wú)向連通圖1、2、3、6、7、9、B.r-f-1C.(r-f)%N+1D.邏輯結(jié)構(gòu)OD.雙向循環(huán)鏈表不可能的出棧序列是_ b D.a ， b, c， d f和r，那么其元素個(gè)數(shù)為D.(r-f+N)%NB.任意個(gè)字母的序列D.有限個(gè)字符的序列曰疋1的分支結(jié)點(diǎn)棵二叉樹，最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)棵二叉樹，進(jìn)行2n-1次合并后才能剩下最終的哈夫曼樹最小生成樹。A.只有一棵B

22、.有一棵或多棵C.一定有多棵D.可能不存在10、只有在順序存儲(chǔ)結(jié)構(gòu)上才能實(shí)現(xiàn)的查找方法是 法。A.順序查找B.二分查找C.樹型查找D.哈希查找二、填空題(每題1分，共計(jì)10分)1、 在一個(gè)長(zhǎng)度為 n的順序表中向第i個(gè)元素(1 < i < n)之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)個(gè)元素。2、只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除元素操作的線性表稱為3、 假設(shè)串S = ' software '(串長(zhǎng)度為8)，其子串?dāng)?shù)目是 個(gè)。4、 一個(gè)nxn的對(duì)稱矩陣，如果以行或列為主序放入內(nèi)存，那么容量為 。5、 對(duì)于廣義表(a,b),(),(a,(b)來說，其有 個(gè)元素。6、

23、某棵樹的的結(jié)點(diǎn)A有3兄弟，而且結(jié)點(diǎn) B是A的雙親，那么結(jié)點(diǎn) B的度是7、 n個(gè)結(jié)點(diǎn)的二叉樹，最大高度是 。8、 克魯斯卡爾(Kruskal)算法適用于求 的網(wǎng)的最小生成樹。9、 在各種查找方法中，其平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是 。10、 對(duì)關(guān)鍵字序列13，11,54, 26，14,36, 77，用篩選法建堆，必須從鍵值為 的 開始。三、應(yīng)用題(每題10分，共計(jì)40分)1、 某二叉樹中序遍歷的結(jié)果是ABC試畫出其可能的二叉樹五種形態(tài)。(10分)2、某帶權(quán)無(wú)向圖如以下圖所示。圖1.帶權(quán)無(wú)向圖G(1)請(qǐng)用鄰接矩陣法表示該圖。(4分)(2)從頂點(diǎn)0出發(fā)，采用Prim算法畫示最小生成樹的過程

24、。(6分)3、 設(shè)散列表為 T :0.12 ,散列函數(shù)為 H (key) = key%13,給定鍵值序列是 39, 36, 28, 38, 44, 15, 42, 12, 06, 25。(1)請(qǐng)畫出用拉鏈法處理沖突時(shí)所構(gòu)造的散列表。(6分)(2)求出在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度。(4分)4、排序碼值序列17, 18, 60, 40, 7, 32, 73, 65, 85,排序后成后非遞減序列，請(qǐng)寫出冒泡排序每一趟的排序結(jié)果。(10分)四、 算法閱讀題 (每題10分，共計(jì)20分)。1、二叉樹的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedef struct nodeElemType data;/ 數(shù)據(jù)元

25、素struct node *lchild;/ 指向左孩子struct node *rchild;/ 指向右孩子BTNode;閱讀以下二叉樹算法，答復(fù)以下問題。int fun 1(BTNode *b)int lchilddep,rchilddep;if(b=NULL)return 0;elselchilddep=fu n1(b->lchild);rchilddep=fu n1(b->rchild);return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); (1) 該算法執(zhí)行二叉樹運(yùn)算的什么功能？(5分)(2) 假設(shè)存在二

26、叉樹如圖2所示，試問執(zhí)行上述算法后，其執(zhí)行結(jié)果是多少？(5分)圖2.二叉樹2、線性表 R數(shù)據(jù)類型如下：# define max 100Typedef struct int keyinfotypeinfo； Sqnode;Sqnode R max;閱讀下面算法，答復(fù)以下問題。int fun2 sqnode R 口，intn , int kint i= 0 ;R n .key= k;2分，共10分五、算法設(shè)計(jì)題在以下算法的橫線內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句或表達(dá)式。每空 單鏈表的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedef struct LnodeElemType data;Struct Lnode *n ext;Lin

27、kList;假設(shè)ha=a1 , a2, ,an和hb=b1 , b2, , bn是兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表，編,LinkList *hb , LinkList *&hc)寫將這兩個(gè)表合并為帶頭結(jié)點(diǎn)的循環(huán)單鏈表hc的算法。void Merge(LinkList *haLin klist *p = ha->n ext;hc = ha;while ( p -> n ext!= ha )P = (1)；= hb->next;/ 將ha的最后一個(gè)結(jié)點(diǎn)的next指向hb的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)while (p-> next != (3)(4)p_>next = (5),/找到

28、ha的最后一個(gè)結(jié)點(diǎn)*p/找到hb的最后一個(gè)結(jié)點(diǎn)*p/構(gòu)成循環(huán)單鏈表答案如下一、選擇題每題2分，共計(jì)20分DDACD二、填空題1、 n-i+16、4三、應(yīng)用題DCDBB每題1分,2、隊(duì)列7、n共計(jì)10分3、368、邊稀疏4、n+1 x n/29、哈希散列查找5、310、541、每題10分，共計(jì)40分 二叉樹圖形如以下圖 1 : 10分圖1二叉樹的不同形態(tài)評(píng)分標(biāo)準(zhǔn)：每正確畫出一棵二叉樹，得分2分。2、1其鄰接矩陣如下：4分2采用Prim算法畫示最小生成樹的過程如下：6分，每幅圖1分圖2. Prim算法求最小生成樹3、答：1用拉鏈法處理沖突構(gòu)造的散列表如以下圖所示：6分圖3.拉鏈法解決沖突(2)在等

29、概率的情況下，查找成功的平均查找長(zhǎng)度：ASLs= (1X 7+2 X 2+3X 1) /10=1.4(4 分)4、冒泡排序(10分，每趟排序正確得2分)(此答案不唯一)第一趟17,18 ,407 ,32 ,60 ,65 ,73 , 85第二趟17,18 ,7 ,32 ,40 ,60 ,65 ,73第三趟17,7 ,18 ,32 ,40 ,60 ,65第四趟7,17 ,18 ,32 ,40 ,60第五趟：7，17，18，32，4O (沒有發(fā)生交換，結(jié)束排序)四、算法閱讀題(每題10分，共計(jì)20分)1、(1)計(jì)算二叉樹深度。(2)該二叉樹葉子深度是 4。2、 (1)其目的是在 while循環(huán)中省去

30、檢測(cè)整個(gè)表是否查完，R n起到了監(jiān)視哨的作用。(2)順序查找算法，查找成功時(shí)函數(shù)返回值為該結(jié)點(diǎn)的位置，否那么函數(shù)返回值為-1。五、算法設(shè)計(jì)題(每空2分，共計(jì)10分)(1) p-> next (2) p-> next(3) hb p = p-> next(5) he重慶工商大學(xué)試卷考試科目：數(shù)據(jù)結(jié)構(gòu)試卷適用專業(yè)(班)：2004考核方式：開卷()閉卷(V)2005 2006 學(xué)年度 一2_學(xué)期一選擇題(單項(xiàng)選擇，每題 2分，共計(jì)20分)1、 某數(shù)據(jù)的邏輯結(jié)構(gòu)S = (D , R),其中D = a, b, e, d, e, f, R = a, b >,b, e， e, d，d

31、, e， e , f >,請(qǐng)指出它們屬于下面的哪種結(jié)構(gòu) :A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖形結(jié)構(gòu)2、 假設(shè)線性表最常用的運(yùn)算是存取第i個(gè)元素及其前趨的值，那么采用 存儲(chǔ)方式節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表3、 單鏈表中，假設(shè)*p結(jié)點(diǎn)不是末尾結(jié)點(diǎn)，在其后插入*s的操作是 。A.s->n ext = p; p->next = s;B.s->n ext = p->n ext; p->n ext = s;C. s_>next = p_>n ext; p = s;D.p->next = s; s_>next = p;

32、4、經(jīng)過以下棧運(yùn)算后，x的值是 。InitStaek(s); Push(s, a); Push(s, b); Pop(s, x) ; GetTop(s, x);A.aB. bC.1D.05、 最適合用作鏈?zhǔn)疥?duì)列的鏈表是 。A. 帶隊(duì)首指針和隊(duì)尾指針的循環(huán)單鏈表B. 帶隊(duì)首指針和隊(duì)尾指針的非循環(huán)單鏈表C. 只帶隊(duì)首指針的非循環(huán)單鏈表D. 只帶隊(duì)首指針的循環(huán)單鏈表6、 串是一種特殊的線性表，其特殊性表達(dá)在 。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符7、 對(duì)稱矩陣壓縮存儲(chǔ)是為了 。A.方便運(yùn)算B.節(jié)省空間C.提高運(yùn)算速度D.以上都不是8、 高度為h的二叉樹上至

33、多有 個(gè)結(jié)點(diǎn)(h > 1)。A. 2 h-1B. 2 h-1C.2h+1D.2 h9、 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中 。A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)的回路D.最短的回路10、 在采用線性探測(cè)法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)的這些位置上的鍵值 。A.定都是同義詞B.定都不是同義詞C.都相同D.不一定都是同義詞二、填空題(每題1分，共計(jì)10分)1、 具有n個(gè)結(jié)點(diǎn)的單鏈表，在的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 。2、 假設(shè)用一個(gè)大小為 6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 front和rear的值分別為3和0 ,

34、當(dāng)從隊(duì)列中刪除一個(gè)元素，再參加兩個(gè)元素后，front和rear的值分別為 。3、 設(shè)有兩個(gè)串p和q,其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串q在p中的位置的算法稱為 。4、數(shù)組A0.5,0.6( 即數(shù)組A67)的每個(gè)元素占5個(gè)單元，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)內(nèi)存單元中，那么元素 a55的地址為。5、 廣義表A=(a,b，(c,d) ，(e,(f,g), 那么式子 tailheadtailtail(A)的值為。6、 對(duì)任何二叉樹，假設(shè)度為2的結(jié)點(diǎn)數(shù)為n2，那么葉子數(shù)n0=。7、 假設(shè)以4，5，6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，那么其帶權(quán)路徑長(zhǎng)度是 。8、

35、 普里姆(Prim)算法適用于求 的網(wǎng)的最小生成樹。9、 有一個(gè)有序表 R : 1 13 =1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100, 當(dāng)用二分查找法查找值為82的結(jié)點(diǎn)時(shí)，經(jīng) 次比擬查找成功。10、 在各種查找方法中，其平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法是。三、應(yīng)用題(每題10分，共計(jì)40分)1、一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖1所示。(小計(jì)10分)(1)畫出此棵二叉樹。(4分)1 234567 8910 111213 14ABFCGJDEHIK圖1.某二叉樹的順序存儲(chǔ)結(jié)構(gòu)(2) 寫出該二叉樹的先根遍歷和后根遍歷的序列。(6分)2、設(shè)無(wú)向

36、圖有6個(gè)結(jié)點(diǎn)，依次輸入的9條邊為(1,2) , (1,3) , (1,5) , (1,6) , (2,3) , (3,4), (3,5) , (4,5) , (5,6)。1)畫出無(wú)向圖G (4分)2)畫出G的鄰接表(6分)3、 將整數(shù)序列4 , 5 , 7 , 2 , 1 , 3 , 6中的數(shù)依次插入一棵空的二叉排序樹中。(10分)(1)畫出相應(yīng)的二叉排序樹。(6分)(2)求等概率情況下查找成功的平均查找長(zhǎng)度。(4分)4、以關(guān)鍵字序列10 , 2 , 13 , 15 , 12 , 14為例，用堆排序方法進(jìn)行排序。寫出每趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。(請(qǐng)按小根堆進(jìn)行排序)(小計(jì)10分)四、算法

37、閱讀題 (每題10分，共計(jì)20分)。1、二叉樹的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedef struct nodeElemType data;/ 數(shù)據(jù)元素struct node *lchild;/ 指向左孩子struct node *rchild;/ 指向右孩子BTNode;閱讀以下二叉樹算法，答復(fù)以下問題。int fun 1(BTNode *b)int nu m1, nu m2;if(b=NULL)return 0;else if (b->lchild=NULL && b->rchild = NULL)return 1;elsenum仁fun 1(b->lchild)

38、;nu m2=fu n1(b->rchild);return (nu m1+ nu m2); (1) 該算法執(zhí)行二叉樹運(yùn)算的什么功能？(6分)(2) 假設(shè)存在二叉樹如圖2所示二叉樹，試問執(zhí)行上述算法后，其執(zhí)行結(jié)果是多少？(4分)圖2.二叉樹2、L是一個(gè)遞增有序表，x的數(shù)據(jù)類型與L中元素類型一致。執(zhí)行以下算法，問:void fun2 (SeqList &L, DataType x) int i=0,j;while ( i < L.length && L.datai < x)i+;for (j=Len gth; j>=i; j-)L.dataj+1=

39、L.dataj;L.datai = x;L.le ngth + +; (1) 該算法執(zhí)行什么功能？(6分)(2) 假設(shè)初始有序表L=1 ，3，5，8，9，x=7。執(zhí)行上述算法后，該有序表發(fā)生什么變 化？ (4分)五、算法設(shè)計(jì)題(在以下算法的橫線內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句或表達(dá)式。每空2分，共10分)單鏈表的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedef struct Lnode ElemType data;Struct Lnode *n ext;L in kList;設(shè)計(jì)一個(gè)算法，將一個(gè)帶頭結(jié)點(diǎn)的數(shù)據(jù)域依次為a1, a2,an(n >3)的單鏈表的的an，最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域變?yōu)閍1)，生成一采用前插法生成新的

40、單鏈表/掃描所有結(jié)點(diǎn)所有結(jié)點(diǎn)逆置(即第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域變?yōu)?個(gè)新的單鏈表。void Reverse ( Lin kList *& head )Lin kList *p = head -> n ext;head -> next = (1); /while (p !=(2 ) q = p ->next ;llq 指向*p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)p-> next =；/總是將*p作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)head -> next =4; ；答案：一、選擇題每題2分，共計(jì)20分BDBAB1 BBAAD二、填空題每題1分，共計(jì)10分)1、0(1)2、4 和 23、模式匹配4、 11

41、755、d6、 n2+17、698、邊稠密9、410、哈希散列查找三、應(yīng)用題每題10分，共計(jì)40分1、1二叉樹圖形如以下圖1：圖1二叉樹畫正確11個(gè)結(jié)點(diǎn)，得分 4分。畫正確7-10個(gè)結(jié)點(diǎn)，得分 .3分。畫正確4-6個(gè)結(jié)點(diǎn)，得分 2分畫正確2-3個(gè)結(jié)點(diǎn)，得分 1分先根遍歷序列是：ABCDEFGHIJK3分后根遍歷序列是：DECBHIGKJFA3分2、1 4 分圖2.無(wú)向圖26分圖3鄰接矩陣3、1生成的二叉排序樹如以下圖所示：6分圖4.二叉排序樹評(píng)分標(biāo)準(zhǔn)：從插入的第二個(gè)結(jié)點(diǎn)開始計(jì)分，每正確插入一個(gè)結(jié)點(diǎn)，得1分。2查找成功的平均查找長(zhǎng)度是：ASL=1 X 1+2 X 2+3 X 3+4 X 1/7=

42、18/7=2.574、(10 分)初始狀態(tài):10, 2,13 ,15 ,12 ,14第1趟：(2：,10,13 ,15 ,12 ,14)2分第2趟：2,(10,12 ,13 ,15 ,14)2分第3趟：2,10 ,(12 ,14 ,13 ,15)2分第4趟：2,10,12 ,(13 ,14 ,15)2分第5趟：2,10,12 ,13 ,(14 ,15)2分第6趟：2,10,12 ,13 ,14 ,15四、算法閱讀題每題10分，共計(jì)20分1、1計(jì)算二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)。6分2該二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)是4。4分2、(1)在該有序表中新增一個(gè)元素x，并保持該有序表的有序性。(6分)(2)L=1 , 3,

43、5, 7, 8, 9。(4 分)五、算法設(shè)計(jì)題(每空2分，共計(jì)10分)(1)NULL (2)NULL(3) head-next(4) p(5) p=q山東：07年專升本考試數(shù)據(jù)結(jié)構(gòu)模擬試題1一、填空題：(每題2分，共10分)1. 設(shè)有數(shù)據(jù)結(jié)構(gòu)(D, R)，其中D是數(shù)據(jù)元素的有限集，R是的有限集。2. 深度為k的二叉樹其結(jié)點(diǎn)數(shù)至多有個(gè)。3. 棧是一種特殊的線性表，它允許在表的一端進(jìn)行操作。4. 通常象交通、道路問題的數(shù)學(xué)模型是一種稱為 的數(shù)據(jù)結(jié)構(gòu)。5. 哈希表是一種查找表，可以根據(jù)哈希函數(shù)直接獲 得二、 單項(xiàng)選擇題：(每題2分，共10分)對(duì)于以下各題，在備選答案中選出一個(gè)正確的，并將其編號(hào)填在“

44、位置上。1. 假設(shè)線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，那么采用存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表2. 以下排序算法中，算法在進(jìn)行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個(gè)元素放到其最終位置上。A.直選擇排序B.冒泡排序C.歸并排序D.堆排序3. 隊(duì)列的操作原那么是。A.先進(jìn)后出B.先進(jìn)先出C.只能進(jìn)行插入D.只能進(jìn)行刪除4. 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，非空的鏈域個(gè)數(shù)為。A. n-1B. nC. n+1D.不確定5. 對(duì)具有n個(gè)元素的有序查找表采用折半查找算法查找一個(gè)鍵值，其最壞比擬次數(shù)的數(shù)量級(jí)為。A. O(log2 n)B. O(n)C. O(

45、nl og2 n)D. O(n 2)三、判斷題：(每題2分，共10 分)判斷以下各題是否正確，假設(shè)正確，在題后的括號(hào)內(nèi)填“T，否那么填“ F。1. 在棧為空的情況下不能作出棧處理，否那么，將產(chǎn)生下溢出。()2. 如果有向圖G=(V, E)的拓?fù)湫蛄形ㄒ?，那么圖中必定僅有一個(gè)頂點(diǎn)的入度為0、一個(gè)頂點(diǎn)的出度為0。()3. 在大根堆中，必定滿足每個(gè)結(jié)點(diǎn)的鍵值大于其左右子樹中所有結(jié)點(diǎn)的鍵值。(4. 在采用線性探測(cè)法處理沖突的散列表中所有同義詞在表中相鄰。5. 在索引順序表中，對(duì)索引表既可采用順序查找，也可采用二分查找。四、解答以下各題：每題10分，共40分1. 線性表L采用帶頭結(jié)點(diǎn)的的單向循環(huán)鏈表表示

46、，試給出它的存儲(chǔ)結(jié)構(gòu)類型描述及相應(yīng)的示意圖。2. 一棵二叉樹的先序、中序和后序序列如下所示，請(qǐng)?zhí)顚懜餍蛄兄锌崭裉幍慕Y(jié)點(diǎn)，并 畫出該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖。先序序列是：_ B _ F _ I C E H _ G ； 中序序列是：D _ K F I A _ E J C _；后序序列是：_ K _ F B H J _ G _ A3. 數(shù)據(jù)表為48, 70, 33, 65, 24, 56, 12，92, 86, 22, a寫出采用快速排序算法進(jìn)行排序時(shí)第一趟快速劃分的詳細(xì)過程及結(jié)果；b寫出按基數(shù)排序思想對(duì)最低位進(jìn)行一次分配和收集的結(jié)果。4. 對(duì)圖1所示的帶權(quán)無(wú)向圖，寫出它的鄰接矩陣和深度優(yōu)先搜

47、索序列，并按克魯斯卡算法 求其最小生成樹寫出求解的詳細(xì)過程示意圖。圖1 帶權(quán)無(wú)向圖五、 算法設(shè)計(jì)題：前兩題必做，每題15分，共30分；第三題為附加題，選做， 10分1. 隊(duì)列Q以循環(huán)隊(duì)列存儲(chǔ)。寫出Q的存儲(chǔ)結(jié)構(gòu)類型描述，并試編寫算法實(shí)現(xiàn)將元素x插入隊(duì)列Q的入隊(duì)操作EnQueueQ,x和從隊(duì)列Q中獲取隊(duì)首元素的函數(shù)GetTopQ。2. 假設(shè)線性表L=a1,a2,an用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)表示，試編寫算法對(duì)其實(shí)現(xiàn)就地逆置，即利用原鏈表中每一個(gè)結(jié)點(diǎn)存儲(chǔ)空間，使得元素的邏輯次序改變?yōu)閍n,a2,a1。3. 設(shè)非空二叉樹T采用中序線索二叉鏈表表示，寫出T的存儲(chǔ)結(jié)構(gòu)類型描述。試編寫算法InOrderTrav

48、erseT實(shí)現(xiàn)對(duì)二叉樹T的中序遍歷。專升本-山東模擬2一、填空題：每題2分，共10分1. 設(shè)有數(shù)據(jù)結(jié)構(gòu)D , R,其中D是數(shù)據(jù)元素的有限集，R是的有限集。2. 深度為k的二叉樹其結(jié)點(diǎn)數(shù)至多有個(gè)。3. 棧是一種特殊的線性表，它允許在表的一端進(jìn)行操作。4. 通常象交通、道路問題的數(shù)學(xué)模型是一種稱為的數(shù)據(jù)結(jié)構(gòu)。5. 哈希表是一種查找表，可以根據(jù)哈希函數(shù)直接獲得。二、單項(xiàng)選擇題：每題2分，共10分對(duì)于以下各題，在備選答案中選出一個(gè)正確的，并將其編號(hào)填在“位置上。1. 假設(shè)線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，那么采用存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B.雙鏈表 C.單循環(huán)鏈表D.順序表

49、2. 以下排序算法中，算法在進(jìn)行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個(gè)元素放到其最終位置上。A.直選擇排序B.冒泡排序 C.歸并排序D.堆排序3. 隊(duì)列的操作原那么是。A.先進(jìn)后出B.先進(jìn)先出C.只能進(jìn)行插入D.只能進(jìn)行刪除4. 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，非空的鏈域個(gè)數(shù)為。A. n-1 B. n C. n+1 D.不確定5. 對(duì)具有n個(gè)元素的有序查找表采用折半查找算法查找一個(gè)鍵值，其最壞比擬次數(shù)的數(shù) 量級(jí)為 。A. Olog2 n B. 0n C. Onl og2 nD. 0n 2三、 判斷題：每題2分，共10分判斷以下各題是否正確，假設(shè)正確，在題后的括號(hào)內(nèi)填“T；否那么填“F1. 在棧為

50、空的情況下不能作出棧處理，否那么，將產(chǎn)生下溢出。2. 如果有向圖 G=V, E的拓?fù)湫蛄形ㄒ?，那么圖中必定僅有一個(gè)頂點(diǎn)的入度為0、一個(gè)頂點(diǎn)的出度為0。3. 在大根堆中，必定滿足每個(gè)結(jié)點(diǎn)的鍵值大于其左右子樹中所有結(jié)點(diǎn)的鍵值。4. 在采用線性探測(cè)法處理沖突的散列表中所有同義詞在表中相鄰。5. 在索引順序表中，對(duì)索引表既可采用順序查找，也可采用二分查找。四、 解答以下各題：每題10分，共40分1. 線性表L采用帶頭結(jié)點(diǎn)的的單向循環(huán)鏈表表示，試給出它的存儲(chǔ)結(jié)構(gòu)類型描述及相應(yīng)的示意圖。2. 一棵二叉樹的先序、中序和后序序列如下所示，請(qǐng)?zhí)顚懜餍蛄兄锌崭裉幍慕Y(jié)點(diǎn)，并 畫出該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)示意圖。先

51、序序列是：_ B _ F _ I C E H _ G ； 中序序列是：D _ K F I A _ E J C _ ；后序序列是：_ K _ F B H J _ G _ A3. 數(shù)據(jù)表為48, 70，33, 65, 24，56, 12，92，86, 22，a寫出采用快速排序算法進(jìn)行排序時(shí)第一趟快速劃分的詳細(xì)過程及結(jié)果；b寫出按基數(shù)排序思想對(duì)最低位進(jìn)行一次分配和收集的結(jié)果。4. 對(duì)圖1所示的帶權(quán)無(wú)向圖，寫出它的鄰接矩陣和深度優(yōu)先搜索序列，并按克魯斯卡算法求其最小生成樹寫出求解的詳細(xì)過程示意圖。圖1 帶權(quán)無(wú)向圖五、算法設(shè)計(jì)題：前兩題必做，每題 15分，共30分；第三題為附加題，選做， 10分1. 隊(duì)列 Q以循環(huán)隊(duì)列存儲(chǔ)。寫出Q的存儲(chǔ)結(jié)構(gòu)類型描述，并試編寫算法實(shí)現(xiàn)將元素x插入隊(duì)列Q的入隊(duì)操作EnQueueQ,x和從隊(duì)列Q中獲取隊(duì)首元素的函數(shù)GetTopQ。2. 假設(shè)線性表 L=a1,a2, ,an用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)表示，試編寫算法對(duì)其實(shí)現(xiàn)就地逆置，即利用原鏈表中每一個(gè)結(jié)點(diǎn)存儲(chǔ)空間，使得元素的邏輯次序改變?yōu)閍n, ,a2,a13. 設(shè)非空二叉樹 T采用中序線索二叉鏈表表示，寫出T的存儲(chǔ)結(jié)構(gòu)類型描述。試編寫算法 InOrderTraverseT實(shí)現(xiàn)對(duì)二叉樹 T的中序遍歷。文章錄入：fly800責(zé)任編輯：fly800上一篇文章：山東：2007年