更多優質自考資料盡在百度貼吧自考樂園俱樂部
(歡迎加入...歡迎交流...止不住的驚喜等著你.........
2023年全國自考資料結構模擬試卷(八)
一、單項選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個備選專案中
只有乙個是符號題目要求的,請將其**填寫的括號內.錯選、多選或未選均無分。
1. 在下面的程式中,語句s的執行次數為()
for(i=1;i<=n-1;i++)
a. a
b. b
c. c
d. d
答案:b
2. 用陣列a[0..n-1]存放迴圈佇列的元素值,若其頭尾指標分別為front和rear,則迴圈隊
列中當前元素的個數為()
a. (rear-front+m) mod m
b. (rear-front+1) mod m
c. (rear-front-1+m) mod m
d. (rear-front)mod m
答案:a
3. 迴圈鍊錶的主要優點是()
a. 不再需要頭指標了
b. 已知某個結點的位置後,能夠容易找到它的直接前趨
c. 在進行插入、刪除運算時,能更好地保證鍊錶不斷開
d. 從表中任一結點出發都能掃瞄到整個鍊錶
答案:d
4. 下面的查詢方式中,可以對無序表進行查詢的是()
a. 順序查詢
b. 二分查詢
c. 二叉排序樹
d. b-樹上的查詢
答案:a
5. 在乙個具有n個頂點的無向完全圖中,包含的邊的總數是()
a. n(n-1)/2
b. n(n-1)
c. n(n+1)
d. n(n+1)/2
答案:a
6. 靜態查詢表與動態查詢表二者的根本差別在於()
a. 它們的邏輯結構不一樣
b. 施加在其上的操作不同
c. 所包含的資料元素的型別不一樣
d. 儲存實現不一樣
答案:b
7. 考慮下列四種排序方法,在排序過程中,關鍵碼比較的次數與記錄的初始排列順序無關的
是()a. 直接插入排序和快速排序
b. 快速排序和歸併排序
c. 直接選擇排序和歸併排序
d. 直接插入排序和歸併排序
答案:c
8. 具有24個記錄的序列,採用氣泡排序最少的比較次數是()
a. 1
b. 23
c. 24
d. 529
答案:b
9. 對檔案進行直接訪問的是根據()
a. 邏輯記錄號去訪問某個記錄
b. 邏輯記錄的關鍵字去訪問某個記錄
c. 邏輯記錄的結構去訪問某個記錄
d. 邏輯記錄的具體內容去訪問某個記錄
答案:a
10. 通常要求同一邏輯結構中的所有資料元素具有相同的特性,這意味著()
a. 資料元素具有同一特點
b. 不僅資料元素所包含的資料項的個數要相同,而且對應資料項的型別要一致
c. 每個資料元素都一樣
d. 資料元素所包含的資料項的個數要相等
答案:b
11. 如果二叉樹中任何乙個結點的值都小於它的左子樹上所有結點的值而大於右子樹上所有結
點的值,要得到各結點值的遞增序列,應按下列哪種次序排列結點()
a. 先根
b. 中根
c. 後根
d. 層次
答案:b
12. 順序查詢法適用於儲存結構為()的線性表。
a. 雜湊儲存
b. 壓縮儲存
c. 順序儲存或鏈結儲存
d. 索引儲存
答案:c
13. 在桶排序中,其平均時間複雜度是()
a. a
b. b
c. c
d. d
答案:b
14. 如果以鍊錶作為棧的儲存結構,則退棧操作時()
a. 必須判別棧是否滿
b. 判別棧元素的型別
c. 必須判別棧是否空
d. 對棧不作任何判別
答案:c
15. 乙個佇列的輸入序列是1,2,3,4,則佇列的輸出序列是()
a. 4,3,2,1
b. 1,2,3,4
c. 1,4,3,2
d. 3,2,4,1
答案:b
二、填空題(本大題共10小題,每小題2分,共20分)請在每小題的空格中填寫上正確
答案。錯填、不填均無分。
1. 設有乙個已按各元素的值排好序的線性表,長度為125,對給定的k值,用二分法查詢與k相
等的元素,若查詢成功,則至少需要比較___次,至多需比較___次。
答案:1 7
2. ___的鄰接矩陣不一定是不對稱的。
答案:有向圖
3. 對於乙個具有n個結點的單鏈表,在已知p結點後插入乙個新結點的事件的時間複雜性為
___,在給定值為x的結點後插入乙個新結點的時間複雜性為___。
答案:o(1) o(n)
4. 對快速排序來講,其最好情況下的時間複雜度是___,其最壞情況下的時間複雜度是___。
答案:5. 無向圖的鄰接矩陣是___,並且主對角線上的元素的值為___。
答案:對稱零
6. 設乙個鏈棧的棧頂指標為ls,棧中結點兩個字段分別為info和next,其中next是指示後繼
結點的指標,棧空的條件是___。如果棧不空,則退棧操作為p:=ls;___;dispose(p)。
答案:ls=null這是指鏈棧沒有設定頭結點的情況,一般情況下也不必設定
ls:=ls↑.next;這一操作讓頭指標指示下乙個結點
7. 計算機軟體系統中,有兩種處理字串長度的方法:一種是採用___,第二種是___。
答案:固定長度設定長度指標
8. 棧和佇列均可視為特殊的線性表,所不同的在於對這二種特殊線性表___和___運算的限定
不一樣。
答案:插入刪除
9. ___與資料元素本身的內容和形式無關。
答案:資料的邏輯結構
10. 在計算機軟體系統中,有兩種處理字串長度的方法:一種是採用___,第二種是設定
___。
答案:固定長度長度指標
三、解答題(本大題共4小題,每小題5分,共20分)
1. 已知一棵二叉樹的前序遍歷序列是abdgcefh,其中序遍歷序列為dgbaechf。請畫出相應的
二叉樹,並求出對應此二叉樹的後序遍歷序列,此二叉樹是完全二叉樹嗎?完全二叉樹有什麼性
質(特點)?
答案:根據二叉樹的遍歷規則,前序遍歷總是先訪問根結點,然後依次遍歷其左右子樹,而中序
遍歷規則是先遍歷左子樹,再訪問根結點,然後訪問右子樹,則由以上規則,我們極易得出此二
叉樹的根結點是a,中序遍歷序列中,根結點左右兩邊的結果分別屬於其左、右子樹,所以得出
左子樹包含3個節點:b,d,g,右子樹包含四個結點c,e,f,h。在左子樹中,先序遍歷序b位
於最前,而中序遍歷序列中,b位於最後,則可以得出結點b無右子樹,只有左子樹,又在b的子
樹中,無論先序遍歷還是中序遍歷,d都位於g的前面,則g只能是d的右孩子,且d無左孩子,按
照以上分析規則,我們同樣可以分析出此二叉樹的右子樹的結構。從而我們得到了此二叉樹的最
終結構為:此二叉樹的後序遍歷序列為:gdbehfca
從求出的二叉樹的形狀我們可以看出此二叉樹不是完全二叉樹,完全二叉樹的性質是:一棵完全
二叉樹只有最下面的兩層的結點數可以小於2,並且最下面一層的結點都集中在該層最左邊的若
幹位置上。
2. 試分別畫出具有3個結點的樹和具有3個結點的二叉樹的所有不同的形態。
答案:含有三個結點的樹只有兩種形式[見(1)和(2)];含有3個結點的二叉樹有5種形態[見
(3),(4),(5),(6),(7)]
對於一棵普通的樹來說,圖(4),(5),(6),(7)是完全相同的,但如果它們作為二叉樹,則表示
不同的二叉樹,因為在一棵二叉樹中,每個結點的孩子都有左右之分,即使某節含有乙個孩子
,則此孩子結點仍有左右點之分。
3. 請根據下面所給出的鄰接矩陣畫出相應的有向圖或者是無向圖(頂點vi表示)。
答案:a,b,c對應的圖分別為:
4. 對於下面的3個廣義表,請畫出其圖形表示式,並說明它們各屬於什麼型別的廣義表。
(1)b(a(x,l(a,b)),y)
(2)c(a(x,l(a,b)),b(a(x,l(a,b)),y))
(3)d(a,d(a,d(…)))
答案:廣義表對應的圖形如下圖所示,其中圖1為樹形結構,所以是純表,圖2中結點a為共享結
點,則它屬於再入錶,圖3中因為存在遞迴,則它屬
於遞迴表。
四、演算法閱讀題(本大題共4小題,每小題5分,共20分)
1. 以下運算實現在迴圈隊上判隊空,請在___處用適當的語句予以填充。
int emptycycqueue(cycqueuetp sq)
答案:2. 以下是圖的廣度優先搜尋演算法,請在___處填充適當的語句。
bfs(graphtp g,int v)
___;
} }}答案:enqueue(&q,v) outqueue(&q,&v) p=p->nextarc
3. 以下運算實現在順序棧上的退棧,請在___處用適當的語句予以填充。
int pop(sqstacktp *sq,datatype *x)
else
更多優質自考資料盡在百度貼吧自考樂園俱樂部
(歡迎加入...歡迎交流...止不住的驚喜等著你.........
}答案:sq->data[sq->top] sq->top--
4. 以下運算實現在鏈棧上的進棧,請在___處用適當的語句予以填充。
void push(lstacktp *ls,datatype x)
答案:p->data=x ls=p
五、演算法設計題(本題10分)
1. 若輸入12000個不同的整數,其值介於0和19999之間,採用雜湊表儲存這些數,雜湊函式為
h(k)=k/2,請設計實現的演算法。
2023年全國自考資料結構模擬試卷 九 及答案
更多優質自考資料盡在貼吧自考樂園俱樂部 歡迎加入.歡迎交流.止不住的驚喜等著你.2010年全國自考資料結構模擬試卷 九 一 單項選擇題 本大題共15小題,每小題2分,共30分 在每小題列出的四個備選專案中 只有乙個是符號題目要求的,請將其 填寫的括號內.錯選 多選或未選均無分。1.當初始序列已經按鍵...
02331自考全國資料結構試題
a.a,b,cb.a,b,c c.a b,cd.a,b,c 8.二維陣列a按行優先順序儲存,其中每個元素佔1個儲存單元。若a 1 1 的儲存位址為420,a 3 3 的儲存位址為446,則a 5 5 的儲存位址為 a.470b.471 c.472d.473 9.二叉樹中第5層上的結點個數最多為 a....
全國自考試題資料結構試卷
全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題,每小題2分,共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的,請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和...