數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型(5篇)

每個人都曾試圖在平淡的學(xué)習(xí)、工作和生活中寫一篇文章。寫作是培養(yǎng)人的觀察、聯(lián)想、想象、思維和記憶的重要手段。范文怎么寫才能發(fā)揮它最大的作用呢？接下來小編就給大家介紹一下優(yōu)秀的范文該怎么寫，我們一起來看一看吧。

數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型篇一

1．排序算法比較

利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進行排序，并且（1）統(tǒng)計每一種排序上機所花費的時間。

（2）統(tǒng)計在完全正序，完全逆序情況下記錄的比較次數(shù)和移動次數(shù)。（3）比較的指標為關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)(一次記錄交換計為3次移動)。

（4）對結(jié)果作簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。2．圖的深度遍歷

對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判?？眨崿F(xiàn)圖的深度優(yōu)先搜索遍歷。畫出搜索順序示意圖。3．圖的廣度遍歷

對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索遍歷。畫出搜索順序示意圖。4．二叉樹的遍歷

對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。畫出搜索順序示意圖。5．鏈表操作

利用鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數(shù)、輸出等運算反復(fù)實現(xiàn)鏈表的這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。畫出搜索順序示意圖。6．一元稀疏多項式簡單計數(shù)器（1）輸入并建立多項式

（2）輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2……cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列。（3）多項式a和b相加，建立多項式a+b，輸出相加的多項式。（4）多項式a和b相減，建立多項式a-b，輸出相減的多項式。用帶頭結(jié)點的單鏈表存儲多項式。測試數(shù)據(jù)：

（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．實現(xiàn)兩個鏈表的合并 基本功能要求：（1）建立兩個鏈表a和b，鏈表元素個數(shù)分別為m和n個。

（2）假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線性表c，使得：

當m>=n時，c=x1,y1,x2,y2,…xn,yn,…,xm 當n>m時，c=y1,x1,y2,x2,…ym,xm,…,yn 輸出線性表c：

（1）用直接插入排序法對c進行升序排序，生成鏈表d，并輸出鏈表d。測試數(shù)據(jù)：

（1）a表（30，41，15，12，56，80）

b表（23，56，78，23，12，33，79，90，55）

（2）a表（30，41，15，12，56，80，23，12，34）b表（23，56，78，23，12）8．哈夫曼編碼的實現(xiàn)與應(yīng)用

（1）從文件中讀入任意一篇英文短文（至少含3000個字符，文件為ascii編碼的文本文件）

（2）統(tǒng)計不同字符在文章中出現(xiàn)的頻率（空格、換行、標點等也按字符處理）（3）根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼。

（4）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率

（5）根據(jù)相應(yīng)哈夫曼編碼，對編碼后的文件進行解碼，恢復(fù)成ascii編碼的英文短文后輸出。

分析及設(shè)計步驟（供參考）

1.分析問題，給出數(shù)學(xué)模型，設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。

1)分析問題特點，用數(shù)學(xué)表達式或其它形式描述其數(shù)學(xué)模型。2)選擇能夠體現(xiàn)問題本身特點的一種或幾種邏輯結(jié)構(gòu)。

3)依據(jù)邏輯結(jié)構(gòu)和問題特點，設(shè)計并選擇相應(yīng)的存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)對應(yīng)的算法實現(xiàn)有區(qū)別）。

2.算法設(shè)計

1)確定所需模塊：對于復(fù)雜的程序設(shè)計，要充分利用模塊化程序設(shè)計方法和面向?qū)ο笏枷?，自頂向下，逐步細化?/p>

2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調(diào)用關(guān)系：給出算法各模塊之間的關(guān)系圖示。3.上機實現(xiàn)程序

為提高工作效率，充分利用上機調(diào)試時間，在上機之前應(yīng)列出程序清單。

4.用有代表性的各種測試數(shù)據(jù)去驗證算法及程序的正確性

5.算法分析及優(yōu)化

經(jīng)過上機調(diào)試，源程序運行正確，并且實現(xiàn)算法要求的功能，解決課程設(shè)計題目中給出的問題后，分析算法的時間復(fù)雜度和空間復(fù)雜度，如有可能對程序進行優(yōu)化改進。

課程設(shè)計報告范例（參考）

約瑟夫環(huán)問題。

問題描述：設(shè)編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù)；如此下去，直到所有人全部出列為止。要求設(shè)計一個程序模擬此過程，并給出出列人的編號序列?；疽螅?/p>

（1）初始報數(shù)上限值m和測試數(shù)據(jù)在程序中確定；（2）用帶頭結(jié)點的單循環(huán)鏈表作數(shù)據(jù)元素的存儲結(jié)構(gòu)；（3）把帶頭結(jié)點的單循環(huán)鏈表作為抽象數(shù)據(jù)類型設(shè)計。測試數(shù)據(jù)：

n = 7，七個人的密碼依次為3,1,7,2,4,8,4 初始報數(shù)上限值m = 20 算法思想：

jesephring()函數(shù)是實現(xiàn)問題要求的主要函數(shù)，其算法思想是：從1至m對帶頭結(jié)點的單循環(huán)鏈表循環(huán)計數(shù)，到m時，輸出該結(jié)點的編號值，將該結(jié)點的密碼作為新的m值，再從該結(jié)點的下一個結(jié)點起重新自1起循環(huán)計數(shù)；如此下去，直到單循環(huán)鏈表空時循環(huán)過程結(jié)束。模塊劃分：

（1）帶頭結(jié)點的單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist，其中包括基本操作的函數(shù)有：初始化操作函數(shù)、插入一個結(jié)點操作函數(shù)、刪除一個結(jié)點操作函數(shù)、取一個結(jié)點數(shù)據(jù)操作函數(shù)和判表是否非空操作函數(shù)。該抽象數(shù)據(jù)類型文件名為sclinlist.h。

（2）void sclldeleteafter(sclnode *p)，其功能是刪除帶頭結(jié)點的單循環(huán)鏈表中指針p所指結(jié)點的下一個結(jié)點。這是對帶頭結(jié)點的單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist，補充本問題需要的一個操作函數(shù)。（3）void jesephring(sclnode *head, int m)，其功能是對帶頭結(jié)點的單循環(huán)鏈表head,以m為初始報數(shù)上限值實現(xiàn)問題要求。

（4）void main(void)，主函數(shù)，功能是給出測試數(shù)據(jù)值，建立測試數(shù)據(jù)值的帶頭結(jié)點單循環(huán)鏈表，調(diào)用jesephring()函數(shù)實現(xiàn)問題要求。數(shù)據(jù)結(jié)構(gòu)：

（1）數(shù)據(jù)類型datatype定義如下： typedef struct { int number;int cipher;} datatype;

（2）帶頭結(jié)點單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist。

（3）帶頭結(jié)點單循環(huán)鏈表抽象數(shù)據(jù)類型的結(jié)點結(jié)構(gòu)定義如下：

typedef struct node { datatype data;struct node *next;} sclnode;源程序：

源程序存放在兩個文件中，文件sclinlist.h是帶頭結(jié)點單循環(huán)鏈表抽象數(shù)據(jù)類型，文件exam3-9.c是主程序。

文件sclinlist.h： typedef struct node { datatype data;struct node *next;} sclnode;/*結(jié)點結(jié)構(gòu)定義*/ void scllinitiate(sclnode **head)/*初始化*/ { if((*head =(sclnode *)malloc(sizeof(sclnode)))== null)exit(1);(*head)->next = *head;} int scllinsert(sclnode *head, int i, datatype x)/*插入一個結(jié)點*/ { sclnode *p, *q;int j;p = head->next;j = 1;while(p!= head && j < i1 && i!= 1){ printf(“插入位置參數(shù)錯！”);return 0;} if((q =(sclnode *)malloc(sizeof(sclnode)))== null)exit(1);q->data = x;q->next = p->next;p->next = q;return 1;} int sclldelete(sclnode *head, int i, datatype *x)/*刪除一個結(jié)點*/ { sclnode *p, *q;int j;p = head;j = 0;while(p->next!= head && j < i1){ printf(“刪除位置參數(shù)錯！”);return 0;} q = p->next;p->next = p->next->next;*x = q->data;free(q);return 1;} int scllget(sclnode *head, int i, datatype *x)/*取一個結(jié)點數(shù)據(jù)元素值*/ { sclnode *p;int j;p = head;j = 0;while(p->next!= head && j < i){ p = p->next;j++;} if(j!= i){ printf(“取元素位置參數(shù)錯！”);return 0;} *x = p->data;return 1;} int scllnotempty(sclnode *head)/*鏈表非空否*/ { if(head->next == head)return 0;else return 1;} 文件exam3-9.c： #include

#include

typedef struct { int number;int cipher;} datatype;/*定義具體的數(shù)據(jù)類型datatype*/ #include “sclinlist.h” /*包含sclinlist抽象數(shù)據(jù)類型*/ void sclldeleteafter(sclnode *p)/*刪除p指針所指結(jié)點的下一個結(jié)點*/ { sclnode *q = p->next;p->next = p->next->next;free(q);} void jesephring(sclnode *head, int m)/*對帶頭結(jié)點單循環(huán)鏈表head，初始值為m的約瑟夫環(huán)問題函數(shù)*/ { sclnode *pre, *curr;int i;pre = head;curr = head->next;while(scllnotempty(head)== 1){ for(i = 1;i < m;i++){ pre = curr;curr = curr->next;if(curr == head){ pre = curr;curr = curr->next;} }

各種排序比較結(jié)果（參考）

直接插入的比較圖表***030002500直接插入的移動圖表比較次數(shù)2000系列1******4738291100次數(shù)移動次數(shù)2000系列1******4738291100次數(shù) 冒泡的比較次數(shù)***00冒泡的移動圖表***00比較次數(shù)移動次數(shù)*********1100執(zhí)行次數(shù)系列*********91100次數(shù)系列1

shell的比較次數(shù)12001000800***01200shell的移動圖表比較次數(shù)移動次數(shù)******1100執(zhí)行次數(shù)系列******564738291100次數(shù)系列1

快速排序的比較次數(shù)800700600快速排序的移動圖表540520500比較次數(shù)移動次數(shù)******4738291100執(zhí)行次數(shù)系列******8291100次數(shù)簡單選擇的移動圖表350300250系列1

簡單選擇的比較次數(shù)***0比較次數(shù)移動次數(shù)300025002000******4738291100執(zhí)行次數(shù)堆排序的比較次數(shù)107010601050系列1200系列1******8291100次數(shù) 堆排序的移動圖表***0比較次數(shù)移動次數(shù)*********00執(zhí)行次數(shù)系列117401720******65564738291100次數(shù)系列1

數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型篇二

數(shù)據(jù)結(jié)構(gòu)試題6

一、單項選擇題（每小題3分，共30分）

1．設(shè)棧的輸入序列是1、2、3、4，則______不可能是其出棧序列。

（）[a] 1234

[b] 2134

[c] 1432

[d] 4312

2．在一個具有n個結(jié)點的線性鏈表中查找某個結(jié)點，若查找成功，需要平均比較_____個結(jié)點。

（）[a] n

[b] n/2

[c](n+1)/2

[d](n-1)/2

3．設(shè)每個字符占一個字節(jié)，二維數(shù)組 a中每個元素有6個字符組成，其行下標從0到9，列下標從0到3，元素_____當a按行優(yōu)先存儲起始地址與當a按列優(yōu)先存儲的起始地址相同。

（）[a] a[3][0]

[b] a[3][1]

[c] a[3][2]

[d] a[2][3]

4．具有2000個結(jié)點的非空二叉樹的最小深度為_______。

（）[a] 9

[b] 10

[c] 11

[d] 12

5．已知某二叉樹的后根序列是dabec，中根序列是debac，則先根序列是_____。

（）[a] acbed

[b] decab

[c] deabc

[d] cedba 6.無向圖中所有邊的數(shù)目等于所有頂點的度數(shù)之和的_____倍。

（）[a] 1

[b] 2

[c] 1/2

[d] 不一定

7．遞歸函數(shù)f(n)=f(n-1)+n+1(n>1)的遞歸體是_______。

（）[a] f(0)=0

[b] f(1)=1

[c] f(n)=n+1

[d] f(n)=f(n-1)+n+1 8.若需要在o(nlog2n)的時間內(nèi)完成對 n個元素的排序，且要求排序是穩(wěn)定的,則可選擇的排序方法是_______。

（）[a] 快速排序

[b] 堆排序

[c] 歸并排序

[d] 直接插入排序

9．在對n個元素的序列進行排序時,堆排序所需要的附加存儲空間是__。（）

[a] o(1)

[b] o(log2n)

[c] o(n)

[d] o(n log2n)

10．假定有k個關(guān)鍵字互為同義詞，若用線性探查法把這k個關(guān)鍵字存入散列表中，則總的探查次數(shù)至少為______。

()

[a] k-1

[b] k

[c] k+1

[d] k（k+1）/22

二、填空題（每小題2分，共20分）

1．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為______，在表尾插入元素的時間復(fù)雜度為________。

2.在一棵二叉樹中，第5層(根結(jié)點為1層)上的結(jié)點數(shù)最多為____________。

3.一棵高度為h的理想平衡樹中，最少含有______個結(jié)點，最多含有________個結(jié)點。

4.在一個小根堆中，堆頂結(jié)點的值是所有結(jié)點中的_________，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的_________。

5.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要_________條邊。

6．假定一個圖具有n個頂點和e條邊，貝采用鄰接矩陣、鄰接表表示時，其相應(yīng)的空間復(fù)雜度分別為__________和___________。

7．以二分查找方法查找一個線性表時，此線性表必須是_________存儲的________表。

8．在線性表的散列存儲中，處理沖突有___________和___________兩種方法。

9．快速排序在平均情況下的空間復(fù)雜度為_____，在最壞情況下的空間復(fù)雜度為_____。

10．在一棵20階 b_樹中，每個非樹根結(jié)點的關(guān)鍵字數(shù)目最少為_______個,最多為____。

三、判斷題（認為對的，在題后的括號內(nèi)打“√”，錯的打“ⅹ”，每小題 １分，共１０）

1．線性表中，每個結(jié)點都有一個前驅(qū)和一個后繼。

（）

2．有向圖的鄰接表和逆鄰接表中的結(jié)點數(shù)一定相同。

（）

3.單鏈表中要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結(jié)構(gòu)。

（）

4.在快速排序、歸并排序和shell排序中，穩(wěn)定的是shell排序。

（）5.對不同的存儲結(jié)構(gòu)，檢索的方法不同。

（）

6.在散列表中，負載因子值越小則存元素時發(fā)生沖突的可能性就越大。

（）

7.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹。

（）

8.若一棵二叉樹的樹葉是某子樹對稱序周游序列中的第一個結(jié)點，則它 必是該子樹后序周游序列中的第一個結(jié)點。

（）

9.二叉樹按線索化后，任一結(jié)點均有指向其前驅(qū)和后繼的線索。

（）

10.在采用線性探查法處理沖突的散列表中，所有同義詞在表中相鄰。

（）

四、簡答題（每題10分，共60分）

1．說明數(shù)組和鏈表的區(qū)別，各有何優(yōu)缺點？

2．回答下列關(guān)于堆的一些問題：

（1）堆的定義是什么？

（2）存儲表示是順序的，還是鏈式的？

（3）設(shè)有一個最小堆，其具有最小值、最大值的元素分別可能在什么地方？

3．完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)最合適，為什么？

4.在直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排 序和歸并排序中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？

5．用下列三種表示法畫出下圖g的存儲結(jié)構(gòu)

（1）相鄰矩陣

（2）鄰接表

（3）鄰接多重表

6．已知序列（70，83，100，65，10，32，7），請給出采用插入排序法對該序列作升序排序時的每一趟結(jié)果。

五、算法設(shè)計題（每題15分，共30分）

說明：可以使用任何高級程序設(shè)計語言或偽（類）程序設(shè)計語言。

1．已知非空單鏈表第一個結(jié)點由 list 指出，寫一算法，交換p 所指結(jié)點（不是鏈表中第一個結(jié)點,也不是鏈表中最后的那個結(jié)點）與其下一個結(jié)點在鏈表中的位置，并給出算法的時間復(fù)雜度。

2．設(shè)計一個算法，統(tǒng)計一個采用鄰接矩陣存儲、具有n個頂點的無向無權(quán)圖所有頂點的度。

數(shù)據(jù)結(jié)構(gòu)試題6答案

一、1.d 2.c 3.b 4.c 5.d 6.c 7.d 8.c 9.a 10.d

二、1．o（n）o（1）

2．16

3．2 h 一 h 一1

4．最小值 最大值

5．n一1

6．o（n 2）o（n十e）、7．順序 有序

8．開放定址法 鏈接法（次序無先后）

9．o（1og2n）

o（n）

10．9

三、1.x

2.√

3.x 4.x

5.√

6.x

7.x

8.√

9.x

10.x

四、1．區(qū)別：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點的空間連續(xù)。

各有何優(yōu)缺點：（1）插入和刪除操作。數(shù)組插入和刪除需移動數(shù)據(jù)元素，鏈表插入和刪除不移動數(shù)據(jù)元素，鏈表比數(shù)組易于實現(xiàn)插入和刪除操作；（2）在空間占用方面，數(shù)組優(yōu)于鏈表；

（3）在數(shù)據(jù)存取方面，數(shù)組是隨機存取方式，而2 鏈表是順序存取方式。2．（1）堆是 n個元素的有限序列 k1，k2，? , kn，且滿足以下條件: ki <= k2i 且ki <= k2i+

1i=1,2,?, n/2（最小堆）

或ki >= k2i 且ki >= k2i+1

i=1,2,?, n/2（最大堆）

（2）因為完全二叉樹采用順序存儲更加有效，所以堆應(yīng)采用順序存儲結(jié)構(gòu)。

（3）最小堆的最小值元素必在堆頂，最大值的元素只有在葉結(jié)點上。

3．完全二叉樹用一維數(shù)組實現(xiàn)最合適。（1）不存在空間浪費問題；（2）順序存儲方式下，父子結(jié)點之間的關(guān)系可用公式描述，訪問結(jié)點方便。采用鏈表存儲存在空間浪費問題，且不易尋找父結(jié)點。

4.在上述排序方法中，只有直接插入排序、冒泡排序、直接選擇排序易于在鏈表上實現(xiàn)。

5.相鄰矩陣：

鄰接表：

鄰接多重表：

6．初

始：（70），83，100，65，10，32，07 第1趟：（70，83），100，65，10，32，07 第2趟：（70，83，100），65，10，32，07 第3趟：（65，70，83，100），10，32，07 第4趟：（10，65，70，83，100），32，07 第5趟：（10，32，65，70，83，100），07 第6趟：（07，10，32，65，70，83，100）

五、算法的 adl描述如下：

算法change(list,p)q←list

while(next(q)<>p)do

q←next(q)r←next(p)next(q)←r next(p)←next(r)next(r)←p

算法的時間復(fù)雜度為o(n)

2．假設(shè)鄰接矩陣為 adjacency（二維數(shù)組），頂點的度保存在一維數(shù)組a中。

算法的 adl描述如下： [初始化]

for i=1 to n do a[i]←0

for i=1 to n do for j=1 to n do

if adjacency[i,j]=1 then

a[i]←a[i]+1

數(shù)據(jù)結(jié)構(gòu)試題7

一、單項選擇題（每小題 2 分，共 20 分）

1．序列 a,b,c,d,e 順序入棧,不能獲得的序列是:（）

a．a(chǎn)bcde

2.通常算法分析中算法的空間復(fù)雜度是指:（）

a.所需全部空間大小 b.完成運算所需輔助空間大小 c.待處理數(shù)據(jù)所需全部空間大小 d.存儲空間的復(fù)雜程度

n樹是:（）

a.最佳二叉樹

b.路徑長度最短的二叉樹

c.最佳二叉排序樹 d.加權(quán)路徑長度最短的二叉樹

4.在單鏈表中刪除 p指針後的節(jié)點 q 需要修改的指針域個數(shù)為:（）a．2

b.4

c.6

d.1

5．設(shè) n0,n1,n2 分別是二叉樹中度為 0,1,2 的結(jié)點數(shù),則有:（）a．n0=n2+1

b.n0=n2-1

c.n0=n1+1

d.n0=n1-1 6．下列說法中錯誤的是：（）

a.n 個結(jié)點的樹的各結(jié)點度數(shù)之和為 n-1

b.n 個結(jié)點的有向圖最多有 n*(n-1)條邊 c.用相鄰矩陣存儲圖時所需存儲空間大小與圖中邊數(shù)有關(guān) d.散列表中碰撞的可能性大小與負載因子有關(guān)

7． 若線性表采用順序存儲結(jié)構(gòu)，每個元素占用 4個存儲單元，第一個元素的存儲地址為 100，則第 12 個 元素的存儲地址是：（）a． 113

b.144 c.148 d.412

8.下列哪一種排序方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關(guān)？（）a.直接插入排序 b.起泡排序 c.快速排序 d.直接選擇排序

9.設(shè)有 5000 個無序的元素，希望用最快的速度挑選出其中前 50個最大的元素，最好選用:（）

a.冒泡排序 b.快速排序 c.堆排序 d.基數(shù)排序

10.用某種排序方法對序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的 變化情況如下，則所采用的排序方法是:（）

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84

a．選擇排序 b．希爾排序 c．歸并排序 d．快速排序

二、判斷題（每小題 1 分，共 10 分，對的打√，錯的打×）

1.給出不同輸入序列建造二叉排序樹，一定得到不同二叉排序樹。（）2.有向圖的鄰接表和逆鄰接表中的結(jié)點數(shù)一定相同。（）

3.圖 g 的拓撲序列唯一，則其弧數(shù)必為 n-1(其中 n為 g 的頂點數(shù))。（）4.在索引順序文件中插入新的記錄時，必須復(fù)制整個文件。()

5.如果某種排序算法是不穩(wěn)定的，則該方法沒有實際的應(yīng)用價值。（）6.對 n 個記錄進行冒泡排序，在最壞情況下所需要的時間是 o(n 2)（）7.在線性結(jié)構(gòu)中，每個結(jié)點都有一個直接前驅(qū)和一個直接后繼。（） 樹的任何子樹都是 avl樹。（）

9.b＋樹既適于隨機檢索，也適于順序檢索。（）

10.兩個字符串相等的充要條件是兩個串包含的字符相同。（）

三、填空題（每空 1 分，共 15分）

1．用起泡法對 n 個關(guān)鍵碼排序，在最好情況下，只需做__次比較和 _______次移動； 在最壞的情況下要做___ _ _ _次比較。

2．若按層次順序?qū)⒁豢糜衝個結(jié)點的完全二叉樹的所有結(jié)點從1到n編號，那么當i為_____且大于 1時，結(jié)點i 的左兄弟是結(jié)點___ _，否則結(jié)點 i 沒有左兄弟。

3．具有 n 個結(jié)點的完全二叉樹的深度為________。

4.樹的三種主要的遍歷方法是：__

__ ____、____

____和層次遍歷。

5．采用散列技術(shù)實現(xiàn)散列表時，需要考慮的兩個主要問題是： _____和解決_____ ___。

6．在一個帶頭結(jié)點的單循環(huán)鏈表中，p 指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針 head

可用 p 表示為 head=_______。

7．棧頂?shù)奈恢檬请S著_______、_________操作而變化的。

8． 已知一棵完全二叉樹中共有 768 結(jié)點，則該樹中共有_______個葉子結(jié)點。

四、簡答題（第 1、2 題每小題 6 分，第 3、4、5 題每小題 8 分，共 36 分）1．已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下圖 1 所示

(1)畫出該圖的圖形；

（2）根據(jù)鄰接矩陣從頂點 a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,寫出相應(yīng)的遍歷序列。

（圖1）

（圖2）

2．將上圖 2所示的二叉樹轉(zhuǎn)換為樹或樹林（畫出連線-刪線圖和結(jié)果圖）。

3：設(shè)有一組關(guān)鍵碼序列：

{6097,3485,8129,407,8136,6615,6617,526,12287,9535,9173,2134,1903,99} 和散列函數(shù)：h(key)=key mod 19。采用線性探測法解決沖突，試在 0～18 的散列地址空間中對該關(guān)鍵碼序列構(gòu)造散列表。

4．設(shè)有關(guān)鍵碼集合 k={72，73，71，23，94，16，05，68}，將其建成一個堆（畫出每步所 得的圖即可）。

5．從一棵空的 avl 樹開始，將關(guān)鍵碼 xal,wan,wil,zol,yo,xum 逐個插入，畫出每插入一 個關(guān)鍵碼后得到的 avl 樹。

五、算法設(shè)計（19 分）

用類 pascal語言或類 c 語言寫出將 n 個記錄用冒泡排序法進行升序排 序的算法(第一次冒泡將排序碼最小的記錄放在第一個位置，第二次冒泡將排序碼次最小的 記錄放在第二個位置 ? ?)。

數(shù)據(jù)結(jié)構(gòu)試題7答案

一． 1.d 2.a

3.d

4.d

5.a

6.c

7.b

8.d 9.c 10.d 二． 1．× 2.√ 3.√ 4.× 5.× 6.√ 7.× 8.√ 9.× 10.×

三．

1． n-1 0 n(n-1)/2

2． 奇數(shù) i-1

3． [log2n]+1

4． 先根 后根

5．選取好的散列函數(shù) 沖突（碰撞）

6． p↑.next↑.next

7． 進棧 退棧

8． 384 四．1.2、深度：a,b,d,e,c 廣度：a,b,e,d,c3、4、5、五、type node=record

var i,j:integer;

key:integer;

flag:0..1;info:datatype

x:node;end;

r:arrar[1..n] of node;for i:=1 to n do begin flag:=0;

for j:=n-1 to i do if r[j+1].key

then 算法結(jié)束

end

數(shù)據(jù)結(jié)構(gòu)試題8 一.單項選擇題(每小題 1 分,15 分)

1.編號為 a,b,c,d 的四輛列車,順序開進棧式結(jié)構(gòu)的站臺,則開出車站的順序中,不可能出 現(xiàn)的次序為:（）

2.兩個同義詞子表結(jié)合在一起的現(xiàn)象稱為:（）a.碰撞 b.拉鏈 c.鏈接 d.堆積

3.一棵二叉樹若前序和對稱序周游得到的節(jié)點序列相同,則這棵二叉樹滿足:

（）a.只能是一個節(jié)點的二叉樹 b.為空二叉樹或者該樹所有節(jié)點的左子樹為空二叉樹

c.只能是空二叉樹 d.為空二叉樹或者該樹所有節(jié)點的右子樹為空二叉樹

4.一棵深度為m的滿三叉樹定義為:或者是空三叉樹,或者是第m層有3 1 ? m 個葉節(jié)點,其余 各層的節(jié)點均有三棵(左,中,右)非空子三叉樹.對該樹按層自左向右從 1 開始順序編號, 則編號為 n的節(jié)點,其父節(jié)點若存在,則父節(jié)點編號為:（）

5.有 n 個節(jié)點的有向完全圖的邊數(shù)為:（）

a.n

b.n(n-1)c.2n

d.n(n-1)/2 6.廣義表 l=(((),()),(),())的長度為:（）

a.3

b.0

c.4

d.5

7.設(shè) h(key)為散列函數(shù),key 為記錄的關(guān)鍵字.在散列表中,記錄 r1 和 r2 的關(guān)鍵字分別為 key 1 和 key 2 ,稱他們?yōu)橥x詞的條件是:（） 1 =key 2

1 =key 2 且 h(key 1)=(key 2)c.r1=r2

1 ≠ key 2 且 h(key 1)=(key 2)8.下面那一個不是存儲管理考慮的問題:（）

a.壓縮碎片問題 b.無用節(jié)點收集 c.表節(jié)點的順序 d.空間溢出管理

9.不能存儲二叉樹的存儲結(jié)構(gòu)為:（）

a.三叉鏈表 b.散列表 c.順序表 d.二叉鏈表2 10．a(chǎn)vl 數(shù)不平衡后要調(diào)整的情形有:（）a.2 種 b.4 種 c.6 種 d.8 種

11．在排序過程序中,使用輔助存儲空間為 o（n）的算法是:（）a.插入排序 b.歸并排序 c.起泡排序 d.快速排序

12．若無向圖中有 n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:（）a.2e

b.2e+n

c.2e+1

d.e+2n 13．字符串的緊縮存儲形式是每個字符占:（）

a.1 個二進制位 b.1 個字節(jié) c.1 個字 d.1 個結(jié)點單元

14．循環(huán)隊列 sq有 m 個單元,其滿隊條件是:（）a.(+1)mod m=

= c.=m

d.=m 15．通常算法分析中算法的空間復(fù)雜度是指:（）

a.所需全部空間大小 c.完成運算所需輔助空間大小 b.待處理數(shù)據(jù)所需全部空間大小 d.存儲空間的復(fù)雜程度

二.填空題(每空1 分,共 10 分)

1.數(shù)據(jù)結(jié)構(gòu)中的節(jié)點可分為兩大類:___________和___________.2.結(jié)構(gòu)的____________是指數(shù)據(jù)本身所占存儲量/整個結(jié)構(gòu)所占存儲量.3.散列存儲方法的關(guān)鍵問題是________________和________________.4.一棵樹刪去根節(jié)點就變成_______________.5.用二分檢索法進行檢索時,要求節(jié)點事先________________.6.設(shè)圖 g 有 n個節(jié)點,t條邊,若 d i 為節(jié)點 v i 的度數(shù),則 t=___________.7.對于不連通的無向圖和不是強連通的有向圖進行周游,得到的是:________.8.排序方法的穩(wěn)定性是指排序關(guān)鍵字值相同的記錄在排序過程中不改變其原有的 _____________關(guān)系.三．多項選擇題(錯選,多選,漏選均不得分.每小題 2 分,共 6 分)1.根據(jù)描述算法的語言不同，可將算法分為：（）

a.形式算法 b.非形式算法 c.偽語言算法3 d.運行不終止的程序可執(zhí)行部分 e.運行終止的程序可執(zhí)行部分

2.能夠從任意節(jié)點出發(fā)訪問到其余結(jié)點的結(jié)構(gòu)有:（）a.單鏈表 b.循環(huán)鏈表 c.雙鏈表 d.二叉鏈表 e.鄰接表

3.圖的常見存儲結(jié)構(gòu)可以選取:（）a．鄰接表 b.鄰接矩陣 c.逆鄰接表 d.鄰接多重表 e.散列表

四．簡答題(每小題 4 分,共 12 分)

1.快速排序算法是否穩(wěn)定?舉一個具有六個記錄(只考慮排序碼)的例子予以說明.2.穿線樹的最大優(yōu)點是什么? 3.簡述關(guān)鍵碼和排序碼的概念.五．分析計算題(每小題 7 分,共 21分)1.計算如下程序段的時間復(fù)雜度.??

s:=0;for i:=1 to n do begin

t:=1;

while t<=i do begin t:=t*2;s:=s+t end end;?

2.將上三角矩陣(a ij)n * n的上三角元素逐行存放于數(shù)組 b[1..m]中(m 充分大),使得 b[k]=a ij ,且 k=f 1(i)+f 2(j)+c,試推導(dǎo)出函數(shù) f 1(i), f 2(j)和常數(shù) c,要求 f 1(i)和 f 2(j)中不含常數(shù)項.3.關(guān)鍵碼序列{jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec},按字母序號排號序為{apr,aug,dec,feb,jan,jul,jun,mar,may,nov,oct,sep},然后用二分發(fā)進行檢索,計算在等概率條件下檢索成功的平均查找長度.六．綜合題（5+5+8+10+8）

1.分步寫出將下面樹林轉(zhuǎn)換成二叉樹的過程.2．對于下圖給出其鄰接表,并從頂點 1 出發(fā)依據(jù)存儲結(jié)構(gòu)進行深度遍歷,寫出遍歷結(jié)果.3．程序填空:在橫線處填入適當?shù)膬?nèi)容,將程序補充完整.程序功能:在有序表中用二分檢索法查找關(guān)鍵碼為 k的記錄,若找到則返回其位置, 找不到則返回零.類型說明如下:

type node=record

key: integer;info :datatype end;

table=array[1..n] of node;

function binfind(r:table;k:integer):integer;begin

low:=1;hig:=n;_______1_____

while(______2_____)and(y=0)do begin mid : =(low+hig)span 2

if k=r[mid].key then

y:=mid else

if k>r[mid].key then _____3______

else _____4_______

end;binfind:=y;end;4．修改起泡排序算法,反方向進行掃描,即第一趟把排序碼最小的記錄放到最前頭,第 二趟把排序碼次小的放到第二個位置, 第三趟把排序碼第三小的放到第三個位置, 如此反復(fù)進行.用類pascal語言給出該算法的程序.(類型說明與上面第3小題相同)

5．試編寫一個交換二叉樹t中節(jié)點的左右子樹的類pascal語言算法，設(shè)節(jié)點的類型為：

type bitree=^node;node=record data:datatype;lchild,rchild:bitree end;

數(shù)據(jù)結(jié)構(gòu)試題8答案

一、1、a

2、d

3、b

4、c

5、b

6、a

7、d

8、c

9、b

10、b

11、b

12、b

13、b

14、a

15、a

二、1、初等，組合

2、存儲密度

3、散列函數(shù)的選取，沖突（碰撞）的解決

4、樹（森）林

5、按關(guān)鍵碼排序 6、1/2σdi

7、生成樹林

8、相對位置

三、1、b c e

2、b c

3、a b c d

四、1、快速排序是不穩(wěn)定的如對初始類排序碼：81 2 5 82 4 1

經(jīng)第一趟快排后為：〔1 2 5 82 4〕8

1經(jīng)第二趟快排后為： 1 〔2 5 82 4〕81

經(jīng)第三趟快排后為： 1 2 〔5 82 4〕81

經(jīng)第四趟快排后為： 1 2 4 5 8

281

和 82 相對位置發(fā)生了變化

2、由于有了線索的存在而使的周游樹形結(jié)構(gòu)和找結(jié)點在指定次序下的前驅(qū)、后繼的算法變

得很簡單、直截了當。

3、關(guān)鍵碼是其值能唯一確定一個記錄的字段或字段組合，兩個記錄的關(guān)鍵碼不可能相等 排序碼是排序運算的依據(jù)，是結(jié)構(gòu)中的一個或多個字段，兩個記錄的排序碼可以相同

五、1、i=1 時 while 循環(huán)執(zhí)行 1 次

故總排序時間為：σ[㏒ 2(i+1)]=σ[㏒ 2i]

i=2 時 while 循環(huán)執(zhí)行 2 次

≈n㏒ 2 n i=3 時 while 循環(huán)執(zhí)行 2 次

i=4 時 while 循環(huán)執(zhí)行 3 次

i=5，6，7 時 while 循環(huán)執(zhí)行 3 次 i=8 時 while 循環(huán)執(zhí)行 4 次 ?

2、k=n+(n-1)+(n-2)+?+〔n-(i-2)+(j-i+1)〕

=n(i-1)-〔i+2+?+(i-1)〕+j=ni-n-(i+1)(i+2)/2+j=〔i 2 +(2n+3)i〕/2+j-(n+1)所以 f1(i)=〔i 2 +(2n+3)i〕/2;f2(j)=j;c=-(n+1)

3、檢索次數(shù)

平均查找長度為：1/12（1+2*2+3*4+4*5）=37/12

六、1、得到:

2、深度遍歷結(jié)果為：1，2，3，5，4，6，7，83、1、y=0

2、low≤high

3、low：=mid+1

4、high：=mid-1

4、var

r：table;x:node;

i,j:integer;flag:0..1;

1.循環(huán)，i 以-1 為步長，從 1 到 n-1,執(zhí)行(n-1 次冒泡)(1)flag ← 0

(2)循環(huán),j以-1 為步長,從 n到 i+1 執(zhí)行

若 r〔j〕.key＜r〔j-1〕.key 則 flag＜-1

x ← r〔j〕;r〔j〕← r〔j-1〕;r〔j-1〕← x(3)若 flag=0 則跳出循環(huán)

2.算法結(jié)束

5、procedure exchange_lr_node(t:bitree);

begin

if t=nil

then 算法結(jié)束

else begin q ← t ↑.lchild;t↑.lchild←t↑.rchild;t↑.rchild←q;

exchange_lr_node(t↑.lchild);exchange_lr_node(t↑.rchild)end;end;

數(shù)據(jù)結(jié)構(gòu)試題9 一.單項選擇題(每小題 1 分,15 分)1.作為一個算法必須滿足:（）

a.2 個要素 b.4 個要素 c.5 個要素 d.7 個要素

2.雙鏈表中,刪除節(jié)點 p之后的節(jié)點 q 需要修改的指針域的個數(shù)為:（）a.1

b.2

c.3

d.4 3.隊列是一種:（）

a.鏈表 表 c.順序表 表

4.串的求子串運算 substr(‘a(chǎn)bcdef’,2,3)的引用結(jié)果是:（）a． ‘bcd’ b.‘bc’ c.‘cde’ d.‘cd’

5.循環(huán)隊列 sq有 m 個單元,其滿隊條件是:（）

a.=

c. mod m+1= +1=

d. = mod m+1

6.在列主序下順序的存儲數(shù)組 a 4 * 4 的上三角元素 a(3,2)的位置是第:（）a.10 個 b.7 個 c.6 個 d.5 個

7.廣義表 d=(a,d)的深度為:（）

a.2

b.1

c.+

d.–

8.有三個節(jié)點 a,b,c 可以構(gòu)成多少種二叉樹:（）a.5

b.8

c.32

d.30 9.有 n 個節(jié)點的完全二叉樹,其深度為:（）

10.中序序列和后序序列相同的二叉樹是:（）

a.完全二叉樹

b.滿二叉樹

c.所有結(jié)點無左孩子的二叉樹 d.所有結(jié)點無右孩子的二叉樹

11.若有向圖中有 n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:（）a.e

b.2e

c.e-1

d.e+1

12.克魯斯卡爾(kruskal)算法求最小生成樹,是針對那種圖的:（）a.無向圖 b.有向圖 c.連通無向圖 d.連通帶權(quán)圖

13.在排序過程中,使用輔助空間為 o（n）的算法是:（）a.插入法 b.歸并法 c.快速 d.分配

14.在散列結(jié)構(gòu)中,同義詞是指:（）

≠ 且 hash()=hash()

=

= 且 hash()=hash()

= 文件屬于:（）

a.順序文件 b.散列文件 c.索引文件 d.多關(guān)鍵字文件

二.多項選擇題(錯選,多選,漏選均不得分.每小題 1 分,共 5 分)1.在下列算法中,涉及到棧運算的有:（）

a.二叉樹的遍歷 b.廣度優(yōu)先搜索遍歷 c.深度優(yōu)先搜索遍歷

d.表達式求值 e.基數(shù)排序

2.排序算法在最壞執(zhí)行情況下,算法的時間復(fù)雜度是 o(n 2)的有:（）a.插入排序法 b.塊序排序法 c.堆排序法 d.歸并排序法 e.基數(shù)排序法

3.稀疏矩陣通常采用的存儲方式有:（）

a.單鏈表 b.循環(huán)鏈表 c.三元組表 d.散列表 e.十字鏈表

4.根據(jù)排序期間數(shù)據(jù)規(guī)模的大小及數(shù)據(jù)所處存儲器的不同,可以將排序分為:()a.插入排序 b.希爾排序 c.交換排序 d.內(nèi)部排序 e.外部排序

5.能夠從任一節(jié)點訪問到其余節(jié)點的結(jié)構(gòu)有:（）

a.單鏈表 b.循環(huán)鏈表 c.雙鏈表 d.二叉鏈表 e.鄰接表

三.填空題(每空1 分,共10 分)

1.數(shù)據(jù)的基本存儲結(jié)構(gòu)有_________,________,_________,________四種.2.排序方法的穩(wěn)定性是值排序關(guān)鍵字值相同的記錄在排序過程中不改變其原有的 _____________關(guān)系.3.算法的確定性是指每條__________________.4.散列結(jié)構(gòu)中處理沖突的方法基本上可分為兩大類: __________和_________.5.文件的操作主要有:___________和__________兩類.四.判斷改錯題(對的打”√”,錯的打”╳”,并說明理由.每小題 2 分,判斷和說明各得 1 分,判斷3 錯誤,全題無分.共 10分)

1.二叉樹是度為 2 的樹.（）2.堆排序是不穩(wěn)定的,其時間復(fù)雜度為 o(n log 2 n).（）3.隊列是受限的線性表,限制在于節(jié)點的位置相對固定.（）4.要完成樹的層次遍歷一般要利用棧作為輔助結(jié)構(gòu).（）5.圖的最小生成樹如果存在,則一般唯一.（）五.解釋概念題(每小題 3 分,共 9 分)1.三元組表 2.拓撲排序 樹

六.簡答題(共 31分)

1.把下圖森林轉(zhuǎn)化為一棵二叉樹,并畫出主要轉(zhuǎn)化過程圖示.(4 分)

2.給定權(quán)集 w={2,3,4,7,8},試構(gòu)造關(guān)于 w 的一棵哈夫曼樹,并求其加權(quán)路徑長度 wpl 的 值.(6 分)

3.對于下圖給出其鄰接表,并從頂點 1 出發(fā)依據(jù)存儲結(jié)構(gòu)進行廣度遍歷,寫出遍歷結(jié)果.4.有一棵二叉樹其前序序列為 abcdef,中序序列為 bcaedf,畫出此二叉樹的示意圖,并給 出其后序序列的線索樹.(6 分)

5.對于關(guān)鍵字集合{51,28,36,86,7},請建立一個堆,要求畫出堆形成的示意圖.(6 分)

6.在雙鏈表h中,現(xiàn)在要在節(jié)點p之后插入一個節(jié)點q,請寫出插入動作的具體語句.(4分)七.算法設(shè)計（共20 分）

1.數(shù)組 a[1..m]作為循環(huán)隊列的存儲區(qū)域,試編寫一個出隊的類 pascal 語言算法.(6 分)2．利用類 pascal 語言寫出統(tǒng)計二叉樹中節(jié)點個數(shù)的算法（6 分）.3．利用類 pascal 語言寫出快速排序中一趟塊排的算法（8 分）.數(shù)據(jù)結(jié)構(gòu)試題9答案

一、1、c

2、b

3、d

4、a

5、d

6、b

7、c

8、d

9、a

10、d

11、a

12、d

13、b

14、a

15、c

二、1、a c d

2、a b

3、a c d e

4、d e

5、b c

三、1、順序,鏈接,索引,散列

2、相對位置

3、指令必須有確切含義,無歧義性

4、開地址法,拉鏈法

5、修改,檢索

四、1、×

2、√

3、×

4、×

5、×

五、1、三元組表 p244

2、拓撲排序 p229

3、avl樹 p180

六、3、鄰接表存儲表示同 a 卷

六、2 廣度遍歷結(jié)果:1, 2, 6, 3, 4, 7, 8, 5

4、后序:c b e f d a 5、6、q↑.llink←p

q↑.rlink←p↑.rlink p↑.rlink↑.llink←q p↑.rlink←q

七、算法設(shè)計(6+6+8=20′)1、

r=f

then

print(‘underflow’)else

f←f mod m+1

算法結(jié)束

2、type

pointer=↑node

node=record info: datatype;llink, rlink: pointer end var

t: pointer;

count: integer;進入算法時,二叉樹已用二叉鏈表存儲,t指向根結(jié)點,count初值為 0 procedure node_count(t: pointer;var count: integer);begin if t=nil

then 算法結(jié)束

else

begin count:=count+1;node_count(t↑.llink,count);node_count(t↑.rlink,count)end end;

3、type node=record key: integer;info: datatype end;

list=arrap〔1..n〕of node;var x:node;j:0..n;

procedure quickpass(var r:list;l,r:integer;var i:integer);begini:=l;j:=r;x:=r〔i〕;repeatwhile(r〔i〕.key＞=)and(i＜j＝doj:=j-1;if i＜j then

r〔j〕:=r〔j〕;i:=i+1;

while(r〔i〕.key＜=＝and(i＜j＝do i:=i+1;if i＜j then 〔r〔j〕:= r〔i〕;j:=j-1〕 until i=j r〔i〕:=x end

注:整個快速排序 procedure quicksort(var r:list;s,t:integer);begin if s＜t then 〔quickpass(r,s,t,i);quicksort(r,s,i-1);quicksort(r,i+1,t)〕

end;

數(shù)據(jù)結(jié)構(gòu)試題10 一.單項選擇題(每小題 1 分,共 20分)

1.設(shè)n為正整數(shù),以下程序段的執(zhí)行次數(shù)是:

（）

k:=0;s:=1;repeat s:=s+k;k:=k+1 until(k=-n)

a.(2n+3)次

b.2(n+1)次

c.無限多次

d.1 次

2.序列 a,b,c,d,e 順序入棧,不能獲得的序列是:

（）

3.數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括:

（）a.三層次五要素

c.五層次三要素

b.三層次三要素

d.五層次五要素

4.在雙鏈表中要在 p 所指的結(jié)點后插入一個新結(jié)點q,要修改的指針域個數(shù)為:（）

a.2 個

b.4 個

c.6 個

d.8 個

5.在列主序下順序的存儲數(shù)組 a 4 * 4 的下三角元素 a(3,2)的位置是第:

（）

a.5 個

b.6 個

c.7 個

d.10 個

6.n 個結(jié)點順序存儲的完全二叉樹, i(1

7.對任何二叉樹,設(shè) n0,n1,n2 分別是度數(shù)為 0,1,2的結(jié)點數(shù),則有:

（）

a.n0=n2+1

b.n0=n2-1

c.n0=n1+1

d.n0=n1-1

8.對圖(一)的二叉樹,其后續(xù)遍歷結(jié)果為:

（）

圖

（一）

9.結(jié)點可以排在拓撲序列中的圖是:

（）

a.無向圖

b.有向圖

c.有向無環(huán)圖

d.無向有環(huán)圖

10.串的求子串運算 substr(‘a(chǎn)bcdefgh’,4,5)的引用結(jié)果是:

（）

a.‘de’

b.‘defgh’

c.‘efgh’

d.‘bcde’

11.對于記錄r1,r2其健值分別是k1和k2,數(shù)據(jù)為d1和d2,稱r1和r2是同義詞的條件是

（）

a.k1=k2

c.k1=k2且 h(k1)≠h(k2)b.d1=d2

d.k1≠k2 且 h(k1)=h(k2)

12.快速排序?qū)儆?

（）a.插入排序

b.交換排序

c.選擇排序

d.歸并排序

數(shù)不平衡后要調(diào)整的情形有:

（）

a.2種

b.4 種

c.6 種

d.8 種

算法是求圖的:

（）

a.連通分量

b.最短路徑

c.最小生成樹

d.拓撲序列

15.在排序過程序中,使用輔助存儲空間為 o（n）的算法是:

（）

a.插入排序

b.歸并排序

c.起泡排序

d.快速排序

16.若無向圖中有 n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:

（）

a.2e

b.2e+n

c.2e+1

d.e+2n

17.字符串的緊縮存儲形式是每個字符占:

（）a.1 個二進制位

b.1 個字節(jié)

c.1 個字

d.1 個結(jié)點單元

18.循環(huán)隊列 sq有 m 個單元,其滿隊條件是:

（）

a.(+1)mod m=

c.=m =

d.=m

文件屬于:

（）

a.順序文件

b.散列文件

c.多關(guān)鍵字文件

d.索引文件

20．下列說法中錯誤的是：

（）

b.n 個結(jié)點的有向圖最多有 n*(n-1)條邊

c.用相鄰矩陣存儲圖時所需存儲空間大小與圖中邊數(shù)有關(guān)

d.散列表中碰撞的可能性大小與負載因子有關(guān)

二.多項選擇題(錯選,多選,漏選均不得分,每小題 2 分,共 14 分)

1.根據(jù)描述算法的語言不同，可將算法分為：

（）

a.形式算法

b.非形式算法

c.偽語言算法

d.運行終止的程序可執(zhí)行部分

e.運行不終止的程序可執(zhí)行部分

2.圖的常見存儲結(jié)構(gòu)可以選取:

（）a.鄰接表

b.鄰接矩陣

c.逆鄰接表

d.鄰接多重表

e.散列表

3.在下列算法中,涉及到棧運算的有:

（）

a.二叉樹遍歷

b.廣度優(yōu)先搜索

c.深度優(yōu)先搜索 d.構(gòu)造哈夫曼樹

e.表達式求值算法

4.某表組織如下:將元素均勻的分成塊,塊內(nèi)元素不排序,塊之間排序,則查找塊及塊內(nèi)某元素實施的方法是:

（）a.折半查塊 順序查元素

b.順序查塊 順序查元素

c.順序查塊 折半查元素 d.散列法查找數(shù)據(jù)元素

e.折半查塊 折半查元素

5.能夠從任意節(jié)點出發(fā)訪問到其余結(jié)點的結(jié)構(gòu)有:

（）

a.單鏈表

b.循環(huán)鏈表

c.雙鏈表

d.二叉樹表

e.散列表

6.數(shù)據(jù)的邏輯結(jié)構(gòu)與:

（）

a.數(shù)據(jù)元素本身的形式,內(nèi)容有關(guān)

b.數(shù)據(jù)元素本身的形式,內(nèi)容無關(guān)

c.數(shù)據(jù)元素的相對位置有關(guān)

d.數(shù)據(jù)元素的相對位置無關(guān)

e.所含節(jié)點個數(shù)無關(guān)

7.稀疏矩陣通常采用的存儲方式有:

（）

a.單鏈表

b.循環(huán)鏈表

c.三元組

d.散列表

e.正交表

三.判斷說明題(對的打”√”,錯的打”╳”,并說明理由.判斷和說明各得 1 分,判斷錯誤,全題無分.共 10 分)

1.在隊列中,新插入的結(jié)點只能插到隊頭.（）2.二叉樹是度數(shù)最大為2 的樹.（）3.在哈希表中,相同的關(guān)鍵字散列在不同的地址空間上的現(xiàn)象稱為沖突.（）4.堆排序是不穩(wěn)定的,其時間復(fù)雜度為:o(n log2n).（）5.完成樹的深度遍歷一般要利用隊列作為輔助結(jié)構(gòu).（）四.解釋概念題(每小題 4 分,共 12分) 樹

2.稀疏矩陣

3.哈夫曼樹 五.簡答題(每小題 5 分,共 20 分)1.將圖(二)所示二叉樹轉(zhuǎn)化成森林.圖(二)

圖

（三）2.什么是串的壓縮存儲(緊縮格式)? 他有哪些優(yōu)缺點?

3.已知圖g如圖(三)所示,給出其鄰接表,并寫出從1出發(fā)進行深度優(yōu)先和廣度優(yōu)先遍歷的

結(jié)果.4.輸入關(guān)鍵字序列:xal,wan,wil,zdl,yo,xul,yum,試建立建立一棵最佳二叉排序樹.六.綜合應(yīng)用(每小題 12 分,共 24 分)

1.利用類 pascal 語言寫出統(tǒng)計二叉樹中節(jié)點個數(shù)的算法.2.利用類 pascal 語言寫出直接選擇排序的算法.數(shù)據(jù)結(jié)構(gòu)試題10答案

一、1、c

2、d

3、a

4、b

5、c

6、a

7、c

8、a

9、d

10、c

11、b

12、d

13、b

14、b

15、c

16、b

17、b

18、b

19、a 20、d

二、1、b c d

2、a b c d

3、a c e

4、a b

5、b c

6、b d e

7、a c d e或 c d e

三、1、× 對尾

2、× 二叉數(shù)不是樹的特例

3、× 不同,相同

4、√

5、× 不含任何字符,空白字符

四、1、avl 樹

2、稀疏矩陣

3、哈夫曼樹

五、1、2、盡可能將串中多個字符存入同一單元的存儲方式,其優(yōu)點是節(jié)省存儲空間,缺點是對某些運算時間加長.3、深度優(yōu)先：1，2，4，5，3，6，7 廣度優(yōu)先：1，2，3，4，5，6，7

4、六、1、type pointer=↑node node=record

info: datatype;llink,rlink: pointer end;

進入算法時，二叉樹用二叉鏈表存儲。count 初值為0 procedure

count_node(t: pointer;var count: integer);begin

if t≠nil then begin

count:=count+1;count_node(t↑.llink,count);count_node(t↑.rlink,count)end end;

2、type node=record

key: integer;info: datatype end;

list: array〔1..n〕of node var x: node;j: 0..n;以下略

數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型篇三

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目

1.運動會分數(shù)統(tǒng)計（限1 人完成）

任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）

功能要求：

1)可以輸入各個項目的前三名或前五名的成績； 2)能統(tǒng)計各學(xué)?？偡?，3)可以按學(xué)校編號或名稱、學(xué)?？偡?、男女團體總分排序輸出；

4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。5)數(shù)據(jù)存入文件并能隨時查詢

6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運動項目的名稱

輸出形式：有合理的提示，各學(xué)校分數(shù)為整形

界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。

存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；

測試數(shù)據(jù)：要求使用

1、全部合法數(shù)據(jù)；

2、整體非法數(shù)據(jù)；

3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；

2.飛機訂票系統(tǒng)（限1 人完成）

任務(wù)：通過此系統(tǒng)可以實現(xiàn)如下功能：

錄入：

可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）

查詢：

可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；

可以輸入起飛抵達城市，查詢飛機航班情況；

訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）

可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；

退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。

修改航班信息：

當航班信息改變可以修改航班數(shù)據(jù)文件

要求：

根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能；

3.文章編輯（限1 人完成）

功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共n行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；

4.宿舍管理查詢軟件（限1 人完成）

1)任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設(shè)計要求： a.采用交互工作方式

b.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)a.按姓名查詢

b.按學(xué)號查詢

c.按房號查詢

3)打印任一查詢結(jié)果（可以連續(xù)操作）

5.校園導(dǎo)航問題（限1 人完成）

設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。

6.教學(xué)計劃編制問題（限1 人完成）

設(shè)計要求：針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。

7.散列法的實驗研究（限1 人完成）

散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。

8.圖書借閱管理系統(tǒng)（限1 人完成）

主要分為兩大功能：

1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；

9.學(xué)生成績管理（限1 人完成）

實現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。

10.活期儲蓄帳目管理（限1 人完成）

活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設(shè)計要求： 1)能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬； 2)能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。

11.二叉排序樹的實現(xiàn)（限1 人完成）

用順序和二叉鏈表作存儲結(jié)構(gòu)

1)以回車('n')為輸入結(jié)束標志,輸入數(shù)列l(wèi)，生成一棵二叉排 序樹t； 2)對二叉排序樹t作中序遍歷，輸出結(jié)果；

3)輸入元素x,查找二叉排序樹t,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；

12.最小生成樹問題（限1 人完成）

設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。

13.通訊錄的制作（限1 人完成）

設(shè)計目的：用〈〈數(shù)據(jù)結(jié)構(gòu)〉〉中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)，結(jié)合c語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識應(yīng)用到實際軟件開發(fā)中去。設(shè)計內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display();3)查找以姓名作為關(guān)鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設(shè)計要求：

1)每條信息至包含 ：姓名（name）街道（street）城市（city）郵編（eip）國家（state）幾項 2)作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設(shè)計報告

14.哈夫曼編碼/譯碼器（限1 人完成）【問題描述】

設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止?！净疽蟆?/p>

1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(，位于執(zhí)行程序的當前目錄中)2)分別采用動態(tài)和靜態(tài)存儲結(jié)構(gòu)

3)初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼；

6)設(shè)字符集及頻度如下表：

字符 空格 a b c d e f g h i j k l m 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內(nèi)容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設(shè)計的優(yōu)化。

15.圖書管理系統(tǒng)（限1 人完成）【問題描述】

設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù)?！净疽蟆?/p>

1)每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：

*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量?！具M一步完成內(nèi)容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設(shè)計內(nèi)容 4)程序流程圖 5)源程序

6)軟件測試報告（包括所用到的數(shù)據(jù)及結(jié)果）

16.散列表的設(shè)計與實現(xiàn)（限1 人完成）【問題描述】

設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)?！净疽蟆?/p>

1)設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；

2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄。【進一步完成內(nèi)容】 1)系統(tǒng)功能的完善；

2)設(shè)計不同的散列函數(shù)，比較沖突率；

3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

17.順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。（限1 人完成）

設(shè)有一元多項式am(x)和bn(x).am(x)=a0+a1x1+a2x2+a3x3+… +amxm

bn(x)=b0+b1x1+b2x2+b3x3+… +bnxn

請實現(xiàn)求m(x)= am(x)+bn(x)、m(x)= am(x)-bn(x)和m(x)= am(x)×bn(x)。要求：

1)首先判定多項式是否稀疏

2)分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)； 3)結(jié)果m(x)中無重復(fù)階項和無零系數(shù)項； 4)要求輸出結(jié)果的升冪和降冪兩種排列情況

18.利用棧求表達式的值，可供小學(xué)生作業(yè)，并能給出分數(shù)。（限1 人完成）

要求：建立試題庫文件，隨機產(chǎn)生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù)比較后的評價

19.簡易文本編輯器（限1 人完成）要求：

1)具有圖形菜單界面；

2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數(shù)。

20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。（限1 人完成）

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

樹與二叉樹的轉(zhuǎn)換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

21.學(xué)生搭配問題（限1 人完成）

一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下: 1)輸出每曲配對情況

2)計算出任何一個男生(編號為x)和任意女生(編號為y),在第k曲配對跳舞的情況.至少求出k的兩個值.3)盡量設(shè)計出多種算法及程序,可視情況適當加分

提示:用隊列來解決比較方便.22.猴子吃桃子問題（限1 人完成）

有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。

要求：

1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 2)采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 3)采用遞歸實現(xiàn)上述求解

23.數(shù)制轉(zhuǎn)換問題（限1 人完成）

任意給定一個m進制的數(shù)x，請實現(xiàn)如下要求 1)求出此數(shù)x的10進制值（用md表示）2)實現(xiàn)對x向任意的一個非m進制的數(shù)的轉(zhuǎn)換。

3)至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

24.排序綜合（限1 人完成）

利用隨機函數(shù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：

1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。

2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。

25.學(xué)生成績管理系統(tǒng)（限1 人完成）現(xiàn)有學(xué)生成績信息文件1（），內(nèi)容如下 姓名 學(xué)號 語文 數(shù)學(xué) 英語

張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…

學(xué)生成績信息文件2（）,內(nèi)容如下: 姓名 學(xué)號 語文 數(shù)學(xué) 英語

陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統(tǒng),要求如下: 1)實現(xiàn)對兩個文件數(shù)據(jù)進行合并, 2) 3)中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實現(xiàn))4)輸入一個學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實現(xiàn))5)要求使用結(jié)構(gòu)體,鏈或數(shù)組等實現(xiàn)上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現(xiàn)（限1 人完成）要求：

1)先任意創(chuàng)建一個圖；

2)圖的dfs,bfs的遞歸和非遞歸算法的實現(xiàn) 3)要求用有向圖和無向圖分別實現(xiàn)

4)要求用鄰接矩陣、鄰接表多種結(jié)構(gòu)存儲實現(xiàn)

27.線索二叉樹的應(yīng)用（限1 人完成）

要求：實現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實現(xiàn)。

28.稀疏矩陣應(yīng)用（限1 人完成）

要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉(zhuǎn)置

29.樹的應(yīng)用（限1 人完成）

要求：實現(xiàn)樹與二叉樹的轉(zhuǎn)換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。

30.文本文件單詞的檢索與計數(shù) 設(shè)計要求與分析：

要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫；統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。該設(shè)計要求可分為三個部分實現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數(shù)，輸入一個不含空格的單詞，統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應(yīng)位置。（1）.建立文本文件（2）給定單詞的計數(shù)

（3）檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置（4）主控菜單程序的結(jié)構(gòu) ① 頭文件包含 ② 菜單選項包含

建立文件、單詞定位、單詞計數(shù)、退出程序 ③ 選擇1-4執(zhí)行相應(yīng)的操作，其他字符為非法。

31.任意長的整數(shù)加法（限1 人完成）

問題描述：設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)的求和運算。

基本要求：利用雙向循環(huán)鏈表，設(shè)計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。

32.二叉平衡排序樹（限1 人完成）

問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹轉(zhuǎn)換為二叉平衡排序樹?；疽螅?.創(chuàng)建（插入、調(diào)整、改組）

2.輸出

33.串的查找和替換（限1 人完成）

問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。

34.約瑟夫環(huán)（限1 人完成）

問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設(shè)計一個程序求出出列順序。

基本要求：

1、利用單循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程；

2、鍵盤輸入總?cè)藬?shù)、初始報數(shù)上限值m及各人密碼；

3、按照出列順序輸出各人的編號。

35.構(gòu)造可以使n個城市連接的最小生成樹（限1 人完成）

問題描述：給定一個地區(qū)的n個城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?/p>

1、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結(jié)構(gòu)定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。

2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個城市，10條邊）

3、最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價。

36.客戶消費積分管理系統(tǒng)（限1 人完成）

問題描述：針對客戶的消費情況，進行客戶管理，根據(jù)客戶的消費積分對客戶實行不同程度的打折優(yōu)惠。基本要求：

1.采用一定的存儲結(jié)構(gòu)進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據(jù)消費情況進行客戶積分的計算； 4.根據(jù)積分情況實行不同程度的打折優(yōu)惠；

37.產(chǎn)品進銷存管理系統(tǒng)（限1 人完成）

問題描述：針對某一種行業(yè)的庫房的產(chǎn)品進銷存情況進行管理?；疽螅?/p>

1.采用一定的存儲結(jié)構(gòu)對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；

3.能夠查詢庫房每種產(chǎn)品的總量、進貨日期、銷出數(shù)量、銷售時間等；

38.特殊矩陣的壓縮存儲算法的實現(xiàn)（限1 人完成）問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間。基本要求：

1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關(guān)地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應(yīng)的值；

39.算術(shù)表達式的求解（限1 人完成）

問題描述：給定一個算術(shù)表達式，通過程序求出最后的結(jié)果?；疽螅?/p>

1． 從鍵盤輸入要求解的算術(shù)表達式； 2． 采用棧結(jié)構(gòu)進行算術(shù)表達式的求解過程； 3． 能夠判斷算術(shù)表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結(jié)果；

40.實時監(jiān)控報警系統(tǒng)（限1 人完成）問題描述：建立一個報警和出警管理的系統(tǒng) 基本要求：

1.采用一定的存儲結(jié)構(gòu)存儲報警信息，要求有內(nèi)容、時間； 2.有一次的出警就應(yīng)該在待處理的信息中刪除這條信息； 3.記錄出警信息；

4.待處理信息過多時會發(fā)出警告；

41.車廂調(diào)度（限1 人完成）

問題描述：假設(shè)停在鐵路調(diào)度站入口處的車廂序列的編號一次為1，2，3，4。設(shè)計一個程序，求出所有可能由此輸出的長度為4的車廂序列。

42.迷宮問題（棧）問題描述：

以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?；疽螅?/p>

首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據(jù)：

迷宮的測試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)的迷宮沒有通路。

可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內(nèi)容：

（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：

本題目要求對普通的二叉排序樹、avl樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據(jù)結(jié)構(gòu)對應(yīng)的一系列插入和刪除操作的效率。要求測試對n個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入n個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入n個整數(shù)，并按相反順序刪除；（3）按隨機順序插入n個整數(shù)，并按隨機順序刪除；

要求n從1000到10000取值，并以數(shù)據(jù)規(guī)模n為橫軸，運行時間為縱軸，畫出3種不同數(shù)據(jù)結(jié)構(gòu)對應(yīng)的操作效率比較圖。

45.病毒測試程序 本題的任務(wù)是：

當整個網(wǎng)絡(luò)被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：

輸入由若干組測試數(shù)據(jù)組成。

每組數(shù)據(jù)的第1行包含2個整數(shù)m和n（1≤m,n≤500），接下來是一個m*n的矩陣表示網(wǎng)絡(luò)的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。

下面一行給出一個正整數(shù)q，是將要查詢的變種的個數(shù)。接下去的q行里，每行給出一個變種的類型。當m或n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。輸出要求：

對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。

46關(guān)鍵路徑問題（限1 人完成）

問題描述：設(shè)計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關(guān)鍵活動?；疽螅?/p>

（1）對一個描述工程的aoe網(wǎng)，應(yīng)判斷其是否能夠順利進行。

（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關(guān)鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。

47.神秘國度的愛情故事

輸入要求：輸入由若干組測試數(shù)據(jù)組成。

每組數(shù)據(jù)的第1行包含一正整數(shù)n（1≤n≤50000），代表神秘國度中小村的個數(shù)，每個小村即從0到n-1編號。接下來有n-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數(shù)m（1≤m≤500000），代表著該組測試問題的個數(shù)。接下來m行，每行給出a,b,c三個小村 的編號，中間用空格分開。當n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。

輸出要求：對每一組測試給定的a,b,c，在一行里輸出答案，即：如果c在a和b之間的路徑上，輸出yes,否則輸出no。

48.并查集：檢查網(wǎng)絡(luò)

題目要求：給定一個計算機網(wǎng)絡(luò)以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？

輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡(luò)中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結(jié)束。當n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。

輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當讀到s時，檢查整個網(wǎng)絡(luò)。若網(wǎng)絡(luò)中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡(luò)中連通集的個數(shù)。兩組測試數(shù)據(jù)之間請輸出一空行分隔。

49.廣義表的應(yīng)用

由于廣義表在結(jié)構(gòu)上較線性表復(fù)雜得多，因此，廣義表的運算也不如線性表簡單。本設(shè)計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設(shè)計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結(jié)點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度

50.網(wǎng)絡(luò)流：宇宙旅行 題目要求：

在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經(jīng)過謹慎調(diào)查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時?？恐修D(zhuǎn)，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉(zhuǎn)乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預(yù)算，現(xiàn)在旅游狂人需要知道終點星球的接待站應(yīng)該設(shè)計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：

輸入若干組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)n（n為0標志全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理）。

接下來的n行里，數(shù)據(jù)格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由a～z之間三個大寫字母組成的字符串，例如：zju。測試數(shù)據(jù)中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：

對每一組測試，在一行里輸出終點星球接待站應(yīng)具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。

數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型篇四

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目(大題目).doc

一、公司銷售管理系統(tǒng) 項目開發(fā)基本要求

1．客戶信息管理：對客戶的基本信息進行添加、修改和刪除。2．產(chǎn)品信息管理：對產(chǎn)品的基本信息進行添加、修改和刪除。3．供應(yīng)商信息管理：對供應(yīng)商的基本信息進行添加、修改和刪除。4．訂單信息管理：對訂單的基本信息進行添加、修改和刪除。

二、高?？蒲泄芾硐到y(tǒng)

系統(tǒng)主要用于幫助高?；蚩蒲袉挝还芾砗途S護各項科研相關(guān)資料 項目開發(fā)基本要求

1．系統(tǒng)用戶管理模塊：為系統(tǒng)新用戶設(shè)置用戶名及口令；操作員更改自己的系統(tǒng)口令。2．數(shù)據(jù)字典管理模塊：管理項目性質(zhì)包括：分為國家自然科學(xué)基金、863、部省科委及企業(yè)集團四種情況；范圍包括：分為全國、國際、地方三種情況；檢索源包括：分為ei、sci、核心和一般四種情況。

3．項目參加人員管理模塊包括：顯示添加修改刪除查詢。4．項目基本情況模塊包括：顯示添加修改刪除查詢。5．項目獲獎情況模塊包括：顯示添加修改刪除查詢。6．期刊論文管理模塊包括：顯示添加修改刪除查詢。7．著作管理模塊包括：顯示添加修改刪除查詢。

8．科研工作量統(tǒng)計模塊：按照學(xué)?？蒲泄ぷ髁坑嬎戕k法，為每位科研人員進行科研工作量的計算和統(tǒng)計。

9．科研積分統(tǒng)計模塊：按照學(xué)校科研積分計算辦法，為每位科研人員進行科研計分的計算和統(tǒng)計。

三、網(wǎng)絡(luò)五子棋對戰(zhàn)

四、不同排序算法模擬

五、科學(xué)計算器

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目

1.運動會分數(shù)統(tǒng)計

任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）

功能要求：

1)可以輸入各個項目的前三名或前五名的成績； 2)能統(tǒng)計各學(xué)?？偡?，3)可以按學(xué)校編號或名稱、學(xué)校總分、男女團體總分排序輸出； 4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。5)數(shù)據(jù)存入文件并能隨時查詢

6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運動項目的名稱

輸出形式：有合理的提示，各學(xué)校分數(shù)為整形

界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。

存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；

測試數(shù)據(jù)：要求使用

1、全部合法數(shù)據(jù)；

2、整體非法數(shù)據(jù)；

3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；

2.飛機訂票系統(tǒng)

任務(wù)：通過此系統(tǒng)可以實現(xiàn)如下功能：

錄入：

可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）

查詢：

可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；

可以輸入起飛抵達城市，查詢飛機航班情況；

訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）

可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；

退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。

修改航班信息：

當航班信息改變可以修改航班數(shù)據(jù)文件

要求：

根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能；

3.文章編輯

功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共n行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；

4.宿舍管理查詢軟件

1)任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設(shè)計要求： a.采用交互工作方式

b.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)a.按姓名查詢 b.按學(xué)號查詢 c.按房號查詢

3)打印任一查詢結(jié)果（可以連續(xù)操作）

5.校園導(dǎo)航問題

設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。

6.教學(xué)計劃編制問題

設(shè)計要求：針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。

7.散列法的實驗研究

散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。

8.圖書借閱管理系統(tǒng)

主要分為兩大功能：

1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；

9.學(xué)生成績管理

實現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。

10.活期儲蓄帳目管理

活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設(shè)計要求： 1)能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬； 2)能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。

11.二叉排序樹的實現(xiàn)

用順序和二叉鏈表作存儲結(jié)構(gòu)

1)以回車('n')為輸入結(jié)束標志,輸入數(shù)列l(wèi)，生成一棵二叉排 序樹t； 2)對二叉排序樹t作中序遍歷，輸出結(jié)果；

3)輸入元素x,查找二叉排序樹t,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；

12.最小生成樹問題 設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。

13.通訊錄的制作

設(shè)計目的：用〈〈數(shù)據(jù)結(jié)構(gòu)〉〉中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)，結(jié)合c語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識應(yīng)用到實際軟件開發(fā)中去。設(shè)計內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display();

3)查找以姓名作為關(guān)鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設(shè)計要求：

1)每條信息至包含 ：姓名（name）街道（street）城市（city）郵編（eip）國家（state）幾項 2)作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設(shè)計報告

14.哈夫曼編碼/譯碼器 【問題描述】

設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止?！净疽蟆?/p>

1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(，位于執(zhí)行程序的當前目錄中)2)分別采用動態(tài)和靜態(tài)存儲結(jié)構(gòu)

3)初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼；

6)設(shè)字符集及頻度如下表：

字符 空格 a b c d e f g h i j k l m 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內(nèi)容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設(shè)計的優(yōu)化。

15.圖書管理系統(tǒng) 【問題描述】

設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù)。【基本要求】

1)每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：

*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量?！具M一步完成內(nèi)容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設(shè)計內(nèi)容 4)程序流程圖 5)源程序

6)軟件測試報告（包括所用到的數(shù)據(jù)及結(jié)果）

16.散列表的設(shè)計與實現(xiàn) 【問題描述】

設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)?！净疽蟆?/p>

1)設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；

2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄?！具M一步完成內(nèi)容】 1)系統(tǒng)功能的完善；

2)設(shè)計不同的散列函數(shù)，比較沖突率；

3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

17.順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。

設(shè)有一元多項式am(x)和bn(x).am(x)=a0+a1x1+a2x2+a3x3+… +amxm

bn(x)=b0+b1x1+b2x2+b3x3+… +bnxn

請實現(xiàn)求m(x)= am(x)+bn(x)、m(x)= am(x)-bn(x)和m(x)= am(x)×bn(x)。

要求：

1)首先判定多項式是否稀疏

2)分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)； 3)結(jié)果m(x)中無重復(fù)階項和無零系數(shù)項； 4)要求輸出結(jié)果的升冪和降冪兩種排列情況

18.利用棧求表達式的值，可供小學(xué)生作業(yè)，并能給出分數(shù)。

要求：建立試題庫文件，隨機產(chǎn)生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù)比較后的評價

19.簡易文本編輯器 要求：

1)具有圖形菜單界面；

2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數(shù)。

20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

樹與二叉樹的轉(zhuǎn)換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

21.學(xué)生搭配問題

一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下: 1)輸出每曲配對情況

2)計算出任何一個男生(編號為x)和任意女生(編號為y),在第k曲配對跳舞的情況.至少求出k的兩個值.3)盡量設(shè)計出多種算法及程序,可視情況適當加分

提示:用隊列來解決比較方便.22.猴子吃桃子問題

有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。

要求：

1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 2)采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 3)采用遞歸實現(xiàn)上述求解

23.數(shù)制轉(zhuǎn)換問題

任意給定一個m進制的數(shù)x，請實現(xiàn)如下要求 1)求出此數(shù)x的10進制值（用md表示）2)實現(xiàn)對x向任意的一個非m進制的數(shù)的轉(zhuǎn)換。

3)至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

24.排序綜合

利用隨機函數(shù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：

1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。

2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。

25.學(xué)生成績管理系統(tǒng)

現(xiàn)有學(xué)生成績信息文件1（），內(nèi)容如下 姓名 學(xué)號 語文 數(shù)學(xué) 英語

張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…

學(xué)生成績信息文件2（）,內(nèi)容如下: 姓名 學(xué)號 語文 數(shù)學(xué) 英語

陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統(tǒng),要求如下:

1)實現(xiàn)對兩個文件數(shù)據(jù)進行合并,

2)

3)中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實現(xiàn))

4)輸入一個學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實現(xiàn))5)要求使用結(jié)構(gòu)體,鏈或數(shù)組等實現(xiàn)上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現(xiàn) 要求：

1)先任意創(chuàng)建一個圖；

2)圖的dfs,bfs的遞歸和非遞歸算法的實現(xiàn) 3)要求用有向圖和無向圖分別實現(xiàn)

4)要求用鄰接矩陣、鄰接表多種結(jié)構(gòu)存儲實現(xiàn)

27.線索二叉樹的應(yīng)用 要求：實現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實現(xiàn)。

28.稀疏矩陣應(yīng)用

要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉(zhuǎn)置

29.樹的應(yīng)用

要求：實現(xiàn)樹與二叉樹的轉(zhuǎn)換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。

30.文本文件單詞的檢索與計數(shù) 設(shè)計要求與分析：

要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫；統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。該設(shè)計要求可分為三個部分實現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數(shù)，輸入一個不含空格的單詞，統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應(yīng)位置。（1）.建立文本文件（2）給定單詞的計數(shù)

（3）檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置（4）主控菜單程序的結(jié)構(gòu) ① 頭文件包含 ② 菜單選項包含

建立文件、單詞定位、單詞計數(shù)、退出程序 ③ 選擇1-4執(zhí)行相應(yīng)的操作，其他字符為非法。

31.任意長的整數(shù)加法

問題描述：設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)的求和運算。

基本要求：利用雙向循環(huán)鏈表，設(shè)計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。

32.二叉平衡排序樹

問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹轉(zhuǎn)換為二叉平衡排序樹。基本要求：1.創(chuàng)建（插入、調(diào)整、改組）2.輸出

33.串的查找和替換

問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。

34.約瑟夫環(huán)

問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設(shè)計一個程序求出出列順序?；疽螅?/p>

1、利用單循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程；

2、鍵盤輸入總?cè)藬?shù)、初始報數(shù)上限值m及各人密碼；

3、按照出列順序輸出各人的編號。

35.構(gòu)造可以使n個城市連接的最小生成樹

問題描述：給定一個地區(qū)的n個城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?/p>

1、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結(jié)構(gòu)定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。

2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個城市，10條邊）

3、最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價。

36.客戶消費積分管理系統(tǒng)

問題描述：針對客戶的消費情況，進行客戶管理，根據(jù)客戶的消費積分對客戶實行不同程度的打折優(yōu)惠?；疽螅?/p>

1.采用一定的存儲結(jié)構(gòu)進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據(jù)消費情況進行客戶積分的計算； 4.根據(jù)積分情況實行不同程度的打折優(yōu)惠；

37.產(chǎn)品進銷存管理系統(tǒng)

問題描述：針對某一種行業(yè)的庫房的產(chǎn)品進銷存情況進行管理?；疽螅?/p>

1.采用一定的存儲結(jié)構(gòu)對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；

3.能夠查詢庫房每種產(chǎn)品的總量、進貨日期、銷出數(shù)量、銷售時間等；

38.特殊矩陣的壓縮存儲算法的實現(xiàn)

問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間?；疽螅?/p>

1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關(guān)地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應(yīng)的值；

39.算術(shù)表達式的求解

問題描述：給定一個算術(shù)表達式，通過程序求出最后的結(jié)果?；疽螅?/p>

1． 從鍵盤輸入要求解的算術(shù)表達式； 2． 采用棧結(jié)構(gòu)進行算術(shù)表達式的求解過程； 3． 能夠判斷算術(shù)表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結(jié)果；

40.實時監(jiān)控報警系統(tǒng)

問題描述：建立一個報警和出警管理的系統(tǒng) 基本要求：

1.采用一定的存儲結(jié)構(gòu)存儲報警信息，要求有內(nèi)容、時間； 2.有一次的出警就應(yīng)該在待處理的信息中刪除這條信息； 3.記錄出警信息；

4.待處理信息過多時會發(fā)出警告；

41.車廂調(diào)度

問題描述：假設(shè)停在鐵路調(diào)度站入口處的車廂序列的編號一次為1，2，3，4。設(shè)計一個程序，求出所有可能由此輸出的長度為4的車廂序列。

42.迷宮問題（棧）問題描述：

以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?；疽螅?/p>

首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據(jù)：

迷宮的測試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示：

計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)的迷宮沒有通路。

可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內(nèi)容：

（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：

本題目要求對普通的二叉排序樹、avl樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據(jù)結(jié)構(gòu)對應(yīng)的一系列插入和刪除操作的效率。要求測試對n個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入n個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入n個整數(shù)，并按相反順序刪除；（3）按隨機順序插入n個整數(shù)，并按隨機順序刪除；

要求n從1000到10000取值，并以數(shù)據(jù)規(guī)模n為橫軸，運行時間為縱軸，畫出3種不同數(shù)據(jù)結(jié)構(gòu)對應(yīng)的操作效率比較圖。

45.病毒測試程序 本題的任務(wù)是：

當整個網(wǎng)絡(luò)被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：

輸入由若干組測試數(shù)據(jù)組成。

每組數(shù)據(jù)的第1行包含2個整數(shù)m和n（1≤m,n≤500），接下來是一個m*n的矩陣表示網(wǎng)絡(luò)的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。

下面一行給出一個正整數(shù)q，是將要查詢的變種的個數(shù)。接下去的q行里，每行給出一個變種的類型。當m或n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。輸出要求：

對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。

46關(guān)鍵路徑問題

問題描述：設(shè)計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關(guān)鍵活動?；疽螅?/p>

（1）對一個描述工程的aoe網(wǎng)，應(yīng)判斷其是否能夠順利進行。

（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關(guān)鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。

47.神秘國度的愛情故事

輸入要求：輸入由若干組測試數(shù)據(jù)組成。

每組數(shù)據(jù)的第1行包含一正整數(shù)n（1≤n≤50000），代表神秘國度中小村的個數(shù)，每個小村即從0到n-1編號。接下來有n-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數(shù)m（1≤m≤500000），代表著該組測試問題的個數(shù)。接下來m行，每行給出a,b,c三個小村 的編號，中間用空格分開。

當n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。

輸出要求：對每一組測試給定的a,b,c，在一行里輸出答案，即：如果c在a和b之間的路徑上，輸出yes,否則輸出no。

48.并查集：檢查網(wǎng)絡(luò)

題目要求：給定一個計算機網(wǎng)絡(luò)以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？

輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡(luò)中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結(jié)束。當n為0時，表示全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理。

輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當讀到s時，檢查整個網(wǎng)絡(luò)。若網(wǎng)絡(luò)中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡(luò)中連通集的個數(shù)。兩組測試數(shù)據(jù)之間請輸出一空行分隔。

49.廣義表的應(yīng)用

由于廣義表在結(jié)構(gòu)上較線性表復(fù)雜得多，因此，廣義表的運算也不如線性表簡單。本設(shè)計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設(shè)計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結(jié)點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度

50.網(wǎng)絡(luò)流：宇宙旅行 題目要求：

在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經(jīng)過謹慎調(diào)查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時?？恐修D(zhuǎn)，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉(zhuǎn)乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預(yù)算，現(xiàn)在旅游狂人需要知道終點星球的接待站應(yīng)該設(shè)計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：

輸入若干組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)n（n為0標志全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理）。

接下來的n行里，數(shù)據(jù)格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由a～z之間三個大寫字母組成的字符串，例如：zju。

測試數(shù)據(jù)中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：

對每一組測試，在一行里輸出終點星球接待站應(yīng)具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。

51：算術(shù)運算測試

功能要求：該程序用圖形界面實現(xiàn)十道100以內(nèi)加減法數(shù)學(xué)題，能根據(jù)題目計算出答案，與輸入答案對比，判斷做題是否正確，最后計算分數(shù)。

界面要求：用圖形界面實現(xiàn)。52：猜數(shù)游戲 功能要求：計算機產(chǎn)生隨機數(shù)，猜中即勝，猜不中，提示是大了還是小了，繼續(xù)猜，直至猜到，給出所用時間和評語。

界面要示：用圖形界面實現(xiàn)。

53、學(xué)生成績管理

功能要求：

1)輸入十個同學(xué)的學(xué)號，姓名，四科成績（應(yīng)用數(shù)學(xué)、大學(xué)英語、java程序設(shè)計、計算機應(yīng)用基礎(chǔ)）

2)計算出平均成績。以平均成績降序輸出成績表。3)輸出全組各科平均分，最高分和最低分。4)輸入姓名查詢成績

界面要示：用圖形界面實現(xiàn)。54．矩陣的運算

采用鏈表表示稀疏矩陣，并實現(xiàn)矩陣的加法，乘法，求逆運算, 要求：要檢查有關(guān)運算的條件，并對錯誤的條件產(chǎn)生報警。

55．建立二叉樹和線索二叉樹

分別用以下方法建立二叉樹并用圖型顯示出來：

用先序遍歷的輸入序列

用層次遍歷的輸入序列

用先序和中序遍歷的結(jié)果

最后對所建立的二叉樹進行中序線索化，并對此線索樹進行中序遍歷(不使用棧)。

56．銀行業(yè)務(wù)模擬：

客戶業(yè)務(wù)分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。

銀行有兩個服務(wù)窗口，相應(yīng)的有兩個隊列?？蛻舻竭_銀行后先排第一個隊。處理每個客戶業(yè)務(wù)時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立即排入第二隊等候，直至滿足時才離開銀行，否則業(yè)務(wù)處理完后立即離開銀行。每接待完一個第二種業(yè)務(wù)的客戶，則順序檢查和處理（如果可能）第二個隊列的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶（第二種業(yè)務(wù)）被接待之前的數(shù)額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查（因為此時已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個隊列的客戶。任何時刻都只開一個窗口。假設(shè)檢查不需要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務(wù)的事件驅(qū)動模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的平均時間。

57.假設(shè)一個賓館有n個標準的客房，每個標準客房有m個標準間，利用鏈表、?；蛘哧犃械葦?shù)據(jù)結(jié)構(gòu)設(shè)計出具有訂房和退房等功能的管理系統(tǒng)。

數(shù)據(jù)結(jié)構(gòu)考試題目及答案詳解 數(shù)據(jù)結(jié)構(gòu)考試題型篇五

一、表達式求值（2-3人）

? 問題描述：從鍵盤上輸入中綴算數(shù)表達式，計算出表達式的值。? 基本要求：

1.程序?qū)λ斎氲谋磉_式做簡單的判斷，如果表達式有錯，能給出適當?shù)奶崾尽?/p>

2.能處理+、－、×、÷

這四種基本的算術(shù)運算符。

二、停車場管理（3-4人）

? 問題描述：假設(shè)停車場只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達的先后順序依次排列，如果車場內(nèi)已經(jīng)停滿了汽車，則后來的汽車只能在門外的便道上等候。一旦停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該車輛開出大門后，為它讓路的車輛再按原次序進入停車場。每輛汽車在離開時都要依據(jù)停留時間交費（在便道上停留的時間不計費）。

? 基本要求：

1.汽車的輸入信息格式為：到達/離去的標識，汽車牌照號碼，到達/離去的時間。

2.對于不合理的輸入信息有適當?shù)奶崾?，例如要求離開的汽車沒在停車場或便道時有相應(yīng)的提示。

? 提示：以棧模擬停車場，用隊列模擬便道，另設(shè)一個棧臨時停放為讓路而從車場退出的車。

三、約瑟夫環(huán)問題（2人）

問題描述：設(shè)編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)作為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程，求出出列編號序列。

四、航空客運訂票系統(tǒng)（4-5人）

? 問題描述：業(yè)務(wù)主要包括查詢航線和客票預(yù)訂的信息、客票預(yù)訂和辦理退票等。? 基本要求：

1.系統(tǒng)必須能存儲以下數(shù)據(jù)信息：

航班信息：飛機抵達城市、航班號、飛機號、起降時間、票價、總座位數(shù)和剩余座位數(shù)、已訂票的客戶名單?？蛻粜畔ⅲ嚎蛻粜彰?、證件號、座位號。2.系統(tǒng)能實現(xiàn)的功能：

承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求查詢該航班信息，若滿足要求，則為客戶辦理訂票手續(xù)，輸出座位號。

退票業(yè)務(wù)：根據(jù)客戶提供的航班號和訂票數(shù)量辦理退票手續(xù)。查詢功能：查詢航線信息（根據(jù)飛機的降落地點輸出航班號、飛機好、起降時間、票價和剩余座位數(shù)）和客戶預(yù)訂信息（根據(jù)客戶證件號輸出航班號、飛機號和座位號）

五、漢諾塔游戲程序（2-3人）

? 問題描述：在平面上有三個位置a、b、c，在a位置上有n個大小不等的圓盤、小盤壓在大盤上形成圓盤堆。要求將a位置的n個圓盤通過b位置移動到c位置上，并按同樣的順序疊放。移動圓盤時必須遵循以下規(guī)則：

1.每一次只能移動一個圓盤

2.圓盤可以放在a、b、c任何一個塔座上 3.任何時刻都不能將大圓盤壓在小圓盤上 ? 基本要求：

圓盤的個數(shù)從鍵盤輸入（如3-64等）；用動畫的形式在屏幕上顯示盤的移動。六、八皇后問題（2人）

? 問題描述：八皇后問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。

? 基本要求：統(tǒng)計總共有多少種擺法，并以一定方式輸出擺好的格局。

七、簡單個人圖書管理系統(tǒng)（3-4人）

? 問題描述：學(xué)生在學(xué)習(xí)過程中擁有很多書籍，對購買的書籍進行分類和統(tǒng)計是一種良好的習(xí)慣。如果用文件來存儲相關(guān)書籍的各種信息，包括書號、書名、作者名、價格和購買日期，輔之以程序?qū)畔⑦M行統(tǒng)計和查詢會使書籍管理工作輕松有趣。? 基本要求：

1.在外存中用文件存儲書籍相關(guān)信息 2.在內(nèi)存中設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲圖書信息 3.能查找、刪除、插入、更新

4.能按作者名對書籍進行排序并顯示排序結(jié)果

八、雙端隊列（2人）

? 問題描述：雙端隊列是插入和刪除操作可以在兩端進行的線性表，表的兩端分別稱作端點1和端點2。設(shè)計雙端隊列的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)入隊、出隊等基本操作。

提示：為便于操作，采用帶頭結(jié)點的雙鏈表存儲雙端隊列

九、迷宮問題（2人）

? 問題描述：迷宮實驗是取自心理學(xué)的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒中設(shè)置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。在給出入口和出口的前提下，給出動態(tài)的迷宮行走路線 ? 基本要求：

1.設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲迷宮

提示：用二維數(shù)組表示迷宮，1代表有障礙，0代表無障礙 2.設(shè)計存儲結(jié)構(gòu)保存入口到出口的通路

十、火車車廂重排問題（4-5人）

? 問題描述：一列貨運列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1-n，即貨運列車按照第n站到第1站的次序經(jīng)過車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號應(yīng)與車站的編號相同，這樣，在每個車站只要卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列它們。車廂的重排工作可以通過轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個出軌、一個入軌和一個緩沖軌，緩沖軌位于入軌和出軌之間。設(shè)緩沖軌按先進先出的方式運作，設(shè)計算法解決火車車廂重排問題。

? 基本要求：設(shè)計存儲結(jié)構(gòu)表示n個車廂、k個緩沖軌以及入軌、出軌。假設(shè)k=3。

十一、魔方陣（2人）

? 問題描述： 在一個n×n的矩陣中填入一個1到n2的數(shù)字（n為奇數(shù)），使得每一行、每一列、每條對角線的累加和都相等。

十二、簡單個人電話號碼查詢系統(tǒng)（3-4人）

? 問題描述：人們在日常生活中經(jīng)常要查找某個人或某個單位的電話號碼，要求實現(xiàn)一個簡單的個人電話號碼查詢系統(tǒng)，根據(jù)用戶輸入的信息（例如姓名等）進行快速查詢。? 基本要求：

1.在外存中用文件保存電話號碼信息

2.在內(nèi)存中設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲電話號碼信息

3.將電話號碼信息按某一字段排序，以提高查找效率 4.提供插入、刪除、修改等維護功能。

十三、直接插入排序基于單鏈表的實現(xiàn)（1人）

? 問題描述：采用單鏈表存儲待排序數(shù)據(jù)，在其上實現(xiàn)直接插入排序算法。? 基本要求：排序的數(shù)據(jù)的個數(shù)及其內(nèi)容由用戶從鍵盤上輸入。

十四、患者看病過程模擬（2人）

? 問題描述：患者到醫(yī)院看病的過程為先排隊等候再看病治療。在排隊的過程中主要重復(fù)做兩件事：一是患者到達診室，將病歷交給護士，排到等候隊列中候診；二是護士從等候隊列中取出下一個患者的病歷，該患者進入診室看病。設(shè)計算法模擬該過程。? 基本要求：

1.以菜單的形式供用戶選擇相應(yīng)的操作 2.可以查看當前正在就診的病人的信息 3.可以查詢當前等候就診的病人的信息

十五、汽車牌照數(shù)據(jù)的排序與快速查找（3人）

? 問題描述：在汽車數(shù)據(jù)的信息模型中，汽車牌照是關(guān)鍵字，而且是具有結(jié)構(gòu)特點的一類關(guān)鍵字。因為汽車牌照號是數(shù)字和字母混編的，例如01b7328，這種記錄集合是一個適用于多關(guān)鍵字進行排序的典型例子。? 基本要求：

1.首先利用鏈式基數(shù)排序方法排序，然后利用折半查找方法實現(xiàn)對汽車記錄按關(guān)鍵字查找

2.汽車記錄集合可以人工錄入，也可以按自動方式隨機生成十六、求圖的中心點（2人）

? 問題描述：假設(shè)有一個公司在某個地區(qū)有n個產(chǎn)品銷售點，現(xiàn)根據(jù)業(yè)務(wù)需要打算在其中某個銷售點上建立一個中心倉庫負責向其他銷售點提供產(chǎn)品。由于運輸路線不同，運輸費用也不同。假定每天需要向每個銷售點運輸一次產(chǎn)品，那么應(yīng)將中心倉庫建在哪個銷售點上才能使運輸費用最低。

十七、集合的交、并和差運算的實現(xiàn)（1-2人）

? 問題描述：用有序單鏈表表示集合，實現(xiàn)集合的交、并、差運算 ? 基本要求： 空間復(fù)雜度為o(1)

十八、單鏈表實現(xiàn)十進制大整數(shù)運算（1-2人）

? 問題描述：使用單鏈表實現(xiàn)不限大小的整數(shù)，每個結(jié)點存儲一位數(shù)字，要求實現(xiàn)加、減運算。即能從鍵盤上輸入兩個大整數(shù)，比如：***12345和-***11111，則加的結(jié)果應(yīng)為：***01234；減的結(jié)果應(yīng)為：***23456。? 基本要求： 從鍵盤上輸入運算數(shù)和運算符，輸出結(jié)果。

十九、哈夫曼編碼（4-5人）

? 問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這就要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完成的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。?

基本要求：

1.初始化。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹。

2.編碼。利用已建好的哈夫曼樹,對正文進行編碼。

3.譯碼。對編碼好的內(nèi)容進行譯碼。

4.打印編碼。

二十、商品貨架管理（2人）

? 問題描述：商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時需要倒貨架，以保證生產(chǎn)商品較近的商品在較下的位置。用棧和隊列作為周轉(zhuǎn)，實現(xiàn)上述管理過程。

二十一、稀疏矩陣運算器（3人）

? 問題描述：實現(xiàn)兩個稀疏矩陣的加、減、乘運算。

? 基本要求：可用三元組順序表存儲稀疏矩陣，矩陣的運算結(jié)果以通常的陣列形式輸出。

二十二、校園導(dǎo)游程序（3-4人）

? 問題描述：用無向圖表示你所在學(xué)校的景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等消息。? 基本要求：

1.能查詢各景點的相關(guān)信息

2.為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某景點之間的一條最短路徑及長度。

二十三、排序綜合（2-3人）

? 問題描述：利用隨機函數(shù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)使用多種方法進行排序。? 基本要求： 1.至少采用三種方法（希爾排序、快速排序、堆排序）實現(xiàn)上述問題求解

2.統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法

3.統(tǒng)計每種算法所用的比較次數(shù)和交換次數(shù)，最后列表顯示

二十四、線索二叉樹（1人）

? 問題描述：建立一個中序線索二叉樹，并且完成中序遍歷。求該中序線索二叉樹上已知結(jié)點在中序的前驅(qū)和后繼；

【本文地址：http://aiweibaby.com/zuowen/1086888.html】