南開《數(shù)據(jù)結(jié)構(gòu)》20春在線作業(yè)（標準答案）

南開《數(shù)據(jù)結(jié)構(gòu)》20春在線作業(yè)(標準答案)

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

A.插入排序

B.快速排序

C.歸并排序

D.選擇排序

下列關(guān)鍵字序列中，()是堆

A.16,72,31,23,94,53

B.94,23,31,72,16,53

C.16,53,23,94,31,72

D.16,23,53,31,94,72

對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是()

A.0(n)

B.0(n2)

C.0(nlog2n)

D.0(n3)

己知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列

是()

0101

1001001

100000

110010

1011010

000101

00010

A.0243651

B.0136425

C.0423156

D.0134256

折半搜索與二叉搜索樹的時間性能()

A.相同

B.完全不同

C.有時不相同

D.數(shù)量級都是0(log2n)

向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要

移動()個元素

A.8

B.63.5

C.63

D.7

單鏈表的存儲密度()

A.大于1

B.等于1

C.小于1

D.不能確定

用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用()來實現(xiàn)算法的

A.棧

B.隊列

C.樹

D.圖

若已知一個棧的入棧序列是1,2,3,n,其輸出序列為pl,p2,p3,,

pn,若pl=n,則pi為0

A.i

B.n=i

C.n-i+1

D.不確定

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

歷的結(jié)果為()

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不定

任何一個無向連通圖的最小生成樹()

A.只有一棵

B.一棵或多棵

C.一定有多棵

D.可能不存在

己知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點

序列是()

C.0321

D.0123

在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的()倍

A.1/2

B.1

C.2

D.4

己知圖的鄰接矩陣，根據(jù)算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序

列是0

0111101

1001001

1000100

1100110

1011010

0001101

1100010

A.0243156

B.0136542

C.0423165

D.0361542

設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B

中右指針域為空的結(jié)點有()個

A.n-1

B.n

C.n+1

D.n+2

線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址0

A.必須是連續(xù)的

B.部分地址必須是連續(xù)的

c.一定是不連續(xù)的

D.連續(xù)或不連續(xù)都可以

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

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用()來實現(xiàn)算法的

A.棧

B.隊列

C.樹

D.圖

設(shè)串sl='ABCDEFG',s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串,

subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串

s的長度，則con(subs(si,2,len(s2)),subs(si,len(s2),2))的結(jié)果串是

0

A.BCDEF

B.BCDEFG

C.BCPQRST

D.BCDEFEF

設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作()

A.連接

B.模式匹配

C.求子串

D.求串長

排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元

素進行比較，將其放入已排序序列的正確位置上的方法，稱為0

A.希爾排序

B.冒泡排序

C.插入排序

D.選擇排序

在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的()倍

A.1/2

B.1

C.2

D.4

判定一個棧ST(最多元素為mO)為空的條件是()

A.ST->topO

B.ST->top=0

C.ST->topmO

D.ST->top=mO

有8個結(jié)點的無向圖最多有()條邊

A.14

28

BC.

56

D.112

已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按深度優(yōu)先遍歷的結(jié)點序列

是0

011101

100001

100000

110010

1011010

0001101

1100010

A.0243156

B.0135642

C.0423165

D.0134256

從未排序序列中挑選元素，并將其依次插入已排序序列(初始時為空)的一端的

方法，稱為()

A.希爾排序

B.歸并排序

C.插入排序

D.選擇排序

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

A.可以順序存儲

B.數(shù)據(jù)元素是一個字符

C.可以鏈式存儲

D.數(shù)據(jù)元素可以是多個字符

深度優(yōu)先遍歷類似于二叉樹的()

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

對個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）

A.從小到大排列好的

B.從大到小排列好的

C.元素無序

D.元素基本有序

若一組記錄的排序碼為（46,79,56,38,40,84）,則利用堆排序的方法

建立的初始堆為0

A.79,46,56,38,40,84

B.84,79,56,38,40,46

C.84,79,56,46,40,38

D.84,56,79,40,46,38

對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。

0

A.正確

B.錯誤

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

A.正確

B.錯誤

二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。（）

A.正確

B.錯誤

鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。（）

A.正確

B.錯誤

棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先

出型結(jié)構(gòu)。（）

A.正確

B.錯誤

二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。（）

A.正確

B.錯誤

順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。（）

A.正確

B.錯誤

棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（）

A.正確

B.錯誤

鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)

的各個單元向前移動。（）

A.正確

B.錯誤

一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。（）

A.正確

B.錯誤

對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i一

1個結(jié)點。（）

A.正確

B.錯誤

二叉樹中每個結(jié)點的兩棵子樹是有序的。（）

A.正確

B.錯誤

若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n-1個非

空指針域。（）

A.正確

B.錯誤

線性表在物理存儲空間中也一定是連續(xù)的。（）

A.正確

B.錯誤

用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域

中有n+1個為空指針。（）

A.正確

B.錯誤

棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。（）

A.正確

B.錯誤

線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（）

A.正確

B.錯誤

隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)

構(gòu)。（）

A.正確

B.錯誤

順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）

A.正確

B.錯誤

線性表的邏輯順序與存儲順序總是一致的。（）

A.正確

B.錯誤

參考答案：C

參考答案：D

參考答案：B

參考答案：B

參考答案：C

參考答案：B

參考答案：C

參考答案：A

參考答案：C

參考答案：A

參考答案：A

參考答案：D

參考答案：C

參考答案：C

參考答案：C

參考答案：D

參考答