數(shù)據(jù)結(jié)構(gòu)2022年春學(xué)期在線作業(yè)1題目
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 60 分)
1.某二叉樹結(jié)點的前序序列為ECBAD，中序序列為EBCDA，則該二叉樹結(jié)點的后序序列為 ( )。
A.ABCED
B.DECAB
C.DEABC
D.BDACE
2.存放在外存中的數(shù)據(jù)的組織結(jié)構(gòu)是 ()。
A.數(shù)組
B.表
C.文件
D.鏈表
3.在下述幾種排序方法中，不穩(wěn)定的排序方法是 ()。
A.直接插入排序
B.冒泡排序
C.直接選擇排序
D.歸并排序
4.“堆積”問題是由于()引起的。
A.同義詞之間發(fā)生沖突
B.散列函數(shù)
C.不同的同義詞子表結(jié)合在一起
D.散列表“溢出”
5.若要求盡可能快地對序列進行穩(wěn)定的排序，則應(yīng)選 () 。
A.快速排序
B.歸并排序
C.起泡排序
D.希爾排序
6.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 ()。
A.n
B.(n-1)/2
C.n/2
D.(n+1)/2
7.用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點序列是 ()。
A.逆拓撲有序
B.拓撲有序
C.無序的
D.部分有序的
8.設(shè)根結(jié)點的層數(shù)為0，若高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此二叉樹上所包含的結(jié)點數(shù)至少為 ( )。
A.h+1
B.2h-1
C.2h
D.2h+1
9.在下列情況中，可稱為二叉樹的是 ( )。
A.每個結(jié)點至多有兩棵子樹的樹
B.哈夫曼樹
C.每個結(jié)點至多有兩棵子樹的有序樹
D.每個結(jié)點只有一棵右子樹
10.廣義表 (( a , b , c , d ) ) 的表頭是 ()。
A.a
B.( )
C.( a , b , c , d )
D.( b , c , d )
11.設(shè)散列地址空間為0～m-1，key為關(guān)鍵字，用p去除key，將得到的余數(shù)作為key的散列地址，即h(key) = key % p。為了減少發(fā)生沖突的頻率，一般取p為 ()。
A.小于等于m的最大奇數(shù)
B.小于等于m的最大偶數(shù)
C.小于等于m的最大素數(shù)
D.小于等于m的最大合數(shù)
12.有m個葉結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為 ( )。
A.m
B.m+1
C.2m-1
D.2m
13.樹最適合用來表示 ( )。
A.有序數(shù)據(jù)元素
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無聯(lián)系的數(shù)據(jù)
14.在下面的排序方法中，其比較次數(shù)與待排序記錄的初始排列狀態(tài)無關(guān)的是 ()。
A.直接插入排序
B.快速排序
C.直接選擇排序
D.歸并排序
15.有n個頂點的有向圖的邊數(shù)最多為 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
16.假定有k個關(guān)鍵字互為同義詞，若采用線性探查法把這k個關(guān)鍵字存入散列表中，至少需要進行多少次探測？（）
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
17.在排序方法中，從未排序序列中挑選記錄，并將其依次放入已排序序列(初始時為空)的一端的方法，稱為 ()。
A.希爾排序
B.插入排序
C.歸并排序
D.選擇排序
18.在下面的敘述中，正確的是 ( )。
A.樹的先根遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同
B.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同
C.樹的先根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同
D.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同
19.有n個頂點的無向圖的邊數(shù)最多為 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
20.在排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 ()。
A.直接選擇排序
B.冒泡排序
C.直接插入排序
D.希爾排序
二、判斷題 (共 20 道試題,共 40 分)
21.快速排序的速度在所有排序方法中最快，而且所需附加空間也最少。
22.在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點。
23.當(dāng)待排序記錄已經(jīng)從小到大排序或從大到小有序時，快速排序的執(zhí)行時間最省。
24.快速排序和歸并排序在最壞情況下的比較次數(shù)都是O(nlog2n )。
25.二叉樹中除葉結(jié)點外，任一結(jié)點X ，其左子樹根結(jié)點的值小于該結(jié)點X的值；其右子樹根結(jié)點的值大于等于該結(jié)點X的值，則此二叉樹一定是二叉排序樹。
26.對有序的單鏈表可以進行折半查找。
27.堆是完全二叉樹。
28.對一棵二叉樹進行層次次序遍歷時，應(yīng)借助于一個棧。
29.直接選擇排序算法對n個記錄排序，在最好情況下的時間復(fù)雜度為O(n)。
30.二維以上的數(shù)組其實是一種特殊的廣義表。
31.若一個廣義表的表頭為空表，則此廣義表亦為空表。
32.空串與空格串是相同的。
33.在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。
34.二叉樹中每個結(jié)點至多有兩個子結(jié)點，而對一般的樹則無此限制。因此，二叉樹是樹的特殊情形。
35.最小生成樹問題是構(gòu)造帶權(quán)連通圖 ( 網(wǎng) ) 的最小代價生成樹。
36.串是一種數(shù)據(jù)對象和操作都特殊的線性表。
37.( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
38.二叉樹結(jié)點的中序遍歷序列與前序遍歷序列可以唯一地確定該棵二叉樹。
39.順序存儲結(jié)構(gòu)的主要缺點是不利于插入、刪除操作。
40.文件系統(tǒng)采用索引結(jié)構(gòu)是為了節(jié)省存儲空間。
奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學(xué)習(xí)
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
