更多優質自考資料盡在百度貼吧自考樂園俱樂部
（歡迎加入...歡迎交流...止不住的驚喜等著你.........
2023年全國自考資料結構模擬試卷(九)
一、單項選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個備選專案中
只有乙個是符號題目要求的,請將其**填寫的括號內.錯選、多選或未選均無分。
1. 當初始序列已經按鍵值有序時，用直接插入演算法進行排序，需要比較的次數為()
a. a
b. b
c. c
d. d
答案：d
2. 堆(heap)是()
a. 完全二叉樹
b. 線性表
c. 二叉排序樹
d. 平衡二叉樹
答案：b
3. 非空的單迴圈鍊錶l的尾結點p↑，滿足()
a. p↑.next＝null；
b. p＝null；
c. p↑.next＝l；
d. p＝l
答案：c
4. 在乙個鏈佇列中，若f,r分別為隊首、隊尾指標，則插入s所指結點的操作為()
a. f->next=c;f=s;
b. r->next=s;r=s;
c. s->next=r;r=s
d. s->next=f,f=s;
答案：b
5. 設陣列data［0..m］作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則
執行出隊操作的語句為()
a. front:＝front+1
b. front:＝(front+1)mod m
c. rear:＝(rear+1)mod m
d. front:＝(front+1)mod (m+1)
答案：d
6. 設有乙個無向圖g＝(v，e)和g′＝(v′，e′)，如果g′是g的生成樹，則下面不正確的說
法是()
a. g′為g的子圖
b. g′為g的連通分量
c. g′為g的極小連通子圖且v′＝v
d. g′是g的乙個無環子圖
答案：b
7. 在圖的鄰接表儲存結構上執行深度優先搜尋遍歷類似於二叉樹上的()
a. 先序遍歷
b. 中序遍歷
c. 後序遍歷
d. 按層次遍歷
答案：a
8. 二維陣列m［i,j］的元素是4個字元(每個字元佔乙個儲存單元)組成的串，行下標i的範圍
從0到4，列下標j的範圍從0到5。m按行儲存時元素m［3，5］的起始位址與m按列儲存時元素()的
起始位址相同。
a. m［2，4］
b. m［3，4］
c. m［3，5］
d. m［4，4］
答案：b
9. 含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過()
a. 1
b. n/2
c. n-1
d. n
答案：c
10. 在一棵完全二叉樹的順序儲存方式中，若編號為t的結點有右孩子，則此結點右孩子的編
號為()
a. 2t
b. 2t-1
c. 2t+1
d. t/2
答案：c
11. 如果t2是由有序樹t轉換而來的二叉樹，那麼t中結點的後序就是t2中結點的()前序b.中序
c.後序d.層次序
a. 前序
b. 中序
c. 後序
d. 層次序
答案：b
12. 串是一種特殊的線性表，其特殊性體現在()
a. 可以順序儲存
b. 資料元素是乙個字元
c. 可以鏈結儲存
d. 資料元素可以是多個字元
答案：b
13. 下面四種內排序方法中，要求記憶體容量最大的是()
a. 插入排序
b. 選擇排序
c. 快速排序
d. 歸併排序
答案：d
14. 從乙個包含2000個結點的雜湊表a［1..2000］中查詢結點的平均比較次數()從乙個包含
200個結點的雜湊表b［1..200］中查詢結點的平均比
較次數。
a. 大於
b. 小於
c. 等於
d. 不確定
答案：d
15. 對一棵非空二叉樹進行中序遍歷，則根結點的左邊()
a. 只有左子樹上的所有結點
b. 只有右子樹上的所有結點
c. 只有左子樹上的部分結點
d. 只有右子樹上的部分結點
答案：a
二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填寫上正確
答案。錯填、不填均無分。
1. 設樹t的度為4，其中度為1、2、3和4的結點個數分別是4、2、1和1，則t中葉子結點的個數
是：___。
答案：8個
2. 任意一棵具有n個結點的二叉樹，若它有m個葉子，則該二叉樹上度數為1的結點為___個 。
答案：n-2m+1
3. 有m個葉子結點(又稱外結點)的哈夫曼樹，其結點總數是___。
答案：2m-1
4. 在二叉排序樹中，其左子樹中任何乙個結點的關鍵字一定___其右子樹的各結點的關鍵字。
答案：小於
5. 從乙個順序儲存的迴圈佇列中刪除乙個元素時，應該___。
答案：先移動隊首指標，後取出元素
6. 對角矩陣中，除了___的元素之外，其餘的元素都是零。則對於乙個k對角線矩陣(k為奇數
)a是滿足下面的條件的矩陣；如果___，則元素aij=0。
答案：主對角線和主對角線相臨兩側的若干條對角線上i＞k或j＞k
7. 在串的鏈式儲存結構中，有乙個串s1=″ejidc″，我們假設儲存時結點的大小為1，並設指
針占有4個位元組，則鏈串的儲存密度為___，又假設串
s2=″abcdefg″在儲存時我們設定結點的大小為4，指標占有4個位元組，則此鏈串的儲存密度為
___。
答案：20% 50%
8. 對於乙個具有n條邊和e個頂點的圖來說，如果採用鄰接表表示，則其空間複雜度為___，若
採用鄰接矩陣表示，則其空間複雜度為___。
答案：9. 陣列a［1..10,-2..6,2..8］以行優先順序儲存，設第乙個元素的首位址是100，每個元素
佔3個儲存長度的儲存空間，則元素a［5，0，7］
的儲存位址為___。
答案：913
10. ___查詢法的平均查詢長度與元素個數n無關。
答案：雜湊表
三、解答題（本大題共4小題，每小題5分，共20分）
1. 已知有一關鍵字序列為，如果我們採用直
接選擇排序方法對此序列進行排序(按照公升序排列)，請給出每一趟的排序結果。
答案：直接選擇排序的過程為：從第i趟開始時，當前的有序區和無序區分別為r［1…i］和
r［1…n］(1≤-1≤n-1)，則在該趟排序是從當前無序區中選出關鍵字最小的記錄r［k］，將它
與無序區中的第1個記錄r［i］交換，使r［1…i］和r［i+1…n］分別變成新的有序區和新的無
序區，每次排序都使有序區增加乙個記錄，無序區減少乙個記錄，按照以上規則，我們得到各趟
結果如下：
初始：97，86，53，108，72，34，215，232，11，68
第1趟：11［86，53，108，72，34，215，232，97，68］
第2趟：11，34［53，108，72，86，215，232，97，68］
第3趟：11，34，53［108，72，86，215，232，97，68］
第4趟：11，34，53，68［72，86，215，232，97，108］
第5趟：11，34，53，68，72［86，215，232，97，108］
第6趟：11，34，53，68，72，86［215，232，97，108］
第7趟：11，34，53，68，72，86，97［232，215，108］
第8趟：11，34，53，68，72，86，97，108［215，232］
第9趟：11，34，53，68，72，86，97，108，215，232
2. 判別下列二序列是否為堆，如不是，按照對序列建堆的思想把它調整為堆，用圖表示建堆
的過程。
（1）(1，5，7，25，21，8，8，42)
（2）(3，9，5，8，4，17，21，6)
答案：序列(1)為堆；
序列(2)不是堆，調整為堆的過程如下圖所示：
3. 已知雜湊函式為h(k)=k mod 12,鍵值序列為
25，37，52，43，84，99，120，15，26，11，70，82，採用拉鍊法處理衝突，試構造開雜湊表
，並計算查詢成功的平均查詢長度。
答案：4. 已知有如下乙個關鍵字序列,按照上述插入順序構造
一棵二叉排序樹，則請給出二叉排序樹的構造過
程，說明其深度，並在等概率的條件下求出平均查詢長度。
答案：根據二叉排序樹的生成過程，我們可以得到如下二叉排序樹的構造結果：
此二叉排序樹的深度(即高度)為4，在二叉樹上，要找到第i層上的結點恰好需要比較i次，而在
此二叉排序樹上，第1，2，3，4層上分別有1，2
，3，4個結點，則在等概率的條件下，查詢成功的平均查詢長度為：
四、演算法閱讀題（本大題共4小題，每小題5分，共20分）
1. 以下演算法假定以線性探測法解決衝突，在閉雜湊表hl中查詢鍵值為k的結點，成功時回送該
位置；不成功時回送標誌-1。請分析程式，並在___上填充合適的語句。
int search-closehash(keytype k,closehash hl)
答案：(i+1)/m hl［i］.key==k
2. 以下為順序表的定位運算，分析演算法，請在___處用正確的語句予以填充。
int locate-sqlist(sqlist l,datatype x)
/*在順序表l中查詢第乙個值等於x的結點。若找到回傳該結點序號；否則回傳0*/
答案：i=1 i≤
3. 基於三元組的稀疏矩陣轉置的處理方法有兩種，以下運算按照矩陣a的列序來進行轉置，請
在___處用適當的語句予以填充。
trans-sparmat(spmatrixtp a,spmatrixtp *b) }
}答案：col<= q++
2023年全國自考資料結構模擬試卷 八 及答案
更多優質自考資料盡在貼吧自考樂園俱樂部 歡迎加入.歡迎交流.止不住的驚喜等著你.2010年全國自考資料結構模擬試卷 八 一 單項選擇題 本大題共15小題,每小題2分,共30分 在每小題列出的四個備選專案中 只有乙個是符號題目要求的,請將其 填寫的括號內.錯選 多選或未選均無分。1.在下面的程式中，語...
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....
全國自考試題資料結構試卷
全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和...