北交《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)二-0002
試卷總分:100 得分:100
一、單選題 (共 38 道試題,共 95 分)
1.下列數(shù)據(jù)組織形式中，（ ）的各個(gè)結(jié)點(diǎn)可以任意鄰接。
A.集合
B.樹形結(jié)構(gòu)
C.線性結(jié)構(gòu)
D.圖狀結(jié)構(gòu)
2.鏈表不具有的特點(diǎn)是（ ）。
A.不必事先估計(jì)存儲空間
B.可隨機(jī)訪問任一元素
C.插入刪除不需要移動元素
D.所需空間與線性表長度成正比
3.線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是（）。
A.D->Lchild=Null
B.D->ltag=1
C.D->Rchild=Null
D.D->ltag=0
4.設(shè)有兩個(gè)串（S1和S2），求S1在S2中首次出現(xiàn)的位置的運(yùn)算稱為（）。
A.連接
B.模式匹配
C.求子串
D.求串長
5.無向圖的鄰接矩陣是一個(gè) ( )。
A.對稱矩陣
B.零矩陣
C.上三角矩陣
D.對角矩陣
6.二叉樹第i層上至多有（）結(jié)點(diǎn)。
A.2i
B.2 的i次方
C.2i-1
D.2 的i-1次方
7.串的邏輯結(jié)構(gòu)與（ ）的邏輯結(jié)構(gòu)不同。
A.線性表
B.棧
C.隊(duì)列
D.樹
8.線性表的鏈接實(shí)現(xiàn)有利于（）運(yùn)算。
A.插入
B.讀表元
C.查找
D.定位
9.在線性表的散列存儲中，若用m表示散列表的長度，n表示待散列存儲的元素的個(gè)數(shù)，則裝填因子a等于（）。
A.n/m
B.m/n
C.n/(n+m)
D.m/(n+m)
10.設(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
11.鄰接表是圖的一種（ ）。
A.順序存儲結(jié)構(gòu)
B.鏈?zhǔn)酱鎯Y(jié)構(gòu)
C.索引存儲結(jié)構(gòu)
D.列存儲結(jié)構(gòu)
12.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。
A.n-1
B.n(n-1)/2
C.n(n+1)/2
D.0
13.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（ ）種。
A.3
B.4
C.5
D.6
14.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。
A.空或只有一個(gè)結(jié)點(diǎn)高度等于其結(jié)點(diǎn)數(shù)
B.任一結(jié)點(diǎn)無左孩子
C.任一結(jié)點(diǎn)無右孩子
15.從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹高度是（ ）。
A.原樹高度加1
B.原樹高度減1
C.原樹高度
D.不確定
16.下列數(shù)據(jù)結(jié)構(gòu)中，能用折半查找的是( )。
A.順序存儲的有序線性表
B.線性鏈表
C.二叉鏈表
D.有序線性鏈表
17.在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為()。
A.e
B.2e
C.n*n－e
D.n*n－2e
18.一個(gè)隊(duì)的入隊(duì)序列是1，2，3，4 ，則隊(duì)列的輸出序列是（ ）。
A.4，3，2，1
B.1，2，3，4
C.1，4，3，2
D.3，2，1，4
19.廣義表（（a）,a）的表頭是（）。
A.a
B.b
C.(a)
D.((a))
20.如果只想得到1024個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（ ）方法最快。
A.起泡排序
B.快速排序
C.簡單選擇排序
D.堆排序
21.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。
A.n-1
B.n
C.n+1
D.n+2
22.串的長度是（ ）。
A.串中不同字符的個(gè)數(shù)
B.串中不同字母的個(gè)數(shù)
C.串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于0
D.串中所含字符的個(gè)數(shù)
23.在一個(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;
24.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的（）。
A.行號
B.列號
C.元素值
D.地址
25.算法的時(shí)間復(fù)雜度是指（ ）。
A.執(zhí)行算法程序所需要的時(shí)間
B.算法程序的長度
C.算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)
D.算法程序中的指令條數(shù)
26.如下敘述中正確的是（ ）。
A.串是一種特殊的線性表
B.串的長度必須大于零
C.串中元素只能是字母
D.空串就是空白串
27.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動（ ）個(gè)元素。
A.8
B.63.5
C.64
D.7
28.若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）種情況。
A.3，2，1
B.2，1，3
C.3，1，2
D.1，3，2
29.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（ ）。
A.不確定
B.2n
C.2n+1
D.2n-1
30.當(dāng)利用大小為N 的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top = = N表示?？?，則退棧時(shí)，用（ ）語句修改top指針。
A.top++
B.top=0
C.top--
D.top=N
31.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ ）。
A.先移動棧頂指針，再存入元素
B.先存入元素，再移動棧頂指針
C.先后次序無關(guān)緊要
D.同時(shí)進(jìn)行
32.二叉樹上葉結(jié)點(diǎn)數(shù)等于（）。
A.分支結(jié)點(diǎn)數(shù)加1
B.單分支結(jié)點(diǎn)數(shù)加1
C.雙分支結(jié)點(diǎn)數(shù)加1
D.雙分支結(jié)點(diǎn)數(shù)減1
33.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（ ）。
A.Shell排序
B.起泡排序
C.插入排序
D.選擇排序
34.已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（ ）。
A.acbed
B.decab
C.deabc
D.cedba
35.樹最適合用來表示（ ）。
A.有序數(shù)據(jù)元素
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無聯(lián)系的數(shù)據(jù)
36.如果一個(gè)樹中，結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B的度為（ ）。
A.1
B.3
C.4
D.5
37.對某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為（ ）。
A.DBFEAC
B.DFEBCA
C.BDFECA
D.BDEFAC
38.完成堆排序的全過程需要 ( )個(gè)紀(jì)錄大小的輔助空間。
A.1
B.n
C.nlog2n
D.|nlog2n|
二、判斷題 (共 2 道試題,共 5 分)
39.線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r(shí)所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù)?
40.當(dāng)3階B_樹中有255個(gè)關(guān)鍵碼時(shí),其最大高度(包括失敗結(jié)點(diǎn)層)不超過8?
