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