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