正在為2016年考研備考的考生，現在的首要任務就是將基礎知識打牢，為了幫助考生將基礎知識復習的更加牢固，唯學網小編準備了大量的輔導資料及試題，下面便是小編準備的2016年考研計算機數據結構練習題及答案，以供各位考生備考使用。
一、選擇題(30分)
1. 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為( )。
(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.設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時間復雜度不受數據初始狀態(tài)影響而恒為O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5.設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。
(A) 空或只有一個結點 (B) 高度等于其結點數
(C) 任一結點無左孩子 (D) 任一結點無右孩子
6.一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7.設某棵三叉樹中有40個結點，則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸并排序的時間復雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有( )個結點。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為( )。
(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.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有( )個葉子結點。
(A) 99 (B) 100 (C) 101 (D) 102
14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為( )。
(A) 第i行非0元素的個數之和 (B) 第i列非0元素的個數之和
(C) 第i行0元素的個數之和 (D) 第i列0元素的個數之和
二、判斷題(20分)
1.調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。( )
2.分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。( )
3.冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數最多。( )
4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。( )
5.設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。( )
6.層次遍歷初始堆可以得到一個有序的序列。( )
7.設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。( )
8.線性表的順序存儲結構比鏈式存儲結構更好。( )
9.中序遍歷二叉排序樹可以得到一個有序的序列。( )
10.快速排序是排序算法中平均性能最好的一種排序。( )
三、填空題(30分)
1.for(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時間復雜度為_________。
2.設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________(設結點的指針域為next)。
3.設有向圖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>}，則給出該圖的一種拓撲排序序列__________。
4.設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多是_________。
5.設二叉樹中度數為0的結點數為50，度數為1的結點數為30，則該二叉樹中總共有_______個結點數。
6.設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。
7.設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。
8.簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。
9.快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。
10.散列表中解決沖突的兩種方法是_____________和_____________。
四、算法設計題(20分)
1.1. 設計在順序有序表中實現二分查找的算法。
2.2. 設計判斷二叉樹是否為二叉排序樹的算法。
3.3. 在鏈式存儲結構上設計直接插入排序算法
參考答案
一、選擇題
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.錯 2.對 3.對 4.對 5.錯
6.錯 7.對 8.錯 9.對 10.對
三、填空題
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. 開放定址法，鏈地址法
四、算法設計題
1. 1. 設計在順序有序表中實現二分查找的算法。
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. 設計判斷二叉樹是否為二叉排序樹的算法。
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. 在鏈式存儲結構上設計直接插入排序算法
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年考研計算機數據結構練習題及答案，希望對考生們能有所幫助，若想了解更多研究生相關信息，如考研改革、考研考試等，請關注唯學網考研欄目，小編會第一時間為你更新最新資訊。
招研究生.png)
