數據結構習題集含答案

目錄

目錄1

選擇題2

第一章緒論2

第二章線性表4

第三章棧和隊列5

第四章串6

第五章數組和廣義表7

第六章樹和二叉樹7

第七章圖9

第八章查找10

第九章排序II

簡答題15

第一章緒論15

第二章線性表18

第三章棧和隊列20

第四章串21

第五章數組和廣義表22

第六章樹和二叉樹23

第七章圖25

第八章查找26

第九章排序26

編程題28

第一章緒論28

第二章線性表28

第三章棧和隊列38

第四章串38

第五章數組和廣義表38

第六章樹和二叉樹38

第七章圖38

第八章查找38

第九章排序44

選擇題

第一章緒論

1.數據結構這門學科是針對什么問題而產生的？〔A

A、針對非數值計算的程序設計問題B、針對數值計算的程序設計問題

C、數值計算與非數值計算的問題都針對D、兩者都不針對

2.數據結構這門學科的研究內容下面選項最準確的是〔D

A、研究數據對象和數據之間的關系B、研究數據對象

C、研究數據對象和數據的操作D、研究數據對象、數據之間的關系和操作

3.某班級的學生成績表中查得張三同學的各科成績記錄，其中數據結構考了90

分，那么下面關于數據對象、數據元素、數據項描述正確的是〔C

A、某班級的學生成績表是數據元素,90分是數據項

B、某班級的學生成績表是數據對象,90分是數據元素

C、某班級的學生成績表是數據對象,90分是數據項

D、某班級的學生成績表是數據元素,90分是數據元素

4.*數據結構是指〔A。

A、數據元素的組織形式B、數據類型

C、數據存儲結構D、數據定義

5.數據在計算機存儲器內表示時，物理地址與邏輯地址不相同,稱之為〔C

A、存儲結構B、邏輯結構

C、鏈式存儲結構D、順序存儲結構

6.算法分析的目的是〔C

A、找出數據的合理性B、研究算法中的輸入和輸出關系

C、分析算法效率以求改進D、分析算法的易懂性和文檔型性

7.算法分析的主要方法〔A。

A、空間復雜度和時間復雜度B、正確性和簡明性

C、可讀性和文檔性D、數據復雜性和程序復雜性

8.計算機內部處理的基本單元是〔B

A、數據B、數據元素C、數據項D、數據庫

9.數據在計算機內有鏈式和順序兩種存儲方式,在存儲空間使用的靈活性上，鏈

式存儲比順序存儲要〔B。

A、低B、高C、相同D、不好說

10.算法的時間復雜度取決于〔C

A、問題的規(guī)模B、待處理數據的初始狀態(tài)

C、問題的規(guī)模和待處理數據的初始狀態(tài)D、不好說

11.數據結構既研究數據的邏輯結構，又研究物理結構，這種觀點〔Bo

A、正確B、錯誤

C、前半句對，后半句錯D、前半句錯，后半句對

12.在數據結構中，從邏輯上可以把數據結構分成〔C

A、動態(tài)結構和靜態(tài)結構B、緊湊結構和非緊湊結構

C、線性結構和非線性結構D、內部結構和外部結構

13.線性表的順序存儲結構是一種＜＞的存儲結構，線性表的鏈式存儲結構是一

種〔A存儲結構。

A、隨機存取B、順序存取

C、索引存取D、散列存取

14.*下列程序的時間復雜度是〔A

for<i=l;i<=n;++i>{

for<j=l;j<=n;++j>{

c[i][j]=0;

)

)

A、0<n2>B、0<n>C、0<2n>D、0<2n2>

15.*下列程序的空間復雜度是〔A

for<i=l;i<=n;++i>{

for<j=l;j<=m;++j>{

c[i][j]=0;

)

)

A、0<m*n>B>0<m+n>C、0<m-n>D、0<m/n>

16.*求下列程序段的時間復雜度＜B＞

for<i=l;i<=n;i++>

for<j=l;j<=n;j++>

x=x+l;

A、O<n2>B、O<n>C>O<1>D、O<0>

第二章線性表

1.關于線性表的說法不正確的是？〔D

A、存在唯一的一個被稱為〃第一個”的數據元素〔開始結點

B、存在唯一的一個被稱為"最后一個"的數據元素（終端結點

C、除第一個之外，集合中的每個數據元素均只有一個前驅

D、除第一個之外，集合中的每個數據元素均只有一個后繼

2.關于順序表的說法不正確的是？〔D

A、邏輯關系上相鄰的兩個元素在物理存儲位置上也相鄰

B、可以隨機存取表中任一元素，方便快捷

C、在線性表中插入某一元素時，往往需要移動大量元素

D、在線性表中刪除某一元素時,無需移動大量元素

3.當線性表的元素總數基本穩(wěn)定,且很少進行插入和刪除操作，但要求以最快

的速度存取線性表中的元素時,應采用仕么存儲結構？〔A

A、順序表B、單鏈表C、循環(huán)鏈表D、雙鏈表

4.在一個長度為n的順序表中第i個元素〔l〈=i〈=n之前插入一個元素時,需向

后移動多少個元素。〔C

A、n-1B、n-iC、n-i+1D、n-i-l

5.在單鏈表中設置頭結點的作用是〈＞o

A、單鏈表定義而已B、指定表的起始位置

C、為雙向鏈表做準備D、為循環(huán)鏈表做準備

6.根據線性表鏈式存儲結構中每一個結點包含的指針數，將線性鏈表分成〔C

A、單鏈表與循環(huán)鏈表B、單鏈表與十字鏈表

C、單鏈表與雙鏈表D、循環(huán)鏈表與多鏈表

7.鏈接存儲的特點是利用仕么來表示數據元素之間的邏輯關系〔A

A、引用B、串聯(lián)C、掛接D、指派

8.已知指針p指向單鏈表L中的某結點,則刪除其后繼結點的語句是〔D

9.*在單鏈表L中,指針p所指結點有后繼結點的條件是〔B

A>p=p.nextB、p.next!=null

10.*在單鏈表P結點之后插入s結點的操作是〔C

A、p.next=s;s.next=p.next;B、s.next=p.next;p.next=p.next,next;

C、s.next=p.next;p.next=s;D、s.next=p;p.next=s;

第三章棧和隊列

1.棧、隊列通常采用兩種存儲結構，它們是〈B>

A、散列方式和索引方式B、順序存儲結構和鏈式存儲結構

C、鏈表存儲結構和數組D、線性和非線性存儲結構

2.一個棧入棧序列是a,b,c,d,則棧輸出序列不可能是〈C>

A、d,c,b,aB、c,d,b,aC、d,c,a,bD、a,b,c,d

3.判斷順序棧〔最多結點數為m為棧滿的條件是〔D

A、top=0B、top!=mC、top!=0D、top==m

4.棧存取數據原則〔或棧特點是〔B

A、后進后出B、后進先出C、先進先出D、隨意進出

5.*經過以下棧運算后,x的值是〔A

InitStack<s>;

Push<s,d>;

Push<s,e>;

Pop<szx>;

Pop<szx>;

GetTop<s,x>;

A、dB、eC>xD、s

6.一個隊列的進隊序列為：a,b,c,d,則出隊序列是：〈A〉

A、a,b,c,dB、d,c,b,a

C、a,d,c,bD、c,b,d,a

7.循環(huán)隊列為空隊列的條件是：〔D

A、Q.front=0B、Q.(rear+l>%MaxSize==Q.front

C、Q.rear=0D>Q.rear==Q.front

8.在存儲結構上,如果用帶頭節(jié)點單鏈表實現(xiàn)隊列〔假定front和rear分別為

隊首和隊尾指針,則刪除一個結點的操作為〔A。

A、front.next=front.next,nextB、rear=rear.next

C、rear=front.nextD、front=front,next

9.棧和隊列共同點是〔C

A、先進后出B、先進先出

C、允許在端點處進行操作線性表D、無共同點

10.插入和刪除只能在一端進行的線性表是〔B

A、循環(huán)隊列B、棧

C、隊列D、循環(huán)棧

11.插入和刪除分別在兩端端進行的線性表是〔C

A、循環(huán)隊列B、棧

C、隊列D、循環(huán)棧

12.循環(huán)隊列為滿隊列的條件是：〔B

A、Q.front=0B、Q.(rear+1>%MaxSize==Q.front

C、Q.rear=0D、Q.rear==Q.front

第四章串

1.關于串的敘述，錯誤的是:

A.串是字符有限序列B.空串是由空格構成的串

C.模式匹配是串的重要運算D.串有用順序、鏈式兩種存儲方式

2.串長度是指〔B

A.串所含不同字母數目B.串所含字符數目

C.串所含不同字符數目D.串所含非空格字符數目

3.*若串S="database”,其子串數目是〔B。

A.16B.37C.8D.36

4.設串S1是串S子串，則求S1在S中定位運算稱為〔B

A.求子串B.串匹配C.聯(lián)接D.求串長

5.設有串sl="welcometozdsoftcolleage!”和s2="so”,那么s2在si中的

索引位置是（C

A.12B.14C.13D.10

6.*若串S="software”,其子串的數目是〔B。

A.8B.37C.36D.9

第五章數組和廣義表

第六章樹和二叉樹

1.假設在一棵二叉樹中，雙分支結點數為15,單分支結點數為30個,則葉子結

點數為〔B個。

A.15B.16C.17D.47

2.假定一棵三叉樹的結點數為50,則它的最小高度為〔Co

A.3B.4C.5D.6

3.在一棵二叉樹上第4層的結點數最多為〔D。

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

4.用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組中結

點R[i]若有左孩子，其左孩子的編號為結點〔Bo

A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]

5.設n,m為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是

〔Bo

A.n在m右方B.nm

C.n是m的祖先D.n是m的子孫

6.下面敘述正確的是〔Do

A.二叉樹是特殊的樹

B.二叉樹等價于度為2的樹

C.完全二叉樹必為滿二叉樹

D.二叉樹的左右子樹有次序之分

7.現(xiàn)有一深度為5的二叉樹，請問其最多有〔D個結點。

A.32B.5C.30D.31

8.現(xiàn)有一深度為4的二叉樹，請問其最多有〔A個結點。

A.15B.16C.17D.6

9.在一棵二叉排序樹上按〔B遍歷得到的結點序列是一個有序序列。

A.先序B.中序C.后序D.頭序

10.在一棵二叉樹中，度為0的結點數為no,度為2的結點數為ri2,則no=〔C

A.n+1B.n+2C.n2+1D.2n+1

11.由三個結點構成的二叉樹，共有〔B種不同的形態(tài)。

A.4B.5C.6D.7

12.一棵含有n個結點的樹，〔A形態(tài)達到最大深度。

A.單支樹B.二叉樹C.三叉樹D.n叉樹

13.不含任何結點的空樹〔Co

A.是一棵樹；B.是一棵二叉樹；

C.是一棵樹也是一棵二叉樹；D.既不是樹也不是二叉樹

14.二叉樹是非線性數據結構，所以<C>o

A.它不能用順序存儲結構存儲；B.它不能用鏈式存儲結構存儲；

C.順序存儲結構和鏈式存儲結構都能存儲；

D.順序存儲結構和鏈式存儲結構都不能使用

15.具有n<n>0>個結點的完全二叉樹的深度為<C>。

A.log2<n>B.Iog2<n>C.[Iog2<n>]+1D.Iog2<n>+1

16.在一棵三元樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結

點數為2個,則度為0的結點數為〔D個。

A.4B.5C.6D.7

17.有關二叉樹下列說法正確的是〔B

A.二叉樹的度為2B.一棵二叉樹的度可以小于2

C.二叉樹中至少有一個結點的度為2D.二叉樹中任何一個結點的度都為2

18.在完全二叉樹中，若一個結點是葉結點,則它沒〔C。

A.左子結點B.右子結點

C.左子結點和右子結點D.左子結點,右子結點和兄弟結點

19.在下列情況中，可稱為二叉樹的是〔B

A.每個結點至多有兩棵子樹的樹B.哈夫曼樹

C.每個結點至多有兩棵子樹的有序樹D.每個結點只有一棵右子樹

第七章圖

1.圖的深度優(yōu)先遍歷類似于二叉樹的〔Ao

A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷

2.已知一個圖如圖所示，若從頂點a出發(fā)按深度優(yōu)先遍歷，則可能得到的一種頂

點序列為〔C

A.abecdfB.acfebdC.aebcfdD.aedfcb

3.若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有

的頂點，則該圖一定是〔B圖。

A.非連通B.連通C.強連通D.有向

4.在一個圖中，所有頂點的度數之和等于所有邊數的〔C倍。

A1/2BlC2D3

5.在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的〔B倍。

A1/2BlC2D3

6.一個有N個頂點的有向圖最多有〔B條邊。

ANBN<N-1>CN<n-l>/2D2N

7.具有4個頂點的無向完全圖有〔A條邊。

A6B12C18D20

8.具有6個頂點的無向圖至少有A條邊才能確保是一個連通圖。

A5B6C7D8

9.對于一個具有N個頂點的無向圖,若采用鄰接矩陣表示，則該矩陣大小是〔D

ANB<N-1>2CN-lDN*N

10.一個具有N個頂點的無向圖中，要連通全部頂點至少要〔C條邊

ANBN+lCN-lDN/2

11.*已知圖的鄰接矩陣如圖所示，則從頂點0出發(fā)按深度優(yōu)先遍歷的結果是

0111101

〔c1001001

1000100

1100110

1011010

0001101

1100010

A.0243156B.0136542C.0134256D.0361542

12.已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結果是〔

按深度優(yōu)先遍歷的結果是〔D。

A.0132B.0231C.0321D.0123

13.已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結果是〔，

按深度優(yōu)先遍歷的結果是〔。

A.0132B.0231C.0321D.0123

14.當在一個有序的順序表上查找一個數據時，既可用折半查找，也可用順序查找,

但前者比后者的查找速度〔CO

A.必定快B.不一定

C.在大部分情況下要快D.取決于表遞增還是遞減

15.折半查找有序表C4,6,10,12,20,30,50,70,88,100o若查找表中元素58,則它

將依次與表中〔A比較大小，查找結果是失敗。

A.20,70,30,50B.30,88,70,50

C.20,50D.30,88,50

第八章查找

1.順序查找法適合于存儲結構為〔B的線性表。

A.散列存儲B.順序存儲或鏈式存儲

C.壓縮存儲D.索引存儲

2.在查找過程中，若同時還要增、刪工作，這種查找稱為〔Bo

A、靜態(tài)查找B、動態(tài)查找C、內查找D、外查找

3.索引順序表的特點是順序表中的數據〔Ao

A、有序B、無序C、塊間有序D、散列

4.采用順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為〔C

A、nB>n/2C><n+l>/2D><n-l>/2

5.*將10個元素散列到1000000個單元的哈希表，則〔C產生沖突。

A、一定會B、一定不會C、仍可能會D、以上都不對

6.*散列表的地址區(qū)間為0?16,散列函數H<k>=k%17,采用線性探測法解決地

址沖突，將關鍵字26、25、72、38、1、18、59依次存儲到散列表中。元素

59存放在散列表中的地址為〔A

A、8B、9C、10D、11

7.設有序表的關鍵字序列為{1,3,9,12,32,41,45,62,75,77,82,95,100},當采用二

分查找法查找值為82的節(jié)點時，經〔C次比較后查找成功。

A、IB、2C、3D、4

8.設有100個元素，用折半查找法進行查找時，最大、最小比較次數分別時〔A

A、7,IB,6,IC、5,ID、8,1

第九章排序

1.對n個不同的記錄按排序碼值從小到大次序重新排列，用冒泡〈起泡〉排序方

法，初始序列在〔A情況下，與排序碼值總比較次數最少。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

2.對n個不同的記錄按排序碼值從小到大次序重新排列，用冒泡〈起泡〉排序方

法，在〔B情況下，與排序碼值總比較次數最多。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

3.對n個不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法,

初始序列在〔A情況下，與排序碼值總比較次數最少。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

4.對n個不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法,

初始序列在〔B情況下，與排序碼值總比較次數最多。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

5.對n個不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法在

〔C情況下，與排序碼值總比較次數最少。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

6.對n個不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法，在

〔A情況下與排序碼值總比較次數最多。

A.按排序碼值從小到大排列B.按排序碼值從大到小排列

C.隨機排列〈完全無序〉D.基本按排序碼值升序排列

7.用冒泡排序方法對n個記錄按排序碼值從小到大排序時，當初始序列是按排

序碼值從大到小排列時,與碼值總比較次數是〔D。

A.n-lB.nC.n+1D.n<n-l>/2

8.下列排序方法中，與排序碼值總比較次數與待排序記錄的初始序列排列狀態(tài)

無關的是vD>o

A.直接插入排序B.冒泡排序C.快速排序D.直接選擇排序

9.將6個不同的整數進行排序,至少需要比較vA>次。

A.5B.6C.15D.21

10.將6個不同的整數進行排序,至多需要比較vC>次。

A.5B.6C.15D.21

11.*若需要時間復雜度在O＜nlog2n＞內,對整數數組進行排序，且要求排序方法是

穩(wěn)定的，則可選擇的排序方法是＜B＞。

A.快速排序B.歸并排序C.堆排序D.直接插入排序

12.當待排序的整數是有序序列時，采用＜B＞方法比較好，其時間復雜度為

O＜n＞o

A.快速排序B.冒泡排序C.歸并排序D.直接選擇排序

13.當待排序的整數是有序序歹時，采用〔A方法比較差,達到最壞情況下時間

2

復雜度為O＜n＞o

A.快速排序B.冒泡排序C.歸并排序D.直接選擇排序

14.當待排序的整數是有序序列時，無論待排序序列排列是否有序，采用〔D方

法的時間復雜度都是0＜產＞。

A.快速排序B.冒泡排序C.歸并排序D.直接選擇排序

15.*堆是一種＜B＞排序。

A.插入B.選擇C.交換D.歸并

16.*若一組記錄的排序碼值序列為｛40,80,50,30,60,70｝,利用堆排序方法進行排

序，初建的大頂堆是＜D＞o

A.80,40,50,30,60,70B.80,70,60,50,40,30

C.80,70,50,40,30,60D.80,60,70,30,40,50

17.若一組記錄的排序碼值序列為｛50,80,30,40,70,60｝利用快速排序方法以第

一個記錄為基準,得到一趟快速排序的結果為〔Bo

A.30,40,50,60,70,80B.40,30,50,80,70,60

C.50,30,40,70,60,80D.40,50,30,70,60,80

18.*下列幾種排序方法中要求輔助空間最大的是〔C。

A.堆排序B.直接選擇排序C.歸并排序D.快速排序

19.已知A[m]中每個數組元素距其最終位置不遠，采用下列＜A＞排序方法最

節(jié)省時間。

A.直接插入B.堆C.快速D.直接選擇

20.*設有10000個互不相等的無序整數,若僅要求找出其中前10個最大整數，最

好采用〔B排序方法。

A.歸并B.堆C.快速D.直接選擇

21.*在下列排序方法中不需要對排序碼值進行比較就能進行排序的是〔A。

A：基數排序B.快速排序C.直接插入排序D.堆排序

22.*給定排序碼值序列為下力/。上八1。0舊},對其按字母的字典序列的次序

進行排列，希爾＜Shell＞排序的第一趟＜d1=5＞結果應為〔Do

A.{B,F,C,J,A,E,D,I.C,H)

B.{C,B,D,A,E,F,I,C,J,H}

C.{B,F,C,E,A,I,D,C,H,J}

D.{A,B,D,C,E,F,I,J,C,H}

23.給定排序碼值序列為化舊/。￡》,1。。1~1},對其按字母的字典序列的次序進

行排列，冒泡排序〈大數下沉》的第一趟排序結果應為〔Co

A.{B,F,C,J,A,E,D,I,C,H}

B.{C,B,D,A,E,F,I,C,J,H}

C.{B,F,C,E,A,I,D,C,H,J}

D.{A,B,D,C,E,F,I,J,C,H}

24.給定排序碼值序列為伊力小。￡分,1。。E,對其按字母的字典序列的次序進

行排列，快速排序的第一趟排序結果為〔B。

A.{B,F,C,J,A,E,D,I,C,H)

B.{C,B,D,A,E,F,I*C,J,H}

C.{B,F,C,E,A,I,D,C,H,J}

D.{A,B,D,C,E,F,I,J,C,H}

25.*給定排序碼值序列為下力/。工人,1。G巾,對其按字母的字典序列的次序

進行排列,二路歸并排序的第一趟排序結果是〔Ao

A.{B,F,C,J,A,E,D,I,C,H)

B.{C,B,D,A,E,F,I,C,J,H}

C.{B,F,C,E,A,I,D,C,H,J}

D.{A,B,D,C,E,F,I,J,C,H}

簡答題

第一章緒論

1.請分別給出數據、數據對象、數據元素、數據項的含義，并說明四者的關系。

數據〈Data〉:是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機

中并能被計算機程序處理的符號的總稱。〔一個得分點

數據元素〈DataElement》:是數據的基本單位,在計算機程序中通常作為一個整體

進行考慮和處理，相當于表中的一條記錄。（一個得分點

數據項：相當于記錄的"域"，是數據的不可分割的最小單位,如學號〔一個得分點

數據對象:性質相同的數據元素的集合,是數據的一個子集.例如：同一個班的所有

學生記錄集合。（一個得分點

關系：包含關系：數據泛指所有。數據對象是數據的一個子集，由數據元素組成，數

據元素是由數據項組成。〔一個得分點

評分標準，總共5個得分點，每段話一個得分。

2.請給出數據的邏輯結構的含義,并舉例說明數據的邏輯結構通常有哪些。

數據的邏輯結構：指數據元素之間的邏輯關系。即用自然語言描述數據,它與數據的存

儲無關，是獨立于計算機的，邏輯結構有四種。（一個得分點

集合結構：僅同屬一個集合〔結構名字0.5個得分點、舉例0.5得分點

線性結構：一對一（1:1>（結構名字0.5個得分點、舉例0.5得分點

樹結構：一對多（l：n>〔結構名字0.5個得分點、舉例0.5得分點

圖結構：多對多<m:n>〔結構名字0.5個得分點、舉例0.5得分點

評分標準：每段話一個得分點，總共5個得分點。

什么是數據的物理結構？有哪些物理結構？數據的物理結構與邏輯結構有什么區(qū)別與

聯(lián)系？

數據的物理結構：物理結構亦稱存儲結構，是數據的邏輯結構在計算機存儲器內的表示

（或映像。它依賴于計算機。（一個得分點

存儲結構可分為4大類：順序、鏈式、索引、散列。（共2個得分點，一個0.5得分點

區(qū)別：數據的邏輯結構屬于用戶視圖，是面向問題的,數據的存儲結構屬于具體實現(xiàn)的視

圖，是面向計算機的。（一個得分點

聯(lián)系：一種數據的邏輯結構可以用多種存儲結構來存儲，而采用不同的存儲結構其處理

的效率往往不同。（一個得分點

評分標準：共5個得分點,按照每段話各自標注的得分點進行評分。

3.求兩個正整數m,n中的最大數MAX的算法

[1若m>n貝!]max=m

[2若m<=n貝!|max=n

請根據上述算法解釋一下算法的組成要素有哪些，分別是什么。

算法由操作、控制結構、數據結構3要素組成

操作包含：算術運算、關系比較、邏輯運算、數據傳送（輸入、輸出、賦值〔一個得分

點

例子中有關系比較和賦值計算的操作。〔一個得分點

控制結構包含：順序結構、選擇結構、循環(huán)結構（一個得分點

例子中有選擇結構（一個得分點

數據結構：算法操作的對象是數據,數據間的邏輯關系、數據的存儲方式及處理方式就

是數據結構。〔一個得分點

本例是數值問題，涉及到兩個正整數，因此使用基本的整數類型就可以解決問題。（一個得

分點

評分標準：本題共6個得分點,每段話一個得分點。

4.簡述算法的基本性質

1輸入：0個或多個輸入

2輸出：1個或多個輸出

3有窮性：算法必須在有限步內結束

4確定性：組成算法的操作必須清晰無二義性

5可行性：組成算法的操作必須能夠在計算機上實現(xiàn)

評分標準,本題共5個得分點，每個要點一分。

5.簡述算法的設計要求

1、正確性（correctness

2、可讀性〔readability

3、健壯性（robustness

4、通用性（generality

5、效率與存儲的要求（執(zhí)行算法所耗費的存儲空間、執(zhí)行算法所耗費的時間

評分標準,本題共5個得分點，每個要點一分。

6.評價算法好壞的3條主要標準

1算法實現(xiàn)所耗費的時間。

2算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。

3算法應易于理解、易于編碼、易于調試等。

評分標準,本題共3個得分點，每個要點一分。

7.請簡述數據結構所研究的三種基本結構，以及數據元素間的關系。

線性結構：數據元素之間一對一的關系。［2分

樹形結構：數據元素之間一對多的關系。［1.5分

圖形結構：數據元素之間多對多的關系。［1.5分

8.請問算法的分析和評價的兩個標準，以及各自作用。

時間復雜度：評估算法運行所需時間。［1.5+1分

空間復雜度：評估算法運行時所需最大存儲空間。〔1.5+1分

9.請說出三種邏輯數據結構，以及他們的特點。〔5分

門線性結構：數據元素只有一個前驅數據元素和一個后繼數據元素。［2分

(2樹結構:每個數據元素只有一個前驅數據元素,可有零個或若干個后繼數據元素。(1.5

分

(3圖結構：每個數據元素可有零個或若干個前驅數據元素，零個或若干個后繼數據元

素。(1.5分

10.評價算法的主要標準是什么？

(1算法實現(xiàn)所耗費的時間〔2分

(2算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。(2分

13算法應易于理解、易于編碼、易于調試。門分

11.請說出三種邏輯數據結構，并分別畫圖表示它們。

ia,2分,b,c各1.5分

12.算法的基本性質有哪些？并簡述每個特性。＜5分〉

(1有窮性........11分

(2確定性........11分

(3可行性一一....〔1分

(4輸入性........11分

(5輸出性——....［1分

13.通常從那幾個方面來評價算法的質量？<5分〉

通常從四個方面評價算法的質量：正確性、可讀性、健壯性和高效性。（少一個扣1分

14.請描述線性數據結構的兩種存儲方式，并說出其各有什么特點。

順序存儲：連續(xù)存儲，易于定位,不易于插入和刪除。11+1.5分

鏈式存儲：非連續(xù)存儲，不易于定位，易于插入和刪除。11+1.5分

15.請問算法的分析和評價的兩種方法，它們關注點各有什么不同？〔簡單

空間效率：關注算法對內存的占用度。［1+1.5分

時間效率：關注算法的運算速度。U+L5分

第二章線性表

1.請問如果要插入一個數據到一個線性表中，順序表和鏈表哪個的效率高？為

什么？

鏈表的效率高（2分，因為順序表要移動插入位置后的每一個元素的位置給新數據騰位置

（1.5分。鏈表只需要將前一個數據的指針指向新數據并將新數據的指針指向后一個數

據即可（1.5分。

2.線性表有哪些特點？

1除第一個和最后一個數據元素外，每個數據元素只有一個前驅數據元素和一個后繼數

據元素；［2分

2第一個數據元素沒有前驅數據元素；［1.5分

3最后一個數據元素沒有后繼數據元素。（1.5分

3.順序存儲結構的優(yōu)缺點有哪些？〈中等〉

順序存儲結構的優(yōu)點：［2.5分

存儲空間連續(xù)

邏輯相鄰，物理相鄰

可隨機存取任一元素

缺點：〔2.5分

插入、刪除操作需要移動大量的元素

預先分配空間需按最大空間分配，利用不充分

表容量難以擴充

4.單鏈式存儲結構的優(yōu)缺點有哪些？〈中等〉

單鏈式存儲結構的優(yōu)點：（2.5分

不需預先分配空間,空間利用充分

插入、刪除操作簡單，無需移動大量的元素

表容量易于擴充

缺點：［2.5分

每個數據元素，除存儲本身信息外，還需空間存儲其直接后繼的信息

邏輯相鄰，物理不一定相鄰

不可隨機存取任一元素，只能從鏈表頭依次查找.

5.有順序表A=<aO,a1,22,..88?9,..總19>,要在28?9之間插入一個元素a20,

請描述其操作〈思想>步驟。〈中等〉

插入思想或步驟:根據順序表的存儲特點，要在表中某位置10插入一新數據元素,則要進

行如下兩步操作：

11、從位置10到表尾位置的所有數據元素均要從后至前依次向后移一個存儲位置，

為新插入結點騰出第10個位置。［2分

12、將新結點插入到空余位置10處。2分

〔3表長度加1.11分

6.有順序表A=<a0,a1,a2,..a8,a9,…a19>,要刪除一個元素a9,請描述其操作

(思想〉步驟。〈中等〉

門然后將從位置11到表尾的所有數據元素依次向前移一個存儲位置。［3分

〔2表長度減1.12分

7.請描述在順序表中第i個位置插入新的數據x操作過程。

根據順序表的存儲特點，要在表中某位置i插入一新數據元素，則要進行如下兩步操作：

(1從位置i到表尾位置的所有數據元素均要從后至前依次向后移一個存儲位置,為新插

入結點騰出第i個位置；［2分

(2將新數據x插入到空余位置i處。［2分

(3表長度加1.(1分

8.請描述在順序表中刪除第i個位置的數據的過程。

11然后將從位置i到表尾的所有數據元素依次向前移一個存儲位置。［3分

(2表長度減1.(2分

9.請描述在一個單鏈表中插入一個數據q的插入過程。

(1)找到將插入數據位置的前一個結點p;11分

(2)q的next值等于p的next值；(2分

(3p的next值等于q；［2分

10.請描述從一個單鏈表中刪除一個數據的刪除過程。

(1找到將被刪除數據的前一個結點P；(2分

(2p的next指針指向被刪除數據的后一個結點；(2分

(3將被刪除數據原來的next指針指向null;11分

第三章棧和隊列

1.請簡述線性表、棧和隊列三者之間的聯(lián)系。〔簡單

(1線性表、棧和隊列都屬于線性結構。［2分

(2棧和隊列都是特殊的線性表，并且都有順序存儲、鏈式存儲兩種存儲方式。(1分

(3棧是一種先進后出的線性表，隊列是一種先進先出的線性表(2分

2.在計算機進行運算時，需要把十進制轉換為二進制。請問答：這種數制轉換可

以借助于哪種數據結構實現(xiàn)、及原因。

答:棧。(2分

原因：(3分

在進行數值轉換時,其實質是求余的過程，并且余數的倒序序列正是所求結果。

棧是一種先進后出的線性結構,能夠滿足這種操作。

3.有一字符序列abcde依次按照某一線性結構存儲，請回答以下問題：

6、如果該線性結構是隊列，那么，寫出出隊序列。

〔2、如果該線性結構是棧，那么，輸出序列可能是d,c,e,a,b嗎，為什么？

［3、如果該線性結構是棧，且輸出序列是abcde。請寫出操作過程。［push<x>：表示把

X壓入棧內；pop<X>:表示把X彈出棧

答：

［1、abcde［1分

12、不可能，因為：d是第一出棧字符，說明a,b已別壓入棧內；并且壓入棧的次序為

abcde；由以上得出:ab出棧的順序只能是b、a,而不是a、b。所以，出棧序列d,c,e,a,b

是不可能的。(2分

〔3、〔2分

push<a>,pop<a>

push<b>,pop<b>

push<c>,pop<c>

push<d>,pop<d>

push<e>,pop<e>

4.簡述棧和隊列的異同點。

相同點：棧和隊列都是只允許在表的端點處進行插入、刪除操作的線性表。［2分

不同點：棧的特點是先進后出，隊列的特點是后進先出。［3分

5.若依次讀入數據元素序列1、2、3,進棧的過程中允許出棧，試寫出各種可能

的出棧序列。

答:123、132,213、231、321[各1分

6.如果入棧序列有ABC組成，請問輸出序列可能有哪些？〈較難〉

輸出序列有5種：

CBA,BCA,BAC,ACB,ABC(各1分

7.如果有abcde五個數據依次全部存入，如果采用隊列和棧來進行存儲,依次取

出分別將獲得什么內容。〔簡單

隊列:abcde(2.5分

棧:edcba(2.5分

8.設將整數1,2,3,4依次進棧，能否得到1423出棧序列和1432?并說明為什么

不能得到或者如何得到。〔中等

不能得到1423,但可以得到1432(2分

因為要得到4必須將所有數據入棧，這樣將只能依次獲取到1432不能獲得1423。采用

push、pop、push、push>push、pop、pop、pop可以獲得1432。(3分

9.循環(huán)隊列的優(yōu)點是什么？如何判斷它的空和滿？〈可不考〉

循環(huán)隊列的優(yōu)點是可以克服順序隊列的“假上溢”現(xiàn)象,能夠使存儲隊列的向量空間得到

充分的利用。(3分采用犧牲一個元素空間的方法,循環(huán)隊列隊空的條件是front==rear,

循環(huán)隊列隊滿的條件是：〈rear+l>%M==front。(2分

第四章串

1.對于字符串S='abcde',請問：〔簡單

[1字符串s的長度是多少？

12字符串S的子串有幾個,并列出所有子串？

答：

(1、511分

[2、16,11分所有字串「a'、，b，、，c，、，d'、，e，、，ab'、"be'、'

cd'、'de'、'abc'、

'bed'、'cde'、'abed'、'bcde,、'abcde?、①。[3分

2.對于字符串S='12345',請問：〔簡單

【I字符串S的長度是多少？

[2字符串S的子串有幾個,并列出所有子串？

答：

[1、511分

[2、16,11分所有字串：，V、，2，、，3，、，4，、，5，、，12，、'23，、?

34‘、'45'、'123'、

'234'、'345'、'1234'、'2345'、'12345'、①。（3分

3.請問答：什么串的模式匹配？模式匹配算法有幾種？〔簡單

答：串的模式匹配是指子串的定位運算,即在主串中查找子串第一次出現(xiàn)的位置。

模式匹配算法有兩種：簡單匹配算法<Brute-Force>、KMP算法。

〔該題共4個得分點，答對串匹配定義或大意基本相同，得2分；答對兩種匹配算，得2

分，答錯或少答一個扣1分

第五章數組和廣義表

1.在數據結構中，數組是最基本的結構，請完成以下要求：

（1、定義一個能容納5個整型元素的數組iAry,且元素的值為10、20、30、40、50。［2、*

畫出數組iAry的順序存儲結構。〔規(guī)定：整型長度為兩個字節(jié)

（1、intiAry［5］={10、20、30、40、50}〔2分

（2、如下圖：［3分，根據情況，酌情扣分

2.簡述數組的定義、特點和分類。〔簡單

定義：數組是n個相同數據類型的數據元素a0,al,a2,...,an-l構成的有限集合。（1個得分點

特點：

1數組中各元素具有統(tǒng)一的類型；（1個得分點

2數組元素的下標一般具有固定的上界和下界，即數組一旦被定義，它的維數和維界就不再改

變。［1個得分點

3數組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操

作。口個得分點

分類：按維度可分為一維數組、二維數組、多維數組（1個得分點

3.已知一個二維數組A如下所示。〔較難

（1請按照行優(yōu)先、列優(yōu)先的方式進行順序存儲，給出順序存儲的序列（2個得分點

行優(yōu)先：alla12al3a21a22a23

列優(yōu)先：alia21al2a22al3a23

12若all在內存中存儲的地址為a,每個元素的存儲空間大小為L,則按照行優(yōu)先的方式

和列優(yōu)先的方式分別存儲，其中a22的地址loc<a22>分別為多少〔2個得分點

行優(yōu)先：loc<a22>=a+4L

列優(yōu)先：Ioc<a22>=a+3L

〔3對于數組，除了順序存儲外，還有沒有其他存儲方式？沒有填無，若有，請說明。

有，鏈式存儲，如下圖所示〔1個得分點

第六章樹和二叉樹

1.有一樹，如下圖所示：〔簡單

請回答以下問題：

樹的葉子結點及其度。

(2非終端結點及其度。

門樹的深度。

答：

(1、葉子結點有：D、E、F、G,它們的度都為零。[2分

〔2、非終端結點有：A度為3,B度為2,C度為1。(2分

[3、樹的深度為3。(1分

2.請回答：樹與二叉樹有什么區(qū)別？〔中等

答：區(qū)別有兩點：

〈1〉二叉樹的一個結點至多有兩個子樹,樹則不然。[2.5分

<2>二叉樹一個結點的子樹有左右之分,而樹的子樹沒有次序。(2.5分

3.有一棵具有n個結點的滿二叉樹。請問：該滿二叉樹的葉子結點數目是多少,

答：<n+l>/2?[2分

分析過程：滿二叉樹中只有度為2和度為0的結點，故設葉子結點數目為：nO,度為2

結點數目為：n2-又由于n0=n2+l,n=n2+n0，所以可得出：n0=<n+l>/2。[3分

4.有一棵二叉樹，如下圖所示：〔簡單請問答以下問題：

11、用先序遍歷法遍歷該二叉樹，則遍歷結果是什么？

(2、用中序遍歷法遍歷該二叉樹，則遍歷結果是什么？

(3、用后序遍歷法遍歷該二叉樹，則遍歷結果是什么？

答：[1、ABDCEF

[2、DBAECF

[3、DBEFCA〈錯一個扣1.5分〉

5.請問如下二叉樹,如果采用前序'中序'后序遍歷結果是什么