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