《數(shù)據(jù)結(jié)構(gòu)（本科）》23年6月作業(yè)考核-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 100 分)
1.設(shè)某算法的問題規(guī)模函數(shù)f(n)=300n2+8000n+900，則它的漸進(jìn)時(shí)間復(fù)雜度為（ )
A.O(n3)
B.O(n2)
C.O(n)
D.O(1)
2.對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是( )
A.直接選擇排序
B.直接插入排序
C.快速排序
D.起泡排序
3.設(shè)有整型二維數(shù)組M[7][6]，每個(gè)元素（整數(shù)）占4個(gè)存儲(chǔ)單元，元素按行的順序存儲(chǔ)，數(shù)組的起始地址為1000，元素M[5][3]的地址是（ )
A.1032
B.1132
C.1192
D.1232
4.一個(gè)關(guān)鍵字序列為{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素為基準(zhǔn)而得到的第一次劃分結(jié)果為（ )
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}
5.若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況( )
A.3，2，1
B.2，1，3
C.3，1，2
D.1，3，2
6.一個(gè)二叉樹按順序方式存儲(chǔ)在如下的一個(gè)維數(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則結(jié)點(diǎn)E在二叉樹的第（ ）層。
A.1
B.2
C.3
D.4
7.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用領(lǐng)接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為( )
A.O（nlog2e）
B.O（n+e）
C.O(ne)
D.O(n2)
8.設(shè)有100個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為( )
A.6
B.7
C.8
D.10
9.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ）
A.front=front+1
B.front=(front+1)%(m-1)
C.front=(front-1)%m
D.front=(front+1)%m
10.設(shè)有一個(gè)含有n 個(gè)(n>2)關(guān)鍵字的有序表，分別用順序查找法和二分查找法查找一個(gè)給定的關(guān)鍵字，比較次數(shù)分別為s和h，在查找成功的情況下，s和h的關(guān)系是( )
A.s = h
B.s > h
C.s < h
D.不能確定
11.AVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點(diǎn)的( )
A.左、右子樹的高度均相同
B.左、右子樹高度差的絕對(duì)值不超過1
C.左子樹的高度均大于右子樹的高度
D.左子樹的高度均小于右子樹的高度
12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（ )
A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)
13.依次在初始為空的隊(duì)列中插入元素X，Y，Z，W以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)頭元素是（ )
A.X
B.Y
C.Z
D.W
14.向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )
A.O(㏒2n)
B.O(n)
C.O(1)
D.O(㏒2n)
15.設(shè)串sl=″Data Structures with Java″,s2=″it″，則子串定位函數(shù)index(s1,s2)的值為( )
A.15
B.16
C.17
D.18
16.若采用鄰接矩陣法存儲(chǔ)一個(gè)N個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè)( )
A.隊(duì)頭元素的前一個(gè)位置
B.隊(duì)頭元素的后一個(gè)位置
C.隊(duì)頭元素位置
D.隊(duì)尾元素的前一位置
17.向一個(gè)有127個(gè)元素原順序表中插入一個(gè)新元素并保存原來順序不變，平均要移動(dòng)（ ）個(gè)元素。
A.8
B.63.5
C.63
D.7
18.對(duì)某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為（ ）
A.DBFEAC
B.DFEBCA
C.BDFECA
D.BDEFAC
19.右圖中的拓?fù)湫蛄袨椋?)
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
20.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ )
A.n-1
B.n
C.n+1
D.n+2
21.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件為( )
A.f+1==r
B.r+1==f
C.f==0
D.f==r
22.一組記錄的關(guān)鍵字經(jīng)一趟二路歸并排序后得到含有5個(gè)長度為2的有序表如下：［25，48］，［16，35］，［79，82］，［23，40］，［36，72］，在此基礎(chǔ)上按二路歸并排序方法再對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為( )
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
23.用鏈表表示線性表的優(yōu)點(diǎn)是( )
A.便于隨機(jī)存取
B.花費(fèi)的存儲(chǔ)空間比順序表少
C.便于插入與刪除
D.數(shù)據(jù)元素的物理順序與邏輯順序相同
24.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)( )
A.先移動(dòng)棧頂位置，再存入元素
B.先存入元素，再移動(dòng)棧頂位置
C.先后次序無關(guān)緊要
D.同時(shí)進(jìn)行
25.對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行（ ）次比較
A.8
B.10
C.15
D.25
奧鵬，國開，廣開，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請(qǐng)咨詢QQ : 3230981406或微信:aopopenfd777
