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

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

下述幾種排序方法中，要求內(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個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是()

A.0(n)

B.0(n2)

C.0(nlog2n)

D.0(n3)

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

是()

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.不能確定

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

A.棧

B.隊(duì)列

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ù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)

序列是()

C.0321

D.0123

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

A.1/2

B.1

C.2

D.4

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

列是0

0111101

1001001

1000100

1100110

1011010

0001101

1100010

A.0243156

B.0136542

C.0423165

D.0361542

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

中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有()個

A.n-1

B.n

C.n+1

D.n+2

線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址0

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

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

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

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

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

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

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

A.棧

B.隊(duì)列

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)的位置的運(yùn)算稱作()

A.連接

B.模式匹配

C.求子串

D.求串長

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

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

A.希爾排序

B.冒泡排序

C.插入排序

D.選擇排序

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

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é)點(diǎn)的無向圖最多有()條邊

A.14

28

BC.

56

D.112

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

是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.可以鏈?zhǔn)酱鎯?/p>

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

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

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

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

A.從小到大排列好的

B.從大到小排列好的

C.元素?zé)o序

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)既可以是棧，也可以是隊(duì)列，也可以是線性表。

0

A.正確

B.錯誤

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

A.正確

B.錯誤

鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個結(jié)點(diǎn)后，計(jì)算機(jī)會自動地將后續(xù)

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

1個結(jié)點(diǎn)。（）

A.正確

B.錯誤

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

A.正確

B.錯誤

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

空指針域。（）

A.正確

B.錯誤

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

A.正確

B.錯誤

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

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

A.正確

B.錯誤

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

A.正確

B.錯誤

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

A.正確

B.錯誤

隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(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

參考答