一、單項(xiàng)選擇題（在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。每小題2分，共30分）
1.下列數(shù)據(jù)結(jié)構(gòu)中，（ ）不都是線性結(jié)構(gòu)。
A.棧和隊(duì)列 B.隊(duì)列和數(shù)組
C.數(shù)組和串 D.文件和隊(duì)列
2.為了最快地對(duì)線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行某數(shù)據(jù)元素的讀取操作，則其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用（ ）方式。
A.順序存儲(chǔ) B.鏈?zhǔn)酱鎯?chǔ)
C.索引存儲(chǔ) D.散列存儲(chǔ)
3.設(shè)雙鏈表中結(jié)點(diǎn)的前趨指針和后繼指針的域名分別為t1和r1，則刪除雙鏈表中指針s所指結(jié)點(diǎn)的操作為（ ）
A.s->t1->r1=s->t1；s->r1->t1=s->r1；
B.s->t1->r1=s->r1；s->r1->t1=s->t1；
C.s->r1=s->t1->r1；s->t1=s->r->t1；
D.s->t1=s->t1->r1；s->r1=s->r->t1；
4.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針域，現(xiàn)要把一個(gè)指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指地點(diǎn)（中間結(jié)點(diǎn)）的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是（ ）
A.q->right=s； s->left=q； q->right->left=s； s->right=q->right；
B.s->left=q； q->right=s； q->right->left=s； s->right=q->right；
C.s->left=q； s->right=q->right； q->right->left=s； q->right=s；
D.以上都不對(duì)
5.由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹為（ ）
6.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（ ）
A.6 B.7 C.8 D.9
7.已知一個(gè)稀疏矩陣的三元組表如下：（1，2，3），（1，6，1），（3，1，5），（3，2，-1），（4，5，4），（5，1，-3），則其轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組為（ ）
A.（2，1，3） B.（3，1，5） C.（3，2，-1） D.（2，3，-1）
8.無向圖的鄰接矩陣是一個(gè)（ ）
A.對(duì)稱矩陣 B.零矩陣 C.上三角矩陣 D.對(duì)角矩陣
9.下列說法中正確的是（ ）
A.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為n（n-1）
B.連通圖的生成樹是該圖的一個(gè)極大連通子圖
C.圖的廣度優(yōu)先搜索是一個(gè)遞歸過程
D.對(duì)于非連通圖的遍歷過程中每調(diào)用一次深度優(yōu)先搜索算法都得到該圖的一個(gè)連通分量
10.順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的要求是（ ）
A.順序查找與二分查找均只適用于順序表
B.順序查找與二分查找既適用于順序表，也適用于鏈表
C.順序查找只適用于順序表
D.二分查找只適用于順序表
11.在開散列表上，每個(gè)地址單元所鏈接的同義詞表（ ）
A.其鍵值相同 B.其元素值相同
C.其散列地址相同 D.其含義相同
12.散列文件中的記錄通常成組存放，若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，這個(gè)存儲(chǔ)單位稱為（ ）
A.磁道 B.塊 C.柱面 D.桶
13.索引非順序文件中的索引表是（ ）
A.非稠密索引 B.稠密索引
C.主索引 D.多級(jí)索引
14.對(duì)n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為（ ）
A.O（log2n） B.O（nlog2n）
C.O（n） D.O（n2）
15.一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）
A.38，40，46，56，79，84 B.40，38，46，79，56，84
C.40，38，46，56，79，84 D.40，38，46，84，56，79
二、填空題（每小題2分，共26分）
請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。
16.下列程序段的時(shí)間復(fù)雜性的量級(jí)為_________.
for （i=1；i for（j=i；j date
next
t=t+1
17.設(shè)某非空單鏈表，其結(jié)點(diǎn)形式為 ， 若要?jiǎng)h除指針q所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，則需執(zhí)行下列語句序列：
p=q->next；________；free（p）；
18.隊(duì)列可以看成是一種運(yùn)算受限制的線性表，也稱為______線性表。
19.鏈棧的類型定義如下：
typedef struct node
{ DateType date；
struct node *next；
}LStackTp；
若棧非空，則退棧操作可以用下列算法片段實(shí)現(xiàn)：
p=ls；/* ls為棧頂指針*/
*x=p->date； /*棧頂元素通過參數(shù)返回*/
___________；
free（p）； /*釋放原棧頂結(jié)點(diǎn)空間*/
20.在非空樹上，_____沒有直接前趨。
21.設(shè)有33個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有____個(gè)結(jié)點(diǎn)。
22.無向圖中的連通分量定義為無向圖的_________.
23.在開散列表上查找鍵值等于K的結(jié)點(diǎn)，首先必須計(jì)算該鍵值的______，然后再通過指針查找該結(jié)點(diǎn)。
24.對(duì)靜態(tài)表順序查找算法采用設(shè)置崗哨方式與普通的設(shè)置循環(huán)控制變量相比，進(jìn)行一次查找所花費(fèi)的平均時(shí)間大約減少_____.
25.若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出的所有結(jié)點(diǎn)鍵值序列按遞增次序排列，應(yīng)對(duì)該二叉樹采用_________遍歷法。
26.文件的基本存取單位是_________.
27.設(shè)需將一組數(shù)據(jù)按升序排序。在無序區(qū)中依次比較相鄰兩個(gè)元素ai和ai+1的值，若ai的值大于ai+1的值，則交換ai和ai+1.如此反復(fù)，直到某一趟中沒有記錄需要交換為止，該排序方法被稱為_________.
28.在插入排序、快速排列、堆排序、歸并排序中，排序方法不穩(wěn)定的有_________.
三、應(yīng)用題（本大題共5小題，共30分）
29.現(xiàn)有一組單詞（WEK，SUN，MON，TUE，WED，THU，F(xiàn)RI，SAT），其相應(yīng)的散列函數(shù)值為（3，2，6，3，2，5，6，0），散列表長(zhǎng)度為10（散列地址空間為0……9），要求：（6分）
（1）構(gòu)造該閉散列表，并用線性探測(cè)法解決沖突；
（2）若對(duì)每個(gè)元素查找一次，求總的比較次數(shù)。
30.已知無向圖G的鄰接矩陣如下。假設(shè)對(duì)其訪問時(shí)每行元素必須從右到左，請(qǐng)畫出其所有的連通分量，并且寫出按深度優(yōu)先搜索時(shí)各連通分量的訪問序列。（8分）
31.設(shè)要將序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，請(qǐng)畫出采用堆排序方法時(shí)建立的初始堆及第一次輸出堆頂元素后篩選調(diào)整以后的堆。（8分）
32.設(shè)二叉樹后根遍歷的結(jié)果為BCA，畫出所有可得到這一結(jié)果的二叉樹。（5分）
33.設(shè)有一循環(huán)隊(duì)列sq.data［maxsize］，一般情況下隊(duì)列中至多可存放多少個(gè)元素？為什么？（3分）
四、設(shè)計(jì)題（本大題共2小題，共14分）
34.設(shè)有兩個(gè)按升序排列的單鏈表X和Y，其頭指針分別為p，q結(jié)點(diǎn)結(jié)構(gòu)說明如下：
typedef struct nodel
{
int data；
struct nodel *next
}node；
試設(shè)計(jì)一個(gè)算法void concat（node *p，*q）將它們合并成一個(gè)以p為頭指針的單鏈表Z，使其仍然有序。（6分）
35.設(shè)有序表r長(zhǎng)度為n，欲在表中查找鍵值為Kn的某元素。若查找成功，則返回該元素在有序表r中的位置，若不成功，則返回0值。用二分查找法，編寫一算法完成上述操作，并給出該算法的平均查找長(zhǎng)度。該有序表存儲(chǔ)結(jié)構(gòu)定義如下：（8分）
typedef struct
{ keytype key；
Elemtype data；
}rec；
typedef struct
{ rec item［maxsize+1］；
int n；
}sqtable；
1.下列數(shù)據(jù)結(jié)構(gòu)中，（ ）不都是線性結(jié)構(gòu)。
A.棧和隊(duì)列 B.隊(duì)列和數(shù)組
C.數(shù)組和串 D.文件和隊(duì)列
2.為了最快地對(duì)線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行某數(shù)據(jù)元素的讀取操作，則其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用（ ）方式。
A.順序存儲(chǔ) B.鏈?zhǔn)酱鎯?chǔ)
C.索引存儲(chǔ) D.散列存儲(chǔ)
3.設(shè)雙鏈表中結(jié)點(diǎn)的前趨指針和后繼指針的域名分別為t1和r1，則刪除雙鏈表中指針s所指結(jié)點(diǎn)的操作為（ ）
A.s->t1->r1=s->t1；s->r1->t1=s->r1；
B.s->t1->r1=s->r1；s->r1->t1=s->t1；
C.s->r1=s->t1->r1；s->t1=s->r->t1；
D.s->t1=s->t1->r1；s->r1=s->r->t1；
4.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針域，現(xiàn)要把一個(gè)指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指地點(diǎn)（中間結(jié)點(diǎn)）的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是（ ）
A.q->right=s； s->left=q； q->right->left=s； s->right=q->right；
B.s->left=q； q->right=s； q->right->left=s； s->right=q->right；
C.s->left=q； s->right=q->right； q->right->left=s； q->right=s；
D.以上都不對(duì)
5.由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹為（ ）
6.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（ ）
A.6 B.7 C.8 D.9
7.已知一個(gè)稀疏矩陣的三元組表如下：（1，2，3），（1，6，1），（3，1，5），（3，2，-1），（4，5，4），（5，1，-3），則其轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組為（ ）
A.（2，1，3） B.（3，1，5） C.（3，2，-1） D.（2，3，-1）
8.無向圖的鄰接矩陣是一個(gè)（ ）
A.對(duì)稱矩陣 B.零矩陣 C.上三角矩陣 D.對(duì)角矩陣
9.下列說法中正確的是（ ）
A.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為n（n-1）
B.連通圖的生成樹是該圖的一個(gè)極大連通子圖
C.圖的廣度優(yōu)先搜索是一個(gè)遞歸過程
D.對(duì)于非連通圖的遍歷過程中每調(diào)用一次深度優(yōu)先搜索算法都得到該圖的一個(gè)連通分量
10.順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的要求是（ ）
A.順序查找與二分查找均只適用于順序表
B.順序查找與二分查找既適用于順序表，也適用于鏈表
C.順序查找只適用于順序表
D.二分查找只適用于順序表
11.在開散列表上，每個(gè)地址單元所鏈接的同義詞表（ ）
A.其鍵值相同 B.其元素值相同
C.其散列地址相同 D.其含義相同
12.散列文件中的記錄通常成組存放，若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，這個(gè)存儲(chǔ)單位稱為（ ）
A.磁道 B.塊 C.柱面 D.桶
13.索引非順序文件中的索引表是（ ）
A.非稠密索引 B.稠密索引
C.主索引 D.多級(jí)索引
14.對(duì)n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為（ ）
A.O（log2n） B.O（nlog2n）
C.O（n） D.O（n2）
15.一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）
A.38，40，46，56，79，84 B.40，38，46，79，56，84
C.40，38，46，56，79，84 D.40，38，46，84，56，79
二、填空題（每小題2分，共26分）
請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。
16.下列程序段的時(shí)間復(fù)雜性的量級(jí)為_________.
for （i=1；i
next
t=t+1
17.設(shè)某非空單鏈表，其結(jié)點(diǎn)形式為 ， 若要?jiǎng)h除指針q所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，則需執(zhí)行下列語句序列：
p=q->next；________；free（p）；
18.隊(duì)列可以看成是一種運(yùn)算受限制的線性表，也稱為______線性表。
19.鏈棧的類型定義如下：
typedef struct node
{ DateType date；
struct node *next；
}LStackTp；
若棧非空，則退棧操作可以用下列算法片段實(shí)現(xiàn)：
p=ls；/* ls為棧頂指針*/
*x=p->date； /*棧頂元素通過參數(shù)返回*/
___________；
free（p）； /*釋放原棧頂結(jié)點(diǎn)空間*/
20.在非空樹上，_____沒有直接前趨。
21.設(shè)有33個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有____個(gè)結(jié)點(diǎn)。
22.無向圖中的連通分量定義為無向圖的_________.
23.在開散列表上查找鍵值等于K的結(jié)點(diǎn)，首先必須計(jì)算該鍵值的______，然后再通過指針查找該結(jié)點(diǎn)。
24.對(duì)靜態(tài)表順序查找算法采用設(shè)置崗哨方式與普通的設(shè)置循環(huán)控制變量相比，進(jìn)行一次查找所花費(fèi)的平均時(shí)間大約減少_____.
25.若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出的所有結(jié)點(diǎn)鍵值序列按遞增次序排列，應(yīng)對(duì)該二叉樹采用_________遍歷法。
26.文件的基本存取單位是_________.
27.設(shè)需將一組數(shù)據(jù)按升序排序。在無序區(qū)中依次比較相鄰兩個(gè)元素ai和ai+1的值，若ai的值大于ai+1的值，則交換ai和ai+1.如此反復(fù)，直到某一趟中沒有記錄需要交換為止，該排序方法被稱為_________.
28.在插入排序、快速排列、堆排序、歸并排序中，排序方法不穩(wěn)定的有_________.
三、應(yīng)用題（本大題共5小題，共30分）
29.現(xiàn)有一組單詞（WEK，SUN，MON，TUE，WED，THU，F(xiàn)RI，SAT），其相應(yīng)的散列函數(shù)值為（3，2，6，3，2，5，6，0），散列表長(zhǎng)度為10（散列地址空間為0……9），要求：（6分）
（1）構(gòu)造該閉散列表，并用線性探測(cè)法解決沖突；
（2）若對(duì)每個(gè)元素查找一次，求總的比較次數(shù)。
30.已知無向圖G的鄰接矩陣如下。假設(shè)對(duì)其訪問時(shí)每行元素必須從右到左，請(qǐng)畫出其所有的連通分量，并且寫出按深度優(yōu)先搜索時(shí)各連通分量的訪問序列。（8分）
31.設(shè)要將序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，請(qǐng)畫出采用堆排序方法時(shí)建立的初始堆及第一次輸出堆頂元素后篩選調(diào)整以后的堆。（8分）
32.設(shè)二叉樹后根遍歷的結(jié)果為BCA，畫出所有可得到這一結(jié)果的二叉樹。（5分）
33.設(shè)有一循環(huán)隊(duì)列sq.data［maxsize］，一般情況下隊(duì)列中至多可存放多少個(gè)元素？為什么？（3分）
四、設(shè)計(jì)題（本大題共2小題，共14分）
34.設(shè)有兩個(gè)按升序排列的單鏈表X和Y，其頭指針分別為p，q結(jié)點(diǎn)結(jié)構(gòu)說明如下：
typedef struct nodel
{
int data；
struct nodel *next
}node；
試設(shè)計(jì)一個(gè)算法void concat（node *p，*q）將它們合并成一個(gè)以p為頭指針的單鏈表Z，使其仍然有序。（6分）
35.設(shè)有序表r長(zhǎng)度為n，欲在表中查找鍵值為Kn的某元素。若查找成功，則返回該元素在有序表r中的位置，若不成功，則返回0值。用二分查找法，編寫一算法完成上述操作，并給出該算法的平均查找長(zhǎng)度。該有序表存儲(chǔ)結(jié)構(gòu)定義如下：（8分）
typedef struct
{ keytype key；
Elemtype data；
}rec；
typedef struct
{ rec item［maxsize+1］；
int n；
}sqtable；