西南科技大學網路教育學院重修補考試題單
課程名稱：資料結構專業班級命題教師：孫敏
學生姓名學號成績
考試時間月日第1頁共4 頁
一. 填空題(每空2分,共20分)
1. 資料元素是__的基本單位
2. 資料結構被形式的定義為(d,s),其中d是__的有限集合,s是d上__的有限集合
3. 計算機演算法指的是___,它的五個特性有:有窮性,_,_,輸入,輸出.
4. 向乙個長度為n的向量中刪除第i個元素(1<=i<=n)時,需向前移動__個元素
5. 單鏈表是__的鏈結儲存表示
6. 一棵有k層的滿二叉樹一共有__個結點,如果它是一棵完全二叉樹,則至少有__個結點.
二. 選擇題 (每題3分,共30分)
1. 計算機演算法指的是____
a) 計算方法b) 排序方法
c) 解決問題的有限操作序列 d) 排程方法
2. 線性結構通常採用的兩種儲存結構是_____。
a) 順序儲存結構和鏈式儲存結構 b) 雜湊方式和索引方式
c) 鍊錶儲存結構和陣列 d) 線性儲存結構和非線性儲存結構
3. 乙個棧的入棧序列是a, b, c, d, e, 則出棧的不可能的輸出序列是__
a) edcba b) dceba c) dceab d) abcde
4. 設n, m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是_____。
a) n在m的右方b） n是m的祖先
c）n 在m的左方d） n是 m的子孫
5. 對線性表進行二分查詢時，要求線性表必須____。
a） 以順序方式儲存 b） 以順序方式儲存，且結點關鍵字有序排序
c） 以鏈結方式儲存 d） 以鏈結方式儲存，且結點關鍵字有序排序
6.在乙個單鏈表中，若p所指結點不是最後結點，在p之後插入s所指結點，則執行____。
a) s->next=p; p->next=sb) s->next=p->next; p->next=s;
c) s->next=p->next; p=sd) p->next=s; s->next=p;
7.具有4個頂點的無向完全圖有_____條邊。
a) 6 b) 12 c) 16 d) 20
8.棧和佇列的共同點是___。
a)都是先進後出 b) 只允許在端點處插入和刪除
c) 沒有共同點 d)都是後進先出
9.串是一種特殊的線性表，其特殊性體現在____。
a) 可以順序儲存b) 資料元素是乙個字元
c) 可以鏈結儲存d) 資料元素可以是多個字元
10.在乙個無向圖中，所有頂點的度數之和等於所有邊數的（ ）倍。
a) 1 b) 2 c) 4d) 1/2
三、判斷題（每小題1分，共10分）
1. 二維陣列可以視為陣列元素為一維陣列的一維陣列
2. 鏈結儲存表示的儲存空間一般在程式的執行過程中動態分配和釋放，通常儲存器中還有空閒儲存空間，就不會產生儲存溢位的問題
3. 在用單鏈表表示的鏈式佇列中，隊頭在鍊錶的鏈尾位置
4. 凡是遞迴定義的資料結構都可以用遞迴演算法來實現它的操作
5. 當向乙個小根堆（最小堆）中插入乙個具有最小值的元素時，該元素需要逐層向上調整，直到被調整到堆頂位置為止
6. 對於一棵具有n個結點，其高度為h的二叉樹，進行任一種次序遍歷的時間複雜度為o（n
7. 進行折半搜尋的表必須是順序儲存的有序表
8. 一棵m階b樹中每個結點最多有m個關鍵碼，最少有2個關鍵碼
9. 在雜湊法中採取開雜湊（鏈位址）法來解決衝突時，其裝載因子的取值一定在（0，1）之間
10. 快速排序肯定是最快的排序方法( )
三．解答題（40分）
1.已知有序序列,請用二分查詢法查詢元素37,並寫出每次查詢比較的過程,用」↑」標示查詢過程的mid元素,分別用」[」 和 」]」標示low和high元素(10分)
2．由如右圖所示的樹,回答以下問題:（6分）
(1) 該樹的深度是_______
(2) 該樹的度是______
(3) 該樹的葉子結點有哪些______
3.閱讀下面的演算法程式,補上空格處的語句(每空2分，共6分)
typedef structsstable; //靜態查詢表的順序儲存結構
int search_bin(sstable st,keytype key)
return 0;
}//search_bin
4. 說明下列歸併過程的功能(10分)
void unknown(bintreenode * t,int i)
}主程式除錯方式unknown ( 0 )
// 二叉樹根結點的層次號為０，其他結點的層次號等於其雙親的層次號加一。
5．假定用於通訊的電文由８個字母a,b,c,d,e,f,g,h組成，各字母在電文**現的頻率分別為試為這８個字母設計不等長huffman編碼，並給出該電文的總碼數。（8分）
a b c d e f g h
電文總長度：
答案一．填空題 (1空2 分共20分)
1．資料 2.資料元素 , 關係 3.有若干條指令組成的有窮序列，可執行性, 確定性 5.
線性表 6. 2^k-1, 2^(k-1)
二． 選擇題 (每題3分,共30分)
caccb,babbb
三． 判斷題（10分）
1.√ 2.√ 3.× 4.√ 5.√ 6.√ 7.√ 8.× 9.× 10. ×
四． 解答題（40分）
1．(8 分)
原始:[3 12 24 37 45 53 61 78 90 100]
↑lowmidhigh
第一次後[3 12 24 37] 45 53 61 78 90 100
low ↑midhigh
第二次後3 12 [24 37] 45 53 61 78 90 100
low ↑high
第三次後3 12 24 [37] 45 53 61 78 90 100
low↑high
mid經過3次比較後，找到了元素37
2． 44c f g l i m k （每個2分，共6分）
3． return 1， high=mid-1， low=mid+1 （每個2分，共6分）
4．以前序順序輸出用二叉鍊錶表示的二叉樹各結點的資料和結點的層次號。（每乙個下劃線標明的概念給２分）
5．已知字母集｛a, b, c, d, e, f, g, h｝
次數則huffman 編碼為
a b c d e f g h
電文總碼數為
資料結構試題
a 排序是按照元素的值或某個域的值排列元素，使之成為有序表 b 線性表的排序不改變表中元素及其各個域的值 c 插入排序演算法的時間複雜度的數量級是o n2 d 對線性表排序不改變元素的儲存順序 8 對單鏈表表示法，以下說法錯誤的是 d a 資料域用於儲存線性表的乙個資料元素 b 指標域用於存放乙個指...
資料結構部分試題
1 資料的邏輯結構包括四種型別。2 在棧中，訪問資料遵循的原則是 3 二分查詢法，表中元素必須按存放 4 雜湊表一般按儲存方式構造的儲存結構 5 圖有和三種結構 6 評價演算法優劣的主要標準是和 7 在佇列結構中，允許插入的一端成為允許刪除的一端稱為8 順序表相對於鍊錶的優點有和 9 解決佇列假溢位...
資料結構基礎試題
資料結構試卷 a卷 考試時間 分鐘閉卷 班級學號姓名成績 一 單項選擇 每空2分，共30分 1.資料結構是一門研究非數值計算的程式設計問題中,資料元素的 資料資訊在計算機中的 以及一組相關的運算等的課程。a 操作物件 計算方法 邏輯結構 資料映象 a 儲存結構 關係運算演算法 2.線性表的邏輯順序與...