1、一、單選題知識點一：緒論1. 設有如下遺產繼承規則：丈夫和妻子可以互相繼承遺產；子女可以繼承父親或母親的遺產：子女間不能相互繼承。則表示該遺產繼承關系的最合適數據結構應該是（）。A. 樹 B.圖 C.數組 D. 二叉樹2. 設有一遺傳關系:X是丫的父親，X可以把它的屬性遺傳給Y。則表示該遺傳關系最適合的數據結構為（）。A. 向量 B.樹 C. 圖 D. 廣義表3. 在數據結構中，從邏輯上可以把數據結構分成（）A. 動態結構和靜態結構B.緊湊結構和非緊湊結構C. 線性結構和非線性結構D.內部結構和外部結構4. 數據結構在計算機內存中的表示是指（）A. 數據的存儲結構B.數據結構C.數據的邏輯結構

2、D.數據元素之間的關系5. 計算機算法指（）A.計算方法B.排序方法C.解決問題的有限運算序列D.調度方法6. 在以下的敘述中，正確的是A.線性表的線性存儲結構優于鏈表存儲結構B.二維數組是其數據元素為線性表的線性表C.校的操作方式是先進先出D. 隊列的操作方式是先進后出7. 在決定選取何種存儲結構時，一般不考慮（）A.各結點的值如何B.結點個數的多少 C.對數據有哪些運算D.所用編程語言實現這種結構是否方便8. 在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲（）A.數據的處理方法B.數據元素的類型 C.數據元素之間的關系 D.數據的存儲方法9. 以下說法正確的是（）A.數據元素是數

3、據的最小單位B. 數據項是數據的基本單位C. 數據結構是帶結構的數據項的集合D. 一些表面上很不相同的數據可以有相同的邏輯結構）。B.正確性、可讀性、健壯性及有窮性正確性、可讀性、健壯性及確定性10設計一個“好”的算法應達到的目標為（A.正確性、可讀性、健壯性及效率與低存儲量需求C.正確性、可讀性、健壯性及可行性D.知識點二：線性表11. 與線性表的鏈接存儲相符的特性是（）。A.插入和刪除操作靈活 B.需要連續存儲空間C.便于隨機訪問 D.存儲密度大12. 在單向循環鏈表中，若頭指針為h，那么p所指結點為尾結點的條件是（）A. p=NULL B. p-> next=NULL C. p=h

4、 D. p-> next=h13. 與線性表的鏈接存儲不相符的特性是（）。A.插入和刪除操作靈活B.需要連續的存儲空間C.存儲空間動態分配D.需另外開辟空間來保存元素間的關系14. 以h為頭指針的帶頭結點的單向循環鏈表為空的條件是（）。A. h=NULL B. h-> next=NULL C. h-> next=h D. h-> next-next=h15. 與線性表的鏈式存儲不相符合的特性是（）。A.插入和刪除操作靈活 B.需要連續的存儲空間 C.存儲空間動態分配D.非緊湊結構16. 鏈表不具備的特點是（）A.可隨機訪問任一結點 B插入刪除不需要移動元素C.不必事先估

5、計存儲空間 D.所需空間與其長度成正比17. 帶頭結點的單鏈表head為空的判定條件是（）A. head = NULL B. head ->next=NULL C. head ->next = head D. head!=NULL18. 需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構A.單鏈表B.靜態鏈表c.線性鏈表D.頂序存儲結構19. 如果最常用的操作是取第i個結點及其前驅，則采用存儲方式最節省時間。A.單鏈表B.雙鏈表C.單循環鏈表D.順序表20. 在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是2A. 0（1） B. 0（ n） C

6、. 0（n） D. 0（n Iog2 n）21. 與單鏈表相比，雙鏈表的優點之A.插入、刪除操作更簡單BC.可以省略表頭指針或表尾指針22. 一維數組和線性表的區別是（A.前者長度固定，后者長度可變C.兩者長度均固定D.是（）可以進行隨機訪問D.順序訪問相鄰結點更靈活）B. 后者長度固定，前者長度可變兩者長度均可變知識點三：棧和隊列23. 若進隊序列為1，2，3，4，則出隊序列是（）。A. 4， 3，2，1 B. 1，2， 3， 4 C. 1， 3， 2，4 D.3， 2， 4，124. 設輸入序列為1，2，3，4借助一個棧不可能得到的輸出序列是（）。A.1， 2，3， 4 B.4，3， 2，

7、1C.3，4，1， 2 D. 125.若進棧序列為1, 2，3,4則不可能得到的出棧序列為（）A. 3， 2， 1， 4 B. 3，2，4，1C. 4 ， 2， 3， 1D.2， 3， 4，126.棧應用的典型事例是（）。A.排隊 B.查找C.歸并D.用“算符優先法”進仃表達式求值27.棧和隊列都是（）。A.順序存儲的線性結構B.鏈式存儲的線性結構C.限制存取點的線性結構D.限制存取點的非線性結構28. 對于順序存儲的隊列，存儲空間大小為n,頭、尾指針分別為F和R,若將其看成一個首尾相接的圓環，則隊列中元素個數為（）。A. R-F B. n+R-F C.C（R-F+1）% nD. （n+R-F

8、）% n29. 從一個順序隊列刪除元素時，首先需要 A.前移一位隊首指針B. 后移一位隊首指針C. 取出隊首指針所指位置上的元素D.取出隊尾指針所指位置上的元素30. 假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為 學習必備歡迎下載31. 初始為空的堆棧中依次插入元素:f 、e、d、c、b、a以后,連續進行了 3次刪除操作，此時的棧頂元素是(A.cB.d C.b D.e32 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據緩沖區，這樣主機將要輸出的數據依次寫入該緩沖區，而打印機則從該緩沖區中取出數據打印。該緩沖區應該是一個()結構。A.堆B.隊列C.數組 D.

9、線性表33 設一個棧的入棧序列是ABC D則借助于一個棧所得到的出棧序列不可能是()。A.ABCD B.DCBA C.ACDBD.DABC34.設棧最大長度為3,入棧序列為1、2、3、4、5、6，則不可能的出棧序列是()。A.1、2、3、4、5、6B.2、1、3、4、5、6C. 3、4、2、1、5、6D.4、3、2、1、5、635設棧的輸入序列是 1, 2,，n,若輸出序列的第一個元素是n,則第i個輸出元素是()。A.n-i+1B.iC. n-iD.前面都不正確知識點四：串)。B. 串中不同字符的個數D.串中所有字符的個數36. 串的長度是(A.串中不同字母的個數C.串中所含數字的個數37.

10、()是C語言中"abcd32IABCD"的子串。D."21AB"A.abed B.32IAB C."abcABC"38. 串是()。A.不少于一個字符的序列 B.有限個字符的序列C.不少于一個字母的序列D.任意個字母的序列39. 設有兩個串p和q,求q在p中首次出現的位置的運算稱做()A.連接B.模式匹配C. 求子串 D. 求串長40 .若串s='software'，其真子串(不含自身)的個數是A.8B.37C.36D.9的字符,2)41. 有串sl ='ABCDEFG' , s2='PQRST

11、'，假設函數con(x,y)返回x和y串的連接串，subs( s , i , j)返回串S的從序號i 開始的j個字符組成的子串， len(s) 返回串S的長 度，貝U con( subs( s 1 , 2, len( s2) ) , subs( s 1 , len( s2 ) 的結果串是A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG42. 串是一種特殊的線性表，其特殊性體現在()A.可以順序存儲B.數據元素是一個字符 C.可以鏈式存儲D.數據元素可以是多個字符知識點五：數組和廣義表43. 己知廣義表 A=(a , b)(c , d)，則 head(A)等于()

12、。A. ( a , b ) B. ( a , b ) C. a , b D. a44. 設一個具有t個非零元素的m*n大小的稀疏矩陣采用順序存儲，求其轉置矩陣的普通轉置算法的時間復雜度為A. O(m) B. O(n) C. O(n+t)D. O( n*t)45. 一個三對角矩陣Anx n已按行壓縮存儲到一維數組B中，則B的長度至少為()。A.3 n+1B.3 nC.3 n-1D.3 n-246. 二維數組A1020采用列序為主方式存儲，每個元素占1個存儲單元，并且A00的存儲地址是200，則A612的地址是（）A. 328 B. 327C.326 D. 32947. 多維數組的數組元素之間的關

13、系，A.是線性的B.是樹形的C.既是線性的，又是樹形的D.既不是線性的，也不是樹形的知識點六：樹和二叉樹48. n個結點的二叉樹，若用二叉鏈表作為存儲結構，則非空閑的左、右孩子鏈域為A.n B. 2n C. n-l D. n+l49. 對于下邊的二叉樹，其中序序列為 （）A. DBAFCGB. DBAFGC()A.8 B. 15 C. 16 D. 3251. 對于下面的二叉樹，其中序序列為 （）。A. ABCDEFG B. ABDECFG C. DBEAFCG D. ADEBCFG52. n個結點的二叉樹中，用二叉鏈表做存儲，非空指針數目為（）A. n B. 2n C. n-1 D. n+15

14、3. 由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 A. 24 B. 48 C. 72 D. 5154. 二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK中序遍歷：HFIEJKG該二叉樹根的右子樹的根是（A.E B.F C.G D.H）。55.樹結構最適合用來表示（)°A.兀素間具有分支層次關系的數據B.無序數據C.有序數據D.元素間沒有關聯的數據56. 具有127個結點的完全二叉樹其深度為（）。57. 哈夫曼樹是（）A.滿二叉樹B.二叉排序樹C.樹的路徑長度最短的二叉樹D.帶權路徑長度最短的二叉樹58. 設一棵二叉樹中沒有度為1的結點，已知葉

15、子結點數為n此樹的結點數為（）。A.2 n+2B.2 n+1C.2 nD.2 n-159. 設二叉樹中有n2個度為2的結點，ni個度為1的結點，no個葉子結點，則此二叉樹中空指針域個數為（A.no+n計n2 B.n2+ni+2no C.2 n2+ni D.2 n o+ni60. 用權值分別為15, 2, 4, 5的四個結點，構造出的哈夫曼樹為（D）。61 .由帶權9、1、3、5、6的五個葉子結點生成的哈夫曼樹的帶權路徑長度為（A.50B.60C.52D.6562. A、B兩個結點可以構成（）棵不等價的二叉樹。A.2B.3C.4D.563設哈夫曼樹的葉結點數為n,則它的結點總數為（）。A.2 n

16、-1B.2 nC.2 n+1D.不確定64. 深度為k的完全二叉樹所含葉結點的個數最多為（）kk 1A. 2 B. 2- C. k D. 2k65. 在線索化二叉樹中，t所指結點沒有左子樹的充要條件是A. t 一 >lchild = NULLB. t 一 >ltag=1C. t->ltag=l且t 一>lchild=NULLD. .以上都不對66. 在一非空二叉樹的中序遍歷序列中，根結點的右邊（）A.只有右子樹上的所有結點B.只有右子樹上的部分結點C.只有左子樹上的部分結點D.只有左子樹上的所有結點67. 任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次A.

17、不發生改變B.發生改變C.不能確定D.以上都不對68. 對一個滿二叉樹，m個樹葉，n個結點，深度為h,則（）A. n=h+m B. h+m=2 n C. m=h-l D. n=2h-l69. 某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定（）A.空或只有一個結點 B.完全二叉樹C.二叉排序樹D.高度等于其結點數70. 線索二叉樹是一種（）結構。A.邏輯 B.邏輯和存儲C.物理 D.線性知識點七：圖71. 給定下列有向圖，從頂點 V1出發，其深度優先搜索序列為（）A. 12534 B.12435 C. 14325 D. 12345A. 6 B. 5 C. 7 D. 473. 具有8

18、個頂點的連通圖的深度優先生成樹，其邊數為（）。A. 8 B. 9 C. 7 D. 674. G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A.6B.7C.8D.975. 一個n個頂點的連通無向圖，其邊的個數至少為（）。A.n-1B.n C.n+1D.n log ni 1 o76. 對于有向圖的鄰接矩陣A= 1 0 1，該圖共有（）條弧。? 1 0一A.5B.4C.3D.277 對于具有n個頂點的強連通圖，其弧條數的最小值為（）。A. n+1 B.n C.n-1D.n-278 采用鄰接表存儲的圖按深度優先搜索方法進行遍歷的算法類似于二叉樹的（）。A.先序遍歷 B.中序遍歷 C.后序

19、遍歷 D.層次遍歷79. 采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的（）A.先序遍歷 B.中序遍歷 C. 后序遍歷 D.按層遍歷80. 對某個無向圖的鄰接矩陣來說，A. 第i行上的非零元素個數和第i列的非零元素個數一定相等B. 矩陣中的非零元素個數等于圖中的邊數C. 第i行上，第i列上非零元素總數等于頂點Vi的度數D. 矩陣中非全零行的行數等于圖中的頂點數81 .以下說法中不正確的是A. 無向圖中的極大連通子圖稱為連通分量B. 連通圖的廣度優先搜索中一般要采用隊列來暫存剛訪問過的頂點C. 圖的深度優先搜索中一般要采用找來暫存剛訪問過的頂點D. 有向圖的遍歷不可采用廣度優先搜索方法82.

20、 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（）學習必備歡迎下載83. 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，所有鄰接表中的結點總數是（）A. e/2 B. e C.2e D.n+e知識點八：查找84. 以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為 .2A.n（n+1）/2 B.nC.n（n-1）/2 D.log2n85. 以二分查找方法查找一個線性表時，此線性表必須是順序存儲的A.有序表 B.無序表 C. 棧 D.隊列86. 若在線性表中采用折半查找法查找元素，該線性表應該（）。A.元素按值有序B.采用順序存儲結構C.元素

21、按值有序，且采用順序存儲結構D.元素按值有序，且采用鏈式存儲結構87. 衡量查找算法效率的主要標準是（）。（A）元素個數（B）所需的存儲量（C）平均查找長度（D）算法難易程度88. 設哈希表長 m=14,哈希函數H（key）=key%11,表中已有4個結點：Add（15）=4Add（38）=5Add（61）=6Add（84）=7其余地址為空，如用二次探測再散列處理沖突，關鍵字為49的結點地址是（）A.8 B.3 C.5 D.9知識點九：排序89. 下列排序算法中，最壞情況下，時間復雜度為0（n2）的排序算法是（）。A.堆排序 B.希爾排序 C.歸并排序D.快速排序90. Shell排序的平均時

22、間復雜度為（）。A. O（ n） B.O（n log 2n）C. O（n2） D. n 1.391. 下列排序中，占用的輔助空間最多的是（）。A.快速排序 B.冒泡排序C.直接選擇排序D.二路歸并排序92. 下列排序算法中不穩定的是（）。A.直接選擇排序 B.二分插入排序C.冒泡排序 D.歸并排序93. 在文件局部有序的情況下，最好的內部排序應該是（）。A.直接插入排序 B.冒泡排序C. 直接選擇排序 D.快速排序94. n個關鍵字的直接插入排序所需的最小移動次數是（）。A. 2（n-1） B.0 C. （n+3）（ n-2）/2D. n2/295. 如表r有100000個元素，前99999個

23、元素遞增有序，則采用（）方法比較次數較少。A.直接插入排序 B.快速排序C.歸并排序 D.選擇排序96. 初始文件中有兩個關鍵字相同的記錄，通過不穩定的排序方法排序后，（）。A.使得領先關系不發生變化 B.領先關系一定發生變化C.兩個位置都不會發生變化D.領先關系可能發生變化97. 每一趟都能選出一個元素放在其最終位置上，并且不穩定的排序算法是（學習必備歡迎下載A.冒泡排序B.簡單選擇排序C.希爾排序D.直接插入排序知識點十：文件98. 在索引順序文件中（）A.主文件是無序的B.主文件是有序的c.不適合隨機查找D.索引是稠密索引99. 散列文件的特點是A. 記錄按關鍵字排序B. 記錄可以進行順

24、序存取c.存取速度快，但占用較多的存儲空間D. 記錄不需要排序，存取效率高100. 用ISAM和VSAMfi織文件屬于A.順序文件B.索引文件c.散列文件 解ISAM和VSAM都屬于索引順序文件。二、填空題緒論1 在數據結構中，從邏輯上可以把數據結構分成 結構和結構。2 分析一個算法的優劣要從兩個方面，即 復雜度和 復雜度。3數據的結構是依賴于計算機存在的。4 線性結構元素之間是 對的關系；樹形結構元素之間關系是 ;圖形結構元素之間關系是 。線性表5. 單鏈表的結點空間包括兩部分，即 域和域。6. 帶頭結點的單鏈表 L為空的條件是 。7. 單鏈表的 和操作大多數情況下要優于順序表。&在

25、長度為n的順序表中刪除第i個元素時，假設i值合法，需向前移動 個元素。9在線性表的順序存儲中，若一個元素的下標為i,則它的前驅元素的下標為 ，后繼元素的下標為 棧和隊列10. 插入限定在表的一端，而刪除限定在表的另一端進行的線性表稱為,允許插入的一端稱為 11. 順序循環隊列 QM,下標從0到M-I，頭尾指針分別用 F和R表示，則隊空條件是 。12. 是限定僅在表尾進行插入或刪除操作的線性表。13. 插入和刪除操作在 進行。串14. 串s= “love ” ,其真子串（不含自身）的個數是 。15. 設 S仁 “GOOD, S2= “j' , S3= “ BYE!”，則 S1, S2,

26、S3 連接之后的結果是 數組和廣義表16. 個廣義表的深度等于嵌套的最大層數。17. 在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的_、_和_ 三項。樹與二叉樹18. 二叉樹的葉結點數 no與二度結點數n2的關系是_。19. 具有256個結點的完全二叉樹的深度為 _。20. 深度為k的完全二叉樹至少有 個結點，至多有 個結點。21. 如果結點A有3個兄弟，而且 B是A的雙親，貝U B的度是。22. 具有n個結點的二叉樹，采用二叉鏈表存儲，共有 個空鏈域。23. 線索二叉樹的左線索指向其 _，右線索指向其q24 .具有50個結點的完全二叉樹的高度是 q25.具有100個結點的完全二叉樹

27、有個葉子。圖26具有n個頂點的圖用鄰接矩陣存儲，矩陣是 行列。27.一個n個頂點的連通無向圖，其邊的個數至少為 q28要連通具有n個頂點的有向圖，至少需要 條邊。29. n個結點的完全有向圖含有邊的數目是 q30. 具有10個頂點的無向圖，邊的總數最多為 q31. 在圖G的鄰接表表示中，每個頂點鄰接表中所含的結點數，對于無向圖來說等于該頂點的;對于有向圖來說等于該頂點的q查找、排序32 .順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數最多為 次；最少為 次。33. 以二分查找方法查找一個線性表時，此線性表必須是- _ 存儲的_ _ 表。34. 每次從無序表中取出一個元素，把它插入到有

28、序表中的適當位置，此種排序方法叫做排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。35. n個元素進行冒泡排序，最少的比較次數是 q三、判斷題緒論1. 在數據結構中，數據的邏輯結構與所使用的計算機無關2. 數據元素是數據的最小單位。3. 健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態線性表4. 線性表的邏輯順序與存儲順序總是一致的5. 在線性表的順序存儲結構中，邏輯上相鄰的2個元素在物理位置上并不一定緊鄰6. 順序存儲的線性表示可以按序號隨機存取7. 循環鏈表中每一個元素都有后繼8. 線性表的唯一存儲形式是鏈表。9. 在順序表中取出第i個元素所花

29、費的時間與 i成正比。10. 線性表的長度是線性表所占用的存儲空間的大小。11. 線性表的鏈式存儲結構優于順序存儲結構。12. 鏈表的每個節點中都包含一個指針域。棧和隊列13. 一個棧的入棧順序為 A、B、C、D、E,則，出棧順序 ACEDB是不可能的。14. 棧和隊列都是運算受限的線性表。15. 在棧為空的情況下，不能做出棧操作，否則產生下溢出。16. 在循環隊列中，若尾指針Rear大于頭指針Fro nt，則其元素數為(Rear -Fro nt)。17. 一個棧的輸入序列是 12345,則輸出序列43512是可能的。18. 循環隊列隊滿的條件是rear+仁front。19. 循環隊列是鏈隊列

30、。串20. 串長度是指串中不同字符的個數。21. 串是n (0個字母的有限序列。22. 空串的長度為零。23. 子串是指串中任意個連續字符組成的子序列。24. 空串是任何串的子串。25. 空串與空白串是相同的。數組和廣義表26. 廣義表的長度是指廣義表中的原子個數。27. 取出廣義表 A=(a, (b,c), d)中的運算head(tail(A)的結果不是b。28. 若廣義表中的每個元素都是原子，則廣義表為線性表。29. 稀疏矩陣是指大多數元素值為0，只有少數元素值不為 0的矩陣。30. 矩陣的壓縮存儲適用于所有矩陣。31. 稀疏矩陣可以用三元組的方式存儲。樹和二叉樹32. 完全二叉樹中沒有度

31、為1的結點。33. 樹是一種線性結構。34. 已知一棵樹的先序序列和后序序列，一定能構造出該樹。35. 二叉樹只能采用二叉鏈表來存儲。36. 若樹的度為2時，該數為二叉樹。37. 樹最適合表示元素之間具有層次關系的數據。38. 具有三個結點的二叉樹有五種。39. 深度為5的二叉樹最多有3層。圖40. 有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第 i列的元素個數。41. 對任意一個圖，從它的某個結點出發進行一次DFS或BFS可訪問到該圖的每個結點。42. 有向圖用鄰接矩陣表示后，結點i的出度等于第i行中非0且非旳的元素個數。43. 圖的廣度優先搜索算法類似于二叉樹的按層遍歷操作。44.

32、無向圖的極大連通子圖稱為連通分量。45. 有n個頂點的無向圖最多有n(n+1)條邊。查找46. 二分查找只適用于有序表。47. 二分查找對線性表的存儲結構無任何要求。48. 采用順序查找的平均查找長度為n-1/2。排序49. 只有初始數據為倒序時，冒泡排序所執行的比較次數最多。50. 選擇排序的比較次數與數據初始狀態無關。四、綜合應用題樹和二叉樹1. 己知二叉樹的中序序列為 DBHEIAFJCKG先序序列為ABDEHICFJGK請畫出該二叉樹。2. 對于給定的5個實數W=8, 5,13, 2, 6，試構造Huffman樹，并求出該樹的最小帶權路徑長度。3. 請分別寫出下列二叉樹的先序、中序和后

33、序序列。4. 對下圖進行如下操作寫出其鄰接矩陣。(2)求出從頂點V5出發的廣度優先搜索遍歷序列。5. 給定無向圖如下，寫出它的鄰接矩陣，求出一棵最小生成樹6. 對下邊給出的圖進行如下操作(1) 寫出圖的鄰接矩陣。(2) 畫出圖的鄰接表。查找7. 給定有序表D= 15, 17, 18, 22, 35, 51, 60, 72, 93，用折半查找法在 D中查找18。現要求：試用圖示法表示查找過程。排序8. 假定有以下關鍵字序列，試給出快速排序的第一趟排序結果。80 15 85 25 65 90 05 959. 用直接選擇排序的方法對下列關鍵字序列進行排序，請寫出每一趟排序的結果。60 40 20 8

34、0 30 10 5010假定有以下關鍵字序列，試給出兩兩歸并排序的每一趟排序結果。70 80 76 25 94 16 05 68五、程序填空題第二章以下算法是實現在順序表的第i個位置插入元素e,請將程序補充完整1.int List In sert(SqList *&L,i nt i,ElemType e)int j;if (i<1 | i>L->le ngth+1)return 0;i-;將順序表位序轉化為elem下標for (j=L->le ngth_1;j>i;j_) /將datai及后面元素后移一個位置L->data=L->data;L-

35、>data=e;L->le ngth;/順序表長度增1Retur n 1;2.以下算法是頭插法建立長度為n，元素值由數組a賦值的帶頭結點的單鏈表，請將程序補充完整void CreateListF(LinkList *&L,ElemType a,int n)/頭插法建立單鏈表Li nkList *s;int i;創建頭結點創建新結點L=(Li nkList *)malloc(sizeof(L in kList); /L-> next=NULL;for (i=0;i<i+)s=(L in kList *)malloc(sizeof(Li nkList);/s->

36、;data=ai;/ 將*s插在原開始結點之前，頭結點之后3以下代碼是實現在單鏈表L的第i個位置插入元素e,請將程序補充完整。int List In sert(Li nkList *&L,i nt i,ElemType e)int j=0;Lin kList *p=L,*s;while (j<i-1 && p!=NULL) /查找第 i-1 個結點 5if (p=NULL) /未找到位序為i-1的結點return 0;else /找到位序為i-1的結點*p s=(LinkList *)malloc(sizeof(LinkList);/創建新結點 *ss->d

37、ata=e;: _/ 將*s插入到*p之后return 1;第三章：4 以下代碼是順序棧的入棧算法，請將程序補充完整。int Push(SqStack *& s,ElemType e)if (s->top=MaxSize-1) /棧滿的情況，即棧上溢出return 0;s->top _;s->data =e;return 1;5 以下代碼是實現循環隊列的入隊算法，請將程序補充完整。int en Queue(SqQueue *& q,ElemType e)if ()_/ 隊滿return 0;q->rear= 也 入隊時隊尾增 1q->dataq-&

38、gt;rear=e;return 1;第四章：6以下代碼是實現兩個字符串的連接，請將程序補充完整。SqStri ng Co ncat(SqStri ng s,SqStri ng t)SqStri ng str;int i;將 s.data0 s.datas.length-1復制到 strstr.le ngth=sen gth+t.le ngth;for (i=0;i<s .len gth;i+) /for (i=0;i<t.length;i+) /將 t.data0t.datat.length-1復制到 strreturn str;7 以下代碼是實現刪除一個字符串從位置開始的連續j

39、個字符，請將程序補充完整。SqString DelStr(SqString s,int i,int j)int k;SqStri ng str;str.le ngth=0;參數不正確時返回空串if (i<=0 | i>s.length | i+j>s.length+1) /return str;for (k=0;k<k+)/將 s.data0s.datai-2 復制到 strstr.datak=s.datak;for (k=;k<s.length;k+)/將 s.datai+j-1datas.length-1 復制到 strstr.datak-j=s.datak;

40、str.le ngth=return str;查找算法:&以下代碼是實現對長度為n的順序表R查找K的折半查找算法，請將程序補充完整。int Bin Search(SeqList R,i nt n,KeyType k)int low= ,high=,mid;while (low<=high)mid=if (Rmid.key=k) /查找成功返回return mid;if (Rmid.key>k) /繼續在Rlow.mid-1 中查找high=elselow=/繼續在Rmid+1.high 中查找return -1;排序算法：9 以下代碼是選擇排序算法，請將程序補充完整。voi

41、d SelectSort(i nt R,i nt n)int i,j,k,l;int temp;for (i=0;i< n-1;i+)/做第i趟排序k=i;for (j=i+1;j <n ;j+) /if (Rj.key<Rk.key)在當前無序區 Ri.n-1 中選key最小的Rk;/k記下目前找到的最小關鍵字所在的位置if (k!=i)/交換Ri和Rkprin tf("i=%d: ",i);for (l=0;l< n;l+)prin tf("%d ”,Rl.key);prin tf("n");10 以下算法是對R進行

42、冒泡排序，請將程序補充完整。void BubbleSort(RecType R,i nt n)int i,j,k;RecType tmp;for (i=0;i< n_1;i+)for (j=;»訃-)/比較，找出本趟最小關鍵字的記錄if (Rj.key<Rj-1.key);R【il與Rj-1進行交換，將最小關鍵字記錄前移for (k=0;k< n; k+)printf("%d ”,Rk.key);prin tf("n");(A) 3 , 2, 1 , 4(B) 3, 2, 4, 1(C) 4, 2, 3, 12. 對于下列二叉樹，其后序

43、序列為 ()。(A) ABDECFG (B) DBEAFCG(C) DEBFGCA (D) GFCEBDA3. 對于下列AOV網，不能出現的拓撲序列為 ()(C) 24135 (D) 21435(A) 12345(B) 12435題三 2 圖題三3圖4. 深度為k的完全二叉樹所含葉結點的個數最多為()(A) 2 k(B) 2 k-1(C) k(D) 2k5衡量查找算法效率的主要標準是(A)元素個數 (B) 所需的存儲量(C)平均查找長度(D)算法難易程度四、應用題1 將下列森林轉化為二叉樹2對下圖進行如下操作：(1)寫出其鄰接矩陣。(2分)(4分)(2)按Kruskal算法求其最小生成樹，并寫

44、出相應的邊集數組。3請畫出后序和中序序列相同的二叉樹的所有形態。(3分)32,13,49,4. 散列函數為H(k)=k%7，散列表的地址從 O-.- 6用線性探查法解決沖突，建立散列表ht。給定關鍵字序列為55, 22, 38, 21 。要求：(1)構造散列表(只畫出表，不寫算法)0 (5分)(2 )求出平均查找長度。(2分)5. 用直接選擇排序方法對下列關鍵字進行排序，請寫出每一趟排序的結果。(6分)68 45 20 90 15 10 50五、算法設計(在下列算法的橫線上填上適當的表達式、語句或運算符。每空3分，共30分)1. 在帶頭結點的head單鏈表的結點a之后插入新元素xstruct

45、node elemtype data;node *n ext;void Ikinsert (node叮 lead , elemtype x) node *s , *p;S=;s->data=;p=head->n ext;while (p!=NULL) &&( p->data!=a) if (p=NULL)cout?"不存在結點a"else ;2. 快速排序學習必備歡迎下載void qksort (int R , int p , int q) / 按遞增序對 RpRq進行快速排序 int i=p , j=q；R 0 =R i ;IIRO作臨時

46、單元while (j >i )&&( R j _R 0) j-;if (j>i)R i =Rj; i+；while (i<j ) && (R i R 0) i+;if(i<j) Rj=Ri;j-;R i=;i+; j-;if (j >p) qksort(R , p, j);if (i<q);模擬試題二一、判斷題(下列各題，你認為正確的，請在前面的括號內打J，錯誤的打X。每小題 1分，共10分)()1.數據的存儲結構獨立于計算機。()2.線性表簡稱為”順序表”。()3.對數據的任何運算都不能改變數據原有的結構特性。()4.從循環

47、單鏈表的任一結點出發，可以找到表中所有結點。)5.校是一種先進先出的線性表。()6.鏈表的主要缺點是不能隨機訪問。)7.二叉樹是樹的特殊形式。()8.圖可以沒有邊，但不能沒有頂點。)9.冒泡排序算法是穩定的排序。()10.散列法是一種對關鍵字進行比較的查找方法。二、填空題(每空 2分，共20分)1. 對數據所施加的運算可分為兩類，即 型和型。2. 將插入限定在表的一端，而刪除限定在表的另一端進行的線性表稱為,允許插入的一端稱為 3. 二叉樹的葉結點數n(與二度結點數n2的關系是.4. 對于順序循環隊列QM,下標從0到M-I，頭尾指針分別用F和R表示，則隊空條件是 .5. n個頂點的無向完全圖具

48、有 邊。6. 拓撲排序的操作對象是 7快速排序的最壞情況是初始序列為正序和反序，其時間復雜度為8.希爾排序是屬于 排序的改進方法。括號內，多選不給分，每小題 3分,三、單選題(本題的每一備選答案中，只有一個是正確的，請把你認為正確的答案填入 共15分)1. 校和隊列都是(A)順序存儲的線性結構(B) 限制存取點的線性結構(C)鏈接存儲的線性結構(D)限制存取點的非線性結構2. 與線性表的鏈接存儲不相符合的特性是(A)便于插入、刪除運算(B)存儲空間動態分配(C)需要連續的存儲空間(D)只能順序查找3.設二叉樹的根為第一層，則第層上的結點數最多有(A) 2 i(B)2 i +1(C) 2 i -

49、1(D) 2 i4.直接選擇排序的時間復雜度為(A)0( n)B) O(n logi) (C)o(n(D) O(log 2 n)5.給定下列有向圖，從頂點 VI出發,其深度優先搜索序列為 (C) 14325(D)12345(2. 對于下邊的有向圖進行如下操作。(1)畫出其鄰接表。(4分)寫出3種不同的拓撲序列。(3分)3請畫出先序與中序序列相同的二叉樹的所有形態。（3分）4. 給定關鍵字序列19 ,14, 27 , 68, 84, 23, 1 , 20, 55, 12, 10, 79,散列函數為HK=K% 11,散列 表的地址從0-10 ,用外鏈法處理沖突，散列地址為d的同義詞均掛在以htd為

50、頭指針的單 鏈表中。（1）請畫出其散列表（不寫算法 ）0（5分）（2）求出成功的平均查找長度。（2分）5. 對下列關鍵字序列進行快速排序，請寫出第一趟排序結果，并標識出在第一趟排序過程中數據交換的情況。（5分）35 92 15 19 10 80 100五、算法設計（在下列算法的橫線內填上適當的語旬或表達式。每空 3分，共30分）1. 直接插入排序void in sertsort（i nt R）/按遞增序對R1 Rn進行直接插入排序int i , j;for （i=2; i <=;i+）R 0 =R i ; II設定RO為監視哨while （R 0Rj）;j-;Rj+l =;/插入第i個記

51、錄2. 先序遍歷二叉樹設二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表結點的類型為node找S的元素類 型為指向node勺指針類型，找容量M足夠大。先序遍歷的非遞歸算法如下：Struct node char data;Node *lc,*rc;；void preorder (node *t)node *s M , *p=;int top=- 1;/ 置棧空do while (p!=NULL);S+top=;if (top! = -1)p=stop-; while ( top! = - 1) | (p ! =NULL );模擬試題三一、判斷題(下列各題，你認為正確的，請在前面的括號內打"

52、，錯誤的打X。每題1分，共10分)()1.數據是計算機加工處理的對象。()2.數據結構的概念包括數據的邏輯結構、數據在計算機中的存儲方式和數據的運算三個方面。()3.線性表是由n%個相同類型元素組成的有限序列。()4.棧是一種后進先出的線性表。()5.從循環鏈表的某一結點出發，只能找到它的后繼結點，不能找到它的前趨結點。()6.單鏈表設置頭結點的目的是為了簡化運算。()7.深度為h的二叉樹最多有2h -1個結點。()8.圖G由兩個集合V(G)和E(G)所組成，其中頂點集 V(G)可以為空集，而邊集 E(G)不能為空。()9.散列法是一種對關鍵字進行運算的查找方法和存儲方法。學習必備歡迎下載()10.快速排序在任何情況下，都是速度最快的二種排序方法。二、填空題(每空2分，共20分)1. 數據元素之間存在的相互關系稱為 2數據結構從邏輯上分為 結構和結構。3. 線性表的順序存儲結構稱為 4. 所有插入在表的一端進行，而所有刪除在表的另一端進行的線性表稱5.