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

1、數(shù)據(jù)結(jié)構(gòu)模擬試題09一、單項(xiàng)選擇題（每題 2 分，共30分）1 設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為（ ）。(A) 20(B) 30(C) 40(D) 452執(zhí)行一趟快速排序能夠得到的序列是（ ）。(A) 41，12，34，45，27 55 72，63(B) 45，34，12，41 55 72，63，27(C) 63，12，34，45，27 55 41，72(D) 12，27，45，41 55 34，63，723設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（ ）。(A) head=0(B) head->next=0

2、(C) head->next=head(D) head!=04時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（ ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序5設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是（ ）。(A) 空或只有一個(gè)結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無(wú)左孩子(D) 任一結(jié)點(diǎn)無(wú)右孩子6一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（ ）。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希爾排序7設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（ ）。(A) 3(B) 4(C) 5(D) 68

3、順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)9二路歸并排序的時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)10. 深度為k的完全二叉樹(shù)中最少有（ ）個(gè)結(jié)點(diǎn)。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-111.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（ ）。(A) front->next=s；front=s；(

4、B) s->next=rear；rear=s；(C) rear->next=s；rear=s；(D) s->next=front；front=s；12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（ ）。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n3)13.設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（ ）個(gè)葉子結(jié)點(diǎn)。(A) 99(B) 100(C) 101(D) 10214.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n

5、)15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。(A) 第i行非0元素的個(gè)數(shù)之和(B) 第i列非0元素的個(gè)數(shù)之和(C) 第i行0元素的個(gè)數(shù)之和(D) 第i列0元素的個(gè)數(shù)之和二、填空題（每題2分，共20分）1for(i=1，t=1，s=0；i<=n；i+) t=t*i；s=s+t；的時(shí)間復(fù)雜度為_(kāi)。2設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為_(kāi)（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。3設(shè)有向圖G的二元組形式表示為G =（D，R），D=1，2，3，4，5，R=r，r=<1,2>，<2,4>，<

6、4,5>，<1,3>，<3,2>，<3,5>，則給出該圖的一種拓?fù)渑判蛐蛄衉。4設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_。5設(shè)二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹(shù)中總共有_個(gè)結(jié)點(diǎn)數(shù)。6設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_(kāi)。7設(shè)二叉樹(shù)中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_。8簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為_(kāi)。9快速排序算法的空間復(fù)雜度平均情況下為_(kāi)，最壞的情況下為_(kāi)。10.散列表中解決沖突

7、的兩種方法是_和_。三、判斷題（每題 2 分，共20分）1調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。（ ）2分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（ ）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）4滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。（ ）5設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（ ）6層次遍歷初始堆可以得到一個(gè)有序的序列。（ ）7設(shè)一棵樹(shù)T可以轉(zhuǎn)化成二叉樹(shù)BT，則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。（ ）8線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ ）9中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。（ ）

8、10.快速排序是排序算法中平均性能最好的一種排序。（ ）四、算法設(shè)計(jì)題（每題10分，共30分） 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題09參考答案一、單項(xiàng)選擇題（每題 2 分，共30分）1D2A3A4A5D6D7B8A9C10B11C 12A 13B 14D 15B二、填空題（每小題2分，共20分）1. O(n)2. s->next=p->next; p->next=s3. (1，3，2，4，5)4. n-15. 1296. F=R7. p->lchild=0&&a

9、mp;p->rchild=08. O(n2)9. O(nlog2n)， O(n)10. 開(kāi)放定址法，鏈地址法三、判斷題（每題 2分，共20分）1錯(cuò)2對(duì)3對(duì)4對(duì)5錯(cuò)6錯(cuò)7對(duì)8錯(cuò)9對(duì)10對(duì)四、算法設(shè)計(jì)題（每題10分，共30分）1. 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。struct record int key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(low<=high) mid=(low+high)/2; if(rmid.key=k) return(mid+1);

10、else if(rmid.key>k) high=mid-1; else low=mid+1; return(0);2. 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitree;void inorder(bitree *bt) if (bt!=0) inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法void straightinsertsort(lklist *&head) lklist *s,*p,*q; int t; if (head=0 | head->next=0) return; else for(q=head,p=head->next;p!=0;p=q->next) for(s=head;s!=q->next;s=s->next) i