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