一、選擇題(30分)
1. 1. 字符串的長(zhǎng)度是指( )。
(A) 串中不同字符的個(gè)數(shù) (B) 串中不同字母的個(gè)數(shù)
(C) 串中所含字符的個(gè)數(shù) (D) 串中不同數(shù)字的個(gè)數(shù)
2. 2. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為( )
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
3. 3. 兩個(gè)字符串相等的充要條件是( )。
(A) 兩個(gè)字符串的長(zhǎng)度相等 (B) 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等
(C) 同時(shí)具備(A)和(B)兩個(gè)條件 (D) 以上答案都不對(duì)
4. 4. 設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k % P，則P通常情況下選擇( )。
(A) 99 (B) 97 (C) 91 (D) 93
5. 5. 在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)
6. 6. 設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)? )。
(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]
(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]
7. 7. 設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為( )。
(A) 8 (B) 7 (C) 6 (D) 5
8. 8. 設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有( )個(gè)度數(shù)為0的結(jié)點(diǎn)。
(A) 5 (B) 6 (C) 7 (D) 8
9. 9. 設(shè)無(wú)向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為( )。
(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc
10. 10. 隊(duì)列是一種( )的線性表。
(A) 先進(jìn)先出 (B) 先進(jìn)后出 (C) 只能插入 (D) 只能刪除
二、判斷題(20分)
1. 1. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。( )
2. 2. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。( )
3. 3. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。( )
4. 4. 二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。( )
5. 5. 向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。( )
6. 6. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。( )
7. 7. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。( )
8. 8. 不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。( )
9. 9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。( )
10. 10. 稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。( )
三、填空題(30分)
1. 1. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_(kāi)____________________________。
2. 2. 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。
typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;
void bstinsert(bitree *&t,int k)
{
if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}
else if (t->data>k) bstinsert(t->lchild,k);else__________________________;
}
3. 3. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next; _________________;。
4. 4. 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)。
5. 5. 設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_(kāi)_________。
6. 6. 完全二叉樹(shù)中第5層上最少有__________個(gè)結(jié)點(diǎn)，最多有_________個(gè)結(jié)點(diǎn)。
7. 7. 設(shè)有向圖中不存在有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。
8. 8. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_(kāi)____________________________。
9. 9. 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有___________條邊。
10. 10. 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。
四、算法設(shè)計(jì)題(20分)
1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。
2. 2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。
答案
一、選擇題
1.C 2.C 3.C 4.B 5.B
6.C 7.B 8.C 9.A 10.A
二、判斷題
1.對(duì) 2.錯(cuò) 3.對(duì) 4.錯(cuò) 5.錯(cuò)
6.對(duì) 7.對(duì) 8.對(duì) 9.對(duì) 10.對(duì)
三、填空題
1. 1. (49，13，27，50，76，38，65，97)
2. 2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)
3. 3. p->next=s
4. 4. head->rlink，p->llink
5. 5. CABD
6. 6. 1，16
7. 7. 0
8. 8. (13，27，38，50，76，49，65，97)
9. 9. n-1
10. 10. 50
四、算法設(shè)計(jì)題
1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。
void countnode(bitree *bt,int &count)
{
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}
}
2. 2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。
typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;
typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;
typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])
{
int i,j; glinklistnode *p;
for(i=0;i<=n-1;i++) g2[i].firstarc=0;
for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++)
if (g1.edge[i][j]==1)
{
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;
p->nextarc=g[i].firstarc; g[i].firstarc=p;
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;
p->nextarc=g[j].firstarc; g[j].firstarc=p;
}
}
1. 1. 字符串的長(zhǎng)度是指( )。
(A) 串中不同字符的個(gè)數(shù) (B) 串中不同字母的個(gè)數(shù)
(C) 串中所含字符的個(gè)數(shù) (D) 串中不同數(shù)字的個(gè)數(shù)
2. 2. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為( )
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
3. 3. 兩個(gè)字符串相等的充要條件是( )。
(A) 兩個(gè)字符串的長(zhǎng)度相等 (B) 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等
(C) 同時(shí)具備(A)和(B)兩個(gè)條件 (D) 以上答案都不對(duì)
4. 4. 設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k % P，則P通常情況下選擇( )。
(A) 99 (B) 97 (C) 91 (D) 93
5. 5. 在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)
6. 6. 設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)? )。
(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]
(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]
7. 7. 設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為( )。
(A) 8 (B) 7 (C) 6 (D) 5
8. 8. 設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有( )個(gè)度數(shù)為0的結(jié)點(diǎn)。
(A) 5 (B) 6 (C) 7 (D) 8
9. 9. 設(shè)無(wú)向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為( )。
(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc
10. 10. 隊(duì)列是一種( )的線性表。
(A) 先進(jìn)先出 (B) 先進(jìn)后出 (C) 只能插入 (D) 只能刪除
二、判斷題(20分)
1. 1. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。( )
2. 2. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。( )
3. 3. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。( )
4. 4. 二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。( )
5. 5. 向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。( )
6. 6. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。( )
7. 7. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。( )
8. 8. 不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。( )
9. 9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。( )
10. 10. 稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。( )
三、填空題(30分)
1. 1. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_(kāi)____________________________。
2. 2. 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。
typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;
void bstinsert(bitree *&t,int k)
{
if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}
else if (t->data>k) bstinsert(t->lchild,k);else__________________________;
}
3. 3. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next; _________________;。
4. 4. 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)。
5. 5. 設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_(kāi)_________。
6. 6. 完全二叉樹(shù)中第5層上最少有__________個(gè)結(jié)點(diǎn)，最多有_________個(gè)結(jié)點(diǎn)。
7. 7. 設(shè)有向圖中不存在有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。
8. 8. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_(kāi)____________________________。
9. 9. 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有___________條邊。
10. 10. 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。
四、算法設(shè)計(jì)題(20分)
1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。
2. 2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。
答案
一、選擇題
1.C 2.C 3.C 4.B 5.B
6.C 7.B 8.C 9.A 10.A
二、判斷題
1.對(duì) 2.錯(cuò) 3.對(duì) 4.錯(cuò) 5.錯(cuò)
6.對(duì) 7.對(duì) 8.對(duì) 9.對(duì) 10.對(duì)
三、填空題
1. 1. (49，13，27，50，76，38，65，97)
2. 2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)
3. 3. p->next=s
4. 4. head->rlink，p->llink
5. 5. CABD
6. 6. 1，16
7. 7. 0
8. 8. (13，27，38，50，76，49，65，97)
9. 9. n-1
10. 10. 50
四、算法設(shè)計(jì)題
1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。
void countnode(bitree *bt,int &count)
{
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}
}
2. 2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。
typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;
typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;
typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])
{
int i,j; glinklistnode *p;
for(i=0;i<=n-1;i++) g2[i].firstarc=0;
for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++)
if (g1.edge[i][j]==1)
{
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;
p->nextarc=g[i].firstarc; g[i].firstarc=p;
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;
p->nextarc=g[j].firstarc; g[j].firstarc=p;
}
}