第一部分選擇題（30分）
一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。
1.算法指的是（）
A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法
C.排序算法D.解決問題的有限運(yùn)算序列
2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）
A.必須是不連續(xù)的
B.連續(xù)與否均可
C.必須是連續(xù)的
D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)
3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）
A.O（1）B.O（n）C.O（m）D.O（m+n）
4.由兩個(gè)棧共享一個(gè)向量空間的好處是：（）
A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率
B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率
C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率
D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率
5.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（）
A.front=front+1 B.front=（front+1）%（m-1）
C.front=（front-1）%m D.front=（front+1）%m
6.如下陳述中正確的是（）
A.串是一種特殊的線性表B.串的長度必須大于零
C.串中元素只能是字母D.空串就是空白串
7.若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（）
A.O（）B.O（n）C.O（n2）D.O（n3）
8.一個(gè)非空廣義表的表頭（）
A.不可能是子表B.只能是子表
C.只能是原子D.可以是子表或原子
9.假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表
0 2 3 3 5
對應(yīng)的稀疏矩陣是（）
10.在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ ）
A.4 B.5 C.6 D.7
11.在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ ）
A.e B.2e C.n2－e D.n2－2e
12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（ ）
A.O（n） B.O（e） C.O（n+e） D.O（n*e）
13.用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
則所采用的排序方法是（）
A.選擇排序B.希爾排序C.歸并排序D.快速排序
14.適于對動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）
A.有序表B.分塊有序表C.三叉排序樹D.線性鏈表
15.不定長文件是指（）
A.文件的長度不固定B.記錄的長度不固定
C.字段的長度不固定D.關(guān)鍵字項(xiàng)的長度不固定
第二部分非選擇題（共70分）
二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。
16.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨(dú)立于計(jì)算機(jī)的。
17.在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=.
18.棧頂?shù)奈恢檬请S著操作而變化的。
19.在串S=“structure”中，以t為首字符的子串有個(gè)。
20.假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B
一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。
1.算法指的是（）
A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法
C.排序算法D.解決問題的有限運(yùn)算序列
2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）
A.必須是不連續(xù)的
B.連續(xù)與否均可
C.必須是連續(xù)的
D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)
3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）
A.O（1）B.O（n）C.O（m）D.O（m+n）
4.由兩個(gè)棧共享一個(gè)向量空間的好處是：（）
A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率
B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率
C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率
D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率
5.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（）
A.front=front+1 B.front=（front+1）%（m-1）
C.front=（front-1）%m D.front=（front+1）%m
6.如下陳述中正確的是（）
A.串是一種特殊的線性表B.串的長度必須大于零
C.串中元素只能是字母D.空串就是空白串
7.若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（）
A.O（）B.O（n）C.O（n2）D.O（n3）
8.一個(gè)非空廣義表的表頭（）
A.不可能是子表B.只能是子表
C.只能是原子D.可以是子表或原子
9.假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表
0 2 3 3 5
對應(yīng)的稀疏矩陣是（）
10.在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ ）
A.4 B.5 C.6 D.7
11.在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ ）
A.e B.2e C.n2－e D.n2－2e
12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（ ）
A.O（n） B.O（e） C.O（n+e） D.O（n*e）
13.用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
則所采用的排序方法是（）
A.選擇排序B.希爾排序C.歸并排序D.快速排序
14.適于對動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）
A.有序表B.分塊有序表C.三叉排序樹D.線性鏈表
15.不定長文件是指（）
A.文件的長度不固定B.記錄的長度不固定
C.字段的長度不固定D.關(guān)鍵字項(xiàng)的長度不固定
第二部分非選擇題（共70分）
二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。
16.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨(dú)立于計(jì)算機(jī)的。
17.在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=.
18.棧頂?shù)奈恢檬请S著操作而變化的。
19.在串S=“structure”中，以t為首字符的子串有個(gè)。
20.假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B