數據結構試題
課程代碼：02331
壹、單項選擇題(本大題***15小題，每小題2分，***30分)
在每小題列出的四個備選項中只有壹個是最符合題目要求的，請將其代碼填寫在題後的括號內。錯選、多選或未選均無分。
1.如果在數據結構中每個數據元素只可能有壹個直接前驅，但可以有多個直接後繼，則該結構是（ ）
A. 棧 B. 隊列
C. 樹 D. 圖
2.下面程序段的時間復雜度為（ ）
for (i=0; i<m; i++)
for (j=0; j<n; j++)
A[i][j]=i*j;
A. O (m2) B. O (n2)
C. O (m*n) D. O (m+n)
3.在頭指針為head的非空單循環鏈表中，指針p指向尾結點，下列關系成立的是（ ）
A. p->next==head B. p->next->next==head
C. p->next==NULL D. p==head
4.若以S和X分別表示進棧和退棧操作，則對初始狀態為空的棧可以進行的棧操作系列是（ ）
A. SXSSXXXX B. SXXSXSSX
C. SXSXXSSX D. SSSXXSXX
5.兩個字符串相等的條件是（ ）
A. 串的長度相等 B. 含有相同的字符集
C. 都是非空串 D. 串的長度相等且對應的字符相同
6.如果將矩陣An×n的每壹列看成壹個子表，整個矩陣看成是壹個廣義表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),並且可以通過求表頭head和求表尾tail的運算求取矩陣中的每壹個元素，則求得a21的運算是（ ）
A. head (tail (head (L))) B. head (head(head(L)))
C. tail (head (tail (L))) D. head (head (tail (L)))
7.已知壹棵含50個結點的二叉樹中只有壹個葉子結點，則該樹中度為1的結點個數為（ ）
A. 0 B. 1
C. 48 D. 49
8.在壹個具有n個頂點的有向圖中，所有頂點的出度之和為Dout ，則所有頂點的入度之和為（ ）
A. Dout B. Dout-1
C. Dout+1 D. n
9.如圖所示的有向無環圖可以得到的拓撲序列的個數是（ ）
A. 3 B. 4
C. 5 D. 6
10.如圖所示的帶權無向圖的最小生成樹的權為（ ）
A. 51 B. 52
C. 54 D. 56
11.對長度為n的關鍵字序列進行堆排序的空間復雜度為（ ）
A. O（log2n） B. O（1）
C. O（n） D. O（n*log2n）
12.已知用某種排序方法對關鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結果為
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）
所采用的排序方法是（ ）
A. 插入排序 B. 冒泡排序
C. 快速排序 D. 歸並排序
13.已知散列表的存儲空間為T[0..18]，散列函數H（key）=key%17,並用二次探測法處理沖突。散列表中已插入下列關鍵字：T[5]=39，T[6]=57和T[7]=7，則下壹個關鍵字23插入的位置是（ ）
A. T[2] B. T[4]
C. T[8] D. T[10]
14.適宜進行批量處理的文件類型是（ ）
A. 順序文件 B. 索引順序文件
C. 散列文件 D. 多關鍵字文件
15.VSAM文件的索引結構為（ ）
A. B+樹 B. 二叉排序樹
C. B-樹 D. 最優二叉樹
二、填空題(本大題***10小題，每小題2分，***20分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.如果某算法對於規模為n的問題的時間耗費為T（n）=3n3，在壹臺計算機上運行時間為t秒，則在另壹臺運行速度是其64倍的機器上，用同樣的時間能解決的問題規模是原問題規模的 倍。
17.將兩個長度分別為m和n的遞增有序單鏈表，歸並成壹個按元素遞減有序的單鏈表，可能達到的最好的時間復雜度是 。
18.已知循環隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下壹個位置，則在隊列不滿的情況下，隊列的長度是 。
19.字符串“sgabacbadfgbacst” 中存在有 個與字符串“ba”相同的子串。
20.假設以列優先順序存儲二維數組A[5][8]，其中元素A[0][0]的存儲地址為LOC（a00）,且每個元素占4個存儲單元，則數組元素A[i][j]的存儲地址為 。
21.假設用<x,y>表示樹的邊（其中x是y的雙親），已知壹棵樹的邊集為
{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>}，該樹的度是 。
22.n個頂點且含有環路的無向連通圖中，至少含有 條邊。
23.在壹般情況下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數最少的是 。
24.和二分查找相比，順序查找的優點是除了不要求表中數據元素有序之外，對 結構也無特殊要求。
25.順序文件中記錄存放的物理順序和 順序壹致。
三、解答題(本大題***4小題，每小題5分，***20分)
26.由森林轉換得到的對應二叉樹如圖所示，寫出原森林中第三棵樹的前序序列和後序序列。
前序序列：
後序序列：
27.圖的鄰接表的類型定義如下所示：
#define MaxVertexNum 50
typedef struct node {
int adjvex;
struct node *next;
}EdgeNode;
typedef struct {
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct {
AdjList adjlist;
int n, e;
}ALGraph;
為便於刪除和插入圖的頂點的操作，可將鄰接表的表頭向量定義為鏈式結構，兩種定義的存儲表示實例如下圖所示，請寫出重新定義的類型說明。
題27圖
28.某類物品的編號由壹個大寫英文字母及2位數字（0..9）組成，形如E32。運用基數排序
對下列物品編號序列進行按字典序的排序，寫出每壹趟（分配和收集）後的結果。
E13，A37，F43，B32，B47，E12，F37，B12
第壹趟：
第二趟：
第三趟：
29.（1）畫出對表長為13的有序順序表進行二分查找的判定樹；
（2）已知關鍵字序列為（12，14，16，21，24，28，35，43，52，67，71，84，99），寫出在該序列中二分查找37時所需進行的比較次數。
（1）
（2）
四、算法閱讀題（本大題***4小題，每小題5分，***20分）
30.已知線性表的存儲結構為順序表，閱讀下列算法，並回答問題：
（1）設線性表L=（21，-7，-8，19，0，-11，34，30，-10），寫出執行f30(&L)後的L狀態；
（2）簡述算法f30的功能。
void f30 (SeqList *L) {
int i,j;
for (i=j=0;i<L->length; i++)
if(L->data[i]>=0){
if(i!=j)L->data[j]=L->data[i];
j++；
}
L->length=j;
}
(1)
(2)
31.閱讀下列算法，並回答問題：
（1）Q、Q1和Q2都是隊列結構，設隊列Q=（1，0，-5，2，-4，-6，9），其中1為隊頭元素，寫出執行f31 (&Q,&Q1,&Q2)之後隊列Q、Q1和Q2的狀態；
（2）簡述算法f31的功能。
（註：lnitQueue、EnQueue、DeQueue和QueueEmpty分別是隊列初始化、入列、出隊和判隊空的操作）
void f31 (Queue*Q, Queue*Q1, Queue*Q2) {
int e;
lnitQueue (Q1);
lnitQueue (Q2);
while (!QueueEmpty (Q)) {
e=DeQueue (Q);
if (e>=0) EnQueue (Q1,e);
else EnQueue (Q2,e)
}
}
（1）
（2）
32.閱讀下列算法，並回答問題：
（1）假設串由合法的英文字母和空格組成，並以’\0’作結束符。設串s=”?|?am?astudent”(?表示空格符)，寫出f32（s）的返回值；
（2）簡述算法f32的功能。
int f32 (char*s){
int i, n, inword;
n=inword=0;
for (i=0;s[i]!=’\0’;i++)
if (s[i]!=’?’&& inword==0){
inword=1;
n++;
}
else if (s[i]==’?’&& inword==1)
inword=0;
return n;
}
（1）
（2）
33.閱讀下列對正整數關鍵字序列L操作的算法，並回答問題：
（1）設L=(28,19,27,49,56,12,10,25,20,50),寫出f33 (L,4)的返回值；
（2）簡述函數f33的功能。
int Partition (SeqList*L, int low, int high);
‖對L[low..high]做劃分，返回基準記錄的位置，並使左部的關鍵字
‖都小於或等於基準記錄的關鍵字，右部的關鍵字都大於基準記錄的關鍵字
int f33 (SeqList L, int k){
int low, high, pivotpos;
low=1;
high=L.length;
if (k<low || k>high)
return-1;
do {
pivotpos=Partition (&L, low, high);‖調用快速排序的劃分算法
if (pivotpos<k)
low=pivotpos+1;
else if (pivotpos>k)
high=pivotpos-1;
}while (pivotpos!=k);
return L.data [pivotpos];
}
（1）
（2）
五、算法設計題（本題10分）
34.二叉排序樹的類型定義如下：
typedef struct BSTNode {‖ 二叉排序樹的結點結構
int data; ‖數據域
struct BSTNode *lchild, *rchild; ‖左、右孩子指針
}BSTNode,*BSTree;
設計遞歸算法，統計壹棵二叉排序樹T中值小於a的結點個數。