正在為2016年考研備考的考生，現(xiàn)在的首要任務(wù)就是將基礎(chǔ)知識(shí)打牢，為了幫助考生將基礎(chǔ)知識(shí)復(fù)習(xí)的更加牢固，唯學(xué)網(wǎng)小編準(zhǔn)備了大量的輔導(dǎo)資料及試題，下面便是小編準(zhǔn)備的2016年考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案，以供各位考生備考使用。

一、選擇題(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) 45

2.執(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，72]

3.設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是( )。

(A) head==0 (B) head->next==0

(C) head->next==head (D) head!=0

4.時(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) 6

8.順序查找不論在順序線性表中還是在鏈?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-1

11.設(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; (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) 102

14.設(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)

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ù)之和

二、判斷題(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è)有序的序列。( )

10.快速排序是排序算法中平均性能最好的一種排序。( )

三、填空題(30分)

1.for(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>，<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.散列表中解決沖突的兩種方法是_____________和_____________。

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

1.1. 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

2.2. 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。

3.3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法

參考答案

一、選擇題

1.D 2.A 3.A 4.A 5.D

6.D 7.B 8.A 9.C 10.B

11.C 12.A 13.B 14.D 15.B

二、判斷題

1.錯(cuò) 2.對(duì) 3.對(duì) 4.對(duì) 5.錯(cuò)

6.錯(cuò) 7.對(duì) 8.錯(cuò) 9.對(duì) 10.對(duì)

三、填空題

1. 1. O(n)

2. 2. s->next=p->next; p->next=s

3. 3. (1，3，2，4，5)

4. 4. n-1

5. 5. 129

6. 6. F==R

7. 7. p->lchild==0&&p->rchild==0

8. 8. O(n2)

9. 9. O(nlog2n)， O(n)

10. 10. 開(kāi)放定址法，鏈地址法

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

1. 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(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1;

}

return(0);

}

2. 2. 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。

int minnum=-32768,flag=1;

typedef struct node{int 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. 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) if (s->data>p->data) break;

if(s==q->next)q=p;

else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;}

}

}

以上為2016年考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案，希望對(duì)考生們能有所幫助，若想了解更多研究生相關(guān)信息，如考研改革、考研考試等，請(qǐng)關(guān)注唯學(xué)網(wǎng)考研欄目，小編會(huì)第一時(shí)間為你更新最新資訊。