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