11．設c語言陣列data[m]作為迴圈佇列的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句是( )。
y!a. front=front+1;b. front=(front+1)%m;+ c/+ oc. rear=reart+1;d. rear=(reart+1)%m;
…………………密……………封……………線……………密……………封……………線…………………
電腦科學與技術專業資料結構中考試題a07（3、4）班題號一
二三四總分
複核人12.若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）。' h2 h
a. 9b.11c. 15d.不確定得分
13．n個結點的線索二叉樹上含有的線索數為（）。* s0 i
一、單項選擇題（本大題共13小題，每小題1分，共13分，請將正確a. nb. 2nc. n－ld. n＋l2
選項前的字母填在下列**的相應位置。）題號1答案a
2d3d
4c5b
6b7b
8c910111213dab
bd二、判斷題(每小題1分，共12分。判斷下列各題，正確的打「√」，錯的打「×」，請將答案填在下列**的相應位置。)
題號1234
5678
9101112
學號姓名
1、演算法的時間複雜度與有關。
(a)問題規模(b)計算機硬體效能(c)編譯程式的質量(d)程式語言2、**性表的下列儲存結構中，讀取元素花費時間最少的是_____。(a)單鏈表(b)雙鏈表(c)迴圈鍊錶(d)順序表3、線性表採用鏈式儲存結構時，其位址
(a)必須是連續(b)一定是不連續(c)部分位址必須是連續(d)連續與否均可4、設有一棧，元素依次進棧順序為a，b，c，d，e。下面( )是不可能的出棧（a）abcde（b）bcdeab（c）eabcd（d）edcba,5、串是一種特殊的線性表，其特殊性體現在a)可以順序儲存(b)資料元素是乙個字元(c)可以鏈結儲存(d)資料元素可以是多個字元6、對矩陣壓縮儲存是為了
(a)方便運算(b)節省空間(c)方便儲存(d)提高運算速度7、將遞迴演算法轉換成對應的非遞迴演算法時，通常需要使用儲存中間結果。(a)佇列(b)棧(c)鍊錶(d)樹
8、二叉樹若用順序方法儲存，則下列4種運算中的______最容易實現。(a)先序遍歷二叉樹(b)判斷兩個結點是否在同一層上(c)層次遍歷二叉樹(d)根據結點的值查詢其儲存位置9．帶頭結點的單鏈表head為空的判斷條件是（）
(a)head = =null(b)head! =null9 -(c)head->next= =head(d)head->next==null
10.在單鏈表中，指標p指向結點a，若要刪除a之後的結點（存在），則指標的操作方式為( )。
a. p-> next= p-> next-> next;b. p= p-> next;c. p= p-> next-> next;d. p-> next=p;%
答案1．單鏈表中的頭結點就是單鏈表的第乙個結點。
2.順序表和一維陣列一樣，都可以按下標隨機（或直接）訪問。3、二叉排序樹中，新結點總是作為樹葉來插入的。
4、在用迴圈單鏈表表示的鏈式佇列中，可不設隊頭指標，僅在鏈尾設定隊尾指標。5、在哈夫曼樹中，權值相同的樹葉結點都在同一層上。6、二叉樹就是結點度為2的樹。
7、棧底元素和棧頂元素有可能是同乙個元素。
8、無論是順序佇列還是鏈結佇列，插入、刪除運算的時間複雜度都是o(1)。9、線性表的順序儲存結構優於鏈式儲存結構。
10、對於單鏈表來說，只有從頭結點開始才能掃瞄表中全部結點。11、用非遞迴方法實現遞迴演算法時一定要使用遞迴工作棧。
12.在一棵二叉樹中，假定每個結點只有左子女，沒有右子女，對它分別進行中序遍歷和後序遍歷，則具有相同的結果。
共5頁第1頁
…………………密……………封……………線……………密……………封……………線…………………
三、應用題（本大題共2小題，共15分）
1、已知一棵二叉樹的中序序列是cbedahgijf，後序序列為cedbhjigfa，請畫出該二叉樹，並寫出該二叉樹先序序列。
解：該二叉樹如下圖：
33189943
7158a
bfcd
eh其先序序列是：abcdefghij。
（評分標準：正確畫出圖，5分，正確寫出先序序列，3分）52j
gi學號姓名
其加權路徑長度wpl=(9+7+8)*2+4*3+(2+3)*4=80
(評分標準：正確畫出圖，給5分；正確計算wpl，給3分；若不完全正確則酌情給分)
四.演算法設計題：(每題8分，共5小題，共計40分)
2、設給定權集散地w=，試構造關於w的一棵哈夫曼樹，並求其1、設計乙個演算法，將x插入乙個有序（從小到大排序）的線性表（順加權路徑長度wpl。
解：解：設這8個字母所對應的權值分別為（5，25，4，7，9，12，30，8），並且n=8。（1）赫夫曼樹為：（4分）
1004357
18272530
915912
5847
（2）在上面求出的赫夫曼樹中規定左分支表示「0」，右分支表示「1」（如右圖所示），則可以構造赫夫曼編碼為：a:0011 b:
01 c:0010 d:1010 e:
000 f:100 g:11 h:
1011（4分）
序儲存結構）的適當位置上，並保持線性表的有序性。
解：儲存結構如下：typedef struct sqlistsqlist;演算法如下：
void insertordersqlist(sqlist &l, elemtype x)
(評分標準：正確寫出儲存結構可給2分，演算法正確給6分，不完全正確則酌情給分)
共5頁第2頁
…………………密……………封……………線……………密……………封……………
3、已知乙個不帶頭結點的單鏈表head，結點結構為node。寫出乙個通用的演算法，
2、設計乙個演算法，將乙個帶頭結點的資料域依次為a1, a2,…, an（n≥3）
刪除鍊錶中值相同的結點（如果有值相同的結點只保留首次出現的結點）。例如，刪除前：yhead&
的單鏈表的所有結點逆置，即第乙個結點的資料域變為an，最後乙個結
刪除後：fhead2 g# d; r8 z" j,
預編譯命令：# definenull0//null表示空指標
點的資料域變為a1。
結點結構：
解：儲存結構如下：typedefstruct node7 ^2 b( m+ j1 `% h9 d4typedef struct lnodenode;+ v' o! u/ b-
}lnode, *linklist;演算法如下：
voidreverse(linklist&h)}
(評分標準：正確寫出儲存結構可給2分，演算法正確給6分，不完全正確則酌情給分)
解：node * expurgate (node * head)
//7分else//8分}
p=p->next;//9分}
return(head);//10分}
學號姓名
共5頁第3頁
…………………密……………封……………線……………密……………封……………
5、假設二叉樹採用二叉鍊錶儲存結構儲存，設計乙個演算法，刪除該二叉樹，並釋放所有的結點。
4、假定二叉樹採用二叉鏈儲存結構儲存，試設計乙個演算法，計算一棵給定二叉樹的所有結點的個數。
解：儲存結構如下：
解：儲存結構如下：typedef struct bitnodetypedef struct bitnodebitnode, *bitree;}bitnode, *bitree;演算法如下：
演算法如下：voiddeletebitree(bitree &t)int nodes(bitree &t)deletebitree(t->right);(評分標準：正確寫出儲存結構可給2分，演算法正確給6分，不完全正確則酌情給分，演算法可以寫delete(t); t=0;成遞迴演算法，也可以寫成非遞迴演算法)}
}(評分標準：正確寫出儲存結構可給2分，演算法正確給6分，不完全正確則酌情給分，演算法可以
寫成遞迴演算法，也可以寫成非遞迴演算法)
學號姓名
共5頁第4頁
共5頁第5頁
資料結構考試題
要求 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。1.資料結構是指 a.一種資料型別 b.資料的儲存結構 c.一組性質相同的資料元素的集合 d.相互之間存在一種或多種特定關係的資料元素的集合 2.以下演算法的時間複雜度為 void fun int n a.o n...
資料結構試題,模擬考試題
資料結構試題 單選題在資料結構的討論中把資料結構從邏輯上分為 c a 內部結構與外部結構b 靜態結構與動態結構 c 線性結構與非線性結構d 緊湊結構與非緊湊結構。2 採用線性鍊錶表示乙個向量時，要求占用的儲存空間位址 d a 必須是連續的b 部分位址必須是連續的 c 一定是不連續的d 可連續可不連續...
資料結構期末考試題及答案
2012年資料結構期末考試題及答案 一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d ...