• 一、選擇題

1、設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（? ）。?
(A) O(n)?????????
(B) O(nlog2n)???
(C) O(1)????????
(D) O(n2)

參考答案是：C

2、設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（? ）個(gè)結(jié)點(diǎn)。?
(A) 2k-1?????????
(B) 2k?????????
(C) 2k-1?????????
(D) 2k-1

參考答案是：D

3、設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為（? ）。?
(A) n???????????
(B) e???????????
(C) 2n??????????
(D) 2e

參考答案是：D

4、在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（? ）。?
(A) O(1)????????
(B) O(n)????????
(C) O(log2n)???
(D) O(n2)

參考答案是：B

5、設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（? ）條有向邊。?
(A) n????????????
(B) n-1?????????
(C) m???????????
(D) m-1

參考答案是：C

6、設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（? ）趟的分配和回收才能使得初始關(guān)鍵字
序列變成有序序列。?
(A) 3????????????
(B) 4??????????
(C) 5???????????
(D) 8

參考答案是：A

7、設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（? ）。?
(A) 必須判別棧是否為滿(mǎn)??????????
(B) 必須判別棧是否為空?
(C) 判別棧元素的類(lèi)型????????????
(D) 對(duì)棧不作任何判別

參考答案是：B

8、下列四種排序中（? ）的空間復(fù)雜度最大。?
(A) 快速排序????
(B) 冒泡排序????
(C) 希爾排序????
(D) 堆

參考答案是：A

9、設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的（? ）。

(A) N0=N1+1??
(B) N0=Nl+N2?
(C) N0=N2+1??
(D) N0=2N1+l

參考答案是：C

10、設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)（? ）。?
(A) log2n+1??????
(B) log2n-1?????
(C) log2n???????
(D) log2(n+1)

參考答案是：A

二、填空題

1、設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為_(kāi)_______，快速排序的平均時(shí)間復(fù)雜度為_(kāi)________。

參考答案是：O(n2)，O(nlog2n)

2、設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為_(kāi)______________________________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。

參考答案是：p>llink->rlink=p->rlink; p->rlink->llink=p->rlink

3、根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹(shù)的高度為_(kāi)___________。

參考答案是：3

4、深度為k的完全二叉樹(shù)中最少有____________個(gè)結(jié)點(diǎn)。

參考答案是：2k-1

5、設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個(gè)元素開(kāi)始進(jìn)行篩選。

參考答案是：n/2

6、設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有_________個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有_____個(gè)空指針
域。

參考答案是：50，51

7、設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)_________個(gè)隊(duì)
列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。

參考答案是：m-1，(R-F+M)%M

8、設(shè)順序線(xiàn)性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元
素需要移動(dòng)表中_______個(gè)元素。

參考答案是：n+1-i，n-i

9、設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為_(kāi)__________。

參考答案是：(19，18，16，20，30，22)

10、設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)____________。

參考答案是：(16，18，19，20，32，22)

11、設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是_______________。

參考答案是：A[i][j]=1

12、設(shè)無(wú)向圖對(duì)應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè)數(shù)_________第i列上非0元素的個(gè)數(shù)（填等于，大于或小于）。

參考答案是：等于

13、設(shè)前序遍歷某二叉樹(shù)的序列為ABCD，中序遍歷該二叉樹(shù)的序列為BADC，則后序遍歷該二叉樹(shù)的序列為_(kāi)____________。

參考答案是：BDCA

14、設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線(xiàn)處填上正確的語(yǔ)句完成在散列表hashtalbe中查找
關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。

typedef struct node?
{
???? int key;
???? struct node *next;
} lklist;?
void createlkhash(lklist *hashtable[ ])
{
???? int i,k;? lklist *s;
???? for(i=0;i<m;i++)_____________________;
???? for(i=0;i<n;i++)
???? {
???????? s=(lklist *)malloc(sizeof(lklist));?
???????? s->key=a[i];
???????? k=a[i] % p;?
???????? s->next=hashtable[k];
???????? _______________________;
???? }
}

參考答案是：hashtable[i]=0，hashtable[k]=s

三、計(jì)算題

1、畫(huà)出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。

參考答案是：

2、下圖所示的森林：　　
（1） 求樹(shù)（a）的先根序列和后根序列；?
（2） 求森林先序序列和中序序列；
（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；
?

參考答案是：(1) ABCDEF; BDEFCA；
(2) ABCDEFGHIJK; BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；
(3)

3、設(shè)散列表的地址范圍是[ 0..9 ]，散列函數(shù)為H（key）= （key2?+2）MOD 9,并采用鏈表處理沖突，請(qǐng)畫(huà)出元素7、4、5、3、6、
2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。

參考答案是：H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

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

1、設(shè)單鏈表中有僅三類(lèi)字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使
每個(gè)單鏈表只包含同類(lèi)字符。

參考答案是：typedef?char?datatype; typedef?struct?node {datatype?data;?struct?node?*next; }lklist; void?split(lklist?*head,lklist?*&ha,lklist?*&hb,lklist?*&hc) {lklist?*p;?ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;?p->next=0;if(p->data>='A'?&&?p->data<='Z')?{p->next=ha;?ha=p;}else?if(p->data>='0'?&&?p->data<='9')?{p->next=hb;?hb=p;}?else?{p->next=hc;?hc=p;}} }

2、設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。

參考答案是：typedef?struct?node? {int?data;?struct?node?*lchild,*rchild; }?bitree; void?swapbitree(bitree?*bt) {bitree?*p;if(bt==0)?return;swapbitree(bt->lchild);?swapbitree(bt->rchild);p=bt->lchild;?bt->lchild=bt->rchild;?bt->rchild=p; }

3、在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。

參考答案是：#define?n?10 typedef?struct?node {int?key;?struct?node?*lchild,*rchild; }bitree; void?bstinsert(bitree?*&bt,int?key) {if(bt==0){bt=(bitree?*)malloc(sizeof(bitree));?bt->key=key;bt->lchild=bt->rchild=0;}else?if(bt->key>key)?bstinsert(bt->lchild,key);?else?bstinsert(bt->rchild,key); } void?createbsttree(bitree?*&bt) {int?i;for(i=1;i<=n;i++)?bstinsert(bt,random(100)); }

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

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

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

總結(jié)

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

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