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