數(shù)據(jù)結(jié)構(gòu)智慧樹(shù)知到課后章節(jié)答案2023年下大慶師范學(xué)院

數(shù)據(jù)結(jié)構(gòu)智慧樹(shù)知到課后章節(jié)答案2023年下大慶師范學(xué)院大慶師范學(xué)院

第一章測(cè)試

在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。

A:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

B:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C:線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

答案:線性結(jié)構(gòu)和非線性結(jié)構(gòu)

在數(shù)據(jù)結(jié)構(gòu)中,從存儲(chǔ)結(jié)構(gòu)上可以將之分為()。

A:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C:順序存儲(chǔ)和非順序存儲(chǔ)

D:線性結(jié)構(gòu)和非線性結(jié)構(gòu)

答案:順序存儲(chǔ)和非順序存儲(chǔ)

某算法的時(shí)間復(fù)雜度是O(n^2),表明該算法的()。

A:執(zhí)行時(shí)間等于n^2

B:執(zhí)行時(shí)間與n^2成正比

C:問(wèn)題規(guī)模與n^2成正比

D:問(wèn)題規(guī)模是n^2

答案:執(zhí)行時(shí)間與n^2成正比

在下面的程序段中,x=x+1;的語(yǔ)句頻度為()。for(i=1;i＜=n;i++)for(j=1;j＜=n;j++)x=x+1;

A:O(2n)

B:O(n)

C:O(log2n)

D:O(n^2)

答案:O(n^2)

數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（）

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

答案:對(duì)

第二章測(cè)試

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

A:單循環(huán)鏈表

B:帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

C:順序表

D:雙鏈表

答案:順序表

設(shè)某順序表中第一個(gè)元素的地址是se(下標(biāo)從1開(kāi)始),每個(gè)結(jié)點(diǎn)占m個(gè)單元,則第i個(gè)結(jié)點(diǎn)的地址為()。

A:se-i×m

B:se+(i+1)×m

C:se+(i-1)×m

D:se+i×m

答案:se+(i-1)×m

在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn),正確的操作是()。

A:s-＞next=p-＞next;p-＞next=s;

B:p-＞next=s;s-＞next=p-＞next;

C:p-＞next=s-＞next;p-＞next=s;

D:p-＞next=s;p-＞next=s-＞next;

答案:s-＞next=p-＞next;p-＞next=s;

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（）

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

答案:對(duì)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。

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

答案:對(duì)

第三章測(cè)試

若串S='software',其前綴真子串的數(shù)目是()。

A:8

B:10

C:9

D:7

答案:7

設(shè)有兩個(gè)串p和q,其中q是p的子串,求q在p中首次出現(xiàn)的位置的算法稱為()。

A:串聯(lián)接

B:串的模式匹配

C:求串長(zhǎng)

D:求子串

答案:串的模式匹配

若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）

A:i

B:其余選項(xiàng)都不對(duì)

C:n=i

D:n-i+1

答案:n-i+1

棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（）

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

答案:對(duì)

若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（

）存儲(chǔ)方式最節(jié)省時(shí)間。

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

答案:順序表

第四章測(cè)試

棧和隊(duì)列都是()。

A:限制存取點(diǎn)的線性結(jié)構(gòu)

B:鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)

C:限制存取點(diǎn)的非線性結(jié)構(gòu)

D:順序存儲(chǔ)的線性結(jié)構(gòu)

答案:限制存取點(diǎn)的線性結(jié)構(gòu)

設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5和e6依次通過(guò)棧S,一個(gè)元素出棧后隨即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該是()。

A:2

B:6

C:3

D:4

答案:3

表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。

A:abc*+d-

B:cb+a*d-

C:abc+*d-

D:abcd+*-

答案:abc+*d-

對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度和在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度分別為()。

A:O(n),O(n)

B:O(1),O(n)

C:O(1),O(1)

D:O(n),O(1)

答案:O(1),O(n)

在對(duì)不帶頭結(jié)點(diǎn)的鏈隊(duì)列作出隊(duì)操作時(shí),不會(huì)改變頭指針的值。（）

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

答案:錯(cuò)

第五章測(cè)試

假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1...100,1...100],設(shè)每個(gè)數(shù)組元素占2個(gè)存儲(chǔ)單元,基地址為10,則LOC[5,5]=()。

A:808

B:818

C:1020

D:1010

答案:818

某二叉樹(shù)的后序遍歷序列于先序遍歷序列正好相反，則該二叉樹(shù)一是（）

A:空或只有一個(gè)結(jié)點(diǎn)

B:高度等于其結(jié)點(diǎn)數(shù)

C:二叉排序樹(shù)

D:完全二叉樹(shù)

答案:高度等于其結(jié)點(diǎn)數(shù)

設(shè)廣義表L=((a,b,c)),則L的長(zhǎng)度和深度分別為()。

A:1和3

B:1和1

C:1和2

D:1和4

答案:1和3

下列陳述中正確的是（）

A:二叉樹(shù)是度為2的有序樹(shù)

B:二叉樹(shù)中必有度為2的結(jié)點(diǎn)

C:二叉樹(shù)中最多只有兩棵子樹(shù)，且有左右之分

D:二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分

答案:二叉樹(shù)中最多只有兩棵子樹(shù)，且有左右之分

二叉樹(shù)的左右子樹(shù)可以任意交換。（）

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

答案:錯(cuò)

第六章測(cè)試

樹(shù)最適合用來(lái)表示的結(jié)構(gòu)是()。

A:元素間無(wú)聯(lián)系的結(jié)構(gòu)

B:元素間的無(wú)序結(jié)構(gòu)

C:元素間具有分支及層次關(guān)系的結(jié)構(gòu)

D:元素間的有序結(jié)構(gòu)

答案:元素間具有分支及層次關(guān)系的結(jié)構(gòu)

任意一棵二叉樹(shù)的葉子結(jié)點(diǎn)在其先序、中序、后序序列中的相對(duì)位置()。

A:有時(shí)發(fā)生變化

B:無(wú)法確定

C:肯定發(fā)生變化

D:肯定不發(fā)生變化

答案:肯定不發(fā)生變化

以數(shù)據(jù)集{4,5,6,7,10,12,18}為葉結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù),其帶權(quán)路徑長(zhǎng)度為()。

A:165

B:155

C:160

D:170

答案:165

已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn),3個(gè)度為2的結(jié)點(diǎn),4個(gè)度為3的結(jié)點(diǎn),則該樹(shù)中有()個(gè)葉子結(jié)點(diǎn)。

A:10

B:13

C:12

D:11

答案:12

滿二叉樹(shù)一定完全是二叉樹(shù)。（）

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

答案:對(duì)

第七章測(cè)試

一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有()邊。

A:n

B:n(n-1)

C:n(n-1)/2

D:2n

答案:n(n-1)/2

對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則占用的存儲(chǔ)空間為()。

A:e

B:n+2e

C:n+e

D:2e

答案:n+2e

一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（）

A:n-1

B:n

C:nlogn

D:n+1

答案:n-1

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

A:1、2

B:1/2、1

C:4、2

D:2、1

答案:2、1

圖的深度優(yōu)先遍歷序列不是唯一的。（）

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

答案:對(duì)

第八章測(cè)試

如果要求用線性表既能較快地查找,又能適應(yīng)動(dòng)態(tài)變化的要求,則可采用()查找方法。

A:折半查找

B:順序查找

C:分塊查找

D:基于屬性

答案:分塊查找

已知一如下10個(gè)記錄的表,其關(guān)鍵字序列為(2,15,19,25,30,34,44,55,58,80),用折半查找法查找關(guān)鍵字為55的記錄,比較次數(shù)是()。

A:3次

B:1次

C:4次

D:2次

答案:2次

如果按關(guān)鍵碼值遞增的順序依次將99個(gè)關(guān)鍵碼值插入到二叉排序樹(shù)中,則對(duì)這樣的二叉排序樹(shù)檢索時(shí),在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度ASL為()。

A:48

B:45

C:47

D:50

答案:50

對(duì)包含n個(gè)元素的散列表進(jìn)行查找,平均查找長(zhǎng)度為()。

A:O(n)

B:O(log2n)

C:不直接依賴于n

D:O(n2)

答案:不直接依賴于n

Hash表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。（）

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

答案:錯(cuò)

第九章測(cè)試

有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序的篩選方法建立的初始小根堆為()。

A:-1,4,8,9,20,7,15,7

B:-1,7,15,7,4,8,20,9

C:A,B,C均不對(duì)。

D:-1,4,7,8,20,15,7,9

答案:-1,4,7,8,20,15,7,9

一組記錄的關(guān)鍵字為(46,79,56,38,40,84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。

A:(40,38,46,56,79,84)

B:(40,38,46,79,56,84)

C:(38,40,46,56,79,84)

D:(40,38,46,84,56,79)

答案:(40,38,46,56,79,84)

對(duì)序列{15,9,7,8,20,-1,4}進(jìn)行排序,進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)閧9,15,7,8,20,-