全國2023年1月高等教育自學考試
資料結構試題
課程**：02331
一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.邏輯上通常可以將資料結構分為（ ）
a.動態結構和靜態結構 b.順序結構和鏈式結構
c.線性結構和非線性結構 d.初等結構和組合結構
2.在下列對順序表進行的操作中，演算法時間複雜度為o(1)的是（ ）
a.訪問第i個元素的前驅（1<）
b.在第i個元素之後插入乙個新元素()
c.刪除第i個元素()
d.對順序表中元素進行排序
3.假設帶頭結點的單向迴圈鍊錶的頭指標為head,則該鍊錶為空的判定條件是（ ）
a.head= =null b.head–>next= =null
c.head!=null d.head–>next= =head
4.已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則可能出現的出棧序列為（ ）
a.5，4，3，2，1，6 b.2，3，5，6，1，4
c.3，2，5，4，1，6 d.1，4，6，5，2，3
5.與線性表相比，串的插入和刪除操作的特點是（ ）
a.通常以串整體作為操作物件 b.需要更多的輔助空間
c.演算法的時間複雜度較高 d.涉及移動的元素更多
6.假設以三元組表表示稀疏矩陣，則與如圖所示三元組表對應的4×5的稀疏矩陣是（注：矩陣的行列下標均從1開始）（ ）
a. b.
c. d.
7.以下有關廣義表的表述中，正確的是（ ）
a.由0個或多個原子或子表構成的有限序列
b.至少有乙個元素是子表
c.不能遞迴定義
d.不能為空表
8.樹的先根序列等同於與該樹對應的二叉樹的（ ）
a.先序序列 b.中序序列
c.後序序列 d.層序序列
9.假設有向圖含n個頂點及e條弧，則表示該圖的鄰接表中包含的弧結點個數為（ ）
a.n b.e
c.2e d.n·e
10.如圖所示的有向無環圖可以得到的不同拓撲序列的個數為（ ）
a.1 b.2
c.3 d.4
11.下列排序方法中，穩定的排序方法為（ ）
a.希爾排序 b.堆排序
c.快速排序 d.直接插入排序
12.對下列關鍵字序列進行快速排序時，所需進行比較次數最少的是（ ）
a.（1，2，3，4，5，6，7，8） b.（8，7，6，5，4，3，2，1）
c.（4，3，8，6，1，7，5，2） d.（2，1，5，4，3，6，7，8）
13.含n個關鍵字的二叉排序樹的平均查詢長度主要取決於（ ）
a.關鍵字的個數 b.樹的形態
c.關鍵字的取值範圍 d.關鍵字的資料型別
14.下列查詢演算法中，平均查詢長度與元素個數n不直接相關的查詢方法是（ ）
a.分塊查詢 b.順序查詢
c.二分查詢 d.雜湊查詢
15.可有效提高次關鍵字查詢效率的檔案是（ ）
a.順序檔案 b.倒排檔案
c.雜湊檔案 d.vsam檔案
二、填空題（本大題共10小題，每小題2分，共20分）
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.資料的儲存結構是其邏輯結構
17.輸入線性表的n個元素建立帶頭結點的單鏈表，其時間複雜度為
18.假設迴圈佇列的元素儲存空間大小為m，隊頭指標f指向隊頭元素，隊尾指標r指向隊尾元素的下乙個位置，則在少用乙個元素空間的前提下，表示「隊滿」的條件是
19.給定串的聯接操作函式：
char *strcat(char *to, char *from);
//將串from聯接到串to的末尾，並返回聯接後的串
若字串s1=〞point〞,s2=〞of〞,則strcat(s1,strcat)(s2,s1))的操作結果是
20.假設二維陣列a[8][10]按行優先順序儲存,若每個元素佔2個儲存單元,元素a[0][0]的儲存位址為100,則元素a[4][5]的儲存位址為
21.假設一棵完全二叉樹含1000個結點,則其中度為2的結點數為
22.已知乙個有向網如圖所示,從頂點1到頂點4的最短路徑長度為
23.在快速排序、堆排序和歸併排序中，最壞時間複雜度為o(n2)的排序演算法有
24.假設雜湊表的表長為11,雜湊函式為h(key)=key%7,若用線性探測處理衝突,則探查位址序列hi的計算公式為
25.vsam檔案由和資料集三部分組成。
三、解答題（本大題共4小題，每小題5分，共20分）
26.已知廣義表的圖形表示如圖所示,
(1) 寫出該廣義表l;
(2) 分別寫出該廣義表的深度和長度。
(1)(2)27.已知二叉樹的先序序列和中序序列分別為abdehcfi和dbheacif，
(1) 畫出該二叉樹的二叉鍊錶儲存表示;
(2) 寫出該二叉樹的後序序列。
(1)(2)28.已知有向圖的鄰接表如圖所示,
(1) 寫出從頂點a出發,對該圖進行廣度優先搜尋遍歷的頂點序列;
(2) 畫出該有向圖的逆鄰接表。
(1)(2)
29.依次讀入給定的整數序列，完成下列操作：
1)構造一棵二叉排序樹,計算在等概率情況下該二叉排序樹的平均查詢長度asl;
2)若變更序列中元素的排列,可構造出平均查詢長度達到最小的二叉排序樹。寫出滿足上述要求的序列中的第乙個元素。
(1)(2)
四、演算法閱讀題（本大題共4小題，每小題5分，共20分）
30.假設以帶頭結點的單鏈表表示線性表,閱讀下列演算法f30,並回答問題:
(1) 設線性表為( a1, a2, a3, a4, a5, a6, a7 ), 寫出執行演算法f30後的線性表；
(2) 簡述演算法f30的功能。
void f30(linklist l)
} (1)
(2)31.演算法f31的功能是借助棧結構實現整數從10進製到8進製的轉換，閱讀演算法並回答問題：
(1) 畫出n為十進位制的1348時演算法執行過程中棧的動態變化情況;
(2) 說明演算法中while迴圈完成的操作。
void f31(int n) //n為非負的十進位制整數
while (n);
while ( ! stackempty(& s))
}(1)
(2)32.已知以二叉鍊錶作二叉樹的儲存結構，閱讀演算法f32，並回答問題：
(1) 設二叉樹t如圖所示,寫出執行f32(t)的返回值;
(2) 簡述演算法f32的功能。
int f32(bintree t)
}(1)
(2)33.設有向圖鄰接表定義如下；
typedef struct algraph鄰接表型別
其中頂點表結點vertexnode結構為：
邊表結點edegnode結構為：
閱讀下列演算法f33，並回答問題：
(1)已知有向圖g的鄰接表如圖所示,
寫出演算法f33的輸出結果;
(2)簡述演算法f33的功能。
void dfs (algraph *g,int v)
void f33(algraph *g)
}(1)(2)
五、演算法設計題(本大題10分)
34.假設以單鏈表表示線性表,單鏈表的型別定義如下:
typedef struct node linknode, *linklist;
編寫演算法,將乙個頭指標為head且不帶頭結點的單鏈表改造為乙個含頭結點且頭指標仍為head的單向迴圈鍊錶,並分析演算法的時間複雜度。
資料結構導論自考試題
全國2008年10月高等教育自學考試 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.從邏輯上可以把資料結構分為 a.動態結構 靜態結構 b.順序結構 鏈式結構 c....
02331自考全國資料結構試題
a.a,b,cb.a,b,c c.a b,cd.a,b,c 8.二維陣列a按行優先順序儲存，其中每個元素佔1個儲存單元。若a 1 1 的儲存位址為420，a 3 3 的儲存位址為446，則a 5 5 的儲存位址為 a.470b.471 c.472d.473 9.二叉樹中第5層上的結點個數最多為 a....
資料結構考試題
要求 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。1.資料結構是指 a.一種資料型別 b.資料的儲存結構 c.一組性質相同的資料元素的集合 d.相互之間存在一種或多種特定關係的資料元素的集合 2.以下演算法的時間複雜度為 void fun int n a.o n...