全國2023年10月高等教育自學考試
課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.從邏輯上可以把資料結構分為（ ）
a.動態結構、靜態結構
b.順序結構、鏈式結構
c.線性結構、非線性結構
d.初等結構、構造型結構
2.關於演算法的描述，不正確的是（ ）
a.演算法最終必須由電腦程式實現
b.所謂時間複雜度是指最壞情況下，估算演算法執行時間的乙個上界
c.健壯的演算法不會因非法的輸入資料而出現莫名其妙的狀態
d.演算法的優劣與演算法描述語言無關
3.在單鏈表中，儲存每個結點需要有兩個域，乙個是資料域，另乙個是指標域，指標域指向該結點的（ ）
a.直接前趨
b.直接後繼
c.開始結點
d.終端結點
4.將兩個各有n個元素的有序表合併成乙個有序表，其最少的比較次數為（ ）
b.2n-1
c.2n
5.棧和佇列共同具有的特點是（ ）
a.都是先進後出
b.都是先進先出
c.只允許在端點進行操作運算
d.既能先進先出，也能先進後出
6.若用乙個有6個單元的陣列來實現迴圈佇列，rear和front的初值分別為0和3。則從佇列中刪除乙個元素，再新增兩個元素後，rear和front的值分別為（ ）
a.1和5
b.2和4
c.4和2
d.5和1
7.陣列a[0..5][0..5]的每個元素佔5個位元組，將其以列為主序儲存在起始位址為1000的記憶體單元中，則元素a［5］［5］的位址是（ ）
a.1175
b.1180
c.1205
d.1210
8.含有n個結點的二叉樹採用二叉鍊錶儲存時，空指標域的個數為（ ）
9.在一棵深度為h的完全二叉樹中，所含結點的個數不少於（ ）
a.2h-1-1
b.2h-1
c.2h-1
d.2h
10.乙個具有n個頂點的無向連通圖，它所包含的連通分量數為（ ）
a.0b.1
d.不確定
11.下列說法中不正確的是（ ）
a.無向圖的極大連通子圖稱為連通分量
b.連通圖的廣度優先搜尋中一般要採用佇列來暫存剛訪問過的頂點
c.連通圖的深度優先搜尋中一般要採用棧來暫存剛訪問過的頂點
d.有向圖的遍歷不可採用廣度優先搜尋演算法
12.對一棵二叉排序樹採用中根遍歷進行輸出的資料一定是（ ）
a.遞增或遞減序列
b.遞減序列
c.無序序列
d.遞增序列
13.乙個有序表為，當二分查詢值為82的結點時，查詢成功時的比較次數為（ ）
a.1b.2
c.4d.8
14.一組記錄的關鍵字為，則利用堆排序的方法建立的初始堆為（ ）
a.80，45，55，40，42，85
b.85，80，55，40，42，45
c.85，80，55，45，42，40
d.85，55，80，42，45，40
15.關於vsam檔案訪問操作的說法，正確的是（ ）
a.不能順序訪問，只能按關鍵字隨機訪問
b.不能順序訪問，不能按關鍵字隨機訪問
c.只能順序訪問，不能按關鍵字隨機訪問
d.既能順序訪問，也能按關鍵字隨機訪問
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.在任何問題中，資料元素都不是孤立的，它們之間總存在某種關係，通常稱這種關係為
17.儲存結點之間通常有四種基本儲存方式，即順序儲存方式、索引儲存方式、________和雜湊儲存方式。
18.在乙個長度為n的順序表中第i個元素（1≤i≤n）之前插入乙個元素時，需向後移動________個元素。
19.對一棵深度為10的滿二叉樹按層編號，則編號為51的結點，它的雙親結點編號為
20.用s表示入棧操作，x表示出棧操作，若元素入棧順序為1234，為了得到1342的出棧順序，相應的s和x操作串為
21.具有n個葉子結點的哈夫曼樹，其結點總數為
22.一棵具有n個結點的樹，所有非終端結點的度均為k，則該樹中葉子結點個數為
23.在無向圖g的鄰接矩陣a中，若a[i][j]等於0，則a[j][i]等於
24.兩個串是相等的，當且僅當兩個串的長度相等且________的字元都相同。
25.某二叉樹的後根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為
26.先在所有的記錄中選出鍵值最小的記錄，將它與第乙個記錄交換；然後在其餘的記錄中再選出最小的記錄與第二個記錄交換，依此類推，直至所有記錄排序完成。這種排序方法稱為
27.對含有n個結點e條邊的無向連通圖，利用prim演算法生成最小生成樹的時間複雜度為
28.對n個元素進行氣泡排序時，最少的比較次數為
三、應用題(本大題共5小題，每小題6分，共30分)
29.設有編碼為a，b，c，d的4列火車，依次進入乙個棧式結構的站台，試寫出這4列火車開出站台的所有可能的順序。
30.畫出題30圖所示的二叉樹的二叉鍊錶儲存結構。
題30圖
31.對於題31圖，試給出：
（1）鄰接矩陣；
（2）鄰接表。
題31圖
32.給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成後的二叉排序樹。
33.用插入排序演算法對資料序列（47，33，61，82，72，11，25，57）進行排序，寫出整個插入排序的每一趟過程。
四、演算法設計題(本大題共2小題，每小題7分，共14分)
34.設兩個資料元素均為整型資料的線性表a=(a1，a2，…，an)和b=(b1，b2，…，bm)。若n=m且ai=bi（i=1，2,…，n）則認為a=b；若ai=bi（i=1，2,…，j）且aj+1 試編寫乙個比較a和b的演算法，當ab時，輸出1。要求線性表的儲存結構使用鏈結儲存。 35.設二叉樹的結點型別定義如下： typedef struct nodebitree; bitree*t; 試編寫乙個計算二叉樹深度的遞迴演算法(int depth(bitree*t))。 全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和... 要求 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。1.資料結構是指 a.一種資料型別 b.資料的儲存結構 c.一組性質相同的資料元素的集合 d.相互之間存在一種或多種特定關係的資料元素的集合 2.以下演算法的時間複雜度為 void fun int n a.o n... 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下述檔案中適合於磁帶儲存的是 a.順序檔案 b.索引檔案 c.雜湊檔案 d.多關鍵字檔案 2.某二叉樹的後根遍歷序列為...全國自考試題資料結構試卷
資料結構考試題
自考資料結構導論真題