《數(shù)據(jù)結(jié)構(gòu)》試題庫中的習題

1、數(shù)據(jù)結(jié)構(gòu)試題庫中的習題一、填空1、線性表的順序存儲是用一組_ 連續(xù)的空間單元實現(xiàn)數(shù)據(jù)元素的存儲。2、線性表的鏈式存儲是用_ 語句實現(xiàn)空間單元動態(tài)分配。3、頭結(jié)點地址指針為L的循環(huán)單鏈表，空表的判別標志是_ 。4、含有N 個結(jié)點的一棵完全二叉樹上，葉子結(jié)點的最小編號是_ 。5、高度為K的一棵完全二叉樹中，結(jié)點的總個數(shù)至少是_個；至多是 _個。6、圖的遍歷過程中，選擇出發(fā)頂點V0的次數(shù)，為該圖的_的個數(shù)。7、圖的鄰接表存儲適用于_ ，_，_ 。8、拓撲排序的功能是檢驗AOV網(wǎng)絡中是否存在。9、在拓撲排序過程中，若圖中沒有入度為零的結(jié)點，則此時_確定在該圖中存在回路。10、關鍵路徑的功能是計算_時間

2、；找出 _ 頂點；提供_ 策略。11、圖的遍歷輸出序列_唯一的。12、一個賦權(quán)圖的最小代價生成樹_唯一的。13、僅適用于有向圖存儲的存儲方法是_法。14、義表的頭元素可以是_元素，也可以是_元素；其尾元素只能是_ 元素。15、給出二叉樹的先根序序列和中根序序列，便能_的確定這棵二叉樹。16、先根序序列和中根序序列相同的二叉樹是樹中每個結(jié)點只有_孩子結(jié)點的二叉樹。17、后根序序列和中根序序列相同的二叉樹是樹中每個結(jié)點只有_孩子結(jié)點的二叉樹。18、先根序序列、中根序序列和后根序序列均相同的二叉樹是_樹或者是只有_個結(jié)點的二叉樹.l19、判定一棵線索二叉樹中未知結(jié)點P沒有左孩子的標志_ 。20、線索

3、二叉樹是利用結(jié)點中空閑字段來記錄_次序的二叉樹。21、在一棵中序線索二叉樹中已知結(jié)點P的左側(cè)插入一個新結(jié)點Y后仍然是一棵中序線索二叉樹的操作，主要是查找P的_前驅(qū)結(jié)點22、本書介紹的靜態(tài)查找方法有 _，_，_ ；其中，_ 需要記錄表是順序存儲且按關鍵字大小有序。23、二叉排序樹中刪除有左右孩子的結(jié)點P時，一般用P的_前驅(qū)或_ 后繼來帶替P的位置。24、含有N 個頂點E條邊的無向圖中，假設每個頂點和每條邊都占用一個存儲單元，采用鄰接表存儲方式，那么，共需要_ 單元。25、在一個圖中，若兩個頂點是鄰接的，那么，這兩個頂點之間至少存在_路徑。路徑長度為 _。26、在一個圖中，若兩個頂點間存在路徑，則

4、這兩個頂點 _ 是相鄰接。27、在對一個有向圖進行拓撲排序結(jié)束后，發(fā)現(xiàn)輸出頂點個數(shù)為0，那么，該圖一定是一個 圖。28、分塊查找的索引表中的關鍵字是_有序的。所以，在索引表中確定給定值所在塊時，可以用_查找方式。29、在構(gòu)造二叉排序樹時，若新結(jié)點插在左重結(jié)點左孩子的左分支上，則稱為 _型。用_旋轉(zhuǎn)的方法調(diào)整。30、哈希表查找，從原理上講，查找時間只與被查記錄的_有關，而與表的 _無關。31、影響哈希表查找時間的因素有_,_ 。32、哈希表查找的主要缺點是 _ ，解決的辦法通常有下列四種其一，_ ；其二，_；其三，_；其四，_。33、在實際工作中選擇小于1的目的是為了_沖突。 34、哈希表查找成

5、功的平均查找長度是對所有記錄查找成功時總的比較次數(shù)與 _的比值。35、哈希表查找不成功的平均查找長度是對所有記錄查找不成功時總的比較次數(shù)與 _的比值。36、排序時，若待排序記錄能一次全部調(diào)入內(nèi)存進行排序的方式，一般稱_ 排序。37、平均時間量級為O（）的排序方法有_，_，_。38、希爾排序是屬于_ ，但它不是穩(wěn)定排序。39、磁帶文件只能是 _。40、順序文件分為_文件_文件。它們分別對應于線性表的順序存儲和鏈式存儲。41、一棵M叉的樹中，結(jié)點的度最多有_種。42、一棵高度為N 的樹中，結(jié)點的最大 _為N。43、構(gòu)成森林的每棵子樹的根結(jié)點是 _關系。45、有序樹中每個結(jié)點的孩子結(jié)點的_是固定的。

6、46、一棵具有N個結(jié)點的完全二叉樹中，葉子結(jié)點的最大_為N。47、磁帶文件批處理時，待修改的原文件稱為_。所有的修改申請構(gòu)成一個_ 。這兩個文件是有序文件。它們利用的方式形成新 _。48、一棵二叉樹中結(jié)點的度有 _，_，_，三種。49、哈（霍、赫）夫曼樹中結(jié)點的度，只有_，_兩種。50、從連通圖的定義出發(fā)，樹是一個沒有 _的連通圖。51、B-樹的葉子結(jié)點為_結(jié)點，它們必須在_層上。52、除根為葉子結(jié)點外，根結(jié)點至少有 _棵子樹。53、M 階的B 樹中，非葉子結(jié)點上最多有_個關鍵字。54、 M 階的B 樹中，非葉子結(jié)點上最少有_個關鍵字。55、N階B+樹中，結(jié)點上有_個關鍵字。56、在B+樹上查

7、找記錄時，可以，從_開始按索引方式查找也可以從_開始按順序查找。57、在計算機科學中常用的數(shù)據(jù)結(jié)構(gòu)有_, _， _ ,_ 。58、棧的操作特點是 先進后出；隊列的操作特點是 先進先出。59、線性表的順序存儲，要求每個數(shù)據(jù)元素都占用 相同的存儲單元數(shù)。60、線性表的順序存儲可以用順序查找，也可以用_ 查找。61、線性表的順序存儲的缺點是在任意位置上 插入數(shù)據(jù)與刪除 數(shù)據(jù)費時間。62、在實際應用中，一般最多建立_ 級索引。63、線性表的順序存儲可以用順序查找，也可以用_查找。64、線性表的順序存儲的缺點是在任意位置上 插入 數(shù)據(jù)與 刪除 數(shù)據(jù)費時間。65、線性表的順序存儲是用一組 物理 連續(xù)的空間

8、單元實現(xiàn)數(shù)據(jù)元素的存儲。66、編寫在內(nèi)存中生成線性表（a1 a2 a3an ）的算法。(判斷表是否滿了)67、已知線性表（ a1 a2 a3an ）以順序的方式存儲在內(nèi)存，編寫在表中查找值為X的元素，若存在把它與其直接前驅(qū)元素交換，否則把X插到表尾的算法。并計算該算法的時間復雜性.（如果是a1就不交換）（可用while語句做）68、編寫把線性表（ a1 a2 a3an ）的順序完全倒置的算法。并計算該算法的時間復雜性及決定時間復雜性的語句頻度。(對稱交換)69編寫把從線性表（ a1 a2 a3an ）中值為X 的元素開始到的所有元素順序倒置的算法。70、線性表的鏈式存儲C語言是用 語句實現(xiàn)空間

9、單元動態(tài)分配。71、設一線性表的順序存儲，總存儲容量為M ，其指針的變化范圍為。(0M-1)72、線性表的順序存儲，要求每個數(shù)據(jù)元素都占用 的存儲單元。73、頭結(jié)點地址指針為L的循環(huán)單鏈表，空表的判別標志是 。74、頭結(jié)點地址指針為L1的雙循環(huán)鏈表，空表的判別標志是 。75、含有N 個結(jié)點的一棵完全二叉樹上，葉子結(jié)點的最小編號是_。76、后根序序列和中根序序列相同的二叉樹是樹中每個結(jié)點只有 左 孩子結(jié)點的二叉樹。77、先根序序列、中根序序列和后根序序列均相同的二叉樹是 空 樹或者是只有 一 個結(jié)點的二叉樹。78、判定一棵線索二叉樹中未知結(jié)點P沒有左孩子的標志是 。79、線索二叉樹是利用結(jié)點中空

10、閑字段來記錄 次序的二叉樹。80、高度為K的一棵完全二叉樹中，結(jié)點的總個數(shù)至少是 個；至多是 個。給出二叉樹的先根序序列和中根序序列，便能 唯一 的確定這棵二叉樹。81、先根序序列和中根序序列相同的二叉樹是樹中每個結(jié)點只有 左 孩子結(jié)點的二叉樹。82、在一棵中序線索二叉樹中已知在結(jié)點P的左側(cè)插入一個新結(jié)點Y后仍然是一棵中序線索二叉樹的操作，主要是查找P的 前驅(qū)結(jié)點。83、高度為K的一棵完全二叉樹中，結(jié)點的總個數(shù)至少是 個；至多是 個。84、一棵M叉的樹中，結(jié)點的度最多有 種。85、一棵高度為N 的樹中，結(jié)點的最大 為N。86、一棵具有N個結(jié)點的完全二叉樹中，葉子結(jié)點的最大_為N。87、構(gòu)成森林

11、的每棵子樹的根結(jié)點是 兄弟 關系。88、有序樹中每個結(jié)點的孩子結(jié)點的 是固定的。89、含有N 個結(jié)點的一棵完全二叉樹上，葉子結(jié)點的最小編號是 。二、完成下列各題1、知A為二維數(shù)組，A-1 2，-2 3，按順序存儲，基址為999，每個元素都占用4個存儲單元，分別計算元素A（-1，-1）按行（列）優(yōu)先存儲的地址號。（寫出計算公式）2、知S=“aabbbccaabccaabc”, t =xxyy; m=ASSIGN( m, SUBSTR ( S ,LEN(t);i =INDEX( m,SUBSTR(S,6,LEN(t);求 REPLACE( m, SUBSTR(m,i,LEN(t),t) = ?3、

12、知廣義表A= (a),b,(d,(f),c),(e),g,(h),求A的長度與深度；4） 設有abcd，按順序進入一個棧，試寫出所有可能的輸出序列。5 ）設有abcde,經(jīng)過一個棧的處理得到輸出序列為cdbea 。假設，用P代表一次進棧操作，Q代表一次退棧操作。要求，寫出用PQ序列表示得到上述輸出結(jié)果的過程。6 ）假設三維數(shù)組A，它的各維界偶分別為（4，9），（-1，5）， （-9，-2），基地址為20，每個元素占三個存儲單元，試計算元素A6，0，-5的存儲位置。7 ）寫出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的運算結(jié)果。畫出A的

13、圖形表示及一種存儲結(jié)構(gòu)圖；寫出用求頭、尾元素的方式求出單元素h的過程。8、知一棵二叉樹的先根序、中根序序列分別為123456789，243168975，試畫出這棵二叉樹。9、知一棵完全二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，求該二叉樹的葉子結(jié)點個數(shù)。10、知一有向圖G，用n*n維鄰接矩陣表示，據(jù)此回答下列問題：1）該圖中邊的條數(shù)為多少？2）任一頂點的V的入度、出度是多少？3）若用鄰接表方式存儲圖G，應構(gòu)成多少個單鏈表？11、知一無向圖G，用n*n維鄰接矩陣表示，據(jù)此回答下列問題：1）該圖中邊的條數(shù)為多少？2）任一頂點的V度是多少？3）若用鄰接表方式存儲圖G，應構(gòu)成多少個單鏈表？12、假設N 為

14、一棵結(jié)點的度只有0和2的二叉樹中葉子結(jié)點的個數(shù)，M 為樹中結(jié)點的總個數(shù)，證明：M = 2*N 1。13、設一棵具有N 個結(jié)點的二叉樹用鏈式存儲，每個結(jié)點都含有左右孩子指針域和數(shù)據(jù)域，證明：該樹中共空閑N + 1個字段。14、知算術(shù)表達式為A*（B C）/E+ F*G H/（I + J），用學過的方法把它劃成一棵二叉樹。然后，再畫成按后序遍歷的線索二叉樹。15、知要傳輸?shù)臄?shù)據(jù)為字符串“AABBBBAAAACCCDDCC”，試畫出哈夫曼樹并求出數(shù)據(jù)中每種符號的哈夫曼編碼。16、知A，B，C，D，E為高度為3的一棵三叉樹上的結(jié)點，也是由這棵三叉樹轉(zhuǎn)換成的高度為4的一棵二叉樹上的結(jié)點，試畫出滿足上述兩

15、條件的所有三叉樹和二叉樹。17、知關鍵字集合（60，70，50， 40，30， 55，58）按順序輸入構(gòu)成一棵平衡二叉排序樹，畫出中間出現(xiàn)的各不平衡樹，并說明屬于何種類型；畫出最后的平衡二叉排序樹。18、判斷關鍵字集合（20，45，60，55，70，90，80，75）是否是堆樹，若不是畫出按順序輸入構(gòu)成的樹及整理成的堆樹。然后再畫出輸出一個排序結(jié)果的樹及調(diào)整后的堆。19、設某系學生舉辦運動會，參加同學的學號為（9301，9382，9372，9324，9345，9248，9262，9207，9223，9246，9152，9162，9109，9147，9118）。試畫出其塊大小為5的分塊查找的數(shù)據(jù)

16、結(jié)構(gòu)圖。20、設關鍵字集合（16，87，54，70，75，26，63，29，32，52，53，78），a = 0、75，設計一種散列函數(shù)，將它們進行散列，畫出散列表并計算查找成功時的平均查找長度。21、在實際工作中順序棧有兩種，一種是我們講過的棧頂移動的棧。另一種是棧底移動的棧。但一般都不用第二種方式，請回答為什么？22、設有abcd，按順序進入一個棧，試寫出所有可能的輸出序列。23、高度為K的一棵完全二叉樹中，結(jié)點的總個數(shù)最多是多少？最少是多少？24、設一棵滿二叉樹中，結(jié)點的總個數(shù)為20 40間的一個素數(shù)，問滿二叉樹中共有多少個葉子結(jié)點？25、一棵完全二叉樹中結(jié)點的總個數(shù)是一個偶數(shù)，問該完全

17、二叉樹中有多少個度為一的結(jié)點？26、設一棵完全二叉樹中結(jié)點i的堂兄弟結(jié)點的編號是2i+3 ，問該堂兄弟結(jié)點的雙親結(jié)點編號是多少？27、知A為二維數(shù)組，A-1 2，-2 3，按順序存儲，基址為999每個元素都占用4個存儲單元，分別計算元素A（-1，-1）按行（列）優(yōu)先存儲的地址號。（寫出計算公式）28、假設三維數(shù)組A，它的各維界偶分別為（4，9），（-1，5）， （-9，-2），基地址為20，每個元素占三個存儲單元，試計算元素A6，0，-5的存儲位置。29、寫出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的運算結(jié)果。30、設有abcde,

18、經(jīng)過一個棧的處理得到輸出序列為cdbea 假設，用P代表一次進棧操作，Q代表一次退棧操作。要求，寫出用PQ序列表示得到上述輸出結(jié)果的過程。31、一棵完全二叉樹中的某個結(jié)點，如果沒有左孩子結(jié)點，則其一定沒有右孩子。這種說法正確嗎？32、具有N個結(jié)點的一棵完全二叉樹中，編號最小的葉子結(jié)點的編號是多少？33、知A為二維數(shù)組，A-1 2，-2 3，按順序存儲，基址為999每個元素都占用4個存儲單元，分別計算元素A（-1，-1）按行（列）優(yōu)先存儲的地址號。（寫出計算公式）34、已知下邊給出的兩棵二叉樹是由森林轉(zhuǎn)換成的，現(xiàn)要求畫出原森林。35、用迪杰斯特拉算法，求右下圖中從頂點V1到其他各頂點的最短路徑，

19、要求寫出： 無圖（1）網(wǎng)的帶權(quán)鄰接矩陣；（2）求最短路徑的計算過程。36、利用深度優(yōu)先搜索的方法編寫求無向圖中通過給定頂點VK的簡單回路的算法。37、利用廣度優(yōu)先搜索思想編寫求無向圖中從V1頂點到VK頂點之間的最短路徑（指邊的條數(shù)）的算法。38、根據(jù)右下圖的AOE網(wǎng)絡完成各題：（1）求每個頂點的最早、晚時間； 無圖（2）寫出關鍵頂點；（3）是否有哪項活動減少時間后能使整個工期縮短。39、假設三維數(shù)組A，它的各維界偶分別為（4，9），（-1，5）， （-9，-2），基地址為20，每個元素占三個存儲單元，試計算元素A6，0，-5的存儲位置。40、寫出head(tail(head(a,b),c,d)

20、和tail(head(tail(a,(b,c,d)各自的運算結(jié)果。41、已知T為一棵二叉樹的根結(jié)點，按先序遍歷該樹的輸出序列為ABDFGHCE，按中序遍歷該樹的輸出序列為BFDHGAEC，要求畫出這棵二叉樹。1、已知L 為單鏈表的頭結(jié)點的地址指針，編寫把L從第i個結(jié)點處分開形成兩個帶頭結(jié)點的單鏈表的算法。第1個結(jié)點為新表結(jié)點。2、編寫把一個值為X的結(jié)點插到表中地址為Y的結(jié)點之前的算法。3、已知L 為單鏈表的頭結(jié)點的地址指針，數(shù)據(jù)結(jié)點值遞增有序。編寫把表中從值大于X的結(jié)點開始到小于值為Y的結(jié)點之間 的所有結(jié)點的順序完全倒置的算法。4、已知L 為單鏈表的頭結(jié)點的地址指針，表中結(jié)點的值都是正整數(shù)，編

21、寫把表中值為奇數(shù)的所有結(jié)點從表中刪除并生成一個新的帶頭結(jié)點的單鏈表的算法。（要求用的時間較少）5、已知L 為單鏈表的頭結(jié)點的地址指針，編寫把表中值X的結(jié)點的直接前驅(qū)結(jié)點刪除的算法。6、已知L為循環(huán)單鏈表的頭結(jié)點指針，且每個結(jié)點都有一個空閑的前驅(qū)指針域，要求編寫一個算法把該表變?yōu)檠h(huán)雙鏈表。7、已知一個循環(huán)單鏈表，要求編寫刪除表中地址為Y的結(jié)點的直接前驅(qū)結(jié)點的算法。8、已知L為循環(huán)單鏈表的頭結(jié)點指針，要求編寫把表從地址為Y的結(jié)點處分開，形成兩個循環(huán)單鏈表的算法。Y作為新表的第一個結(jié)點。9、編寫把一個循環(huán)雙鏈表中已知結(jié)點P與其直接前驅(qū)結(jié)點位置交換的算法。（要求只用一個輔助空間P）10、已知一個循環(huán)

22、單鏈表的尾結(jié)點地址P，問在該鏈表中能否執(zhí)行首部刪除、尾部插入結(jié)點的操作？如何實現(xiàn)？11、完成兩個棧的設計以及進、退棧的算法。12、完成將迷宮的算法編寫成C 語言的程序。13、編寫鏈式棧的進、退棧算法。14、已知L為循環(huán)單鏈表的頭結(jié)點地址指針，AV為另一單鏈表的第一個結(jié)點地址指針（如圖示），要求用最少的時間、用最少的操作完成把L表中的全部結(jié)點鏈接到鏈表AV中，并寫出相應的算法。15、求出子串NG在字符串JIAOTONG中的位置序號。ab圖 三個盤子移動ca c b b cL AV16、由下圖1知，此時隊列中的空間并非全部都被占用（若用循環(huán)隊列，這些空間可以被重新使用），現(xiàn)在，希望你想另外一種方法

23、，也能使這些空間可以被重新使用。并設計實現(xiàn)進、出隊列的算法。17、編寫一個計算循環(huán)隊列中數(shù)據(jù)元素個數(shù)的算法。（圖2）18、設有m個連續(xù)的存儲單元，現(xiàn)分成由一個棧和一個隊列使用。棧和隊列的容量不知且不相等。要求在任何時刻，只要棧和隊列中已存儲的元素個數(shù)之和小于m，便能滿足用戶的存放數(shù)據(jù)的申請。試設計出 F0 16 3 5 47 2CG D F EQ. front圖2圖1這種結(jié)構(gòu)并寫出進、出棧的算法。19、已知T為一棵二叉樹的根結(jié)點，設計把樹中每個結(jié)點的左右孩子結(jié)點交換的算法。20、已知T為一棵二叉樹的根結(jié)點，設計把樹中每個單分支結(jié)點，用添加數(shù)據(jù)值為0的新結(jié)點變?yōu)殡p分支結(jié)點的算法。21、已知T為一

24、棵二叉樹的根結(jié)點，設計把樹中值為X的結(jié)點找出，并將它的兩個孩子分別作為根生成兩棵子樹的算法。22、已知T為一棵二叉樹的根結(jié)點，設計計算該樹高度（深度）的算法。23、已知T為一棵二叉樹的根結(jié)點，樹中結(jié)點的數(shù)據(jù)值都是正整數(shù)其中只有一個值是寄數(shù)，設計找出該結(jié)點的算法。24、已知T為一棵二叉樹的根結(jié)點，設計計算該樹中結(jié)點總個數(shù)的算法。25、已知T為一棵中序線索二叉樹的根結(jié)點指針，P為樹中一個結(jié)點的地址，設計把一個新結(jié)點X插到結(jié)點P左側(cè)（即作為P的左孩子）的算法。26、設計把一個新結(jié)點X插到結(jié)點P右側(cè)（即作為P的右孩子）的算法。27、若把第一題中的新結(jié)點X改成是以X為根的一棵中序線索二叉樹，設計把以X為

25、根的一棵中序線索二叉樹，插到結(jié)點P左側(cè)（或右側(cè)）的算法。四術(shù)語1. 數(shù)據(jù)結(jié)構(gòu)2. 邏輯結(jié)構(gòu)3. 存儲結(jié)構(gòu)4. 算法5. 時間復雜度6. 空間復雜度7. 數(shù)據(jù)類型8. 抽象數(shù)據(jù)類型9. 線性表10. 循環(huán)鏈表11. 雙向鏈表12. 靜態(tài)鏈表13. 棧14. 循環(huán)隊列15. 隊列16. 串17. 子串18. 廣義表19. 二叉樹20. 滿二叉樹21. 中序遍歷22. 線索23. 線索化24. 先序遍歷25. 后序遍歷26. 水平遍歷27. 樹的深度28. 樹的度29. 樹30. 完全二叉樹31. 前綴碼32. 哈夫曼編碼33. 最優(yōu)二叉樹34. 最小生成樹35. 完全有向圖36. 完全無向圖37.

26、 廣度遍歷38. 深度遍歷39. 生成樹40. 生成森林41. 環(huán)（簡單環(huán)）42. 路徑43. 極大連通子圖44. 連通圖45. 拓撲排序46. 關鍵路徑47. 最短路徑48. 折半查找49. 索引順序表50. 二叉排序樹51. 平衡因子52. 平衡二叉樹53. 平衡旋轉(zhuǎn)54. LR型平衡旋轉(zhuǎn)55. LL型平衡旋轉(zhuǎn)56. RL型平衡旋轉(zhuǎn)57. RR型平衡旋轉(zhuǎn)58. 哈希函數(shù)59. 哈希表60. shell排序61. 氣泡排序法62. 選擇排序63. 快速排序64. 堆排序65. 交換排序66. 插入排序67. 穩(wěn)定排序68. 不穩(wěn)定排序69. 內(nèi)部排序70. 歸并排序71. 基數(shù)排序72. 外

27、部排序五簡答1、什么是數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)項？何謂主關鍵字？2、什么是數(shù)據(jù)結(jié)構(gòu)？什么是存儲結(jié)構(gòu)？它們各有多少種形式？3、衡量一個算法性能好壞的標準是什么？5、如果兩個算法的平均時間復雜度相同，能否說，這兩個算法的實際執(zhí)行時間一定相等？6、試描述數(shù)據(jù)結(jié)構(gòu)的概念與程序設計語言中數(shù)據(jù)類型概念的區(qū)別。1、 什么是數(shù)據(jù)結(jié)構(gòu)？什么是存儲結(jié)構(gòu)？它們各有多少種形式？2、 數(shù)據(jù)結(jié)構(gòu)是如何分類的？舉出你所學的六種并分類。3、 衡量一個算法性能好壞的標準是什么？4、 抽象數(shù)據(jù)類型如何描述，以線性表為例說明。5、 描述以下三個概念的區(qū)別：哨兵指針，哨兵結(jié)點，首結(jié)點（第一個元素結(jié)點）。6、 算法與程序的主要區(qū)別是什么？

28、7、 如果兩個算法的平均時間復雜度相同，能否說，這兩個算法的實際執(zhí)行時間一定相等？（不一定）。8、 線性表、棧、隊列的區(qū)別與聯(lián)系。9、 線性表的順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)在操作上的特點是什么？10、 線性表與串的區(qū)別與聯(lián)系。11、 靜態(tài)鏈表與動態(tài)鏈表的不同點與相同點。12、 簡述隊列在順序存儲結(jié)構(gòu)上實現(xiàn)的特點。13、 簡述二棧共享空間時的數(shù)據(jù)結(jié)構(gòu)、操作實現(xiàn)過程及優(yōu)點。14、 鏈式結(jié)構(gòu)存儲串時，每個結(jié)點可存放多個字符，當插入和刪除子串時操作如何實現(xiàn)？15、 如何用一維數(shù)組存儲對稱矩陣？16、 如何用一維數(shù)組存儲下三角矩陣？17、 稀疏矩陣有幾種存儲方式分別敘述。18、 已知二叉樹的中序遍歷和先序遍歷結(jié)果，如何確定這棵二叉樹？19、 簡述哈夫曼算法。20、 樹的存儲結(jié)構(gòu)有幾種？簡述之。21、 一棵完全二叉樹中的某個結(jié)點，如果沒有左孩子結(jié)點，則其一定沒