《數(shù)據(jù)結構（?？疲?2年6月課程考核-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 100 分)
1.在一個單鏈表HL中，若要在指針q所指結點的后面插入一個由指針P所指向的結點，則執(zhí)行( )
A.q—＞next＝p—＞next；p—＞next＝q
B.p—＞next＝q—＞next；q＝p
C.q—＞next＝p—＞next；p—＞next＝q
D.p—＞next＝q—＞next；q—＞next＝p
2.下列存儲形式中不是樹的存儲形式( )
A.雙親表示法
B.孩子兄弟表示法
C.順序表示法
D.廣義表表示法
3.假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是（ )
A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)
4.設有向圖有n個頂點和e條邊，采用領接表作為其存儲表示，在進行拓撲排序時，總的計算時間為( )
A.O（nlog2e）
B.O（n+e）
C.O(ne)
D.O(n2)
5.設某算法的問題規(guī)模函數(shù)f(n)=300n2+8000n+900，則它的漸進時間復雜度為（ )
A.O(n3)
B.O(n2)
C.O(n)
D.O(1)
6.對5個不同的數(shù)據(jù)元素進行直接插入排序，最多需要進行（ ）次比較
A.8
B.10
C.15
D.25
7.設有整型二維數(shù)組M[7][6]，每個元素（整數(shù)）占4個存儲單元，元素按行的順序存儲，數(shù)組的起始地址為1000，元素M[5][3]的地址是（ )
A.1032
B.1132
C.1192
D.1232
8.右圖中的拓撲序列為（ )
A.C1，C2，C6，C7，C5，C4，C3
B.C1，C2，C6，C3，C4，C5，C7
C.C1，C4，C2，C3，C5，C6，C7
D.C5，C7，C4，C1，C2，C6，C3
9.AVL樹是一種平衡的二叉排序樹，樹中任一結點的( )
A.左、右子樹的高度均相同
B.左、右子樹高度差的絕對值不超過1
C.左子樹的高度均大于右子樹的高度
D.左子樹的高度均小于右子樹的高度
10.設有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為( )
A.6
B.7
C.8
D.10
11.設數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ）
A.front=front+1
B.front=(front+1)%(m-1)
C.front=(front-1)%m
D.front=(front+1)%m
12.鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是( )
A.插入操作更加方便
B.通常不會出現(xiàn)棧滿的情況
C.不會出現(xiàn)?？盏那闆r
D.刪除操作更加方便
13.線性表是一個具有n個（ ）的有限序列。
A.表元素
B.字符
C.數(shù)據(jù)元素
D.數(shù)據(jù)項
14.深度為8的二叉樹至多有（ ）個結點
A.7
B.15
C.127
D.255
15.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的( )
A.存儲結構
B.邏輯結構
C.算法
D.操作
16.依次在初始為空的隊列中插入元素X，Y，Z，W以后，緊接著作了兩次刪除操作，此時的隊頭元素是（ )
A.X
B.Y
C.Z
D.W
17.一組記錄的關鍵字經(jīng)一趟二路歸并排序后得到含有5個長度為2的有序表如下：［25，48］，［16，35］，［79，82］，［23，40］，［36，72］，在此基礎上按二路歸并排序方法再對該序列進行一趟歸并后的結果為( )
A.16，25，35，48，23，40，79，82，36，72
B.16，25，35，48，23，40，79，82，72，36
C.16，25，48，35，79，82，23，36，40，72
D.16，25，35，48，79，23，36，40，72，82
18.設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非葉結點，則B中右指針域為空的結點有（ )
A.n-1
B.n
C.n+1
D.n+2
19.向順序棧中壓入新元素時，應當( )
A.先移動棧頂位置，再存入元素
B.先存入元素，再移動棧頂位置
C.先后次序無關緊要
D.同時進行
20.假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為( )
A.f+1==r
B.r+1==f
C.f==0
D.f==r
21.對某二叉樹進行前序遍歷的結果為ABDEFC，中序遍歷的結果為DBFEAC，則后序遍歷的結果為（ ）
A.DBFEAC
B.DFEBCA
C.BDFECA
D.BDEFAC
22.對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是( )
A.直接選擇排序
B.直接插入排序
C.快速排序
D.起泡排序
23.設有一個含有n 個(n>2)關鍵字的有序表，分別用順序查找法和二分查找法查找一個給定的關鍵字，比較次數(shù)分別為s和h，在查找成功的情況下，s和h的關系是( )
A.s = h
B.s > h
C.s < h
D.不能確定
24.一個關鍵字序列為{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素為基準而得到的第一次劃分結果為（ )
A.{38，46，79，56，40，84}
B.{38，79，56，46，40，84}
C.{40，38，46，56，79，84}
D.{38，46，56，79，40，84}
25.一個二叉樹按順序方式存儲在如下的一個維數(shù)組中,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14A B C D E F G H I J則結點E在二叉樹的第（ ）層。
A.1
B.2
C.3
D.4
