數據結構試題庫及答案第一章一、選擇題、研究數據結構就是研究（）。.數據的邏輯結構 .數據的存儲結構.數據的邏輯結構和存儲結構 .數據的邏輯結構、存儲結構及其基本操作、算法分析的兩個主要方面是（）。.空間復雜度和時間復雜度 .正確性和簡單性.可讀性和文檔性.數據復雜性和程序復雜性、具有線性結構的數據結構是（）。.圖 .樹 .二叉樹 .棧、計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備輸入、輸出、（）等個特性。.可執行性、可移植性和可擴充性 .可執行性、有窮性和確定性.確定性、有窮性和穩定性 .易讀性、穩定性和確定性、下面程序段的時間復雜度是（）。(<) (<) [][]*; .().() .(*) .()、算法是（）。.計算機程序 .解決問題的計算方法.排序算法.解決問題的有限運算序列、某算法的語句執行頻度為（）,其時間復雜度表示（）。.() .() .() .()、下面程序段的時間復雜度為（）。 ; (<) *;.().() .().() 、數據結構是一門研究非數值計算的程序設計問題中計算機的數據元素以及它們之間的（）和運算等的學科。.結構 .關系 .運算 .算法、抽象數據類型的三個組成部分分別為（）。.數據對象、數據關系和基本操作.數據元素、邏輯結構和存儲結構 .數據項、數據元素和數據類型.數據元素、數據結構和數據類型、下列程序段的時間復雜度為（）。; (>()*());.() . . () .().算法分析的目的是（）)找出數據結構的合理性)研究算法中的輸入和輸出的關系)分析算法的效率以求改進)分析算法的易懂性和文檔性.數據結構中，與所使用的計算機無關的是數據的結構；)存儲)物理)邏輯)物理和存儲二、填空題.數據結構被形式地定義為（,），其中是數據元素的有限集合，是上的關系有限集合。.數據結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。.程序段“(<)*;”的時間復雜度為()。.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。．在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有個前驅結點；最后一個結點沒有后繼結點，其余每個結點有且只有個后續結點。.在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有個前驅結點；葉子結點沒有后繼結點，其余每個結點的后繼結點數可以任意多個。.在圖形結構中，每個結點的前驅結點數和后繼結點數可以任意多個。．數據的存儲結構可用兩種基本的存儲方法表示，它們分別是順序、鏈式。.一個算法的效率可分為時間效率和空間效率。三、簡答題什么是數據結構什么是數據類型？答：簡單地說，數據結構定義了一組按某些關系結合在一起的數據元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了一組操作。.;.;(;<;)(;<;)[][];;(*)..(;<;)(;<;)[][];(*).;.;(;<;)(;<;);(*).;(<)*;()第二章線性表一、選擇題、若長度為的線性表采用順序存儲結構，在其第個位置插入一個新元素算法的時間復雜度（）。.() () .() ()、若一個線性表中最常用的操作是取第個元素和找第個元素的前驅元素，則采用（）存儲方式最節省時間。.順序表 .單鏈表 .雙鏈表 .單循環鏈表、具有線性結構的數據結構是（）。.圖 .樹 .二叉樹.棧、在一個長度為的順序表中，在第個元素之前插入一個新元素時，需向后移動（）個元素。. . . .、非空的循環單鏈表的尾結點滿足（）。.> .>..、鏈表不具有的特點是（）。.可隨機訪問任一元素 .插入刪除不需要移動元素 .不必事先估計存儲空間 .所需空間與線性表長度成正比、線性表采用鏈式存儲時，結點的存儲地址（）。.必須是連續的.必須是不連續的.連續與否均可.和頭結點的存儲地址相連續、在一個長度為的順序表中刪除第個元素，需要向前移動（）個元素。. .. .、線性表是個（）的有限序列。.表元素.字符 .數據元素.數據項 、從表中任一結點出發，都能掃描整個表的是（）。.單鏈表 .順序表.循環鏈表 .靜態鏈表、在具有個結點的單鏈表上查找值為的元素時，其時間復雜度為（）。.() .().().()、線性表(,……)，下列說法正確的是（）。.每個元素都有一個直接前驅和一個直接后繼.線性表中至少要有一個元素.表中諸元素的排列順序必須是由小到大或由大到小.除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅和直接后繼、一個順序表的第一個元素的存儲地址是，每個元素的長度為，則第個元素的存儲地址是（）。. . . .、在線性表的下列存儲結構中，讀取元素花費的時間最少的是（）。.單鏈表 .雙鏈表 .循環鏈表.順序表、在一個單鏈表中，若刪除所指向結點的后續結點，則執行（）。.>>>;.>>>>;.>;.>>;、線性表的順序存儲結構是一種（）存儲結構。.隨機存取.順序存取 .索引存取 .散列存取 、順序表中，插入一個元素所需移動的元素平均數是（）。.() . . .()、循環鏈表的主要優點是（）。.不再需要頭指針.已知某結點位置后能容易找到其直接前驅.在進行插入、刪除運算時能保證鏈表不斷開.在表中任一結點出發都能掃描整個鏈表、在下列對順序表進行的操作中，算法時間復雜度為()的是（）。.訪問第個元素的前驅（<） .在第個元素之后插入一個新元素().刪除第個元素().對順序表中元素進行排序、已知指針和分別指向某單鏈表中第一個結點和最后一個結點。假設指針指向另一個單鏈表中某個結點，則在所指結點之后插入上述鏈表應執行的語句為（）。.>>；>；.>；>>；.>>；>；.>；>>；、在以下的敘述中，正確的是（）。.線性表的順序存儲結構優于鏈表存儲結構.線性表的順序存儲結構適用于頻繁插入刪除數據元素的情況.線性表的鏈表存儲結構適用于頻繁插入刪除數據元素的情況.線性表的鏈表存儲結構優于順序存儲結構、在表長為的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個數為（）。.() . .() .、在一個單鏈表中，已知所指結點是所指結點的前驅結點，若在和之間插入一個結點，則執行（）。.>>;>; .>>>; .>>; .>>; 、在單鏈表中，指針指向元素為的結點，要刪除的后繼,則實現語句是（）。.>;.>>>;.>; .>>;、帶頭結點的單鏈表為空的判定條件是（）。. .>.>.二、填空題、設單鏈表的結點結構為（）。已知指針指向單鏈表中的結點，指向新結點，欲將插入到結點之后，則需要執行的語句：；。答案：>> >、線性表的邏輯結構是，其所含元素的個數稱為線性表的。答案：線性結構長度、寫出帶頭結點的雙向循環鏈表為空表的條件。答案：>>、帶頭結點的單鏈表為空的條件是。答案：>、在一個單鏈表中刪除所指結點的后繼結點時，應執行以下操作：>;>;答案：>三、判斷題、單鏈表不是一種隨機存儲結構。、在具有頭結點的單鏈表中，頭指針指向鏈表的第一個數據結點。、用循環單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。、順序存儲方式只能用于存儲線性結構。、在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。、鏈式存儲的線性表可以隨機存取。、在單鏈表中，要訪問某個結點，只要知道該結點的地址即可；因此，單鏈表是一種隨機存取結構。四、程序分析填空題、函數實現返回單鏈表的第個元素，請在空格處將算法補充完整。(){ ；；>; (<){();}(>);();;}答案：()>()>、函數實現單鏈表的插入算法，請在空格處將算法補充完整。(){*,*; ; (()(<)){>;; } (>); (*)(()); >;();(); ;}**答案：()>>()>、函數實現單鏈表的刪除算法，請在空格處將算法補充完整。(){*,*;;;((（）)(<)){>;}(>>);>;（）;>;();;}**答案：()>()>>、寫出算法的功能。(){; ; () {>; ; } (); }答案：求單鏈表的長度第三章棧和隊列一、選擇題、一個棧的輸入序列為：，，，，，則棧的不可能輸出的序列是（）。....、判斷一個循環隊列（最多個元素）為滿的條件是（）。.>>.>>.>(>).>(>)、設計一個判別表達式中括號是否配對的算法，采用（）數據結構最佳。.順序表 .鏈表.隊列.棧、一個棧的輸入序列為：，則棧的不可能輸出的序列是（）。.... .、若用一個大小為的數組來實現循環隊列，且當和的值分別為，。當從隊列中刪除一個元素，再加入兩個元素后，和的值分別為（）。.和.和.和.和、隊列的插入操作是在（）。.隊尾 .隊頭 .隊列任意位置 .隊頭元素后、一個順序棧，其棧頂指針為，則將元素入棧的操作是（）。.*>>;.>;*>;.*>.>;、表達式*()的后綴表達式是（）。. .* .* .*、將遞歸算法轉換成對應的非遞歸算法時，通常需要使用（）來保存中間結果。.隊列.棧.鏈表.樹、棧的插入和刪除操作在（）。.棧底.棧頂 .任意位置 .指定位置、五節車廂以編號，，，，順序進入鐵路調度站（棧），可以得到（）的編組。 .，，，， .，，，， .，，，，.，，，，、判定一個順序棧（?？臻g大小為）為空的條件是（）。.> .>.>.>、在一個鏈隊列中，和分別為頭指針和尾指針，則插入一個結點的操作為（）。.>.>.>;.>;、一個隊列的入隊序列是，，，，則隊列的出隊序列是（）。.，，，.，，，.，，，.，，，、依次在初始為空的隊列中插入元素以后，緊接著做了兩次刪除操作，此時的隊頭元素是（）。. . ..、正常情況下，刪除非空的順序存儲結構的堆棧的棧頂元素，棧頂指針的變化是（）。.不變 . . .、判斷一個循環隊列（空間大小為）為空的條件是（）。.>> .>>.>>.>>、當用大小為的數組存儲順序循環隊列時，該隊列的最大長度為（）。. ...、隊列的刪除操作是在（）。.隊尾.隊頭 .隊列任意位置 .隊頭元素后、若讓元素，，依次進棧，則出棧次序不可能是（）。.，， .，，.，，.，，、循環隊列用數組[，]存放其元素值，已知其頭尾指針分別是和，則當前隊列中的元素個數是（）。.(). . .、在解決計算機主機和打印機之間速度不匹配問題時，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則從該緩沖區中取走數據打印。該緩沖區應該是一個（）結構。.堆棧 .隊列 .數組 .線性表、棧和隊列都是（）。.鏈式存儲的線性結構.鏈式存儲的非線性結構.限制插入刪除位置的線性結構.限制存取點的非線性結構、在一個鏈隊列中，假定和分別為隊頭指針和隊尾指針，刪除一個結點的操作是（）。.> .>.>.>、隊和棧的主要區別是（）。.邏輯結構不同.存儲結構不同.所包含的運算個數不同.限定插入和刪除的位置不同二、填空題、設棧和隊列的初始狀態為空，元素依次通過棧，一個元素出棧后即進入隊列，若個元素出隊的序列是，則棧的容量至少應該是。答案：、一個循環隊列的存儲空間大小為,其隊頭和隊尾指針分別為和，則循環隊列中元素的個數為：。答案：()、在具有個元素的循環隊列中，隊滿時具有個元素。答案：、設循環隊列的容量為，現經過一系列的入隊和出隊操作后，為，為，則隊列中元素的個數為。答案：、已知循環隊列的存儲空間大小為，且當前隊列的頭指針和尾指針的值分別為和，且該隊列的當前的長度為。答案：三、判斷題、棧和隊列都是受限的線性結構。、以鏈表作為棧的存儲結構，出棧操作必須判別棧空的情況。四、程序分析填空題、已知棧的基本操作函數： (*);構造空棧 (*)判斷?？?*)入棧 (**)出棧函數實現十進制數轉換為八進制數，請將函數補充完整。(){ (); (“”); (){（）; ;}(（）){ ();(“”);}}答案：（）() （）()、寫出算法的功能。(**){ (>>) ; *>[>];>(>); ;}答案：出隊。刪除順序隊列的隊頭元素，并將被刪元素保存至形參第四章串一、選擇題、設有兩個串和，求串在中首次出現位置的運算稱作（）。.連接 .求子串.模式匹配.判斷子串、串與普通的線性表相比較，它的特殊性體現在（）。.順序的存儲結構 .鏈式存儲結構.數據元素是一個字符 .數據元素任意、空串和空格串（）。.相同.不相同.可能相同.無法確定、設()是求中從第個字符開始的連續個字符組成的子串的操作，則對于’’，()（）。.‘’.‘’.‘’ .‘’第五章數組和廣義表一、選擇題、設廣義表((，，))，則的長度和深度分別為（）。.和 .和.和 .和、廣義表(())的表尾是（）。. .().() .(())、稀疏矩陣的常見壓縮存儲方法有（）兩種。.二維數組和三維數組 .三元組和散列表.三元組和十字鏈表.散列表和十字鏈表、一個非空廣義表中的數據元素（）。.不可能是子表 .只能是子表.只能是原子.可以是子表或原子、廣義表(,(,()))的長度是（）。. . . .、采用稀疏矩陣的三元組表形式進行壓縮存儲，若要完成對三元組表進行轉置，只要將行和列對換，這種說法（）。.正確.錯誤 .無法確定 .以上均不對、廣義表()的表尾是（）。. .(). .()、常對數組進行兩種基本操作是（）。.建立和刪除.索引和修改.查找和修改 .查找與索引、對一些特殊矩陣采用壓縮存儲的目的主要是為了（）。.表達變得簡單.對矩陣元素的存取變得簡單.去掉矩陣中的多余元素.減少不必要的存儲空間的開銷、設有一個階的對稱矩陣，采用壓縮存儲方式，以行序為主存儲，為第一個元素，其存儲地址為，每元素占個地址空間，則的地址為（）。... .、設矩陣是一個對稱矩陣，為了節省存儲，將其下三角部分按行序存放在一維數組[()]中，對下三角部分中任一元素(>)，在一維數組的下標位置的值是（）。.() .().().()、廣義表(())的表頭是（）。. .(). .(())、稀疏矩陣一般的壓縮存儲方法有兩種，即（）。.二維數組和三維數組 .三元組和散列.三元組和十字鏈表 .散列和十字鏈表、假設以三元組表表示稀疏矩陣，則與如圖所示三元組表對應的×的稀疏矩陣是（注：矩陣的行列下標均從開始）（）。... .、以下有關廣義表的表述中，正確的是（）。.由個或多個原子或子表構成的有限序列 .至少有一個元素是子表.不能遞歸定義.不能為空表、對廣義表((),((),()))執行(((())))操作的結果是（）。...() .（）二、判斷題（錯）、廣義表中原子個數即為廣義表的長度。（錯）、一個稀疏矩陣采用三元組表示，若把三元組中有關行下標與列下標的值互換，并把和的值進行互換，則完成了矩陣轉置。（錯）、廣義表的長度是指廣義表中括號嵌套的層數。（√）、廣義表的深度是指廣義表中括號嵌套的層數。（√）、廣義表是一種多層次的數據結構，其元素可以是單原子也可以是子表。三、填空題、已知二維數組[][]采用行序為主方式存儲，每個元素占個存儲單元，并且第一個元素的存儲地址是([][])，則[][]的地址是([][])(*)*。、廣義表運算式(((),()))的結果是：()。、稀疏矩陣的壓縮存儲方式有：三元組和十字鏈表。四、綜合題、現有一個稀疏矩陣，請給出它的三元組表。答案：第六章樹一、選擇題、二叉樹的深度為，則二叉樹最多有（）個結點。. . . .、用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數組[]中，若結點[]有右孩子，則其右孩子是（）。.[].[].[] .[]、設為一棵二叉樹上的兩個結點，在中序遍歷時，在前面的條件是（）。.在的右方.在的左方.是的祖先 .是的子孫、設一棵二叉樹的中序遍歷序列：，后序遍歷序列：，則二叉樹先序遍歷序列為（）。. . . .、在一棵具有層的滿二叉樹中結點總數為（）。. . . .、由二叉樹的前序和后序遍歷序列（）惟一確定這棵二叉樹。.能.不能、某二叉樹的中序序列為，后序序列為，則其左子樹中結點數目為（）。. .. .、若以{}作為權值構造哈夫曼樹，則該樹的帶權路徑長度為（）。. .. .、將一棵有個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為，則編號為的結點的左孩子編號為（）。. . . .、表達式*()的后綴表達式是（）。. .* .* .*、對某二叉樹進行先序遍歷的結果為，中序遍歷的結果為，則后序遍歷的結果是（）。 ....、樹最適合用來表示（）。.有序數據元素.無序數據元素.元素之間具有分支層次關系的數據.元素之間無聯系的數據、假定在一棵二叉樹中，度為的結點數為，度為的結點數為，則葉子結點數為（）個。....、用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數組[]中，若結點[]有左孩子，則其左孩子是（）。.[] .[] .[] .[]、樹的先根序列等同于與該樹對應的二叉樹的（）。.先序序列.中序序列.后序序列.層序序列、按照二叉樹的定義，具有個結點的二叉樹有（）種。. .. .、由權值為，，，，的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。. . . .二、判斷題（對）、存在這樣的二叉樹，對它采用任何次序的遍歷，結果相同。（對）、中序遍歷一棵二叉排序樹的結點，可得到排好序的結點序列。（√）、一個含有個結點的完全二叉樹，它的高度是＋。（√）、完全二叉樹的某結點若無左孩子，則它必是葉結點。（√）、完全二叉樹某結點有右子樹，則必然有左子樹。三、填空題、具有個結點的完全二叉樹的深度是。、哈夫曼樹是其樹的帶權路徑長度最小的二叉樹。、在一棵二叉樹中，度為的結點的個數是，度為的結點的個數為，則有。、樹內各結點度的最大值稱為樹的度。四、代碼填空題、函數()實現二叉樹的中序遍歷，請在空格處將算法補充完整。(){ (){ (>); (“”>);(>); } }五、綜合題、假設以有序對<>表示從雙親結點到孩子結點的一條邊，若已知樹中邊的集合為{<>,<>,<>,<>,<>,<>,<>,<>,<>,<>},請回答下列問題：（）哪個結點是根結點？（）哪些結點是葉子結點？（）哪些結點是的祖先？（）哪些結點是的兄弟？（）樹的深度是多少？、假設一棵二叉樹的先序序列為，中序序列為，請畫出該二叉樹。、假設用于通訊的電文僅由個字母、、、、、、、組成，字母在電文中出現的頻率分別為：，，，，，，，。請為這個字母設計哈夫曼編碼。答案：、已知二叉樹的先序遍歷序列為，中序遍歷序列為，畫出二叉樹。答案：二叉樹形態、試用權集合{}構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。答案：*()*()*、已知權值集合為{}，要求給出哈夫曼樹，并計算帶權路徑長度。答案：()樹形態：()帶權路徑長度：()**()*、已知一棵二叉樹的先序序列：；中序序列：。畫出二叉樹的形態。答案：、一份電文中有種字符：，它們的出現頻率依次為，，，，，，完成問題：（）設計一棵哈夫曼樹；（畫出其樹結構）（）計算其帶權路徑長度；答案：()樹形態：()帶權路徑長度：****()*、已知某森林的二叉樹如下所示，試畫出它所表示的森林。答案：、有一分電文共使用個字符，它們的出現頻率依次為、、、、，試構造哈夫曼樹，并給出每個字符的哈夫曼編碼。、畫出與下圖所示的森林相對應的二叉樹，并指出森林中的葉子結點在二叉樹中具有什么特點。、如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。答案：先序：中序：后序：第七章圖一、選擇題、對于具有個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。....()、如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖一定是（）。.完全圖.連通圖 .有回路 .一棵樹、關鍵路徑是事件結點網絡中（）。.從源點到匯點的最長路徑 .從源點到匯點的最短路徑.最長的回路.最短的回路、下面（）可以判斷出一個有向圖中是否有環（回路）。.廣度優先遍歷.拓撲排序.求最短路徑 .求關鍵路徑、帶權有向圖用鄰接矩陣存儲，則頂點的入度等于中（）。.第行非無窮的元素之和.第列非無窮的元素個數之和.第行非無窮且非的元素個數 .第行與第列非無窮且非的元素之和、采用鄰接表存儲的圖，其深度優先遍歷類似于二叉樹的（）。.中序遍歷.先序遍歷.后序遍歷 .按層次遍歷、無向圖的鄰接矩陣是一個（）。.對稱矩陣.零矩陣.上三角矩陣.對角矩陣、鄰接表是圖的一種（）。.順序存儲結構.鏈式存儲結構.索引存儲結構.散列存儲結構、下面有向圖所示的拓撲排序的結果序列是（）。. . . .、在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。.入邊 .出邊 .入邊和出邊 .不是出邊也不是入邊、設()和()為兩個圖，如果則稱（）。.是的子圖 .是的子圖.是的連通分量.是的連通分量、已知一個有向圖的鄰接矩陣表示，要刪除所有從第個結點發出的邊，應（）。.將鄰接矩陣的第行刪除.將鄰接矩陣的第行元素全部置為.將鄰接矩陣的第列刪除 .將鄰接矩陣的第列元素全部置為、任一個有向圖的拓撲序列（）。.不存在 .有一個 .一定有多個.有一個或多個、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。. .. .、下列關于圖遍歷的說法不正確的是（）。.連通圖的深度優先搜索是一個遞歸過程.圖的廣度優先搜索中鄰接點的尋找具有“先進先出”的特征.非連通圖不能用深度優先搜索法.圖的遍歷要求每一頂點僅被訪問一次、帶權有向圖用鄰接矩陣存儲，則頂點的入度為中：（）。.第行非的元素之和.第列非的元素之和.第行非且非的元素個數 .第列非且非的元素個數、采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的（）。.先序遍歷.中序遍歷 .后序遍歷 .按層次遍歷、一個具有個頂點的有向圖最多有（）條邊。.×().×().×().、已知一個有向圖的鄰接表存儲結構如圖所示，根據深度優先遍歷算法，從頂點出發，所得到的頂點序列是（）。. .. .、以下說法正確的是（）。.連通分量是無向圖中的極小連通子圖.強連通分量是有向圖中的極大強連通子圖.在一個有向圖的拓撲序列中若頂點在頂點之前，則圖中必有一條弧<>.對有向圖，如果以任一頂點出發進行一次深度優先或廣度優先搜索能訪問到每個頂點，則該圖一定是完全圖、假設有向圖含個頂點及條弧，則表示該圖的鄰接表中包含的弧結點個數為（）。. ...*、設圖的鄰接矩陣為，則該圖為（）。.有向圖 .無向圖.強連通圖 .完全圖、任何一個無向連通圖的最小生成樹（）種。.只有一棵 .有一棵或多棵 .一定有多棵 .可能不存在、對于一個有向圖，若一個頂點的入度為,、出度為，則對應鄰接表中該頂點單鏈表中的結點數為（）。....、一個具有個頂點的有向圖中，所有頂點的入度之和與所有頂點的出度之和的差等于（）。. . . .、無向圖中一個頂點的度是指圖中（）。.通過該頂點的簡單路徑數.與該頂點相鄰接的頂點數.與該頂點連通的頂點數.通過該頂點的回路數二、填空題、個頂點的連通圖至少有邊。答案：條、一個連通圖的生成樹是一個，它包含圖中所有頂點，但只有足以構成一棵樹的條邊。答案：極小連通子圖、遍歷圖的基本方法有深度優先搜索和廣度優先搜索，其中是一個遞歸過程。答案：深度優先搜索、在無向圖的鄰接矩陣中，若[][]等于，則[][]等于。答案：、判定一個有向圖是否存在回路，可以利用。答案：拓撲排序、已知一個圖的鄰接矩陣表示，計算第個結點的入度的方法是。答案：鄰接矩陣中第列非元素的個數、個頂點的無向圖最多有邊。答案：*()、已知一個圖的鄰接矩陣表示，刪除所有從第個結點出發的邊的方法是。答案：將鄰接矩陣中第行所有元素的值置為、若以鄰接矩陣表示有向圖，則鄰接矩陣上第行中非零元素的個數即為頂點的。答案：第個結點的出度三、判斷題、圖的連通分量是無向圖的極小連通子圖。、一個圖的廣度優先生成樹是惟一的。、圖的深度優先遍歷序列和廣度優先遍歷序列不是惟一的。、鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數有關，而且與圖的邊數也有關。、從源點到終點的最短路徑是唯一的。、圖的生成樹是惟一的。四、綜合題、已知圖的鄰接矩陣如下所示：（）求從頂點出發的廣度優先遍歷序列；（）根據算法，求圖從頂點出發的最小生成樹，要求表示出其每一步生成過程。（用圖或者表的方式均可）。答案：()廣度優先遍歷序列：;,,;;()最小生成樹（算法）、設一個無向圖的鄰接矩陣如下圖所示：（）畫出該圖；（）畫出從頂點出發的深度優先生成樹；答案：()圖形態()深度優先搜索樹、寫出下圖中全部可能的拓撲排序序列。答案：，，，，，，，，，，，，，，，，，，，，，，，，，、網如下所示，求關鍵路徑。（要求標明每個頂點的最早發生時間和最遲發生時間，每條邊的最早發生時間和最遲發生時間并畫出關鍵路徑）答案：()頂點的最早發生時間和最遲發生時間：()關鍵路徑：（）邊的最早發生時間和最遲發生時間邊、已知圖如下所示，根據算法，構造最小生成樹。（要求給出生成過程）答案：算法求最小生成樹如下：、已知有向圖如下所示，請寫出該圖所有的拓撲序列。答案：拓撲排序如下：,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,、如下圖所示的網，求：（）求事件的最早開始時間和最遲開始時間，并求邊的最早時間和最遲時間；事件（）求出關鍵路徑；答案：()求和()關鍵路徑（）邊的最早發生時間和最遲發生時間邊、如下所示的有向圖，回答下面問題：（）該圖是強連通的嗎？若不是，給出強連通分量。（）請給出圖的鄰接矩陣和鄰接表表示。答案：()是強連通圖()鄰接矩陣和鄰接表為：、已知圖的鄰接矩陣，試畫出它所表示的圖，并根據算法求出圖的的最小生成樹（給出生成過程）。答案：()圖形態：()算法求最小生成樹：、如下圖所示的網，寫出其中三種拓撲排序序列。、已知圖如下，根據克魯斯卡爾算法求圖的一棵最小生成樹。（要求給出構造過程）答案：算法的最小生成樹第九章查找一、選擇題、已知一個有序表為（，，，，，，，，），則折半查找需要比較（）次。. . . .、在一棵深度為的具有個元素的二叉排序樹中，查找所有元素的最長查找長度為（）。. . .().、已知表長為的哈希表，用除留取余法，按公式()建立哈希表，則應?。ǎ橐?。... .、設哈希表長,哈希函數()。表中已有個結點：()()()()其余地址為空，如用二次探測再散列處理沖突，則關鍵字為的地址為（）。 . . .、在散列查找中，平均查找長度主要與（）有關。.散列表長度.散列元素個數 .裝填因子 .處理沖突方法、一個待散列的線性表為{}，散列函數為()，與發生沖突的元素有（）個。.. . .、在對查找表的查找過程中，若被查找的數據元素不存在，則把該數據元素插到集合中，這種方式主要適合于（）。.靜態查找表.動態查找表 .靜態查找表和動態查找表.兩種表都不適合、在各種查找方法中，平均查找次數與結點個數無關的查找方法是（）。.順序查找.折半查找.哈希查找 .分塊查找、下列二叉樹中，不平衡的二叉樹是（）。、對一棵二叉排序樹按（）遍歷，可得到結點值從小到大的排列序列。.先序.中序 .后序 .層次、解決散列法中出現的沖突問題常采用的方法是（）。.數字分析法、除余法、平方取中法.數字分析法、除余法、線性探測法.數字分析法、線性探測法、多重散列法.線性探測法、多重散列法、鏈地址法、對線性表進行折半查找時，要求線性表必須（）。.以順序方式存儲.以鏈接方式存儲.以順序方式存儲，且結點按關鍵字有序排序.以鏈接方式存儲，且結點按關鍵字有序排序二、填空題、已知有序表為（，，，，，，，，，，），當用折半查找時，需進行次查找可確定成功。、具有相同函數值的關鍵字對哈希函數來說稱為同義詞。、在一棵二叉排序樹上實施中序遍歷后，其關鍵字序列是一個有序表。三、判斷題（×）、折半查找只適用于有序表，包括有序的順序表和鏈表。（√）、二叉排序樹的任意一棵子樹中，關鍵字最小的結點必無左孩子，關鍵字最大的結點必無右孩子。（√）、平衡二叉樹是指左右子樹的高度差的絕對值不大于的二叉樹。（√）、是一棵二叉樹，其樹上任一結點的平衡因子的絕對值不大于。四、綜合題、選取哈希函數（）（）。用二次探測再散列處理沖突，試在的散列地址空間中對關鍵字序列（）造哈希表，并求等概率情況下查找成功時的平均查找長度。答案：()表形態：()：()(***)()、設哈希表表長為，哈希函數為()，給定的關鍵值序列為{}。試求出用線性探測法解決沖突時所構造的哈希表，并求出在等概率的情況下查找成功的平均查找長度。答案：()表形態：()平均查找長度：()(***)、設散列表容量為（散列地址空間），給定表（，，，，）,散列函數（），采用線性探測法解決沖突，要求：（）構造散列表；（）求查找數需要比較的次數。答案：()表形態：()查找的比較次數：、已知下面二叉排序樹的各結點的值依次為－，請標出各結點的值。答案：（說明，圖中結點的值應該為）、若依次輸入序列{}中的元素，生成一棵二叉排序樹。畫出生成后的二叉排序樹（不需畫出生成過程）。、根據一組記錄（，，，，）依次插入結點生成一棵樹（畫出生成過程）。、設有一組關鍵字{},采用哈希函數(),采用開放地址法的二次探測再散列方法解決沖突，試在－的散列空間中對關鍵字序列構造哈希表，畫出哈希表，并求其查找成功時的平均查找長度。、已知關鍵字序列{}，設哈希表表長為，哈希函數()，處理沖突的方法為線性探測法，請給出哈希表，并計算在等概率的條件下的平均查找長度。、設散列表的長度為，散列函數為()，給定的關鍵碼序列為，，，，，，，，，，，，試寫出用線性探查法解決沖突時所構造的散列表。答案：表形態：、依次讀入給定的整數序列{}，構造一棵二叉排序樹,并計算在等概率情況下該二叉排序樹的平均查找長度。（要求給出構造過程）、設有一組關鍵字（，，，，，，，，，，，），采用哈希函數()，采用二次探測再散列的方法解決沖突，試在的散列地址空間中對該關鍵字序列構造哈希表。答案：、有一組關鍵字序列{}，哈希表的表長為，哈希函數為(),沖突解決的辦法為鏈地址法，請構造哈希表（用圖表示）。第十章內部排序一、選擇題、若需要在()的時間內完成對數組的排序，且要求排序是穩定的，則可選擇的排序方法是（）。.快速排序 .堆排序 .歸并排序 .直接插入排序、下列排序方法中（）方法是不穩定的。.冒泡排序 .選擇排序.堆排序 .直接插入排序、一個序列中有個元素，若只想得到其中前個最小元素，則最好采用（）方法。.快速排序.堆排序 .插入排序 .歸并排序、一組待排序序列為（），需要降序排列，則利用堆排序的方法建立的初始堆為（）。. ...、快速排序方法在（）情況下最不利于發揮其長處。.要排序的數據量太大.要排序的數據中有多個相同值.要排序的數據已基本有序 .要排序的數據個數為奇數、排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置，這是（）排序的基本思想。.堆排序 .直接插入排序 .快速排序 .冒泡排序、在任何情況下，時間復雜度均為()的不穩定的排序方法是（）。.直接插入 .快速排序.堆排序.歸并排序、如果將所有中國人按照生日來排序，則使用（）算法最快。.歸并排序 .希爾排序 .快速排序.基數排序、在對個元素的序列進行排序時，堆排序所需要的附加存儲空間是（）。.().().().()、排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）。.希爾排序.冒泡排序.插入排序 .選擇排序、用某種排序方法對線性表（，，，，，，，，）進行排序時，元素序列的變化情況如下：⑴，，，，，，，，⑵，，，，，，，，⑶，，，，，，，，⑷，，，，，，，，則所采用的排序方法是（）。 .選擇排序 .希爾排序 .歸并排序.快速排序、設有個無序的元素，希望用最快的速度挑選出其中前個最大的元素，最好選用（）。.冒泡排序 .選擇排序 .快速排序 .堆排序、希爾排序的增量序列必須是（）。.遞增的.遞減的 .隨機的 .非遞減的三、判斷題、直接選擇排序是一種穩定的排序方法。、快速排序在所有排序方法中最快，而且所需附加空間也最少。、直接插入排序是不穩定的排序方法。、選擇排序是一種不穩定的排序方法。五、綜合題、寫出用直接插入排序將關鍵字序列{}排序過程的每一趟結果。答案：初始：，，，，，，，，：（，），，，，，，，：（，，），，，，，，：（，，，），，，，，：（，，，，），，，，：（，，，，，），，，：（，，，，，，），，：（，，，，，，，）， ：（，，，，，，，，）、設待排序序列為{}請寫出希爾排序每一趟的結果。增量序列為，，，。答案：初始：，，，，，，，，，：，，，，，，，，，：，，，，，，，，，：，，，，，，，，，：，，，，，，，，，、已知關鍵字序列{，，，，，，，，}，按遞減排序，求初始堆（畫出初始堆的狀態）。答案：，，，，，，，，、有一關鍵字序列（，，，，，，，，，），寫出希爾排序的每趟排序結果。（取增量為，，）答案：初始：，，，，，，，，，：，，，，，，，，，：，，，，，，，，，：，，，，，，，，，、對于直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序和歸并排序等排序方法，分別寫出：（）平均時間復雜度低于（）的排序方法；（）所需輔助空間最多的排序方法；答案：()希爾、快速、堆、歸并()歸并、對關鍵字序列（，，，，，，，）進行堆排序，使之按關鍵字遞減次序排列，請寫出排序過程中得到的初始堆和前三趟的序列狀態。答案：第一章概論自測題答案一、填空題.數據結構被形式地定義為（,），其中是數據元素的有限集合，是上的關系有限集合。.數據結構包括數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容。.數據結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。．在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有個前驅結點；最后一個結點沒有后續結點，其余每個結點有且只有個后續結點。.在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有個前驅結點；葉子結點沒有后續結點，其余每個結點的后續結點數可以任意多個。.在圖形結構中，每個結點的前驅結點數和后續結點數可以任意多個。．數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和散列。.數據的運算最常用的有種，它們分別是插入、刪除、修改、查找、排序。.一個算法的效率可分為時間效率和空間效率。.任何一個程序都由一個主函數和若干個被調用的其它函數組成。二、單項選擇題（）.非線性結構是數據元素之間存在一種：）一對多關系）多對多關系）多對一關系）一對一關系（）.數據結構中，與所使用的計算機無關的是數據的結構；)存儲)物理)邏輯)物理和存儲（）.算法分析的目的是：)找出數據結構的合理性)研究算法中的輸入和輸出的關系)分析算法的效率以求改進)分析算法的易懂性和文檔性（）.算法分析的兩個主要方面是：)空間復雜性和時間復雜性)正確性和簡明性)可讀性和文檔性)數據復雜性和程序復雜性（）.計算機算法指的是：)計算方法)排序方法)解決問題的有限運算序列)調度方法（）.計算機算法必須具備輸入、輸出和等個特性。)可行性、可移植性和可擴充性)可行性、確定性和有窮性)確定性、有窮性和穩定性)易讀性、穩定性和安全性三、簡答題.數據結構和數據類型兩個概念之間有區別嗎？答：簡單地說，數據結構定義了一組按某些關系結合在一起的數組元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了一組操作。.簡述線性結構與非線性結構的不同點。答：線性結構反映結點間的邏輯關系是一對一的，非線性結構反映結點間的邏輯關系是多對多的。第章自測卷答案一、填空.在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。.線性表中結點的集合是有限的，結點間的關系是一對一的。.向一個長度為的向量的第個元素(≤≤)之前插入一個元素時，需向后移動個元素。.向一個長度為的向量中刪除第個元素(≤≤)時，需向前移動個元素。.在順序表中訪問任意一結點的時間復雜度均為()，因此，順序表也稱為隨機存取的數據結構。.順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。.在單鏈表中，除了首元結點外，任一結點的存儲位置由其直接前驅結點的鏈域的值指示。．在個結點的單鏈表中要刪除已知結點*，需找到它的前驅結點的地址，其時間復雜度為（）。二、判斷正誤（×）.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。（×）.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。（×）.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內容改變。（×）.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。（×）.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（×）.順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優點。順序存儲方式插入、刪除運算效率較低，在表長為的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。（×）.線性表在物理存儲空間中也一定是連續的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續存放。（×）.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（×）.順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。（后一節介紹）（×）.線性表的邏輯順序與存儲順序總是一致的。錯，理由同。鏈式存儲就無需一致。三、單項選擇題（）．數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為：（）存儲結構（）邏輯結構（）順序存儲結構（）鏈式存儲結構（）.一個向量第一個元素的存儲地址是，每個元素的長度為，則第個元素的地址是（）（）（）（）（）.在個結點的順序表中，算法的時間復雜度是（）的操作是：訪問第個結點（≤≤）和求第個結點的直接前驅（≤≤）在第個結點后插入一個新結點（≤≤）刪除第個結點（≤≤）將個結點從小到大排序（）.向一個有個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素（）（）（）（）（）.鏈接存儲的存儲結構所占存儲空間：分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針只有一部分，存放結點值（）只有一部分，存儲表示結點間關系的指針（）分兩部分，一部分存放結點值，另一部分存放結點所占單元數（）.鏈表是一種采用存儲結構存儲的線性表；（）順序（）鏈式（）星式（）網狀（）.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址:（）必須是連續的（）部分地址必須是連續的（）一定是不連續的（）連續或不連續都可以（）．線性表Ｌ在情況下適用于使用鏈式結構實現。（Ａ）需經常修改Ｌ中的結點值（Ｂ）需不斷對Ｌ進行刪除插入（Ｃ）Ｌ中含有大量的結點（Ｄ）Ｌ中結點結構復雜（）．單鏈表的存儲密度（Ａ）大于；（Ｂ）等于；（Ｃ）小于；（Ｄ）不能確定四、簡答題.試比較順序存儲結構和鏈式存儲結構的優缺點。在什么情況下用順序表比鏈表好？答：①順序存儲時，相鄰數據元素的存放地址也相鄰（邏輯與物理統一）；要求內存中可用存儲單元的地址必須是連續的。優點：存儲密度大（＝？），存儲空間利用率高。缺點：插入或刪除元素時不方便。②鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。?lt;），存儲空間利用率低。順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪除這樣的動態操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。.描述以下三個概念的區別：頭指針、頭結點、首元結點（第一個元素結點）。在單鏈表中設置頭結點的作用是什么？答：首元結點是指鏈表中存儲線性表中第一個數據元素的結點。為了操作方便，通常在鏈表的首元結點之前附設一個結點，稱為頭結點，該結點的數據域中不存儲線性表的數據元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。若鏈表中附設頭結點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環鏈表均適用。是否設置頭結點，是不同的存儲結構表示同一邏輯結構的問題。頭結點頭指針首元結點簡而言之，頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針；頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息首元素結點是指鏈表中存儲線性表中第一個數據元素的結點。五、線性表具有兩種存儲方式，即順序方式和鏈接方式?，F有一個具有五個元素的線性表{，，，，}，若它以鏈接方式存儲在下列～號地址空間中，每個結點由數據（占個字節）和指針（占個字節）組成，如下所示：^^其中指針，，的值分別為多少？該線性表的首結點起始地址為多少？末結點的起始地址為多少？（分）答：首址末址六、編程題();();[];{;;(;<;){[];[][];[];};}解：輸入：長度為的線性表數組()輸出：逆轉后的長度為的線性表數組()。語言描述如下（其中為數據元素的類型）：.編寫程序，將若干整數從鍵盤輸入，以單鏈表形式存儲起來，然后計算單鏈表中結點的個數（其中指針指向該鏈表的第一個結點）。解：編寫程序如下(已上機通過)：全局變量及函數提前說明：<><>{*;};*,*,*,*;();()*第一步，從鍵盤輸入整數，不斷添加到鏈表*{;(*)();*();*;;(){("['']:");("");>;**>(*)();*());*;>;}>;*原先用>似乎太晚！*;;*統計鏈表結點的個數并打印出來*(>){("">);>;;}("\\",);*結點的個數不包括*}第章棧和隊列自測卷答案一、填空題.向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。.隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。.在一個循環隊列中，隊首指針指向隊首元素的前一個位置。.在具有個單元的循環隊列中，隊滿時共有個元素。.向棧中壓入元素的操作是先移動棧頂指針，后存入元素。.從循環隊列中刪除一個元素時，其操作是先移動隊首指針，后取出元素。.帶表頭結點的空循環雙向鏈表的長度等于。頭結點解：頭結點二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（×）.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。（×）.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調用子程序或函數常用，中也用隊列。（√）.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（√）.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（×）.棧和鏈表是兩種不同的數據結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。（×）.棧和隊列是一種非線性數據結構。錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（√）.兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（×）.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。錯，后半句不對。（×）.一個棧的輸入序列是，則棧的輸出序列不可能是。錯，有可能。三、單項選擇題（）.棧中元素的進出原則是Ａ．先進先出Ｂ．后進先出Ｃ．?？談t進Ｄ．棧滿則出（）.若已知一個棧的入棧序列是，，，…，，其輸出序列為，，，…，，若，則為Ａ．Ｂ．Ｃ．Ｄ．不確定解釋：當，即是最先出棧的，根據棧的原理，必定是最后入棧的（事實上題目已經表明了），那么輸入順序必定是，，，…，，則出棧的序列是，…，，，。（若不要求順序出棧，則輸出序列不確定）（）.判定一個棧（最多元素為）為空的條件是Ａ．><>Ｂ．>Ｃ．><>Ｄ．>（）.判定一個隊列（最多元素為）為滿隊列的條件是Ａ．>－>Ｂ．>－>－Ｃ．>>Ｄ．>>解：隊滿條件是元素個數為。由于約定滿隊時隊首指針與隊尾指針相差，所以不必再減了，應當選。當然，更正確的答案應該取模，即：>(>)（）．數組Ｑ［ｎ］用來表示一個循環隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數小于ｎ，計算隊列中元素的公式為（Ａ）－;（Ｂ）（＋－）;（Ｃ）＋－;（Ｄ）（＋－）.從供選擇的答案中，選出應填入下面敘述？內的最確切的解答，把相應編號寫在答卷的對應欄內。設有個數據元素、、和，對他們分別進行棧操作或隊操作。在進?；蜻M隊操作時，按、、、次序每次進入一個元素。假設?；蜿牭某跏紶顟B都是空?，F要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是，第二次出棧得到的元素是是；類似地，考慮對這四個數據元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是，第二次出隊得到的元素是。經操作后，最后在棧中或隊中的元素還有個。供選擇的答案：～：①②③④：①②③④答：＝,,,,.從供選擇的答案中，選出應填入下面敘述？內的最確切的解答，把相應編號寫在答卷的對應欄內。棧是一種線性表，它的特點是。設用一維數組[,…]來表示一個棧，[]為棧底，用整型變量指示當前棧頂位置，[]為棧頂元素。往棧中推入（）一個新元素時，變量的值；從棧中彈出（）一個元素時，變量的值。設?？諘r，有輸入序列，，，經過，，，，操作后，從棧中彈出的元素的序列是，變量的值是。供選擇的答案：：①先進先出②后進先出 ③進優于出 ④出優于進 ⑤隨機進出，： ①加②減③不變 ④清⑤加⑥減：①②③④⑤⑥：①②③④⑤答案：,,,,注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為，向地址的低端遞減生成，稱為向下生成堆棧。.從供選擇的答案中，選出應填入下面敘述？內的最確切的解答，把相應編號寫在答卷的對應欄內。在做進棧運算時，應先判別棧是否；在做退棧運算時，應先判別棧是否。當棧中元素為個，做進棧運算時發生上溢，則說明該棧的最大容量為。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續的內存空間時，應將兩棧的分別設在這片內存空間的兩端，這樣，只有當時，才產生上溢。供選擇的答案：，：①空②滿③上溢④下溢： ①②③④：①長度②深度③棧頂④棧底：①兩個棧的棧頂同時到達棧空間的中心點②其中一個棧的棧頂到達?？臻g的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空，且一個棧的棧頂到達另一個棧的棧底答案：＝,,,,四、簡答題.說明線性表、棧與隊的異同點。劉答：相同點：都是線性結構，都是邏輯結構的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表。②用途不同，堆棧用于子程調用和保護現場，隊列用于多道作業處理、指令寄存及其他運算等等。.設有編號為，，，的四輛列車，順序進入一個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有種。①全進之后再出情況，只有種：，，，②進個之后再出的情況，有種，③進個之后再出的情況，有種，,④進個之后再出的情況，有種，,.順序隊的“假溢出”是怎樣產生的？如何知道循環隊列是空還是滿？答：一般的一維數組隊列的尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫“假溢出”。采用循環隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：設置一個布爾變量以區別隊滿還是隊空；浪費一個元素的空間，用于區別隊滿還是隊空。使用一個計數器記錄隊列中元素個數（即隊列長度）。我們常采用法②，即隊頭指針、隊尾指針中有一個指向實元素，而另一個指向空閑元素。判斷循環隊列隊空標志是：隊滿標志是：().設循環隊列的容量為（序號從到），現經過一系列的入隊和出隊運算后，有①，;②，；問在這兩種情況下，循環隊列中各有元素多少個？答：用隊列長度計算公式：(＋－)①（＋－）②（＋－）第～章串和數組自測卷答案一、填空題（每空分，共分）.不包含任何字符（長度為）的串稱為空串；由一個或多個空格（僅由空格符）組成的串稱為空白串。（對應嚴題集①，簡答題：簡述空串和空格串的區別）.設“”，則(),“”的字符定位的位置為。.子串的定位運算稱為串的模式匹配；被匹配的主串稱為目標串，子串稱為模式。.設目標””，模式“”，則第次匹配成功。.若為主串長，為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數為()*。.假設有二維數組×，每個元素用相鄰的個字節存儲，存儲器按字節編址。已知的起始存儲位置（基地址）為，則數組的體積（存儲量）為；末尾元素的第一個字節地址為；若按行存儲時，元素的第一個字節地址為()×；若按列存儲時，元素的第一個字節地址為(×＋)×＋）＝。(注：數組是從行列還是從行列計算起呢？由末單元為可知，是從行列開始！).設數組[…,…]的基地址為，每個元素占個存儲單元，若以列序為主序順序存儲，則元素[]的存儲地址為。答：不考慮行列，利用列優先公式：()(，)[()*())]*得：()[()*()]]*＝.三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的行下標、列下標和元素值。.求下列廣義表操作的結果：（）【((),())】(,);頭元素不必加括號（）【【((),())】】();（）【【【((),())】】】;（）【【【((),())】】】（）;二、單選題（每小題分，共分）（）.串是一種特殊的線性表，其特殊性體現在：Ａ．可以順序存儲Ｂ．數據元素是一個字符Ｃ．可以鏈式存儲Ｄ．數據元素可以是多個字符（）.設有兩個串和，求在中首次出現的位置的運算稱作：Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長（）.設串’’，’’，函數()返回和串的連接串，(,,)返回串的從序號開始的個字符組成的子串，()返回串的長度，則((,,()),(,(),))的結果串是：Ａ．Ｂ．Ｃ．Ｄ．解：()返回和串的連接串，即()＝‘’；(,,)返回串的從序號開始的個字符組成的子串，則(,,())＝(,,)’’;(,(),)＝(,,)’’;所以((,,()),(,(),))＝(’’,’’)之連接，即（）.假設有行列的二維數組[…,…]以列序為主序順序存儲，其基地址為，每個元素占個存儲單元，那么第行第列的元素[]的存儲地址為。（無第行第列元素）Ａ．Ｂ．Ｃ．Ｄ．答案,,均不對答：此題與填空題第小題相似。（列×行＋行）×字節＋().設矩陣是一個對稱矩陣，為了節省存儲，將其下三角部分（如下圖所示）按行序存放在一維數組[,()]中，對下三角部分中任一元素(≤),在一維數組中下標的值是：Ａ．()Ｂ．()Ｃ．()Ｄ．()解：注意的下標要求從開始。解：注意的下標要求從開始。先用第一個元素去套用，可能有和；再用第二個元素去套用和，而＝（不符）；所以選.從供選擇的答案中，選出應填入下面敘述？內的最確切的解答，把相應編號寫在答卷的對應欄內。有一個二維數組，行下標的范圍是到，列下標的范圍是到，每個數組元素用相鄰的個字節存儲。存儲器按字節編址。假設存儲數組元素[]的第一個字節的地址是。存儲數組的最后一個元素的第一個字節的地址是。若按行存儲，則[]和[]的第一個字節的地址分別是和。若按列存儲，則[]和[]的第一個字節的地址分別是和。供選擇的答案：～：①②③④⑤⑥⑦⑧⑨⑩答案：,,,,.有一個二維數組，行下標的范圍是到，列下標的范圍是到，每個數組元素用相鄰的個字節存儲，存儲器按字節編址。那么，這個數組的體積是個字節。假設存儲數組元素[]的第一個字節的地址是，則存儲數組的最后一個元素的第一個字節的地址是。若按行存儲，則[]的第一個字節的地址是。若按列存儲，則[]的第一個字節的地址是。供選擇的答案～：①②③④⑤⑥⑦⑧⑨⑩（）（）答案：,,,第章樹和二叉樹自測卷解答一、下面是有關二叉樹的敘述，請判斷正誤（每小題分，共分）（√）.若二叉樹用二叉鏈表作存貯結構，則在個結點的二叉樹鏈表中只有—個非空指針域。（×）.二叉樹中每個結點的兩棵子樹的高度差等于。（√）.二叉樹中每個結點的兩棵子樹是有序的。（×）.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（×）.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（應當是二叉排序樹的特點）（×）.二叉樹中所有結點個數是，其中是樹的深度。（應）（×）.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（×）.對于一棵非空二叉樹，它的根結點作為第一層，則它的第層上最多能有—個結點。（應）（√）.用二叉鏈表法（）存儲包含個結點的二叉樹，結點的個指針區域中有個為空指針。（正確。用二叉鏈表存儲包含個結點的二叉樹，結點共有個鏈域。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有個結點的鏈域存放指向非空子女結點的指針，還有個空指針。）即有后繼鏈接的指針僅個。（√）.具有個結點的完全二叉樹有個度為的結點。最快方法：用葉子數＝[]＝，再求二、填空（每空分，共分）．由３個結點所構成的二叉樹有種形態。.一棵深度為的滿二叉樹有個分支結點和個葉子。注：滿二叉樹沒有度為的結點，所以分支結點數就是二度結點數。．一棵具有２５７個結點的完全二叉樹，它的深度為。（注：用()設一棵完全二叉樹有個結點，則共有個葉子結點。答：最快方法：用葉子數＝[]＝.設一棵完全二叉樹具有個結點，則此完全二叉樹有個葉子結點，有個度為的結點，有個結點只有非空左子樹，有個結點只有非空右子樹。答：最快方法：用葉子數＝[]＝，。另外，最后一結點為屬于左葉子，右葉子是空的，所以有個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數＝..一棵含有個結點的叉樹，可能達到的最大深度為，最小深度為。答：當(單叉樹)時應該最深，深度＝（層）；當（叉樹）時應該最淺，深度＝（層），但不包括或時的特例情況。教材答案是“完全叉樹”，未定量。).二叉樹的基本組成部分是：根（）、左子樹（）和右子樹（）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按次序），后序法（即按次序）和中序法（也稱對稱序法，即按次序）。這三種方法相互之間有關聯。若已知一棵二叉樹的前序序列是，中序序列是，則它的后序序列必是。

解：法：先由已知條件畫圖，再后序遍歷得到結果；法：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定，由中序先確定左子樹。例如，前序遍歷中，根結點在最前面，是；則后序遍歷中一定在最后面。法：遞歸計算。如在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對的左右子樹同樣處理，則問題得解。.中序遍歷的遞歸算法平均空間復雜度為()。答：即遞歸最大嵌套層數，即棧