數(shù)據(jù)結(jié)構(gòu)知到智慧樹章節(jié)測(cè)試課后答案2024年秋海南師范大學(xué)

數(shù)據(jù)結(jié)構(gòu)知到智慧樹章節(jié)測(cè)試課后答案2024年秋海南師范大學(xué)第一章單元測(cè)試

從一個(gè)二維數(shù)組b[m][n]中找出最大值元素的時(shí)間復(fù)雜度為

A:mB:nC:m*nD:m+n

答案:m*n在以下時(shí)間復(fù)雜度的數(shù)量級(jí)中，數(shù)量級(jí)最大的是

A:B:C:D:

答案:下面程序段的時(shí)間復(fù)雜度為____________。for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j;

A:O(m*n)B:O(n2)C:O(m2)D:O(m+n)

答案:O(m*n)執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為（

）。for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)

S;

A:n(n+1)B:n2C:n(n+1)/2D:n2/2

答案:n(n+1)/2線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：（

）。

A:多對(duì)一關(guān)系B:多對(duì)多關(guān)系C:一對(duì)多關(guān)系D:一對(duì)一關(guān)系

答案:一對(duì)一關(guān)系數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（

）結(jié)構(gòu)。

A:物理B:物理和存儲(chǔ)C:邏輯D:存儲(chǔ)

答案:邏輯算法分析的目的是：（

）。

A:分析算法的易懂性和文檔性B:研究算法中的輸入和輸出的關(guān)系C:分析算法的效率以求改進(jìn)D:找出數(shù)據(jù)結(jié)構(gòu)的合理性

答案:分析算法的效率以求改進(jìn)算法分析的兩個(gè)主要方面是：（

）。

A:數(shù)據(jù)復(fù)雜性和程序復(fù)雜性B:空間復(fù)雜性和時(shí)間復(fù)雜性C:正確性和簡(jiǎn)明性D:可讀性和文檔性

答案:空間復(fù)雜性和時(shí)間復(fù)雜性計(jì)算機(jī)算法指的是：（

）。

A:解決問題的有限運(yùn)算序列B:調(diào)度方法C:排序方法D:計(jì)算方法

答案:解決問題的有限運(yùn)算序列計(jì)算機(jī)算法必須具備輸入、輸出和（

）等5個(gè)特性。

A:易讀性、穩(wěn)定性和安全性B:可行性、可移植性和可擴(kuò)充性C:可行性、確定性和有窮性D:確定性、有窮性和穩(wěn)定性

答案:可行性、確定性和有窮性一個(gè)算法的好壞可以通過復(fù)雜性、可讀性、健壯性、高效性這四個(gè)方面進(jìn)行評(píng)價(jià)。

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

答案:錯(cuò)數(shù)據(jù)結(jié)構(gòu)是一門研究算法的學(xué)科。

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

答案:錯(cuò)數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、圖結(jié)構(gòu)、樹形結(jié)構(gòu)、集合。

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

答案:對(duì)線性表的邏輯順序與存儲(chǔ)順序總是一致的。

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

答案:錯(cuò)每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找。

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

答案:錯(cuò)線性結(jié)構(gòu)中元素之間只存在多對(duì)多關(guān)系。

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

答案:錯(cuò)在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。

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

答案:對(duì)在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

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

答案:對(duì)算法分析的目的是分析算法的效率以求改進(jìn)。

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

答案:對(duì)同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。

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

答案:對(duì)

第二章單元測(cè)試

在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：（

）

A:在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）B:刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）C:訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）D:將n個(gè)結(jié)點(diǎn)從小到大排序

答案:訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（

）個(gè)元素。

A:63.5B:63C:7D:8

答案:63.5線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（

）

A:一定是不連續(xù)的B:連續(xù)或不連續(xù)都可以C:必須是連續(xù)的D:部分地址必須是連續(xù)的

答案:連續(xù)或不連續(xù)都可以若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用_______存儲(chǔ)方式最節(jié)省時(shí)間。

A:帶頭節(jié)點(diǎn)的雙循環(huán)鏈表B:順序表C:雙鏈表D:單循環(huán)鏈表

答案:順序表在一個(gè)以h為頭結(jié)點(diǎn)的單循環(huán)鏈表中，使指針p指向鏈尾結(jié)點(diǎn)的條件是（

）。

A:p->next==h;B:p->next==h->nextC:p->next->next==hD:p->next==NULL

答案:p->next==h;鏈表是一種采用（

）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表

A:鏈?zhǔn)?/p>

B:順序C:網(wǎng)狀D:星式

答案:鏈?zhǔn)?/p>

單鏈表包括兩個(gè)域：（

）。

A:數(shù)據(jù)域和指針域B:數(shù)據(jù)域和星式C:數(shù)據(jù)域和表位D:鏈?zhǔn)胶蛿?shù)字

答案:數(shù)據(jù)域和指針域單鏈表可以用（

）來命名。

A:KB:LC:結(jié)點(diǎn)名D:頭指針的名字

答案:頭指針的名字單鏈表的插入操作其時(shí)間復(fù)雜度為（

）。

A:O（n2）B:O（1）C:O（n）D:O（n3）

答案:O（n）

順序表的插入操作的時(shí)間復(fù)雜度為（

）。

A:O（n）B:O（n2）C:O（1）

D:O（n3）

答案:O（n）線性表的邏輯結(jié)構(gòu)特性是一對(duì)多的。

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

答案:錯(cuò)順序表在進(jìn)行插入和刪除操作時(shí)不需要移動(dòng)元素。

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

答案:錯(cuò)對(duì)于鏈表是依靠指針來反映其線性邏輯關(guān)系的。

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

答案:對(duì)在單鏈表的第一個(gè)結(jié)點(diǎn)之前是不允許附設(shè)結(jié)點(diǎn)的。

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

答案:錯(cuò)在單鏈表中首元結(jié)點(diǎn)就是頭結(jié)點(diǎn)。

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

答案:錯(cuò)循環(huán)單鏈表的最大優(yōu)點(diǎn)是從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個(gè)元素。

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

答案:對(duì)線性表采用鏈?zhǔn)酱鎯?chǔ)，便于插入和刪除操作。

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

答案:對(duì)線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

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

答案:對(duì)單鏈表可以有多個(gè)指針域。

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

答案:錯(cuò)順序表的每個(gè)元素所占的存儲(chǔ)單元是相等的。

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

答案:對(duì)

第三章單元測(cè)試

棧的插入和刪除操作在（

）

A:指定位置

B:棧頂

C:棧底

D:任意位置

答案:棧頂

五節(jié)車廂以編號(hào)a，b，c，d，e順序進(jìn)入鐵路調(diào)度站（棧），可以得到（

）的編組

A:b，d，a，c，e

B:c，d，e，a，b

C:c，e，d，b，a

D:a，c，e，b，d

答案:c，e，d，b，a

判定一個(gè)順序棧S（?？臻g大小為n）為空的條件是（）

A:S->top==n

B:S->top!=0

C:S->top==0

D:S->top!=n

答案:S->top==0

在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作為（

）

A:s->next=front;front=s;

B:s->next=rear;rear=s

C:front=front->next

D:rear->next=s;rear=s;

答案:rear->next=s;rear=s;

一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的出隊(duì)序列是（

）

A:1，4，3，2

B:4，3，2，1

C:1，2，3，4

D:3，4，1，2

答案:4，3，2，1

依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì)頭元素是（）

A:a

B:cC:bD:d

答案:c棧是一種非線性結(jié)構(gòu)。

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

答案:錯(cuò)隊(duì)列允許在一端進(jìn)行插入，另一端進(jìn)行刪除操作。

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

答案:對(duì)在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸操作是用到棧實(shí)現(xiàn)的。

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

答案:對(duì)遞歸程序在執(zhí)行時(shí)是用隊(duì)列來保存調(diào)用過程中的參數(shù)、局部變量和返回參數(shù)的。

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

答案:錯(cuò)在表達(dá)式求值算法中運(yùn)用到隊(duì)列來實(shí)現(xiàn)的。

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

答案:錯(cuò)隊(duì)列假溢出問題的一個(gè)解決方法是運(yùn)用循環(huán)隊(duì)列。

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

答案:對(duì)隊(duì)列Q滿的條件是：Q.front==Q.rear。

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

答案:錯(cuò)每當(dāng)在新隊(duì)列中插入一個(gè)新元素時(shí)，尾指針rear增1。

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

答案:對(duì)在順序隊(duì)列中，頭指針始終指向隊(duì)列的最后一個(gè)元素。

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

答案:錯(cuò)在順序隊(duì)列中，尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。

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

答案:對(duì)

第四章單元測(cè)試

串的長(zhǎng)度是指（

）

A:串中所含非空格字符的個(gè)數(shù)B:串中所含不同字符的個(gè)數(shù)C:串中所含不同字母的個(gè)數(shù)D:串中所含字符的個(gè)數(shù)

答案:串中所含不同字母的個(gè)數(shù)設(shè)有串t='I

am

a

good

student

'，那么Substr(t,6,6)=（

）

A:studentB:a

good

sC:goodD:agood

答案:agood串“ababaaababaa”的next數(shù)組為（

）

A:012121111212B:012345678999C:0123012322345D:011234223456

答案:011234223456函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（

）

A:“ASTRUCTUR”B:“DATASTRUCTURE”C:“DATA”D:“STRUCTURE”

答案:“STRUCTURE”設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（

）

A:求串長(zhǎng)B:連接C:求子串D:模式匹配

答案:模式匹配設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是（

）

A:BCDEFB:BCDEFGC:BCPQRSTD:BCDEFEF

答案:BCDEFEF若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘；’,S4=‘012345’,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其結(jié)果為（）

A:ABC；G1234

B:ABCD；2345

C:ABC；G2345

D:ABC；G0123

答案:ABC；G1234

主串為’abaababaddecab’

,模式串為’abad’。使用KMP算法需要（

）次匹配成功。

A:5B:12C:10D:4

答案:4

不包含任何字符的串稱為空白串。

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

答案:錯(cuò)在串的模式匹配運(yùn)算中，被匹配的主串稱為模式。

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

答案:錯(cuò)組成串的數(shù)據(jù)元素只能是字符。

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

答案:對(duì)串不能采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。

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

答案:錯(cuò)模式匹配簡(jiǎn)單算法時(shí)間復(fù)雜度是O(m*n)。

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

答案:對(duì)空格串與空串的沒有區(qū)別。

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

答案:錯(cuò)設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的KMP算法的時(shí)間復(fù)雜度為O(m+n)。

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

答案:對(duì)兩個(gè)字符串相等的充分必要條件是兩串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等。

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

答案:對(duì)串是一種非線性結(jié)構(gòu)。

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

答案:錯(cuò)串的模式匹配算法只能采用串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來實(shí)現(xiàn)。

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

答案:錯(cuò)

第五章單元測(cè)試

設(shè)二維數(shù)組A[0..m-1][0..n-1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，每個(gè)元素aij占d個(gè)字節(jié)，則元素aij的地址為（

）

A:LOC(a00)+(i*n+j)*dB:LOC(a00)+(j*n+i-1)*dC:LOC(a00)+((i-1)*n+j-1)*dD:LOC(a00)+((j-1)*n+i-1)*d

答案:LOC(a00)+(i*n+j)*d若數(shù)組A[0..m-1][0..n-1]按列優(yōu)先順序存儲(chǔ)，則aij地址為（）

A:LOC(a00)+(j-1)*m+I-1B:LOC(a00)+(j-1)*n+i-1C:LOC(a00)+j*n+ID:LOC(a00)+j*m+i

答案:LOC(a00)+j*m+i若下三角矩陣An*n，按行順序壓縮存儲(chǔ)在數(shù)組a[0..(n+1)n/2]中，則非零元素aij的地址為（）（設(shè)每個(gè)元素占d個(gè)字節(jié)）

A:LOC(a00)+((i-1)i/2+i-1)*dB:LOC(a00)+((i-1)i/2+j-1)*dC:LOC(a00)+((i+1)i/2+j)*dD:LOC(a00)+((j-1)j/2+i)*d

答案:LOC(a00)+((i-1)i/2+j-1)*d稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）

A:散列和十字鏈表B:三元組和十字鏈表C:三元組和散列D:二維數(shù)組和三維數(shù)組

答案:三元組和十字鏈表廣義表A=((x,(a,b)),((x,(a,b)),y))，則運(yùn)算head(head(tail(A)))為（

）

A:AB:(x,(a,b))

C:xD:(a,b)

答案:(x,(a,b))

二維數(shù)組可以看成是一個(gè)線性表。

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

答案:對(duì)不做插入刪除操作的數(shù)組，采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組比較合適。

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

答案:對(duì)二維數(shù)組的順序存儲(chǔ)方法只可以行序?yàn)橹餍虻拇鎯?chǔ)方式。

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

答案:錯(cuò)對(duì)稱矩陣在存儲(chǔ)時(shí)可進(jìn)行壓縮存儲(chǔ)。

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

答案:對(duì)稀疏矩陣是非零值元素分布有一定規(guī)律的矩陣。

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

答案:錯(cuò)

第六章單元測(cè)試

一棵具有67個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為（

）。

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

答案:7給定樹如圖所示，請(qǐng)列出的中序遍歷序列（

）

。

A:ABDCEFB:DBEFCAC:DBAECFD:DABECF

答案:DBAECF設(shè)有樹如圖所示，則結(jié)點(diǎn)g的度為（

）。

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

答案:3用4個(gè)權(quán)值{7,2,4,5}構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是（

）。

A:35B:34C:32D:33

答案:35對(duì)于任何一棵具有n個(gè)結(jié)點(diǎn)的線索二叉樹，具有（

）個(gè)線索。

A:

n-1B:

n+1C:

0D:

n

答案:

n+1一棵深度為5的滿二叉樹有（

）個(gè)分支結(jié)點(diǎn)。

A:7B:14C:15D:16

答案:15一棵深度為5的滿二叉樹有（

）個(gè)葉子。

A:31B:32C:17D:16

答案:16給定二叉樹如圖所示，請(qǐng)列出的后序遍歷序列（

）

。

A:BADCEB:BDECAC:BACDED:ABCDE

答案:BDECA設(shè)有二叉樹如圖所示，按其中序遍歷次序遍歷，對(duì)于根a的右子樹最先訪問的結(jié)點(diǎn)是（

）。

A:bB:hC:dD:a

答案:h若按層序?qū)ι疃葹?的完全二叉樹中全部結(jié)點(diǎn)從１開始編號(hào)，則編號(hào)為10的結(jié)點(diǎn)其右孩子的編號(hào)為（

）。

A:12B:11

C:20

D:21

答案:21二叉樹的子樹無左右之分的。

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

答案:錯(cuò)二叉樹的度大于2的樹。

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

答案:錯(cuò)二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)。

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

答案:錯(cuò)二叉樹不能轉(zhuǎn)換為樹，樹也不能轉(zhuǎn)換為二叉樹。

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

答案:錯(cuò)哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是最小的。

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

答案:對(duì)滿二叉樹就是一種特殊的完全二叉樹。

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

答案:對(duì)假設(shè)n(n>0)個(gè)結(jié)點(diǎn)的樹，它有且只有1個(gè)根結(jié)點(diǎn)。

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

答案:對(duì)n個(gè)結(jié)點(diǎn)的線索二叉樹中線索的數(shù)目是不確定的。

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

答案:錯(cuò)不含任何結(jié)點(diǎn)的空樹，它可以是一棵樹也是一棵二叉樹。

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

答案:對(duì)可以采用遞歸的方法計(jì)算二叉樹的深度。

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

答案:對(duì)

第七章單元測(cè)試

無向圖的鄰接矩陣是一個(gè)(

)

A:零矩陣B:上三角矩陣C:對(duì)稱矩陣D:對(duì)角陣

答案:對(duì)稱矩陣若圖G(V,E)中含有7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的需要的邊數(shù)最少是(

)

A:6B:16C:21D:15

答案:16如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先遍歷即可訪問所以頂點(diǎn)，則該圖一定是(

)

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

答案:連通圖用Prim算法求一個(gè)連通的帶權(quán)圖的最小代價(jià)生成樹，在算法執(zhí)行的某時(shí)刻，已選取的頂點(diǎn)集合U={1,2,3},已選取的邊的集合TE={(1,2),(2,3)},要選取下一條權(quán)值最小的邊，應(yīng)該從(

)組中選取。

A:{(3,4),(3,5),(4,5),(1,4)}B:{(1,4),(3,4),(3,5),(2,5)}C:{(4,5),(1,3),(3,5)}D:{(1,2),(2,3),(3,5)}

答案:{(1,4),(3,4),(3,5),(2,5)}已知圖的頂點(diǎn)集合U={1,2,3,4},邊的集合TE={(1,2),(1,3),(2,3),(3,4)}，則從頂點(diǎn)1出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（

）。

A:1234B:1423C:1432

D:2314

答案:1234已知圖的頂點(diǎn)集合U={1,2,3,4},邊的集合TE={(1,2),(1,3),(2,3),(3,4)}，則從頂點(diǎn)1出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（

）。

A:1324B:1432C:1243D:1342

答案:1324任何一個(gè)無向連通圖的最小生成樹（

）。

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

答案:只有一棵有8個(gè)結(jié)點(diǎn)的無向圖最多有（

）條邊。

A:56B:112C:14D:28

答案:28有8個(gè)結(jié)點(diǎn)的無向連通圖最少有（

）條邊。

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

答案:7有8個(gè)結(jié)點(diǎn)的有向完全圖有（

）條邊。

A:14B:28C:56D:112

答案:56已知無向圖的頂點(diǎn)集合U={1,2,3,4},邊的集合TE={(1,2),(1,3),(2,3),(3,4)}，則頂點(diǎn)3的度是（

）。

A:2B:1C:3D:0

答案:3已知有向圖的頂點(diǎn)集合U={1,2,3,4},弧的集合TE={<1,2>,<1,3>,<2,3>,<3,4>}，則該有向圖的拓?fù)渑判蛐蛄惺牵?/p>

）。

A:1234B:1324C:4321D:1423

答案:1234圖的深度優(yōu)先遍歷序列（

）。

A:無B:不存在C:可以有多個(gè)D:只有一個(gè)

答案:可以有多個(gè)拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有（

）個(gè)前驅(qū)頂點(diǎn)的過程來完成的。

A:3

B:1C:0D:2

答案:0n個(gè)頂點(diǎn)e條邊的圖采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為（

）。

A:O(n+e)

B:O(n)

C:O(n2)D:O(e)

答案:O(n+e)

n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，該算法的時(shí)間復(fù)雜度為（

）。

A:O(n)

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

答案:O(n2)

第八章單元測(cè)試

在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為（

）。

A:ＡＳＬ＝（ｎ＋１）／２B:ＡＳＬ＝ｎC:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１D:

答案:ＡＳＬ＝（ｎ＋１）／２有一個(gè)有序表（1，3，9，12，32，41，45，62，75，77，82，95，100），當(dāng)折半查找有序表中值為82的結(jié)點(diǎn)時(shí)，則它與表元素中比較了（

）次后查找成功。

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

答案:4采用折半查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（

）。

A:O(n)B:O(n2)C:O(nlog2n)D:O(log2n)

答案:O(log2n)鏈表適用于以下（

）查找

A:二分法B:順序C:隨機(jī)D:順序，也能二分法

答案:順序

順序表查找法適合于以下（

）存儲(chǔ)結(jié)構(gòu)的線性表。

A:順序存儲(chǔ)或鏈接存儲(chǔ)B:索引存儲(chǔ)C:壓縮存儲(chǔ)D:散列存儲(chǔ)

答案:順序存儲(chǔ)或鏈接存儲(chǔ)對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（

）。

A:以順序方式存儲(chǔ)B:以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序C:以鏈接方式存儲(chǔ)D:以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

答案:以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序有一個(gè)長(zhǎng)度為12的有序表，按二分查找對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（

）。

A:35/12B:39/12C:37/12D:43/12

答案:37/12碰撞（沖突）指的是（

）。

A:兩個(gè)元素具有相同序號(hào)B:兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同C:負(fù)載因子過大D:不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址

答案:不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是（

）。

A:順序查找B:分塊查找C:折半查找D:散列查找

答案:散列查找散列法存儲(chǔ)的基本思想是（

）。

A:順序查找B:由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址C:查找與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)D:以順序方式且結(jié)點(diǎn)按關(guān)鍵字有序排序

答案:由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址在散列函數(shù)H(key)=key%p，p應(yīng)?。?/p>

）。

A:整數(shù)B:素?cái)?shù)C:偶數(shù)D:小數(shù)

答案:素?cái)?shù)采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分（

）個(gè)結(jié)點(diǎn)最佳。

A:6B:25C:10D:625

答案:25平衡二叉樹上的平衡因子只能?。?/p>

）。

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

答案:-1,0,1以下對(duì)二叉排序樹的描述不正確的是（

）。

A:二叉排序樹左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值B:中序遍歷一棵二叉樹時(shí)可以得到一個(gè)結(jié)點(diǎn)值遞減的序列C:二叉排序樹右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值

D:左、右子樹也分別是二叉排序樹

答案:中序遍歷一棵二叉樹時(shí)可以得到一個(gè)結(jié)點(diǎn)值遞減的序列

假設(shè)在平衡二叉樹上插入一個(gè)結(jié)點(diǎn)后造成了不平衡，其最近不平衡點(diǎn)為A，且已知A的左子樹的平衡因子為-1，其右子樹的平衡因子為0，應(yīng)該進(jìn)行（

）型調(diào)整可使二叉樹平衡。

A:RRB:RLC:LRD:LL

答案:LR

第九章單元測(cè)試

從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（

）。

A:冒泡排序B:插入排序C:歸并排序D:選擇排序

答案:插入排序從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（

）。

A:冒泡排序B:歸并排序C:選擇排序D:插入排序

答案:選擇排序?qū)個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（

）。

A:O(n2)B:O(n3)C:O(n)D:O(nlog2n)

答案:O(n2)下列關(guān)鍵字序列中，（

）是堆。

A:16，23，53，31，94，72B:16，72，31，23，94，53C:94，23，31，72，16，53D:16，53，23，94，31，72

答案:16，23，53，31，94，72下述幾種排序方法中，（

）是穩(wěn)定的排序方法。

A:快速排序B:歸并排序C:堆排序D:希爾排序

答案:歸并排序在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（

）。

A:選擇排序B:插入排序C:起泡排序D:希爾排序

答案:選擇排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是（

）。

A:選擇排序B:歸并排序C:插入排序D:快速排序

答案:插入排序在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較（

）次。

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

答案:6