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

1、數(shù)據(jù)結(jié)構(gòu)模擬試題04一、單項(xiàng)選擇題（每題 2 分，共20分）1組成數(shù)據(jù)的基本單位是（ ）。 (A) 數(shù)據(jù)項(xiàng)(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) 隊(duì)列(D) 樹4二叉樹中第i(i1)層上的結(jié)點(diǎn)數(shù)最多有（ ）個(gè)。(A) 2i(B) 2i(C) 2i-1(D) 2i-15設(shè)

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

3、5(D) 808設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)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)隊(duì)列Q0：m-1的隊(duì)頭指針和隊(duì)尾指針分別為F和R，其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)列的語(yǔ)句為F =_;。2. 設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上

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

5、到下、從左到右的順序從1開始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是_，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是_。9. 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)句。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è)連通圖G中有n個(gè)頂點(diǎn)e條邊，則其最小生成樹上有_條邊。三、運(yùn)算題（每題

6、 6 分，共30分）1設(shè)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2設(shè)給定一個(gè)權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計(jì)算哈夫曼樹的帶權(quán)路徑長(zhǎng)度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)，散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。5設(shè)無向圖G（所下圖所

7、示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計(jì)題（每題10分，共30分）1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法。3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題04參考答案一、單項(xiàng)選擇題（每題 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三、算法簡(jiǎn)答題（每題 6分，共30分）1. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2. 哈夫曼樹略，WPL=783. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 線性探測(cè)：鏈地址法：5. 深度：125364，廣度：123456，最小生成樹T的邊集為E=(1，4)，(1，3)，(3，5)，(5，6)，(5,6)四、算法設(shè)計(jì)題（每題10分，共30分）1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。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è)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(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è)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct