《數(shù)據(jù)結(jié)構(gòu)》練習(xí)題及答案 清華出版社

《《數(shù)據(jù)結(jié)構(gòu)》練習(xí)題及答案 清華出版社》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》練習(xí)題及答案 清華出版社（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 《數(shù)據(jù)結(jié)構(gòu)》模擬題 2010年7月 ? 一、單選題 （每空2分，共10分） 1、隊(duì)列的刪除操作是在（ ）進(jìn)行。 A．隊(duì)首 B．隊(duì)尾 C．隊(duì)前 D．對后 2、當(dāng)利用大小為N 的數(shù)組順序存儲一個棧時，假定用top = = N表示?？?，則退棧時，用（ ）語句修改top指針。 A．top++; B．top=0; C．top--; D．top=N; 3、由權(quán)值分別為3,6,7,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）。 A．51 B．23 C．53 D．74 4、在一棵二叉樹

2、中，第4層上的結(jié)點(diǎn)數(shù)最多為（ ）。 A．31 B．8 C.15 D．16 5、 向堆中插入一個元素的時間復(fù)雜度為（ ）。 A．O(log2n) B．O(n) C．O(1) D． O(nlog2n) ? 二、填空題（每空1分，共20分） 1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為____________、___________、____________和____________四種。 2、若對一棵二叉樹的結(jié)點(diǎn)編號從1開始順序編碼，按順序存儲，把編號為1的結(jié)點(diǎn)存儲到a[1]中，其余類推，則a[i]元素的左孩子元素為______，右孩子元素為

3、_____，雙親元素(i>0)為________。 3、從一個棧刪除元素時，首先取出 ，然后再前移一位 。 4、后綴表達(dá)式“2 10 + 5 * 6 – 9 /”的值為 。 5、假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J)),K)，則度為3、2、1、0的結(jié)點(diǎn)數(shù)分別為______、______、______和______個。 6、在一個具有n個頂點(diǎn)的無向完全圖中，包含有________條邊，在一個具有n個頂點(diǎn)的有向完全圖中，包含有________條邊。 7、在索引表中，若一個索引項(xiàng)對應(yīng)主表中的

4、一條記錄，則稱此索引為________索引，若對應(yīng)主表中的若干條記錄，則稱此索引為________索引。 8、對于二分查找所對應(yīng)的判定樹，它既是一棵_ ____，又是一棵_____ __ ___。 三、運(yùn)算題（每小題5分，共10分） 1、 1、 空堆開始依次向堆中插入線性表（64,52, 12,48,45,26）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。（為小根堆） ? ?2、在一份電文中共使用五種字符：A，G，F(xiàn)，U，Y，Z，它們的出現(xiàn)頻率依次為12,9,18,7,14，11，求出每個字符的哈夫曼編碼。 ? 四、閱讀算法，回答問題（每小題5分，共

5、20分） 1、void AA (LNode * HL,const ElemType & item) { LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL; while ( p->next!=HL ) p=p->next; newptr->next=HL; p->next=newptr; } 對于結(jié)點(diǎn)類型為LNode的單鏈表，以上算法的功能為： ?? 2、void BB(List &L) { int i=0; while (i

6、+1; while (j

7、后，生成的二叉搜索數(shù)的中序序列為： ? ?4、void DD ( ) { ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9); for ( int i=0; i<10; i++) cout<

8、ode; InitList (head); int i; for (i=0;inext; i=0; while ( ) { a[i++]=p->data; } ClearList (head); } ? 六、編寫算法(10分) 編寫一個非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對應(yīng)的索引項(xiàng)，即索引值剛好大于等于K的索引項(xiàng)，返回該索引項(xiàng)的sta

9、rt域的值，若查找失敗則返回-1。 《數(shù)據(jù)結(jié)構(gòu)》模擬題答案及評分標(biāo)準(zhǔn) （供參考） 一、單選題 （每空2分，共10分） 1、A 2、 A 3、A 4、 B 5 、A 二、填空題（每空1分，共20分） 1、順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu) 2、2i+1、2i+2、 3、棧頂元素、棧頂指針 4、6 5、2、2、0、7 6、n(n-1)/2 、n(n-1) 7、稠密、稀疏 8、二叉搜索樹、理想平衡樹 三、運(yùn)算題（每小題5分，共10分） 1、（64） （52，64） （12，64，5

10、2） （12，48，52，64） （12，45，52，64，48） （12，45，26，64，48，52） 2、 A：111 G：011 F：10 U：010 Y：00 Z：110 （或0、1 相反） ? 四、閱讀算法，回答問題（每小題5分，共20分） 1、向單鏈表的末尾添加一個元素。 2、刪除線性表中所有重復(fù)的元素。 3、23 25 35 45 77 78 4、 1 2 3 4 5 6 7 8 9

11、 10 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)。 p!=NULL p=p->next; delete head; 六、編寫算法(10分) int Binsch(IndexList B, int m, IndexKeyType K) { int low=0, high=m-1; while (low<= high) { int mid=(low+high)/2; if (K= =B[mid]. index ) return B[mid].start; else if (K