• 一、選擇題

1、下列程序段的時(shí)間復(fù)雜度為（? ）。?
for(i=0;i<m;i++)?
?? for(j=0;j<t;j++)?
???? c[i][j]=0；?
for(i=0;i<m;i++)?
?? for(j=0;j<t;j++)?
???? for(k=0;k<n;k++)?
?????? c[i][j]=c[i][j]+a[i][k]*b[k][j]；?
(A) O(m*n*t)?????
(B) O(m+n+t)???
(C) O(m+n*t)????
(D) O(m*t+n)

C語言之父

參考答案是：A

2、設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動（? ）個(gè)元素。?
(A) n-i?????????
(B) n+1-i?????
(C) n-1-i???????
(D) i

參考答案是：A

3、設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)
點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（?? ）。?
(A) N1-1?????????
(B) N2-1????????
(C) N2+N3???????
(D) N1+N3

參考答案是：A

4、利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（? ）。?
(A) O(n)?????????
(B) O(nlog2n)???
(C) O(n2)??????
(D) O(1og2n)

參考答案是：C

5、設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（? ）。?
(A) p->right=s； s->left=p； p->right->left=s； s->right=p->right；?
(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；?
(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；?
(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；

參考答案是：D

6、下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（?? ）。?
(A) 快速排序????
(B) 堆排序??????
(C) 歸并排序???
(D) 冒泡排序

參考答案是：D

7、設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（? ）。?
(A) n-i??????????
(B) n-1-i??????
(C) n+1 -i??????
(D) 不能確定

參考答案是：C

8、設(shè)散列表中有m個(gè)存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇（? ）。
(A) 小于等于m的最大奇數(shù)??????????
(B) 小于等于m的最大素?cái)?shù)?
(C) 小于等于m的最大偶數(shù)?????????
(D) 小于等于m的最大合數(shù)

參考答案是：B

9、設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（? ）個(gè)。?
(A) 4???????????
(B) 5???????????
(C) 6??????????
(D) 7

參考答案是：C

10、設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（? ）條邊。?
(A) n(n-1)/2?????
(B) n(n-1)?????
(C) n(n+1)/2????
(D) (n-1)/2

參考答案是：A

11、設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（? ）。?
(A) n????????????
(B) n/2?????????
(C) (n+1)/2?????
(D) (n-1)/2

參考答案是：C

12、設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（? ）次比較。?
(A) 1???????????
(B) 2???????????
(C) 3??????????
(D) 4

參考答案是：C

13、設(shè)順序線性表的長度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長度為（? ）。?
(A) 6????????????
(B) 11??????????
(C) 5??????????
(D) 6.5

參考答案是：D

14、設(shè)有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?#xff08;? ）。?
(A) 1，2，3，4???
(B) 2，3，4，1??
(C) 1，4，2，3?
(D) 1，2，4，3

參考答案是：A

15、設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（? ）。?
(A) 4???????????
(B) 5???????????
(C) 6??????????
(D) 7

參考答案是：A

二、填空題

1、設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：
1) s->next=___________；
2) p->next=s；
3) t=p->data；
4) p->data=___________；
5) s->data=t；

參考答案是：p->next，s->data

2、設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有______________個(gè)葉子結(jié)點(diǎn)。

參考答案是：50

3、設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)
隊(duì)列中最多存儲_______隊(duì)列元素。

參考答案是：m-1

4、對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為
__________，在整個(gè)排序過程中最多需要進(jìn)行__________趟排序才可以完成。

參考答案是：6，8

5、在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序，如果從節(jié)省存儲空間的角
度來考慮則最好選擇________排序。

參考答案是：快速，堆

6、設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是
____________。

參考答案是：19/7

7、設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。

參考答案是：CBDA

8、設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值
構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。

參考答案是：6

9、設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。

參考答案是：(24，65，33，80，70，56，48)

10、設(shè)無向圖G（如下圖所示），則其最小生成樹上所有邊的權(quán)值之和為_________________。
?

參考答案是：8

三、判斷題

1、有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。(? )

參考答案是：錯(cuò)

2、對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。(? )

參考答案是：對

3、子串“ABC”在主串“AABCABCD”中的位置為2。(? )

參考答案是：對

4、若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。(? )

參考答案是：對

5、希爾排序算法的時(shí)間復(fù)雜度為O(n2)。(? )

參考答案是：錯(cuò)

6、用鄰接矩陣作為圖的存儲結(jié)構(gòu)時(shí)，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。(? )

參考答案是：錯(cuò)

7、中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。(? )

參考答案是：對

8、入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。(? )

參考答案是：對

9、順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（? ）

參考答案是：錯(cuò)

10、堆是完全二叉樹，完全二叉樹不一定是堆。（? ）

參考答案是：對

四、算法設(shè)計(jì)題

1、設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。

參考答案是：void?sum(bitree?*bt,int?&s) {if(bt!=0)?{s=s+bt->data;?sum(bt->lchild,s);?sum(bt->rchild,s);} }

2、設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。

參考答案是：void?quickpass(int?r[],?int?s,?int?t) {int?i=s,j=t,x=r[s];while(i<j){while(i<j?&&?r[j]%2==0)?j=j-1;??if(i<j)?{r[i]=r[j];i=i+1;}while(i<j?&&?r[i]%2==1)?i=i+1;??if?(i<j)?{r[j]=r[i];j=j-1;}}r[i]=x; }

3、設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。

參考答案是：int?isriselk(lklist?*head) {if(head==0||head->next==0)?return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)?return(0);return(1); }

來源：我是碼農(nóng)，轉(zhuǎn)載請保留出處和鏈接！

本文鏈接：http://www.54manong.com/?id=53

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })(); '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();

總結(jié)

以上是生活随笔為你收集整理的数据结构试卷及答案（九）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。