西交《數(shù)據(jù)結構》在線作業(yè)-00001
試卷總分:100 得分:100
一、單選題 (共 30 道試題,共 60 分)
1.由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）
A.24
B.71
C.48
D.53
答案:
2.由兩個棧共享一個向量空間的好處是：（）
A.減少存取時間，降低下溢發(fā)生的機率
B.節(jié)省存儲空間，降低上溢發(fā)生的機率
C.減少存取時間，降低上溢發(fā)生的機率
D.節(jié)省存儲空間，降低下溢發(fā)生的機率
答案:
3.數(shù)據(jù)的基本單位（ ）。
A.數(shù)據(jù)結構
B.數(shù)據(jù)元素
C.數(shù)據(jù)項
D.文件
答案:
4.設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（ ）。
A.40，42，60，55，80，85
B.42，45，55，60，85，80
C.42，40，55，60，80，85
D.42，40，60，85，55，80
答案:
5.下列各種排序算法中平均時間復雜度為O（n）是（）。
A.快速排序
B.堆排序
C.歸并排序
D.冒泡排序
答案:
6.對于一些特殊矩陣，采用壓縮存儲的目的是（ ）。
A.使表達變得更簡單
B.對矩陣元素的存取變得簡單
C.去掉矩陣中的多于元素
D.減少不必要的存儲空間
答案:
7.循環(huán)隊列占用的空間（ ）。
A.必須連續(xù)
B.不必連續(xù)
C.不能連續(xù)
D.可以不連續(xù)
答案:
8.鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是（）
A.插入操作更加方便
B.通常不會出現(xiàn)棧滿的情況
C.不會出現(xiàn)?？盏那闆r
D.刪除操作更加方便
答案:
9.在二叉排序樹中插入一個結點的時間復雜度為（）。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n)
答案:
10.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。
A.99
B.100
C.101
D.102
答案:
11.設給定權值總數(shù)有n 個，其哈夫曼樹的結點總數(shù)為( )
A.不確定
B.2n
C.2n+1
D.2n-1
答案:
12.設輸入序列1、2、3、?、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（）。
A.n-i
B.n-1-i
C.n+l-i
D.不能確定
答案:
13.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。
A.O(n)
B.O(n^2)
C.O(nlog2n)
D.O(log2n)
答案:
14.如果要求頻繁的對線性表進行插入和刪除操作,則線性表應該采用( )存儲結構。
A.散列
B.順序
C.鏈式
D.任意
答案:
15.下列說法中，正確的是（ ）。
A.度為2的樹是二叉樹
B.度為2的有序樹是二叉樹
C.子樹有嚴格的左、右之分的樹是二叉樹
D.子樹有嚴格的左、右之分，且度不超過2的樹是二叉樹
答案:
16.兩個字符串相等的條件是( )。
A.兩串的長度相等；
B.兩串包含的字符相同；
C.兩串的長度相等，并且兩串包含的字符相同；
D.兩串的長度相等，并且對應位置上的字符相同。
答案:
17.設有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為（）
A.6
B.7
C.8
D.10
答案:
18.設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。
A.快速排序
B.堆排序
C.歸并排序
D.插入排序
答案:
19.建立一個長度為n的有序單鏈表的時間復雜度為（）
A.O(n)
B.O(1)
C.O(n)
D.O(log2n)
答案:
20.下面關于線性表的敘述錯誤的是（）。
A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間
B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間
C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)
D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)
答案:
21.線性表采用鏈式存儲時，結點的存儲地址（）
A.必須是不連續(xù)的
B.連續(xù)與否均可
C.必須是連續(xù)的
D.和頭結點的存儲地址相連續(xù)
答案:
22.下列存儲形式中，（）不是樹的存儲形式
A.雙親表示法
B.左子女右兄弟表示法
C.廣義表表示法
D.順序表示法
答案:
23.有n個頂點的無向圖的鄰接矩陣是用（ ）數(shù)組存儲。
A.一維
B.n行n列
C.任意行n列
D.n行任意列
答案:
24.若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用( )遍歷方法最合適。
A.前序
B.中序
C.后序
D.按層次
答案:
25.設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（）。
A.5，3，4，6，1，2
B.3，2，5，6，4，1
C.3，1，2，5，4，6
D.1，5，4，6，2，3
答案:
26.在一棵具有5層的滿二叉樹中結點數(shù)為（）
A.31
B.32
C.33
D.16
答案:
27.若進隊的序列為A、B、C、D，則出隊的序列是（ ）。
A.C、D、A
B.C、B、D
C.B、C、D
D.B、D、A
答案:
28.線性鏈表各結點之間的地址( )
A.必須連續(xù)
B.一定不連續(xù)
C.部分地址必須連續(xù)
D.連續(xù)與否無所謂
答案:
29.設某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結點且度數(shù)為0的結點數(shù)為n，則這棵二叉中共有（）個結點。
A.2n
B.n+l
C.2n-1
D.2n+l
答案:
30.設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數(shù)為（）。
A.1
B.2
C.3
D.4
答案:
二、判斷題 (共 20 道試題,共 40 分)
31.滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。
答案:
32.一般樹和二叉樹的結點數(shù)目都可以為0。 ( )
答案:
33.在使用后綴表表示實現(xiàn)計算器時用到一個棧的實例，其作用是暫存運算對象。
答案:
34.堆是完全二叉樹，完全二叉樹不一定是堆。
答案:
35.線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ ）
答案:
36.算法與程序沒有區(qū)別。 ( )
答案:
37.在B+樹中查找和在B-樹中查找的過程完全相同。 ( )
答案:
38.從本質(zhì)上看,文件是一種非線性結構。
答案:
39.在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（ ）
答案:
40.如果某種排序算法不穩(wěn)定，則該排序方法就沒有實用價值。（ ）
答案:
41.棧和隊列都是限制存取點的線性結構。
答案:
42.設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（ ）
答案:
43.有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。
答案:
44.先序遍歷一棵二叉排序樹得到的結點序列不一定是有序的序列。
答案:
45.如果兩個關鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關鍵字為同義詞。
答案:
46.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）
答案:
47.除了插入和刪除操作之外，數(shù)組的操作還包括存取、修改、檢索和排序。( )
答案:
48.當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（ ）
答案:
49.在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear-front。（ ）
答案:
50.線性表的順序存儲結構比鏈式存儲結構更好。
答案:
奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學習
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
