數(shù)據(jù)結(jié)構(gòu)與算法（仲愷農(nóng)業(yè)工程學(xué)院）知到智慧樹章節(jié)測(cè)試課后答案2024年秋仲愷農(nóng)業(yè)工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)與算法（仲愷農(nóng)業(yè)工程學(xué)院）知到智慧樹章節(jié)測(cè)試課后答案2024年秋仲愷農(nóng)業(yè)工程學(xué)院第二章單元測(cè)試

線性表是（）。

A:一個(gè)有限序列，可以為空B:一個(gè)元限序列，不可以為空C:一個(gè)無限序列，可以為空D:一個(gè)有限序列，不可以為空

答案:一個(gè)有限序列，可以為空在一個(gè)長度為n的順序表中于第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素，需要向后移動(dòng)（）個(gè)元素。

A:n-iB:n-i+1C:iD:n-i-1

答案:n-i+1鏈表不具有的特點(diǎn)是（）。

A:插入刪除不需要移動(dòng)元素B:不必事先估計(jì)存儲(chǔ)空間C:可隨機(jī)訪問任一元素D:所需空間與線性表長度成正比

答案:可隨機(jī)訪問任一元素線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，各節(jié)點(diǎn)之間的地址（）。

A:連續(xù)與否均可以B:一定是不連續(xù)的C:必須是連續(xù)的

答案:連續(xù)與否均可以若線性表最常用的運(yùn)算是存取第i個(gè)元素及其前驅(qū)的值，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A:循環(huán)單鏈表B:單鏈表C:雙鏈表D:順序表

答案:順序表對(duì)于用一維數(shù)組d[0..n-1]順序存儲(chǔ)的線性表，其算法的時(shí)間復(fù)雜度為O(1)的操作是（）。

A:查找第i個(gè)元素(1≤i≤n)B:將n個(gè)元素從小到大排序C:從線性表中刪除第i個(gè)元素(1≤i≤n)D:在線性表中第i個(gè)元素之后插入一個(gè)元素

答案:查找第i個(gè)元素(1≤i≤n)在單鏈表中，若*p節(jié)點(diǎn)不是尾節(jié)點(diǎn)，在其后插入*s節(jié)點(diǎn)的操作是（）。

A:s->next=p->next;p->next=s;B:s->next=p->next;p=s;C:p->next=s;s->next=p;D:s--->next=p;p->next=s;

答案:s->next=p->next;p->next=s;在一個(gè)單鏈表中，刪除*p節(jié)點(diǎn)(非尾節(jié)點(diǎn))之后的一個(gè)節(jié)點(diǎn)的操作是（）。

A:p->next->next=p->nextB:p->next=pC:p->next->next=pD:p->next=p->next->next

答案:p->next=p->next->next在一個(gè)雙鏈表中，在*p節(jié)點(diǎn)(非尾節(jié)點(diǎn))之后插入一個(gè)節(jié)點(diǎn)*s的操作是（）。

A:s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;B:s->prior=p;p->next=s;p->next->prior=s;s->next=p->next;C:p->next=s;s->prior=p;s->next=p->next;p->next->prior=s;D:p->prior=s;s->next=p;s->next->prior=p;p->next=s->next;

答案:s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;在一個(gè)雙鏈表中，刪除*p節(jié)點(diǎn)(非尾節(jié)點(diǎn))之后的一個(gè)節(jié)點(diǎn)的操作是（）。

A:p->next=p->next->next;p->next->prior=p;B:p->next->prior=p;p->next=p->next->next;C:p->next->next=p->next;p->next->prior=p;D:p->next=p->next->next;p->next->next->prior=p;

答案:p->next=p->next->next;p->next->prior=p;

第三章單元測(cè)試

設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6?依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s4,s3,s6,s5,s1，則棧的容量至少應(yīng)該是

A:2B:3C:5D:4

答案:3一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能輸出序列是

A:1,2,3,4,5B:5,4,3,1,2C:3,2,4,5,1D:3,5,4,2,1

答案:5,4,3,1,2一個(gè)隊(duì)列的入隊(duì)序列是1，3，5，7，9，則出隊(duì)的輸出序列只能是

A:1,3,5,7,9B:9,5,1,7,3C:9,7,5,3,1D:1,5,9,3,7

答案:1,3,5,7,9設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為

A:r-f+1B:(r-f+n)%nC:r-fD:(r-f)%n+1

答案:(r-f+n)%n設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作后其尾指針rear值為

A:rear=(rear+1)%(m-1)B:rear=rear+1C:rear=(rear+1)%mD:rear=(rear-1)%m

答案:rear=(rear+1)%m遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，使用的數(shù)據(jù)結(jié)構(gòu)是

A:多維數(shù)組B:線性表C:棧D:隊(duì)列

答案:棧棧中元素的進(jìn)出原則是

A:?？談t進(jìn)B:棧滿則出C:后進(jìn)先出D:先進(jìn)先出

答案:后進(jìn)先出判定一個(gè)棧ST（最多元素為m0）為空的條件是

A:ST->top<>0B:ST->top==m0C:ST->top<>m0D:ST->top==0

答案:ST->top==0判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是

A:QU->front?=?=?QU->rear?B:QU->rear?－?QU->front?－1=?=?m0?C:QU->rear?－?QU->front?=?=?m0?D:QU->front?=?=?QU->rear?+1

答案:QU->rear?－?QU->front?=?=?m0?在一個(gè)鏈?zhǔn)疥?duì)列中.假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則插入s所指的結(jié)點(diǎn)運(yùn)算是

A:f->next=s;f=s;?B:s->next=s;r=s;?C:s->next=f;f=s;?D:r->next=s;r=s;?

答案:r->next=s;r=s;?向一個(gè)棧指針為HS的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)s所指的結(jié)點(diǎn)時(shí),則執(zhí)行

A:S->NEXT=HS->NEXT;HS->NEXT=S;B:?S->NEXT=HS;HS=HS->NEXT;?C:HS->NEXT=S;?

答案:S->NEXT=HS->NEXT;HS->NEXT=S;設(shè)一個(gè)棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（?）。

A:45?1?32B:43?1?25C:5?1?23?4?D:3?2?15?4?

答案:3?2?15?4?進(jìn)棧序列為a，b，c，則通過入、出?？赡艿玫降腶，b，c的不同排列個(gè)數(shù)是（）。

A:7B:6C:5D:4

答案:5表達(dá)式a*(b+c)-d?的后綴表達(dá)式是(?)。

A:-+*abcd?B:abcd*+-C:abc*+d-?D:abc+*d-?

答案:abc+*d-?設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A:棧B:線性表的順序存儲(chǔ)結(jié)構(gòu)C:隊(duì)列D:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?

答案:棧用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)()。

A:隊(duì)頭、隊(duì)尾指針都可能要修改B:隊(duì)頭、隊(duì)尾指針都要修改C:僅修改隊(duì)尾指針D:僅修改隊(duì)頭指針

答案:隊(duì)頭、隊(duì)尾指針都可能要修改假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。

A:(rear-front+m)%m?B:(rear-front)%m?C:(front-rear+m)%m?D:rear-front+1??

答案:(rear-front+m)%m?循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是(??)。?

A:rear-front-1??B:(rear-front+m)%m?C:rear-front+1??D:rear-front?

答案:(rear-front+m)%m?若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？()?

A:1?和5B:4和2C:5?和1?D:2和4

答案:1?和5棧和隊(duì)都是（）。?

A:順序存儲(chǔ)的線性結(jié)構(gòu)?B:限制存取點(diǎn)的非線性結(jié)構(gòu)C:限制存取點(diǎn)的線性結(jié)構(gòu)D:鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)?

答案:限制存取點(diǎn)的線性結(jié)構(gòu)棧的操作原則是（?）。?

A:先進(jìn)先出B:后進(jìn)先出C:后進(jìn)后出?D:順序進(jìn)出?

答案:后進(jìn)先出下面術(shù)語中，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的是（?）。?

A:棧B:順序表C:循環(huán)隊(duì)列?D:順序棧?

答案:棧棧和隊(duì)列具有相同的（?）。?

A:邏輯結(jié)構(gòu)?B:運(yùn)算C:存儲(chǔ)結(jié)構(gòu)D:抽象數(shù)據(jù)類型

答案:邏輯結(jié)構(gòu)?遞歸算法必須包括（?）。?

A:終止條件和迭代部分?B:迭代部分C:遞歸部分D:終止條件和遞歸部分??

答案:終止條件和遞歸部分??

第四章單元測(cè)試

串s="ABCDEF"的串長度為

A:8B:3C:7D:4

答案:7設(shè)有串s="ABCBBCBBCBBA"和串t="CB"，則串t在s中的匹配位置是

A:9B:6C:1D:3

答案:3串是

A:不少于一個(gè)字符的序列B:有限個(gè)字符的序列C:不少于一個(gè)字母的序列D:任意個(gè)字母的序列

答案:有限個(gè)字符的序列設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為

A:求子串B:聯(lián)接C:求串長D:匹配

答案:匹配設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為

A:33B:13C:18D:40

答案:33設(shè)A是n*n的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為

A:i(i-l)/2+jB:j(j-l)/2+iC:j(j-l)/2+i-1D:i(i-l)/2+j-1

答案:j(j-l)/2+i對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是

A:節(jié)省存儲(chǔ)空間B:便于輸入和輸出C:便于進(jìn)行矩陣運(yùn)算D:降低運(yùn)算的時(shí)間復(fù)雜度

答案:節(jié)省存儲(chǔ)空間有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是

A:66B:33C:60D:180

答案:66廣義表（a,(b,c),d,e）的表頭為

A:a,(b,c)B:aC:(a)D:(a,(b,c))

答案:a下面說法不正確的是

A:廣義表難以用順序存儲(chǔ)結(jié)構(gòu)B:廣義表可以是一個(gè)多層次的結(jié)構(gòu)C:廣義表至少有一個(gè)元素D:廣義表可以是一個(gè)遞歸表

答案:廣義表至少有一個(gè)元素設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為

A:

1和1B:1和3C:2和3D:1和2

答案:1和2廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是

A:(c,d)B:dC:c,dD:((c,d))

答案:((c,d))串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表。

A:錯(cuò)B:對(duì)

答案:對(duì)KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。

A:對(duì)B:錯(cuò)

答案:對(duì)稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。

A:錯(cuò)B:對(duì)

答案:對(duì)數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入，刪除等操作。

A:對(duì)B:錯(cuò)

答案:錯(cuò)若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。

A:對(duì)B:錯(cuò)

答案:錯(cuò)廣義表中的元素或者是一個(gè)不可分割的原子，或者是一個(gè)非空的廣義表。

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第五章單元測(cè)試

設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）

A:7B:6C:5D:8

答案:8一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）

A:501B:250C:499D:500

答案:501設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()

A:2n-1B:2n+1C:不確定D:2n

答案:2n-1一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有()結(jié)點(diǎn)

A:2hB:2h-1C:h+1D:2h+1

答案:2h-1將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度（）

A:6B:4C:7D:5

答案:6對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，

同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用()次序的遍歷實(shí)現(xiàn)編號(hào)

A:后序B:層序C:先序D:中序

答案:后序樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的()

A:后序B:中序C:層序D:先序

答案:中序在下列存儲(chǔ)形式中，哪一個(gè)不是樹的存儲(chǔ)形式？（）

A:孩子鏈表示法B:孩子兄弟表示法C:順序存儲(chǔ)結(jié)構(gòu)D:雙親表示法

答案:順序存儲(chǔ)結(jié)構(gòu)已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。

A:不確定B:CBEFDAC:FEDCBAD:CBEDFA

答案:CBEFDA某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。

A:任一結(jié)點(diǎn)無左子樹B:空或只有一個(gè)結(jié)點(diǎn)C:任一結(jié)點(diǎn)無右子樹D:高度等于其結(jié)點(diǎn)數(shù)

答案:高度等于其結(jié)點(diǎn)數(shù)若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為()

A:X的雙親B:X的左子樹中最右葉結(jié)點(diǎn)C:X的右子樹中最左結(jié)點(diǎn)D:X的左子樹中最右結(jié)點(diǎn)

答案:X的左子樹中最右結(jié)點(diǎn)二叉樹的第i層上最多含有結(jié)點(diǎn)數(shù)為（

）。

A:B:

C:

D:

答案:

n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（

）

A:n+1B:nC:2nD:n-1

答案:n+1由3

個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（

）

A:5B:2C:3D:4

答案:5當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組

A[l..n]中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（

）

A:A[2i](2i=<n)

B:A[2i+1](2i+1=<n)C:A[i/2]D:無法確定

答案:無法確定度為4，高度為h的樹，（

）。

A:至多有個(gè)結(jié)點(diǎn)B:至少有h+4個(gè)結(jié)點(diǎn)C:至少有4h個(gè)結(jié)點(diǎn)D:至少有h+3個(gè)結(jié)點(diǎn)

答案:至少有h+3個(gè)結(jié)點(diǎn)用孩子鏈存儲(chǔ)結(jié)構(gòu)表示樹，其優(yōu)點(diǎn)之一是（

）比較方便。

A:判斷兩個(gè)結(jié)點(diǎn)是不是兄弟B:判斷指定結(jié)點(diǎn)在第幾層C:計(jì)算機(jī)指定結(jié)點(diǎn)的度D:找指定結(jié)點(diǎn)的雙親

答案:計(jì)算機(jī)指定結(jié)點(diǎn)的度根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（

）。

A:100，11，10，1，0B:000，001，010，011，1C:001，000，01，11，10D:111，110，10，01，00

答案:100，11，10，1，0一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（

）。

A:DACEFBG

B:ABCDEFGC:ADBCFEG

D:CABDEFG

答案:ABCDEFG二叉樹是度為2的有序樹。（

）

A:對(duì)B:錯(cuò)

答案:錯(cuò)對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹，其高度為。（

）

A:錯(cuò)B:對(duì)

答案:錯(cuò)二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。（

）

A:對(duì)B:錯(cuò)

答案:對(duì)一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。（

）

A:錯(cuò)B:對(duì)

答案:錯(cuò)中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（

）

A:錯(cuò)B:對(duì)

答案:對(duì)由一棵二叉樹的前序序列和后序序列可以唯一確定它。（

）

A:錯(cuò)B:對(duì)

答案:錯(cuò)完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（

）

A:對(duì)B:錯(cuò)

答案:對(duì)將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。（

）

A:對(duì)B:錯(cuò)

答案:錯(cuò)一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。（

）

A:對(duì)B:錯(cuò)

答案:錯(cuò)當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹的WPL值為最小時(shí)，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。（

）

A:錯(cuò)B:對(duì)

答案:錯(cuò)

第六章單元測(cè)試

要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。

A:n+1B:nC:n-1D:2n

答案:n在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍

A:2B:1/2C:1D:4

答案:2下列說法不正確的是（）

A:圖的深度遍歷不適用于有向圖B:圖的深度遍歷是一個(gè)遞歸過程C:圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次

D:遍歷的基本算法有兩種：深度遍歷和廣度遍歷

答案:圖的深度遍歷不適用于有向圖下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（）

A:有向圖B:AOE網(wǎng)C:無向圖D:AOV網(wǎng)

答案:無向圖已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，G的拓?fù)湫蛄惺牵?/p>

）。

A:V1,V3,V4,V6,V2,V5,V7B:V1,V3,V2,V6,V4,V5,V7C:V1,V2,V5,V3,V4,V6,V7D:V1,V3,V4,V5,V2,V6,V7

答案:V1,V3,V4,V6,V2,V5,V7關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）

A:最短回路B:從源點(diǎn)到匯點(diǎn)的最短路徑C:從源點(diǎn)到匯點(diǎn)的最長路徑D:最長回路

答案:從源點(diǎn)到匯點(diǎn)的最長路徑下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。

A:所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成B:某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C:關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間D:任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成

答案:任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成任何一個(gè)帶權(quán)無向連通圖（）最小生成樹

A:只有一棵B:可能不存在C:一定有多棵D:有一棵或多棵

答案:有一棵或多棵判斷一個(gè)有向圖是否存在回路除了可以使用拓?fù)渑判蛩惴?，還可以使用（）

A:求最短路徑的Dijkstra算法B:求關(guān)鍵路徑的方法C:廣度優(yōu)先遍歷算法D:深度優(yōu)先遍歷算法

答案:深度優(yōu)先遍歷算法如果從無向圖的任一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（）

A:完全圖B:有回路C:連通圖D:一棵樹

答案:連通圖采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）算法

A:中序遍歷B:先序遍歷C:層序遍歷D:后序遍歷

答案:先序遍歷采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）算法

A:后序遍歷B:先序遍歷C:中序遍歷D:層序遍歷

答案:層序遍歷一個(gè)無向連通圖的最小生成樹是含有該連通圖的全部頂點(diǎn)的（）

A:極小連通子圖B:極大連通子圖C:極大子圖D:極小子圖

答案:極小連通子圖無權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（）。

A:第i行0的元素個(gè)數(shù)B:第i列非0的元素個(gè)數(shù)C:第i行非0的元素個(gè)數(shù)D:第i列0的元素個(gè)數(shù)

答案:第i列非0的元素個(gè)數(shù)設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（

）條邊。

A:B:n*(n+1)/2

C:n-1D:n*(n-1)/2

答案:n*(n-1)/2

由n個(gè)頂點(diǎn)、e條邊構(gòu)成的圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為（

）。

A:B:O(n)C:D:O(n+e)

答案:O(n+e)一個(gè)具有n個(gè)頂點(diǎn)的五項(xiàng)圖，采用鄰接矩陣表示，這該矩陣大小為（

）。

A:B:n-1C:nD:

答案:設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（

）。

A:aedfbcB:acfebdC:aedfcbD:aebcfd

答案:aedfcb一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（

）個(gè)連通分量。

A:n-1B:1C:0D:n

答案:1

第七章單元測(cè)試

對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須

A:順序但鍵值不一定有序B:鍵值有序的順序表C:鏈接表但鍵值不一定有序D:鍵值有序的鏈接表

答案:鍵值有序的順序表有一個(gè)有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng)()比較后查找成功

A:3B:4C:2D:12

答案:4設(shè)散列表長度為m，散列函數(shù)為H（key）=key%p，為了減少發(fā)生沖突的可能性，p應(yīng)取

A:小于m的最大素?cái)?shù)B:小于m的最大奇數(shù)C:小于m的最大合數(shù)D:小于m的最大偶數(shù)

答案:小于m的最大素?cái)?shù)查找效率最高的二叉排序樹是

A:所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹B:沒有左子樹的二叉排序樹C:所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹D:平衡二叉樹

答案:平衡二叉樹以下說法錯(cuò)誤的是

A:散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法B:散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址C:負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度D:散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針

答案:散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針順序查找法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表

A:散列存儲(chǔ)B:壓縮存儲(chǔ)C:順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)D:索引存儲(chǔ)

答案:順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)下列排序方法中，(?)是穩(wěn)定的排序方法

A:快速排序，堆排序B:歸并排序，冒泡排序C:堆排序，冒泡排序D:直接選擇排序，歸并排序

答案:歸并排序，冒泡排序若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長度ASL為(???)。

A:(n+1)/2B:?(n-1)/2C:n/2?D:n

答案:(n+1)/2適用于折半查找的表的存儲(chǔ)方式及元素排列要求為(????)??

A:鏈接方式存儲(chǔ)，元素有序?B:順序方式存儲(chǔ)，元素有序?C:順序方式存儲(chǔ)，元素?zé)o序?D:鏈接方式存儲(chǔ)，元素?zé)o序

答案:順序方式存儲(chǔ)，元素有序?當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度(????)??

A:不一定B:取決于表遞增還是遞減C:必定快D:在大部分情況下要快

答案:在大部分情況下要快二叉查找樹的查找效率與二叉樹的(??)有關(guān)

A:高度?B:結(jié)點(diǎn)的多少C:結(jié)點(diǎn)的位置?D:樹型

答案:樹型二叉查找樹在?(???)時(shí)其查找效率最低。

A:結(jié)點(diǎn)太復(fù)雜B:呈單枝樹C:完全二叉樹D:結(jié)點(diǎn)太多

答案:呈單枝樹如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用(????)查找法。

A:分快查找B:順序查找C:基于屬性D:折半查找

答案:分快查找分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是(????)。?

A:（100，60，?80，?90，?120，110，130）B:（100，80，?90，?60，?120，110，130）C:（100，120，110，130，80，?60，?90）D:(100，80，?60，?90，?120，130，110)?

答案:（100，60，?80，?90，?120，110，130）設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地