浙江大學(xué)大數(shù)據(jù)結(jié)構(gòu)與算法課程自我測(cè)試問題詳解

1、實(shí)用文檔窗體頂端1 .鄰接表是圖的一種X正確答案點(diǎn)評(píng)1- A順序存儲(chǔ)結(jié)構(gòu)lB鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)PC索引存儲(chǔ)結(jié)構(gòu)2- D散列存儲(chǔ)結(jié)構(gòu)正確答案：B答案講解：無【試題出處】第6章第3節(jié)1窗體底端窗體頂端2 .一組記錄的關(guān)鍵字為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為。X正確答案點(diǎn)評(píng)市A38,40,46,56,79,84rB40,38,46,79,56,84tjI尸C40,38,46,56,79,84rID40,38,46,84,56,79正確答案：C實(shí)用文檔窗體底端窗體頂端3 .設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包

2、含的結(jié)點(diǎn)數(shù)至多為在意C和D中h是指數(shù))。X正確答案點(diǎn)評(píng)JA2h-1rB2(h-1)-C2*h-11 D2*h正確答案：A窗體底端窗體頂端4 .一個(gè)棧的入棧序列是a,b,c,d,則下列序列中不可能的輸出序列是X正確答案點(diǎn)評(píng)-AacbdrBdcbaCacdbrDdbac窗體底端窗體頂端5 .計(jì)算機(jī)算法是指X正確答案點(diǎn)評(píng)PA計(jì)算方法LB排序方法LC調(diào)度方法R-界D解決問題的有限運(yùn)算序列正確答案：D窗體底端窗體頂端6 .關(guān)于二叉樹的三種遍歷，下列說法正確的是X正確答案點(diǎn)評(píng)任意兩種遍歷序列都不可以唯一決定該二叉樹任意兩種遍歷序列都可以唯一決定該二叉樹先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹D先序遍

3、歷序列和中序遍歷序列可以唯一決定該二叉樹正確答案：D7 .順序表的特點(diǎn)是X正確答案點(diǎn)評(píng)gA邏輯上相鄰的結(jié)點(diǎn)其物理位置不相鄰XB邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰PC順序表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)PD在順序表中插入和刪除操作比在鏈表上方便正確答案：B窗體底端窗體頂端8 .設(shè)散列表長(zhǎng)為14,散列函數(shù)是H(key尸key%11,表中已有數(shù)據(jù)白關(guān)鍵字為15,38,61,84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)法解決沖突，則放入的位置X正確答案點(diǎn)評(píng)D9正確答案：D窗體底端窗體頂端實(shí)用文檔9 .對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n,且在任何位置上插入或刪除操作都是等概率的。則插入一個(gè)元素時(shí)平均要移動(dòng)表中

4、的個(gè)元素。X正確答案點(diǎn)評(píng)An/2B(n+1)/2C(n-1)/2NDn正確答案：A窗體底端窗體頂端10 .樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。么以下結(jié)論中是正確的。x正確答案點(diǎn)評(píng)PA樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同PB樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同£c樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同CD以上都不對(duì)正確答案：A窗體頂端11 .在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的一信。X正確答案點(diǎn)評(píng)尸A1/2SB1C2ND

5、4正確答案：C窗體底端窗體頂端12 .如果某二叉樹的先序遍歷序列是abdcef,中序遍歷序列是dbaefc,則其后序遍歷序列是OX正確答案點(diǎn)評(píng)尸Adbafec1- BfecdbaCefcdbarDdbfeca正確答案：D窗體底端窗體頂端實(shí)用文檔13 .向一個(gè)有115個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)個(gè)元素。X正確答案點(diǎn)評(píng)尸A115rB114SIC58Nd57正確答案：C窗體底端窗體頂端14 .某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是的二叉樹。X正確答案點(diǎn)評(píng)過A空或只有一個(gè)結(jié)點(diǎn)15 B高度等于其結(jié)點(diǎn)數(shù)LC.任一結(jié)點(diǎn)無左孩子rD任一結(jié)點(diǎn)無右孩子正確答案：A

6、窗體底端窗體頂端15 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，鄰接表中所有結(jié)點(diǎn)總數(shù)是X正確答案點(diǎn)評(píng)Dn+e正確答案：B窗體底端窗體頂端C語(yǔ)百標(biāo)識(shí)符的16 .當(dāng)字符序列x5y作為字符堆棧的輸入時(shí)，輸出長(zhǎng)度為3的且可以作為個(gè)數(shù)是X正確答案點(diǎn)評(píng)正確答案：A窗體底端窗體頂端17 .用某種排序方法對(duì)線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí)，元素序列的變化情況如下(1)20,15,21,25,47,27,68,35,84(2)15,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則所采用的排序方法是。X正確

7、答案點(diǎn)評(píng)0A選擇排序PB希爾排序PC歸并排序PD快速排序正確答案：D窗體底端窗體頂端18 .樹最適合用來表示X正確答案點(diǎn)評(píng)AA有序數(shù)據(jù)元素1 B無序數(shù)據(jù)元素PC元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)正確答案：C窗體底端窗體頂端19 .設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好序法。X正確答案點(diǎn)評(píng)I一A起泡排序沖B快速排序PC堆排序PD基數(shù)排序正確答案：C窗體底端窗體頂端20 .如果無向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)，則下列說法中不正確的是X正確答案點(diǎn)評(píng)mAG肯定不是完全圖RBG一定不是連通圖LCG中一定有回路CDG有2個(gè)連通分量正

8、確答案：C窗體底端窗體頂端21 .有m個(gè)葉子結(jié)點(diǎn)的Huffman樹所具有的結(jié)點(diǎn)總數(shù)為?X正確答案點(diǎn)評(píng)Am+1PB2m-1r1 C2m1- D2m+1正確答案：B窗體底端窗體頂端22.在順序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找關(guān)鍵碼12需做次關(guān)鍵碼比較。X正確答案點(diǎn)評(píng)正確答案：C窗體底端窗體頂端23.將10個(gè)元素散列到100000個(gè)單元的散列表中，則產(chǎn)生沖突。正確答案點(diǎn)評(píng)X總A一定會(huì)PB一定不會(huì)1 C仍可能會(huì)正確答案：C窗體底端窗體頂端24 .已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是OX正確答案點(diǎn)評(píng)LAacbed

9、1- BdecabriCdeabcrDcedba正確答案：D窗體底端窗體頂端25 .一個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的出棧序列是?X正確答案點(diǎn)評(píng)HAedcbaBdceabnJCdecbaDabcde正確答案：B窗體底端窗體頂端26 .已知10個(gè)數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,26,43),對(duì)該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為X正確答案點(diǎn)評(píng)A 16283454736260264395163454627360264395C 28163454626073264395°d 16283454626073,264395正確答案：B窗體底

10、端窗體頂端27 .作進(jìn)棧操作時(shí)，應(yīng)先判斷棧是否為x正確答案點(diǎn)評(píng)C上溢1- D下溢正確答案：B窗體底端窗體頂端28 .若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入和刪除結(jié)點(diǎn)的運(yùn)算，則選擇最合適。X正確答案點(diǎn)評(píng)界A單鏈表1 B帶尾指針的單循環(huán)鏈表LC雙鏈表PD雙循環(huán)鏈表正確答案：B窗體底端窗體頂端29 .判斷一個(gè)循環(huán)隊(duì)列是空隊(duì)列的條件是X正確答案點(diǎn)評(píng)rAQ.rear=Q.front-BQ.front=0r1 CQ.rear=0rD(Q.rear+1)%maxsize=Q.front正確答案：A實(shí)用文檔窗體底端窗體頂端30 .任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對(duì)次序?X正確答案點(diǎn)評(píng)LA不

11、發(fā)生變化LB發(fā)生變化界C不能確定再D以上都不對(duì)正確答案：A窗體底端窗體頂端31 .下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的？x正確答案點(diǎn)評(píng)PA用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)舁1 B用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)lC用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)CD用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)正確答案：A窗體底端實(shí)用文檔窗體頂端32 .鏈表不具有的特點(diǎn)是X正確答案點(diǎn)評(píng)1- A可隨機(jī)訪問任一元素PB插入和刪除不需要移動(dòng)元素PC不必事先估計(jì)存儲(chǔ)空間PD所需空間

12、和線性表長(zhǎng)度成正比正確答案：A窗體底端窗體頂端33 .若用二分查找法取得的中間位置元素鍵值大于被查找值，說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始位置至X正確答案點(diǎn)評(píng)gA該中間位置產(chǎn)B該中間位置1LC該中間位置+1DD該中間位置/2正確答案：B窗體底端窗體頂端實(shí)用文檔34 .線性表按鏈?zhǔn)椒绞酱鎯?chǔ)時(shí)，每個(gè)結(jié)點(diǎn)的存儲(chǔ)包括兩部分。X正確答案點(diǎn)評(píng)gA數(shù)據(jù)值與符號(hào)沖B數(shù)據(jù)與指針PC數(shù)據(jù)與表名PD數(shù)據(jù)項(xiàng)與符號(hào)正確答案：B窗體底端窗體頂端35 .下列排序算法的時(shí)間復(fù)雜度最小的是X正確答案點(diǎn)評(píng)lA冒泡排序尸B希爾排序I11 C簡(jiǎn)單選擇排序LD歸并排序正確答案：D窗體底端窗體頂端36 .線性表采用鏈

13、式存儲(chǔ)時(shí)，其地址X正確答案點(diǎn)評(píng)PA必須是連續(xù)的1 B必須是不連續(xù)的PC連續(xù)與否均可XD部分地址必須是連續(xù)的正確答案：C窗體底端窗體頂端37 .具有5個(gè)頂點(diǎn)的有向完全圖有條弧。X正確答案點(diǎn)評(píng)號(hào)A10LB16rC20Md25正確答案：C窗體底端窗體頂端38 .設(shè)某二維數(shù)組A1.n,1.n,則在該數(shù)組中用順序查找法查找一個(gè)元素的時(shí)間復(fù)雜性的量級(jí)為x正確答案點(diǎn)評(píng)AO(log2n)存BO(n)CO(nlog2n)PDO(nA2)正確答案：D窗體底端窗體頂端39 .關(guān)于無向連通圖的最小生成樹的個(gè)數(shù)X正確答案點(diǎn)評(píng)SA一定有多棵PB一定只有一棵PC有一棵或多棵ED可能不存在正確答案：B窗體底端窗體頂端.叉樹中

14、所包含的結(jié)點(diǎn)數(shù)40 .設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類至少為住意C和D中h為指數(shù)）。X正確答案點(diǎn)評(píng)A2h-1B 2(h-1)C2*h-1mD2*h正確答案：A窗體底端窗體頂端41 .若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會(huì)超過X正確答案點(diǎn)評(píng)產(chǎn)An/2BnBnC(n+1)/2NDn+1正確答案：B窗體底端窗體頂端42 .若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是X正確答案點(diǎn)評(píng)lA根結(jié)點(diǎn)無右子樹的二叉樹1 B根結(jié)點(diǎn)無左子樹的二叉樹LC根節(jié)點(diǎn)可能有左子樹和右子樹的二叉樹0ID各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹實(shí)用文檔正確答案：C窗體底端窗體頂端43 .在長(zhǎng)度

15、為n的雙鏈表中某結(jié)點(diǎn)（已知其地址）之前，插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是X正確答案點(diǎn)評(píng)十A0(n)BO(log2n)C0(1)D0(nA2)正確答案：C窗體底端窗體頂端a在b前的條件是?44 .設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí),x正確答案點(diǎn)評(píng)是b祖先是b子孫在b左方在b右方窗體底端窗體頂端45 .若某堆棧的輸入序列為1,2,3,，n-1,n,輸出序列的第1個(gè)元素為n,則第i個(gè)輸出元素為X正確答案點(diǎn)評(píng)JAn-i+lrBn-iCiPD哪個(gè)元素?zé)o所謂正確答案：A窗體底端窗體頂端46 .數(shù)據(jù)結(jié)構(gòu)課程主要研究以下三方面的內(nèi)容，它們是X正確答案點(diǎn)評(píng)PA數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型LB數(shù)據(jù)元素、數(shù)據(jù)類

16、型、算法實(shí)現(xiàn)lC數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算正確答案:窗體底端窗體頂端47 .在某棵二叉樹的一種序列中，如果發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判斷定這種序列為中序序列。X正確答案點(diǎn)評(píng)1- A正確I-B不正確正確答案：A窗體底端窗體頂端48 .設(shè)二叉樹根結(jié)點(diǎn)的層次為1,所有含有15個(gè)結(jié)點(diǎn)的二叉樹中，最小高度是X正確答案點(diǎn)評(píng)A6gB5C4rD3正確答案：C窗體底端窗體頂端49 .設(shè)n個(gè)頂點(diǎn)e條邊的圖G用鄰接表存儲(chǔ)，則求每個(gè)頂點(diǎn)入度的時(shí)間復(fù)雜度為X正確答案點(diǎn)評(píng)AO(n)PBO(n+e)rLCO(n*n)i-DO(n*e)正確答案：B窗體底

17、端窗體頂端50.在待排序的元素序列基本有序的前提下，效率最高的排序方法是X正確答案點(diǎn)評(píng)LA插入排序lB快速排序C-C歸并排序I-D選擇排序正確答案：A窗體底端窗體頂端51 .下列關(guān)于圖的生成樹的唯一性，正確的是。x正確答案點(diǎn)評(píng)A生成樹是唯一的1 B生成樹是不唯一的PC生成樹是唯一性不確定PD圖的生成樹有兩棵正確答案：C窗體底端窗體頂端52 .棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是X正確答案點(diǎn)評(píng)SA線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)PB散列方式和索引方式PC鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組于lD線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)正確答案：D窗體底端窗體頂端53 .隊(duì)列的操作原則是X正確答案點(diǎn)評(píng)tjLA先進(jìn)先出丁LB先進(jìn)后出rC只能

18、進(jìn)行插入4D只能進(jìn)行刪除正確答案：A窗體底端窗體頂端54 .一組記錄的排序碼為(20,29,11,74,35,3,8,56)，則利用堆排序方法建立的初始(小頂)堆為X正確答案點(diǎn)評(píng)A20,29,11,74,35,3,8,56B3,29,8,56,35,20,11,74C3,8,11,20,29,35,56,74D20,29,3,8,11,35,74,56正確答案：B窗體底端窗體頂端55 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中，插入一個(gè)新的結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度x正確答案點(diǎn)評(píng)AO(n)號(hào)BO(log2n)C0(1)pDO(nA2)正確答案：A窗體底端窗體頂端56 .在一個(gè)長(zhǎng)度為n的順序表中，在

19、第i個(gè)元素(1<=i<=n)之前插入一個(gè)新元素時(shí)需向后移動(dòng)個(gè)元素。X正確答案點(diǎn)評(píng)A1BnBn-iCn-i-11 Dn-i+1正確答案：D窗體底端窗體頂端57 .在數(shù)據(jù)結(jié)構(gòu)中，與所使用的方t算機(jī)無關(guān)的是數(shù)據(jù)的一結(jié)構(gòu)。X正確答案點(diǎn)評(píng)lA存儲(chǔ)LB物理凸C邏輯CD物理與存儲(chǔ)實(shí)用文檔正確答案：C窗體底端窗體頂端58 .對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須?X正確答案點(diǎn)評(píng)PA以順序方式存儲(chǔ)于界B以順序方式存儲(chǔ)且元素有序LC以鏈?zhǔn)椒绞酱鎯?chǔ)PD以鏈?zhǔn)椒绞酱鎯?chǔ)且元素有序正確答案：B窗體底端窗體頂端59 .帶頭結(jié)點(diǎn)的單鏈表Head為空表的判定條件是X正確答案點(diǎn)評(píng)'AHead->next

20、=HeadrBHead->next=NULL產(chǎn)CHead!=NULLrDHead=NULL窗體底端窗體頂端棧頂結(jié)點(diǎn)的插入與60 .采用不帶尾指針的單鏈表方式表示一個(gè)棧，便于結(jié)點(diǎn)的插入與刪除。刪除通常在鏈表的進(jìn)行。X正確答案點(diǎn)評(píng)PA任意位置PB鏈表頭尾兩端1- C鏈表頭一端lD鏈表尾一端正確答案：C窗體底端2、判斷題窗體頂端61 .用鄰接矩陣表示圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。X正確答案點(diǎn)評(píng)r r對(duì) 錯(cuò)正確答案：錯(cuò)實(shí)用文檔窗體底端窗體頂端62 .哈希表是用于查找的技術(shù)之X正確答案點(diǎn)評(píng)正確答案：對(duì)窗體底端窗體頂端63 .判斷順序儲(chǔ)存下堆棧s是空的條件是s.top=0X正確答案點(diǎn)評(píng)正確答

21、案：對(duì)窗體底端窗體頂端64 .若散列表的裝載因子a<1,則可避免沖突的產(chǎn)生。X正確答案點(diǎn)評(píng)r r對(duì) 錯(cuò)實(shí)用文檔正確答案：錯(cuò)窗體底端窗體頂端65 .二叉排序樹一般用于查找某個(gè)元素。X正確答案點(diǎn)評(píng)對(duì)錯(cuò)正確答案：對(duì)窗體底端窗體頂端66 .滿二叉樹一定是完全二叉樹，反之不然。X正確答案點(diǎn)評(píng)對(duì)。錯(cuò)正確答案：對(duì)窗體底端窗體頂端67 .哈夫曼編碼使一串文字的編碼長(zhǎng)度最短。X正確答案點(diǎn)評(píng)實(shí)用文檔正確答案：對(duì)窗體底端窗體頂端68 .所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界X正確答案點(diǎn)評(píng)正確答案：對(duì)窗體底端窗體頂端69 .連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)。X正確答案點(diǎn)評(píng)coH對(duì)錯(cuò)正確答案：對(duì)70 .n(n>0)個(gè)結(jié)點(diǎn)的樹有n-1條邊。X正確答案點(diǎn)評(píng)對(duì)錯(cuò)正確答案：對(duì)窗體底端窗體頂端71 .5個(gè)頂點(diǎn)的無向圖，若不連通，則最多可能有6條邊。X正確答案點(diǎn)評(píng)正確答案：對(duì)窗體底端窗體頂端72 .任何一個(gè)森林都可以唯一地與一棵二叉樹對(duì)應(yīng)。X正