您當(dāng)前所在位置：
發(fā)布時(shí)間：2022-11-21 16:04
關(guān)注次數(shù)：課程代碼:02331
更多自考真題及答案，可以關(guān)注“重慶自考真題”欄目，也可以聯(lián)系在線老師免費(fèi)獲取全套真題及復(fù)習(xí)方法！
一、單項(xiàng)選擇題(本大題共15小題,每小題2分,共30分)
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是最符合題目要求的,請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi).錯(cuò)選、多選或未選均無(wú)分.
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū),但可以有多個(gè)直接后繼,則該結(jié)構(gòu)是（ ）
A. 棧
B. 隊(duì)列
C. 樹(shù)
D. 圖
2.下面程序段的時(shí)間復(fù)雜度為（ ）
for (i=0; i
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
3.在頭指針為head的非空單循環(huán)鏈表中,指針p指向尾結(jié)點(diǎn),下列關(guān)系成立的是（ ）
A. p->next==head
B. p->next->next==head
C. p->next==NULL
D. p==head
4.若以S和X分別表示進(jìn)棧和退棧操作,則對(duì)初始狀態(tài)為空的棧可以進(jìn)行的棧操作系列是（ ）
A. SXSSXXXX
B. SXXSXSSX
C. SXSXXSSX
D. SSSXXSXX
5.兩個(gè)字符串相等的條件是（ ）
A. 串的長(zhǎng)度相等
B. 含有相同的字符集
C. 都是非空串
D. 串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同
6.如果將矩陣An×n的每一列看成一個(gè)子表,整個(gè)矩陣看成是一個(gè)廣義表L,即L=((a11,a21,…,an1),( a12,a22,…,an2),…,（a1n,a2n,…,ann）),并且可以通過(guò)求表頭head和求表尾tail的運(yùn)算求取矩陣中的每一個(gè)元素,則求得a21的運(yùn)算是（ ）
A. head (tail (head (L)))
B. head (head(head(L)))
C. tail (head (tail (L)))
D. head (head (tail (L)))
7.已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹(shù)中只有一個(gè)葉子結(jié)點(diǎn),則該樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)為（ ）
A. 0
B. 1
C. 48
D. 49
8.在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中,所有頂點(diǎn)的出度之和為Dout ,則所有頂點(diǎn)的入度之和為（ ）
A. Dout
B. Dout-1
C. Dout+1
D. n
9.如圖所示的有向無(wú)環(huán)圖可以得到的拓?fù)湫蛄械膫€(gè)數(shù)是（ ）
A. 3
B. 4
C. 5
D. 6
10.如圖所示的帶權(quán)無(wú)向圖的最小生成樹(shù)的權(quán)為（ ）
A. 51
B. 52
C. 54
D. 56
11.對(duì)長(zhǎng)度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為（ ）
A. O（log2n）
B. O（1）
C. O（n）
D. O（n*log2n）
12.已知用某種排序方法對(duì)關(guān)鍵字序列（51,35,93,24,13,68,56,42,77）進(jìn)行排序時(shí),前兩趟排序的結(jié)果為
（35,51,24,13,68,56,42,77,93）
（35,24,13,51,56,42,68,77,93）
所采用的排序方法是（ ）
A. 插入排序
B. 冒泡排序
C. 快速排序
D. 歸并排序
13.已知散列表的存儲(chǔ)空間為T(mén)[0..18],散列函數(shù)H（key）=key,并用二次探測(cè)法處理沖突.散列表中已插入下列關(guān)鍵字:T[5]=39,T[6]=57和T[7]=7,則下一個(gè)關(guān)鍵字23插入的位置是（ ）
A. T[2]
B. T[4]
C. T[8]
D. T[10]
14.適宜進(jìn)行批量處理的文件類(lèi)型是（ ）
A. 順序文件
B. 索引順序文件
C. 散列文件
D. 多關(guān)鍵字文件
15.VSAM文件的索引結(jié)構(gòu)為（ ）
A. B+樹(shù)
B. 二叉排序樹(shù)
C. B-樹(shù)
D. 最優(yōu)二叉樹(shù)
二、填空題(本大題共10小題,每小題2分,共20分)
請(qǐng)?jiān)诿啃☆}的空格中填上正確答案.錯(cuò)填、不填均無(wú)分.
16.如果某算法對(duì)于規(guī)模為n的問(wèn)題的時(shí)間耗費(fèi)為T(mén)（n）=3n3,在一臺(tái)計(jì)算機(jī)上運(yùn)行時(shí)間為t秒,則在另一臺(tái)運(yùn)行速度是其64倍的機(jī)器上,用同樣的時(shí)間能解決的問(wèn)題規(guī)模是原問(wèn)題規(guī)模的 倍.
17.將兩個(gè)長(zhǎng)度分別為m和n的遞增有序單鏈表,歸并成一個(gè)按元素遞減有序的單鏈表,可能達(dá)到的最好的時(shí)間復(fù)雜度是 .
18.已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為m,隊(duì)頭指針front指向隊(duì)頭元素,隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置,則在隊(duì)列不滿的情況下,隊(duì)列的長(zhǎng)度是 .
19.字符串"sgabacbadfgbacst" 中存在有個(gè) 與字符串"ba"相同的子串.
20.假設(shè)以列優(yōu)先順序存儲(chǔ)二維數(shù)組A[5][8],其中元素A[0][0]的存儲(chǔ)地址為L(zhǎng)OC（a00）,且每個(gè)元素占4個(gè)存儲(chǔ)單元,則數(shù)組元素A[i][j]的存儲(chǔ)地址為 .
21.假設(shè)用
22.n個(gè)頂點(diǎn)且含有環(huán)路的無(wú)向連通圖中,至少含有 條邊.
23.在一般情況下用直接插入排序、選擇排序和冒泡排序的過(guò)程中,所需記錄交換次數(shù)最少的是 .
24.和二分查找相比,順序查找的優(yōu)點(diǎn)是除了不要求表中數(shù)據(jù)元素有序之外,對(duì) 結(jié)構(gòu)也無(wú)特殊要求.
25.順序文件中記錄存放的物理順序和 順序一致.
三、解答題(本大題共4小題,每小題5分,共20分)
26.由森林轉(zhuǎn)換得到的對(duì)應(yīng)二叉樹(shù)如圖所示,寫(xiě)出原森林中第三棵樹(shù)的前序序列和后序序列.
前序序列:
后序序列:
27.圖的鄰接表的類(lèi)型定義如下所示:
#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;
為便于刪除和插入圖的頂點(diǎn)的操作,可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu),兩種定義的存儲(chǔ)表示實(shí)例如下圖所示,請(qǐng)寫(xiě)出重新定義的類(lèi)型說(shuō)明.
