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