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