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

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

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

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

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

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

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

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

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

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

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

11、的每棵子樹的根結(jié)點(diǎn)是 兄弟 關(guān)系。88、有序樹中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的 是固定的。89、含有N 個(gè)結(jié)點(diǎn)的一棵完全二叉樹上，葉子結(jié)點(diǎn)的最小編號(hào)是 。二、完成下列各題1、知A為二維數(shù)組，A-1 2，-2 3，按順序存儲(chǔ)，基址為999，每個(gè)元素都占用4個(gè)存儲(chǔ)單元，分別計(jì)算元素A（-1，-1）按行（列）優(yōu)先存儲(chǔ)的地址號(hào)。（寫出計(jì)算公式）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） 設(shè)有abcd，按順序進(jìn)入一個(gè)棧，試寫出所有可能的輸出序列。5 ）設(shè)有abcde,經(jīng)過一個(gè)棧的處理得到輸出序列為cdbea 。假設(shè)，用P代表一次進(jìn)棧操作，Q代表一次退棧操作。要求，寫出用PQ序列表示得到上述輸出結(jié)果的過程。6 ）假設(shè)三維數(shù)組A，它的各維界偶分別為（4，9），（-1，5）， （-9，-2），基地址為20，每個(gè)元素占三個(gè)存儲(chǔ)單元，試計(jì)算元素A6，0，-5的存儲(chǔ)位置。7 ）寫出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的運(yùn)算結(jié)果。畫出A的

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

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

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

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

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

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

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

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

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

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

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

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

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

26、成樹35. 完全有向圖36. 完全無向圖37. 廣度遍歷38. 深度遍歷39. 生成樹40. 生成森林41. 環(huán)（簡單環(huán)）42. 路徑43. 極大連通子圖44. 連通圖45. 拓?fù)渑判?6. 關(guān)鍵路徑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)部

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

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