浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程自我測試答案

窗體頂端1. 鄰接表是圖的一種 ____。正確答案 點(diǎn)評順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)正確答案： B答案講解：無【試題出處】第6章第3節(jié)1窗體底端窗體頂端一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,則利用快速排序的方法，以第一個記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為。正確答案點(diǎn)評38,40,46,56,79,8440,38,46,79,56,8440,38,46,56,79,8440,38,46,84,56,79正確答案： C窗體底端窗體頂端設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至多為_____(注意C和D中h是指數(shù))。正確答案點(diǎn)評2h-12(h-1)2*h-1D2*h正確答案： A窗體底端窗體頂端4. 一個棧的入棧序列是正確答案 點(diǎn)評

a,b,c,d,

則下列序列中不可能的輸出序列是

_______

。acbddcbaacdbdbac正確答案： D窗體底端窗體頂端5. 計算機(jī)算法是指 ______。正確答案 點(diǎn)評計算方法排序方法調(diào)度方法解決問題的有限運(yùn)算序列正確答案：D窗體底端窗體頂端6. 關(guān)于二叉樹的三種遍歷，下列說法正確的是正確答案 點(diǎn)評

____。任意兩種遍歷序列都不可以唯一決定該二叉樹任意兩種遍歷序列都可以唯一決定該二叉樹先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹正確答案：D窗體底端窗體頂端7. 順序表的特點(diǎn)是 ______。正確答案 點(diǎn)評邏輯上相鄰的結(jié)點(diǎn)其物理位置不相鄰邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰順序表不是隨機(jī)存儲結(jié)構(gòu)在順序表中插入和刪除操作比在鏈表上方便正確答案：B窗體底端窗體頂端8. 設(shè)散列表長為 14，散列函數(shù)是 H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為 15，38，61，共四個，現(xiàn)要將關(guān)鍵字為 49的結(jié)點(diǎn)加到表中，用二次探測法解決沖突，則放入的位置是

84____________

。正確答案

點(diǎn)評8359正確答案： D窗體底端窗體頂端9. 對順序存儲的線性表， 設(shè)其長度為 n，且在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的 _____個元素。

則正確答案

點(diǎn)評n/2(n+1)/2(n-1)/2n正確答案： A窗體底端窗體頂端樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。 這里我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。 那么以下結(jié)論中 _____是正確的。正確答案 點(diǎn)評樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同以上都不對正確答案： A窗體底端窗體頂端11.在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 ____倍。正確答案 點(diǎn)評1/2124正確答案： C窗體底端窗體頂端12.如果某二叉樹的先序遍歷序列是 abdcef，中序遍歷序列是 dbaefc，則其后序遍歷序列是____。正確答案 點(diǎn)評dbafecfecdbaefcdbaDdbfeca正確答案： D窗體底端窗體頂端13.向一個有 115個元素的順序表中插入一個新元素并保持原來順序不變， 平均要移動 _____個元素。正確答案 點(diǎn)評1151145857正確答案： C窗體底端窗體頂端14.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是 _____的二叉樹。正確答案 點(diǎn)評空或只有一個結(jié)點(diǎn)高度等于其結(jié)點(diǎn)數(shù).任一結(jié)點(diǎn)無左孩子任一結(jié)點(diǎn)無右孩子正確答案：A窗體底端窗體頂端15.對于一個具有 n個頂點(diǎn)和 e條邊的無向圖， 若采用鄰接表表示， 鄰接表中所有結(jié)點(diǎn)總數(shù)是_____。正確答案點(diǎn)評e/22eeDn+e正確答案： B窗體底端窗體頂端16.當(dāng)字符序列 x5y 作為字符堆棧的輸入時，輸出長度為 3的且可以作為 C語言標(biāo)識符的個數(shù)是____。正確答案 點(diǎn)評A3個B4個C5個D6個正確答案： A窗體底端窗體頂端17. 用某種排序方法對線性表 (25,84,21,47,15,27,68,35,20) 進(jìn)行排序時 ,元素序列的變化情況如下(1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,20,21,25,27,35,47,68,84則所采用的排序方法是 ____ 。正確答案 點(diǎn)評選擇排序希爾排序歸并排序快速排序正確答案：D窗體底端窗體頂端18.樹最適合用來表示 _____。正確答案 點(diǎn)評有序數(shù)據(jù)元素?zé)o序數(shù)據(jù)元素元素之間具有分支層次關(guān)系的數(shù)據(jù)元素之間無聯(lián)系的數(shù)據(jù)正確答案： C窗體底端窗體頂端19.設(shè)有 1000個無序的元素 ,希望用最快的速度挑選出其中前 10個最大的元素 ,最好____排序法。正確答案 點(diǎn)評起泡排序快速排序堆排序基數(shù)排序正確答案：C窗體底端窗體頂端20.如果無向圖 G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)， 則下列說法中不正確的是_____。正確答案點(diǎn)評AG肯定不是完全圖BG一定不是連通圖CG中一定有回路DG有2個連通分量正確答案： C窗體底端窗體頂端21.有m個葉子結(jié)點(diǎn)的 Huffman 樹所具有的結(jié)點(diǎn)總數(shù)為 ____。正確答案 點(diǎn)評m+12m-12mD2m+1正確答案： B窗體底端窗體頂端22.在順序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找關(guān)鍵碼12需做____次關(guān)鍵碼比較。正確答案點(diǎn)評2345正確答案： C窗體底端窗體頂端23.將10個元素散列到正確答案 點(diǎn)評

100000

個單元的散列表中，則

__________

產(chǎn)生沖突。一定會一定不會仍可能會正確答案：C窗體底端窗體頂端24. 已知某二叉樹的后序遍歷序列是____。

dabec,

中序遍歷序列是

debac,

它的前序遍歷序列是正確答案

點(diǎn)評acbeddecabdeabccedba正確答案： D窗體底端窗體頂端25.一個棧的進(jìn)棧序列是 a,b,c,d,e, 則棧的不可能的出棧序列是 _____。正確答案 點(diǎn)評edcbadceabdecbaabcde正確答案： B窗體底端窗體頂端26.已知 10個數(shù)據(jù)元素為（ 54，28，16，34，73，62，95，60，26，43），對該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為 ____。正確答案 點(diǎn)評16，28，34，54，73，62，60，26，43，9528，16，34，54，62，73，60，26，43，9528，16，34，54，62，60，73，26，43，9516，28，34，54，62，60，73，26，43，95正確答案： B窗體底端窗體頂端27.作進(jìn)棧操作時，應(yīng)先判斷棧是否為 _____。正確答案 點(diǎn)評空滿上溢下溢正確答案：B窗體底端窗體頂端28.若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入和刪除結(jié)點(diǎn)的運(yùn)算，則選擇 _____最合適。正確答案 點(diǎn)評單鏈表帶尾指針的單循環(huán)鏈表雙鏈表雙循環(huán)鏈表正確答案：B窗體底端窗體頂端29.判斷一個循環(huán)隊列是空隊列的條件是正確答案 點(diǎn)評

_____

。Q.rear==Q.frontQ.front==0Q.rear==0(Q.rear+1)%maxsize==Q.front正確答案： A窗體底端窗體頂端30.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對次序正確答案 點(diǎn)評

____。不發(fā)生變化發(fā)生變化不能確定以上都不對正確答案：A窗體底端窗體頂端下面關(guān)于圖的存儲的敘述中，哪一個是正確的？正確答案A

點(diǎn)評用相鄰矩陣法存儲圖

,占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān)

,而與邊數(shù)無關(guān)B用相鄰矩陣法存儲圖

,占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)

,而與結(jié)點(diǎn)個數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān)正確答案：A窗體底端窗體頂端32.鏈表不具有的特點(diǎn)是 _____。正確答案 點(diǎn)評可隨機(jī)訪問任一元素插入和刪除不需要移動元素不必事先估計存儲空間所需空間和線性表長度成正比正確答案：A窗體底端窗體頂端33.若用二分查找法取得的中間位置元素鍵值大于被查找值，

說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始位置至

____。正確答案

點(diǎn)評該中間位置該中間位置－1該中間位置＋1該中間位置／2正確答案： B窗體底端窗體頂端34.線性表按鏈?zhǔn)椒绞酱鎯r，每個結(jié)點(diǎn)的存儲包括正確答案 點(diǎn)評

_____

兩部分。數(shù)據(jù)值與符號數(shù)據(jù)與指針數(shù)據(jù)與表名數(shù)據(jù)項與符號正確答案：B窗體底端窗體頂端35.下列排序算法的時間復(fù)雜度最小的是 ____。正確答案 點(diǎn)評冒泡排序希爾排序簡單選擇排序歸并排序正確答案：D窗體底端窗體頂端36.線性表采用鏈?zhǔn)酱鎯r，其地址 _____。正確答案 點(diǎn)評必須是連續(xù)的必須是不連續(xù)的連續(xù)與否均可部分地址必須是連續(xù)的正確答案：C窗體底端窗體頂端37.具有 5個頂點(diǎn)的有向完全圖有 ____條弧。正確答案 點(diǎn)評A10162025正確答案： C窗體底端窗體頂端設(shè)某二維數(shù)組A［1..n，1..n］，則在該數(shù)組中用順序查找法查找一個元素的時間復(fù)雜性的量級為______。正確答案點(diǎn)評AO（log2n）O(n)O(nlog2n)O(n^2)正確答案： D窗體底端窗體頂端39.關(guān)于無向連通圖的最小生成樹的個數(shù) _____。正確答案 點(diǎn)評一定有多棵一定只有一棵有一棵或多棵可能不存在正確答案：B窗體底端窗體頂端設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____(注意C和D中h為指數(shù))。正確答案點(diǎn)評A2h-12(h-1)2*h-12*h正確答案： A窗體底端窗體頂端41.若構(gòu)造一棵具有 n個結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會超過 ____。正確答案 點(diǎn)評n/2n(n+1)/2n+1正確答案： B窗體底端窗體頂端42.若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是 ____。正確答案 點(diǎn)評根結(jié)點(diǎn)無右子樹的二叉樹根結(jié)點(diǎn)無左子樹的二叉樹根節(jié)點(diǎn)可能有左子樹和右子樹的二叉樹各結(jié)點(diǎn)只有一個兒子的二叉樹正確答案：C窗體底端窗體頂端在長度為n的雙鏈表中某結(jié)點(diǎn)（已知其地址）之前，插入一個新結(jié)點(diǎn)的時間復(fù)雜度是_____ 。正確答案 點(diǎn)評AO(n)BO(log2n)O(1)O(n^2)正確答案： C窗體底端窗體頂端44.設(shè)a,b為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時， a在b前的條件是 ____。正確答案 點(diǎn)評Aa是b祖先Ba是b子孫Ca在b左方Da在b右方正確答案： C窗體底端窗體頂端45.若某堆棧的輸入序列為 1，2，3，?，n-1，n，輸出序列的第 1個元素為 n，則第 i個輸出元素為 ______。正確答案 點(diǎn)評n-i+ln-ii哪個元素?zé)o所謂正確答案：A窗體底端窗體頂端46.數(shù)據(jù)結(jié)構(gòu)課程主要研究以下三方面的內(nèi)容，它們是 ______。正確答案 點(diǎn)評數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型數(shù)據(jù)元素、數(shù)據(jù)類型、算法實(shí)現(xiàn)數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算正確答案：D窗體底端窗體頂端在某棵二叉樹的一種序列中，如果發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判斷定這種序列為中序序列。正確答案點(diǎn)評正確不正確正確答案：A窗體底端窗體頂端48.設(shè)二叉樹根結(jié)點(diǎn)的層次為 1，所有含有 15個結(jié)點(diǎn)的二叉樹中，最小高度是 _____。正確答案 點(diǎn)評6543正確答案： C窗體底端窗體頂端49.設(shè)n個頂點(diǎn) e條邊的圖 G用鄰接表存儲，則求每個頂點(diǎn)入度的時間復(fù)雜度為 ____。正確答案 點(diǎn)評O(n)O(n+e)O(n*n)O(n*e)正確答案： B窗體底端窗體頂端50.在待排序的元素序列基本有序的前提下，效率最高的排序方法是

____

。正確答案 點(diǎn)評插入排序快速排序歸并排序選擇排序正確答案：A窗體底端窗體頂端51.下列關(guān)于圖的生成樹的唯一性，正確的是正確答案 點(diǎn)評

_____

。生成樹是唯一的生成樹是不唯一的生成樹是唯一性不確定圖的生成樹有兩棵正確答案：C窗體底端窗體頂端52.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是正確答案 點(diǎn)評

_____。線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)散列方式和索引方式鏈表存儲結(jié)構(gòu)和數(shù)組線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)正確答案：D窗體底端窗體頂端53.隊列的操作原則是 _____。正確答案 點(diǎn)評先進(jìn)先出先進(jìn)后出只能進(jìn)行插入只能進(jìn)行刪除正確答案：A窗體底端窗體頂端54.一組記錄的排序碼為（____。

20,29,11,74,35,3,8,56

），則利用堆排序方法建立的初始

(小頂

)堆為正確答案

點(diǎn)評20,29,11,74,35,3,8,563,29,8,56,35,20,11,743,8,11,20,29,35,56,7420,29,3,8,11,35,74,56正確答案： B窗體底端窗體頂端55.在一個具有

n個結(jié)點(diǎn)的有序單鏈表中，

插入一個新的結(jié)點(diǎn)并使之仍然有序的時間復(fù)雜度是______。正確答案點(diǎn)評O(n)O(log2n)O(1)O(n^2)正確答案： A窗體底端窗體頂端56.在一個長度為

n的順序表中，在第

i個元素（

1<=i<=n

）之前插入一個新元素時需向后移動_______個元素。正確答案點(diǎn)評1n-in-i-1n-i+1正確答案： D窗體底端窗體頂端57.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的正確答案 點(diǎn)評

____結(jié)構(gòu)。存儲物理邏輯物理與存儲正確答案：C窗體底端窗體頂端58.對線性表進(jìn)行二分查找時，要求線性表必須正確答案 點(diǎn)評

____。以順序方式存儲以順序方式存儲且元素有序以鏈?zhǔn)椒绞酱鎯σ枣準(zhǔn)椒绞酱鎯η以赜行蛘_答案：B窗體底端窗體頂端59.帶頭結(jié)點(diǎn)的單鏈表正確答案 點(diǎn)評

Head

為空表的判定條件是

______

。Head->next==HeadHead->next==NULLHead!=NULLHead==NULL正確答案： B窗體底端窗體頂端采用不帶尾指針的單鏈表方式表示一個棧，便于結(jié)點(diǎn)的插入與刪除。棧頂結(jié)點(diǎn)的插入與刪除通常在鏈表的 _____進(jìn)行。正確答案 點(diǎn)評任意位置鏈表頭尾兩端鏈表頭一端鏈表尾一端正確答案： C窗體底端2、 判斷題窗體頂端用鄰接矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。正確答案點(diǎn)評對 錯正確答案：錯窗體底端窗體頂端哈希表是用于查找的技術(shù)之一。正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端63.判斷順序儲存下堆棧 s是空的條件是 s.top==0。正確答案 點(diǎn)評對 錯正確答案：對窗體底端窗體頂端64.若散列表的裝載因子 α<1，則可避免沖突的產(chǎn)生。正確答案 點(diǎn)評對 錯正確答案：錯窗體底端窗體頂端二叉排序樹一般用于查找某個元素。正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端滿二叉樹一定是完全二叉樹，反之不然。正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端哈夫曼編碼使一串文字的編碼長度最短。正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端69.連通圖的廣度優(yōu)先搜索中一般要采用隊列 來暫存剛訪問過的頂點(diǎn)。正確答案 點(diǎn)評對 錯正確答案：對窗體底端窗體頂端n(n>0)個結(jié)點(diǎn)的樹有n-1條邊。正確答案點(diǎn)評對 錯正確答案：對窗體底端窗體頂端71.5個頂點(diǎn)的無向圖，若不連通，則最多可能有 6條邊。正確答案 點(diǎn)評對 錯正確答案：對窗體