北交《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)一-0003
試卷總分:100 得分:100
一、單選題 (共 38 道試題,共 95 分)
1.每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做（）排序.
A.插入
B.交換
C.選擇
D.歸并
2.線性鏈表不具有的特點(diǎn)是（）。
A.隨機(jī)訪問
B.不必事先估計(jì)所需存儲(chǔ)空間大小
C.插入與刪除時(shí)不必移動(dòng)元素
D.所需空間與線性表長(zhǎng)度成正比
3.下列那種排序需要的附加存儲(chǔ)開銷最大（）。
A.快速排序
B.堆排序
C.歸并排序
D.插入排序
4.線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是（）。
A.D->Lchild=Null
B.D->ltag=1
C.D->Rchild=Null
D.D->ltag=0
5.順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置也（ ）。
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個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為()。
A.e
B.2e
C.n*n－e
D.n*n－2e
9.無向圖的鄰接矩陣是一個(gè) ( )。
A.對(duì)稱矩陣
B.零矩陣
C.上三角矩陣
D.對(duì)角矩陣
10.下列數(shù)據(jù)結(jié)構(gòu)中，能用折半查找的是( )。
A.順序存儲(chǔ)的有序線性表
B.線性鏈表
C.二叉鏈表
D.有序線性鏈表
11.從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹高度是（ ）。
A.原樹高度加1
B.原樹高度減1
C.原樹高度
D.不確定
12.設(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(n*e)
D.O(n*n)
13.若某線性表中最常用的操作是取第I個(gè)元素和找第I個(gè)元素的前趨元素，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。
A.順序表
B.單鏈表
C.雙鏈表
D.單循環(huán)鏈表
14.關(guān)于有向圖的鄰接表和逆鄰接表表示法，下列結(jié)論正確的是 （）。
A.用鄰接表表示法計(jì)算入度比較方便
B.用鄰接表表示法計(jì)算入度和出度都方便
C.用逆鄰接表表示法計(jì)算入度和出度都不方便
D.用逆鄰接表表示法計(jì)算入度比計(jì)算出度方便
15.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。下列選項(xiàng)中，（）就是不穩(wěn)定的排序方法。
A.起泡排序
B.歸并排序
C.直接插入法排序
D.簡(jiǎn)單選擇排序
16.判定一個(gè)順序棧（最多元素為m個(gè)）為空的條件是（ ）。
A.top＝＝0
B.top＝＝m
C.top!＝0
D.top!＝m
17.下列數(shù)據(jù)組織形式中，（ ）的各個(gè)結(jié)點(diǎn)可以任意鄰接。
A.集合
B.樹形結(jié)構(gòu)
C.線性結(jié)構(gòu)
D.圖狀結(jié)構(gòu)
18.具有2000個(gè)節(jié)點(diǎn)的二叉樹，其高度至少為（）。
A.9
B.10
C.11
D.12
19.隊(duì)列的插入操作是在（ ）進(jìn)行。
A.隊(duì)首
B.隊(duì)尾
C.隊(duì)前
D.隊(duì)后
20.如果一個(gè)樹中，結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B的度為（ ）。
A.1
B.3
C.4
D.5
21.下列關(guān)于棧的敘述正確的是（ ）。
A.棧是非線性結(jié)構(gòu)
B.棧是一種樹狀結(jié)構(gòu)
C.棧具有先進(jìn)先出的特征
D.棧具有后進(jìn)先出的特征
22.對(duì)于含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為( )。
A.O(log2n)
B.O(n*n)
C.O(ne)
D.O(elog2e)
23.在線性表的散列存儲(chǔ)中，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則裝填因子a等于（）。
A.n/m
B.m/n
C.n/(n+m)
D.m/(n+m)
24.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。
A.空或只有一個(gè)結(jié)點(diǎn)高度等于其結(jié)點(diǎn)數(shù)
B.任一結(jié)點(diǎn)無左孩子
C.任一結(jié)點(diǎn)無右孩子
25.設(shè)一數(shù)列的順序?yàn)?，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.對(duì)某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為（ ）。
A.DBFEAC
B.DFEBCA
C.BDFECA
D.BDEFAC
27.非空的循環(huán)單鏈表head的尾節(jié)點(diǎn)（由p所指向）滿足（ ）。
A.p->next=NULL
B.p=NULL
C.p->next=head
D.p=head
28.計(jì)算機(jī)的算法必須具備輸入，輸出和（ ）五個(gè)特性。
A.可行性，可移植性和可擴(kuò)充性
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.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。
A.散列表
B.順序存儲(chǔ)或鏈接存儲(chǔ)
C.壓縮存儲(chǔ)
D.索引存儲(chǔ)
31.設(shè)有1000個(gè)元素，用折半查找時(shí)，最大比較次數(shù)是（）。
A.1
B.7
C.10
D.25
32.若從二叉樹的任一節(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的節(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是（ ）。
A.二叉排序樹
B.哈夫曼樹
C.堆
D.AVL樹
33.數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)I 從1到8,列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。
A.80
B.100
C.240
D.270
34.如果只想得到1024個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（ ）方法最快。
A.起泡排序
B.快速排序
C.簡(jiǎn)單選擇排序
D.堆排序
35.在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(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個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（ ）。
A.不確定
B.2n
C.2n+1
D.2n-1
37.帶頭節(jié)點(diǎn)的單鏈表 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.隊(duì)列
D.樹
二、判斷題 (共 2 道試題,共 5 分)
39.線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示?
40.當(dāng)3階B_樹中有255個(gè)關(guān)鍵碼時(shí),其最大高度(包括失敗結(jié)點(diǎn)層)不超過8?
