2014浙江大學(xué)遠(yuǎn)程教育學(xué)院在線作業(yè)數(shù)據(jù)結(jié)構(gòu)與算法講解

2014--浙江大學(xué)遠(yuǎn)程教育學(xué)院在線作業(yè)數(shù)據(jù)構(gòu)造與算法100分講解2014--浙江大學(xué)遠(yuǎn)程教育學(xué)院在線作業(yè)數(shù)據(jù)構(gòu)造與算法100分講解2014--浙江大學(xué)遠(yuǎn)程教育學(xué)院在線作業(yè)數(shù)據(jù)構(gòu)造與算法100分講解您的本次作業(yè)分?jǐn)?shù)為：100分單項選擇題1.設(shè)散列表長為14，散列函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的要點(diǎn)字為15，38，61，84共四個，現(xiàn)要將要點(diǎn)字為49的結(jié)點(diǎn)加到表中，用二次探測法解決矛盾，則放入的地址是____________。8359正確答案:D單項選擇題2.以下排序算法的時間復(fù)雜度最小的是____。冒泡排序希爾排序C簡單項選擇擇排序歸并排序正確答案:D單項選擇題3.帶頭結(jié)點(diǎn)的單鏈表Head為空表的判斷條件是______。Head->next==HeadHead->next==NULLHead!=NULLHead==NULL正確答案:B單項選擇題4.若用二分查找法獲取的中間地址元素鍵值大于被查找值，說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始地址至____。該中間地址該中間地址－1該中間地址＋1D該中間地址／2正確答案:B單項選擇題5.一組記錄的要點(diǎn)字為（46,79,56,38,40,84）,則利用快速排序的方法，以第一個記錄為基準(zhǔn)元素獲取的一次劃分結(jié)果為。38,40,46,56,79,8440,38,46,79,56,8440,38,46,56,79,8440,38,46,84,56,79正確答案:C單項選擇題6.下面關(guān)于圖的儲藏的表達(dá)中，哪一個是正確的？A用相鄰矩陣法儲藏圖,占用的儲藏空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān),而與邊數(shù)沒關(guān)B用相鄰矩陣法儲藏圖,占用的儲藏空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個數(shù)沒關(guān)C用毗鄰表法儲藏圖，占用的儲藏空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與邊數(shù)沒關(guān)用毗鄰表法儲藏圖，占用的儲藏空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個數(shù)沒關(guān)正確答案:A單項選擇題7.擁有5個極點(diǎn)的有向完好圖有____條弧。10162025正確答案:C單項選擇題8.數(shù)據(jù)構(gòu)造課程主要研究以下三方面的內(nèi)容，它們是______。數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)種類數(shù)據(jù)元素、數(shù)據(jù)種類、算法實現(xiàn)C數(shù)據(jù)元素、數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的儲藏構(gòu)造數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的儲藏構(gòu)造、數(shù)據(jù)的運(yùn)算正確答案:D單項選擇題9.設(shè)二叉樹根結(jié)點(diǎn)的層次為1，全部含有15個結(jié)點(diǎn)的二叉樹中，最小高度是_____。6543正確答案:C單項選擇題10.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹必然是_____的二叉樹?？栈蛑挥幸粋€結(jié)點(diǎn)高度等于其結(jié)點(diǎn)數(shù).任一結(jié)點(diǎn)無左孩子任一結(jié)點(diǎn)無右孩子正確答案:A單項選擇題11.鏈表不擁有的特點(diǎn)是_____?？呻S機(jī)接見任一元素插入和刪除不需要搬動元素C不用早先估計儲藏空間所需空間和線性表長度成正比正確答案:A單項選擇題12.在一個長度為n的次序表中，在第i個元素（1<=i<=n）從前插入一個新元素時需向后搬動_______個元素。1n-in-i-1n-i+1正確答案:D單項選擇題13.關(guān)于一個擁有n個極點(diǎn)和e條邊的無向圖，若采用毗鄰表表示，毗鄰表中全部結(jié)點(diǎn)總數(shù)是_____。e/22een+e正確答案:B單項選擇題14.設(shè)某二維數(shù)組A［1..n，1..n］，則在該數(shù)組中用次序查找法查找一個元素的時間復(fù)雜性的量級為______。O（log2n）O(n)O(nlog2n)O(n^2)正確答案:D單項選擇題15.以下關(guān)于圖的生成樹的獨(dú)一性，正確的選項是_____。生成樹是獨(dú)一的生成樹是不獨(dú)一的C生成樹是獨(dú)一性不確定圖的生成樹有兩棵正確答案:C單項選擇題16.在數(shù)據(jù)構(gòu)造中，與所使用的計算機(jī)沒關(guān)的是數(shù)據(jù)的____構(gòu)造。儲藏物理C邏輯物理與儲藏正確答案:C單項選擇題17.線性表采用鏈?zhǔn)絻Σ貢r，其地址_____。必定是連續(xù)的必定是不連續(xù)的C連續(xù)與否均可部分地址必定是連續(xù)的正確答案:C單項選擇題18.設(shè)有1000個無序的元素,希望用最快的速度優(yōu)選出其中前10個最大的元素,最好____排序法。起泡排序快速排序C堆排序基數(shù)排序正確答案:C單項選擇題19.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里我們把由樹轉(zhuǎn)變獲取的二叉樹叫做這棵樹對應(yīng)的二叉樹。那么以下結(jié)論中_____是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同以上都不對正確答案:A單項選擇題20.在某棵二叉樹的一種序列中，若是發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判判斷這種序列為中序序列。正確不正確正確答案:A單項選擇題21.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對次序____。不發(fā)生變化發(fā)生變化C不能夠確定以上都不對正確答案:A單項選擇題22.作進(jìn)棧操作時，應(yīng)先判斷棧可否為_____?？諠MC上溢下溢正確答案:B單項選擇題23.一個棧的入棧序列是a,b,c,d,則以下序列中不能能的輸出序列是_______。acbddcbaacdbdbac正確答案:D單項選擇題24.線性表按鏈?zhǔn)椒绞絻Σ貢r，每個結(jié)點(diǎn)的儲藏包括_____兩部分。數(shù)據(jù)值與符號數(shù)據(jù)與指針C數(shù)據(jù)與表名數(shù)據(jù)項與符號正確答案:B單項選擇題25.判斷一個循環(huán)隊列是空隊列的條件是_____。BQ.front==0Q.rear==0正確答案:A單項選擇題26.當(dāng)字符序列x5y作為字符貨倉的輸入時，輸出長度為3的且能夠作為C語言表記符的個數(shù)是____。3個4個5個6個正確答案:A單項選擇題27.若某貨倉的輸入序列為1，2，3，，n-1，n，輸出序列的第1個元素為n，則第i個輸出元素為______。n-i+ln-ii哪個元素?zé)o所謂正確答案:A單項選擇題28.一組記錄的排序碼為（20,29,11,74,35,3,8,56），則利用堆排序方法建立的初始(小頂)堆為____。A20,29,11,74,35,3,8,56B3,29,8,56,35,20,11,743,8,11,20,29,35,56,7420,29,3,8,11,35,74,56正確答案:B單項選擇題29.用某種排序方法對線性表(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則所采用的排序方法是____。選擇排序希爾排序C歸并排序快速排序正確答案:D單項選擇題30.在一個無向圖中，全部極點(diǎn)的度數(shù)之和等于全部邊數(shù)的____倍。1/2124正確答案:C單項選擇題31.若要求能快速地實現(xiàn)在鏈表的尾端插入和刪除結(jié)點(diǎn)的運(yùn)算，則選擇_____最合適。單鏈表帶尾指針的單循環(huán)鏈表C雙鏈表雙循環(huán)鏈表正確答案:B單項選擇題32.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。插入排序快速排序C歸并排序選擇排序正確答案:A單項選擇題33.采用不帶尾指針的單鏈表方式表示一個棧，便于結(jié)點(diǎn)的插入與刪除。棧頂結(jié)點(diǎn)的插入與刪除平時在鏈表的_____進(jìn)行。任意地址鏈表頭尾兩端C鏈表頭一端鏈表尾一端正確答案:C單項選擇題34.對線性表進(jìn)行二分查找時，要求線性表必定____。以次序方式儲藏以次序方式儲藏且元素有序C以鏈?zhǔn)椒绞絻Σ匾枣準(zhǔn)椒绞絻Σ厍以赜行蛘_答案:B單項選擇題35.向一個有115個元素的次序表中插入一個新元素并保持原來次序不變，平均要搬動_____個元素。1151145857正確答案:C單項選擇題36.樹最合適用來表示_____。有序數(shù)據(jù)元素?zé)o序數(shù)據(jù)元素C元素之間擁有分支層次關(guān)系的數(shù)據(jù)元素之間無聯(lián)系的數(shù)據(jù)正確答案:C單項選擇題37.設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包括的結(jié)點(diǎn)數(shù)最少為____(注意h為指數(shù))。2h-12(h-1)C2*h-1D2*h正確答案:A單項選擇題38.若由森林轉(zhuǎn)變獲取的二叉樹是非空的二叉樹，則二叉樹形狀是____。根結(jié)點(diǎn)無右子樹的二叉根結(jié)點(diǎn)無左子樹的二叉樹C根結(jié)點(diǎn)可能有左二叉樹和右二叉樹各結(jié)點(diǎn)只有一個兒子的二叉樹正確答案:C單項選擇題39.若是某二叉樹的先序遍歷序列是abdcef，中序遍歷序列是dbaefc，則以后序遍歷序列是____。dbafecfecdbaefcdbadbfeca正確答案:D單項選擇題40.次序表的特點(diǎn)是______。邏輯上相鄰的結(jié)點(diǎn)其物理地址不相鄰邏輯上相鄰的結(jié)點(diǎn)其物理地址亦相鄰C次序表不是隨機(jī)儲藏構(gòu)造在次序表中插入和刪除操作比在鏈表上方便正確答案:B單項選擇題41.一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不能能的出棧序列是_____。edcbadceabdecbaabcde正確答案:B單項選擇題42.毗鄰表是圖的一種____。次序儲藏構(gòu)造鏈?zhǔn)絻Σ貥?gòu)造C索引儲藏構(gòu)造散列儲藏構(gòu)造正確答案:B單項選擇題43.若構(gòu)造一棵擁有n個結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會高出____。n/2n(n+1)/2n+1正確答案:B單項選擇題44.設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包括的結(jié)點(diǎn)數(shù)至多為_____(注意h是指數(shù))。2h-12(h-1)2*h-12*h正確答案:A單項選擇題45.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是____。acbeddecabdeabccedba正確答案:D單項選擇題46.在長度為n的雙鏈表中某結(jié)點(diǎn)（已知其地址）從前，插入一個新結(jié)點(diǎn)的時間復(fù)雜度是_____。O(n)O(log2n)O(1)O(n^2)正確答案:C單項選擇題47.已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為____。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單項選擇題48.設(shè)a,b為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時，a在b前的條件是____。Aa是b祖先Ba是b后輩Ca在b左方Da在b右方正確答案:C單項選擇題若是無向圖G必定進(jìn)行二次廣度優(yōu)先找尋才能接見其全部極點(diǎn)，則以下說法中不正確的選項是_____。G必然不是完好圖G必然不是連通圖G中必然有回路G有2個連通重量正確答案:C單項選擇題50.棧構(gòu)造平時采用的兩種儲藏構(gòu)造是_____。線性儲藏構(gòu)造和鏈表儲藏構(gòu)造散列方式和索引方式C鏈表儲藏構(gòu)造和數(shù)組線性儲藏構(gòu)造和非線性儲藏構(gòu)造正確答案:D單項選擇題51.有m個葉子結(jié)點(diǎn)的Huffman樹所擁有的結(jié)點(diǎn)總數(shù)為____。m+12m-12m2m+1正確答案:B單項選擇題52.關(guān)于二叉樹的三種遍歷，以下說法正確的選項是____。任意兩種遍歷序列都不能夠夠獨(dú)一決定該二叉樹任意兩種遍歷序列都能夠獨(dú)一決定該二叉樹C先序遍歷序列和后序遍歷序列能夠獨(dú)一決定該二叉樹先序遍歷序列和中序遍歷序列能夠獨(dú)一決定該二叉樹正確答案:D單項選擇題53.在一個擁有n個結(jié)點(diǎn)的有序單鏈表中，插入一個新的結(jié)點(diǎn)并使之依舊有序的時間復(fù)雜度是______。AO(n)BO(log2n)CO(1)DO(n^2)正確答案:A單項選擇題54.關(guān)于無向連通圖的最小生成樹的個數(shù)_____。A必然有多棵B必然只有一棵C有一棵或多棵D可能不存在正確答案:B單項選擇題55.在次序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找要點(diǎn)碼12需做____次要點(diǎn)碼比較。A2B3C4D5正確答案:C單項選擇題56.隊列的操作原則是_____。先進(jìn)先出先進(jìn)后出C只能進(jìn)行插入只能進(jìn)行刪除正確答案:A單項選擇題57.對次序儲藏的線性表，設(shè)其長度為n，且在任何地址上插入或刪除操作都是等概率的。則插入一個元素時平均要搬動表中的_____個元素。n/2(n+1)/2(n-1)/2n正確答案:A單項選擇題58.設(shè)n個極點(diǎn)e條邊的圖G用毗鄰表儲藏，則求每個極點(diǎn)入度的時間復(fù)雜度為____。O(n)O(n+e)O(n*n)O(n*e)正確答案:B單項選擇題59.將10個元素散列到100000個單元的散列表中，則__________產(chǎn)生矛盾。必然會必然不會C仍可能會正確答案:C單項選擇題60.計算機(jī)算法是指______。計算方法排序方法C調(diào)換方法解決問題的有限運(yùn)算序列正確答案:D判斷題61.在某個實例的排序結(jié)果看出，值相同的兩個要點(diǎn)字排序前后當(dāng)先關(guān)系不變，由此可知該排序方法是牢固的。正確錯誤正確答案:錯判斷題62.哈希表是用于查找的技術(shù)之一。正確錯誤正確答案:對判斷題63.連通圖的廣度優(yōu)先找尋中一般要采用隊列來暫存剛接見過的極點(diǎn)。正確錯誤正確答案:對判斷題64.在n個元素的次序表中刪除第i個元素，需要搬動n-i個元素。正確錯誤正確答案:對判斷題65.5個極點(diǎn)的無向圖，若不連通，則最多可能有6條邊。正確錯誤正確答案:對判斷題66.二叉排序樹一般用于查找某個元素。正確錯誤正確答案:對判斷題67.任何一個森林都能夠獨(dú)一地與一棵二叉樹對應(yīng)。正確錯誤正確答案:對判斷題68.由二叉樹的前序和中序遍歷序列可獨(dú)一構(gòu)造這棵二叉樹。正確錯誤正確答案:對判斷題69.有向圖各極點(diǎn)入度之和就等于邊的數(shù)量。正確錯誤正確答案:對判斷題70.滿二叉樹必然是完好二叉