數(shù)據(jù)結(jié)構(gòu)（A）知到章節(jié)答案智慧樹2023年山東理工大學(xué)

數(shù)據(jù)結(jié)構(gòu)（A）知到章節(jié)測(cè)試答案智慧樹2023年最新山東理工大學(xué)第一章測(cè)試

數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（）

參考答案:

錯(cuò)

數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。（）

參考答案:

錯(cuò)

順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）

參考答案:

錯(cuò)

數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

參考答案:

錯(cuò)

邏輯結(jié)構(gòu)是（）關(guān)系的整體。（）

參考答案:

數(shù)據(jù)元素之間邏輯

數(shù)據(jù)結(jié)構(gòu)有（）種基本邏輯結(jié)構(gòu)。（）

參考答案:

4

下列四種基本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（）。

參考答案:

集合

從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。（）

參考答案:

線性結(jié)構(gòu)、非線性結(jié)構(gòu)

for（i=0；i＜n；i++）

c[i][i]=i+i算法的時(shí)間復(fù)雜度是（）。

參考答案:

O(n)

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

參考答案:

O(1)

第二章測(cè)試

對(duì)任何數(shù)據(jù)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）

參考答案:

錯(cuò)

循環(huán)鏈表不是線性表。（）

參考答案:

錯(cuò)

在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的指針即可；因此，單鏈表是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。（）

參考答案:

錯(cuò)

順序存儲(chǔ)的線性表可以隨機(jī)存取。（）

參考答案:

對(duì)

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

參考答案:

head-＞next==NULL

在單鏈表中，一個(gè)結(jié)點(diǎn)有（）個(gè)指針。（）

參考答案:

1

對(duì)于只在表的首尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（）。

參考答案:

用尾指針表示的單循環(huán)鏈表

在一個(gè)以h為頭指針的單循環(huán)鏈中，p指針指向鏈尾的條件是：（）。

參考答案:

p-＞next=h

P和q兩個(gè)指針分別指向雙向循環(huán)鏈表L的兩個(gè)結(jié)點(diǎn)，p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)后繼的條件是（）。

參考答案:

q-＞next==p

設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）最節(jié)省時(shí)間。（）

參考答案:

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

第三章測(cè)試

若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1。（）

參考答案:

對(duì)

兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，相向增長(zhǎng)使用，也存在空間溢出問題。（）

參考答案:

對(duì)

隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（）

參考答案:

錯(cuò)

任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。（）

參考答案:

對(duì)

某棧的輸入序列為a,b，c，d，下面的四個(gè)序列中，不可能是它的輸出序列的是：（）。

參考答案:

d,c，a，b

一個(gè)遞歸算法必須包括：（）。

參考答案:

終止條件和遞歸部分

中綴表達(dá)式A-(B+C／D)*E的后綴形式是：（）。

參考答案:

ABCD／+E*

若用大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。

參考答案:

2和4

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

參考答案:

棧

經(jīng)過(guò)InitStack（S）；Push（S，a）；Push（S，b）；Pop（S，x）；Pop（S，x）；的運(yùn)算后EmptyStack（S）的值是（）。

參考答案:

1

第四章測(cè)試

KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的整型指針值不會(huì)減小。（）

參考答案:

對(duì)

設(shè)有兩個(gè)串P和Q，其中Q是P的子串，把Q在P中首次出現(xiàn)的位置作為子串Q在P中的位置的算法稱為模式匹配。（）

參考答案:

對(duì)

INDEX（‘DATASTRUCTURE’，‘STR’）=4。（）

參考答案:

錯(cuò)

空串是零個(gè)字符的串，其長(zhǎng)度等于零。（）

參考答案:

對(duì)

已知U=‘xyxyxyxxyxy’；t=‘xxy’；

ASSIGN（S，U）；

ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；

ASSIGN（m，‘ww’）

求REPLACE（S，V，m）=‘xyxyxywwy’。（）

參考答案:

對(duì)

設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的KMP算法的時(shí)間復(fù)雜度可達(dá)到O(n+m)。（）

參考答案:

對(duì)

字符串’ababaaab’的nextval函數(shù)值為01010421。（）

參考答案:

對(duì)

串又稱字符串，（）。

參考答案:

串中元素只能是字符

模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（）。

參考答案:

01112231123456712

模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的nextval數(shù)組的值為（）。

參考答案:

01102131011021701

第五章測(cè)試

對(duì)于數(shù)組的操作，最常見的兩種是（）

參考答案:

查找和修改

稀疏矩陣一般的壓縮存儲(chǔ)方法有（）兩種。（）

參考答案:

三元組和十字鏈表

若將n階下三角矩陣A按列優(yōu)先順序壓縮存放在一維數(shù)組B[1...n(n+1)/2+1]中，則存放到B[k]中的非零元素aij(1≤i,j≤n）的下標(biāo)i,j與k的對(duì)應(yīng)關(guān)系是（)。

參考答案:

(j-1)(2n-j+2)/2+i-j+1

有一個(gè)n的對(duì)稱矩陣A，將其下三角部分按行存放在一維數(shù)組B中，而A[0][0存放于B[0]中，則第i行的對(duì)角元素A[i][i]存放于B中的（）處。（）

參考答案:

(i+3)i/2

數(shù)組A中，每個(gè)元素的長(zhǎng)度為3B，行下標(biāo)i從0~7，列下標(biāo)j從0~9，從首地址開始連續(xù)存放在存儲(chǔ)器內(nèi)，則存放該數(shù)組至少需要的單元數(shù)是（）。

參考答案:

240

設(shè)有一個(gè)12×12的對(duì)稱矩陣M，將其上三角部分的元素mi,j(1＜i≤j≤12)按行優(yōu)先存入C語(yǔ)言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是()。

參考答案:

50

已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是()。

參考答案:

head(tail(head(tail(LS)))

廣義表（（a,b,c,d））的表尾是（）。

參考答案:

（a,b,c,d）

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

參考答案:

1和2

下面說(shuō)法不正確的是()。

參考答案:

廣義表的表頭總是一個(gè)廣義表

第六章測(cè)試

一棵有n個(gè)結(jié)點(diǎn)的樹的所有結(jié)點(diǎn)的度數(shù)之和為（）

參考答案:

n-1

對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為4的樹來(lái)說(shuō)，()

參考答案:

樹的高度至多是n-3

假定―棵度為3的樹中，結(jié)點(diǎn)數(shù)為50，則其最小高度為（）

參考答案:

5

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

參考答案:

11~1025

設(shè)一棵非空完全二叉樹T的所有葉結(jié)點(diǎn)均位于同一層，且每個(gè)非葉結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)。若T有k個(gè)葉結(jié)點(diǎn)，則T的結(jié)點(diǎn)總數(shù)是（）

參考答案:

2k-1

在任何一棵二叉樹中，若結(jié)點(diǎn)a有左孩子b、右孩子c，則在結(jié)點(diǎn)的先序序列、中序序列、

后序序列中，()。

參考答案:

結(jié)點(diǎn)b一定在結(jié)點(diǎn)c的前面

若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹的中序遍歷序列不會(huì)是()。

參考答案:

3,2,4,1

某二叉樹的樹形所示，其后序序列為e，a，c，b，d，g，f，樹中與結(jié)點(diǎn)a同層的結(jié)點(diǎn)是（）。

參考答案:

d

所示的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)X的左、右線索指向的結(jié)點(diǎn)分別是（）。

參考答案:

b,a

先序序列為a,b,c,d的不同二叉樹的個(gè)數(shù)是（）。

參考答案:

14

若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。

參考答案:

X的左子樹中最右葉結(jié)點(diǎn)

設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹結(jié)點(diǎn)個(gè)

數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）。

參考答案:

m-n

將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點(diǎn)的個(gè)數(shù)等于()。

參考答案:

T中左孩子指針為空的結(jié)點(diǎn)個(gè)數(shù)

若森林F有15條邊、25個(gè)結(jié)點(diǎn)，則F包含樹的個(gè)數(shù)是（）。

參考答案:

10

n(n≥2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中錯(cuò)誤的是（）。

參考答案:

該樹一定是一棵完全二叉樹

給定整數(shù)集合{3,5,6,9,12}，與之對(duì)應(yīng)的哈夫曼樹是（）

參考答案:

如圖C

對(duì)n個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115個(gè)結(jié)點(diǎn)，則n的值是（）。

參考答案:

58

若將一棵樹T轉(zhuǎn)化為對(duì)應(yīng)的二叉樹BT，則不列對(duì)BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是（）。

參考答案:

中序遍歷

在森林的二叉樹表示中，結(jié)點(diǎn)M和結(jié)點(diǎn)N是同一父結(jié)點(diǎn)的左兒子和右心子，則在該森林中().

參考答案:

M和N可能無(wú)公共祖先

某二叉樹結(jié)點(diǎn)的中序序列為BDAECF，后序序列為DBEFCA，則該二叉樹對(duì)應(yīng)的森林包括（）棵樹。（）

參考答案:

3

第七章測(cè)試

十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（）

參考答案:

錯(cuò)

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

參考答案:

對(duì)

若連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹是唯一的。（）

參考答案:

對(duì)

給定有權(quán)無(wú)向圖的鄰接矩陣如下，其最小生成樹的總權(quán)重是（）。

參考答案:

23

圖中關(guān)于路徑的定義是（）。

參考答案:

由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列。

下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（）

參考答案:

無(wú)向圖

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

參考答案:

1

無(wú)向圖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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。

參考答案:

a,e,d,f,c,b

下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是（）。

參考答案:

一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差。

圖G有n個(gè)頂點(diǎn)，求其最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為（）

參考答案:

O（n3）

第八章測(cè)試

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

參考答案:

對(duì)

哈希表的查找效率主要取決于哈希表造表時(shí)選取的哈希函數(shù)和處理沖突的方法。（）

參考答案:

對(duì)

二叉排序樹的查找和折半查找時(shí)間的性能相同。（）

參考答案:

錯(cuò)

AVL樹是一棵二叉樹．該樹上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于1。（）

參考答案:

對(duì)

散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。（）

參考答案:

對(duì)

折半查找是先確定待查有序表記錄的范圍，然后逐步縮小范圍，直到找到或找不到該記錄為止。（）

參考答案:

對(duì)

若根據(jù)查找表建立長(zhǎng)度為m的閉散列表并采用二次探測(cè)處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的散列地址為d，則第4次計(jì)算的散列地址為（）

參考答案:

(d+4)％m

若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（）

參考答案:

元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)

下面關(guān)于二叉排序樹論述中，錯(cuò)誤的是（）

參考答案:

任一二叉排序樹的平均查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線性表的平均查找時(shí)間

在一棵平衡二叉樹中，每個(gè)結(jié)點(diǎn)的平衡因子取值范圍是（）

參考答案:

-1～l

設(shè)Hash表長(zhǎng)m=14，哈希函數(shù)H(key)=key％11。表中已有4個(gè)結(jié)點(diǎn)，地址分別為：addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其余地址為空。如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是（）。

參考答案:

9

在順序表(n足夠大)中進(jìn)行順序查找，其查找不成功的平均長(zhǎng)度是（）

參考答案:

n+1

在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn)，若查找成功，則平均比較（）個(gè)結(jié)點(diǎn)。

參考答案:

(n+l)/2

第九章測(cè)試

有一小根堆，堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左、右孩子關(guān)鍵字。則其具有最大值的結(jié)點(diǎn)一定是一個(gè)葉結(jié)點(diǎn)并可能在堆的最后兩層中。（）

參考答案:

對(duì)

堆排序所需時(shí)間與待排序記錄的個(gè)數(shù)無(wú)關(guān)。（）

參考答案:

對(duì)

排序算法中的比較次數(shù)與初始元素序列的排列無(wú)關(guān)。（）

參考答案:

錯(cuò)

當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。（）

參考答案:

錯(cuò)

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

參考答案:

錯(cuò)

對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的附加空間數(shù)是。（）

參考答案:

錯(cuò)

下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是：（）。

參考答案:

快速排序

下列排序算法中，（）算法可能會(huì)出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。（）

參考答案:

插入排序

在下列排序算法中,哪一