《數(shù)據(jù)結(jié)構(gòu)》2023年春學(xué)期在線作業(yè)2題目
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 60 分)
1.遞歸過程的實(shí)現(xiàn)需用到 ( )。
A.線性表
B.鏈表
C.棧
D.隊(duì)列
2.在下列情況中，可稱為二叉樹的是 ( )。
A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹
B.哈夫曼樹
C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹
D.每個(gè)結(jié)點(diǎn)只有一棵右子樹
3.經(jīng)過下列棧的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A.a
B.b
C.1
D.2
4.若要求盡可能快地對序列進(jìn)行穩(wěn)定的排序，則應(yīng)選 () 。
A.快速排序
B.歸并排序
C.起泡排序
D.希爾排序
5.一個(gè)算法應(yīng)該是（）。
A.程序
B.問題求解步驟的描述
C.要滿足五個(gè)基本特性
D.A和C
6.判斷線索二叉樹中某結(jié)點(diǎn)p有左子女的條件是 ( )。
A.p ! = NULL
B.p->lchild ! = NULL
C.p->ltag = = 0
D.p->ltag = = 1
7.二叉樹在中序線索化后，仍不能有效求解的問題是 ( )。
A.求指定結(jié)點(diǎn)的前序后繼
B.求指定結(jié)點(diǎn)的中序前驅(qū)
C.求指定結(jié)點(diǎn)的中序后繼
D.求指定結(jié)點(diǎn)的后序后繼
8.順序文件采用順序結(jié)構(gòu)實(shí)現(xiàn)文件的存儲(chǔ)，對大型的順序文件的少量修改，要求重新復(fù)制整個(gè)文件，代價(jià)很高，采用 () 的方法可降低所需的代價(jià)。
A.附加文件
B.按關(guān)鍵字大小排序
C.按記錄輸入先后排序
D.連續(xù)排序
9.廣義表A=(a, b, ( c, d ) , (e，( f , g ) ) )，則式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值為 ()。
A.( g )
B.( d )
C.c
D.d
10.( ) 的遍歷仍需要棧的支持。
A.前序線索二叉樹
B.中序線索二叉樹
C.后序線索二叉樹
D.前三種均需要
11.線索二叉樹是一種 ( ) 結(jié)構(gòu)。
A.邏輯
B.物理
C.邏輯和存儲(chǔ)
D.線性
12.有一個(gè)100*90的稀疏矩陣，非零元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 () 。
A.60
B.66
C.18000
D.33
13.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是 () 。
A.堆排序＜快速排序＜?xì)w并排序
B.堆排序＜?xì)w并排序＜快速排序
C.堆排序＞歸并排序＞快速排序
D.堆排序＞快速排序＞歸并排序
14.下列說法不正確的是 ()。
A.圖的遍歷是從給定的源點(diǎn)出發(fā)每個(gè)頂點(diǎn)僅被訪問一次
B.遍歷的基本方法有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷
C.圖的深度優(yōu)先遍歷不適用于有向圖
D.圖的深度優(yōu)先遍歷是一個(gè)遞歸過程
15.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的幾倍 ()。
A.1/2
B.1
C.2
D.4
16.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p之前插入s所指結(jié)點(diǎn)，則執(zhí)行 ( )。
A.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
C.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
17.在對n個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
18.已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占c個(gè)單元，若第一個(gè)結(jié)點(diǎn)的地址為LOC(a0)，則第i個(gè)結(jié)點(diǎn)的地址為 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
D.LOC(a0)+(i+1)*c
19.分塊查找要求表中的結(jié)點(diǎn) ()。
A.全部無序
B.塊之間無序
C.全部有序
D.塊之間有序
20.下面關(guān)于串的敘述中，哪一個(gè)是不正確的? ( )
A.串是字符的有限序列
B.空串是由空格構(gòu)成的串
C.模式匹配是串的一種重要運(yùn)算
D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)
二、判斷題 (共 20 道試題,共 40 分)
21.二叉樹按某種次序線索化后，任一結(jié)點(diǎn)均有指向其前序結(jié)點(diǎn)和后繼結(jié)點(diǎn)的線索。
22.在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著它最終排序位置相反的方向移動(dòng)，則該算法是不穩(wěn)定的。
23.非空的二叉樹一定滿足：某結(jié)點(diǎn)若有左子女，則其中序前驅(qū)一定沒有右子女。
24.數(shù)組是同類型值的集合。
25.用鏈表 ( lchild-rchild表示法 ) 存儲(chǔ)的包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針域中有n + l 個(gè)空指針。
26.鏈表中的表頭指針與表頭結(jié)點(diǎn)起到相同的作用。
27.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健?/span>
28.一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。
29.對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。
30.任何無向圖都存在生成樹。
31.在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左子女，則它必是樹葉。
32.鏈表中的表頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。
33.將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有右子樹。
34.連通分量是無向圖中的極大連通子圖。
35.所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。
36.需要借助于一個(gè)棧來實(shí)現(xiàn)DFS算法。
37.必須把一般的樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲(chǔ)。
38.對于插入、刪除運(yùn)算來說，鏈接存儲(chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。
39.后序線索二叉樹是不完善的，要對它進(jìn)行遍歷，還需要使用棧。
40.二維以上的數(shù)組其實(shí)是一種特殊的廣義表。
奧鵬，國開，廣開，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
