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

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