22秋學(xué)期（高起本1709-1803、全層次1809-2103）《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)-00002
試卷總分:100 得分:100
一、單選題 (共 30 道試題,共 60 分)
1.鏈表適用于()查找
A.順序
B.二分法
C.順序，也能二分法
D.隨機(jī)
2.引入二叉線索樹(shù)的目的是（ ）
A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度
B.為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除
C.為了能方便的找到雙親
D.使二叉樹(shù)的遍歷結(jié)果唯一
3.棧中元素的進(jìn)出原則是（）
A.先進(jìn)先出
B.后進(jìn)先出
C.?？談t進(jìn)
D.棧滿則出
4.堆是一種()排序。
A.插入
B.選擇
C.交換
D.歸并
5.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是（）
A.QU->rear － QU->front = = m0
B.QU->rear － QU->front －1= = m0
C.QU->front = = QU->rear
D.QU->front = = QU->rear+1
6.有8個(gè)結(jié)點(diǎn)的有向完全圖有（）條邊
A.14
B.28
C.56
D.112
7.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。
A.1/2
B.1
C.2
D.4
8.對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。()
A.從小到大排列好的
B.從大到小排列好的
C.元素?zé)o序
D.元素基本有序
9.下述幾種排序方法中，要求內(nèi)存最大的是()
A.插入排序
B.快速排序
C.歸并排序
D.選擇排序
10.堆的形狀是一棵()
A.二叉排序樹(shù)
B.滿二叉樹(shù)
C.完全二叉樹(shù)
D.平衡二叉樹(shù)
11.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為()
A.希爾排序
B.冒泡排序
C.插入排序
D.選擇排序
12.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有（）條邊
A.5
B.6
C.7
D.8
13.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）
A.必須是連續(xù)的
B.部分地址必須是連續(xù)的
C.一定是不連續(xù)的
D.連續(xù)或不連續(xù)都可以
14.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）
{圖}
A.0 3 2 1
B.0 1 2 3
C.0 1 3 2
D.0 3 1 2
15.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中()比較大小，查找結(jié)果是失敗。
A.20，70，30，50
B.30，88，70，50
C.20，50
D.30，88，50
16.將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較()次
A.8
B.9
C.10
D.25
17.串是一種特殊的線性表，其特殊性體現(xiàn)在（）
A.可以順序存儲(chǔ)
B.數(shù)據(jù)元素是一個(gè)字符
C.可以鏈?zhǔn)酱鎯?chǔ)
D.數(shù)據(jù)元素可以是多個(gè)字符
18.判定一個(gè)棧ST（最多元素為m0）為空的條件是（）
A.ST->top<>0
B.ST->top=0
C.ST->top<>m0
D.ST->top=m0
19.不含任何結(jié)點(diǎn)的空樹(shù)（）
A.是一棵樹(shù)
B.是一棵二叉樹(shù)
C.是一棵樹(shù)也是一棵二叉樹(shù)
D.既不是樹(shù)也不是二叉樹(shù)
20.已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）
{圖}
A.0 2 4 3 1 6 5
B.0 1 3 5 6 4 2
C.0 1 2 3 4 6 5
D.0 1 2 3 4 5 6
21.折半搜索與二叉搜索樹(shù)的時(shí)間性能()
A.相同
B.完全不同
C.有時(shí)不相同
D.數(shù)量級(jí)都是O（log2n）
22.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為()
A.存儲(chǔ)結(jié)構(gòu)
B.邏輯結(jié)構(gòu)
C.順序存儲(chǔ)結(jié)構(gòu)
D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
23.設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的結(jié)果串是（）
A.BCDEF
B.BCDEFG
C.BCPQRST
D.BCDEFEF
24.已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為()
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
25.設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有()個(gè)
A.n-1
B.n
C.n+1
D.n+2
26.在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為（ ）
A.ＡＳＬ＝ｎ
B.ＡＳＬ＝（ｎ＋１）／２
C.{圖}
D.{圖}
27.下列關(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
28.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）
{圖}
A.0 1 3 2
B.0 2 3 1
C.0 3 2 1
D.0 1 2 3
29.廣度優(yōu)先遍歷類似于二叉樹(shù)的()
A.先序遍歷
B.中序遍歷
C.后序遍歷
D.層次遍歷
30.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）倍
A.1/2
B.1
C.2
D.4
二、判斷題 (共 20 道試題,共 40 分)
31.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。
32.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。
33.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。
34.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1。
35.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表
36.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。
37.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。
38.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。
39.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。
40.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。
41.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。
42.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子樹(shù)。
43.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。
44.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。
45.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。
46.線性表的邏輯順序與存儲(chǔ)順序總是一致的。
47.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。
48.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。
49.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。
50.若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n—1個(gè)非空指針域。
奧鵬，國(guó)開(kāi)，廣開(kāi)，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請(qǐng)咨詢QQ : 3230981406或微信:aopopenfd777
