演算法期末試卷
Ⅰ 大學期末成績怎麼算，卷面佔百分之八十
Ⅱ 人教版四年級下冊數學期末模擬卷_小學四年級下冊數學期末試卷模板
隨著數學考試的即將來臨，你做好復習的准備了嗎?這份小學數學的模擬卷將會有效的去檢測出你的學習情況。以下是由我收集整理的人教版四年級下冊數學期末模擬卷，希望能夠幫助到你!
人教版四年級下冊數學期末模擬卷一
一、填空：(共20分)
1、在一個三角形中，∠1=105°，∠2=25°，那麼∠3=( )，這是一個( )三角形;一個等腰三角形的底角是60°，它的頂角是( )，這個三角形是( )三角形。
2、0.018裡面有( )個千分之一;9個百分之一寫成小數是( )。
3、把1.8擴大1000倍是( )，縮小到它的千分之一是( )。
4、用0、1、2、3和小數點組成一個最大的小數是( )，組成最小的小數是( )。
5、306900改成用“萬”作單位的數是( )，把387330000改成用“億”作單位的數是( )。
6、把一個小數的小數點先向右移動兩位，再向左移動三位，得到的數比原數( )。
7、 由5個0.1，6個0.01和8個0.001組成的數是( )。
8、 95分米=( )米， 5432米=( )千米。
480公頃=( )平方千米 6500平方米=( )公頃
5.005公頃=( )公頃( )平方米 ，4.05千米=( )千米( )米
9、1.96≈( )(精確到十分位); 3.068≈( )(保留兩位小數)。
7.995≈( )(精確到十分位)，7.99596≈( )(保留兩位小數)
7.99986≈( )(保留三維小數)
10、三角形的內角和是( )度，長方形的內角和是三角形內角和的( )倍。
二、計算題(36分)。
1、口算：(6分)
3.64+0.48= 50-37.5= 11.6+1.4= 60÷5= 48÷8×9= 400×6=
11×800= 0×60÷12= 2.5+0.9= 0.39+0.61= 528-53-47=
192-128= 41.5-41.5= 360÷30= 5×99+5= 0.058×100=
2、計算下面各題，並且驗算：(6分)
41.2-15.6 21.56+6.74
3、計算下面各題：(能簡算的要簡算)(18分)
6.7+25+3.3+75 103×12 14.85-(4.85+2.5)
15×99+15 9.14-1.43-4.57 2000÷125÷8
4、文字題：(6分)
(1)5.38加上9.36與3.72的差,和是多少?
(2)已知兩個數的和是85.7，其中一個加數是15.7，
求另一個加數是多少?
三、判斷題。(6分)
1.A+B+C=A+(B+C)。 ( )
2.在小數後面添上“0”或去掉“0”，小數的大小不變 .( )
3.0.596保留兩位小數是0.6。 ( )
4.0.80元和0.8元都表示8角。 ( )
5把7.6先擴大100倍，再縮小10倍後是76.4。 ( )
6、因為0.3=0.30，所以他們表達的意義也相同。 ( )
四、操作題：(8分)
(1)畫出一個直角等腰三形，並求出這個三角形的另外兩個角的度數。(4分)
3 (2)畫出下面三角形各底上的高。(4分)
五、應用題。(22分)
1、珠海計程車起步價為3千米收費7元，3千米以上，每增加1千米收費1元，不足1千米按一千米收費請完成下表：(4分)
路程(千米) 3 4 5 .6 8收費 (元)
2、地球表面積是5.1億平方千米,其中陸地面積是1.49億平方千米,海洋面積比陸地面積多多少億平方千米?(4分)
3、一根電線，用去32.87米，比剩下的多8.99米，這根電線長多少米?(4分)
4、 甲有14.8元，乙有15.2元，兩人要合買一個 足球 ，一個足球的價錢是他倆錢數總和的2倍，一個足球多少元，他們還差多少元?(5分)
5，100千克油菜籽可榨油21.6千克的油,照這樣計算,1噸油菜籽可榨油多少千克的油?(5分)
人教版四年級下冊數學期末模擬卷二
一、填空。(16%)
1、8.745保留一位小數是(8.7)，0.398精確到百分位是(0.40 )。
2、310.04讀作(三百一十點零四);零點三零七 寫作(0.307 )。
3、5.903是由(5)個1，(9)個0.1，(0)個0.01，(3)個0.001組成的。
4、把一個小數的小數點向右移動三位，再向左移動兩位，這個數是40.9。原來這個小數是(4.09)。
5、三角形具有(穩定)性;三角形的內角和是(180°)。
6、計算48×98+48×2時，運用(乘法分配)律可以使計算簡便。
7、不改變數的大小，把4.5改寫成三位小數是(4.500)。
8、一個等腰三角形的一個底角是350，它的頂角是(110)度。
9、一根木頭長6米，要把它鋸成4段。每鋸一段需要5分鍾，鋸完一共需要(15)分鍾。
二、判斷題。(正確的畫“√”，錯誤的畫“×”)(6%)
1、在表示近似數的時候，小數末尾的零不能去掉。……………………(√ )
2、乘法分配律用字母表示為(a+b)c=ac+bc……………………………(√ )
3、等邊三角形每個內角都是60度。………………………………………(√ )
4、被減數等於減數，差一定是0。…………………………………………(× )
5、用三個完全一樣的直角三角形可以拼成一個梯形。……………………(√)
6、0.078擴大100倍是78。………………………………………………(×)
三、選擇題。(把正確答案的番號填在括弧里。)(6%)
1、三角形任意任意兩邊的和(②)第三邊。
① 等於 ② 大於 ③ 小於 ④ 大於或等於
2、0.0385精確到( ④ )位是0.039。
① 十分位 ② 百分位 ③ 個位 ④ 千分位
3、小於6.98的數是( ④ )。
① 7 ② 6.980 ③ 6.99 ④ 6.890
4、78×99用簡便 方法 計算是( ② )。
① 78×100+78×1 ② 78×100-78
③ 78×100+1 ④ 78×100-1
5、把改寫成小數是( ③ )。
① 0.13 ② 0.130 ③ 0.013 ④ 0.0013
6、雞、鴨、鵝、狗各一隻，一共重28千克，雞和鴨一樣重，鵝重是鴨的3倍，狗重是鵝的3倍。鵝重( ③ )。
① 2千克 ② 8千克 ③ 6千克 ④ 18千克
四、計算。
1、口算。(6%)
0.36+0.14= 7.2-5.8= 1-0.4=
1-0.08= 4.8+3.12= 0.01+0.1=
3.9+4.4+5.1= 4.7-0.47-1.43= 102×5=
25×17×4= 120÷5÷2= 20-20÷5=
2、用豎式計算，並驗算。(6%)
48.5+47.25= 20.8-6.48=
人教版四年級下冊數學期末模擬卷三
1、一個沒有括弧的算式里，如果只有加、減法或者只有乘、除法，要按( )順序依次運算;如果既有加、減法又有乘、除法，要先算( )，後算( )。
2、一個算式里，有括弧的應先算( )，後算( )。
3、0不可以做( )數。
4、加法結合律用字母表示是(a+b)+c=( )。
5、乘法分配律用字母表示a×(b+c)=( )。
6、21.003讀作( )
7、六點零八八寫作：( )
8、一個數十位和百分位上是3，十分位和個位上是0，這個數是( )
9、0.8是8個( )分之一。0.32是( )個百分之一。
10、在( )中，填上“>”、“<”或“=”。
21×1( )21+1 12×5+5( )12×(5+5)
84÷12×2( )84÷(12÷2) 123-23+77( )123-(23+77)
56×99+1( )56×(99+1)
11、整數部分的最低位是( )位，小數部分的最高位是( )位，它們之間的進率是( )。
三、我能判，對的打“√”錯的打“×”(5分)1、(125+8)×8=125×8+8 ( )
2、65+75+25=65+(75+25)，這是應用了加法的結合律. ( )
3、0.09的計數單位是0.01 ( )
4、805的末尾添上兩個“0”，數的大小不變。 ( )
5、a-b-c=a-(b+c) ( )
四、我會選。(5分)
1、小數點的右邊第二位是( )
A.十分位 B.百分位 C.十位
2、把40.06讀作( )
A.四零點零六 B.四十點六 C.四十點零六
3.在計算25×166×4=25×4×166=100×166=16600中應用的運算定律是( )
A.乘法分配律 B.乘法交換率 C.乘法結合律
4、715×99的簡便演算法是( )。
A、715×90×9 B、715×100+715 C、715×100-715
5、小芳在小華的南偏西25º方向200米處，那麼小華在小芳的 ( )方向200米處。
A.西偏南75º B。北偏東25º C.西偏南25º
猜你還感興趣的：
1. 人教版四年級下冊數學期末試卷及答案
2. 新人教版四年級上冊數學期末模擬卷
3. 四年級下冊數學期末試卷
4. 四年級數學下冊期末試卷
5. 四年級下冊數學試卷
6. 四年級下冊數學期末復習試題
Ⅲ 誰有數據結構的期末試題，借我參考下馬上考試了
A：
06－07第一學期期末考試試卷
試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為(K,R)，其中K是數據元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存儲 D.關系
2.線性表若採用鏈式存儲結構時，要求內存中可用存儲單元的地址____。
A.必須連續的 B.部分地址必須連續的 C.一定是不續的 D.連續不連續都可以
3.一個棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是____。
A.edcba B.decba C.dceab D.abcde
4.一個隊列的入隊序列是1、2、3、4，則隊列輸出序列是____。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.棧和隊列的共同點是____。
A.都是先進後出 B.都是先進先出
C.只允許在端點處插入、刪除元素 D.沒有共同點
6.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行____。
A. s->next = p->next; p->next=s; B. p->next = s->next; s->next = p;
C. q->next = s; s->next = p; D. p->next = s; s->next = q;
7.設串s1=『ABCDEFG』，s2=『PQRST』，函數con (x, y) 返回x與y串的連接串，函數subs (s, i, j) 返回串s的從序號i的字元開始的j個字元組成的子串，函數len (s) 返回串s的長度，則con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的結果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷結點訪問順序是dgbaechf，則其後序遍歷結點訪問順序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6個頂點的無向圖至少應有____條邊才能確保是一個連通圖。
A. 5 B. 6 C. 7 D. 8
11.採用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為–。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
12.排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列(註：初始時為空)的一端的方法，稱為____。
A. 希爾排序 B. 歸並排序 C. 插入排序 D. 選擇排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在樹形結構中，樹根結點沒有 結點，其餘每個結點有且只有 個前驅結點。
2.對n個元素的序列進行起泡排序時，最少的比較次數是 。
3.空串是 ，其長度等於0。
4.一棵有n個結點的滿二叉樹共有 個葉子結點。
5.在散列函數H(key)=key % p中，p應取 。
6.已知模式串t=『abcaabbabc』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.在對線性表的處理中一般使用兩種存儲結構，順序存儲結構和鏈式存儲結構。試敘述在什麼情況下使用順序表比鏈表好？
2.簡述什麼是穩定的排序，什麼是不穩定的排序。
3.下列中綴表達式對應的後綴形式是什麼？
(1) (A + B) * D + E / (F + A * D) + C
(2) A && B|| ! (E > F) {註：按C的優先順序)
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.數據元素不是數據的最小單位( )。
2.已知一棵二叉樹的前序序列和後序序列可以唯一地構造出該二叉樹。( )
3.AOE網是一種帶權的無環連通圖。( )
4.對於同一組待輸入的關鍵碼集合，雖然各關鍵碼的輸入次序不同，但得到的二叉搜索樹都是相同的( )。
5.一棵樹中的葉子數一定等於與其對應的二叉樹的葉子數。( )
6.鄰接表只能用於有向圖的存儲，鄰接矩陣對於有向圖和無向圖的存儲都適用。( )
7.折半插入排序是穩定的。( )
8.在散列法中，使用雙散列函數可保證絕對不產生沖突。( )
9.消除遞歸不一定需要使用棧( )
10.堆排序是交換排序的一種。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1．閱讀後分析下面程序段的功能是什麼? （6分）
SeqStack S1, S2, tmp;
DataType x; //設棧tmp和S2已做過初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( S2, x);
}
2.某子系統在通信聯絡中只可能出現8種字元，其出現的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設計赫夫曼編碼。（7分）
3.設散列表為HT[13], 散列函數為 H (key) = key %13。用線性探測再散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試寫出使用希爾排序(增量為5,2,1)方法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.編寫一個演算法frequency，統計在一個輸入字元串中所含各個不同字元出現的頻度。用適當的測試數據來驗證這個演算法。(10分)
2.在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，並統計樹中具有度為1的結點數目的演算法。要求給出二叉鏈表的類型定義。(8分)
答案：
06－07第一學期
期末考試參考答案與評分標准
試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(每小題2分，共24分。)
1. D 2. D 3. C 4. B 5. C 6. C
7. D 8. B 9. D 10. A 11. C 12. D
二、填空題(每空1分，共7分。)
1.父(或前驅)， 1
2. n-1
3. 不包含任何字元的串
4. (n+1)/2
5. 素數
6. 0111223123
三、簡答題(每小題5分，共15分)
1.答：① 順序存儲時，相鄰數據元素的存放地址也相鄰(邏輯與物理統一)；要求內存中可用存儲單元的地址必須是連續的。
優點：存儲密度大，存儲空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式存儲時，相鄰數據元素可隨意存放，但所佔存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針
優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小(<1)，存儲空間利用率低。
順序表適宜於做查找這樣的靜態操作；鏈表宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查找，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鏈表。
2.答：在排序序列中，任何兩個相等的關鍵字Ki=Kj,如果在排序前的序列中Ki領先於Kj，若在排序後的序列中Ki仍領先於Kj，則稱所用的排序方法是穩定的；反之，若可能使排序後的序列中Kj領先於Ki，則稱所用的排序方法是不穩定的。
3.答：各中綴表達式的後綴形式如下：
(1)AB+D*EFAD*+/+C+
(2)AB&&EF>!||
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.T 10.F
五、分析應用題（1、4小題各6分，2、3小題各7分）
1．（6分）
答：程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去。
2．（7分）
答：為方便起見，設各種字元的權值w={5,29,7,8,14,23,3,11}。因為n=8，所以要構造的赫夫曼樹共有m=2n-1=2*8-1=15個結點。生成的赫夫曼樹為下圖所示：
赫夫曼編碼為：概率為0.23的字元編碼為：00
概率為0.11的字元編碼為：010
概率為0.05的字元編碼為：0110
概率為0.03的字元編碼為：0111
概率為0.29的字元編碼為：10
概率為0.14的字元編碼為：110
概率為0.07的字元編碼為：1110
概率為0.08的字元編碼為：1111
3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用線性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
搜索成功的平均搜索長度為：
ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10
4.（6分）
答： 希爾排序(增量為5,2,1)
六、演算法設計題（第1小題10分，第2小題8分）
1. (10分)
include <iostream.h>
include」string.h」
int charnumber=128;
void frequency(string&s,int C[ ]){
for(int i=0;i< charnumber;i++) C[i]=0;
for( i=0;i< s.length();i++) C[atoi(s[i])]++;
for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<」(」<<i<<」):\t」<<C[i]<<」\t」;
}
2. (8分)
類型定義（略）
int Level(BiTree bt) //層次遍歷二叉樹，並統計度為1的結點的個數
{
int num=0; //num統計度為1的結點的個數
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉樹結點指針為元素的隊列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p->data); //出隊,訪問結點
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)
num++;//度為1的結點
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入隊
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入隊
}
}
return(num); //返回度為1的結點的個數
}
B：
06－07第一學期期末考試試卷
試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為 (K, R)，其中K是____的有限集，R是K上的關系有限集。
A.演算法 B.數據元素 C.數據操作 D.邏輯結構
2.在數據結構中，從邏輯上可以把數據結構分成____。
A.動態結構和靜態結構 B.緊湊結構和非緊湊結構
C.線性結構和非線性結構 D.內部結構和外部結構
3.以下的敘述中，正確的是____。
A.線性表的存儲結構優於鏈式存儲結構
B.二維數組是其數據元素為線性表的線性表
C.棧的操作方式是先進先出
D.隊列的操作方式是先進後出
4.若一個棧的入棧序列是1、2、3、… 、n，其輸出序列為p1、p2、p3、… 、pn，若p1=n，則pi為____。
A. i B. n = i C. n - i +1 D.不確定
5.判斷一個循環隊列QU (最多元素為m) 為空的條件是____。
A. QU->front == QU->rear B. QU->front != QU->rear
C. QU->front == (QU->rear+1)%m D. QU->front != (QU->rear+1)%m
6.在某單鏈表中，已知p所指結點不是最後結點，在p之後插入s所指結點，則執行____。
A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s; D. p->next = s; s->next = p;
7.串是一種特殊的線性表，其特殊性體現在____。
A.可以順序存儲 B.數據元素是一個字元
C.可以鏈接存儲 D.數據元素可以是多個字元
8.已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是____。
A. acbed B. decab C. deabc D. cedba
9.對於一個滿二叉樹，m個樹葉，n個結點，深度為h，則____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1
10.一個有n個頂點的無向圖最多有____條邊。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
11.順序查找法適合於存儲結構為____的線性表。
A. 散列存儲 B. 順序存儲或鏈接存儲
C. 壓縮存儲 D. 索引存儲
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B.選擇排序 C.快速排序 D. 歸並排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在線性結構中，第一個結點 前驅結點，其餘每個結點有且只有1個前驅結點。
2.在無權圖G的鄰接矩陣中，若A[i][j]等於1，則等於A[j][i] = 。
3.根據二叉樹的定義，具有三個結點的二叉樹有 種不同的形態。
4.空格串是指 ，其長度等於 。
5.在散列存儲中，裝填因子α的值越大，則存儲元素時發生沖突的可能性就 。
6.已知模式串t= 『abacabaaad』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.比較靜態查找與動態查找的主要區別，它們的基本運算有哪些不同？
2.邏輯結構分哪幾種，存儲結構有哪幾種？
3.在具有n(n>1)個結點的各棵不同形態樹中，其中深度最小的那棵樹的深度是多少？它共有多少葉子和非葉子結點？
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.每種數據結構都應具備三種基本運算：插入、刪除、搜索( )。
2.滿二叉樹不一定是完全二叉樹。( )
3.帶權連通圖的最小生成樹的權值之和一定小於它的其它生成樹的權值之和。( )
4.任一棵二叉搜索樹的平均搜索時間都小於用順序搜索法搜索同樣結點的順序表的平均搜索時間。( )
5.線性鏈表中所有結點的類型必須相同。( )
6.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所佔用的存儲空間大小隻與圖中頂點個數有關，而與圖的邊數無關( )。
7.在散列法中解決沖突時，其裝載因子的取值一定在(0，1)之間。( )
8.任何一個關鍵活動延遲，那麼整個工程將會延遲。( )
9.平衡二叉樹的左右子樹深度之差的絕對值不超過1。( )
10.n個結點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.下述演算法的功能是什麼? （6分）
LinkList Demo(LinkList L)
{ // L 是無頭結點單鏈表
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}
2.將給定的圖簡化為最小的生成樹，要求從頂點1出發。（7分）
3.設散列表為HT[13], 散列函數為 H (key) = key %13。用雙散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函數為 RH (key) = (7*key) % 10 + 1, 尋找下一個地址的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},寫出使用快速排序法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.試設計一個實現下述要求的查找運算函數Locate。設有一個帶表頭結點的雙向鏈表L， 每個結點有4個數據成員：指向前驅結點的指針llink、指向後繼結點的指針rlink，存放字元數據的成員data和訪問頻度freq。所有結點的freq 初始時都為0。每當在鏈表上進行一次Locate(L, x) 操作時，令元素值為x的結點的訪問頻度freq加1，並將該結點前移，鏈接到與它的訪問頻度相等的結點後面，使得鏈表中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。(10分)
2.設一棵二叉樹以二叉鏈表為存貯結構，設計一個演算法將二叉樹中所有結點的左，右子樹相互交換。要求給出二叉鏈表的類型定義。(8分)
答案：
06－07第一學期
期末考試參考答案與評分標准
試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(每小題2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空題(每空1分，共7分。)
1. 無
2. 1
3. 5
4. 串中字元全為空格 ， 空格的個數
5. 大
6. 0112123422 。
三、簡答題(本大題共5小題，每小題5分，共15分)
1．答：兩種查找方法最大的區別在於：
靜態查找方法不修改查找表；動態查找在查找不成功時，將結點插入查找表中，即有可能修改查找表；
靜態查找的基本運算有建表、查找和讀表元；動態查找除上述基本操作外還有初始化、插入和刪除操作；
2.答：根據數據元素之間關系的不同特性，通常有下列四類基本結構：(1)集合；(2)線性結構；(3)樹形結構；(4)圖狀結構或網狀結構。有兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。
3.答：深度最小的那棵樹的深度為2。對於這n個結點，除了一個根結點之外，其餘得n-1個結點均為葉子結點，故其深度為2。該樹葉子結點數為n-1，非葉子結點數為1。
四、判斷題(每小題1分，共10分)
1. (T) 2. (F) 3. (T) 4. (F) 5. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.（6分）
答：該演算法的功能是：將開始結點摘下鏈接到終端結點之後成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。
2.（7分）
答:
3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用雙散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均搜索長度為：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、演算法設計題（第1小題10分，第2小題8分）
1.(10分)
答：
(1) 定義鏈表結構
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始時，所有結點的freq域的值都為0。
(2) 定義函數
DoubleListNode * locate ( DoubleListNode *f ; char &x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳過表頭結點*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*從鏈中摘下p*/
while ( q != f &&q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q後面插入p*/
}
return p;
}
2． (8分)
答：類型定義（略）
void exchange(BiTree bt)//將二叉樹bt所有結點的左右子樹交換
{
if(bt)
{ BiTree s；
s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交換
exchange(bt->lchild); //交換左子樹上所有結點的左右子樹
exchange(bt->rchild); //交換右子樹上所有結點的左右子樹
}
}