20秋電子科技大學《數據結構》在線作業2答卷

下面程序段的時間復雜度為()。for(i=0;iA.0(n2)

B.0(m2)

C.0(m+n)

D.0(m*n)

已知一棵完全二叉樹有64個葉子結點，則該樹可能達到的最大深度為()。

A.9

B.8

C.7

D.10

數據結構是()。

A.相互之間存在一種或多種特定關系的數據元素的集合

B.數據的存儲結構

C.一組性質相同的數據元素的集合

D.一種數據類型

若線性表的插入和刪除操作頻繁地在表頭或表尾位置進行，則更適宜采用的存

儲結構為()。

A.無頭結點的雙向鏈表

B.無頭結點的單鏈表

C.帶尾指針的循環鏈表

D.帶頭指針的循環鏈表

從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需0。

A.視情況而定

B.后移一個位置

C.前移一個位置

D.不動

對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進行的操作為()。

A.深度優先遍歷

B.求一個頂點的鄰接點

C.求一個頂點的度

D.廣度優先遍歷

在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜

度是()。

A.O(nlogn)

B.0(n2)

C.0(n)

D,0(1)

一棵含18個結點的二叉樹的高度至少為0。

A.6

B.5

C.4

D.3

算法分析的目的是0。

A.鑒別算法的可讀性

B.辨別數據結構的合理性

C.評價算法的效率

D.研究算法中輸入與輸出的關系

高度為5的完全二叉樹中含有的結點數至少為()。

A.32

B.31

C.17

D.16

已知函數Sub(s,i,j)的功能是返回串s中從第i個字符起長度為j的子串，

函數Scopy(s,t)的功能為復制串t到s。若字符串S="SCIENCESTUDY"，則

調用函數Scopy(P,Sub(S,1,7))后得到()。

A.S="STUDY”

B.S="SCIENCE”

C.P="STUDY”

D.P="SCIENCE”

設有兩個串T和P,求P在T中首次出現的位置的串運算稱作()。

A.聯接

B.求子串

C.字符定位

D.子串定位

棧是一種操作受限的線性結構，其操作的主要特征是0。

A.進優于出

B.后進先出

C.出優于進

D.先進先出

采用兩類不同存儲結構的字符串可分別簡稱為()。

A.順序串和鏈串

B.目標串和模式串

C.變量串和常量串

D.主串和子串

設串sl="DataStructureswithJava",s2="it”,則子串定位函數

index(si,s2)的值為()。

A.18

B.17

C.16

D.15

在頭指針為head且表長大于1的單循環鏈表中，指針p指向表中某個結點，若

p->next->next=head,貝U()。

A.*p的直接后繼是頭結點

B.p指向尾結點

C.p指向頭結點

D.*P的直接后繼是尾結點

數據的邏輯結構通常包括0。

A.集合

B.線性

C.樹

D.圖

通用的處理哈希沖突的方法有()。

A.鏈地址法

B.開放定址法

C.建立公共溢出區

D.再哈希法

若進棧序列為a,b,c,且進棧和出棧可以穿插進行，則可能出現6個不同的

出棧序列。()

A.正確

B.錯誤

在二叉樹的第i層上至多可以有2i個結點。。

A.正確

B.錯誤

給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。0

A.正確

B.錯誤

數據的邏輯結構在計算機存儲器內的表示，稱為數據的邏輯結構。()

A.正確

B.錯誤

隊列的修改是按先進先出的原則進行的。（）

A.正確

B.錯誤

數據的邏輯結構描述數據元素之間的邏輯關系，與存儲方式無關。（）

A.正確

B.錯誤

如果入棧序列是1,3,5,97,99,且出棧序列的第一個元素為99,則出

棧序列中第30個元素為47。（）

A.正確

B.錯誤

在一個長度為100的順序表中刪除第10個元素時，需移動90個元素。（）

A.正確

B.錯誤

二叉樹中必有度為2的結點。（）

A.正確

B.錯誤

有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第i列的元素個數。（）

A.正確

B.錯誤

二叉樹是度為2的有序樹。（）

A.正確

B.錯誤

參考答案：B

兩個串相等的充分必要條件是兩個串的長度相等且字母相同。（）

A.正確

B.錯誤

若鏈串結點中的指針占4個字節，每個字符占1個字節，則結點大小為2的鏈

串的存儲密度為2/6。（）

A.正確

B.錯誤

二叉樹中的葉子結點就是二叉樹中沒有左右子樹的結點。（）

A.正確

B.錯誤

不含任何字符的串稱為空串。（）

A.正確

B.錯誤

在隊列中，允許進行刪除操作的一端稱為隊尾。（）

A.正確

B.錯誤

在有向圖中，以頂點v為終點的邊的數目稱為v的入度。（）

A.正確

B.錯誤

字符串“sgabacbadfgbacst”中存在有6個與字符串"ba”相同的子串。（）

A.正確

B.錯誤

在文本編輯程序中查找某一特定單詞在文本中出現的位置，可以利用串的定位

操作。（）

A.正確

B.錯誤

二叉樹中結點只有一個孩子時無左右之分。（）

A.正確

B.錯誤

在一個長度為n的循環鏈表中，刪除其元素值為x的結點的時間復雜度為0（n）。

0

A.正確

B.錯誤

在最好和最壞情況下的時間復雜度均為O（nlogn）且穩定的排序方法是堆排序。

0

A.正確

B.錯誤

參考答案：D

參考答案：C

參考答案：A

參考答案：C

參考答案：c

參考答案：c

參考答案：C

參考答案：B

參考答案：C

參考答案：D

參考答案：D

參考答案：D

參考答案：B

參考答案：A

參考答案：A

參考答案：D

參考答案：ABCD

參考答案：ABCD

參考答案：B

參考答案：B

參考答案：B

參考答案：B

參考答案：A

參考答案：A

參考答案：A