一、選擇題(30分)
1. 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為( )。
(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且該鏈表沒有頭結(jié)點，則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。
(A) 空或只有一個結(jié)點 (B) 高度等于其結(jié)點數(shù)
(C) 任一結(jié)點無左孩子 (D) 任一結(jié)點無右孩子
6.一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7.設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸并排序的時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有( )個結(jié)點。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔?，指針變量s指向?qū)⒁腙犃械慕Y(jié)點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.設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有( )個葉子結(jié)點。
(A) 99 (B) 100 (C) 101 (D) 102
14.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為( )。
(A) 第i行非0元素的個數(shù)之和 (B) 第i列非0元素的個數(shù)之和
(C) 第i行0元素的個數(shù)之和 (D) 第i列0元素的個數(shù)之和
二、判斷題(20分)
1.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。( )
2.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。( )
3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。( )
4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。( )
5.設(shè)一棵二叉樹的先序序列和后序序列，則能夠確定出該二叉樹的形狀。( )
6.層次遍歷初始堆可以得到一個有序的序列。( )
7.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。( )
8.線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。( )
9.中序遍歷二叉排序樹可以得到一個有序的序列。( )
10.快速排序是排序算法中平均性能的一種排序。( )
三、填空題(30分)
1.for(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時間復(fù)雜度為_________。
2.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為__________________________(設(shè)結(jié)點的指針域為next)。
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è)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。
5.設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_______個結(jié)點數(shù)。
6.設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。
7.設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。
8.簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。
9.快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。
10.散列表中解決沖突的兩種方法是_____________和_____________。
四、算法設(shè)計題(20分)
1.1. 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。
2.2. 設(shè)計判斷二叉樹是否為二叉排序樹的算法。
3.3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法
答案
一、選擇題
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. 開放定址法，鏈地址法
四、算法設(shè)計題
1. 1. 設(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è)計判斷二叉樹是否為二叉排序樹的算法。
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)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法
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;}
}
}
1. 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為( )。
(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且該鏈表沒有頭結(jié)點，則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。
(A) 空或只有一個結(jié)點 (B) 高度等于其結(jié)點數(shù)
(C) 任一結(jié)點無左孩子 (D) 任一結(jié)點無右孩子
6.一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7.設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸并排序的時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有( )個結(jié)點。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔?，指針變量s指向?qū)⒁腙犃械慕Y(jié)點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.設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有( )個葉子結(jié)點。
(A) 99 (B) 100 (C) 101 (D) 102
14.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為( )。
(A) 第i行非0元素的個數(shù)之和 (B) 第i列非0元素的個數(shù)之和
(C) 第i行0元素的個數(shù)之和 (D) 第i列0元素的個數(shù)之和
二、判斷題(20分)
1.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。( )
2.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。( )
3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。( )
4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。( )
5.設(shè)一棵二叉樹的先序序列和后序序列，則能夠確定出該二叉樹的形狀。( )
6.層次遍歷初始堆可以得到一個有序的序列。( )
7.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。( )
8.線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。( )
9.中序遍歷二叉排序樹可以得到一個有序的序列。( )
10.快速排序是排序算法中平均性能的一種排序。( )
三、填空題(30分)
1.for(i=1，t=1，s=0;i<=n;i++) {t=t*i;s=s+t;}的時間復(fù)雜度為_________。
2.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為__________________________(設(shè)結(jié)點的指針域為next)。
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è)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。
5.設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_______個結(jié)點數(shù)。
6.設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。
7.設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。
8.簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。
9.快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。
10.散列表中解決沖突的兩種方法是_____________和_____________。
四、算法設(shè)計題(20分)
1.1. 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。
2.2. 設(shè)計判斷二叉樹是否為二叉排序樹的算法。
3.3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法
答案
一、選擇題
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. 開放定址法，鏈地址法
四、算法設(shè)計題
1. 1. 設(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è)計判斷二叉樹是否為二叉排序樹的算法。
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)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法
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;}
}
}