【MOOC答案】《數(shù)據(jù)結(jié)構(gòu)與算法》(電子科技大學(xué))章節(jié)作業(yè)慕課答案

【MOOC答案】《數(shù)據(jù)結(jié)構(gòu)與算法》(電子科技大學(xué))章節(jié)作業(yè)慕課答案

有些題目順序不一致，下載后按鍵盤ctrl+F進(jìn)行搜索第一章緒論緒論測驗1.單選題：下面程序段的時間復(fù)雜度是（）i=1;while(i＜=n)i=i*3;

選項：

A、O(n)

B、O(3*n)

C、O(n^3)注釋：n的立方的復(fù)雜度

D、O(logn)注釋：對數(shù)復(fù)雜度

答案：【O(logn)注釋：對數(shù)復(fù)雜度】2.單選題：下面程序段的時間復(fù)雜度是（）i=s=0;while(s＜p=""＞＜＞{i++;s+=i;}

選項：

A、O(n)

B、O(s)

C、O(sqrt(n))注釋：sqrt(n)表示對n開方

D、O(n^2)注釋：n^2表示求n的平方

答案：【O(sqrt(n))注釋：sqrt(n)表示對n開方】3.單選題：下面程序段的時間復(fù)雜度是（）for(i=0;i＜p=""＞＜＞for(j=0;j＜p=""＞＜＞A[i][j]=0;

選項：

A、O(n*m)

B、O(n)

C、O(m)

D、O(n+m)

答案：【O(n*m)】4.單選題：算法分析的目的是（）

選項：

A、找出數(shù)據(jù)結(jié)構(gòu)的合理性

B、研究算法的輸入與輸出的關(guān)系

C、分析算法的效率以求改進(jìn)

D、分析算法的易懂性和文檔性

答案：【分析算法的效率以求改進(jìn)】5.單選題：下面（）術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

選項：

A、順序表

B、鏈表

C、隊列

D、順序隊列

答案：【隊列】6.單選題：算法可以用不同的語言描述，比如C或者java，所以算法實際上就是程序。

選項：

A、正確

B、錯誤

答案：【錯誤】7.單選題：數(shù)據(jù)包含數(shù)據(jù)對象，數(shù)據(jù)對象包含數(shù)據(jù)元素，數(shù)據(jù)元素包含數(shù)據(jù)項。

選項：

A、正確

B、錯誤

答案：【正確】8.單選題：算法和程序都不能無窮的，否則會進(jìn)入死循環(huán)

選項：

A、正確

B、錯誤

答案：【錯誤】9.單選題：下面的遞歸函數(shù)時間復(fù)雜度是O(1)intfact(intn){if(n＜=1)return1;elsereturnn*fact(n-1);}

選項：

A、正確

B、錯誤

答案：【錯誤】10.單選題：數(shù)據(jù)的關(guān)系有邏輯關(guān)系和存儲關(guān)系。其中邏輯關(guān)系是進(jìn)行算法分析和設(shè)計需要考慮與使用的，而存儲關(guān)系是編程實現(xiàn)的時候需要考慮的，邏輯關(guān)系和存儲關(guān)系之間并沒有關(guān)系

選項：

A、正確

B、錯誤

答案：【錯誤】第二章2.1線性表（本章內(nèi)容比較多，需要2周的學(xué)習(xí)時間）線性表編程題1.合并兩個已排序的鏈表

題目內(nèi)容：給定兩個已升序排列的單鏈表（鏈表中允許有重復(fù)元素），合并這兩個鏈表，使其成為一個新的升序排序的單鏈表。下面給出了鏈表結(jié)點定義，各個函數(shù)的原型，及調(diào)用函數(shù)的main函數(shù)。同學(xué)們需要完成initList函數(shù)、以及mergeSortedLists函數(shù)的定義，和下面的代碼一起提交。#include#includetypedefstructNode{intvalue;structNode*next;}Node;//初始化鏈表，同時讀取并添加所有輸入的整數(shù)Node*initList(intN){//這是需要您們完成的第一個函數(shù)代碼}//遍歷并打印鏈表內(nèi)容voidprintList(Node*head){Node*current=head;while(current!=NULL){printf("%d",current->value);current=current->next;}printf("\n");}//合并鏈表Node*mergeSortedLists(Node*list1,Node*list2){//這是需要您們完成的第二個函數(shù)代碼}intmain(){intlen1,len2;scanf("%d",&len1);//初始化鏈表并讀取輸入數(shù)據(jù)Node*list1=initList(len1);scanf("%d",&len2);Node*list2=initList(len2);//合并有序鏈表Node*mergedList=mergeSortedLists(list1,list2);printList(mergedList);//釋放鏈表內(nèi)存Node*current=mergedList;while(current!=NULL){Node*next=current->next;free(current);current=next;}return0;}輸入格式：輸入分為兩部分：第一部分包含第一個鏈表的長度和隨后的空格分隔的元素列表。第一行為第一個有序鏈表長度，第二行為鏈表中的元素。第二部分包含第二個鏈表的長度和隨后的元素列表。第三行為第二個有序鏈表長度，第四行為鏈表中的元素。輸出格式：輸出合并后的鏈表的所有元素，每個元素之間用空格隔開，包括最后一個元素后面也有空格。最后輸出回車符號。輸入樣例：313541357輸出樣例：11335572.建立單鏈表

題目內(nèi)容：設(shè)計并實現(xiàn)自己的單鏈表，單鏈表中的節(jié)點應(yīng)該具備兩個屬性：value和next。value是當(dāng)前節(jié)點的值，next是指向下一個節(jié)點的指針/引用。題目輸入N個整數(shù)，按照輸入的順序建立不帶頭結(jié)點的單鏈表存儲數(shù)據(jù)，并遍歷所建立的單鏈表，輸出這些數(shù)據(jù)。下面給出了鏈表結(jié)點定義，各個函數(shù)的原型，及調(diào)用函數(shù)的main函數(shù)。同學(xué)們需要完成initList函數(shù)的定義，和下面的所有代碼一起提交。#include#includetypedefstructNode{intvalue;structNode*next;}Node;//初始化鏈表，同時讀取并添加所有輸入的整數(shù)Node*initList(intN){//這里的代碼需要您完成returnhead;}//遍歷并打印鏈表內(nèi)容voidprintList(Node*head){Node*current=head;while(current!=NULL){printf("%d",current->value);current=current->next;}printf("\n");}intmain(){intN;scanf("%d",&N);//初始化鏈表并讀取輸入數(shù)據(jù)Node*head=initList(N);//打印鏈表printList(head);//釋放鏈表內(nèi)存Node*current=head;while(current!=NULL){Node*next=current->next;free(current);current=next;}return0;}輸入格式：第一行輸入1個整數(shù)N第二行輸入N個空格分隔的整數(shù)輸出格式：輸出這N個整數(shù)，每個整數(shù)之間用空格隔開（包括最后1個整數(shù)），然后輸出回車符號。輸入樣例：3123輸出樣例：123線性表測驗1.單選題：對于包含n個元素的棧，下面哪個操作的時間復(fù)雜度是O(1)？

選項：

A、入棧操作（插入）

B、出棧操作（刪除）

C、遍歷棧內(nèi)所有元素

D、查找指定元素的位置

E、出棧關(guān)鍵字最大的數(shù)據(jù)

答案：【入棧操作（插入）】2.單選題：隊列中插入和刪除操作所涉及的時間復(fù)雜度分別是：

選項：

A、插入O(n),刪除O(1)

B、插入O(1),刪除O(n)

C、插入O(1),刪除O(1)

D、插入O(n),刪除O(n)

答案：【插入O(1),刪除O(1)】3.單選題：下面哪個不是隊列的特點？

選項：

A、先進(jìn)后出

B、后進(jìn)先出

C、插入的元素只能在隊尾進(jìn)行

D、刪除的元素只能在隊頭進(jìn)行

E、先進(jìn)先出

答案：【先進(jìn)后出】4.單選題：關(guān)鍵字越大，優(yōu)先級越高。為了更好的為優(yōu)先級高的顧客服務(wù)，銀行應(yīng)該采用什么存儲結(jié)構(gòu)支撐算法？

選項：

A、順序存儲結(jié)構(gòu)

B、鏈?zhǔn)酱鎯Y(jié)構(gòu)

C、有序數(shù)組

D、有序鏈表

答案：【有序鏈表】5.單選題：已知有一系列輸入數(shù)據(jù)為32,14,78,2,62,5,需要得到5,2,2,7,4,2，請問用什么數(shù)據(jù)結(jié)構(gòu)支撐算法？

選項：

A、用棧將數(shù)據(jù)全部入棧，再出棧，出棧的數(shù)據(jù)取個位，就得到需要的輸出序列。

B、用隊列將數(shù)據(jù)全部入隊，再全部出隊，出隊的時候取該數(shù)據(jù)的個位，就得到需要的輸出序列。

C、用一個整數(shù)變量空間，把輸入的數(shù)據(jù)依次存儲，存儲之后取個位，輸出個位，再讀入下一個數(shù)據(jù)。這樣的空間利用率最高。

D、用數(shù)組存儲輸入的數(shù)據(jù)，再逆向輸出所有數(shù)據(jù)。

答案：【用棧將數(shù)據(jù)全部入棧，再出棧，出棧的數(shù)據(jù)取個位，就得到需要的輸出序列?！?.單選題：當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時，可用折半查找，也可用順序查找，但前者比后者的查找速度()

選項：

A、一定快

B、不一定快

C、大部分情況下快

D、取決于表遞增還是遞減

答案：【大部分情況下快】7.單選題：雙向鏈表中有2個指針域pre和next，分別指向直接前驅(qū)和直接后繼，假設(shè)有指針p指向鏈表中的一個結(jié)點，指針q指向一個待插入的結(jié)點，現(xiàn)在要求在p的前面插入q所指結(jié)點，則正確的插入語句為（）

選項：

A、p->pre=q;q->next=p;p->pre->next=q;q->pre=p->pre;

B、q->pre=p->pre;p->pre->next=q;q->next=p;p->pre=q->next;

C、q->next=p;p->next=q;p->pre->next=q;q->next=p;

D、p->pre->next=q;q->next=p;q->pre=p->pre;p->pre=q;

答案：【p->pre->next=q;q->next=p;q->pre=p->pre;p->pre=q;】8.單選題：下面程序段的輸出結(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);

選項：

A、hrcha

B、rchah

C、rcha

D、char

答案：【char】9.單選題：已知不帶頭結(jié)點的單鏈表L，下面用函數(shù)實現(xiàn)的在第一個元素前面插入值為x的元素結(jié)點的算法錯誤的是（）

選項：

A、voidinsert(List*L,elemtypex){noded=newnode(x);d.next=*L;*L=&d;}

B、List*insert(List*L,elemtypex){noded=newnode(x);d.next=*L;*L=&d;returnL;}

C、voidinsert(List*L,elemtypex){ptrp=*L;noded=newnode(x);ptrq=&d;p->next=q;L=&q;}

D、Listinsert(List*L,elemtypex){noded=newnode(x);d.next=*L;return&d;}

答案：【voidinsert(List*L,elemtypex){ptrp=*L;noded=newnode(x);ptrq=&d;p->next=q;L=&q;}】10.單選題：已知數(shù)據(jù)3,4,-2,0,8存儲在順序存儲結(jié)構(gòu)中，編程實現(xiàn)刪除x的操作為（）提示：數(shù)據(jù)從順序存儲結(jié)構(gòu)的第0個位置開始存儲

選項：

A、voiddel(SqListL,elemtypex){inti=0;while(i＜br>B、voiddel(SqListL,elemtypex){inti=0;while(i＜br>C、voiddel(SqListL,elemtypex){inti=L.length;while(i>0){if(x!=L.data[i])L.data[i-1]=L.data[i];i--;}}

D、voiddel(SqListL,elemtypex){inti=0,bfind=0;while(i＜br>E、voiddel(SqListL,elemtypex){inti=0;while(ii++;}elsebreak;}while(i＜p=""＞＜＞{L.data[i]=L.data[i+1];i++;}L.length--;}

答案：【voiddel(SqListL,elemtypex){inti=0;while(ii++;}elsebreak;}while(i＜p=""＞＜＞{L.data[i]=L.data[i+1];i++;}L.length--;}】11.單選題：設(shè)順序表L是一個非遞減的有序表，下面的哪個算法，能夠?qū)⒃豿插入L中，并使L仍然有序。

選項：

A、//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=1;while(i＜=L->length){if(x>L->data[i])i++;elseL->data[i]=x;}}

B、//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=L->length-1;while(i＞=0){if(xdata[i]){L->data[i+1]=L->data[i];--i;}}L->data[i]=x；L->length+=1;}

C、//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=1;while(i＜=L->length){if(x>L->data[i]){L->data[i+1]=L->data[i];i++;}else{L->data[i]=x;break;}}}

D、//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=L->length;while(i＞=1){if(xdata[i]){L->data[i+1]=L->data[i];--i;}L->data[i]=x;}}

答案：【//L是順序存儲結(jié)構(gòu)voidinsert(list*L,elemtypex){inti=L->length-1;while(i＞=0){if(xdata[i]){L->data[i+1]=L->data[i];--i;}}L->data[i]=x；L->length+=1;}】12.單選題：當(dāng)對一個線性表經(jīng)常進(jìn)行存取而很少進(jìn)行插入及刪除操作時，采用（）存儲結(jié)構(gòu)最節(jié)省時間；如果經(jīng)常進(jìn)行插入，刪除操作時，則采用（）存儲結(jié)構(gòu)最節(jié)省時間。

選項：

A、順序，順序

B、順序，鏈?zhǔn)?/p>

C、鏈?zhǔn)?，鏈?zhǔn)?/p>

D、鏈?zhǔn)?，順?/p>

答案：【順序，鏈?zhǔn)健?3.單選題：一個棧的入棧序列是a,b,c,d,e,則不可能的出棧輸出序列是（）

選項：

A、edcba

B、decba

C、dceab

D、abcde

答案：【dceab】14.單選題：假設(shè)按照行優(yōu)先存儲整數(shù)數(shù)組A[9][8]，第一個元素a11的首字節(jié)地址是100，每個整數(shù)占4個字節(jié)，則元素a32的存儲地址是（）提示：數(shù)組大小是9行8列，第一個位置是1，不是0

選項：

A、164

B、168

C、144

D、172

答案：【168】15.單選題：在一個具有n個鏈結(jié)點的線性鏈表中，按數(shù)據(jù)內(nèi)容查找某一個結(jié)點，如果查找成功，需要平均比較（）個結(jié)點。

選項：

A、n＜br>B、n/2

C、(n+1)/2

D、(n-1)/2

答案：【(n+1)/2】第二章2.2查找查找測驗1.單選題：長度為n的有序順序表采用折半查找，查找成功的最少次數(shù)為（），查找成功的最大次數(shù)為（），查找失敗的最大次數(shù)為（），所以折半查找的最壞時間復(fù)雜度為（）

選項：

A、1,logn,logn,O(logn)

B、1,n,n,O(n)

C、1,n,logn,O(logn)

D、1,logn,n,O(n)

答案：【1,logn,logn,O(logn)】2.單選題：已知在長度為n的線性表中采用順序查找，查找成功最好的比較次數(shù)是（），查找成功的最壞比較次數(shù)是（），查找失敗的比較次數(shù)是（）

選項：

A、1，n,n＜br>B、0，n,n+1

C、1,n,n+1

D、1,n+1,n+1

答案：【1，n,n】3.單選題：哈希函數(shù)H(k)=k%17,采用開放地址法的線性探測再散列解決沖突，輸入關(guān)鍵字（9,31,26,19,1,13,2,11,27,16,21)，表長為20，查找10在哈希表當(dāng)中和關(guān)鍵字的的比較次數(shù)是（），再次比較發(fā)現(xiàn)當(dāng)前位置是空，確定查找失敗，關(guān)鍵字10不在哈希表當(dāng)中。

選項：

A、6

B、5

C、7

D、4

答案：【5】4.單選題：哈希函數(shù)的作用是什么？

選項：

A、將輸入數(shù)據(jù)壓縮成固定長度的哈希值

B、對輸入數(shù)據(jù)進(jìn)行加密

C、對輸入數(shù)據(jù)進(jìn)行排序

D、轉(zhuǎn)換輸入數(shù)據(jù)的類型

E、將關(guān)鍵字和存儲地址建立映射關(guān)系，方便通過關(guān)鍵字快速查找到數(shù)據(jù)

答案：【將輸入數(shù)據(jù)壓縮成固定長度的哈希值】5.單選題：下面哪個選項不是好的哈希函數(shù)的特點？

選項：

A、均勻分布

B、低沖突率

C、高碰撞率

D、高效計算

E、高沖突率

F、哈希函數(shù)的復(fù)雜度足夠高，計算量比較大

答案：【高碰撞率】6.單選題：哈希函數(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(成功）=（）

選項：

A、地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121112ASL(成功）=15/11

B、地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121122ASL（成功）=15/11?

C、地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121122ASL(成功)=15/12?

D、地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121112ASL(成功)=15/12

答案：【地址0123456789101112關(guān)鍵字1111322627161993121查找次數(shù)11121121122ASL（成功）=15/11?】7.單選題：查找表32,45,18,77,5,23,44,19,7,3,哈希函數(shù)為H(key)=key%5,采用鏈地址法解決沖突的ASL(成功）=（），采用表長為11的線性探測再散列開放地址法的ASL(成功）=（），

選項：

A、18/10，32/10

B、18/5，31/10

C、18/10，31/10

D、18/5，32/10

答案：【18/10，32/10】8.單選題：查找表如下分組(3,7,1,8,15),(22,43,18,45),(60,58,82,77,62),(90,88,99,100)，則索引表為（）,查找58需要比較（）次

選項：

A、(22,1),(60,6),(88,10),(101,15)7

B、(15,1),(45,6),(82,10),(100,15),(NULL,19)5?

C、(15,1),(45,6),(82,10),(100,15)5

D、(15,1),(45,6),(82,10),(100,15)7

答案：【(15,1),(45,6),(82,10),(100,15),(NULL,19)5?】查找編程題1.建立哈希表

題目內(nèi)容：給定一系列整型關(guān)鍵字和素數(shù)p，用除留取余法定義的散列函數(shù)H(key)=key%p將關(guān)鍵字映射到長度為p的散列表中。用線性探測法解決沖突。輸入格式：輸入第1行首先給出兩個正整數(shù)n（n＜=1000）和p（＞=n的最小素數(shù)），分別為待插入的關(guān)鍵字總數(shù)、以及散列表的長度。第2行給出n個整型關(guān)鍵字。數(shù)字間以空格分隔。輸出格式：在一行內(nèi)輸出每個整型關(guān)鍵字在散列表中的位置。數(shù)字間以空格分隔，但行末尾不得有多余空格。輸入樣例：4524156188輸出樣例：4013第二章2.3排序排序測驗1.單選題：已知輸入數(shù)據(jù)1，2，8，5，9，11，34，56，51，77，請分析數(shù)據(jù)，采用（）排序算法效率最低

選項：

A、冒泡排序

B、簡單插入排序

C、選擇排序

D、三者取中法作為樞紐的快速排序

答案：【選擇排序】2.單選題：已知輸入數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，增量序列d=5,3,1,請采用希爾排序算法進(jìn)行排序，2趟排序后的結(jié)果為（）

選項：

A、1，7，5，2，8，9，24，11，34，51，13，77，56

B、1，7，8，9，13，24，11，34，51，2，5，56，77

C、2，11，5，1，8，9，24，7，34，51，13，77，56

D、2，5，11，1，8，9，7，24，34，13，51，77，56

答案：【1，7，5，2，8，9，24，11，34，51，13，77，56】3.單選題：已知輸入數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，請采用快速歸排序算法進(jìn)行排序，其中樞紐采用3者取中法，2趟排序后的結(jié)果為（）注意：答案中的括號表示快排中的分組

選項：

A、（（2，5，1），（7，8），9）），11，（（13，34，24），51，（77，56））

B、（（1，2），5，（7，8，9，11）），13，（（24），34，（56，77，51））

C、（（1，2），5，（13，8，9，7）），11，（（24），34，（51，77，56））

D、（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））

答案：【（（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，請采用2路歸并遞歸排序算法進(jìn)行排序，2趟排序后的結(jié)果為（）

選項：

A、13，7，24，1，8，9，11，56，34，51，2，5，77

B、1，7，13，24，8，9，11，34，51，56，2，5，77

C、7，13，24，1，8，9，11，34，51，56，2，5，77

D、13，24，1，7，8，9，11，34，56，51，2，77，5

答案：【1，7，13，24，8，9，11，34，51，56，2，5，77】5.單選題：請對下列數(shù)據(jù)13，24，7，1，8，9，11，56，34，51，2，77，5，進(jìn)行簡單插入排序，冒泡排序（每趟大數(shù)冒到后面）和選擇排序，2趟后的排序結(jié)果為：（）

選項：

A、2趟后的簡單插入排序序列為：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序為：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的選擇排序為：1，2，7，13，8，9，11，56，34，51，24，77，5

B、2趟后的簡單插入排序序列為：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序為：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的選擇排序為：1，2，5，7，13，8，9，11，56，34，51，24，77

C、2趟后的簡單插入排序序列為：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序為：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的選擇排序為：1，2，7，13，8，9，11，56，34，51，24，77，5

D、2趟后的簡單插入排序序列為：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序為：1，7，8，9，11，13，24，34，2，5，51，56，772趟后的選擇排序為：1，2，7，13，8，9，11，56，34，51，24，77，5

答案：【2趟后的簡單插入排序序列為：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序為：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的選擇排序為：1，2，7，13，8，9，11，56，34，51，24，77，5】6.單選題：快速排序是一種基于比較的排序算法，其特點是

選項：

A、通過不斷地交換元素來實現(xiàn)排序

B、時間復(fù)雜度始終為O(n^2)

C、不需要額外的空間復(fù)雜度

D、適用于已經(jīng)排序好的數(shù)組

E、快速排序最好的時間復(fù)雜度是O(nlogn),最壞的時間復(fù)雜度是O(n^2)

F、快速排序的空間復(fù)雜度是O(n)

答案：【通過不斷地交換元素來實現(xiàn)排序】7.單選題：歸并排序的特點是

選項：

A、只適用于有序數(shù)組

B、時間復(fù)雜度始終為O(n^2)

C、具有穩(wěn)定性

D、通過不斷合并子數(shù)組來實現(xiàn)排序

E、歸并排序可以采用迭代法，也可以采用遞歸方法。

F、歸并排序可以做多路歸并，且常用于外部排序

答案：【通過不斷合并子數(shù)組來實現(xiàn)排序】8.單選題：希爾排序是一種基于插入排序的排序算法，其特點是：

選項：

A、只適用于小規(guī)模數(shù)據(jù)

B、時間復(fù)雜度始終為O(n^2)

C、具有穩(wěn)定性

D、通過定義增量序列來優(yōu)化插入排序

E、通過分組優(yōu)化插入排序的改進(jìn)算法

F、增量序列可以是任意值，但最好是遞減的質(zhì)數(shù)序列

G、增量序列最后1個值必須是1

答案：【通過定義增量序列來優(yōu)化插入排序】9.單選題：下面哪個排序算法具有穩(wěn)定性？

選項：

A、快速排序

B、插入排序

C、希爾排序

D、選擇排序

E、冒泡排序

答案：【插入排序】10.單選題：下列哪種排序算法具有最壞情況時間復(fù)雜度為O(nlogn)

選項：

A、快速排序

B、冒泡排序

C、歸并排序

D、選擇排序

E、簡單插入排序

F、基數(shù)排序

答案：【歸并排序】排序編程題1.實現(xiàn)快速排序

題目內(nèi)容：快速排序是一種高效的排序算法，它的基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分的所有記錄都比另一部分的所有記錄都要小，然后再按此方法對這兩部分記錄分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。本題要求實現(xiàn)快速排序算法中的分區(qū)步驟。給定一個數(shù)組和一個索引范圍[left,right]，你需要選擇數(shù)組中l(wèi)eft位置的元素作為基準(zhǔn)值(pivot)，然后重新排列數(shù)組，使得所有小于基準(zhǔn)值的元素都出現(xiàn)在基準(zhǔn)值前面，所有大于或等于基準(zhǔn)值的元素都出現(xiàn)在基準(zhǔn)值后面。完成這個操作后，返回基準(zhǔn)值最終的位置。你需要輸出經(jīng)過一次分區(qū)操作后數(shù)組的狀態(tài)。分區(qū)操作的原型函數(shù)如下：intpartition(intarr[],intleft,intright);輸入格式：第一行包含空格分隔的3個整數(shù)：整數(shù)N，表示數(shù)組的長度；整數(shù)left表示索引起始位置；整數(shù)right表示索引結(jié)束位置。第二行包含N個由空格分隔的整數(shù)，代表待排序的數(shù)組。輸出格式：輸出一行整數(shù)，包含N個由空格分隔的整數(shù)（最后1個數(shù)后沒有空格或者回車等任何其他符號），表示經(jīng)過一次分區(qū)操作后的數(shù)組。輸入樣例：605654321輸出樣例：154326過程說明：采用與樞紐交換的方式進(jìn)行分區(qū)操作。先選擇樞紐pivot為a[left]，即6。開始分區(qū)操作，由于a[pivot]>a[right]（即6>1），將pivot（6）與right指向的元素（1）交換，數(shù)組變?yōu)?54326。然后left指針加1，此時a[left]（即5）小于pivot（即6），left繼續(xù)向右移動，直到left等于pivot的原始位置或找到不小于pivot的元素為止。在這個過程中，數(shù)組經(jīng)過一次分區(qū)操作后變?yōu)檩敵鰳永?。說明：如果出現(xiàn)重復(fù)數(shù)據(jù)，待交換數(shù)據(jù)和樞紐值相同，則不發(fā)生交換。函數(shù)partition的參數(shù)不合法，則函數(shù)返回-1,否則返回0。第三章遞歸與分治遞歸與分治編程題1.分治法快速計算大整數(shù)乘法

題目內(nèi)容：Karatsuba算法是一種快速乘法算法。這個算法用于高效地計算兩個大整數(shù)的乘積，以下是Karatsuba算法的基本步驟：如果要相乘的兩個數(shù)中的任何一個數(shù)小于某個閾值（比如10），那么算法直接使用傳統(tǒng)的乘法運(yùn)算。這是遞歸的終止條件。（1）對于兩個n位的整數(shù)x和y，首先將它們劃分為兩部分，每部分有n/2位：x=a*(10^(n/2))+by=c*(10^(n/2))+d，則x*y=ac*10^n+(bc+ad)*10^(n/2)+bd（2）遞歸計算以下三項：z0=b*dz2=a*cz1=(a+b)*(c+d)-z2-z0（3）將這些項組合以獲得最終的乘積,result=z2*(10^n)+z1*(10^(n/2))+z0請實現(xiàn)這個算法。輸入格式：輸入兩個用空格隔開的整數(shù)A和B，分別代表兩個乘數(shù)。輸出格式：輸出A×B的結(jié)果輸入樣例：123456789987654321輸出樣例：121932631112635269遞歸與分治測驗1.單選題：下面（）說法是正確的

選項：

A、所有問題都可以寫遞歸程序

B、大部分遞歸程序可以轉(zhuǎn)換為非遞歸程序，非遞歸程序運(yùn)行速度更快。

C、所有遞歸程序都可以轉(zhuǎn)換為非遞歸程序，且遞歸程序運(yùn)行速度更快

D、遞歸程序可以把遞歸出口寫在遞歸關(guān)系的后面

E、尾遞歸可以轉(zhuǎn)換為循環(huán)

答案：【大部分遞歸程序可以轉(zhuǎn)換為非遞歸程序，非遞歸程序運(yùn)行速度更快?！?.單選題：求一個數(shù)據(jù)序列的逆序數(shù)量不可以通過______排序中增加1個計數(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。

選項：

A、歸并

B、簡單插入

C、冒泡

D、堆排序

E、樹形選擇排序

答案：【堆排序】3.單選題：分治法所能解決的問題一般具有以下幾個特征:1.該問題的規(guī)?？s小到一定的程度就可以容易地解決；2.____________3.利用該問題分解出的子問題的解可以合并為該問題的解；4.該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。

選項：

A、最佳答案

B、最優(yōu)解

C、最優(yōu)子結(jié)構(gòu)

D、最優(yōu)值

E、最優(yōu)方法

答案：【最優(yōu)子結(jié)構(gòu)】4.單選題：已知某遞歸算法的復(fù)雜度為：T(n)=2T(n/2)+4,則求解該遞歸式的解為：（）

選項：

A、T(n)=O(1)

B、T(n)=O(n)

C、T(n)=O(n^2)

D、T(n)=O(nlogn)

答案：【T(n)=O(n)】5.單選題：采用分治遞歸方法求解下面問題：給定一個整數(shù)數(shù)組，找到其中的最大元素。請寫出分治遞歸關(guān)系

選項：

A、分治遞歸關(guān)系：fun(a,low,high)=max(fun(a,low,(low+high)/2),fun(a,(low+high)/2+1,high)(low＜p=""＞＜＞遞歸出口：fun(a,low,high)=a[low](low==high)

B、分治遞歸關(guān)系：fun(a,low,high)=max(a[low],fun(a,low+1,high)(low＜p=""＞＜＞遞歸出口：fun(a,low,high)=a[low](low==high)

C、分治遞歸關(guān)系：fun(a,low,high)=max(a[high],fun(a,low,high-1)(low＜p=""＞＜＞遞歸出口：fun(a,low,high)=a[low](low==high)

D、分治遞歸關(guān)系：fun(a,low,high)=a[high]+fun(a,low,high-1)(low＜p=""＞＜＞遞歸出口：fun(a,low,high)=a[low](low==high)

答案：【分治遞歸關(guān)系：fun(a,low,high)=max(fun(a,low,(low+high)/2),fun(a,(low+high)/2+1,high)(low＜p=""＞＜＞遞歸出口：fun(a,low,high)=a[low](low==high)】6.單選題：分治算法的基本思想是

選項：

A、將問題劃分為多個子問題，并對每個子問題進(jìn)行獨(dú)立求解

B、使用動態(tài)規(guī)劃方法求解子問題

C、直接使用循環(huán)迭代求解問題

D、將問題劃分為兩個子問題，然后合并子問題的解

E、分治遞歸的子問題是獨(dú)立的，采用遞歸或者迭代方法都能夠進(jìn)行問題求解，且效率相同。但通常迭代法的實際執(zhí)行時間少于遞歸方法。

答案：【將問題劃分為多個子問題，并對每個子問題進(jìn)行獨(dú)立求解】7.單選題：遞歸算法的特點是

選項：

A、需要使用棧來保存函數(shù)調(diào)用的上下文信息

B、可以有效地處理大規(guī)模問題

C、不會引起函數(shù)調(diào)用的額外開銷

D、必須存在終止條件來結(jié)束遞歸過程

E、通常用遞歸函數(shù)實現(xiàn)遞歸算法。遞歸函數(shù)必須有終止條件，否則函數(shù)調(diào)用會出現(xiàn)內(nèi)存不夠，程序運(yùn)行崩潰的問題。

F、遞歸函數(shù)都可以轉(zhuǎn)換為非遞歸函數(shù)，且一定要借助棧才能夠轉(zhuǎn)換。

答案：【需要使用棧來保存函數(shù)調(diào)用的上下文信息】8.單選題：已知求一組數(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(sum＞left_sum){left_sum=sum;max_left=i;}}sum=0;//frommidtorightfor(intj=mid+1;j＜=high;j++){sum+=arr[j];if(sum＞right_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);——————————完成這里的代碼——————————————————}}

選項：

A、inttmp=(leftSum＞rightSum?leftSum:rightSum;return(tmp＞crossSum?tmp:crossSum);

B、if(leftSum＞rightSum){if(leftSum＞crossSum)returnleftSum;}else{if(rightSum＞crossSum)returnrightSum;}

C、if(leftSum＞rightSum＞crossSum）returnleftSum;if(rightSum＞leftSum＞crossSum)returnrightSum;if(crossSum＞leftSum＞rightSum)returncrossSum;

D、if(leftSum＞rightSum&&leftSum＞crossSum）returnleftSum;if(rightSum＞leftSum&&rightSum＞crossSum)returnrightSum;if(crossSum＞leftSum&&crossSum＞rightSum)returncrossSum;

答案：【inttmp=(leftSum＞rightSum?leftSum:rightSum;return(tmp＞crossSum?tmp:crossSum);】9.大部分遞歸程序可以轉(zhuǎn)換為非遞歸程序，____程序運(yùn)行速度更快。

答案：【非遞歸】第四章樹與二叉樹（本章內(nèi)容需要2周學(xué)習(xí)時間）樹與二叉樹測驗1.單選題：給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)是()

選項：

A、不確定

B、2n＜br>C、2n+1

D、2n-1

答案：【2n-1】2.單選題：二叉排序樹的()結(jié)果是一個關(guān)鍵字的遞增有序序列

選項：

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層序遍歷

答案：【中序遍歷】3.單選題：在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序()

選項：

A、都不相同

B、完全相同

C、先序和中序相同，而與后序不同

D、中序和后序相同，而與先序不同

答案：【完全相同】4.單選題：下列四個序列中，哪一個是堆()

選項：

A、75,65,30,15,25,45,20,10

B、75,65,45,10,30,25,20,15

C、75,45,65,30,15,25,20,10

D、75,45,65,10,25,30,20,15

答案：【75,45,65,30,15,25,20,10】5.單選題：二叉樹的先序序列是EFHIGJK，中序序列為HFIEJKG，該二叉樹右子樹的根是()

選項：

A、E

B、F

C、G

D、H

答案：【G】6.單選題：一棵完全二叉樹上有1001個結(jié)點，其葉子結(jié)點的個數(shù)是()

選項：

A、250

B、500

C、254

D、501

答案：【501】7.單選題：已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序樹的查找成功的平均查找長度ASL為()注意：結(jié)果用最簡分?jǐn)?shù)形式

選項：

A、6

B、39/11

C、39/10

D、40/6

答案：【39/11】8.單選題：二叉樹的先序和中序遍歷序列相同，則此二叉樹為（）

選項：

A、任一結(jié)點無左子樹

B、任一結(jié)點無右子樹

C、根結(jié)點無左子樹

D、根結(jié)點無右子樹

答案：【任一結(jié)點無左子樹】9.單選題：假設(shè)完全二叉樹的樹根為第1層，樹中第10層有5個葉子結(jié)點，則完全二叉樹最多有（）個結(jié)點。

選項：

A、2047

B、2048

C、2038

D、2037

答案：【2037】10.單選題：如果一顆二叉樹具有10個度為2的結(jié)點和5個度為1的結(jié)點，則有（）個葉子結(jié)點

選項：

A、9

B、11

C、14

D、15

答案：【11】11.單選題：已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的二叉排序樹，刪除關(guān)鍵字36的結(jié)點的最佳操作是（）

選項：

A、直接刪除關(guān)鍵字結(jié)點36

B、用左子樹的最大關(guān)鍵字結(jié)點36替換給關(guān)鍵字為36的結(jié)點

C、用右子樹的最小關(guān)鍵字40替換關(guān)鍵字結(jié)點36

D、直接用不含有關(guān)鍵字36的輸入序列重新構(gòu)造新的二叉排序樹

答案：【用右子樹的最小關(guān)鍵字40替換關(guān)鍵字結(jié)點36】12.單選題：3個不同的結(jié)點，可以構(gòu)成（）顆不同的二叉樹

選項：

A、1

B、4

C、5

D、7

答案：【5】13.單選題：已知由一組字符組成的字符串，其中各個字符的訪問次數(shù)分別為17,28,36,54,30,27,94,15,21,83,40，請對該字符串中的字符進(jìn)行最優(yōu)編碼，其最優(yōu)編碼的帶權(quán)路徑長度為（）

選項：

A、1433

B、445

C、1479

D、1447

答案：【1447】14.單選題：已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40構(gòu)造小頂堆，按照層序輸出的關(guān)鍵字序列為：（）注意：用空格分隔輸出序列

選項：

A、1715272130369454288340

B、1517212728303640548394

C、1517272130369454288340

D、1517272830369454218340

答案：【1517272130369454288340】15.單選題：已知由關(guān)鍵字序列17,28,36,54,30,27,94,15,21,83,40得到的平衡二叉樹AVL的查找成功的平均查找長度ASL為()注意：結(jié)果用最簡分?jǐn)?shù)形式

選項：

A、34/11

B、30/11

C、3

D、30/4

答案：【3】數(shù)與二叉樹編程題1.采用插入操作實現(xiàn)二叉查找樹

題目內(nèi)容：實現(xiàn)一個二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)，支持插入和查詢操作。二叉搜索樹是一種特殊的二叉樹，其中任意節(jié)點的值大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。當(dāng)插入重復(fù)值時，不需要在樹中再次插入。輸入格式：輸入包含多行，每行一個操作指令，格式為：insertx：表示插入一個值為x的節(jié)點到二叉搜索樹中。queryx：表示查詢值為x的節(jié)點是否存在。輸入以end結(jié)束，end不作為一個操作指令。輸出格式：對于每一個insert操作，輸出執(zhí)行插入操作后的二叉樹的先序遍歷結(jié)果，結(jié)點間用空格隔開。對于每一個query操作，輸出一行，如果樹中存在值為x的節(jié)點，則輸出true，否則輸出false。輸入樣例：insert5insert3insert7query4insert4query4insert2query2end輸出樣例：553537false5347true53247true2.根據(jù)先序和中序遍歷結(jié)果建立二叉樹

題目內(nèi)容：通過先序和中序遍歷，我們可以確定樹的結(jié)構(gòu)。先序遍歷的第一個元素總是根節(jié)點，而在中序遍歷中，根節(jié)點左邊的所有元素屬于左子樹，右邊的屬于右子樹。有了這些信息，我們可以遞歸地構(gòu)建樹并得到后序遍歷序列。樹的結(jié)點定義如下：typedefstructTreeNode{intval;structTreeNode*left;structTreeNode*right;}*BiTree;給定一棵二叉樹的先序遍歷和中序遍歷序列，要求編寫一個程序，根據(jù)這兩個序列構(gòu)造二叉樹，并輸出這棵樹的后序遍歷序列。輸入格式：輸入包含三行：第一行是一個整數(shù)n，表示樹的節(jié)點總數(shù)。第二行是一個包含n個空格分隔的整數(shù)的列表，表示先序遍歷的結(jié)果，整數(shù)代表結(jié)點的編號。第三行也是一個包含n個空格分隔的整數(shù)的列表，表示中序遍歷的結(jié)果。輸出格式：輸出一行，包含一個空格分隔的整數(shù)列表（最后一個數(shù)據(jù)后面沒有空格和回車），表示后序遍歷的結(jié)果。輸入樣例：712453674251637輸出樣例：4526731第五章圖論與貪心算法（本章內(nèi)容需要2周學(xué)習(xí)時間）貪心算法與圖論測驗1.單選題：用kruscal算法，按順序輸出最小生成樹的各邊（）

選項：

A、（5，6）（4，5）（2，4）（1，2）（2，3）

B、（1，2）（2，4）（4，5）（5，6）（2，3）

C、（5，6）（4，5）（1，2）（2，3）（3，6）

D、（5，6）（4，5）（2，5）（1，2）（2，3）

E、（5，6）（4，5）（2，4）（1，2）（2，3）

F、（5，6）（4，5）（2，4）（1，2）（6，3）

答案：【（5，6）（4，5）（2，4）（1，2）（2，3）】2.單選題：從頂點1開始，用prim算法按次序輸出最小生成樹的邊()

選項：

A、（1，2）（2，3）（3，6）（6，5）（5，4）

B、（1，2）（2，4）（4，5）（5，6）（6，3）

C、（1，2）（2，3）（2，4）（4，5）（5，6）

D、（5，6）（4，5）（2，4）（1，2）（2，3）

E、（1，2）（2，4）（4，5）（5，6）（2，3）

答案：【（1，2）（2，4）（4，5）（5，6）（6，3）】3.單選題：要連通具有n個頂點的無向圖，至少需要（）條邊

選項：

A、n-1

B、n＜br>C、n+1

D、n*(n-1)

答案：【n-1】4.單選題：下圖不是合法的拓?fù)渑判蛴校ǎ?/p>

選項：

A、ACDBEF

B、ADCBEF

C、ABDCEF

D、ABDECF

答案：【ACDBEF】5.單選題：最小生成樹除了prim和kuscal算法，還有沒有其他的算法？

選項：

A、沒有了

B、還有破圈法，就是把圖里面的包含圈的最大邊刪除，直到?jīng)]有圈存在。這個算法效率比上面兩個算法更好。

C、還有其他算法，包括破圈法在內(nèi)的其他最小生成樹算法，效率沒有比prim或者kruscal算法更好。

D、還有其他算法，有的算法比prim算法好，有的算法比kuscal算法好。

E、還有其他算法，包括破圈法在內(nèi)的其他最小生成樹算法，效率沒有比prim或者kruscal算法更好。prim算法適合稠密圖，kurscal算法適合稀疏圖。

答案：【還有其他算法，包括破圈法在內(nèi)的其他最小生成樹算法，效率沒有比prim或者kruscal算法更好?！?.單選題：汽車加油問題問題描述：一輛汽車加滿油可以行駛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下面說法不正確的是（）

選項：

A、采用貪心算法，每一個加油站都去加油，使得油箱出發(fā)的時候都是滿的，即使加油站隔的很遠(yuǎn)，比如大于n公里，也能夠開到下一個加油站。

B、采用排除法，只要剩余的油不足以行駛到下一個加油站，說明繼續(xù)行駛做不到，不能把本加油站排除了，因此需要加油

C、采用貪心算法：最遠(yuǎn)距離優(yōu)先。也就是滿足汽車有油的情況下行駛盡可能遠(yuǎn)的距離。首先保證每2個加油站之間的距離＜=n，否則汽車沒有到下一個加油站就沒有油了，不能完成旅游。然后計算汽車從出發(fā)地開始的行駛的累計路程，只要累計路程小于n，則繼續(xù)開到下一個加油站，一旦行駛里程>n，則在上1個加油站必須加滿油，并加油次數(shù)加1次。然后以上一個加油站為其實出發(fā)地開始用同樣的方法進(jìn)行累計路程，直到到達(dá)目的地。

D、采用窮舉法，把每一種加油方法都枚舉出來，看是否能夠行駛到下一個加油站，不能則排除，否則就是一個可行解。

答案：【采用貪心算法，每一個加油站都去加油，使得油箱出發(fā)的時候都是滿的，即使加油站隔的很遠(yuǎn)，比如大于n公里，也能夠開到下一個加油站?！?.單選題：求城市a到其他城市的最短距離及路線

選項：

A、a到其他城市的最短距離及路徑分別為：(1)a->b:23(2)a->c:18(3)a->c->e:30(4)a->c->e->d:36(5)a->c->f:54(6)a->c->e->g:55

B、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

C、a到其他城市的最短距離及路徑分別為：(1)a->b:23(2)a->c:18(3)a->b->e:32(4)a->c->e->d:36(5)a->c->f:54(6)a->c->e->g:55

D、a到其他城市的最短距離及路徑分別為：(1)a->b:23(2)a->c:18(3)a->b->e:32(4)a->c->e->d:36(5)a->c->e->f:39(6)a->c->e->g:55

答案：【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.單選題：某一工程作業(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ù)

選項：

A、（1）關(guān)鍵路徑上的事件為：0-1-5-6-9-11（2）18天

B、（1）關(guān)鍵路徑上的事件為：0-2-6-9-11（2）20天

C、（1）關(guān)鍵路徑上的事件為：0-2-7-9-11（2）18天

D、（1）關(guān)鍵路徑上的事件為：0-2-7-10-11（2）16天

答案：【（1）關(guān)鍵路徑上的事件為：0-2-6-9-11（2）20天】9.單選題：程序存儲問題問題描述：假設(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下面的選項正確的是（）

選項：

A、將程序按照在磁帶上的存儲長度非遞減排序，假設(shè)排序后，第i個程序的長度為,其中且。則采用貪心算法，將程序長度最小的程序依次存放到磁帶上，直到第k個磁帶不能存儲到磁帶，則結(jié)束。磁帶能夠存放的程序個數(shù)為k-1(k<p=""＞＜＞且

B、窮舉法，枚舉所有的存放程序到磁帶且不會空間不夠的情況，其中最大的程序數(shù)量就是答案。

C、遞歸法，將第n個程序放到磁帶和不放到磁帶，各是2種不可能同時出現(xiàn)的方法，比較這2種方法看哪一種放到磁帶的程序數(shù)量更多，就選擇哪一種放法。

D、先如果,則將所有程序都可以放入磁帶，因此能夠存放的最多程序數(shù)量為n。否則，將程序按照在磁帶上的存儲長度非遞減排序，假設(shè)排序后，第i個程序的長度為,其中且。則采用貪心算法，將程序長度最小的程序依次存放到磁帶上，直到第k個磁帶不能存儲到磁帶，則結(jié)束。磁帶能夠存放的程序個數(shù)為k-1(k<p=""＞＜＞且

答案：【先如果,則將所有程序都可以放入磁帶，因此能夠存放的最多程序數(shù)量為n。否則，將程序按照在磁帶上的存儲長度非遞減排序，假設(shè)排序后，第i個程序的長度為,其中且。則采用貪心算法，將程序長度最小的程序依次存放到磁帶上，直到第k個磁帶不能存儲到磁帶，則結(jié)束。磁帶能夠存放的程序個數(shù)為k-1(k<p=""＞＜＞且】10.單選題：利用dijkstra算法計算從節(jié)點1到其他節(jié)點的最短路徑，算法執(zhí)行到下圖狀態(tài)之后，接下來應(yīng)該把哪個節(jié)點添加到探索集中？（）

選項：

A、結(jié)點5

B、結(jié)點6

C、結(jié)點7

D、結(jié)點8

答案：【結(jié)點5】貪心算法與圖論編程題1.部分背包問題

題目內(nèi)容：你是一名旅行者，計劃去探險，但是你的背包容量有限。你有一系列的物資，每種物資有一定的重量和價值。你不能攜帶超過背包最大容量的物資，但是你可以選擇帶上每種物資的一部分。你的任務(wù)是最大化你所帶物資的總價值。請你編程解決這個問題。輸入格式：輸入共三行：第一行輸入物品的種類n及背包的總承重量W第二行共n個浮點數(shù)，對應(yīng)每件物品的重量，之間用空格隔開第三行共n個浮點數(shù)，對應(yīng)每件物品的價值，之間用空格隔開輸出格式：輸出一行，包含一個實數(shù)，表示可獲得的最大價值，保留兩位小數(shù)。輸入樣例：415.02.03.05.07.04.05.010.016.0輸出樣例：31.672.判斷圖中是否存在歐拉回路

題目內(nèi)容：哥尼斯堡是位于普累格河上的一座城市，它包含兩個島嶼及連接它們的七座橋，能否走過這樣的七座橋，而且每橋只走過一次？瑞士數(shù)學(xué)家歐拉(LeonhardEuler，1707—1783)最終解決了這個問題，并由此創(chuàng)立了拓?fù)鋵W(xué)。這個問題如今可以描述為判斷歐拉回路是否存在的問題。歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且最終回到起點的一條回路?，F(xiàn)給定一個無向圖，問是否存在歐拉回路？輸入格式：輸入第1行給出兩個正整數(shù)，分別是節(jié)點數(shù)n(1＜=1000)和邊數(shù)m；隨后的m行對應(yīng)m條邊，每行給出一對正整數(shù)，分別是該條邊連通的兩個節(jié)點的編號（節(jié)點