【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-電子科技大學(xué) 中國大學(xué)慕課MOOC答案

【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-電子科技大學(xué)中國大學(xué)慕課MOOC答案緒論測驗(yàn)1、【單選題】下面（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)本題答案：【隊(duì)列】2、【單選題】算法分析的目的是（）本題答案：【分析算法的效率以求改進(jìn)】3、【單選題】下面程序段的時間復(fù)雜度是（）for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;本題答案：【O(n*m)】4、【單選題】下面程序段的時間復(fù)雜度是（）i=s=0;while(sn){i++;s+=i;}本題答案：【O(sqrt(n))注釋：sqrt(n)表示對n開方】5、【單選題】下面程序段的時間復(fù)雜度是（）i=1;while(i=n)i=i*3;本題答案：【O(logn)注釋：對數(shù)復(fù)雜度】6、【判斷題】數(shù)據(jù)的關(guān)系有邏輯關(guān)系和存儲關(guān)系。其中邏輯關(guān)系是進(jìn)行算法分析和設(shè)計需要考慮與使用的，而存儲關(guān)系是編程實(shí)現(xiàn)的時候需要考慮的，邏輯關(guān)系和存儲關(guān)系之間并沒有關(guān)系本題答案：【錯誤】7、【判斷題】下面的遞歸函數(shù)時間復(fù)雜度是O(1)intfact(intn){if(n=1)return1;elsereturnn*fact(n-1);}本題答案：【錯誤】8、【判斷題】算法和程序都不能無窮的，否則會進(jìn)入死循環(huán)本題答案：【錯誤】9、【判斷題】數(shù)據(jù)包含數(shù)據(jù)對象，數(shù)據(jù)對象包含數(shù)據(jù)元素，數(shù)據(jù)元素包含數(shù)據(jù)項(xiàng)。本題答案：【正確】10、【判斷題】算法可以用不同的語言描述，比如C或者java，所以算法實(shí)際上就是程序。本題答案：【錯誤】線性表測驗(yàn)1、【單選題】雙向鏈表中有2個指針域pre和next，分別指向直接前驅(qū)和直接后繼，假設(shè)有指針p指向鏈表中的一個結(jié)點(diǎn)，指針q指向一個待插入的結(jié)點(diǎn)，現(xiàn)在要求在p的前面插入q所指結(jié)點(diǎn)，則正確的插入語句為（）本題答案：【p-pre-next=q;q-next=p;q-pre=p-pre;p-pre=q;】2、【單選題】在一個具有n個鏈結(jié)點(diǎn)的線性鏈表中，按數(shù)據(jù)內(nèi)容查找某一個結(jié)點(diǎn)，如果查找成功，需要平均比較（）個結(jié)點(diǎn)。本題答案：【(n+1)/2】3、【單選題】假設(shè)按照行優(yōu)先存儲整數(shù)數(shù)組A[9][8]，第一個元素a11的首字節(jié)地址是100，每個整數(shù)占4個字節(jié)，則元素a32的存儲地址是（）提示：數(shù)組大小是9行8列，第一個位置是1，不是0本題答案：【168】4、【單選題】一個棧的入棧序列是a,b,c,d,e,則不可能的出棧輸出序列是（）本題答案：【dceab】5、【單選題】當(dāng)對一個線性表經(jīng)常進(jìn)行存取而很少進(jìn)行插入及刪除操作時，采用（）存儲結(jié)構(gòu)最節(jié)省時間；如果經(jīng)常進(jìn)行插入，刪除操作時，則采用（）存儲結(jié)構(gòu)最節(jié)省時間。本題答案：【順序，鏈?zhǔn)健?、【單選題】設(shè)順序表L是一個非遞減的有序表，下面的哪個算法，能夠?qū)⒃豿插入L中，并使L仍然有序。本題答案：【//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=L-length-1;while(i=0){if(xL-data[i]){L-data[i+1]=L-data[i];--i;}}L-data[i]=x；L-length+=1;}】7、【單選題】已知數(shù)據(jù)3,4,-2,0,8存儲在順序存儲結(jié)構(gòu)中，編程實(shí)現(xiàn)刪除x的操作為（）提示：數(shù)據(jù)從順序存儲結(jié)構(gòu)的第0個位置開始存儲本題答案：【voiddel(SqListL,elemtypex){inti=0;while(iL.length){if(L.data[i]!=x){i++;}elsebreak;}while(iL.length-1){L.data[i]=L.data[i+1];i++;}L.length--;}】8、【單選題】已知不帶頭結(jié)點(diǎn)的單鏈表L，下面用函數(shù)實(shí)現(xiàn)的在第一個元素前面插入值為x的元素結(jié)點(diǎn)的算法錯誤的是（）本題答案：【voidinsert(List*L,elemtypex){ptrp=*L;noded=newnode(x);ptrq=d;p-next=q;L=q;}】9、【單選題】下面程序段的輸出結(jié)果是（）voidmain(){QueueQ;InitQueue(Q);charx='e',y='c';EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a‘);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);本題答案：【char】10、【單選題】當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時，可用折半查找，也可用順序查找，但前者比后者的查找速度()本題答案：【大部分情況下快】11、【單選題】已知有一系列輸入數(shù)據(jù)為32,14,78,2,62,5,需要得到5,2,2,7,4,2，請問用什么數(shù)據(jù)結(jié)構(gòu)支撐算法？本題答案：【用棧將數(shù)據(jù)全部入棧，再出棧，出棧的數(shù)據(jù)取個位，就得到需要的輸出序列?！?2、【單選題】關(guān)鍵字越大，優(yōu)先級越高。為了更好的為優(yōu)先級高的顧客服務(wù)，銀行應(yīng)該采用什么存儲結(jié)構(gòu)支撐算法？本題答案：【有序鏈表】查找測驗(yàn)1、【單選題】已知在長度為n的線性表中采用順序查找，查找成功最好的比較次數(shù)是（），查找成功的最壞比較次數(shù)是（），查找失敗的比較次數(shù)是（）本題答案：【1，n,n】2、【單選題】長度為n的有序順序表采用折半查找，查找成功的最少次數(shù)為（），查找成功的最大次數(shù)為（），查找失敗的最大次數(shù)為（），所以折半查找的最壞時間復(fù)雜度為（）本題答案：【1,logn,logn,O(logn)】3、【單選題】查找表如下分組(3,7,1,8,15),(22,43,18,45),(60,58,82,77,62),(90,88,99,100)，則索引表為（）,查找58需要比較（）次本題答案：【(15,1),(45,6),(82,10),(100,15),(NULL,19)5?】4、【單選題】查找表32,45,18,77,5,23,44,19,7,3,哈希函數(shù)為H(key)=key%5,采用鏈地址法解決沖突的ASL(成功）=（），采用表長為11的線性探測再散列開放地址法的ASL(成功）=（），本題答案：【18/10，32/10】5、【單選題】哈希函數(shù)H(k)=k%11,采用開放地址法的平方探測再散列（di=1,4,9,16,......)解決沖突，輸入關(guān)鍵字（9,31,26,19,1,13,2,11,27,16,21)，表長為13，建立的哈希表為（），ASL(成功）=（）本題答案：【地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121122ASL（成功）=15/11?】討論：歸并排序問題1、【單選題】3,1,34,25,51,2,11采用迭代法，第一趟排序后的序列是（）本題答案：【1,3,25,34,2,51,11】2、【單選題】3,1,34,25,51,2,11采用歸并排序的分治方法，第一趟劃分的位置是（）本題答案：【(3,1,34,25),(51,2,11)】討論：快速排序問題1、【單選題】13，27，9，5，89，72，4的樞紐是（）本題答案：【以上都可以，看選擇樞紐的方法】2、【單選題】13，27，9，5，89，72，4進(jìn)行快速排序，13為樞紐，第一次快排后的序列為（）本題答案：【以上都對，快速排序?qū)⒈葮屑~小的數(shù)據(jù)放到樞紐前面，比樞紐大的放到樞紐大的數(shù)據(jù)放到后面的具體方法不同，可能得到不同的序列。】排序測驗(yàn)1、【單選題】請對下列數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，進(jìn)行簡單插入排序，冒泡排序（每趟大數(shù)冒到后面）和選擇排序，2趟后的排序結(jié)果為：（）本題答案：【2趟后的簡單插入排序序列為：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序?yàn)椋?，1，8，9，11，13，24，34，2，51，5，56，772趟后的選擇排序?yàn)椋?，2，7，13，8，9，11，56，34，51，24，77，5】2、【單選題】已知輸入數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，請采用2路歸并遞歸排序算法進(jìn)行排序，2趟排序后的結(jié)果為（）本題答案：【1，7，13，24，8，9，11，34，51，56，2，5，77】3、【單選題】已知輸入數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，請采用快速歸排序算法進(jìn)行排序，其中樞紐采用3者取中法，2趟排序后的結(jié)果為（）注意：答案中的括號表示快排中的分組本題答案：【（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））】4、【單選題】已知輸入數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，增量序列d=5,3,1,請采用希爾排序算法進(jìn)行排序，2趟排序后的結(jié)果為（）本題答案：【1，7，5，2，8，9，24，11，34，51，13，77，56】5、【單選題】已知輸入數(shù)據(jù)1，2，8，5，9，11，34，56，51，77，請分析數(shù)據(jù)，采用（）排序算法效率最低本題答案：【選擇排序】遞歸與分治測驗(yàn)1、【單選題】已知某遞歸算法的復(fù)雜度為：T(n)=2T(n/2)+4,則求解該遞歸式的解為：（）本題答案：【T(n)=O(n)】2、【單選題】分治法所能解決的問題一般具有以下幾個特征:1.該問題的規(guī)模縮小到一定的程度就可以容易地解決；2.____________3.利用該問題分解出的子問題的解可以合并為該問題的解；4.該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。本題答案：【最優(yōu)子結(jié)構(gòu)】3、【單選題】求一個數(shù)據(jù)序列的逆序數(shù)量不可以通過______排序中增加1個計數(shù)器實(shí)現(xiàn)。提示:一個排列含有逆序的個數(shù)稱為這個排列的逆序數(shù)。例如排列263451含有8個逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此該排列的逆序數(shù)就是8。本題答案：【堆排序#樹形選擇排序】4、【單選題】下面（）說法是正確的本題答案：【大部分遞歸程序可以轉(zhuǎn)換為非遞歸程序，非遞歸程序運(yùn)行速度更快。#尾遞歸可以轉(zhuǎn)換為循環(huán)】5、【單選題】已知求一組數(shù)據(jù)連續(xù)若干數(shù)和的最大值采用分治方法得到O(nlogn)的時間復(fù)雜度，請完成下面分治法求解的代碼：/************************************************************************//*分治法最大和子數(shù)組有三種情況：1)A[1...mid]2)A[mid+1...N]3)A[i..mid..j]/************************************************************************///findmaxcrossingleftandrightintFind_Max_Crossing_Subarray(intarr[],intlow,intmid,inthigh){constintinfinite=-9999;intleft_sum=infinite;intright_sum=infinite;intmax_left=-1,max_right=-1;intsum=0;//frommidtoleft;for(inti=mid;i=low;i--){sum+=arr[i];if(sumleft_sum){left_sum=sum;max_left=i;}}sum=0;//frommidtorightfor(intj=mid+1;j=high;j++){sum+=arr[j];if(sumright_sum){right_sum=sum;max_right=j;}}return(left_sum+right_sum);}intFind_Maximum_Subarray(intarr[],intlow,inthigh){if(high==low)//onlyoneelement;returnarr[low];else{intmid=(low+high)/2;intleftSum=Find_Maximum_Subarray(arr,low,mid);intrightSum=Find_Maximum_Subarray(arr,mid+1,high);intcrossSum=Find_Max_Crossing_Subarray(arr,low,mid,high);——————————完成這里的代碼——————————————————}}本題答案：【inttmp=(leftSumrightSum?leftSum:rightSum;return(tmpcrossSum?tmp:crossSum);】6、【填空題】已知求一組數(shù)據(jù)連續(xù)若干數(shù)和的最大值采用分治方法得到O(nlogn)的時間復(fù)雜度，請完成下面分治法求解的代碼：/************************************************************************//*分治法最大和子數(shù)組有三種情況：1)A[1...mid]2)A[mid+1...N]3)A[i..mid..j]/************************************************************************///findmaxcrossingleftandrightintFind_Max_Crossing_Subarray(intarr[],intlow,intmid,inthigh){constintinfinite=-9999;intleft_sum=infinite;intright_sum=infinite;intmax_left=-1,max_right=-1;intsum=0;//frommidtoleft;for(inti=mid;i=low;i--){sum+=arr[i];if(sumleft_sum){left_sum=sum;max_left=i;}}sum=0;//frommidtorightfor(intj=mid+1;j=high;j++){sum+=arr[j];if(sumright_sum){right_sum=sum;max_right=j;}}return(left_sum+right_sum);}intFind_Maximum_Subarray(intarr[],intlow,inthigh){if(high==low)//onlyoneelement;returnarr[low];else{intmid=(low+high)/2;intleftSum=Find_Maximum_Subarray(arr,low,mid);intrightSum=Find_Maximum_Subarray(arr,mid+1,high);intcrossSum=Find_Max_Crossing_Subarray(arr,low,mid,high);——————————完成這里的代碼——————————————————}}注意為了盡量減少答案的多樣性，本次編程代碼請通過而不是符號進(jìn)行數(shù)據(jù)的比較。按照leftSum,rightSum,crossSum的順序進(jìn)行比較。運(yùn)算符和操作數(shù)之間需要一個空格（括號除外）。如果造成困惑請見諒！本題答案：【if(leftSum>=rightSum&&leftSum>=crossSum)returnleftSum;elseif(rightSum>=leftSum&&rightSum>=crossSum)returnrightSum;elsereturncrossSum;##%_YZPRLFH_%##if(leftSum>rightSum){if(leftsum>crossSum)returnleftsum;elsereturncrossSum;}elseif(rightSum>crossSum)returnrightSum;elsereturncrossSum;##%_YZPRLFH_%##return((leftSum>rightSum?leftSum:rightSum)>crossSum?(leftSum>rightSum?leftSum:rightSum):crossSum;##%_YZPRLFH_%##return((leftSum>corssSum?leftSum:corssSum)>rightSum?(leftSum>corssSum?leftSum:corssSum):rightSum;】7、【填空題】已知某遞歸算法的復(fù)雜度為：T(n)=2T(n/2)+4,則求解該遞歸式的解為：（）本題答案：【O(n)】8、【填空題】分治法所能解決的問題一般具有以下幾個特征:1.該問題的規(guī)?？s小到一定的程度就可以容易地解決；2.____________3.利用該問題分解出的子問題的解可以合并為該問題的解；4.該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。本題答案：【最優(yōu)子結(jié)構(gòu)】9、【填空題】求一個數(shù)據(jù)序列的逆序數(shù)量可以通過______排序中增加1個計數(shù)器實(shí)現(xiàn)。提示:一個排列含有逆序的個數(shù)稱為這個排列的逆序數(shù)。例如排列263451含有8個逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此該排列的逆序數(shù)就是8。本題答案：【歸并##%_YZPRLFH_%##簡單插入##%_YZPRLFH_%##冒泡】10、【填空題】大部分遞歸程序可以轉(zhuǎn)換為非遞歸程序，____程序運(yùn)行速度更快。本題答案：【非遞歸】討論：二叉樹的復(fù)原1、【填空題】已知一顆二叉樹其中序和后序遍歷為：中序：BDCEAFHG,后序:DECBHGFA請給出先序遍歷結(jié)果：（）注意：答案要求全部大寫，輸出的先序遍歷結(jié)果的各個符號之間沒有空格。本題答案：【ABCDEFGH】討論：二叉樹的遍歷順序1、【判斷題】二叉樹只能從左到右遍歷，不能從右到左遍歷本題答案：【錯誤】討論：二叉排序樹的建立1、【單選題】輸入一組序列3，6，1，2，7，4,通過下面方法正確建立二叉排序樹本題答案：【先建立空樹，然后采用二叉排序樹插入新結(jié)點(diǎn)的方法，按照輸入數(shù)據(jù)順序依次插入每一個數(shù)據(jù)到二叉排序樹當(dāng)中，直到所有數(shù)據(jù)插入完成，則得到一顆有n個結(jié)點(diǎn)的二叉排序樹?！坑懻摚旱怪眯№敹咽遣皇且欢ㄊ谴箜敹?？1、【判斷題】倒置小頂堆一定是大頂堆本題答案：【錯誤】樹與二叉樹測驗(yàn)1、【單選題】已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序樹的查找成功的平均查找長度ASL為()注意：結(jié)果用最簡分?jǐn)?shù)形式本題答案：【39/11】2、【單選題】已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的平衡二叉樹AVL的查找成功的平均查找長度ASL為()注意：結(jié)果用最簡分?jǐn)?shù)形式本題答案：【3】3、【單選題】已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40構(gòu)造小頂堆，按照層序輸出的關(guān)鍵字序列為：（）注意：用空格分隔輸出序列本題答案：【1517272130369454288340】4、【單選題】已知由一組字符組成的字符串，其中各個字符的訪問次數(shù)分別為17,28,36,54,30,27,94,15,21,83,40，請對該字符串中的字符進(jìn)行最優(yōu)編碼，其最優(yōu)編碼的帶權(quán)路徑長度為（）本題答案：【1447】5、【單選題】3個不同的結(jié)點(diǎn)，可以構(gòu)成（）顆不同的二叉樹本題答案：【5】6、【單選題】已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序樹，刪除關(guān)鍵字36的結(jié)點(diǎn)的最佳操作是（）本題答案：【用右子樹的最小關(guān)鍵字40替換關(guān)鍵字結(jié)點(diǎn)36】7、【單選題】如果一顆二叉樹具有10個度為2的結(jié)點(diǎn)和5個度為1的結(jié)點(diǎn)，則有（）個葉子結(jié)點(diǎn)本題答案：【11】8、【單選題】假設(shè)完全二叉樹的樹根為第1層，樹中第10層有5個葉子結(jié)點(diǎn)，則完全二叉樹最多有（）個結(jié)點(diǎn)。本題答案：【2037】9、【單選題】二叉樹的先序和中序遍歷序列相同，則此二叉樹為（）本題答案：【任一結(jié)點(diǎn)無左子樹】10、【單選題】一棵完全二叉樹上有1001個結(jié)點(diǎn)，其葉子結(jié)點(diǎn)的個數(shù)是()本題答案：【501】11、【單選題】二叉樹的先序序列是EFHIGJK，中序序列為HFIEJKG，該二叉樹右子樹的根是()本題答案：【G】12、【單選題】下列四個序列中，哪一個是堆()本題答案：【75,45,65,30,15,25,20,10】13、【單選題】在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序()本題答案：【完全相同】14、【單選題】二叉排序樹的()結(jié)果是一個關(guān)鍵字的遞增有序序列本題答案：【中序遍歷】15、【單選題】給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)是()本題答案：【2n-1】貪心算法測驗(yàn)1、【單選題】要連通具有n個頂點(diǎn)的無向圖，至少需要（）條邊本題答案：【n-1】2、【單選題】本題答案：【（1，2）（2，4）（4，5）（5，6）（6，3）#（1，2）（2，4）（4，5）（5，6）（2，3）】3、【單選題】用kruscal算法，按順序輸出最小生成樹的各邊（）本題答案：【（5，6）（4，5）（2，4）（1，2）（2，3）#（5，6）（4，5）（2，4）（1，2）（2，3）#（5，6）（4，5）（2，4）（1，2）（6，3）】4、【單選題】利用dijkstra算法計算從節(jié)點(diǎn)1到其他節(jié)點(diǎn)的最短路徑，算法執(zhí)行到下圖狀態(tài)之后，接下來應(yīng)該把哪個節(jié)點(diǎn)添加到探索集中？（）本題答案：【結(jié)點(diǎn)5】5、【單選題】程序存儲問題問題描述：假設(shè)有n個程序（1,2,3....,n）要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是,.程序存儲問題要求確定這n個程序在磁帶上的一個存儲方案，使得盡量快地能夠在磁帶上存儲盡可能多的程序。數(shù)據(jù)輸入：第一行讀入2個正整數(shù)，分別表示文件個數(shù)n和磁帶程度L;第二行讀入n個正整數(shù)，分別表示n個文件存儲在磁帶上的長度。輸出：輸出1個整數(shù)數(shù)為滿足要求的最多存儲的文件數(shù)輸入示例：650231388020輸出：5下面的選項(xiàng)正確的是（）本題答案：【先如果,則將所有程序都可以放入磁帶，因此能夠存放的最多程序數(shù)量為n。否則，將程序按照在磁帶上的存儲長度非遞減排序，假設(shè)排序后，第i個程序的長度為,其中且。則采用貪心算法，將程序長度最小的程序依次存放到磁帶上，直到第k個磁帶不能存儲到磁帶，則結(jié)束。磁帶能夠存放的程序個數(shù)為k-1(kn),滿足：且】6、【單選題】某一工程作業(yè)的網(wǎng)絡(luò)圖如圖所示，其中箭頭表示作業(yè)，箭頭上的數(shù)字表示完成作業(yè)所需的天數(shù)。箭頭前后的圓圈表示事件，圓圈中的數(shù)字表示事件的編號。用事件編號的序列（例如0-3-4-8-10-11）表示進(jìn)行作業(yè)的路徑。其中0表示工程開始，11表示工程的結(jié)束。求（1）完成此工程的關(guān)鍵路徑；（2）完成此工程所需的最少天數(shù)本題答案：【（1）關(guān)鍵路徑上的事件為：0-2-6-9-11（2）20天】7、【單選題】求城市a到其他城市的最短距離及路線本題答案：【a到其他城市的最短距離及路徑分別為：(1)a-b:23(2)a-c:18(3)a-c-e:30(4)a-c-e-d:36(5)a-c-e-f:39(6)a-c-e-g:55】8、【單選題】汽車加油問題問題描述：一輛汽車加滿油可以行駛n公里（km)。旅途中有若干加油站。設(shè)計1個有效算法，指出應(yīng)該在哪些加油站加油，使得沿途加油次數(shù)最少。數(shù)據(jù)輸入：第一行2個正整數(shù)n和k，表示汽車加滿油可以行駛n公里，沿途有k個加油站。第二行有k+1個正整數(shù)，表示第i個加油站和第i+1個加油站的距離。第0個加油站是出發(fā)地，汽車已經(jīng)加滿油，第k+1個加油站代表目的地。輸出：輸出1個正整數(shù)表示最少加油次數(shù)輸入示例：7712345166輸出結(jié)果：4下面說法不正確的是（）本題答案：【采用貪心算法，每一個加油站都去加油，使得油箱出發(fā)的時候都是滿的，即使加油站隔的很遠(yuǎn)，比如大于n公里，也能夠開到下一個加油站。】9、【單選題】最小生成樹除了prim和kuscal算法，還有沒有其他的算法？本題答案：【還有其他算法，包括破圈法在內(nèi)的其他最小生成樹算法，效率沒有比prim或者kruscal算法更好。#還有其他算法，包括破圈法在內(nèi)的其他最小生成樹算法，效率沒有比prim或者kruscal算法更好。prim算法適合稠密圖，kurscal算法適合稀疏圖。】10、【單選題】下圖不是合法的拓?fù)渑判蛴校ǎ┍绢}答案：【ACDBEF】動態(tài)規(guī)劃測驗(yàn)1、【單選題】動態(tài)規(guī)劃與貪心算法的最大區(qū)別（）本題答案：【貪心算法不是遞歸問題，動態(tài)規(guī)劃是遞歸問題】2、【單選題】動態(tài)規(guī)劃與分治遞歸的最大區(qū)別（）本題答案：【分治遞歸的子問題如果有重疊，采用動態(tài)規(guī)劃比分治遞歸求解效率更高】3、【單選題】找零錢問題用（）算法本題答案：【貪心算法，不能得到全局最優(yōu)解】4、【單選題】關(guān)于背包問題，正確的是（)本題答案：【01背包用動態(tài)規(guī)劃求解，部分背包用貪心算法求解】5、【單選題】用動態(tài)規(guī)劃的前提條件（）本題答案：【能夠分解為相似子問題，且子問題有重疊】6、【單選題】考慮下面的整數(shù)線性規(guī)劃問題：其中：是非負(fù)整數(shù)，且下面（）是正確求解過程本題答案：【首先給出該問題的子問題描述：且的最優(yōu)值為m(i,j)，也就是m(i,j)表示在背包容量是j，可以選擇物品1,2,...,i的時候背包問題的最優(yōu)值。由背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i,j)的遞歸關(guān)系式如下：m(i,j)=其中初始值，m(0,j)=m(i,0)=0,m(i,j)=】期末考試客觀題1、【單選題】下列說法不正確的是（）本題答案：【圖的深度遍歷不適用于有向圖】2、【單選題】當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時，可用折半查找，也可用順序查找，但前者比后者的查找速度(）本題答案：【在大部分情況下要快】3、【單選題】在下面的程序段中，對x的賦值語句的頻度為（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;本題答案：【】4、【單選題】一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1=i=n）個元素是（)本題答案：【n-i+1】5、【單選題】非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（)本題答案：【p-next=head】6、【單選題】要連通具有n個頂點(diǎn)的無向圖，至少需要（）條邊。本題答案：【n-l】7、【單選題】包含n個結(jié)點(diǎn)的二叉樹中，下列哪種二叉樹的高度不是保持在數(shù)量級（）本題答案：【排序二叉樹】8、【單選題】棧和隊(duì)都是（）本題答案：【限制存取點(diǎn)的線性結(jié)構(gòu)】9、【單選題】設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=keymod7，表長為10，用開放地址法的二次探測再散列方法Hi=(H(key)+di)mod10(di=1,4,9,…,)解決沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計算查找成功的平均查找長度。下面正確的是（）本題答案：【H(9)=9%7=2；H(01)=1%7=1；H(23)=23%7=2沖突H1(23)=(2+1)%10=3；H(14)=14%7=0；H(55)=55%7=6；H(20)=20%7=6沖突H1(20)=(6+1)%10=7；H(84)=84%7=0沖突H1(84)=(0+1)%10=1H2(84)=(0+4)%10=4；H(27)=27%7=6沖突H1(27)=(6+1)%10=7沖突H2(27)=(6+4)%10=0沖突H3(27)=(6+9)%10=5。平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=1