2025年4月自考02331數(shù)據(jù)結構押題及答案含解析匯總

第一章單選

1.數(shù)據(jù)結構不包含的內容是（）

A.數(shù)據(jù)的元素來源B.數(shù)據(jù)的邏輯結構C.數(shù)據(jù)的存儲結構D.對數(shù)據(jù)施加的操作

答案:A

解析:本題考查了數(shù)據(jù)結構的內容、作用和意義。數(shù)據(jù)結構包括邏輯結構和存儲結構，并且也包含某些算

法，如散列存儲就需要利用某種特定的算法來實現(xiàn)，不過數(shù)據(jù)結構不包含元素來源。

2.在數(shù)據(jù)結構中，它的基本單位是（）

A.數(shù)據(jù)B.數(shù)據(jù)項C.數(shù)據(jù)元素D.數(shù)據(jù)對象

答案:C

解析:本題考查了數(shù)據(jù)結構中數(shù)據(jù)的基本單位。數(shù)據(jù)結構的基本單位是數(shù)據(jù)元素。

3.下列關于線性結構的說法中錯誤的是（）

A.結構中只含有一個開始結點B.結構中只含有一個終端結點C.結構中的結點之間存在一對一的

對應關系D.結構中的所有結點都有一個直接前趨和直接后繼

答案:D

解析:本題考查了數(shù)據(jù)結構中的線性結構。在線性結構中，開始結點只有直接后繼，終端結點只有直接前

趨，其他說法均正確。

4.下列關于非線性結構的說法中正確的是（）

A.結構中只含有一個開始結點B.結構中只含有一個終端結點C.結構中的結點之間必定存在一對

一的對應關系D.結構中的結點可能存在多對多的對應關系

答案:D

解析:本題考查了數(shù)據(jù)結構中的非線性結構。在非線性結構中的結點之間存在一對多或多對多的對應關系，

所以可能有多個開始結點或終端結點。

5.在存儲結構的四種基本存儲方法中，需要引用“指針”的是（）

A.順序存儲方法B.鏈接存儲方法C.索引存儲方法D.散列存儲方法

答案:B

解析:本題考查了存儲結構中的鏈接存儲方法。在鏈接存儲方法中，元素間的邏輯關系是由附加的指針域表

示的，需要引用“指針”。

6.下列不屬于五個算法準則的是（）

A.輸入B.有窮性C.隨機性D.可行性

答案:C

解析:本題考查了算法的五個準則。算法的五個準則包括：輸入、輸出、有窮性、確定性和可行性。

7.若要實現(xiàn)更快速地解決問題，就需要高效率的算法，我們把執(zhí)行算法耗費的時間稱為（）

A.時間復雜度B.空間復雜度C.可讀性D.可操作性

答案:A

解析:本題考查了算法分析中的時間復雜性概念。時間復雜性，是指執(zhí)行算法所耗費的時間。

8.算法中有一指令“for(i=0；i<=9；i++)”，則該指令的執(zhí)行次數(shù)和頻度分別為（）

A.9,9B.9,10C.10,10D.10,11

答案:D

解析:本題考查了算法的頻度和時間復雜度。在該指令中，i的值由0增至9，共循環(huán)執(zhí)行10次，但由于指

令自身的特點，i的最終值為10，共計算了11次，所以該指令的執(zhí)行次數(shù)為10，自身執(zhí)行次數(shù)（頻度）為11。

9.A.AB.

BC.CD.D

答案:A

解析:本題考查了算法的時間復雜度。對于任何一個總執(zhí)行次數(shù)為常數(shù)的算法，我們都表示成1，即。

10.下列數(shù)據(jù)結構中，屬于非線性結構的是（）

A.棧B.隊列C.單鏈表D.二叉樹

答案:D

解析:本題考查了非線性結構的概念。選項中只有二叉樹是非線性結構，其余均為線性結構。

11.下列關于算法的說法錯誤的是（）

A.每一步算法的含義要明確B.算法的執(zhí)行次數(shù)是有限的C.算法只能解決數(shù)值計算問題D.

同一種問題可以有多種解決算法

答案:C

解析:本題考查了算法的概念。通過設計不同的算法可以實現(xiàn)不同的功能，不僅僅局限于數(shù)值計算問題，其

余說法均正確。

12.“算法+數(shù)據(jù)結構=程序”中的數(shù)據(jù)結構指的是（）

A.邏輯結構和存儲結構B.線性結構和非線性結構C.順序存儲和非線性結構D.線性結構和

鏈式結構

答案:A

解析:本題考查了數(shù)據(jù)結構的內容。數(shù)據(jù)結構包含邏輯結構和存儲結構。

13.若結點的存儲地址與其關鍵字之間存在某種映射關系，則稱這種存儲結構為（）

A.順序存儲結構B.鏈式存儲結構C.索引存儲結構D.散列存儲結構

答案:D

解析:本題考查了數(shù)據(jù)結構的存儲結構中的散列存儲方法。散列存儲方法根據(jù)元素的關鍵字直接計算出該元

素的存儲地址。

14.算法分析的兩個主要方面是（）

A.正確性和簡明性B.時間復雜性和空間復雜性C.可讀性和可維護性D.數(shù)據(jù)復雜性和程序

復雜性

答案:B

解析:本題考查了算法分析的兩個主要概念。算法分析中要考慮時間復雜性和空間復雜性。

15.算法指的是（）

A.計算機程序B.解決問題的計算方法C.解決問題的有限運算序列D.排序算法

答案:C

解析:本題考查了算法的描述。算法指的是解決問題的有限運算序列。

第一章填空+簡答

1.數(shù)據(jù)結構中的數(shù)據(jù)項，是具有獨立含義的________標識單位。

答案:最小

解析:本題考查了數(shù)據(jù)項的概念。數(shù)據(jù)項是具有獨立含義的最小標識單位。

2.在線性結構中，沒有直接后繼的是_______結點。

答案:終端

解析:本題考查了線性結構中的終端結點的概念。線性結構中的開始結點沒有直接前趨，只有直接后繼。終

端結點有直接前趨，沒有直接后繼。

法五原則分別是輸入、輸出、_________3、.確算定性和可行性。

答案:有窮性

解析:本題考查了算法的五個準則。算法五原則分別是輸入、輸出、有窮性、確定性和可行性。

4.數(shù)據(jù)結構一般包括邏輯結構、存儲結構和______三個方面的內容。

答案:數(shù)據(jù)運算

解析:本題考查了數(shù)據(jù)結構的內容。數(shù)據(jù)結構一般包括邏輯結構、存儲結構和數(shù)據(jù)運算。

5.數(shù)據(jù)的邏輯結構可分為非線性結構和_________兩大類。

答案:線性結構

解析:本題考查了數(shù)據(jù)的邏輯結構的概念。邏輯結構可分為線性結構和非線性結構。

6.數(shù)據(jù)的存儲結構（物理結構）一般可以用_________、鏈接存儲方法、索引存儲方法和散列存儲方法等四種存儲

方法表示。

答案:順序存儲方法

解析:本題考查了存儲結構的四種基本的存儲方法。包括順序存儲方法、鏈接存儲方法、索引存儲方法和散

列存儲方法。

7.設有一批數(shù)據(jù)元素，為了方便地插入一個元素，宜用______結構存儲。

答案:鏈接

解析:本題考查了存儲結構中鏈接存儲方法的概念。鏈接存儲方法可以方便地插入一個元素。

8.答案:

9.

答案:

10.

答案:

11.

答案:第二章

單選1

1.A.AB.B

C.CD.D

答案:A

解析:2.

A.3B.5

C.8D.10

答案:D

解析:3.已知

某線性表中含有6個元素，現(xiàn)要在第2位和第3位元素之間插入一個新的元素，那么需要移動的元素總數(shù)為（）

A.2B.4C.6D.0

答案:B

解析:本題考查了線性表的插入運算。欲在第2位和第3位元素之間插入新元素，那么這個元素應插在第3

位上，則從第3位開始，包括之后的所有元素都需向后移動一位，總數(shù)為：4.已知某

線性表中含有6個元素，現(xiàn)要刪除第3位元素，那么需要移動的元素總數(shù)為（）

A.0B.1C.2D.3

答案:D

解析:本題考查了線性表的刪除運算。欲刪除第3位元素，則該位置之后的所有元素都需向前移動一位，總

數(shù)為：5.在線性表的單鏈表存儲結構中，結點中data和next

分別表示（）

A.存儲的元素，直接前趨的地址B.存儲的元素，直接后繼的地址C.指針的數(shù)量，直接前趨的地

址D.指針的數(shù)量，直接后繼的地址

答案:B

解析:本題考查了鏈表中結點的存儲結構。結點包含兩個域，數(shù)據(jù)域（data）中存放的是存儲的元素，指針

域（next）中存放的是元素的直接后繼的地址，利用指針指向該直接后繼的結點，實現(xiàn)鏈式存儲。

6.在單鏈表中實現(xiàn)插入時，為使插入后的元素順序與輸入的元素順序一致，可采用（）

A.頭插法建表_________B.尾插法建表C.中間法建表_________D.指針法建表

答案:B

解析:本題考查了單鏈表中尾插法建表。利用頭插法建表，每次都將新元素插在表頭，最終的元素順序將與

輸入的元素順序相反；利用尾插法建表，每次都將新元素插在表尾，最終的元素順序和輸入的元素順序相同。

7.下列選項中，屬于順序存儲結構優(yōu)點的是（）

A.插入運算方便B.刪除運算方便C.存儲密度大D.方便存儲各種邏輯結構

答案:C

解析:本題考查了順序存儲結構的特點。在順序存儲結構中，不方便做元素的插入和刪除運算，因為每次都

需要移動很多元素，并且只能存儲線性結構的元素，不適于存儲非線性結構的元素。

8.在鏈式存儲結構中，方便做元素的插入和刪除運算，原因是（）

A.存儲的元素數(shù)量很少B.可進行隨機存取C.元素的存儲地址都是連續(xù)的D.采用了“指

針”表示法

答案:D

解析:本題考查了鏈式存儲結構的特點。在鏈式存儲結構中，利用“指針”指向下一個存儲的結點，在進行

元素的插入和刪除時，只需改變指針的指向即可，不需要移動大量元素。

9.下列關于線性表的說法正確的是（）

A.線性表可以含有無限個元素B.線性表中的元素只能是具體的數(shù)字C.線性表是一種線性結構

D.長度為n的線性表最多可含有n-1個元素

答案:C

解析:本題考查了線性表的概念。長度為n的線性表可含有n個元素，存放元素數(shù)量有限，并且也可存放字

符和圖片等。

10.若某線性表中第三個數(shù)據(jù)元素的存儲地址為5，每個元素占3個存儲單元，那么第10個元素的存儲地址是

（）

A.10B.20C.30D.26

答案:D

解析:

第二章單選+填空+算法閱讀+算法設計

1.下列關于線性結構的說法錯誤的是（）

A.結構中只有一個開始結點B.結構中只有一個終端結點C.終端結點的直接后繼指向開始結點

構中的數(shù)據(jù)元素呈線性關系D.結

答案:C

解析:本題考查了線性表的邏輯特征。線性結構中，數(shù)據(jù)元素是一一對應的線性關系，結構中只含有一個開

始結點和一個終端結點，并且開始結點無直接前趨，終端結點無直接后繼。

2.下列數(shù)據(jù)結構中，不屬于線性結構的是（）

A.棧B.隊列C.樹D.單鏈表

答案:C

解析:本題考查了線性表的邏輯結構特征。除了樹是非線性結構，其他均為線性結構。

3.一個線性表含有10個數(shù)據(jù)元素，每個元素占2個存儲單元，若第一個元素的存儲地址為100，則第10個數(shù)據(jù)

元素的存儲地址為（）

A.100B.110C.118D.190

答案:C

解析:4.下列

關于順序存儲結構說法正確的是（）

A.便于元素的插入B.便于元素的刪除C.含有指針D.可實現(xiàn)隨機存取

答案:D

解析:本題考查了順序存儲結構的特點。順序存儲結構不便于元素的插入和刪除，鏈式存儲結構含有指針。

5.線性表序列為{1311182031}，若將元素22插入該表中，則需移動的元素數(shù)量為（）

A.1B.2C.3D.4

答案:A

解析:本題考查了線性表的插入運算。22應插在20和31之間，所以應后移1位元素“31”。

6.對于一個需要經(jīng)常進行元素在單循環(huán)鏈表中，令頭指針head指向頭結點，則下列表示該鏈表為空的是（）

A.head==NULLB.head！=NULLC.head→next==headD.head→next==NULL

答案:C

解析:本題考查了單循環(huán)鏈表的概念?？諉窝h(huán)鏈表中無任何結點，頭指針只能指向自己。

7.下列關于鏈式存儲結構的說法正確的是（）

A.可實現(xiàn)隨機存取B.引用“指針”來呈現(xiàn)數(shù)據(jù)關系C.不利于元素的插入D.不利于元素的

刪除

答案:B

解析:本題考查了鏈式存儲結構的特點。鏈式存儲結構利于元素的插入和刪除，不可實現(xiàn)隨機存取，并引用

了指針概念。

8.線性表序列為{01122334455}，若將元素33刪除，則需移動的元素數(shù)量為（）

A.1B.2C.3D.4

答案:B

解析:本題考查了線性表的插入運算。23應插在22和33之間，所以應前移2位元素。

9.若線性表中每個元素占5個存儲單元，第1個元素的存儲地址為5，則第5個元素的存儲地址為（）

A.10B.15C.20D.25

答案:D

解析:10.順

序表中，邏輯上相鄰的元素，其存儲地址（）

A.一定相鄰B.一定不相鄰C.不一定相鄰D.可能不相鄰

答案:A

解析:本題考查了順序表中順序存儲結構的特點。順序表的特點是將邏輯上相鄰的元素存儲到地址也相鄰的

物理地址中，所以存儲地址一定相鄰。

11.在單鏈表中，結點D所指的結點不是終端結點，那么將結點H插入到結點D后的語句是_______。

答案:H→next=D→next；D→next=H

解析:本題考查了單鏈表的插入運算?！癏→next=D→next”實現(xiàn)結點H指向結點D的下一個結點，

“D→next=H”實現(xiàn)結點D指向結點H。

12.在線性結構中，沒有直接前趨的是_______結點。

答案:開始

解析:本題考查了線性表的邏輯特征。線性結構中的開始結點沒有直接前趨，只有直接后繼。

13.順序表中第一個元素的存儲地址為100，其中每個元素占5個存儲單元，那么第7個元素的存儲地址為

_______。

答案:130

解析:本題考查了線性表中元素的存儲地址關系。100+（7-1）*5=130。

14.在一個長度為n的順序表中刪除第i個元素，需要向前移動_______個元素。

答案:n-i

解析:本題考查了順序表的刪除運算。需要刪除第i個元素，所以要向前移動n-i個元素。

15.在用p指針訪問單鏈表時，判斷不是訪問結束的條件是______。

答案:p!=NULL；

解析:本題考查了單鏈表的概念。當訪問到最后的終端結點無后繼結點，所以終端結點的指針域為空，用

NULL表示。

16.在訪問單循環(huán)鏈表時，判斷不是訪問表結束的條件是________。

答案:p!=head；

解析:本題考查了單循環(huán)鏈表的概念。單循環(huán)鏈表的終端結點的指針域不為空，而是指向鏈表的頭結點，從

而構成了一個循環(huán)鏈表。

17.對于一個需要經(jīng)常進行元素增減的線性表，宜采用_______存儲結構。

答案:鏈式

解析:本題考查了鏈式存儲結構的特點。在線性表的順序存儲結構和鏈式存儲結構中，鏈式存儲結構方便元

素的插入和刪除。

18.下列函數(shù)的功能是：在帶頭結點的單鏈表上進行選擇排序。請在空白處填上適當內容將函數(shù)補充完整，并說明

該算法是否是穩(wěn)定的。答案:（1）q->next

（2）p->next=q->next（3）r->next=q該算法是穩(wěn)定的。

解析:本題考查單鏈表的刪除與插入（調換）。算法語句含義：從第一個和第二個結點開始比較，若第一個

結點大于第二個結點，則繼續(xù)比較第二個和第三個結點；若第一個結點小于第二個結點，則交換兩結點的位置；直

到查找完畢整條鏈表。該算法的目的是，將鏈表中的結點按關鍵字大小的升序進行排列，通過對算法的分析發(fā)現(xiàn)，

此類算法并不會破壞關鍵字的相對次序，所以是穩(wěn)定的。

19.下列函數(shù)的功能是在帶頭結點的單鏈表head中刪除所有數(shù)據(jù)域值為x的

結點，請在空白處填上適當?shù)恼Z句，使其完成指定的功能。

答案:（1）p->next=q（2）q=q->next（或q=p->next）

解析:本題考查的是單鏈表的刪除操作指令。

20.設非空雙向循環(huán)鏈表L的頭指針為head，表結點類型為DLNode。但L中所有結點的prior域均為空

（NULL），函數(shù)f30的功能就是為每個結點的prior域賦值，請將下列算法補充完整。

答案:（1）head（2）p->next->prior（3）head-

>prior

解析:本題考查了雙向循環(huán)鏈表的構成和指針域的賦值。（1）該語句用來判斷鏈表是否是空鏈；（2）該語

句完成prior域的賦值，使p指向的結點指向p本身，構成雙向循環(huán)鏈表；（3）該語句令頭結點head指向最后一

個結點。

21.設帶頭結點的單鏈表初始為空。將從鍵盤讀入的每個字符作為一個結點加入該鏈表表尾，當讀入回車符時結束

并返回鏈表表頭指針。請在空白處填寫適當內容，完成其功能。

答案:（1）

p=(ListNode*)malloc(sizeof(ListNode))（2）rear->next=p（3）head

解析:本題考查單鏈表的“尾插法建表”。

22.閱讀下列程序，回答問題。

style="max-width:100%;">

（1）若鏈表L={12,0,15,77,26,42}，則f30（L）的輸出結果是？（2）函數(shù)f30的功能是什么？

答案:（1）77（2）返回（找出）鏈表中結點的最大值。

23.閱讀下列算法，并回答問題。style="max-width:100%;">（1）若

SL1->data中的數(shù)據(jù)為{25，4，256，9，-38，47，128，256，64}，SL2->data中的數(shù)據(jù)為{22，4，-63，

15，29，34，42，3}，則算法f33（&SL1，&SL2）后SL1->data和SL2->data中的數(shù)據(jù)各是什么？

（2）該算法的功能是什么？

答案:本題考查了線性表的插入和刪除運算。（1）SL1->data中的數(shù)據(jù)是{25，4，256，15，29，47，

128，256，64}SL2->data中的數(shù)據(jù)是{22，4，-63，9，-38，34，42，3}（2）該算法比較兩個線性表中相同下

標位置的兩個元素，較大者移動到較長的線性表中，較小者移動到較短的線性表中。

解析:該題程序較長，但算法簡單，需耐心分析。該算法的含義是，先比較兩個線性表的長度，將長度較長

的線性表作為SL1代入f33函數(shù)中，將長度較小的線性表作為SL2代入f33函數(shù)中。比較兩個線性表中相同下標位

置的兩個元素，較大者移動到較長的線性表中，較小者移動到較短的線性表中。

24.設有兩個順序表A和B，且都遞增有序。試寫一算法，從A中刪除與B中相同的那些元素（也就是計算A-

B）。

答案:解

析:本題考查了順序表的刪除運算。算法思想是：掃描整個B表，順序取表中每個元素，然后與表A中從某下標開

始的元素進行比較（因為兩表都是有序的，不必每次從頭開始，用一個變量k標識上一次比較結束的位置），當B

中的某元素值大于或等于A的某個元素時，比較結束。記住A表的當前下標值k，之后再比較兩元素值是否相等，

若相等，則從表A中刪除該元素，而后繼續(xù)B中的下一個元素與A中從第k個元素開始向后比較；否則，繼

續(xù)，……，直到B中所有元素比較完為止。

25.設有一個帶頭結點的雙向循環(huán)鏈表，head為鏈表的頭指針。試寫一算法，實現(xiàn)在值為x的結點之前插入一個

值為y的結點。

答案:解析:本題考查了雙向

循環(huán)鏈表的查找運算。因為鏈表是雙向循環(huán)鏈表，所以不需要用指針指向x之前的結點，但要先從開始結點用循環(huán)

找到要插入的位置，也就是x結點的位置。

第三章單選

1.若入棧的一列元素序列為1,2,3,4，則可能的出棧順序是（）

A.1,4,2,3B.3,4,1,2C.2,4,3,1D.4,1,3,2

答案:C

解析:本題考查了棧的“后進先出”原則。棧中的元素遵循“后進先出”的原則，先使1進棧，然后2進

棧，再立刻讓2出棧，之后3和4入棧，再依次使4、3、1出棧。在其他選項中，出棧順序不符合“后進先出”原

則。

2.已知棧頂元素為1，則下列表示元素1出棧的運算是（）

A.InitStack(&S)B.GetTop(S)C.Push（&S,1)D.Pop（&S)

答案:D

解析:本題考查了棧的基本運算中的出棧運算。在棧的運算中，Pop（&S)表示刪除棧頂元素，即出棧。

3.下列可用于判斷順序棧是否為空棧的運算為（）

A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.S-＞top=S-＞

top+1

答案:B

解析:本題考查了順序?；具\算中的置空棧?！皉eturnS-＞top==-1”用來判斷?？眨癝-＞top=-1”

是用來令棧為空棧的。

4.在棧的鏈式存儲結構中，不需要設置頭結點的原因是（）

A.該存儲結構中的結點沒有直接前趨B.該存儲結構中的結點沒有直接后繼C.棧是非線性結構

D.只在棧頂?shù)囊欢诉M行元素的插入和刪除

答案:D

解析:本題考查了棧的鏈式存儲結構的概念。由于棧的“后進先出”原則，元素的插入和刪除都只在棧頂進

行，所以不需要設置頭結點。

5.下列可用于判斷鏈棧是否為空棧的運算為（）

A.returntop==NULLB.top=pC.p-＞next=topD.top=p-＞next

答案:A

解析:本題考查了鏈?；具\算中的判?？铡Ｔ阪湕Ｖ?，用于判斷空棧的運算是“returntop==NULL”。

6.下列關于棧和隊列的相同之處，說法正確的是（）

A.都只在一端進行元素的插入和刪除B.都遵循“先進先出”原則C.鏈式存儲結構中都不需要設

置頭結點D.鏈式存儲結構中都需要設置頭結點

答案:A

解析:本題考查了棧和隊列的概念。對于棧，只在棧頂進行元素的插入和刪除，而在隊列中，在隊尾實現(xiàn)元

素的插入，在隊頭實現(xiàn)元素的刪除，遵循“先進先出”原則，最先插入的元素也會最先被刪除；由于元素的插入和

刪除的實現(xiàn)方式不同，所以鏈棧不需要設置頭結點，而鏈式隊列需要。

7.在隊列的基本運算中，表示將元素1插入隊列中的是（）

A.InitQueue(Q)B.EnQueue(Q,1)C.DeQueue(Q)D.GetFront(Q)

答案:B

解析:本題考查了隊列的基本算法中的入隊列。在隊列的基本運算中，“EnQueue(Q,1)”表示將元素1插入

到隊列中。

8.若用一個大小為5的數(shù)組保存循環(huán)隊列Q，若經(jīng)過一次元素的插入和兩次元素的刪除后，rear和front的值分

別是1、4，那么在此之前rear和front的值分別是（）

A.0,1B.1,2C.0,2D.1,3

答案:C

解析:本題考查了順序循環(huán)隊列的rear值和front值的判斷。在循環(huán)隊列中，每經(jīng)過一次元素的插入則

rear的值加一，每經(jīng)過一次元素的刪除則front的值加一，所以應選擇C。

9.循環(huán)隊列的rear和front的值分別是1,5，若出隊一個元素，入隊兩個元素，則rear和front的值分別是

（）

A.2,5B.3,6C.2,7D.3,7

答案:B

解析:本題考查了順序循環(huán)隊列的rear值和front值的判斷。在循序隊列中，入隊時rear的值加1，出隊

時front的值加1，所以選擇B。

10.在鏈棧中，判?？盏闹噶钍牵ǎ?/p>

A.returntop==NULLB.returntopC.top==NULLD.returnS-＞data[S-＞top]

答案:A

解析:本題考查了鏈棧的基本運算中的判棧空。鏈棧的判棧空為“returntop==NULL”。

11.清空順序棧中所有數(shù)據(jù)元素的指令是（）

A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.return

top==NULL

答案:A

解析:本題考查了順序棧基本運算中的置空棧。置空棧即可達到想要的結果，而置空棧的指令為S-＞top=-

1，而returnS-＞top==-1是用來判斷空棧的。

12.若棧S的序列為{0123}，則執(zhí)行一次Pop（&S)后，棧頂元素為（）

A.0B.1C.2D.3

答案:C

解析:本題考查了棧的出棧運算。Pop（&S)是出棧指令，將會刪去棧頂元素，所以執(zhí)行后的棧頂元素為

2。

13.用于判斷順序棧是否為空棧的是（）

A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.return

top==NULL

答案:B

解析:本題考查了順序棧基本運算中的判?？铡Ｅ袟？眨簉eturnS-＞top==-1。

14.在鏈棧中，“p-＞data=x；p-＞next=top；top=p；”的含義為（）

A.數(shù)據(jù)域為p的結點x的進棧B.數(shù)據(jù)域為x的結點p的進棧C.數(shù)據(jù)域為p的結點p的出棧

D.數(shù)據(jù)域為p的結點x的出棧

答案:B

解析:本題考查了鏈棧的進棧運算?！皃-＞data=x”的含義為將x賦給結點P的數(shù)據(jù)域，“p-＞next=top；

top=p”的含義為插入結點p。

15.循環(huán)隊列的rear和front的值分別是0,2，若出隊兩個元素，入隊一個元素，則rear和front的值分別是

（）

A.0,1B.0,2C.1,3D.1,4

答案:D

解析:本題考查了循環(huán)隊列中rear值和front值的概念。在循序隊列中，入隊時rear的值加1，出隊時

front的值加1，所以選擇D。

16.用于判斷順序棧是否飽和的是（）

A.S-＞top=-1B.returnS-＞top==-1C.returnS-＞top==StackSize-1D.return

top==NULL

答案:C

解析:本題考查了順序棧的判棧滿運算。判棧滿：returnS-＞top==StackSize-1。

17.在鏈棧中，“top=p-＞next；free(p)”的含義為（）

A.結點p的進棧B.結點p的出棧C.利用結點p判棧空D.利用結點p判棧滿

答案:B

解析:本題考查了鏈棧的基本運算。見“押題精華”鏈?；具\算的實現(xiàn)。

18.若棧S的序列為{0123}，x=0，則執(zhí)行一次Push（&S,x)后，棧頂元素為（）

A.0B.1C.2D.3

答案:A

解析:本題考查了棧的入棧運算。Push（&S,x)是入棧指令，最終棧頂元素為x=0。

19.順序棧中，“S-＞top=S-＞top+1；S-＞data[S-＞top]=x”的含義是（）

A.判?？誃.判棧滿C.元素x進棧D.元素x出棧

答案:C

解析:本題考查了順序棧的進棧運算。順序棧棧頂指針top的值加1，然后將元素x放入棧頂，實現(xiàn)元素x

的進棧。

第三章填空+解答

1.現(xiàn)有可容納100個元素的數(shù)組A[0...99]，該數(shù)組供給兩個棧使用，為了充分利用存儲空間，若第一個棧的棧

底元素保存在A[99]中，那么第二個棧的棧底元素應保存在______中。

答案:A[0]

解析:本題考查了棧的順序存儲結構。為實現(xiàn)存儲空間的充分利用，應使兩個棧從頭和尾（相向而行）分別

開始進行元素的存儲，這樣一可避免為某個棧分配的存儲空間不足，二可實現(xiàn)存儲空間的充分利用。

2.假設以S和X分別表示進棧和退棧操作，則對輸入序列a,b,c,d,e進行一系列棧操作SSXSXSSXXX之后，得到的

輸出序列為_______。

答案:b,c,e,d,a

解析:本題考查了棧的基本算法的進棧和退棧操作。

3.設順序棧存放在S.data[maxsize]中，棧底位置是maxsize-1，則?？諚l件是_______；棧滿條件是______。

答案:s.top==maxsize;s.top==0

解析:本題考查了順序棧的基本運算的判?？蘸团袟M。

4.從循環(huán)隊列中刪除一個元素時，其操作是先_______，后_______。

答案:取出隊頭元素移動隊頭指針

解析:本題考查了循環(huán)隊列的基本運算中的出隊列運算。

5.若循環(huán)隊列用數(shù)組data[m]存儲元素值，用front和rear分別作為頭尾指針，則當前元素的個數(shù)為______。

答案:（rear-front+m）%m

解析:本題考查了對循環(huán)隊列中rear值和front值的運用。

6.一個直接調用自己或間接調用自己的函數(shù)，稱為______。

答案:遞歸函數(shù)

解析:本題考查了遞歸的概念。

7.假設輸入棧的元素為a、b、c，在棧S的輸出端得到一個輸出序列為a、b、c，試寫出在輸入端所有可能的輸入

序列。

答案:可能的輸入序列為：a,b,c;a,c,b;b,a,c;c,a,b;c,b,a。

解析:本題考查了棧的基本特性。

8.設將整數(shù)1,2,3,4依次進棧，進棧的同時可以出棧，請回答下述問題：（1）若入、出棧次序為

Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，則出棧的數(shù)字序列是什么？（這里Push

（i）表示i進棧，Pop（）表示出棧）（2）能否得到出棧序列1423和1432？并說明為什么？（3）請分析

1,2,3,4的24種排列中，哪些序列是可以通過相應的入、出棧操作得到的？

答案:（1）出棧序列為：1324。（2）不能得到1423序列。因為要得到14的出棧序列，則應做Push

（1）,Pop(),Push（2）,Push（3）,Push（4）,Pop()。這樣3在棧頂，2在棧底，所以不能得到23的出棧序

列。能得到1432的出棧序列。具體操作為：Push（1）,Pop(),Push（2）,Push（3）,Push

（4）,Pop(),Pop(),Pop()。（3）在1,2,3,4的24種排列中，可通過相應入、出棧操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321，不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312.

解析:本題考查了棧的基本入、出棧操作。

第三章算法閱讀+算法設計

1.已知棧的基本操作定義如下，請在空白處填寫適當內容，完成相應的功能。

答案:（1）s->top==-1（2）s->data[s->top++]

（或s->data[++s->top]）（3）s->data[s->top--]

解析:已知棧的基本操作定義本題考查棧的基本運算指令。

2.閱讀下列程序，寫出f31的輸出結果。答案:catch!

解析:本題考查了棧的基本運算算法。根據(jù)算法中的操作指令，棧中的元素會發(fā)生改變，最終借助“while”

循環(huán)并利用參數(shù)“y”將棧中的元素一一輸出。

3.假設循環(huán)隊列中只設rear和quelen來分別指示隊尾元素的位置和隊中元素的個數(shù)，試給出判別此循環(huán)隊列的

隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊頭元素。

答案:解析:本題考查了循環(huán)隊列基本運算

的判隊滿、入隊與出隊。

第四章單選

1.A.AB.

BC.CD.D

答案:B

解析:2.

A.AB.B

C.CD.D

答案:C

解析:3.

A.AB.B

C.CD.D

答案:D

解析:4.

A.AB.B

C.CD.D

答案:C

解析:5.

A.AB.B

C.CD.D

答案:B

解析:6.

A.AB.B

C.CD.D

答案:D

解析:7.

A.AB.B

C.CD.D

答案:C

解析:8.

A.AB.B

C.CD.D

答案:B

解析:9.

A.AB.B

C.CD.D

答案:C

解析:A.

AB.BC.CD.D

答案:D

解析:11.

A.AB.B

C.CD.D

答案:D

解析:本題考查了數(shù)組的順序存儲概念。

12.A.AB.B

C.CD.D

答案:B

解析:本題考查了上三角矩陣的壓縮存儲。

第四章填空+簡答

1.若廣義表A的長度為1，并且head（A）=tail（A），則A=________。

答案:（（））

解析:本題考查了廣義表的定義和基本運算。該廣義表含有一個由空表組成的元素，head（A）=（），tail

（A）=（）。

2.若廣義表S=（（a，（b）），c，（）），則head（S）=________。

答案:（a，（b））

解析:本題考查了廣義表的基本運算。head（LS）取廣義表LS展開后的第一個子表或元素。

3.若廣義表LS=（（），a，（b），c），則head（LS）=________。

答案:（）

解析:本題考查了廣義表的基本運算。head（LS）取廣義表LS展開后的第一個子表或元素，（）是一個空子

表。

4.______是指相同值的元素或零元素在矩陣中的分布有一定規(guī)律的矩陣。

答案:特殊矩陣

解析:本題考查了特殊矩陣的概念。

5.特殊矩陣和稀疏矩陣哪一種壓縮存儲后會失去隨機存取的功能？為什么？

答案:因為稀疏矩陣的非零元素的分布是沒有規(guī)律的，其壓縮存儲是采用三元組表方式。所以稀疏矩陣壓縮

后會失去隨機存取的功能。

解析:本題考查了特殊矩陣和稀疏矩陣的概念。

6.設廣義表L=（（），（）），試求head(L)、tail（L）、length（L）和depth（L）。

答案:head(L)=（）tail（L）=（（））length（L）=2depth（L）=2

解析:本題考查了廣義表的定義。

第四章算法閱讀+算法設計

1.

答案:

解析:見押題精華第四章“稀疏矩陣”。

2.

答案:

3.試寫一個算法，建立順序存儲稀疏矩陣的三元組表。

答案:解析:本題考查了稀疏矩

陣的三元組表表示方法。假設A為一個稀疏矩陣，其數(shù)據(jù)存儲在二維數(shù)組a中，b為一個存放對應于A矩陣生成的

三元組表。在這個算法中，要進行二重循環(huán)來判斷每個矩陣元素是否為零，若不為零，則將其行、列下標及其值存

入b中。

4.當稀疏矩陣A和B以三元組表作為存儲結構時，試寫出矩陣相加的算法，其結果存放在三元組表C中。

答案:

解析:本題考

查了稀疏矩陣的算法。矩陣相加就是將兩個矩陣中同一位置的元素值相加。由于兩個稀疏矩陣的非零元素按三元組

表形式存放，在建立新的三元組表C時，為了使三元組元素仍按行優(yōu)先排列，所以每次插入的三元組不一定是A

的，按照矩陣元素的行列去找A中的三元組，若有，則加入C，同時，這個元素如果在B中也有，則加上B的這個

元素值，否則這個值就不變；如果A中沒有，則找B，有則插入C，無則查找下一個矩陣元素。

第五章單選

1.某樹的結構如下，那么根節(jié)點是（）A.

AB.CC.ED.F

答案:A

解析:本題考查了樹的定義。樹由根節(jié)點開始，由上至下蔓延，一棵樹的根結點有且只有1個，位于樹的最

。頂端

2.結點C的度數(shù)和樹的度數(shù)分別是（）A.

1,2B.2,2C.2,3D.3,3

答案:C

解析:本題考查了樹的基本術語中度的概念。結點C的子樹數(shù)為2，所以結點C的度數(shù)為2；樹中根結點A的

度數(shù)為3，是所有結點的度數(shù)中最大的，所以樹的度數(shù)為3。

3.樹含有的葉子結點數(shù)量是（）A.0

B.1C.3D.4

答案:D

解析:本題考查了樹的基本術語中葉子結點的概念。度數(shù)為0的結點稱為葉子結點，樹中度數(shù)為0的結點有

B、E、F、G，所以樹的葉子結點