本文格式為Word版，下載可任意編輯——2023年10月全國自考數據結構真題及答案更多優質自考資料盡在百度貼吧自考樂園俱樂部

（http://tieba.http://.//club/5346389）歡迎?參與...歡迎?交流...止不住的驚喜等著你

2023年10月全國自考數據結構真題

一、單項選擇題（本大題共15小題，每題2分，共30分）在每題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多項選擇或未選均無分。

1.按值可否分解，數據類型尋常可分為兩類，它們是()

A.靜態類型和動態類型B.原子類型和表類型C.原子類型和結構類型D.數組類型和指針類型

答案：C

2.

D

答案：C

A.B.C.D.

ABC

3.指針p、q和r依次指向某循環鏈表中三個相鄰的結點，交換結點*q和結點*r在表中次序的程

序段是()

p->next=r；r->next=q；q->next=r->next；r->next=q；q->next=r->next；p->next=r；r->next=q；p->next=r；q->next=r->next；

答案：A

A.B.C.D.

p->next=r；q->next=r->next；r->next=q；

4.若進棧次序為a，b，c，且進棧和出棧可以穿插進行，則可能出現的含3個元素的出棧序列

個數是()567

答案：B

A.B.C.D.

3

5.假設以數組A［n］存放循環隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指

針rear指向隊尾元素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()A.rear==front

B.(front+1)％n==rearC.rear+1==front

D.

(rear+1)％n==front

答案：D

6.串的操作函數str定義為：

A.3B.4C.5D.

6

答案：C

7.二維數組A［10］［6］采用行優先的存儲方法，若每個元素占4個存儲單元，已知元素A［3］［4］的存儲地址為1000，則元素A［4］［3］的存儲地址為()

A.1020B.1024C.1036

D.

1240

答案：A

8.對廣義表L=(a，())執行操作tail(L)的結果是()

A.()B.(())C.aD.(a)

答案：B

9.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為()

A.FEDCBA

B.ABCDEF

C.FDECBAD.FBDCEA

答案：A

10.已知森林F={T1，T2，T3，T4，T5}，各棵樹Ti(i=1，2，3，4，5)中所含結點的個數分別

為7，3，5，1，2，則與F對應的二叉樹的右子樹中的結點個數為()

11

答案：D

A.B.C.D.

238

11.若非連通無向圖G含有21條邊，則G的頂點個數至少為()

A.7B.8C.21D.22

答案：B

12.如下圖的有向圖的拓撲序列是()

c，d，b，a，ec，a，d，b，ec，d，e，a，bc，a，b，d，e

答案：B

A.B.C.D.

13.

對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃

分的結果為()

(8，7，6，5，4，3，2，1)

答案：C

A.B.C.D.

(5，1，4，3，6，2，8，7)(5，1，4，3，2，6，7，8)(5，1，4，3，2，6，8，7)

14.分塊查找方法將表分為多塊，并要求()

A.塊內有序B.塊間有序C.各塊等長D.鏈式存儲

答案：B

15.

便于進行布爾查詢的文件組織方式是()

A.B.C.D.

答案：

順序文件索引文件散列文件

多關鍵字文件

二、填空題（本大題共10小題，每題2分，若有兩個空格，每個空格1分，共20分）請在每個空格中填上正確答案。錯填、不填均無分。

1.數據的鏈式存儲結構的特點是借助___表示數據元素之間的規律關系。

答案：指針

2.假使需要對線性表頻繁進行___或___操作，則不宜采用順序存儲結構。

答案：插入刪除

3.如下圖，可以利用一個向量空間同時實現兩個類型一致的棧。其中棧1為空的條件是

top1=0，棧2為空的條件是top2=n-1，則“棧滿〞的判定條件是___。

答案：top1>top2(或top2=top1-1或top1=top2+1)

4.靜態存儲分派的順序串在進行插入、置換和___等操作時可能發生越界。

答案：聯接

5.廣義表L=（a，（b，()））的深度為___。

答案：3

6.任意一棵完全二叉樹中，度為1的結點數最多為___。

答案：1

7.求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中___的數目正相關。

答案：邊

8.在5階B樹中，每個結點至多含4個關鍵字，除根結點之外，其他結點至少含___個關鍵字。

答案：2

9.若序列中關鍵字一致的記錄在排序前后的相對次序不變，則稱該排序算法是___的。

答案：穩定

10.常用的索引順序文件是___文件和___文件。

答案：ISAMVSAM

三、解答題(本大題共4小題，每題5分，共20分)

1.

答案：

2.由字符集{s，t，a，e，i}及其在電文中出現的頻度構建的哈夫曼樹如下圖。已知某段電

文的哈夫曼編碼為111000010100，請根據該哈夫曼樹進行譯碼，寫出原來的電文。答案：eatst(說明：每個字母1分)（5分）

3.已知無向圖G的鄰接表如下圖，

(1)畫出該無向圖；

（3）假使二叉排序樹T中存在含有關鍵字大于給定值x的結點，則返回指針指向它們中關鍵字最小的結點，否則返回空指針。（1分）

五、算法設計題（此題10分）

1.假設線性表采用順序存儲結構，其類型定義如下：

#defineListSize100

typedefstruct{

intdata［ListSize］;intlength;

}SeqList,*Table;

編寫算法，將順序表L中所有值為奇數的元素調整到表的前端。答案：參考答案一：

voidf34(TableL)(或者參數說明為：SeqList*L,1分)

{inti,j,t;

i=0;（初始化，1分）j=L->length-1;

while(idata［i］;（交換，2分）L->data［i］=L->data［j］;L->data［j］=t;i++;(i和j,1分)j--;

}

}(其他，如“L->〞表達，1分)

}

參考答案二：

voidf34(SeqList*L)(或者參數說明為：TableL,1分){inti,j=0,t;(初始化，1分)

for(i=0;ilength;i++)(循環控制，2分)

if(L->data［i］%2)/*奇數*/（奇數處理框架，1分）{if(i!=j)(避免同一元素交換，1分){t=L->data［i］;(交換，2分)L->data［i］=L->data［j］;L->data［j］=t;

}

更多優質自考資料盡在百度貼吧自考樂園俱樂部

（http://tieba.http://.//club/5346389）歡迎?參與...歡迎?交流.