本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)01》復(fù)習(xí)題一選擇題（每題2分，共20分）

1．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的___c___結(jié)構(gòu)；A）存儲(chǔ)B）物理C）規(guī)律D）物理和存儲(chǔ)2．算法分析的目的是：c

A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）研究算法中的輸入和輸出的關(guān)系C）分析算法的效率以求改進(jìn)D）分析算法的易懂性和文檔性3．計(jì)算機(jī)算法必需具備輸入．輸出和_b______等５個(gè)特性．

Ａ）可行性、可移植性和可擴(kuò)展性B)可行性、確定性和有窮性Ｃ）確定性、有窮性和穩(wěn)定性Ｄ）易懂性、穩(wěn)定性和安全性

４．一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是___b____A）110B）108C）100D）120

5設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作:A)連接B)模式匹配C)求子串D)求串長

6.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變,平均要移動(dòng)____b___個(gè)元素A)8B)63.5C)63D)7

7設(shè)矩陣A是一個(gè)對(duì)稱矩陣,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中,對(duì)下三角部分中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)K的值是:（矩陣是A[1][1]開始）B

A)i(i-1)/2+j-1B)i(i_1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j8.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu),所以__c_____

A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)B）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)C）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)D）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用

9.有8個(gè)結(jié)點(diǎn)的無向連通圖最少有__c_____條邊（邊數(shù)＝節(jié)點(diǎn)－1）A)5B)6C)7D)8

10.所有排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排列次數(shù)無關(guān)的是___d____

A)希爾B)冒泡C)插入D)選擇二.填空題(每題2分,共20分)

1.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示,它們分別是順序_______、鏈?zhǔn)絖______、索引_______和散列_______。

2.在一個(gè)循環(huán)隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的前一個(gè)_______位置。3.向一個(gè)長度為n的向量的第i個(gè)元素(1≤i≤n=1)之前插入一個(gè)元素時(shí),需向后移動(dòng)____n-i+1__個(gè)元素,刪除第i個(gè)元素(1≤i≤n)時(shí),需向前移動(dòng)_n-i_____個(gè)元素。4.向量、棧和隊(duì)列都是__線性_____結(jié)構(gòu),可以在向量的任何_______位置插入和刪除元素;對(duì)于棧只能在_棧頂______插入和刪除元素;對(duì)于隊(duì)列只能在__隊(duì)尾____插入和_____隊(duì)頭__刪除元素。

5.在動(dòng)態(tài)存儲(chǔ)管理中的三種分派策略是首次擬合_______、_最正確擬合______和___最差擬合____。

6.廣義表(((a)))的表頭是__（（A））_____,表尾是_____（）__。7.已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBAD’。寫出模式

串的nextval函數(shù)值_______。P（77）

8.一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為不大于k=log2(n)最大整數(shù)8_____。

9．n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間繁雜度為___O（n^2）____；

若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間繁雜度為O(n+e)_______。

10．已知序列{32，17，18，60，40，7，73，65，85}，給出快速排序第一趟的結(jié)果（升序），并給出該序列的初始小根堆_______。(堆排序先右后左。先建樹，快速排序：記位置，交換)

三．判斷題（每題2分，共10分）

1、線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型（棧和隊(duì)列），而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)繁雜類型。f

2、順序表結(jié)構(gòu)適合于進(jìn)行順序存取，而鏈表適合于進(jìn)行隨機(jī)存取。（說反了）f3、鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（雙向鏈表）f

4、用二叉鏈表法（llink-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的２ｎ個(gè)指針區(qū)域中有n＋1個(gè)為空指針。t

５、二分查找同順序查找一樣，對(duì)數(shù)據(jù)表沒有什么要求。F（有序）四．應(yīng)用題（每題５分，共３０分）１、已知一單向鏈表Ｌ，寫出在指定的Ｐ結(jié)點(diǎn)前成功插入一個(gè)新結(jié)點(diǎn)的有關(guān)語句（包括產(chǎn)生一個(gè)新結(jié)點(diǎn)的有關(guān)語句，并畫出鏈表結(jié)構(gòu)圖）。Link*q,

q=(link*)malloc(sizeof(link));q->data=p->data;q->next=p->next;p->next=q;２、已知二叉樹的先序、中序遍歷序列分別為ＡＢＤＦＪＧＫＣＥＨＩＬＭ和ＢＦＪＤＧＫＡＣＨＥＬＩＭ，試寫出后序遍歷時(shí)得到的結(jié)點(diǎn)序列。３、設(shè)給定權(quán)集Ｗ＝｛２，３，４，７，８，９｝，試構(gòu)造關(guān)于Ｗ的一棵哈夫曼樹和哈夫曼編碼，并求其加權(quán)路徑長度ＷＰＬ。４、給出入如圖Ｇ所示的無向圖的鄰接表，從１點(diǎn)出發(fā)的ＤＳＦ序列和使用Ｐrim算法構(gòu)造的最小生成樹。

１４２３６５5、設(shè)關(guān)鍵字集合為：{10，20，30，50，40}，依次輸入各結(jié)點(diǎn)，畫出平衡二叉樹的構(gòu)造過程。

6、已知一組關(guān)鍵字為{25，36，41，38，44，15，68，12，6，51，26}的數(shù)據(jù)，用線性探查法解決沖突，構(gòu)造這關(guān)鍵字的散列表，并計(jì)算成功查找的平均找長度ASL。

五．編程題（每題10分，共20分）

1、編寫一個(gè)采用雙冒泡進(jìn)行升序排序的算法（即：上下交替進(jìn)行）。2、編寫一個(gè)計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目遞歸算法。

試卷（參考答案）

一、選擇題（20分：每題2分）

1、C2、C3、B4、B5、B6、B7、B8、C9、C10、D二、填空題（20分：每題2分）

1、順序、鏈?zhǔn)健⑺饕蜕⒘?、前一個(gè)3、n-i+1、n-i

4、線性、任意、棧頂、隊(duì)尾、隊(duì)頭5、首次擬合、最正確擬合、最差擬合6、（（a））、（）7、01021018、9

9、O（n2）、O（n+e）

10、快速排序：71718324060736585堆排序：71718604032736585三、判斷題（10分：每題2分）

1、×2、×3、×4、√5、×四、應(yīng)用題（30分，每題5分）

1、

s=(linklist)malloc(sizeof(linknode));

s->data=x;s->next=NULL;s->next=p->next;

p->next=s;p->datas->data;2、LRD序列：JFKGDBHLMIECA

2、

WPL=2*4+3*4+4*3+7*2+8*2+9*2（哈夫曼樹見右圖）

3315哈夫曼編碼：2：00003：0001184：0017：108：1199：0154234、1263197845＾＾56＾＾＾64＾21635533112545415356252336666344256DFS序列：123465

1423

6

5

5、

2010403050（過程略）

6、

表長：m=11/0.75≈15

散列地址：01234567891011121314關(guān)鍵字：512641156844636253812MOD13：1202235610121212比較次數(shù)：42122111123

成功查找的平均查找長度：

ASL=（4+2+1+2+2+1+1+1+1+2+3）/11=20/11=1.82五、編程題（20分：每題10分）

voidBubble_Sort(inta[],intn)//相鄰兩趟是反方向起的冒泡排序算法{low=0;hight=n-1;//冒泡的上下界change=1;

while(lowa[i+1]){a[i]a[i+1];change=1;}

high--;//修改上界

for(i=high;i>low;i--)//從下向上起泡if(a[i]a[i-1];change=1;}

low++;//修改下界}}

intleafs(bitree*t){intnum1,num2