《數(shù)據(jù)結(jié)構(gòu)(本科)》22年6月課程考核-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 100 分)
1.向一個有127個元素原順序表中插入一個新元素并保存原來順序不變,平均要移動( )個元素。
A.8
B.63.5
C.63
D.7
2.鏈?zhǔn)綏Ec順序棧相比,一個比較明顯的優(yōu)點是( )
A.插入操作更加方便
B.通常不會出現(xiàn)棧滿的情況
C.不會出現(xiàn)??盏那闆r
D.刪除操作更加方便
3.假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是( )
A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)
4.設(shè)F是一個森林,B是由F轉(zhuǎn)換得到的二叉樹,F(xiàn)中有n個非葉結(jié)點,則B中右指針域為空的結(jié)點有( )
A.n-1
B.n
C.n+1
D.n+2
5.向順序棧中壓入新元素時,應(yīng)當(dāng)( )
A.先移動棧頂位置,再存入元素
B.先存入元素,再移動棧頂位置
C.先后次序無關(guān)緊要
D.同時進(jìn)行
6.用鏈表表示線性表的優(yōu)點是( )
A.便于隨機(jī)存取
B.花費(fèi)的存儲空間比順序表少
C.便于插入與刪除
D.數(shù)據(jù)元素的物理順序與邏輯順序相同
7.若采用鄰接矩陣法存儲一個N個頂點的無向圖,則該鄰接矩陣是一個( )
A.隊頭元素的前一個位置
B.隊頭元素的后一個位置
C.隊頭元素位置
D.隊尾元素的前一位置
8.一個關(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}
9.設(shè)某算法的問題規(guī)模函數(shù)f(n)=300n2+8000n+900,則它的漸進(jìn)時間復(fù)雜度為( )
A.O(n3)
B.O(n2)
C.O(n)
D.O(1)
10.對待排序的元素序列進(jìn)行劃分,將其分為左、右兩個子序列,再對兩個子序列施加同樣的排序操作,直到子序列為空或只剩一個元素為止。這樣的排序方法是( )
A.直接選擇排序
B.直接插入排序
C.快速排序
D.起泡排序
11.對5個不同的數(shù)據(jù)元素進(jìn)行直接插入排序,最多需要進(jìn)行( )次比較
A.8
B.10
C.15
D.25
12.一個二叉樹按順序方式存儲在如下的一個維數(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é)點E在二叉樹的第( )層。
A.1
B.2
C.3
D.4
13.設(shè)有100個數(shù)據(jù)元素,采用折半搜索時,最大比較次數(shù)為( )
A.6
B.7
C.8
D.10
14.AVL樹是一種平衡的二叉排序樹,樹中任一結(jié)點的( )
A.左、右子樹的高度均相同
B.左、右子樹高度差的絕對值不超過1
C.左子樹的高度均大于右子樹的高度
D.左子樹的高度均小于右子樹的高度
15.對有14個數(shù)據(jù)元素的有序表R[14]進(jìn)行折半搜索,搜索到R[3]的關(guān)鍵碼等于給定值,此時元素比較順序依次為( )
A.R[0],R[1],R[2],R[3]
B.R[0],R[13],R[2],R[3]
C.R[6],R[2],R[4],R[3]
D.R[6],R[4],R[2],R[3]
16.設(shè)數(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
17.向二叉搜索樹中插入一個元素時,其時間復(fù)雜度大致為( )
A.O(㏒2n)
B.O(n)
C.O(1)
D.O(㏒2n)
18.線性表是一個具有n個( )的有限序列。
A.表元素
B.字符
C.數(shù)據(jù)元素
D.數(shù)據(jù)項
19.依次在初始為空的隊列中插入元素X,Y,Z,W以后,緊接著作了兩次刪除操作,此時的隊頭元素是( )
A.X
B.Y
C.Z
D.W
20.設(shè)有向圖有n個頂點和e條邊,采用領(lǐng)接表作為其存儲表示,在進(jìn)行拓?fù)渑判驎r,總的計算時間為( )
A.O(nlog2e)
B.O(n+e)
C.O(ne)
D.O(n2)
21.n個頂點的有向完全圖中含有向邊的數(shù)目最多為( )
A.n(n-1)/2
B.n(n-1)
C.n-1
D.n
22.一組記錄的關(guān)鍵字經(jīng)一趟二路歸并排序后得到含有5個長度為2的有序表如下:[25,48],[16,35],[79,82],[23,40],[36,72],在此基礎(chǔ)上按二路歸并排序方法再對該序列進(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.設(shè)串sl=″Data Structures with Java″,s2=″it″,則子串定位函數(shù)index(s1,s2)的值為( )
A.15
B.16
C.17
D.18
24.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的( )
A.存儲結(jié)構(gòu)
B.邏輯結(jié)構(gòu)
C.算法
D.操作
25.下列存儲形式中不是樹的存儲形式( )
A.雙親表示法
B.孩子兄弟表示法
C.順序表示法
D.廣義表表示法