《《數(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
《數(shù)據(jù)結(jié)構(gòu)》練習(xí)題及答案 清華出版社
