數(shù)據(jù)結(jié)構(gòu)與算法題庫下發(fā)版

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

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

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

4、 D. p-> next=h13. 與線性表的鏈接存儲不相符的特性是（）。A.插入和刪除操作靈活B.需要連續(xù)的存儲空間C.存儲空間動態(tài)分配D.需另外開辟空間來保存元素間的關(guān)系14. 以h為頭指針的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表為空的條件是（）。A. h=NULL B. h-> next=NULL C. h-> next=h D. h-> next-next=h15. 與線性表的鏈?zhǔn)酱鎯Σ幌喾系奶匦允牵ǎ?。A.插入和刪除操作靈活 B.需要連續(xù)的存儲空間 C.存儲空間動態(tài)分配D.非緊湊結(jié)構(gòu)16. 鏈表不具備的特點(diǎn)是（）A.可隨機(jī)訪問任一結(jié)點(diǎn) B插入刪除不需要移動元素C.不必事先估

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

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

7、1C.3，4，1， 2 D. 125.若進(jìn)棧序列為1, 2，3,4則不可能得到的出棧序列為（）A. 3， 2， 1， 4 B. 3，2，4，1C. 4 ， 2， 3， 1D.2， 3， 4，126.棧應(yīng)用的典型事例是（）。A.排隊 B.查找C.歸并D.用“算符優(yōu)先法”進(jìn)仃表達(dá)式求值27.棧和隊列都是（）。A.順序存儲的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)28. 對于順序存儲的隊列，存儲空間大小為n,頭、尾指針分別為F和R,若將其看成一個首尾相接的圓環(huán)，則隊列中元素個數(shù)為（）。A. R-F B. n+R-F C.C（R-F+1）% nD. （n+R-F

8、）% n29. 從一個順序隊列刪除元素時，首先需要 A.前移一位隊首指針B. 后移一位隊首指針C. 取出隊首指針?biāo)肝恢蒙系脑谼.取出隊尾指針?biāo)肝恢蒙系脑?0. 假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為 學(xué)習(xí)必備歡迎下載31. 初始為空的堆棧中依次插入元素:f 、e、d、c、b、a以后,連續(xù)進(jìn)行了 3次刪除操作，此時的棧頂元素是(A.cB.d C.b D.e32 在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，這樣主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個()結(jié)構(gòu)。A.堆B.隊列C.數(shù)組 D.

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

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

11、'，假設(shè)函數(shù)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 ) 的結(jié)果串是A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG42. 串是一種特殊的線性表，其特殊性體現(xiàn)在()A.可以順序存儲B.數(shù)據(jù)元素是一個字符 C.可以鏈?zhǔn)酱鎯.數(shù)據(jù)元素可以是多個字符知識點(diǎn)五：數(shù)組和廣義表43. 己知廣義表 A=(a , b)(c , d)，則 head(A)等于()

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

13、系，A.是線性的B.是樹形的C.既是線性的，又是樹形的D.既不是線性的，也不是樹形的知識點(diǎn)六：樹和二叉樹48. n個結(jié)點(diǎn)的二叉樹，若用二叉鏈表作為存儲結(jié)構(gòu)，則非空閑的左、右孩子鏈域為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個結(jié)點(diǎn)的二叉樹中，用二叉鏈表做存儲，非空指針數(shù)目為（）A. n B. 2n C. n-1 D. n+15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、0 30 10 5010假定有以下關(guān)鍵字序列，試給出兩兩歸并排序的每一趟排序結(jié)果。70 80 76 25 94 16 05 68五、程序填空題第二章以下算法是實現(xiàn)在順序表的第i個位置插入元素e,請將程序補(bǔ)充完整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-;將順序表位序轉(zhuǎn)化為elem下標(biāo)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，元素值由數(shù)組a賦值的帶頭結(jié)點(diǎn)的單鏈表，請將程序補(bǔ)充完整void CreateListF(LinkList *&L,ElemType a,int n)/頭插法建立單鏈表Li nkList *s;int i;創(chuàng)建頭結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn)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插在原開始結(jié)點(diǎn)之前，頭結(jié)點(diǎn)之后3以下代碼是實現(xiàn)在單鏈表L的第i個位置插入元素e,請將程序補(bǔ)充完整。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 個結(jié)點(diǎn) 5if (p=NULL) /未找到位序為i-1的結(jié)點(diǎn)return 0;else /找到位序為i-1的結(jié)點(diǎn)*p s=(LinkList *)malloc(sizeof(LinkList);/創(chuàng)建新結(jié)點(diǎn) *ss->d

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

38、gt;rear=e;return 1;第四章：6以下代碼是實現(xiàn)兩個字符串的連接，請將程序補(bǔ)充完整。SqStri ng Co ncat(SqStri ng s,SqStri ng t)SqStri ng str;int i;將 s.data0 s.datas.length-1復(fù)制到 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復(fù)制到 strreturn str;7 以下代碼是實現(xiàn)刪除一個字符串從位置開始的連續(xù)j

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

40、str.le ngth=return str;查找算法:&以下代碼是實現(xiàn)對長度為n的順序表R查找K的折半查找算法，請將程序補(bǔ)充完整。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) /繼續(xù)在Rlow.mid-1 中查找high=elselow=/繼續(xù)在Rmid+1.high 中查找return -1;排序算法：9 以下代碼是選擇排序算法，請將程序補(bǔ)充完整。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)在當(dāng)前無序區(qū) Ri.n-1 中選key最小的Rk;/k記下目前找到的最小關(guān)鍵字所在的位置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進(jìn)行

42、冒泡排序，請將程序補(bǔ)充完整。void BubbleSort(RecType R,i nt n)int i,j,k;RecType tmp;for (i=0;i< n_1;i+)for (j=;»訃-)/比較，找出本趟最小關(guān)鍵字的記錄if (Rj.key<Rj-1.key);R【il與Rj-1進(jìn)行交換，將最小關(guān)鍵字記錄前移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網(wǎng)，不能出現(xiàn)的拓?fù)湫蛄袨?()(C) 24135 (D) 21435(A) 12345(B) 12435題三 2 圖題三3圖4. 深度為k的完全二叉樹所含葉結(jié)點(diǎn)的個數(shù)最多為()(A) 2 k(B) 2 k-1(C) k(D) 2k5衡量查找算法效率的主要標(biāo)準(zhǔn)是(A)元素個數(shù) (B) 所需的存儲量(C)平均查找長度(D)算法難易程度四、應(yīng)用題1 將下列森林轉(zhuǎn)化為二叉樹2對下圖進(jìn)行如下操作：(1)寫出其鄰接矩陣。(2分)(4分)(2)按Kruskal算法求其最小生成樹，并寫

44、出相應(yīng)的邊集數(shù)組。3請畫出后序和中序序列相同的二叉樹的所有形態(tài)。(3分)32,13,49,4. 散列函數(shù)為H(k)=k%7，散列表的地址從 O-.- 6用線性探查法解決沖突，建立散列表ht。給定關(guān)鍵字序列為55, 22, 38, 21 。要求：(1)構(gòu)造散列表(只畫出表，不寫算法)0 (5分)(2 )求出平均查找長度。(2分)5. 用直接選擇排序方法對下列關(guān)鍵字進(jìn)行排序，請寫出每一趟排序的結(jié)果。(6分)68 45 20 90 15 10 50五、算法設(shè)計(在下列算法的橫線上填上適當(dāng)?shù)谋磉_(dá)式、語句或運(yùn)算符。每空3分，共30分)1. 在帶頭結(jié)點(diǎn)的head單鏈表的結(jié)點(diǎn)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?"不存在結(jié)點(diǎn)a"else ;2. 快速排序?qū)W習(xí)必備歡迎下載void qksort (int R , int p , int q) / 按遞增序?qū)?RpRq進(jìn)行快速排序 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);模擬試題二一、判斷題(下列各題，你認(rèn)為正確的，請在前面的括號內(nèi)打J，錯誤的打X。每小題 1分，共10分)()1.數(shù)據(jù)的存儲結(jié)構(gòu)獨(dú)立于計算機(jī)。()2.線性表簡稱為”順序表”。()3.對數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性。()4.從循環(huán)

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

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

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

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

51、錄2. 先序遍歷二叉樹設(shè)二叉樹用二叉鏈表表示，以t為根指針，二叉鏈表結(jié)點(diǎn)的類型為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 );模擬試題三一、判斷題(下列各題，你認(rèn)為正確的，請在前面的括號內(nèi)打"

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