【MOOC】《數(shù)據(jù)結(jié)構(gòu)》(東北大學(xué))中國(guó)大學(xué)慕課答案

【MOOC】《數(shù)據(jù)結(jié)構(gòu)》(東北大學(xué))中國(guó)大學(xué)慕課答案

有些題目順序不一致，下載后按鍵盤(pán)ctrl+F進(jìn)行搜索第一章緒論單元測(cè)試一1.單選題：具有相同性質(zhì)的數(shù)據(jù)元素的集合稱(chēng)為_(kāi)___________，它是數(shù)據(jù)的一個(gè)子集。

選項(xiàng)：

A、記錄

B、數(shù)據(jù)對(duì)象

C、數(shù)組

D、數(shù)據(jù)結(jié)構(gòu)

答案：【數(shù)據(jù)對(duì)象】2.單選題：利用數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)器的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，稱(chēng)之為_(kāi)__________存儲(chǔ)結(jié)構(gòu)。

選項(xiàng)：

A、物理

B、邏輯

C、順序

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

答案：【順序】3.多選題：算法具有5個(gè)重要特性，除輸入和輸出外還包括:_________，_________，_________。

選項(xiàng)：

A、有窮性

B、確定性

C、可讀性

D、可行性

答案：【有窮性;確定性;可行性】4.多選題：算法的設(shè)計(jì)要求包括達(dá)到以下目標(biāo)：正確性、_________、_________和效率與低存儲(chǔ)量需求。

選項(xiàng)：

A、反編譯性

B、可讀性

C、健壯性

D、操作性

答案：【可讀性;健壯性】5.單選題：數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，也稱(chēng)為映像。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】6.單選題：非線(xiàn)性結(jié)構(gòu)指的是圖和網(wǎng)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】7.數(shù)據(jù)的基本單位是__________。

答案：【數(shù)據(jù)元素】8.計(jì)算機(jī)中具有兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和___________存儲(chǔ)結(jié)構(gòu)。

答案：【鏈?zhǔn)健?.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的___________和操作的學(xué)科。

答案：【關(guān)系】單元作業(yè)一1.分析下面代碼段中各行的執(zhí)行次數(shù)，用大O表示算法的時(shí)間復(fù)雜度。說(shuō)明：方次可用符號(hào)^表示，如100的3次方表示為100^3。y=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;

算法時(shí)間復(fù)雜度為O(n^2)，正確得10分，否則得0分。參考：y=0;//1次for(i=1;i<=n;i++)//n+1次for(j=1;j<=n;j++)//n(n+1)次y++;//n^2全部代碼的執(zhí)行次數(shù)：1+(n+1)+n(n+1)+n^2=2n^2+2n+2因此，時(shí)間復(fù)雜度T(n)=O(n^2)第二章線(xiàn)性表單元測(cè)驗(yàn)二1.單選題：在一個(gè)線(xiàn)性表含有10個(gè)數(shù)據(jù)元素，如果在第i個(gè)位置前插入新的數(shù)據(jù)元素，那么i的取值錯(cuò)誤的是_________。

選項(xiàng)：

A、1

B、10

C、11

D、12

答案：【12】2.單選題：如果在n個(gè)結(jié)點(diǎn)的單鏈表中刪除已知結(jié)點(diǎn)s，那么需要_________。

選項(xiàng)：

A、找到s的直接后繼結(jié)點(diǎn)

B、找到s的直接前驅(qū)結(jié)點(diǎn)

C、移動(dòng)s后的所有結(jié)點(diǎn)

D、釋放s后的所有結(jié)點(diǎn)

答案：【找到s的直接前驅(qū)結(jié)點(diǎn)】3.單選題：判定帶頭結(jié)點(diǎn)的單鏈表head為空的條件是_________。

選項(xiàng)：

A、head->next==NULL

B、head==NULL

C、head->next==head

D、head!=NULL

答案：【head->next==NULL】4.單選題：在線(xiàn)性結(jié)構(gòu)中，所有的結(jié)點(diǎn)僅有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】5.單選題：線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)，即訪(fǎng)問(wèn)任一數(shù)據(jù)元素的時(shí)間相同。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】6.在鏈表的操作中，生成和釋放結(jié)點(diǎn)的標(biāo)準(zhǔn)函數(shù)是malloc和_______。

答案：【free】7.線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，每個(gè)結(jié)點(diǎn)包含兩個(gè)域，存儲(chǔ)數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域；存儲(chǔ)直接后繼存儲(chǔ)位置的域稱(chēng)為_(kāi)______域。

答案：【指針】8.在長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表中，查找一個(gè)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(__)。

答案：【n】9.一個(gè)長(zhǎng)度為1000的線(xiàn)性表，采用順序存儲(chǔ)，如果刪除第900個(gè)元素，需要向前移動(dòng)_______個(gè)元素。

答案：【100】10.一個(gè)長(zhǎng)度為1000的線(xiàn)性表，采用順序存儲(chǔ)，如果在第900個(gè)元素之前插入一個(gè)元素，需要向后移動(dòng)_______個(gè)元素。

答案：【101】單元作業(yè)二1.設(shè)指針p指向單鏈表中的某個(gè)結(jié)點(diǎn)，將要?jiǎng)h除該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，而直接后繼結(jié)點(diǎn)有可能不存在。所有語(yǔ)句如下，需要重新排列才能完成上述功能。1.q=p->next;2.free(q);3.if(p->next==NULL)returnERROR;4.returnOK;5.p->next=q->next;正確的語(yǔ)句順序應(yīng)為_(kāi)________。A.15243B.31524C.31254D.35124

答案為B得10分，否則0分。2.設(shè)存在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表L，每個(gè)結(jié)點(diǎn)包含三個(gè)域，它們分別是prior、data和next。其中data為數(shù)據(jù)域，prior是指針域，其值為空指針；next是指針域，指向直接后繼結(jié)點(diǎn)。下面的代碼將此單鏈表轉(zhuǎn)化為雙向循環(huán)鏈表。#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLNode{structLNode*prior;ElemTypedata;structLNode*next;}DuLNode,*DuLinkList;StatusCreateDuList_prior(DuLinkList&L){//Makethepriorpointtotheprecursornode.DuLinkListp,q;1;do{q=p->next;2;p=q;}while(p!=L);returnOK;}請(qǐng)?zhí)顚?xiě)空格1和2處的代碼，實(shí)現(xiàn)上述功能。

參考答案：1.p=L2.q->prior=p評(píng)分標(biāo)準(zhǔn)：每個(gè)空格5分，代碼正確得分，錯(cuò)誤不得分。第三章棧與隊(duì)列單元測(cè)試三1.單選題：設(shè)循環(huán)隊(duì)列采用一維數(shù)組A[0..20]存儲(chǔ)，隊(duì)頭指針front=15，元素個(gè)數(shù)size=5，在插入兩個(gè)新元素后，隊(duì)尾的位置是______。

選項(xiàng)：

A、0

B、1

C、2

D、22

答案：【1】2.單選題：某鏈棧的棧頂指針為top，若向該棧中插入一個(gè)p所指結(jié)點(diǎn)，則執(zhí)行______。

選項(xiàng)：

A、p->next=top;top=top->next;

B、top->next=p;

C、p->next=top->next;top->next=p;

D、p->next=top;top=p;

答案：【p->next=top;top=p;】3.多選題：一個(gè)隊(duì)列的入列序列是a、b、c、d、e，則隊(duì)列的輸出序列不可能是______。

選項(xiàng)：

A、a、b、c、d、e

B、a、c、b、d、e

C、a、b、d、c、e

D、e、d、c、b、a

答案：【a、c、b、d、e;a、b、d、c、e;e、d、c、b、a】4.多選題：一個(gè)棧的入棧序列是a、b、c、d、e，則棧的可能輸出的序列是______。

選項(xiàng)：

A、a、b、c、d、e

B、d、c、e、a、b

C、d、e、c、b、a

D、e、d、c、b、a

答案：【a、b、c、d、e;d、e、c、b、a;e、d、c、b、a】5.單選題：循環(huán)隊(duì)列解決了一般順序存儲(chǔ)隊(duì)列中出現(xiàn)的“假上溢”問(wèn)題。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】6.單選題：采用順序存儲(chǔ)結(jié)構(gòu)的棧稱(chēng)為鏈棧。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】7.單循環(huán)鏈表表示的隊(duì)列中保存了n個(gè)數(shù)據(jù)元素，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度是O(__）。

答案：【n】8.單循環(huán)鏈表表示的隊(duì)列中保存了n個(gè)數(shù)據(jù)元素，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度是O(___）。

答案：【1】[vk-content]9.在順序棧中入棧和出棧的時(shí)間復(fù)雜度都是O(___）。

答案：【1】單元作業(yè)三1.設(shè)某個(gè)循環(huán)隊(duì)列的頭指針是front，尾指針是rear，循環(huán)隊(duì)列的空間是M，請(qǐng)為下列1~5的情況選擇合適的語(yǔ)句。1.隊(duì)空的條件：。2.隊(duì)滿(mǎn)的條件：。3.隊(duì)長(zhǎng)的計(jì)算：。4.入隊(duì)時(shí)修改指針：。5.出隊(duì)時(shí)修改指針：?？晒┻x擇的語(yǔ)句：A.rear=(rear+1)%MB.(rear-front+M)%MC.(rear-front+1)%MD.front==rearE.front=(front+1)%MF.front==(rear+1)%M

參考答案：1.D2.F3.B4.A5.E評(píng)分標(biāo)準(zhǔn)：每個(gè)空2分，錯(cuò)誤不得分。2.順序棧聲明如下，編寫(xiě)一個(gè)操作（函數(shù)），返回當(dāng)前允許添加到棧中數(shù)據(jù)元素的最大個(gè)數(shù)。typedefintSElemType;typedefstructsqstack{SElemType*base;SElemType*top;intstacksize;}SqStack;

函數(shù)返回值為整型，即int或SElemType，得2分；參數(shù)為引用型，即形參前有&符號(hào)，得2分；num計(jì)算正確，即有S.stacksize-(S.top-S.base)算式，得4分；具有返回語(yǔ)句return2分。如果計(jì)算與返回為一條語(yǔ)句，正確則得6分。intgetNumOfRemain(SqStack&S){intnum=S.stacksize-(S.top-S.base);returnnum;}第四章串單元測(cè)試四1.單選題：設(shè)S="tea"，則其非空子串的數(shù)目為_(kāi)_____。

選項(xiàng)：

A、5

B、6

C、7

D、8

答案：【6】2.單選題：設(shè)S="Chinesedreammydream"，T="dream"，則index(S,T,3)的值為_(kāi)_____。

選項(xiàng)：

A、0

B、9

C、18

D、9和18

答案：【9】3.單選題：設(shè)字符串str1="Datastructures"，其中兩個(gè)單詞之間存在一個(gè)空格符，當(dāng)取子串操SubString(sub1,str1,6,6)執(zhí)行后，sub1=_______。

選項(xiàng)：

A、"Datas"

B、"Datast"

C、"struct"

D、"tructu"

答案：【"struct"】4.單選題：在串的存儲(chǔ)方式中，_______屬于鏈?zhǔn)酱鎯?chǔ)。

選項(xiàng)：

A、定長(zhǎng)順序存儲(chǔ)

B、堆分配存儲(chǔ)

C、塊鏈存儲(chǔ)

D、以上3種全部

答案：【塊鏈存儲(chǔ)】5.多選題：下面關(guān)于字符串的敘述，不正確的有_________。

選項(xiàng)：

A、字符串是不少于一個(gè)字符的序列。

B、字符串是由字母和數(shù)字組成的序列。

C、字符串是由零個(gè)或多個(gè)字符組成的有限序列。

D、字符串是任意個(gè)字母組成的序列。

答案：【字符串是不少于一個(gè)字符的序列。;字符串是由字母和數(shù)字組成的序列。;字符串是任意個(gè)字母組成的序列?！?.多選題：以下____________操作屬于串類(lèi)型的最小操作子集。

選項(xiàng)：

A、串賦值StrAssign

B、串定位Index

C、求串長(zhǎng)StrLength

D、串復(fù)制StrCopy

答案：【串賦值StrAssign;求串長(zhǎng)StrLength】7.單選題：串的堆分配存儲(chǔ)是一種順序存儲(chǔ)結(jié)構(gòu)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】8.單選題：在空串里面僅包含空格符。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】9.設(shè)字符串str=""，str的長(zhǎng)度為_(kāi)_____。

答案：【0/零】單元作業(yè)四1.回文是一個(gè)順讀和倒讀都相同的字符串，如英文單詞madam，noon等。設(shè)字符串采用堆分配存儲(chǔ)，附件中的函數(shù)Palindrome用于判斷字符串是否為回文。要求：在程序空白處補(bǔ)全代碼（標(biāo)記為1、2）。

參考答案：1.j--或--j2.TRUE評(píng)分標(biāo)準(zhǔn)：1、2處正確，各得5分。其他情況不得分。第五章數(shù)組與廣義表單元測(cè)試五1.單選題：對(duì)廣義表取表尾操作，表尾一定是___________。

選項(xiàng)：

A、原子

B、列表

C、原子或列表

D、十字鏈表

答案：【列表】2.單選題：廣義表GL=(a,(b,c,d),(e,f))的長(zhǎng)度為_(kāi)___________。

選項(xiàng)：

A、2

B、3

C、5

D、6

答案：【3】3.多選題：關(guān)于一個(gè)非空廣義表的表尾，以下說(shuō)法不正確的是____________。

選項(xiàng)：

A、只能是原子

B、只能是子表

C、原子或子表

D、既非原子也非子表

答案：【只能是原子;原子或子表;既非原子也非子表】4.多選題：在計(jì)算機(jī)中，稀疏矩陣的存儲(chǔ)表示和實(shí)現(xiàn)包括____________。

選項(xiàng)：

A、三元組順序表

B、行或列為主序

C、行邏輯鏈接的順序表

D、十字鏈表

答案：【三元組順序表;行邏輯鏈接的順序表;十字鏈表】5.單選題：非零元素可用三元組（行下標(biāo)，列下標(biāo)，元素值）表示，利用它能夠恢復(fù)一個(gè)稀疏矩陣。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】6.單選題：若廣義表中的每個(gè)數(shù)據(jù)元素都是原子，則廣義表就是線(xiàn)性表。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】7.單選題：在數(shù)組定義后，可以對(duì)數(shù)組的維數(shù)和維界繼續(xù)更改。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】8.已知廣義表GL=(a，(b，c，d，e)，f，g)，下列運(yùn)算head(head(tail(GL)))的結(jié)果是__________。

答案：【b】9.一個(gè)100*100的對(duì)稱(chēng)矩陣，采用壓縮存儲(chǔ)，所需保存的數(shù)據(jù)量大小是___________。

答案：【5050】單元作業(yè)五1.已知數(shù)組a中保存n個(gè)整數(shù)元素，下面遞歸算法計(jì)算n個(gè)元素的平均值。請(qǐng)?jiān)诔绦蚩瞻滋幯a(bǔ)全代碼。建議在提交作業(yè)前驗(yàn)證算法的正確性。

參考答案：returna[0]評(píng)分標(biāo)準(zhǔn)：語(yǔ)句正確10分；否則不得分。第六章樹(shù)和二叉樹(shù)單元作業(yè)六1.假設(shè)用于通訊的電文由8個(gè)字母C0，C1，C2，C3，C4，C5，C6，C7組成，在電文中各字母出現(xiàn)的頻率分別是14，2，1，7，24，18，5，10。請(qǐng)根據(jù)構(gòu)建的哈夫曼樹(shù)計(jì)算其加權(quán)路徑長(zhǎng)度(WPL)，則WPL=。

參考答案：WPL=(1+2)*5+5*4+(7+10+14)*3+(18+24)*2=212評(píng)分標(biāo)準(zhǔn)：計(jì)算正確，5分；否則得0分。2.已知一棵二叉樹(shù)的中序遍歷序列是CDBEAGF，后序遍歷序列是DCEBGFA，請(qǐng)給出該二叉樹(shù)的先序遍歷序列。

根據(jù)中序和后序遍歷序列重構(gòu)二叉樹(shù)，然后再先序遍歷二叉樹(shù)。參考答案：先序遍歷序列是ABCDEFG。評(píng)分標(biāo)準(zhǔn)：序列完全正確，5分；否則，0分。3.設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)，下面遞歸函數(shù)用于計(jì)算二叉樹(shù)的葉子數(shù)量。請(qǐng)?jiān)诳崭裉幫晟拼a，實(shí)現(xiàn)函數(shù)功能。typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;intCalcLeaves(BiTreeT){/*計(jì)算葉子結(jié)點(diǎn)的數(shù)量*/intnum;if(T==NULL)return0;if((T->lchild==NULL)&&(1))return1;num=2;returnnum;}

參考答案：1.T->rchild==NULL2.CalcLeaves(T->lchild)+CalcLeaves(T->rchild)評(píng)分標(biāo)準(zhǔn)：第1、2處正確，各得5分。否則不得分。單元測(cè)驗(yàn)六1.單選題：設(shè)森林F對(duì)應(yīng)的二叉樹(shù)B有m個(gè)結(jié)點(diǎn)。B的根為t，若t的右子樹(shù)有n個(gè)結(jié)點(diǎn)，則森林F中第一棵樹(shù)具有_________個(gè)結(jié)點(diǎn)。

選項(xiàng)：

A、m-n-1

B、m-n

C、m-n+1

D、m-n+2

答案：【m-n】2.單選題：將樹(shù)轉(zhuǎn)化成二叉樹(shù)，則對(duì)其根結(jié)點(diǎn)而言，_________。

選項(xiàng)：

A、右子樹(shù)可能不空

B、左、右子樹(shù)都可能存在

C、左子樹(shù)一定是空的

D、右子樹(shù)一定是空的

答案：【右子樹(shù)一定是空的】3.單選題：對(duì)一棵二叉樹(shù)進(jìn)行先序遍歷的結(jié)果是A,B,D,C,E,G,H,F，中序遍歷的結(jié)果是B,D,A,G,E,H,C,F。則對(duì)這棵二叉樹(shù)后序遍歷的結(jié)果是_______。

選項(xiàng)：

A、D,B,G,H,E,F,C,A

B、G,H,E,F,C,D,B,A

C、G,H,D,E,F,B,C,A

D、D,B,G,H,F,E,C,A

答案：【D,B,G,H,E,F,C,A】4.單選題：滿(mǎn)二叉樹(shù)也是完全二叉樹(shù)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】5.單選題：樹(shù)的雙親表示法是樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】6.單選題：與二叉樹(shù)類(lèi)似，樹(shù)也可進(jìn)行中根遍歷。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】7.假設(shè)存在一棵樹(shù)，其左子樹(shù)包含50個(gè)結(jié)點(diǎn)，右子樹(shù)包含200個(gè)結(jié)點(diǎn)。采用中序遍歷方法，在處理根結(jié)點(diǎn)之前處理了___________個(gè)結(jié)點(diǎn)。

答案：【50】8.使用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)具有5000個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，假設(shè)一個(gè)結(jié)點(diǎn)存儲(chǔ)在第2499的位置，那么它的雙親存儲(chǔ)的位置是___________。

答案：【1249】9.一棵二叉樹(shù)有10個(gè)葉子結(jié)點(diǎn)，其中度為2的結(jié)點(diǎn)有___________個(gè)。

答案：【9】10.具有20個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)總共有_______個(gè)結(jié)點(diǎn)。

答案：【39】第七章圖單元作業(yè)七1.對(duì)附件中圖的頂點(diǎn)進(jìn)行拓?fù)渑判颉?/p>

參考答案：拓?fù)湫蛄校篈,E,F,D,B,G,C評(píng)分標(biāo)準(zhǔn)：序列正確，5分；序列錯(cuò)誤，0分。2.利用普里姆算法或克魯斯卡爾算法，構(gòu)造下面附件中無(wú)向網(wǎng)的最小生成樹(shù)，則該最小生成樹(shù)的權(quán)值之和為。

參考答案：15評(píng)分標(biāo)準(zhǔn)：正確，4分；錯(cuò)誤，0分。3.在廣度優(yōu)先搜索中利用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，如果采用棧的結(jié)構(gòu)，將發(fā)生什么情況？

參考答案：如果采用棧的結(jié)構(gòu)，將是對(duì)圖的深度優(yōu)先搜索。評(píng)分標(biāo)準(zhǔn)：回答正確，5分；回答錯(cuò)誤，0分。4.(1)選擇題：已知圖G的鄰接矩陣如附件所示，該圖是。A.無(wú)向圖B.有向圖C.無(wú)向網(wǎng)D.有向網(wǎng)(2)填空題：上述圖G中頂點(diǎn)B的入度為。A.1B.2C.3D.4

參考答案：(1)B(2)C評(píng)分標(biāo)準(zhǔn)：每個(gè)3分，共6分。單元測(cè)試七1.單選題：在圖的拓?fù)渑判蜻^(guò)程中，輸出的頂點(diǎn)應(yīng)該滿(mǎn)足________。

選項(xiàng)：

A、入度為1

B、出度為1

C、入度為0

D、出度為0

答案：【入度為0】2.單選題：當(dāng)以鄰接表存儲(chǔ)圖時(shí)，采用________易于實(shí)現(xiàn)圖的廣度優(yōu)先搜索。

選項(xiàng)：

A、拓?fù)湫蛄?/p>

B、棧

C、隊(duì)列

D、最小生成樹(shù)

答案：【隊(duì)列】3.單選題：某無(wú)向連通圖具有n個(gè)頂點(diǎn)e條邊，利用克魯斯卡爾算法生成最小生成樹(shù)的時(shí)間復(fù)雜度是________。

選項(xiàng)：

A、O(elogn)

B、O(eloge)

C、O(nloge)

D、O(ne)

答案：【O(eloge)】4.單選題：某無(wú)向連通圖具有n個(gè)頂點(diǎn)e條邊，利用普利姆算法生成最小生成樹(shù)的時(shí)間復(fù)雜度是________。

選項(xiàng)：

A、O(nlogn)

B、O(nloge)

C、O(elogn)

D、O(n^2)

答案：【O(n^2)】5.單選題：圖的廣度優(yōu)先搜索類(lèi)似于二叉樹(shù)的________。

選項(xiàng)：

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、層次遍歷

答案：【層次遍歷】6.單選題：在圖的遍歷過(guò)程中，如果不標(biāo)記已經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，當(dāng)圖中存在回路時(shí)，將導(dǎo)致無(wú)限循環(huán)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】7.單選題：逆鄰接表也可用于表示無(wú)向圖。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】8.一個(gè)具有20個(gè)頂點(diǎn)的無(wú)向連通圖，其生成樹(shù)有________條邊。

答案：【19】9.有向圖具有8個(gè)頂點(diǎn)和10條弧，采用逆鄰接表存儲(chǔ)時(shí)，則包含8個(gè)頭結(jié)點(diǎn)和___________個(gè)表結(jié)點(diǎn)。

答案：【10】10.無(wú)向圖具有10個(gè)頂點(diǎn)和25條邊，采用鄰接表存儲(chǔ)時(shí)，則包含10個(gè)頭結(jié)點(diǎn)和___________個(gè)表結(jié)點(diǎn)。

答案：【50】第八章查找單元測(cè)試八1.單選題：對(duì)長(zhǎng)度為n的線(xiàn)性表，采用順序查找方法查找，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)______。

選項(xiàng)：

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n

答案：【(n+1)/2】2.單選題：假設(shè)有k個(gè)關(guān)鍵碼互為同義詞，若用線(xiàn)性探測(cè)法把這k個(gè)關(guān)鍵碼值存入散列表中，要進(jìn)行的探測(cè)次數(shù)至少為_(kāi)____。

選項(xiàng)：

A、k-1

B、k

C、k+1

D、k*(k+1)/2

答案：【k*(k+1)/2】3.單選題：設(shè)有一組關(guān)鍵字碼{24,3,17,49,60,20}將要插入到表長(zhǎng)為12的散列表中，設(shè)哈希函數(shù)H(key)=key%11。當(dāng)采用線(xiàn)性探測(cè)再散列法處理沖突時(shí)，關(guān)鍵字為60的記錄的地址是_____。

選項(xiàng)：

A、4

B、5

C、6

D、7

答案：【7】4.單選題：對(duì)長(zhǎng)度為n的線(xiàn)性表，采用折半查找方法查找，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)______。

選項(xiàng)：

A、O(logn)

B、O(n)

C、O(nlogn)

D、O(n^2)

答案：【O(logn)】5.多選題：下列關(guān)于二叉排序樹(shù)的說(shuō)法正確的是_____。

選項(xiàng)：

A、中序遍歷二叉排序樹(shù)可以得到一個(gè)關(guān)鍵字的有序序列。

B、若它的右子樹(shù)不空，則右子樹(shù)所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。

C、它的左、右子樹(shù)均為二叉排序樹(shù)。

D、它的平均查找長(zhǎng)度與樹(shù)的形態(tài)有關(guān)。

答案：【中序遍歷二叉排序樹(shù)可以得到一個(gè)關(guān)鍵字的有序序列。;若它的右子樹(shù)不空，則右子樹(shù)所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。;它的左、右子樹(shù)均為二叉排序樹(shù)。;它的平均查找長(zhǎng)度與樹(shù)的形態(tài)有關(guān)?！?.多選題：在哈希表查找中處理沖突時(shí)，開(kāi)放定址法包括_____等方法。

選項(xiàng)：

A、線(xiàn)性探測(cè)再散列

B、二次探測(cè)再散列

C、再哈希法

D、偽隨機(jī)數(shù)探測(cè)再散列

答案：【線(xiàn)性探測(cè)再散列;二次探測(cè)再散列;偽隨機(jī)數(shù)探測(cè)再散列】7.單選題：與順序表查找類(lèi)似，哈希表的平均查找長(zhǎng)度是表中記錄數(shù)n的函數(shù)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】8.單選題：當(dāng)二叉排序樹(shù)蛻變?yōu)閱沃?shù)時(shí)，其平均查找長(zhǎng)度與順序查找相同。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】9.單選題：哈希表查找的基本思想是按記錄的關(guān)鍵字的值決定記錄的存儲(chǔ)地址。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】10.單選題：含有n（n>2）個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是唯一的。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】11.單選題：如果用low和high分別指向搜索區(qū)間的下界和上界，折半查找失敗的判定條件是low>high的結(jié)果為真值。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】12.一個(gè)順序存儲(chǔ)的有序表為{7，9，11，30，42，45，52，65，77，89，91}，第一個(gè)元素7保存在下標(biāo)為1的位置，當(dāng)折半查找89時(shí)，________次比較后查找成功。

答案：【3/三】13.折半查找也稱(chēng)為二分查找，它需要滿(mǎn)足兩個(gè)條件分別，即記錄是有序的并且采用________存儲(chǔ)結(jié)構(gòu)。

答案：【順序】14.在順序表中，采用從后向前查找時(shí)，通常將待查記錄存放在順序表中下標(biāo)為_(kāi)_______的位置，稱(chēng)之為哨兵。

答案：【0/零】單元作業(yè)八1.一組數(shù)據(jù)元素的關(guān)鍵碼是{7，1，14，2，10，18，5，24}，設(shè)哈希表的長(zhǎng)度為12，采用的哈希函數(shù)為H(k)=k%11，用二次探測(cè)再散列法解決沖突，請(qǐng)回答如下問(wèn)題：（1）關(guān)鍵碼24對(duì)應(yīng)的數(shù)據(jù)元素在哈希表中的位置是。（2）哈希表的裝填因子為。（3）在等概率下查找成功時(shí)的平均查找長(zhǎng)度為。

參考答案：(1)6(2)2/3或0.667(3)1.5查找關(guān)鍵碼24需要4次，18需要2次，其他的各需1次。因此，平均查找長(zhǎng)度為(4+2+1*6)/8=1.5。評(píng)分標(biāo)準(zhǔn)：每空4分，共12分。2.判斷下面關(guān)于二叉排序樹(shù)的說(shuō)法是否正確。1.若二叉排序樹(shù)的左、右子樹(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)的值均小于右子樹(shù)所有結(jié)點(diǎn)的值。2.二叉排序樹(shù)和折半查找的平均查找長(zhǎng)度都與logn成正比。3.在二叉排序樹(shù)中插入新結(jié)點(diǎn)時(shí)需要移動(dòng)其他結(jié)點(diǎn)。4.先序遍歷二叉排序樹(shù)可以得到關(guān)鍵字的有序序列。5.一棵含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度與樹(shù)的形態(tài)有關(guān)。

參考答案：正確的說(shuō)法是1、2、5；錯(cuò)誤的說(shuō)法是3、4。對(duì)于3中的說(shuō)法，正確的應(yīng)該是“不需要移動(dòng)其他結(jié)點(diǎn)”。對(duì)于4中的說(shuō)法，正確的應(yīng)該是“中序遍歷”。評(píng)分標(biāo)準(zhǔn)：正確判斷每個(gè)說(shuō)法得2分，否則得0分。3.如果在關(guān)鍵字集合{23，15，26，19，8，5，13，47，39}上實(shí)現(xiàn)折半查找，需要從小到大排序關(guān)鍵字并順序存儲(chǔ)。設(shè)下標(biāo)為0的位置不保存關(guān)鍵字，如果折半查找關(guān)鍵字26，請(qǐng)給出折半查找的次數(shù)及每次查到的關(guān)鍵字。

參考答案：關(guān)鍵字依從小到大保存在下標(biāo)從1至9的順序表中。折半查找2次可以查到26。第一次，(1+9)/2=5，查到19；第二次，(6+9)/2=7.5，下取整為7，查到26。評(píng)分標(biāo)準(zhǔn)：兩次正確，4分；分別查到19和26，每個(gè)數(shù)2分，共4分。第九章內(nèi)部排序單元測(cè)試九1.單選題：用某種排序方法對(duì)關(guān)鍵字集合{26,80,25,46,11,29,63,32,21}進(jìn)行排序時(shí)，元素序列的變化情況如下：(1)26,80,25,46,11,29,63,32,21(2)26,80,25,46,11,29,63,32,21(3)25,26,80,46,11,29,63,32,21(4)25,26,46,80,11,29,63,32,21則所采用的排序方法是_____。

選項(xiàng)：

A、簡(jiǎn)單選擇排序

B、直接插入排序

C、2-路歸并排序

D、快速排序

答案：【直接插入排序】2.單選題：用某種排序方法對(duì)關(guān)鍵字集合{70,12,83,43,56,33,22,8}進(jìn)行排序時(shí)，元素序列的變化情況如下：(1)70,12,83,43,56,33,22,8(2)8,12,83,43,56,33,22,70(3)8,12,83,43,56,33,22,70(4)8,12,22,43,56,33,83,70則所采用的排序方法是_____。

選項(xiàng)：

A、簡(jiǎn)單選擇排序

B、直接插入排序

C、希爾排序

D、快速排序

答案：【簡(jiǎn)單選擇排序】3.單選題：一組記錄的關(guān)鍵字碼為{45,78,57,36,41,90}，利用快速排序的方法，以第一個(gè)記錄為樞軸，則一次劃分的結(jié)果為_(kāi)____。

選項(xiàng)：

A、36,41,45,57,78,90

B、41,36,45,57,78,90

C、41,36,45,78,57,90

D、41,36,45,90,57,78

答案：【41,36,45,57,78,90】4.多選題：下列哪些排序方法是不穩(wěn)定的_____。

選項(xiàng)：

A、冒泡排序

B、希爾排序

C、快速排序

D、堆排序

答案：【希爾排序;快速排序;堆排序】5.多選題：下列哪些排序方法是穩(wěn)定的_____。

選項(xiàng)：

A、直接插入排序

B、冒泡排序

C、歸并排序

D、基數(shù)排序

答案：【直接插入排序;冒泡排序;歸并排序;基數(shù)排序】6.單選題：基數(shù)排序是基于關(guān)鍵字比較的排序。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】7.單選題：快速排序是不穩(wěn)定的。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】8.單選題：堆排序是一種基于插入的排序方法。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】9.單選題：依據(jù)排序所需的工作量，先進(jìn)排序方法的時(shí)間復(fù)雜度是O(nlogn)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】10.歸并排序、堆排序和快速排序的平均時(shí)間性能相當(dāng)，但是________排序方法所需的輔助存儲(chǔ)量最多。

答案：【歸并】11.在堆排序和快速排序中，如果記錄的關(guān)鍵字近似正序或反序，則優(yōu)先選用________排序。

答案：【堆】12.在最好的情況下，冒泡（發(fā)泡）排序只需要交換_________次即可完成排序。（請(qǐng)?zhí)顢?shù)字）

答案：【