《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測試題帶答案 (4)

1、數(shù)據(jù)結(jié)構(gòu)模擬試題04一、單項選擇題（每題 2 分，共20分）1組成數(shù)據(jù)的基本單位是（ ）。 (A) 數(shù)據(jù)項(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D=1，2，3，4，R=r，r=<1，2>，<2，3>，<3，4>，<4，1>，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu) (C) 圖型結(jié)構(gòu)(D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列（ ）的邏輯結(jié)構(gòu)。(A) 線性表(B) 棧 (C) 隊列(D) 樹4二叉樹中第i(i1)層上的結(jié)點數(shù)最多有（ ）個。(A) 2i(B) 2i(C) 2i-1(D) 2i-15設(shè)

2、指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（ ）。(A) p->next=p->next->next(B) p=p->next(C) p=p->next->next(D) p->next=p6設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是（ ）。(A) 6(B) 4(C) 3(D) 27將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（ ）。(A) 100(B) 40(C) 5

3、5(D) 808設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為（ ）。(A) 3(B) 4(C) 5(D) 19根據(jù)二叉樹的定義可知二叉樹共有（ ）種不同的形態(tài)。(A) 4(B) 5(C) 6(D) 710. 設(shè)有以下四種排序方法，則（ ）的空間復(fù)雜度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希爾排序二、填空題（每題2分，共20分）1. 設(shè)順序循環(huán)隊列Q0：m-1的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當(dāng)前隊頭元素的前一個位置，隊尾指針R指向當(dāng)前隊尾元素所在的位置，則出隊列的語句為F =_;。2. 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上

4、實現(xiàn)順序查找的平均時間復(fù)雜度為_，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_。3. 設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有_個指針域，_個空指針域。4. 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點B，則在結(jié)點A的后面插入結(jié)點B的操作序列為_。5. 設(shè)無向圖G中有n個頂點和e條邊，則其對應(yīng)的鄰接表中有_個表頭結(jié)點和_個表結(jié)點。6. 設(shè)無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有_關(guān)系。7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為_。8. 設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上

5、到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是_，編號為8的左孩子結(jié)點的編號是_。9. 下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。int index(char s , char t )i=j=0;while(i<strlen(s) && j<strlen(t) if(si=tj)i=i+l; j=j+l;elsei=_; j=_;if (j=strlen(t)return(i-strlen(t);else return (-1);10. 設(shè)一個連通圖G中有n個頂點e條邊，則其最小生成樹上有_條邊。三、運算題（每題

6、 6 分，共30分）1設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2設(shè)給定一個權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。3設(shè)一組初始記錄關(guān)鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4設(shè)一組初始記錄關(guān)鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設(shè)計哈希表。5設(shè)無向圖G（所下圖所

7、示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計題（每題10分，共30分）1. 設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。3. 設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題04參考答案一、單項選擇題（每題 2 分，共20分）1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空題（每小題2分，共20分）1.   (F+1) % m2. O(n)，O(n)3. 2n，n+14. s->next=p->next; s->next=s5. n, 2e6. m

8、=2e7.   CBA8. 4，169. i-j+1，010. n-1三、算法簡答題（每題 6分，共30分）1. 鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2. 哈夫曼樹略，WPL=783. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 線性探測：鏈地址法：5. 深度：125364，廣度：123456，最小生成樹T的邊集為E=(1，4)，(1，3)，(3，5)，(5，6)，(5,6)四、算法設(shè)計題（每題10分，共30分）1. 設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。typedef struct int s100; int to

9、p; sqstack;int lklistsymmetry(lklist *head) sqstack stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p->next) stack.top+; stack.sstack.top=p->data; for(p=head;p!=0;p=p->next) if (p->data=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1);2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。typedef

10、char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt) char ch; scanf("%c",&ch); if(ch='#') bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt->data=ch;createbitree(bt->lchild); createbitree(bt->rchild);3. 設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct