北交《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)一-0003

試卷總分:100  得分:100

一、單選題 (共 38 道試題,共 95 分)

1.每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做（）排序.

A.插入

B.交換

C.選擇

D.歸并

2.線性鏈表不具有的特點是（）。

A.隨機訪問

B.不必事先估計所需存儲空間大小

C.插入與刪除時不必移動元素

D.所需空間與線性表長度成正比

3.下列那種排序需要的附加存儲開銷最大（）。

A.快速排序

B.堆排序

C.歸并排序

D.插入排序

4.線索化二叉樹中某結(jié)點D，沒有左孩子的主要條件是（）。

A.D->Lchild=Null

B.D->ltag=1

C.D->Rchild=Null

D.D->ltag=0

5.順序表中邏輯上相鄰的節(jié)點其物理位置也（ ）。

A.一定相鄰

B.不必相鄰

C.按某種規(guī)律排列

D.無要求

6.圖的深度優(yōu)先遍歷類似于二叉樹的（ ）。

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

7.廣義表（（a）,a）的表頭是（）。

A.a

B.b

C.(a)

D.((a))

8.在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為()。

A.e

B.2e

C.n*n－e

D.n*n－2e

9.無向圖的鄰接矩陣是一個 ( )。

A.對稱矩陣

B.零矩陣

C.上三角矩陣

D.對角矩陣

10.下列數(shù)據(jù)結(jié)構(gòu)中，能用折半查找的是( )。

A.順序存儲的有序線性表

B.線性鏈表

C.二叉鏈表

D.有序線性鏈表

11.從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點的合并，則新樹高度是（ ）。

A.原樹高度加1

B.原樹高度減1

C.原樹高度

D.不確定

12.設(shè)有向圖有n個頂點和e條邊，采用領(lǐng)接表作為其存儲表示，在進行拓?fù)渑判驎r，總的計算時間為（）。

A.O（nlog2e）

B.O（n+e）

C.O(n*e)

D.O(n*n)

13.若某線性表中最常用的操作是取第I個元素和找第I個元素的前趨元素，則采用( )存儲方式最節(jié)省時間。

A.順序表

B.單鏈表

C.雙鏈表

D.單循環(huán)鏈表

14.關(guān)于有向圖的鄰接表和逆鄰接表表示法，下列結(jié)論正確的是 （）。

A.用鄰接表表示法計算入度比較方便

B.用鄰接表表示法計算入度和出度都方便

C.用逆鄰接表表示法計算入度和出度都不方便

D.用逆鄰接表表示法計算入度比計算出度方便

15.如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。下列選項中，（）就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡單選擇排序

16.判定一個順序棧（最多元素為m個）為空的條件是（ ）。

A.top＝＝0

B.top＝＝m

C.top!＝0

D.top!＝m

17.下列數(shù)據(jù)組織形式中，（ ）的各個結(jié)點可以任意鄰接。

A.集合

B.樹形結(jié)構(gòu)

C.線性結(jié)構(gòu)

D.圖狀結(jié)構(gòu)

18.具有2000個節(jié)點的二叉樹，其高度至少為（）。

A.9

B.10

C.11

D.12

19.隊列的插入操作是在（ ）進行。

A.隊首

B.隊尾

C.隊前

D.隊后

20.如果一個樹中，結(jié)點A有3個兄弟，而且B為A的雙親，則B的度為（ ）。

A.1

B.3

C.4

D.5

21.下列關(guān)于棧的敘述正確的是（ ）。

A.棧是非線性結(jié)構(gòu)

B.棧是一種樹狀結(jié)構(gòu)

C.棧具有先進先出的特征

D.棧具有后進先出的特征

22.對于含有n個頂點e條邊的無向連通圖，利用Prim算法生成最小代價生成樹其時間復(fù)雜度為( )。

A.O(log2n)

B.O(n*n)

C.O(ne)

D.O(elog2e)

23.在線性表的散列存儲中，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則裝填因子a等于（）。

A.n/m

B.m/n

C.n/(n+m)

D.m/(n+m)

24.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。

A.空或只有一個結(jié)點高度等于其結(jié)點數(shù)

B.任一結(jié)點無左孩子

C.任一結(jié)點無右孩子

25.設(shè)一數(shù)列的順序為1，2，3，4，5，6，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為（）。

A.3，2，5，6，4，1

B.1，5，4，6，2，3

C.2，4，3，5，1，6

D.4，5，3，6，2，1

26.對某二叉樹進行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為（ ）。

A.DBFEAC

B.DFEBCA

C.BDFECA

D.BDEFAC

27.非空的循環(huán)單鏈表head的尾節(jié)點（由p所指向）滿足（ ）。

A.p->next=NULL

B.p=NULL

C.p->next=head

D.p=head

28.計算機的算法必須具備輸入，輸出和（ ）五個特性。

A.可行性，可移植性和可擴充性

B.可行性，確定性和有窮性

C.確定性，有窮性和穩(wěn)定性

D.易讀性，穩(wěn)定性和安全性

29.樹最適合用來表示（ ）。

A.有序數(shù)據(jù)元素

B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)

D.元素之間無聯(lián)系的數(shù)據(jù)

30.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。

A.散列表

B.順序存儲或鏈接存儲

C.壓縮存儲

D.索引存儲

31.設(shè)有1000個元素，用折半查找時，最大比較次數(shù)是（）。

A.1

B.7

C.10

D.25

32.若從二叉樹的任一節(jié)點出發(fā)到根的路徑上所經(jīng)過的節(jié)點序列按其關(guān)鍵字有序，則該二叉樹是（ ）。

A.二叉排序樹

B.哈夫曼樹

C.堆

D.AVL樹

33.數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)I 從1到8,列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。

A.80

B.100

C.240

D.270

34.如果只想得到1024個元素組成的序列中第5個最小元素之前的部分排序的序列，用（ ）方法最快。

A.起泡排序

B.快速排序

C.簡單選擇排序

D.堆排序

35.在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（ ）。

A.HL=p;p->next=HL;

B.p->next=HL;HL=p;

C.p->next=HL;p=HL;

D.p->next=HL->next;HL->next=p;

36.在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（ ）。

A.不確定

B.2n

C.2n+1

D.2n-1

37.帶頭節(jié)點的單鏈表 head 為空的判定條件（ ）。

A.head=NULL

B.head->next=NULL

C.head->next=head

D.head!=head

38.串的邏輯結(jié)構(gòu)與（ ）的邏輯結(jié)構(gòu)不同。

A.線性表

B.棧

C.隊列

D.樹

二、判斷題 (共 2 道試題,共 5 分)

39.線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎?

40.當(dāng)3階B_樹中有255個關(guān)鍵碼時,其最大高度(包括失敗結(jié)點層)不超過8?