數(shù)據(jù)結(jié)構(gòu)-河南師范大學(xué)中國(guó)大學(xué)mooc課后章節(jié)答案期末考試題庫(kù)2023年

數(shù)據(jù)結(jié)構(gòu)_河南師范大學(xué)中國(guó)大學(xué)mooc課后章節(jié)答案期末考試題庫(kù)2023年試分析下面各程序段的時(shí)間復(fù)雜度。s=0;fori=0;i

參考答案:

O(n2)

試分析下面各程序段的時(shí)間復(fù)雜度。for(i=0;i

參考答案:

O(m*n)

通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。

參考答案:

不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

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

參考答案:

45

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

參考答案:

n+1

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

參考答案:

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

設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（）。

參考答案:

(i-1)*n+j

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

參考答案:

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

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

參考答案:

終止條件和遞歸部分

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

參考答案:

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

最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。

參考答案:

rear==front

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

參考答案:

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

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

參考答案:

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

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

參考答案:

頭、尾指針可能都要修改

廣度優(yōu)先遍歷類似于二叉樹的（）。

參考答案:

層次遍歷

試分析下面各程序段的時(shí)間復(fù)雜度。i=1;while(i<=n)i=i*3;

參考答案:

O(log3n)

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

參考答案:

100

圖的BFS生成樹的樹高比DFS生成樹的樹高（）。

參考答案:

小或相等

已知圖的鄰接矩陣如圖6.30所示，則從頂點(diǎn)v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（）?！緢D片】

參考答案:

0134256

已知圖的鄰接表如圖6.31所示，則從頂點(diǎn)v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（），按深度優(yōu)先遍歷的結(jié)果是（）。

參考答案:

01230123

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

參考答案:

d

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

參考答案:

1和2

下面（）方法可以判斷出一個(gè)有向圖是否有環(huán)。

參考答案:

拓?fù)渑判?/p>

m階B-樹是一棵（）。

參考答案:

m叉平衡排序樹

下面關(guān)于哈希查找的說法，正確的是（）。

參考答案:

不存在特別好與壞的哈希函數(shù)，要視情況而定

下面關(guān)于哈希查找的說法，不正確的是（）。

參考答案:

采用鏈地址法處理沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的

設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測(cè)法解決沖突，則放入的位置是（）。

參考答案:

9

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

參考答案:

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

采用線性探測(cè)法處理沖突，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)的這些位置上的關(guān)鍵字()。

參考答案:

不一定都是同義詞

若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（）。

參考答案:

84，79，56，38，40，46

下述幾種排序方法中，要求內(nèi)存最大的是（）。

參考答案:

歸并排序

下述幾種排序方法中，（）是穩(wěn)定的排序方法。

參考答案:

歸并排序

數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用()算法最節(jié)省時(shí)間。

參考答案:

堆排序

廣義表((a,b,c