23秋學期（僅限-高起專1909、專升本1909）《數(shù)據(jù)結構》在線作業(yè)-00001
試卷總分:100 得分:100
一、單選題 (共 30 道試題,共 60 分)
1.設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有()個
A.n-1
B.n
C.n+1
D.n+2
2.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為()
A.希爾排序
B.冒泡排序
C.插入排序
D.選擇排序
3.鏈接存儲的存儲結構所占存儲空間（）
A.分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針
B.只有一部分，存放結點值
C.只有一部分，存儲表示結點間關系的指針
D.分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)
4.一棵具有 n個結點的完全二叉樹的樹高度（深度）是（ ）
A.{圖}
B.{圖}
C.{圖}
D.{圖}
5.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的
A.棧
B.隊列
C.樹
D.圖
6.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中()比較大小，查找結果是失敗。
A.20，70，30，50
B.30，88，70，50
C.20，50
D.30，88，50
7.已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結點序列是（）
{圖}
A.0 2 4 3 6 5 1
B.0 1 3 6 4 2 5
C.0 4 2 3 1 5 6
D.0 1 3 4 2 5 6
8.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（）
{圖}
A.0 1 3 2
B.0 2 3 1
C.0 3 2 1
D.0 1 2 3
9.在n個結點的順序表中，算法的時間復雜度是O（1）的操作是（）
A.訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅(qū)（2≤i≤n）
B.在第i個結點后插入一個新結點（1≤i≤n）
C.刪除第i個結點（1≤i≤n）
D.將n個結點從小到大排序
10.二叉樹是非線性數(shù)據(jù)結構，所以（）
A.它不能用順序存儲結構存儲
B.它不能用鏈式存儲結構存儲
C.順序存儲結構和鏈式存儲結構都能存儲
D.順序存儲結構和鏈式存儲結構都不能使用
11.快速排序在下列哪種情況下最易發(fā)揮其長處()
A.被排序的數(shù)據(jù)中含有多個相同排序碼
B.被排序的數(shù)據(jù)已基本有序
C.被排序的數(shù)據(jù)完全無序
D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊
12.深度優(yōu)先遍歷類似于二叉樹的()
A.先序遍歷
B.中序遍歷
C.后序遍歷
D.層次遍歷
13.鏈表是一種采用 存儲結構存儲的線性表
A.順序
B.鏈式
C.星式
D.網(wǎng)狀
14.對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是()
A.O(n)
B.O(n2)
C.O(nlog2n)
D.O(n3)
15.線性表Ｌ在（）情況下適用于使用鏈式結構實現(xiàn)。
A.需經(jīng)常修改Ｌ中的結點值
B.需不斷對Ｌ進行刪除插入
C.Ｌ中含有大量的結點
D.Ｌ中結點結構復雜
16.用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用()來實現(xiàn)算法的
A.棧
B.隊列
C.樹
D.圖
17.下列關鍵字序列中，()是堆
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
18.將5個不同的數(shù)據(jù)進行排序，至多需要比較()次
A.8
B.9
C.10
D.25
19.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。
A.1/2
B.1
C.2
D.4
20.線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（）
A.必須是連續(xù)的
B.部分地址必須是連續(xù)的
C.一定是不連續(xù)的
D.連續(xù)或不連續(xù)都可以
21.廣度優(yōu)先遍歷類似于二叉樹的()
A.先序遍歷
B.中序遍歷
C.后序遍歷
D.層次遍歷
22.串是一種特殊的線性表，其特殊性體現(xiàn)在（）
A.可以順序存儲
B.數(shù)據(jù)元素是一個字符
C.可以鏈式存儲
D.數(shù)據(jù)元素可以是多個字符
23.數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為
A.r－f
B.（n＋f－r）% n
C.n＋r－f
D.（n＋r－f）% n
24.任何一個無向連通圖的最小生成樹()
A.只有一棵
B.一棵或多棵
C.一定有多棵
D.可能不存在
25.堆的形狀是一棵()
A.二叉排序樹
B.滿二叉樹
C.完全二叉樹
D.平衡二叉樹
26.對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。()
A.從小到大排列好的
B.從大到小排列好的
C.元素無序
D.元素基本有序
27.單鏈表的存儲密度（）
A.大于1
B.等于1
C.小于1
D.不能確定
28.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（）個元素
A.8
B.63.5
C.63
D.7
29.已知一棵二叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果為()
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
30.有8個結點的無向圖最多有（）條邊
A.14
B.28
C.56
D.112
二、判斷題 (共 20 道試題,共 40 分)
31.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。
32.鏈表的每個結點中都恰好包含一個指針。
33.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表
34.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。
35.具有12個結點的完全二叉樹有5個度為2的結點。
36.二叉樹中所有結點個數(shù)是2k-1-1，其中k是樹的深度。
37.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。
38.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。
39.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。
40.順序存儲方式只能用于存儲線性結構。
41.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。
42.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。
43.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。
44.棧和隊列是一種非線性數(shù)據(jù)結構。
45.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。
46.二叉樹中每個結點的兩棵子樹是有序的。
47.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。
48.線性表的邏輯順序與存儲順序總是一致的。
49.鏈表的物理存儲結構具有同鏈表一樣的順序。
50.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i—1個結點。
奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學習
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
