第一篇：數據結構考試題目及答案

數據結構試題6

一、單項選擇題（每小題3分，共30分）

1．設棧的輸入序列是1、2、3、4，則______不可能是其出棧序列。

（）[A] 1234

[B] 2134

[C] 1432

[D] 4312

2．在一個具有n個結點的線性鏈表中查找某個結點，若查找成功，需要平均比較_____個結點。

（）[A] n

[B] n/2

[C](n+1)/2

[D](n-1)/2

3．設每個字符占一個字節，二維數組 A中每個元素有6個字符組成，其行下標從0到9，列下標從0到3，元素_____當A按行優先存儲起始地址與當A按列優先存儲的起始地址相同。

（）[A] A[3][0]

[B] A[3][1]

[C] A[3][2]

[D] A[2][3]

4．具有2000個結點的非空二叉樹的最小深度為_______。

（）[A] 9

[B] 10

[C] 11

[D] 12

5．已知某二叉樹的后根序列是dabec，中根序列是debac，則先根序列是_____。

（）[A] acbed

[B] decab

[C] deabc

[D] cedba 6.無向圖中所有邊的數目等于所有頂點的度數之和的_____倍。

（）[A] 1

[B] 2

[C] 1/2

[D] 不一定

7．遞歸函數F(n)=F(n-1)+n+1(n>1)的遞歸體是_______。

（）[A] F(0)=0

[B] F(1)=1

[C] F(n)=n+1

[D] F(n)=F(n-1)+n+1 8.若需要在O(nlog2n)的時間內完成對 n個元素的排序，且要求排序是穩定的,則可選擇的排序方法是_______。

（）[A] 快速排序

[B] 堆排序

[C] 歸并排序

[D] 直接插入排序

9．在對n個元素的序列進行排序時,堆排序所需要的附加存儲空間是__。（）

[A] O(1)

[B] O(log2n)

[C] O(n)

[D] O(n log2n)

10．假定有K個關鍵字互為同義詞，若用線性探查法把這K個關鍵字存入散列表中，則總的探查次數至少為______。

()

[A] K-1

[B] K

[C] K+1

[D] K（K+1）/22

二、填空題（每小題2分，共20分）

1．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為______，在表尾插入元素的時間復雜度為________。

2.在一棵二叉樹中，第5層(根結點為1層)上的結點數最多為____________。

3.一棵高度為h的理想平衡樹中，最少含有______個結點，最多含有________個結點。

4.在一個小根堆中，堆頂結點的值是所有結點中的_________，在一個大根堆中，堆頂結點的值是所有結點中的_________。

5.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要_________條邊。

6．假定一個圖具有n個頂點和e條邊，貝采用鄰接矩陣、鄰接表表示時，其相應的空間復雜度分別為__________和___________。

7．以二分查找方法查找一個線性表時，此線性表必須是_________存儲的________表。

8．在線性表的散列存儲中，處理沖突有___________和___________兩種方法。

9．快速排序在平均情況下的空間復雜度為_____，在最壞情況下的空間復雜度為_____。

10．在一棵20階 B_樹中，每個非樹根結點的關鍵字數目最少為_______個,最多為____。

三、判斷題（認為對的，在題后的括號內打“√”，錯的打“ⅹ”，每小題 １分，共１０）

1．線性表中，每個結點都有一個前驅和一個后繼。

（）

2．有向圖的鄰接表和逆鄰接表中的結點數一定相同。

（）

3.單鏈表中要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結構。

（）

4.在快速排序、歸并排序和shell排序中，穩定的是shell排序。

（）5.對不同的存儲結構，檢索的方法不同。

（）

6.在散列表中，負載因子值越小則存元素時發生沖突的可能性就越大。

（）

7.由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹。

（）

8.若一棵二叉樹的樹葉是某子樹對稱序周游序列中的第一個結點，則它 必是該子樹后序周游序列中的第一個結點。

（）

9.二叉樹按線索化后，任一結點均有指向其前驅和后繼的線索。

（）

10.在采用線性探查法處理沖突的散列表中，所有同義詞在表中相鄰。

（）

四、簡答題（每題10分，共60分）

1．說明數組和鏈表的區別，各有何優缺點？

2．回答下列關于堆的一些問題：

（1）堆的定義是什么？

（2）存儲表示是順序的，還是鏈式的？

（3）設有一個最小堆，其具有最小值、最大值的元素分別可能在什么地方？

3．完全二叉樹用什么數據結構實現最合適，為什么？

4.在直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排 序和歸并排序中，哪些易于在鏈表（包括各種單、雙、循環鏈表）上實現？

5．用下列三種表示法畫出下圖G的存儲結構

（1）相鄰矩陣

（2）鄰接表

（3）鄰接多重表

6．已知序列（70，83，100，65，10，32，7），請給出采用插入排序法對該序列作升序排序時的每一趟結果。

五、算法設計題（每題15分，共30分）

說明：可以使用任何高級程序設計語言或偽（類）程序設計語言。

1．已知非空單鏈表第一個結點由 list 指出，寫一算法，交換p 所指結點（不是鏈表中第一個結點,也不是鏈表中最后的那個結點）與其下一個結點在鏈表中的位置，并給出算法的時間復雜度。

2．設計一個算法，統計一個采用鄰接矩陣存儲、具有n個頂點的無向無權圖所有頂點的度。

數據結構試題6答案

一、1.D 2.C 3.B 4.C 5.D 6.C 7.D 8.C 9.A 10.D

二、1．O（n）O（1）

2．16

3．2 h 一 h 一1

4．最小值 最大值

5．n一1

6．O（n 2）O（n十e）、7．順序 有序

8．開放定址法 鏈接法（次序無先后）

9．O（1og2n）

O（n）

10．9

三、1.X

2.√

3.X 4.X

5.√

6.X

7.X

8.√

9.X

10.X

四、1．區別：數組占用連續的內存空間，鏈表不要求結點的空間連續。

各有何優缺點：（1）插入和刪除操作。數組插入和刪除需移動數據元素，鏈表插入和刪除不移動數據元素，鏈表比數組易于實現插入和刪除操作；（2）在空間占用方面，數組優于鏈表；

（3）在數據存取方面，數組是隨機存取方式，而2 鏈表是順序存取方式。2．（1）堆是 n個元素的有限序列 K1，K2，? , KN，且滿足以下條件: Ki <= K2i 且Ki <= K2i+

1I=1,2,?, n/2（最小堆）

或Ki >= K2i 且Ki >= K2i+1

I=1,2,?, n/2（最大堆）

（2）因為完全二叉樹采用順序存儲更加有效，所以堆應采用順序存儲結構。

（3）最小堆的最小值元素必在堆頂，最大值的元素只有在葉結點上。

3．完全二叉樹用一維數組實現最合適。（1）不存在空間浪費問題；（2）順序存儲方式下，父子結點之間的關系可用公式描述，訪問結點方便。采用鏈表存儲存在空間浪費問題，且不易尋找父結點。

4.在上述排序方法中，只有直接插入排序、冒泡排序、直接選擇排序易于在鏈表上實現。

5.相鄰矩陣：

鄰接表：

鄰接多重表：

6．初

始：（70），83，100，65，10，32，07 第1趟：（70，83），100，65，10，32，07 第2趟：（70，83，100），65，10，32，07 第3趟：（65，70，83，100），10，32，07 第4趟：（10，65，70，83，100），32，07 第5趟：（10，32，65，70，83，100），07 第6趟：（07，10，32，65，70，83，100）

五、算法的 ADL描述如下：

算法CHANGE(list,p)q←list

WHILE(next(q)<>p)DO

q←next(q)r←next(p)next(q)←r next(p)←next(r)next(r)←p

算法的時間復雜度為O(n)

2．假設鄰接矩陣為 adjacency（二維數組），頂點的度保存在一維數組A中。

算法的 ADL描述如下： [初始化]

FOR i=1 TO n DO A[i]←0

FOR i=1 TO n DO FOR j=1 TO n DO

IF adjacency[i,j]=1 THEN

A[i]←A[i]+1

數據結構試題7

一、單項選擇題（每小題 2 分，共 20 分）

1．序列 A,B,C,D,E 順序入棧,不能獲得的序列是:（）

A．ABCDE

B.CDEBA

C.EDCBA

D.DECAB 2.通常算法分析中算法的空間復雜度是指:（）

A.所需全部空間大小 B.完成運算所需輔助空間大小 C.待處理數據所需全部空間大小 D.存儲空間的復雜程度

3.Huffman樹是:（）

A.最佳二叉樹

B.路徑長度最短的二叉樹

C.最佳二叉排序樹 D.加權路徑長度最短的二叉樹

4.在單鏈表中刪除 P指針後的節點 Q 需要修改的指針域個數為:（）A．2

B.4

C.6

D.1

5．設 n0,n1,n2 分別是二叉樹中度為 0,1,2 的結點數,則有:（）A．n0=n2+1

B.n0=n2-1

C.n0=n1+1

D.n0=n1-1 6．下列說法中錯誤的是：（）

A.n 個結點的樹的各結點度數之和為 n-1

B.n 個結點的有向圖最多有 n*(n-1)條邊 C.用相鄰矩陣存儲圖時所需存儲空間大小與圖中邊數有關 D.散列表中碰撞的可能性大小與負載因子有關

7． 若線性表采用順序存儲結構，每個元素占用 4個存儲單元，第一個元素的存儲地址為 100，則第 12 個 元素的存儲地址是：（）A． 113

B.144 C.148 D.412

8.下列哪一種排序方法的比較次數與紀錄的初始排列狀態無關？（）A.直接插入排序 B.起泡排序 C.快速排序 D.直接選擇排序

9.設有 5000 個無序的元素，希望用最快的速度挑選出其中前 50個最大的元素，最好選用:（）

A.冒泡排序 B.快速排序 C.堆排序 D.基數排序

10.用某種排序方法對序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的 變化情況如下，則所采用的排序方法是:（）

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84

A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序

二、判斷題（每小題 1 分，共 10 分，對的打√，錯的打×）

1.給出不同輸入序列建造二叉排序樹，一定得到不同二叉排序樹。（）2.有向圖的鄰接表和逆鄰接表中的結點數一定相同。（）

3.圖 G 的拓撲序列唯一，則其弧數必為 n-1(其中 n為 G 的頂點數)。（）4.在索引順序文件中插入新的記錄時，必須復制整個文件。()

5.如果某種排序算法是不穩定的，則該方法沒有實際的應用價值。（）6.對 n 個記錄進行冒泡排序，在最壞情況下所需要的時間是 O(n 2)（）7.在線性結構中，每個結點都有一個直接前驅和一個直接后繼。（）8.AVL 樹的任何子樹都是 AVL樹。（）

9.B＋樹既適于隨機檢索，也適于順序檢索。（）

10.兩個字符串相等的充要條件是兩個串包含的字符相同。（）

三、填空題（每空 1 分，共 15分）

1．用起泡法對 n 個關鍵碼排序，在最好情況下，只需做__次比較和 _______次移動； 在最壞的情況下要做___ _ _ _次比較。

2．若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當i為_____且大于 1時，結點I 的左兄弟是結點___ _，否則結點 i 沒有左兄弟。

3．具有 N 個結點的完全二叉樹的深度為________。

4.樹的三種主要的遍歷方法是：__

__ ____、____

____和層次遍歷。

5．采用散列技術實現散列表時，需要考慮的兩個主要問題是： _____和解決_____ ___。

6．在一個帶頭結點的單循環鏈表中，p 指向尾結點的直接前驅，則指向頭結點的指針 head

可用 p 表示為 head=_______。

7．棧頂的位置是隨著_______、_________操作而變化的。

8． 已知一棵完全二叉樹中共有 768 結點，則該樹中共有_______個葉子結點。

四、簡答題（第 1、2 題每小題 6 分，第 3、4、5 題每小題 8 分，共 36 分）1．已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下圖 1 所示

(1)畫出該圖的圖形；

（2）根據鄰接矩陣從頂點 a出發進行深度優先遍歷和廣度優先遍歷,寫出相應的遍歷序列。

（圖1）

（圖2）

2．將上圖 2所示的二叉樹轉換為樹或樹林（畫出連線-刪線圖和結果圖）。

3：設有一組關鍵碼序列：

{6097,3485,8129,407,8136,6615,6617,526,12287,9535,9173,2134,1903,99} 和散列函數：H(key)=key MOD 19。采用線性探測法解決沖突，試在 0～18 的散列地址空間中對該關鍵碼序列構造散列表。

4．設有關鍵碼集合 K={72，73，71，23，94，16，05，68}，將其建成一個堆（畫出每步所 得的圖即可）。

5．從一棵空的 AVL 樹開始，將關鍵碼 xal,wan,wil,zol,yo,xum 逐個插入，畫出每插入一 個關鍵碼后得到的 AVL 樹。

五、算法設計（19 分）

用類 PASCAL語言或類 C 語言寫出將 n 個記錄用冒泡排序法進行升序排 序的算法(第一次冒泡將排序碼最小的記錄放在第一個位置，第二次冒泡將排序碼次最小的 記錄放在第二個位置 ? ?)。

數據結構試題7答案

一． 1.D 2.A

3.D

4.D

5.A

6.C

7.B

8.D 9.C 10.D 二． 1．× 2.√ 3.√ 4.× 5.× 6.√ 7.× 8.√ 9.× 10.×

三．

1． n-1 0 n(n-1)/2

2． 奇數 i-1

3． [log2N]+1

4． 先根 后根

5．選取好的散列函數 沖突（碰撞）

6． P↑.next↑.next

7． 進棧 退棧

8． 384 四．1.2、深度：a,b,d,e,c 廣度：a,b,e,d,c3、4、5、五、TYPE node=RECORD

VAR i,j:integer;

key:integer;

flag:0..1;info:datatype

X:node;END;

R:arrar[1..n] of node;FOR i:=1 TO n DO Begin flag:=0;

FOR j:=n-1 TO I DO if R[j+1].key

then 算法結束

End

數據結構試題8 一.單項選擇題(每小題 1 分,15 分)

1.編號為 A,B,C,D 的四輛列車,順序開進棧式結構的站臺,則開出車站的順序中,不可能出 現的次序為:（）

A.BDAC

B.CBAD

C.ACBD

D.DCBA 2.兩個同義詞子表結合在一起的現象稱為:（）A.碰撞 B.拉鏈 C.鏈接 D.堆積

3.一棵二叉樹若前序和對稱序周游得到的節點序列相同,則這棵二叉樹滿足:

（）A.只能是一個節點的二叉樹 B.為空二叉樹或者該樹所有節點的左子樹為空二叉樹

C.只能是空二叉樹 D.為空二叉樹或者該樹所有節點的右子樹為空二叉樹

4.一棵深度為m的滿三叉樹定義為:或者是空三叉樹,或者是第m層有3 1 ? m 個葉節點,其余 各層的節點均有三棵(左,中,右)非空子三叉樹.對該樹按層自左向右從 1 開始順序編號, 則編號為 n的節點,其父節點若存在,則父節點編號為:（）

5.有 n 個節點的有向完全圖的邊數為:（）

A.n

B.n(n-1)C.2n

D.n(n-1)/2 6.廣義表 L=(((),()),(),())的長度為:（）

A.3

B.0

C.4

D.5

7.設 H(key)為散列函數,key 為記錄的關鍵字.在散列表中,記錄 R1 和 R2 的關鍵字分別為 key 1 和 key 2 ,稱他們為同義詞的條件是:（）A.key 1 =key 2

B.key 1 =key 2 且 H(key 1)=(key 2)C.R1=R2

D.key 1 ≠ key 2 且 H(key 1)=(key 2)8.下面那一個不是存儲管理考慮的問題:（）

A.壓縮碎片問題 B.無用節點收集 C.表節點的順序 D.空間溢出管理

9.不能存儲二叉樹的存儲結構為:（）

A.三叉鏈表 B.散列表 C.順序表 D.二叉鏈表2 10．AVL 數不平衡后要調整的情形有:（）A.2 種 B.4 種 C.6 種 D.8 種

11．在排序過程序中,使用輔助存儲空間為 O（n）的算法是:（）A.插入排序 B.歸并排序 C.起泡排序 D.快速排序

12．若無向圖中有 n 個結點,e 條邊,則它的鄰接表需要表節點數目為:（）A.2e

B.2e+n

C.2e+1

D.e+2n 13．字符串的緊縮存儲形式是每個字符占:（）

A.1 個二進制位 B.1 個字節 C.1 個字 D.1 個結點單元

14．循環隊列 SQ有 m 個單元,其滿隊條件是:（）A.(SQ.rear+1)MOD M=SQ.front

B.SQ.rear=SQ.front C.SQ.rear=m

D.SQ.front=m 15．通常算法分析中算法的空間復雜度是指:（）

A.所需全部空間大小 C.完成運算所需輔助空間大小 B.待處理數據所需全部空間大小 D.存儲空間的復雜程度

二.填空題(每空1 分,共 10 分)

1.數據結構中的節點可分為兩大類:___________和___________.2.結構的____________是指數據本身所占存儲量/整個結構所占存儲量.3.散列存儲方法的關鍵問題是________________和________________.4.一棵樹刪去根節點就變成_______________.5.用二分檢索法進行檢索時,要求節點事先________________.6.設圖 G 有 n個節點,t條邊,若 d i 為節點 v i 的度數,則 t=___________.7.對于不連通的無向圖和不是強連通的有向圖進行周游,得到的是:________.8.排序方法的穩定性是指排序關鍵字值相同的記錄在排序過程中不改變其原有的 _____________關系.三．多項選擇題(錯選,多選,漏選均不得分.每小題 2 分,共 6 分)1.根據描述算法的語言不同，可將算法分為：（）

A.形式算法 B.非形式算法 C.偽語言算法3 D.運行不終止的程序可執行部分 E.運行終止的程序可執行部分

2.能夠從任意節點出發訪問到其余結點的結構有:（）A.單鏈表 B.循環鏈表 C.雙鏈表 D.二叉鏈表 E.鄰接表

3.圖的常見存儲結構可以選取:（）A．鄰接表 B.鄰接矩陣 C.逆鄰接表 D.鄰接多重表 E.散列表

四．簡答題(每小題 4 分,共 12 分)

1.快速排序算法是否穩定?舉一個具有六個記錄(只考慮排序碼)的例子予以說明.2.穿線樹的最大優點是什么? 3.簡述關鍵碼和排序碼的概念.五．分析計算題(每小題 7 分,共 21分)1.計算如下程序段的時間復雜度.??

s:=0;FOR i:=1 TO n DO BEGIN

t:=1;

WHILE t<=i DO BEGIN t:=t*2;s:=s+t END END;?

2.將上三角矩陣(a ij)n * n的上三角元素逐行存放于數組 B[1..m]中(m 充分大),使得 B[k]=a ij ,且 k=f 1(i)+f 2(j)+C,試推導出函數 f 1(i), f 2(j)和常數 C,要求 f 1(i)和 f 2(j)中不含常數項.3.關鍵碼序列{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec},按字母序號排號序為{Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep},然后用二分發進行檢索,計算在等概率條件下檢索成功的平均查找長度.六．綜合題（5+5+8+10+8）

1.分步寫出將下面樹林轉換成二叉樹的過程.2．對于下圖給出其鄰接表,并從頂點 1 出發依據存儲結構進行深度遍歷,寫出遍歷結果.3．程序填空:在橫線處填入適當的內容,將程序補充完整.程序功能:在有序表中用二分檢索法查找關鍵碼為 K的記錄,若找到則返回其位置, 找不到則返回零.類型說明如下:

TYPE node=RECORD

Key: integer;Info :datatype END;

table=ARRAY[1..n] OF node;

FUNCTION binfind(r:table;k:integer):integer;BEGIN

Low:=1;hig:=n;_______1_____

WHILE(______2_____)AND(Y=0)DO BEGIN mid : =(low+hig)DIV 2

IF k=r[mid].key THEN

y:=mid ELSE

IF k>r[mid].key THEN _____3______

ELSE _____4_______

END;Binfind:=y;END;4．修改起泡排序算法,反方向進行掃描,即第一趟把排序碼最小的記錄放到最前頭,第 二趟把排序碼次小的放到第二個位置, 第三趟把排序碼第三小的放到第三個位置, 如此反復進行.用類pascal語言給出該算法的程序.(類型說明與上面第3小題相同)

5．試編寫一個交換二叉樹T中節點的左右子樹的類PASCAL語言算法，設節點的類型為：

TYPE bitree=^node;Node=RECORD Data:datatype;Lchild,rchild:bitree END;

數據結構試題8答案

一、1、A

2、D

3、B

4、C

5、B

6、A

7、D

8、C

9、B

10、B

11、B

12、B

13、B

14、A

15、A

二、1、初等，組合

2、存儲密度

3、散列函數的選取，沖突（碰撞）的解決

4、樹（森）林

5、按關鍵碼排序 6、1/2Σdi

7、生成樹林

8、相對位置

三、1、B C E

2、B C

3、A B C D

四、1、快速排序是不穩定的如對初始類排序碼：81 2 5 82 4 1

經第一趟快排后為：〔1 2 5 82 4〕8

1經第二趟快排后為： 1 〔2 5 82 4〕81

經第三趟快排后為： 1 2 〔5 82 4〕81

經第四趟快排后為： 1 2 4 5 8

281

和 82 相對位置發生了變化

2、由于有了線索的存在而使的周游樹形結構和找結點在指定次序下的前驅、后繼的算法變

得很簡單、直截了當。

3、關鍵碼是其值能唯一確定一個記錄的字段或字段組合，兩個記錄的關鍵碼不可能相等 排序碼是排序運算的依據，是結構中的一個或多個字段，兩個記錄的排序碼可以相同

五、1、I=1 時 WHILE 循環執行 1 次

故總排序時間為：Σ[㏒ 2(i+1)]=Σ[㏒ 2i]

I=2 時 WHILE 循環執行 2 次

≈n㏒ 2 n I=3 時 WHILE 循環執行 2 次

I=4 時 WHILE 循環執行 3 次

I=5，6，7 時 WHILE 循環執行 3 次 I=8 時 WHILE 循環執行 4 次 ?

2、k=n+(n-1)+(n-2)+?+〔n-(i-2)+(j-i+1)〕

=n(i-1)-〔i+2+?+(i-1)〕+j=ni-n-(i+1)(i+2)/2+j=〔i 2 +(2n+3)i〕/2+j-(n+1)所以 f1(i)=〔i 2 +(2n+3)i〕/2;f2(j)=j;c=-(n+1)

3、檢索次數

平均查找長度為：1/12（1+2*2+3*4+4*5）=37/12

六、1、得到:

2、深度遍歷結果為：1，2，3，5，4，6，7，83、1、Y=0

2、Low≤High

3、Low：=Mid+1

4、High：=Mid-1

4、VAR

R：table;X:node;

i,j:integer;flag:0..1;

1.循環，i 以-1 為步長，從 1 到 n-1,執行(n-1 次冒泡)(1)flag ← 0

(2)循環,j以-1 為步長,從 n到 i+1 執行

若 R〔j〕.key＜R〔j-1〕.key 則 flag＜-1

x ← R〔j〕;R〔j〕← R〔j-1〕;R〔j-1〕← x(3)若 flag=0 則跳出循環

2.算法結束

5、Procedure exchange_lr_node(t:bitree);

begin

if t=nil

then 算法結束

else begin q ← t ↑.lchild;t↑.lchild←t↑.rchild;t↑.rchild←q;

exchange_lr_node(t↑.lchild);exchange_lr_node(t↑.rchild)end;end;

數據結構試題9 一.單項選擇題(每小題 1 分,15 分)1.作為一個算法必須滿足:（）

A.2 個要素 B.4 個要素 C.5 個要素 D.7 個要素

2.雙鏈表中,刪除節點 P之后的節點 Q 需要修改的指針域的個數為:（）A.1

B.2

C.3

D.4 3.隊列是一種:（）

A.鏈表 B.LIFO 表 C.順序表 D.FIFO表

4.串的求子串運算 SUBSTR(‘ABCDEF’,2,3)的引用結果是:（）A． ‘BCD’ B.‘BC’ C.‘CDE’ D.‘CD’

5.循環隊列 SQ有 m 個單元,其滿隊條件是:（）

A.SQ.rear=SQ.front

C.SQ.rear MOD M+1=SQ.front B.SQ.rear+1=SQ.front

D.SQ.rear =SQ.front MOD M+1

6.在列主序下順序的存儲數組 A 4 * 4 的上三角元素 A(3,2)的位置是第:（）A.10 個 B.7 個 C.6 個 D.5 個

7.廣義表 D=(a,D)的深度為:（）

A.2

B.1

C.+

D.–

8.有三個節點 A,B,C 可以構成多少種二叉樹:（）A.5

B.8

C.32

D.30 9.有 n 個節點的完全二叉樹,其深度為:（）

10.中序序列和后序序列相同的二叉樹是:（）

A.完全二叉樹

B.滿二叉樹

C.所有結點無左孩子的二叉樹 D.所有結點無右孩子的二叉樹

11.若有向圖中有 n 個結點,e 條邊,則它的鄰接表需要表節點數目為:（）A.e

B.2e

C.e-1

D.e+1

12.克魯斯卡爾(KRUSKAL)算法求最小生成樹,是針對那種圖的:（）A.無向圖 B.有向圖 C.連通無向圖 D.連通帶權圖

13.在排序過程中,使用輔助空間為 O（n）的算法是:（）A.插入法 B.歸并法 C.快速 D.分配

14.在散列結構中,同義詞是指:（）

A.R1.KEY≠R2.KEY 且 HASH(RI.KEY)=HASH(R2.KEY)

B.R1.KEY=R2.KEY

C.R1.KEY=R2.KEY 且 HASH(RI.KEY)=HASH(R2.KEY)

D.R1.DATA=R2.DATA 15.ISAM 文件屬于:（）

A.順序文件 B.散列文件 C.索引文件 D.多關鍵字文件

二.多項選擇題(錯選,多選,漏選均不得分.每小題 1 分,共 5 分)1.在下列算法中,涉及到棧運算的有:（）

A.二叉樹的遍歷 B.廣度優先搜索遍歷 C.深度優先搜索遍歷

D.表達式求值 E.基數排序

2.排序算法在最壞執行情況下,算法的時間復雜度是 O(n 2)的有:（）A.插入排序法 B.塊序排序法 C.堆排序法 D.歸并排序法 E.基數排序法

3.稀疏矩陣通常采用的存儲方式有:（）

A.單鏈表 B.循環鏈表 C.三元組表 D.散列表 E.十字鏈表

4.根據排序期間數據規模的大小及數據所處存儲器的不同,可以將排序分為:()A.插入排序 B.希爾排序 C.交換排序 D.內部排序 E.外部排序

5.能夠從任一節點訪問到其余節點的結構有:（）

A.單鏈表 B.循環鏈表 C.雙鏈表 D.二叉鏈表 E.鄰接表

三.填空題(每空1 分,共10 分)

1.數據的基本存儲結構有_________,________,_________,________四種.2.排序方法的穩定性是值排序關鍵字值相同的記錄在排序過程中不改變其原有的 _____________關系.3.算法的確定性是指每條__________________.4.散列結構中處理沖突的方法基本上可分為兩大類: __________和_________.5.文件的操作主要有:___________和__________兩類.四.判斷改錯題(對的打”√”,錯的打”╳”,并說明理由.每小題 2 分,判斷和說明各得 1 分,判斷3 錯誤,全題無分.共 10分)

1.二叉樹是度為 2 的樹.（）2.堆排序是不穩定的,其時間復雜度為 O(n log 2 n).（）3.隊列是受限的線性表,限制在于節點的位置相對固定.（）4.要完成樹的層次遍歷一般要利用棧作為輔助結構.（）5.圖的最小生成樹如果存在,則一般唯一.（）五.解釋概念題(每小題 3 分,共 9 分)1.三元組表 2.拓撲排序 3.AVL樹

六.簡答題(共 31分)

1.把下圖森林轉化為一棵二叉樹,并畫出主要轉化過程圖示.(4 分)

2.給定權集 W={2,3,4,7,8},試構造關于 W 的一棵哈夫曼樹,并求其加權路徑長度 WPL 的 值.(6 分)

3.對于下圖給出其鄰接表,并從頂點 1 出發依據存儲結構進行廣度遍歷,寫出遍歷結果.4.有一棵二叉樹其前序序列為 ABCDEF,中序序列為 BCAEDF,畫出此二叉樹的示意圖,并給 出其后序序列的線索樹.(6 分)

5.對于關鍵字集合{51,28,36,86,7},請建立一個堆,要求畫出堆形成的示意圖.(6 分)

6.在雙鏈表H中,現在要在節點P之后插入一個節點Q,請寫出插入動作的具體語句.(4分)七.算法設計（共20 分）

1.數組 A[1..m]作為循環隊列的存儲區域,試編寫一個出隊的類 PASCAL 語言算法.(6 分)2．利用類 pascal 語言寫出統計二叉樹中節點個數的算法（6 分）.3．利用類 pascal 語言寫出快速排序中一趟塊排的算法（8 分）.數據結構試題9答案

一、1、C

2、B

3、D

4、A

5、D

6、B

7、C

8、D

9、A

10、D

11、A

12、D

13、B

14、A

15、C

二、1、A C D

2、A B

3、A C D E

4、D E

5、B C

三、1、順序,鏈接,索引,散列

2、相對位置

3、指令必須有確切含義,無歧義性

4、開地址法,拉鏈法

5、修改,檢索

四、1、×

2、√

3、×

4、×

5、×

五、1、三元組表 P244

2、拓撲排序 P229

3、AVL樹 P180

六、3、鄰接表存儲表示同 A 卷

六、2 廣度遍歷結果:1, 2, 6, 3, 4, 7, 8, 5

4、后序:C B E F D A 5、6、q↑.llink←p

q↑.rlink←p↑.rlink p↑.rlink↑.llink←q p↑.rlink←q

七、算法設計(6+6+8=20′)1、1.if

R=F

then

print(‘underflow’)else

F←F MOD m+1

算法結束

2、TYPE

pointer=↑node

node=RECORD info: datatype;llink, rlink: pointer END VAR

t: pointer;

Count: integer;進入算法時,二叉樹已用二叉鏈表存儲,t指向根結點,count初值為 0 Procedure node_Count(t: pointer;VAR count: integer);begin if t=nil

then 算法結束

else

begin count:=count+1;node_count(t↑.llink,count);node_count(t↑.rlink,count)end end;

3、TYPE node=RECORD Key: integer;Info: datatype End;

List=ARRAP〔1..N〕OF node;VAR X:node;j:0..n;

Procedure quickpass(VAR R:list;l,r:integer;VAR i:integer);begini:=l;j:=r;x:=R〔i〕;repeatwhile(R〔i〕.key＞=x.key)and(i＜j＝doj:=j-1;if i＜j then

R〔j〕:=R〔j〕;i:=i+1;

while(R〔i〕.key＜=x.key＝and(i＜j＝do i:=i+1;if i＜j then 〔R〔j〕:= R〔i〕;j:=j-1〕 until i=j R〔i〕:=x end

注:整個快速排序 Procedure quicksort(VAR R:list;s,t:integer);Begin If s＜t Then 〔quickpass(R,s,t,i);quicksort(R,s,i-1);quicksort(R,i+1,t)〕

end;

數據結構試題10 一.單項選擇題(每小題 1 分,共 20分)

1.設n為正整數,以下程序段的執行次數是:

（）

k:=0;s:=1;REPEAT s:=s+k;k:=k+1 UNTIL(k=-n)

A.(2n+3)次

B.2(n+1)次

C.無限多次

D.1 次

2.序列 A,B,C,D,E 順序入棧,不能獲得的序列是:

（）

A.ABCDE

B.CDEBA

C.EDCBA

D.DECAB

3.數據結構的內容包括:

（）A.三層次五要素

C.五層次三要素

B.三層次三要素

D.五層次五要素

4.在雙鏈表中要在 p 所指的結點后插入一個新結點q,要修改的指針域個數為:（）

A.2 個

B.4 個

C.6 個

D.8 個

5.在列主序下順序的存儲數組 A 4 * 4 的下三角元素 A(3,2)的位置是第:

（）

A.5 個

B.6 個

C.7 個

D.10 個

6.n 個結點順序存儲的完全二叉樹, i(1

7.對任何二叉樹,設 n0,n1,n2 分別是度數為 0,1,2的結點數,則有:

（）

A.n0=n2+1

B.n0=n2-1

C.n0=n1+1

D.n0=n1-1

8.對圖(一)的二叉樹,其后續遍歷結果為:

（）

圖

（一）A.ABDCEF

B.ABCDEF

C.DBAECF

D.DBEFCA

9.結點可以排在拓撲序列中的圖是:

（）

A.無向圖

B.有向圖

C.有向無環圖

D.無向有環圖

10.串的求子串運算 SUBSTR(‘ABCDEFGH’,4,5)的引用結果是:

（）

A.‘DE’

B.‘DEFGH’

C.‘EFGH’

D.‘BCDE’

11.對于記錄R1,R2其健值分別是K1和K2,數據為D1和D2,稱R1和R2是同義詞的條件是

（）

A.K1=K2

C.K1=K2且 H(K1)≠H(K2)B.D1=D2

D.K1≠K2 且 H(K1)=H(K2)

12.快速排序屬于:

（）A.插入排序

B.交換排序

C.選擇排序

D.歸并排序

13.AVL 數不平衡后要調整的情形有:

（）

A.2種

B.4 種

C.6 種

D.8 種

14.PRIM 算法是求圖的:

（）

A.連通分量

B.最短路徑

C.最小生成樹

D.拓撲序列

15.在排序過程序中,使用輔助存儲空間為 O（n）的算法是:

（）

A.插入排序

B.歸并排序

C.起泡排序

D.快速排序

16.若無向圖中有 n 個結點,e 條邊,則它的鄰接表需要表節點數目為:

（）

A.2e

B.2e+n

C.2e+1

D.e+2n

17.字符串的緊縮存儲形式是每個字符占:

（）A.1 個二進制位

B.1 個字節

C.1 個字

D.1 個結點單元

18.循環隊列 SQ有 m 個單元,其滿隊條件是:

（）

A.(SQ.rear+1)MOD M=SQ.front

C.SQ.rear=m B.SQ.rear=SQ.front

D.SQ.front=m

19.VSAM 文件屬于:

（）

A.順序文件

B.散列文件

C.多關鍵字文件

D.索引文件

20．下列說法中錯誤的是：

（）

B.n 個結點的有向圖最多有 n*(n-1)條邊

C.用相鄰矩陣存儲圖時所需存儲空間大小與圖中邊數有關

D.散列表中碰撞的可能性大小與負載因子有關

二.多項選擇題(錯選,多選,漏選均不得分,每小題 2 分,共 14 分)

1.根據描述算法的語言不同，可將算法分為：

（）

A.形式算法

B.非形式算法

C.偽語言算法

D.運行終止的程序可執行部分

E.運行不終止的程序可執行部分

2.圖的常見存儲結構可以選取:

（）A.鄰接表

B.鄰接矩陣

C.逆鄰接表

D.鄰接多重表

E.散列表

3.在下列算法中,涉及到棧運算的有:

（）

A.二叉樹遍歷

B.廣度優先搜索

C.深度優先搜索 D.構造哈夫曼樹

E.表達式求值算法

4.某表組織如下:將元素均勻的分成塊,塊內元素不排序,塊之間排序,則查找塊及塊內某元素實施的方法是:

（）A.折半查塊 順序查元素

B.順序查塊 順序查元素

C.順序查塊 折半查元素 D.散列法查找數據元素

E.折半查塊 折半查元素

5.能夠從任意節點出發訪問到其余結點的結構有:

（）

A.單鏈表

B.循環鏈表

C.雙鏈表

D.二叉樹表

E.散列表

6.數據的邏輯結構與:

（）

A.數據元素本身的形式,內容有關

B.數據元素本身的形式,內容無關

C.數據元素的相對位置有關

D.數據元素的相對位置無關

E.所含節點個數無關

7.稀疏矩陣通常采用的存儲方式有:

（）

A.單鏈表

B.循環鏈表

C.三元組

D.散列表

E.正交表

三.判斷說明題(對的打”√”,錯的打”╳”,并說明理由.判斷和說明各得 1 分,判斷錯誤,全題無分.共 10 分)

1.在隊列中,新插入的結點只能插到隊頭.（）2.二叉樹是度數最大為2 的樹.（）3.在哈希表中,相同的關鍵字散列在不同的地址空間上的現象稱為沖突.（）4.堆排序是不穩定的,其時間復雜度為:O(n log2n).（）5.完成樹的深度遍歷一般要利用隊列作為輔助結構.（）四.解釋概念題(每小題 4 分,共 12分)1.AVL 樹

2.稀疏矩陣

3.哈夫曼樹 五.簡答題(每小題 5 分,共 20 分)1.將圖(二)所示二叉樹轉化成森林.圖(二)

圖

（三）2.什么是串的壓縮存儲(緊縮格式)? 他有哪些優缺點?

3.已知圖G如圖(三)所示,給出其鄰接表,并寫出從1出發進行深度優先和廣度優先遍歷的

結果.4.輸入關鍵字序列:xal,wan,wil,zdl,yo,xul,yum,試建立建立一棵最佳二叉排序樹.六.綜合應用(每小題 12 分,共 24 分)

1.利用類 pascal 語言寫出統計二叉樹中節點個數的算法.2.利用類 pascal 語言寫出直接選擇排序的算法.數據結構試題10答案

一、1、C

2、D

3、A

4、B

5、C

6、A

7、C

8、A

9、D

10、C

11、B

12、D

13、B

14、B

15、C

16、B

17、B

18、B

19、A 20、D

二、1、B C D

2、A B C D

3、A C E

4、A B

5、B C

6、B D E

7、A C D E或 C D E

三、1、× 對尾

2、× 二叉數不是樹的特例

3、× 不同,相同

4、√

5、× 不含任何字符,空白字符

四、1、AVL 樹

2、稀疏矩陣

3、哈夫曼樹

五、1、2、盡可能將串中多個字符存入同一單元的存儲方式,其優點是節省存儲空間,缺點是對某些運算時間加長.3、深度優先：1，2，4，5，3，6，7 廣度優先：1，2，3，4，5，6，7

4、六、1、TYPE pointer=↑node node=RECORD

info: datatype;llink,rlink: pointer end;

進入算法時，二叉樹用二叉鏈表存儲。Count 初值為0 Procedure

Count_node(t: pointer;VAR Count: integer);begin

If t≠nil then begin

Count:=Count+1;Count_node(t↑.llink,Count);Count_node(t↑.rlink,Count)end end;

2、TYPE node=RECORD

key: integer;info: datatype end;

list: ARRAY〔1..n〕OF node VAR x: node;j: 0..n;以下略

第二篇：考試題目及答案

意外門診：理賠申請書

發票原件

診斷證明書

門診病歷、處方

本人事故經過（團單：單位意外事故證明）身份證、銀行卡或存折、保單復印件

疾病住院：理賠申請書

發票原件

診斷證明書

病案一套

總費用明細清單

身份證、銀行卡或存折、保單復印件

（津貼：體溫記錄）

意外住院：理賠申請書

發票原件

診斷證明書

病案一套

總費用明細清單

意外事故經過（團單：單位意外事故證明）身份證、銀行卡或存折、保單復印件

（津貼：體溫記錄）

意外身故：理賠申請書

醫學死亡證明或派出所死亡證明

戶口注銷證明

火化證明或土葬證明

醫院搶救記錄及相關材料

身份證及戶口本復印件

所有法定第一順序受益人戶口本、身份證復印件受益人確認書

受益人銀行卡或存折復印件

意外事故經過（團單：單位意外事故證明）保單復印件

（交通事故：交通事故認定書、行駛證、駕駛證）

疾病身故：理賠申請書

醫學死亡證明或派出所死亡證明

戶口注銷證明

火化證明或土葬證明

醫院搶救記錄及相關材料

身份證及戶口本復印件

所有法定第一順序受益人戶口本、身份證復印件

受益人確認書

受益人銀行卡或存折復印件

保單復印件

非被保險人遞交材料：授權委托書（被保險人）、被授權人身份證復印件

另外：

理賠款打入單位賬戶的，需提供：理賠款支付聲明（單位出具）、個人委托聲明（被保險人）

第三篇：考試題目及答案

考試題目及答案

一、單項選擇題 1、2013年11月9日到12日，中共十八屆三中全會在北京召開，這次全會的主題是（A）。

A、全面深化改革

B、全面深化開放

C、全面改革開放

D、全面深化改革開放 2、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出面對十分復雜的國際形式和艱巨繁重的國內改革發展穩定任務，中央政治局全面貫徹黨的十八大精神，高舉中國特色社會主義偉大旗幟，以鄧小平理論、“三個代表”重要思想、科學發展觀為指導，團結帶領全黨全軍全國各族人民，堅持的工作總基調是（A）。

A、穩中求進

B、提質增效

C、又快又好

D、多快好省 3、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出面對十分復雜的國際形式和艱巨繁重的國內改革發展穩定任務，中央政治局全面貫徹黨的十八大精神，高舉中國特色社會主義偉大旗幟，以鄧小平理論、“三個代表”重要思想、科學發展觀為指導，團結帶領全黨全軍全國各族人民，著力（A）。

A、穩增長、調結構、促改革

B、調增長、穩結構、促改革

C、穩增長、促結構、調改革

D、促增長、調結構、穩改革 4、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全面深化改革，必須高舉中國特色社會主義偉大旗幟，以馬克思列寧主義、毛澤東思想、鄧小平理論、“三個代表”重要思想、科學發展觀為指導，堅定信心、凝聚共識，統籌謀劃，協同推進，堅持社會主義市場經濟改革方向，以（C）出發點和落腳點。A、為人民服務

B、立黨為公、執政為民

C、為促進社會公平正義、增進人民福祉

D、權為民所用、利為民所謀、情為民所系 5、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全面深化改革的總目標是（D）。

A、實現中國夢

B、全面建立社會主義市場經濟體制

C、實現和完成社會主義四個現代化建設

D、完善和發展中國特色社會主義制度，推進國家治理體系和治理能力現代化6、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全會指出，深化經濟體制改革要緊緊圍繞使市場在資源配置中起（B）。

A、基礎性作用

B、決定性作用

C、關鍵性作用

D、核心性作用 7、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全會指出，全面深化改革，必須立足于我國長期處于社會主義初級階段這個最大實際，解決我國所有問題的關鍵是（B）。

A、堅持創新

B、堅持發展

C、堅持改革

D、堅持開放 8、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全面深化改革的重點是（B）。

A、政治體制改革

B、經濟體制改革

C、文化體制改革

D、社會體制改革 9、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出指出，經濟體制改革是全面深化改革的重點，核心問題是（B）。A、處理好政府和市場的關系，使政府在資源配置中起決定性作用和更好發揮市場作用

B、處理好政府和市場的關系，使市場在資源配置中起決定性作用和更好發揮政府作用

C、處理好政府和市場的關系，使政府在資源配置中起基礎性作用和更好發揮市場作用

D、處理好政府和市場的關系，使市場在資源配置中起基礎性作用和更好發揮政府作用 10、2013年11月12日，中共十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》提出，國家治理的基礎和重要支柱是（B）。

A、稅收

B、財政

C、科技

D、經濟

二、多項選擇題

1、黨的十一屆三中全會召開三十五年來，我們黨以巨大的政治勇氣，銳意推進經濟體制、政治體制、文化體制、社會體制、生態文明體制和黨的建設制度改革，不斷擴大開放，決心之大、變革之深、影響之廣前所未有，成就舉世矚目。下列對于改革開放的說法，正確的有（ABC)。

A、改革開放是黨在新的時代條件下帶領全國各族人民進行的新的偉大革命，是當代中國最鮮明的特色

B、改革開放最主要的成果是開創和發展了中國特色社會主義，為社會主義現代化建設提供了強大動力和有力保障。

C、改革開放是決定當代中國命運的關鍵抉擇，是黨和人民事業大踏步趕上時代的重要法寶。

D、改革不是對原有制度作細枝末節的修改，而是要對已經建立的制度作根本性變革

2、十八屆三中全會強調，全面深化改革，必須高舉中國特色社會主義偉大旗幟，以馬克思列寧主義、毛澤東思想、鄧小平理論、“三個代表”重要思想、科學發展觀為指導，堅定信心，凝聚共識，統籌謀劃，協同推進，堅持社會主義市場經濟改革方向，以促進社會公平正義、增進人民福祉為出發點和落腳點，進一步(BCD)。

A、解放市場 B、解放思想 C、解放和發展社會生產力 D、解放和增強社會活力

3、十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全面深化改革的總目標是(C D)。

A、到建黨100周年，建成全面小康社會

B、到建國100周年，實現現代化，實現中華民族偉大復興

C、完善和發展中國特色社會主義制度

D、推進國家治理體系和治理能力現代化

4、十八屆三中全會通過的《中共中央關于全面深化改革若干重大問題的決定》指出全面深化改革的總目標是完善和發展中國特色社會主義制度，推進國家治理體系和治理能力現代化，必須更加注重改革的(ABC)。

A、系統性 B、整體性 C、協同性 D、全面性

5、十八屆三中全會指出，要緊緊圍繞使市場在資源配置中起決定性作用深化經濟體制改革，要緊緊圍繞堅持黨的領導、人民當家作主、依法治國有機統一深化政治體制改革以外，除此，還要緊緊圍繞(ABCD)。

A、建設社會主義核心價值體系、社會主義文化強國深化文化體制改革

B、更好保障和改善民生、促進社會公平正義深化社會體制改革

C、建設美麗中國深化生態文明體制改革

D、提高科學執政、民主執政、依法執政水平深化黨的建設制度改革

6、十八屆三中全會指出，全會要求，到2020年，要(ABD)。

A、在重要領域和關鍵環節改革上取得決定性成果

B、形成系統完備、科學規范、運行有效的制度體系

C、實現現代化，實現中國夢

D、使各方面制度更加成熟更加定型。

7、十八屆三中全會指出，改革開放的成功實踐為全面深化改革提供了重要的經驗，必須長期堅持。最重要的是，堅持（ABCD)。

A、黨的領導，貫徹黨的基本路線，不走封閉僵化的老路，不走改旗易幟的邪路，堅定走中國特色社會主義道路，始終確保改革正確方向

B、解放思想、實事求是、與時俱進、求真務實，一切從實際出發，總結國內成功做法，借鑒國外有益經驗，勇于推進理論和實踐創新

C、以人為本，尊重人民主體地位，發揮群眾首創精神，緊緊依靠人民推動改革，促進人的全面發展

D、政府處理改革發展穩定關系，膽子要大、步子要穩，加強頂層設計和摸著石頭過河相結合，整體推進和重點突破相促進，提高改革決策科學性，廣泛凝聚 共識，形成改革合力

8、十八屆三中全會指出，公有制經濟和非公有制經濟都是社會主義市場經濟的重要組成部分，都是我國經濟社會發展的重要基礎。必須(ABCD)。

A、毫不動搖鞏固和發展公有制經濟，堅持公有制主體地位，發揮國有經濟主導作用，不斷增強國有經濟活力、控制力、影響力

B、毫不動搖鼓勵、支持、引導非公有制經濟發展，激發非公有制經濟活力和創造力

C、完善產權保護制度，積極發展混合所有制經濟

D、推動國有企業完善現代企業制度，支持非公有制經濟健康發展

9、十八屆三中全會指出，科學的宏觀調控，有效的政府治理，是發揮社會主義市場經濟體制優勢的內在要求。必須(ABCD)。

A、切實轉變政府職能，深化行政體制改革

B、創新行政管理方式，增強政府公信力和執行力

C、建設法制政府和服務型政府

D、要健全宏觀調控體系，全面正確履行政府職能，優化政府組織結構，提高科學管理水平

10、十八屆三中全會指出，堅持用制度管權管事管人，讓人民監督權力，讓權力在陽光下運行，是把權力關進制度籠子的根本之策。必須(ＡＢＣＤ)。

A、構建決策科學、執行堅決、監督有力的運行體系

B、健全懲治和預防腐敗體系，建設廉潔政治，努力實現干部清正、政府清廉、政治清明

C、形成科學有效的權力制約和協調機制

D、加強反腐敗體制機制創新和制度保障，健全改進作風常態化制度

三、判斷題

1、十八屆三中全會指出，全面深化改革，堅持發展仍是解決我國所有問題的關鍵這個重大戰略判斷，以經濟建設為中心，發揮經濟體制改革牽引作用，推動生產關系同生產力、上層建筑同經濟基礎相適應，推動經濟社會持續健康發展。必須立足于我國的這個最大實際是我國長期處于社會主義初級階段(√)。

2、我國社會主義民主政治的特有形式和獨特優勢，是黨的群眾路線在政治領域的重要體現，是基層民主(×)。

3、黨的十八屆三中全會明確指出，全面深化改革的總目標是：完善和發展中國特色社會主義制度，推進國家治理體系和治理能力現代化。（√）

4、中國夢的本質內涵是國家富強、民主發展、人民幸福。（×）

5、國家治理體系指的是國家在治理經濟、政治、文化、社會、生態等形成的制度體系。（√）

第四篇：考試題目及答案

1、某制劑生產線項目，其項目固廢污染防治措施應重點關注的問題?? 答：典型制劑生產線項目產生的固體廢物，主要為少量的廢棄包裝材料和碎玻璃瓶。同時，應關注藥品分裝企業潔凈廠房空氣凈化系統定期更換的活性炭纖維等空氣過濾介質。

（1）首先關注包裝及貯存場所污染防治措施：根據固體廢物產生量、轉運周期、貯存期限等分析、判斷固體廢物貯存場所的面積是否滿足貯存需求。根據《一般工業固體廢物貯存、處置場污染控制標準》（GB18599-2001）、《危險廢物貯存污染控制標準》（GB18597-2001）等規定要求，評價各類固體廢物是否按照相關要求分類收集貯存，包裝容器是否符合規定、固體廢物貯存場所建設是否達到國家相關標準規定要求。

（2）重點關注固廢污染防治措施的技術先進性、經濟合理性及運行可靠性，特別是廢棄包裝材料等危險廢物的處理處置方式，嚴格執行危險廢物轉移聯單制度，對危險廢物轉移進行全過程的管理。另外，改擴建及異地搬遷項目需說明現有工程固體廢物特別是危險廢物的處置措施情況、存在的環境保護問題及擬采取的整改措施等內容。

2、重大危險源辨識是環境風險評價中的重要內容之一，試說明其目的和基本方法?? 答：（1）目的：通過對重大危險源進行辨識，可以確定哪些是可能發生事故的潛在危險源。重大危險源總是涉及到易燃、易爆、有毒的危害物質，并且在一定范圍內使用、生產、加工、儲，存超過了臨界數量的這些物質。控制重大危險源不僅僅可以預防重大事故的發生，而且一旦發生事故，能夠將事故限制到最低程度，或者說能夠控制到人們可接受的程度。對重大危險源進行辨識后，對項目進行風險評價。

（2）基本方法：通過分析廠內長期或臨時生產、加工、運輸、使用或貯存的危險物質，包括毒性物質、易燃物質以及爆炸性物質等，生產場所最大存在量、廠內最大貯存量以及綜合量，對比《重大危險源識別》（GB18218-2009）和《建設項目環境風險評價技術導則》（HJ/T169-2004）中規定的臨界量，判斷如下： ①單元內存在的危險化學品為單一品種，則該危險化學品的數量即為單元內危險化學品的總量，若等于或超過相應的臨界量，則定為重大危險源。②單元內存在的危險化學品為多品種時，則按下式計算，若滿足下式，則定為重大危險源：

q1/Q1+q2/Q2+…+qn/Qn≧1 式中： q1，q2，…，qn———每種危險化學品實際存在量，單位為噸（t）； Q1，Q2，…，Qn———與各危險化學品相對應的臨界量，單位為噸（t）。

3、石化項目地下水污染防滲分區的原則是什么？舉例說明污染防治分區?? 答：1.原則：將石化項目廠區是否為隱蔽工程、發生物料泄漏是否容易發現和能否及時得到處理作為防滲分區的原則。2.通常將石化企業廠區劃分為：

（1）重點污染防治區，指對地下水環境有污染的物料或污染物泄漏后，不能發現和處理的區域或部位，為隱蔽工程區。如埋地管道、地下容器、儲罐及設備，（半）地下污水池、油品儲罐的罐基礎等，這些區域或部位一旦出現設備腐蝕穿孔、地基下陷造成管道變形、罐基礎變形等情況，就會發生物料或污染物泄漏，滲入土壤并最終進入地下水，從而對地下水環境造成污染。

（2）一般污染防治區，指對地下水環境有污染的物料或污染物泄漏后，容易發現和可及時處理的區域或部位，為裸露工程區。如架空設備、容器、管道，地面明溝等，這些設備、區域發生損壞，造成物料或污染物泄漏后，可及時被發現或發出報警，泄漏出來的物料和污染物短時間內會聚集在地面上，采取緊急處理措施后，不會大量滲入土壤對地下水環境造成污

染。（3）非污染防治區，指沒有污染物泄漏或泄漏物不會對地下水環境造成污染的區域或部位。主要包括石化企業的管理區、集中控制區等輔助區域，石化企業裝置區以外系統管廊區（除系統管廊集中閥門區的地面外）的地面和雨水明溝（長期處于無水狀態）等。

第五篇：數據結構試題及答案

數據結構試卷

（二）一、選擇題(24分)1．下面關于線性表的敘述錯誤的是（）。

(A)線性表采用順序存儲必須占用一片連續的存儲空間

(B)線性表采用鏈式存儲不必占用一片連續的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(D)線性表采用順序存儲便于插入和刪除操作的實現

2．設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。

(A)2m-1(B)2m(C)2m+1(D)4m 3．設順序循環隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數為（）。

(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。

(A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。

(A)n(n-1)/2(B)n(n-1)(C)n

2(D)n2-1 6．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（）。

(A)9(B)10(C)11(D)12 7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（）個表頭結點。

(A)n-1(B)n(C)n+1(D)2n-1 8．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（）。

(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8

二、填空題(24分)1.1.為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。

2.2.下面程序段的功能實現數據x進棧，要求在下劃線處填上正確的語句。

typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);

else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。5.5.設某棵二叉樹中度數為0的結點數為N0，度數為1的結點數為N1，則該二叉樹中度數為2的結點數為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。

6.6.設某無向圖中頂點數和邊數分別為n和e，所有頂點的度數之和為d，則e=_______。

7.7.設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。

v1??3??2??4v2??1??3v3??1??4??28.8.設某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優先遍歷序列為___________；廣度優先遍歷序列為____________。

三、應用題(36分)1． 1． 設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。

2． 2． 設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。

3． 3． 設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關鍵字62時的比較次數并計算出查找成功時的平均查找長度。

4． 4． 設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5． 5． 設有無向圖G（如右圖所示），要求給出用普里姆算法構造最小生成樹所走過的邊的集合。

6． 6． 設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給出構造過程。

數據結構試卷

（二）參考答案

一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空題

1.1.構造一個好的HASH函數，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序

4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4)

三、應用題

1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈式存儲結構略，二叉樹略

5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略

數據結構試卷

（三）一、選擇題(30分)1．設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是（）。

(A)線性結構(B)樹型結構(C)物理結構(D)圖型結構 2．下面程序的時間復雜為（）

for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（）。

(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C)q=p->next；p->next=q->next；free(q)；

(D)q=p->next；p->data=q->data；free(q)；

4．設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。

(A)1(B)n(C)nlog2n(D)n2

5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（）。

(A)n，e(B)e，n(C)2n，e(D)n，2e 8.設某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。

(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。

(A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復雜度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

二、填空殖(48分，其中最后兩小題各6分)1.1.數據的物理結構主要包括_____________和______________兩種情況。

2.2.設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有___________個空指針域。

3.3.設輸入序列為1、2、3，則經過棧的作用后可以得到___________種不同的輸出序列。

4.4.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。

5.5.設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。6.6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為_________。

7.7.__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。

8.8.設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。

9.9.不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。

10.10.設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。11.11.設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。

12.12.設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。

13.13.下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。

struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}

if(_______________________)return(j);else return(-1);} 14.14.下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。

typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){

if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;}

數據結構試卷

（三）參考答案

一、選擇題

1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。

第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。

二、填空題

1.1.順序存儲結構、鏈式存儲結構 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。

}

數據結構試卷

（四）一、選擇題(30分)1．設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。

(A)2k-1(B)2k(C)2k-1(D)2k-1 3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。

(A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結點的時間復雜度為（）。

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。

(A)n(B)n-1(C)m(D)m-1 6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。

(A)3(B)4(C)5(D)8 7．設用鏈表作為棧的存儲結構則退棧操作（）。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復雜度最大。

(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

9．設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過（）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空題(42分)1． 1． 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。

2． 2． 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X需要執行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。3． 3． 根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結點。5． 5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。

6． 6． 設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。

7． 7． 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。

8． 8． 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_______個數據元素；刪除第i個位置上的數據元素需要移動表中_______個元素。9． 9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。

10．10．設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據這些初始關鍵字序列建成的初始堆為________________________。

11．11．設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。

12．12．設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數_________第i列上非0元素的個數（填等于，大于或小于）。

13．13．設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。

14．14．設散列函數H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。

typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;ikey=a[i];k=a[i] % p;s->next=hashtable[k];_______________________;} }

數據結構試卷

（四）參考答案

一、選擇題

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空題

1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s

數據結構試卷

（五）一、選擇題(30分)

1．數據的最小單位是（）。

(A)數據項(B)數據類型(C)數據元素(D)數據變量

2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數substr(“DATASTRUCTURE”，5，9)的返回值為（）。

(A)“STRUCTURE”(B)“DATA”

(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，……，度數為m的結點數為Nm，則N0=（）。

(A)Nl+N2+……+Nm

(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm

7．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。

(A)25(B)10(C)7(D)1 8．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（）。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設輸入序列是1、2、3、……、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。

(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80

二、填空題(共30分)1.1.設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。

2.2.在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是____________________。

3.3.設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續的存儲單元中，則A[i][j]與A[0][0]之間有_______個數據元素。

4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。

5.5.設一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。

6.6.設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。

7.7.設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之和等于頂點i的________，第i列中所有非零元素個數之和等于頂點i的__________。

8.8.設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。

9.9.下面程序段的功能是實現冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實現二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){

int low=0,mid,high=n-1;

while(low<=high){

________________________________;

if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;

}

return(0);}

三、應用題(24分)

1.1.設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。

3.3.設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。

4.4.設散列表的長度為8，散列函數H(k)=k mod 7，初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

數據結構試卷

（五）參考答案

一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C

二、填空題

1.1.top1+1=top2 2.2.可以隨機訪問到任一個頂點的簡單鏈表

3.3.i(i+1)/2+j-1 4.4.FILO，FIFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度

8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k

三、應用題

1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3

數據結構試卷

（六）一、選擇題(30分)1． 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。

(A)20(B)30(C)40(D)45 2．執行一趟快速排序能夠得到的序列是（）。

(A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復雜度不受數據初始狀態影響而恒為O(nlog2n)的是（）。

(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

(A)空或只有一個結點(B)高度等于其結點數

(C)任一結點無左孩子(D)任一結點無右孩子

6．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。

(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。

(A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。

21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。

(A)front->next=s；front=s；(B)s->next=rear；rear=s；

(C)rear->next=s；rear=s；(D)s->next=front；front=s；

12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。

(A)99(B)100(C)101(D)102 14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。

(A)第i行非0元素的個數之和(B)第i列非0元素的個數之和

(C)第i行0元素的個數之和(D)第i列0元素的個數之和

二、判斷題(20分)1．調用一次深度優先遍歷可以訪問到圖中的所有頂點。（）

2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）3．冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）

5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（）

7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（）

9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）

三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。

2．設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________（設結點的指針域為next）。3．設有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多是_________。5．設二叉樹中度數為0的結點數為50，度數為1的結點數為30，則該二叉樹中總共有_______個結點數。

6．設F和R分別表示順序循環隊列的頭指針和尾指針，則判斷該循環隊列為空的條件為_____________________。

7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。

9．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。

數據結構試卷

（六）參考答案

一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B

二、判斷題

1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對

三、填空題

1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法

數據結構試卷

（七）一、選擇題(30分)1．設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結點。

(A)2n(B)n(C)n/2(D)n(n-1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。

(A)n(B)n-1(C)2n(D)2n-1 3．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（）。

(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。

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

5．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。

(A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是（）。

(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。

(A)20(B)256(C)512(D)1024 9．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（）。

(A)1(B)2(C)3(D)4 10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。

(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;

三、填空題(30分)1.1.設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設結點中的兩個指針域分別為left和right）。2.2.設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。

3.3.設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。

4.4.解決散列表沖突的兩種方法是________________和__________________。

5.5.設一棵三叉樹中有50個度數為0的結點，21個度數為2的結點，則該二叉樹中度數為3的結點數有______個。

6.6.高度為h的完全二叉樹中最少有________個結點，最多有________個結點。7.7.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。

8.8.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。

9.9.設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。

10.10.下面程序段的功能是實現一趟快速排序，請在下劃線處填上正確的語句。

struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){

int j=t;struct record x=r[s];i=s;

while(i

while(ix.key)j=j-1;if(i

while(____________________)i=i+1;if(i

}

_________________;}

數據結構試卷

（七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B

三、填空題

1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i

5．B 10．D

數據結構試卷

（八）一、選擇題(30分)1.1.字符串的長度是指（）。

(A)串中不同字符的個數(B)串中不同字母的個數

(C)串中所含字符的個數(D)串中不同數字的個數 2.2.建立一個長度為n的有序單鏈表的時間復雜度為（）

(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。

(A)兩個字符串的長度相等(B)兩個字符串中對應位置上的字符相等

(C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇（）。

(A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。

(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（）。

(A)8(B)7(C)6(D)5 8.8.設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有（）個度數為0的結點。

(A)5(B)6(C)7(D)8 9.9.設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發進行深度優先遍歷可以得到的一種頂點序列為（）。

(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

三、填空題(30分)1． 1． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。

2． 2． 下面程序段的功能是實現在二叉排序樹中插入一個新結點，請在下劃線處填上正確的內容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：s->next=p->next;_________________。4． 4． 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。

5． 5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。

6． 6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。7． 7． 設有向圖中不存在有向邊，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。

8． 8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。

9． 9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10． 10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。

數據結構試卷

（八）參考答案

一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A

三、填空題

1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50