您當前所在位置：
發布時間：2022-11-21 16:04
關注次數：課程代碼:02331
更多自考真題及答案，可以關注“重慶自考真題”欄目，也可以聯系在線老師免費獲取全套真題及復習方法！
一、單項選擇題(本大題共15小題,每小題2分,共30分)
在每小題列出的四個備選項中只有一個是最符合題目要求的,請將其代碼填寫在題后的括號內.錯選、多選或未選均無分.
1.如果在數據結構中每個數據元素只可能有一個直接前驅,但可以有多個直接后繼,則該結構是（ ）
A. 棧
B. 隊列
C. 樹
D. 圖
2.下面程序段的時間復雜度為（ ）
for (i=0; i
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分別表示進棧和退棧操作,則對初始狀態為空的?？梢赃M行的棧操作系列是（ ?。?br />
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.如圖所示的有向無環圖可以得到的拓撲序列的個數是（ ?。?br />
A. 3
B. 4
C. 5
D. 6
10.如圖所示的帶權無向圖的最小生成樹的權為（ ?。?br />
A. 51
B. 52
C. 54
D. 56
11.對長度為n的關鍵字序列進行堆排序的空間復雜度為（ ?。?br />
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,并用二次探測法處理沖突.散列表中已插入下列關鍵字:T[5]=39,T[6]=57和T[7]=7,則下一個關鍵字23插入的位置是（ ?。?br />
A. T[2]
B. T[4]
C. T[8]
D. T[10]
14.適宜進行批量處理的文件類型是（ ?。?br />
A. 順序文件
B. 索引順序文件
C. 散列文件
D. 多關鍵字文件
15.VSAM文件的索引結構為（ ?。?br />
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.假設用
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;
為便于刪除和插入圖的頂點的操作,可將鄰接表的表頭向量定義為鏈式結構,兩種定義的存儲表示實例如下圖所示,請寫出重新定義的類型說明.
