近幾年數(shù)據(jù)結構試卷：

鏈接：https://pan.baidu.com/s/1_ns6dbps8i6UyLN5RNJJiw?pwd=g3z2?
提取碼：g3z2

2019-2020（2）數(shù)據(jù)結構期末考試試卷?
?
一、 簡答題（共10題，100分）?
1、已知某二叉樹的先序序列和中序序列分別為ABDGEHCFI和DGBHEACIF，請畫出這棵二叉樹，并畫出二叉樹對應的森林。
?
正確答案：?
二叉樹正確得4分，森林正確得4分，滿分8分。
?
?
?
解析：?
?
2、依次把結點（50,75,80,35,40,28,63,51,8,21）插入初始狀態(tài)為空的平衡二叉排序樹，使得每次插入后該樹仍然是平衡二叉樹。請依次畫出插入及平衡化過程。
?
正確答案：?
每正確插入一個結點得1分，滿分10分。
?
?
?
?
?
解析：?
?
3、假設用于通訊的電文由字符a,b,c,d,e,f,g,h組成，字符在電文中出現(xiàn)的頻率分別為3,8,12,21,17,19,4,16。
（1）畫出你所建的赫夫曼樹（畫出構建過程）；
（2）給出每一字符的赫夫曼編碼。
正確答案：?
赫夫曼樹答案不唯一。
構造過程為7步，每步1分。編碼正確得3分。
?
?
解析：?
?
4、已知帶權無向圖的鄰接矩陣如下圖所示，
?
（1）請畫出該圖，并畫出該圖的鄰接表；
（2）從頂點A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列；
（3）從頂點A出發(fā)，采用Prim算法求該圖的最小生成樹，畫出求解過程。
正確答案：?
（1）圖正確得4分，鄰接表正確得4分（鄰接表不唯一）。
?（1）圖正確得4分，鄰接表正確得4分（鄰接表不唯一）。
?
?（1）圖正確得4分，鄰接表正確得4分（鄰接表不唯一）。
?
?

?
（2）每個序列正確得1分（遍歷序列不唯一），共2分。
DFS序列：ABECFDG
BFS序列：ABCDEFG
（3）最小生成樹每步1分，共6分。
????????
?
解析：?
?
5、AOE網(wǎng)是帶權有向圖，圖中頂點表示事件，有向邊表示活動，邊上的權值表示完成該活動的開銷。假設某項工程可以分解為若干個活動，下圖給出了該工程各活動之間的優(yōu)先關系和各活動所需的時間，請完成以下各題。

（1）寫出2個拓撲排序序列；
（2）求出各事件、各活動的最早發(fā)生時間和最遲發(fā)生時間。
（3）求出關鍵路徑，并指明完成該工程所需的最短時間。
?
正確答案：?
（1）拓撲排序序列正確得2分（序列不唯一）
? ? ?v1,v2,v4,v5,v3,v6,v7,v8
? ? v1,v2,v3,v4,v5,v6,v7,v8
?
（3）求解正確得2分。
時間活動余量為0的活動：A,E,L,M；關鍵路徑為v1,v2,v6,v7,v8
工程所需最短時間為11。
?
?
解析：?
?
6、對下圖所示的3階B-樹，依次執(zhí)行下列操作，畫出各步操作的結果。
（1）插入65 ?（2）插入25 ?（3）插入55 ? （4）刪除100 ? （5）刪除80
?
正確答案：?
每一小問回答正確得2分。
?
?
解析：?
?
7、給定一組查找關鍵字(32,15,7,11,4,28,56,61,79)，哈希表長為m=12，請按照除留余數(shù)法設計一個哈希函數(shù)，設每個記錄的查找概率相等。
（1）畫出按照線性探測再散列處理沖突得到的哈希表（給出求解過程），并計算查找成功和查找失敗時的平均查找長度各是多少。
（2）畫出按照鏈地址法處理沖突得到的哈希表，并計算查找成功和查找失敗時的平均查找長度各是多少。
正確答案：?
每一小問為5分，其中哈希表構造正確得3分，每種平均查找長度計算正確得1分。哈希函數(shù)樣例：H(key) = kye % 11。
（1）線性探測再散列
H(32) = 32 % 11 = 10
H(15) = 15 % 11 = 4
H(7) = 7 % 11 = 7
H(11) = 11 % 11 = 0
H(4) = 4 % 11 = 4 ?(4+1) % 12 = 5
H(28) = 28 % 11 = 6
H(56) = 56 % 11 = 1
H(61) = 61 % 11 = 6 ?(6+1) % 12 = 7; ?(6+2) % 12 = 8
H(79) = 79 % 11 = 2
?
查找成功時的平均查找長度： ASL = (7*1 + 1*2 + 1*3)/9 = 12/9 = 4/3;
查找失敗時的平均查找長度： ASL = (4+3+2+1+6+5+4+3+2+1+2)/11 = 33/11 = 3。
（2）鏈地址法：
??
查找成功時的平均查找長度： ASL = (7*1 + 2*2)/9 = 11/9;
查找失敗時的平均查找長度： ASL = (2*5 + 1*4 + 3*2)/11 = 20/11。
?
解析：?
?
8、請盡可能多的列舉你所知道的穩(wěn)定排序方法和不穩(wěn)定排序方法，對每種不穩(wěn)定的排序方法各舉一例來證明不穩(wěn)定性。
?
正確答案：?
穩(wěn)定的排序方法有：直接插入排序、冒泡排序、歸并排序、鏈式基數(shù)排序；（2分）
不穩(wěn)定的排序方法有：希爾排序、快速排序、簡單選擇排序、堆排序。（2分）
舉例：
序列 1 ?3 ?2 ?2，希爾排序后為 1 ?2 ?2 ?3； ?（1分）
序列 2 ?2 ?3 ?1，快速排序后為 1 ?2 ?2 ?3； ?（1分）
序列 2 ?3 ?2 ?1，堆排序后為1 ?2 ?2 ?3； ? ?（1分）
序列2 ?2 ?3 ?1，簡單選擇排序后為 1 ?2 ?2 ?3；（1分）
?
解析：?
?
9、單鏈表結構定義如下：
typedef struct LNode{
? ?int ?data;
? ?struct LNode ?*next;
}LNode, *LinkList;
給定一個帶頭結點的單鏈表L，表中結點元素值唯一，按遞減次序輸出單鏈表中各結點的元素值，并釋放結點所占存儲空間（要求：算法的空間復雜度為O(1)）。請采用C或者C++語言描述算法。
正確答案：?
評分標準如下：
（1）能實現(xiàn)題目要求的功能，算法正確，表述清楚，代碼規(guī)范，得8分
（2）能實現(xiàn)題目要求的功能，算法無邏輯錯誤，代碼表述有少量語法錯誤（筆誤性質(zhì)），可得7-8分
（4）能實現(xiàn)題目要求的功能，算法有bug(對某個特殊輸入，可能得不到正確結果），可得4-6分
（5）能表達出核心功能的實現(xiàn)方法，算法有邏輯錯誤，可得2-3分
（6）核心功能沒有實現(xiàn)，算法有嚴重邏輯錯誤，可得0-2分
參考代碼如下
void Delete(LinkList &L)
{
while(L->next != NULL){
? ?pre = L;
? ?p = pre->next;
? ?while( p->next != NULL) {
? ? ? if( p->next->data > pre->next->data)
? ? ? ? ? pre = p;
? ? ? p = p->next;
}
print( pre->next->data);
u = pre->next;
pre->next = u->next;
free(u);
}
free(L);
}
?
解析：?
?
10、單鏈表結構定義如下：
typedef struct LNode{
? int ?data;
? struct LNode ?*next;
}LNode, *LinkList;
給定一個帶頭結點的單鏈表L，表中結點元素值唯一，試采用直接插入排序法將L中的結點按值遞減次序排列，并分析算法的時間復雜度。請采用C或者C++語言描述算法。
正確答案：?
評分標準如下：
（1）能實現(xiàn)題目要求的功能，算法正確，表述清楚，代碼規(guī)范，得8分
（2）能實現(xiàn)題目要求的功能，算法無邏輯錯誤，代碼表述有少量語法錯誤（筆誤性質(zhì)），可得7-8分
（4）能實現(xiàn)題目要求的功能，算法有bug(對某個特殊輸入，可能得不到正確結果），可得4-6分
（5）能表達出核心功能的實現(xiàn)方法，算法有邏輯錯誤，可得2-3分
（6）核心功能沒有實現(xiàn)，算法有嚴重邏輯錯誤，可得0-2分
參考代碼如下
void Sort(LinkList &L)
{
?p = L->next->next; ? ? ??
L->next->next=NULL; ? ?
?while( p!=NULL){
? ?q = p->next; ? ? ? ? ?
? ?pre = L; ? ? ? ? ? ? ?
? ?while( pre->next!=NULL && pre->next->data > p-data){
? ? ? pre = pre->data;
? ?}
? ?p->next = pre->next; ?
? ?pre->next = p;
? ?p=q; ? ? ? ? ? ? ? ?
?}
}
時間復雜度為O( )
?
解析：?
?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-824162.html

?

?

?

?

?

?

?

?

?

?

?

?

到了這里，關于鄭州輕工業(yè)大學近幾年數(shù)據(jù)結構試卷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！