數(shù)據(jù)結(jié)構(gòu)知到章節(jié)答案智慧樹2023年黑龍江工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)知到章節(jié)測試答案智慧樹2023年最新黑龍江工程學(xué)院緒論單元測試

（）在其著作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中，開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系。()

參考答案:

唐納德·克努特

（）提出了著名的公式程序=算法+數(shù)據(jù)結(jié)構(gòu)。()

參考答案:

尼古拉斯·沃斯

數(shù)據(jù)結(jié)構(gòu)課程不是（）課程的先修課程。

參考答案:

高級語言程序設(shè)計(jì)

下面哪個(gè)不是常見的數(shù)據(jù)結(jié)構(gòu)。（）

參考答案:

線性方程組

下面說法錯(cuò)誤的是（）。

參考答案:

我國高校從20世紀(jì)50年代就開設(shè)了數(shù)據(jù)結(jié)構(gòu)這一課程

第一章測試

（）是組成數(shù)據(jù)具有獨(dú)立含義不可分割的最小單位。()

參考答案:

數(shù)據(jù)項(xiàng)

數(shù)據(jù)邏輯結(jié)構(gòu)中非線性結(jié)構(gòu)包括（）。

參考答案:

樹形結(jié)構(gòu)和圖形結(jié)構(gòu)

設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={＜01，02＞，＜01，03＞，＜01，04＞，＜02，05＞，＜02，06＞，＜03，07＞，＜03，08＞，＜03，09＞}，則數(shù)據(jù)結(jié)構(gòu)A是（）。

參考答案:

樹形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容包括數(shù)據(jù)的（）以及數(shù)據(jù)的運(yùn)算和操作。

參考答案:

邏輯結(jié)構(gòu)、物理結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)被形象化的定義為一個(gè)二元組Group=（D，S），其中D為數(shù)據(jù)元素的有限集，S為（）的有限集。

參考答案:

關(guān)系

線性結(jié)構(gòu)中的數(shù)據(jù)元素具有（）關(guān)系。

參考答案:

一對一關(guān)系

對一個(gè)算法的評價(jià)，不包括如下（）方面的內(nèi)容。

參考答案:

并行性

下列時(shí)間復(fù)雜度中最好的是（）。

參考答案:

O（log2n）

以下算法的時(shí)間復(fù)雜度是（）。i=1;while(i＜=n)i=i*3;

參考答案:

O（log3n）

以下算法:s=0;for(i=0;i＜n;i++)

for(j=0;j＜n;j++)s=s+a[i][j];printf("%d\n",sum);的時(shí)間復(fù)雜度為（)

參考答案:

O（n^2）

第二章測試

下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）

參考答案:

線性表采用順序存儲，便于插入和刪除操作

如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲方式最節(jié)省時(shí)間。

參考答案:

順序表

線性表采用順序存儲時(shí)，存儲地址（）。

參考答案:

必須是連續(xù)的

線性表采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)的存儲地址（）。

參考答案:

連續(xù)與否均可

帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）

參考答案:

head-＞next==NULL

設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（）。

參考答案:

p-＞next=p-＞next-＞next

在一個(gè)長度為n（n＞1）的單鏈表上，設(shè)有頭指針和尾指針，執(zhí)行（）操作與鏈表的長度有關(guān)。

參考答案:

刪除單鏈表中的最后一個(gè)元素

若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲方式最節(jié)省運(yùn)算時(shí)間。

參考答案:

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

在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。

參考答案:

p-＞prior-＞next=p-＞next;p-＞next-＞prior=p-＞prior;

建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為（）

參考答案:

O(n^2)

第三章測試

若讓元素C，h，i，n，a依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。

參考答案:

n，i，C，h，a

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

參考答案:

n-i+1

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

參考答案:

棧

若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧（i=1,2）棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是（）

參考答案:

top[1]+1=top[2]

為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。

參考答案:

隊(duì)列

用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)()。

參考答案:

頭、尾指針可能都要修改

棧和隊(duì)列的共同點(diǎn)是（）。

參考答案:

只允許在端點(diǎn)處插入和刪除元素

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

參考答案:

3

循環(huán)隊(duì)列存儲在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。

參考答案:

rear=(rear+1)%(m+1)

遞歸過程或者函數(shù)調(diào)用時(shí)處理參數(shù)和返回地址需要用到（）數(shù)據(jù)結(jié)構(gòu)。

參考答案:

棧

第四章測試

串是一種特殊的線性表，其特殊性體現(xiàn)在（）。

參考答案:

數(shù)據(jù)元素是一個(gè)字符

若串S=“master”其子串的個(gè)數(shù)是（）。

參考答案:

22

串的長度是指（）。

參考答案:

串中所含字符的個(gè)數(shù)

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

參考答案:

匹配

數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（）。

參考答案:

45

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

參考答案:

818

設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲首地址為（）。

參考答案:

BA+180

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

參考答案:

33

廣義表((a,b,c,d))的表頭是（）。

參考答案:

(a,b,c,d)

廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（）。

參考答案:

d

第五章測試

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

參考答案:

5

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

參考答案:

501

一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。

參考答案:

11至1025之間

對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）遍歷實(shí)現(xiàn)編號。

參考答案:

后序

已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（）。

參考答案:

CBEFDA

引入二叉線索樹的目的是（）。

參考答案:

加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度

在下列存儲形式中，（）不是樹的存儲形式？

參考答案:

順序存儲表示法

利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）。

參考答案:

空

設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。

參考答案:

n+1

設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。

參考答案:

100

第六章測試

具有4個(gè)頂點(diǎn)的無向完全圖有（）條邊。

參考答案:

6

具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。

參考答案:

5

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

參考答案:

2

任何一個(gè)無向連通圖的最小生成樹（）。

參考答案:

有一棵或多棵

設(shè)無向圖G=（V，E），G'=（V'，E'），如果G'是G的生成樹，則下面說法錯(cuò)誤的是（）。

參考答案:

null

無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定不是對稱矩陣。（）

參考答案:

錯(cuò)

某無向圖G=（V，E），其中：V=（a,b,c,d,e,f），E=（(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)），對該圖進(jìn)行深度優(yōu)先遍歷，則頂點(diǎn)序列正確的是（）。

參考答案:

a,e,d,f,c,b

已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6},E={＜v1,v2＞,＜v1,v4＞,＜v2,v6＞,

＜v3,v1＞,＜v3,v4＞,＜v4,v5＞,＜v5,v2＞,＜v5,v6＞},G的拓?fù)湫蛄惺牵ǎ?/p>

參考答案:

v3,v1,v4,v5,v2,v6

關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。

參考答案:

從源點(diǎn)到匯點(diǎn)的最長路徑

普里姆算法是一種通過選點(diǎn)法構(gòu)造最小生成樹的算法。時(shí)間復(fù)雜度為（）。

參考答案:

O（n^2）

第七章測試

有一個(gè)長度為12的有序表，按折半查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率的情況下查找成功所需的平均比較次數(shù)為（）。

參考答案:

37/12

對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè)，

參考答案:

4

順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。

參考答案:

O(n)

設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。

參考答案:

2

設(shè)某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。

參考答案:

97

設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（）。

參考答案:

4

二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。

參考答案:

＜

從n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，最壞情況下時(shí)間復(fù)雜度為（）。

參考答案:

O(n)

在平衡二叉樹中，每個(gè)結(jié)點(diǎn)平衡因子的絕對值必須（）。

參考答案:

小于等于1

深度為4的平衡二叉樹中至少有（）個(gè)結(jié)點(diǎn)。

參考答案:

7

第八章測試

用某種排序方法對線性表{25,84,21,47,15,27,68,35,20}進(jìn)行排序時(shí)，元素序列的變化情況如下：

（1）25，84，21，47，15，27，68，35，20

（2）20，15，21，25，47，27，68，35，84

（3）15，20，21，25，35，27，47，68，84

（4）15，20，21，25，27，35，47，68，84

則采用的排序方法是（）。

參考答案:

快速排序

對記錄的關(guān)鍵字為｛51,26,38,80,70,90,8,30,40,20｝進(jìn)行排序，各趟排序結(jié)束時(shí)的結(jié)果為：

（1）51，26，38，80，70，90，8，30，40，20

（2）51，8，30，40，20，90，26，38，80，70

（3）26，8，30，40，20，80，51，38，90，70

（4）8，20，26，30，38，40，51，70，80，90

則采用的排序方法是（）。

參考答案:

希爾排序

設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。

參考答案:

3，2，5，6，8

下列四種排序中（）的空間復(fù)雜度最大。

參考答案:

歸并排序

快速排序的空間復(fù)雜度為（）。

參考答案:

O(log2n)

下面哪種排序算法是穩(wěn)定的排序算法（）。

參考答案:

歸并排序

下面哪種排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（）

參考答案:

快速排序

設(shè)一組初始記錄關(guān)鍵字序列為(