全國2023年10月高等教育自學考試資料結構導論試題
課程**：02142
一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在
題後的括號內。錯選、多選或未選均無分。
1．下列說法正確的是（）
a．資料是資料元素的基本單位
b．資料元素是資料項中不可分割的最小標識單位
c．資料可由若干個資料元素構成
d．資料項可由若干個資料元素構成
2．資料結構的基本任務是（）
a．邏輯結構和儲存結構的設計
b．資料結構的運算實現
c．資料結構的評價與選擇
d．資料結構的設計與實現
3．在乙個具有n個結點的有序單鏈表中插入乙個新結點，並使插入後仍然有序，則該操作的時間複雜性量級為（）
a．o（1）
b．o（n）
c．o（nlog2n）
d．o(n2)
4．順序儲存的線性表（a1,a2,…,an），在任一結點前插入乙個新結點時所需移動結點的平均次數為（）
a．nb．n/2
c．n+1
d．(n+1)/2
6．一棵有16結點的完全二叉樹，對它按層編號，則對編號為7的結點x，它
的雙親結點及右孩子結點的編號分別為（）
a．2，14
b．2，15
c．3，14
d．3，15
7．設有一5階上三角矩陣a［1..5，1..5］，現將其上三角中的元素按列優先
順序存放在一堆陣列b［1..15］中。已知b［1］的位址為100，每個元素占用
2個儲存單元，則a［3，4］的位址為（）
a．116
b．118
c．120
d．122
8．乙個帶權的無向連通圖的最小生成樹（）
a．有一棵或多棵
b．只有一棵
c．一定有多棵
d．可能不存在
9．下列有關圖遍歷的說法中不正確的是（）
a．連通圖的深度優先搜尋是乙個遞迴過程
b．圖的廣度優先搜尋中鄰接點的尋找具有「先進先出」的特徵
c．非連通圖不能用深度優先搜尋法
d．圖的遍歷要求每一頂點僅被訪問一次
10．在最壞的情況下，查詢成功時二叉排序樹的平均查詢長度（）
a．小於順序表的平均查詢長度
b．大於順序表的平均查詢長度
c．與順序表的平均查詢長度相同
d．無法與順序表的平均查詢長度比較
11．閉雜湊表中由於雜湊到同乙個位址而引起的「堆積」現象，是由（）a．同義詞之間發生衝突引起的
b．非同義詞之間發生衝突引起的
c．同義詞之間或非同義詞之間發生衝突引起的
d．雜湊表「溢位」引起的
12．從外存裝置的觀點看，訪問操作的基本單位是（）
a．邏輯記錄
b．資料元素
c．檔案
d．物理記錄
13．對檔案進行檢索操作時，每次都要從第乙個記錄開始的檔案是（）a．順序檔案
b．索引檔案
c．順序索引檔案
d．雜湊檔案
14．一組記錄的鍵值為（46，74，18，53，14，20，40，38，86，65），利用
堆排序的方法建立的初始堆為（）
a．（14，18，38，46，65，40，20，53，86，74）
b．（14，38，18，46，65，20，40， 53，86，74）
c．（14，18，20，38，40，46，53，65，74，86）
d．（14，86，20，38，40，46，53，65，74，18）
15．對序列（22，86，19，49，12，30，65，35，18）進行一趟排序後得到的
結果如下：（18，12，19，22，49，30，65，35，86），則可以認為使用的排
序方法是（）
a．選擇排序
b．氣泡排序
c．快速排序
d．插入排序
二、填空題（本大題共13小題，每空2分，共26分）請在每小題的空格中填
上正確答案。錯填、不填均無分。
16．表示邏輯關係的儲存結構可以有四種方式，即順序儲存方式、鏈式儲存方式和雜湊儲存方式。
prior data next
17．設某非空雙鏈表，其結點形式為若要刪除指標q所指向的結點，則需執行下述語句段：q->prior->next＝q->next
18．如圖所示，設輸入元素的順序是a，b，c，d，通過棧的變換，在輸出端可
得到各種排列。若輸出序列的第乙個元素為d，則輸出序列為
19．佇列中允許進行刪除的一端為
20．設一棵二叉樹中度為2的結點數為10，則該樹的葉子數為
21．如圖所示的二叉樹，若按後根遍歷，則其輸出序列為
22．乙個具有n個頂點的有向完全圖的弧數為
23．查詢表的資料結構有別於線性表、樹型結構等，其邏輯結構為
24．長度為l的順序表，採用設定崗哨方式順序查詢，若查詢不成功，其查詢
長度為25．在開雜湊表上查詢某元素時，通常分兩步進行，首先必須計算該鍵值的雜湊位址，然後在位址指標所指中查詢該結點。
26．檔案的檢索有順序訪問和按關鍵字訪問三種方式。27．在待排序的n個記錄中任取乙個記錄，以該記錄的鍵值作為標準，將所有記錄分為兩組，使得第一組中各記錄的鍵值均小於或等於該鍵值，第二組中的各記錄的鍵值均大於該鍵值；然後將該記錄排在兩組中間。再對所分成的兩組分別使用上述方法，直到所有記錄都排在適當位置為止。
這種排序方法稱為
28．在對一組記錄關鍵字（54，38，96，23，15，72，60，45，83）進行氣泡排序時，整個氣泡排序過程中需進行趟才能完成。
三、應用題（本大題共5小題，共30分）
29．設有一順序佇列sq，容量為5，初始狀態時畫出做完下列操作後佇列及其頭尾指標的狀態變化情況，若不能入隊，請簡述其理由後停止。（6分）
（1）d,e,b入隊
（2）d,e出隊
（3）i,j入隊
（4）b出隊
（5）n,o,p入隊
30．已知無向圖g的鄰接矩陣如下，假設對其每行元素訪問時必須從右到左，
4分）31．畫出下列二叉樹的二叉鍊錶表示圖。（6分）
32．用二分查詢法對乙個長度為10的有序表進行查詢，填寫查詢每一元素需要的比較次數。（8分）
元素下標
比較次數
33．已知序列（
排序法對該序列進行公升序排序時的每一趟結果。（6分）
四、設計題（本大題共2小題，共14分）
34．設某帶頭結頭的單鏈表的結點結構說明如下：
typedef struct nodel
node;
試設計乙個演算法：void copy(node*head l, node*head 2)，將以head 1為頭指標的單鏈表複製到乙個不帶有頭結點且以head2為頭指標的單鏈表中。（6分）
35．修改氣泡排序法以實現雙向氣泡排序。雙向氣泡排序指第一次把最大記錄
放到表尾，第二次把最小記錄放到表頭，如此反覆進行。試編寫修改後的演算法：void dbubble(int a,int n)。（8分）
全國高等教育自學考試資料結構
全國2012年10月高等教育自學考試 資料結構導論試題及答案 課程 02142 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上...
全國高等教育自學考試資料結構
全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...