《南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級(jí)加答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級(jí)加答案（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu)09
一. 填空題（26分，每空2分）
1. 聲明抽象數(shù)據(jù)類型的目的是________________________________________。
2. 已知結(jié)點(diǎn)類Node有data和next域，下列數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)聲明分別為
__________________________________和_____________________________________。
3. 已知SString s1("aababbabac"),s2("aba");，執(zhí)行下列語(yǔ)句后，s1字符串是______________。
s1.replaceAll(s1.sub
2、string(0,1),s2);
s1.removeAll(s2.substring(0,2));
4. 中綴表達(dá)式A+B*(C-D*(E+F)/G+H)-(I+J)*K的后綴表達(dá)式為_(kāi)_____________________。
5. 設(shè)一個(gè)順序循環(huán)隊(duì)列容量為60，當(dāng)front=47，rear=23時(shí)，該隊(duì)列有__________個(gè)元素。
6. 已知二維數(shù)組a[10][8]采用行主序存儲(chǔ)，數(shù)組首地址是1000，每個(gè)元素占用4字節(jié)，則數(shù)組元素a[4][5]的存儲(chǔ)地址是__________________________。
7. 已知一棵完全二叉樹(shù)的根（第0個(gè)）結(jié)點(diǎn)層次為1，則
3、第100個(gè)結(jié)點(diǎn)的層次為_(kāi)______。
8. 中根遍歷序列和后根遍歷序列相反的二叉樹(shù)是_________________________________。
9. 由256個(gè)權(quán)值構(gòu)造一棵哈夫曼樹(shù)，則該二叉樹(shù)共有________________結(jié)點(diǎn)。
10. 由n個(gè)頂點(diǎn)組成的無(wú)向連通圖，最多可以有_____________________條邊。
11. 10個(gè)元素的排序數(shù)據(jù)序列采用折半查找的平均查找長(zhǎng)度 是（寫(xiě)出算式）_____________________________________________________。
12. 已知關(guān)鍵字序列為{67,41,34,10,6
4、9,24,78,54,41*}，采用快速排序算法按升序排序，以第一個(gè)元素為基準(zhǔn)值，其第一趟排序后的關(guān)鍵字序列為_(kāi)___________________________。
二. 問(wèn)答題（45分，每小題5分）
1. 已知目標(biāo)串為"aabcbabcaabcaababc"，模式串為"abcaababc"，寫(xiě)出模式串改進(jìn)的next數(shù)組；畫(huà)出KMP算法的匹配過(guò)程，給出字符比較次數(shù)。
2. 什么是棧和隊(duì)列？?jī)烧哂泻萎愅?？什么情況下需要使用棧或隊(duì)列？采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)需要移動(dòng)數(shù)據(jù)元素嗎？為什么？什么是隊(duì)列的假溢出？為什么順序存儲(chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出？怎樣解決隊(duì)列的假
5、溢出問(wèn)題？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出嗎？順序存儲(chǔ)結(jié)構(gòu)的棧會(huì)出現(xiàn)假溢出嗎？為什么？
3. 已知一棵二叉樹(shù)中根次序遍歷序列為GCBHKAMFDJE，后根次序遍歷序列為CBGHMAJEDFK，畫(huà)出這棵二叉樹(shù)并進(jìn)行中序線索化。
4. 設(shè)一段正文由字符集{A,B,C,D,E,F,G,H}組成，其中每個(gè)字符在正文中的出現(xiàn)次數(shù)依次為{23,5,17,4,9,31,29,18}，采用哈夫曼編碼對(duì)這段正文進(jìn)行壓縮存儲(chǔ)，畫(huà)出所構(gòu)造的哈夫曼樹(shù)，并寫(xiě)出每個(gè)字符的哈夫曼編碼。
5. 刪除以下帶權(quán)無(wú)向圖中的頂點(diǎn)D，畫(huà)出刪除D后圖的鄰接矩陣表示和鄰接表表示。
6. 構(gòu)造以下帶權(quán)無(wú)向圖的最小生成樹(shù)，
6、并給出該最小生成樹(shù)的代價(jià)。
7. 已知關(guān)鍵字序列為{16,74,60,43,54,90,46,31,29,88,71,64,50}，散列表長(zhǎng)度為11，采用除留余數(shù)法的散列函數(shù)為hash(k)=k % 11，畫(huà)出采用鏈地址法構(gòu)造的散列表，計(jì)算 （寫(xiě)出算式）。
8. 畫(huà)出對(duì)關(guān)鍵字序列{93,17,56,42,78,15,42*,25,19}進(jìn)行希爾排序（升序）的每一趟排序過(guò)程，說(shuō)明希爾排序算法的穩(wěn)定性并解釋原因，以及希爾排序適用于什么存儲(chǔ)結(jié)構(gòu)。
9. 將關(guān)鍵字序列{29,10,25,26,58,12,31,18,47}用篩選法分別建成一個(gè)最大堆和一個(gè)最小堆，寫(xiě)出兩個(gè)堆序列并畫(huà)出其對(duì)
7、應(yīng)的完全二叉樹(shù)。
三. 程序閱讀和改錯(cuò)題（15分，每小題5分）
1. 閱讀以下函數(shù)，回答問(wèn)題。
template
void CirHDoublyLinkedList::concat(CirHDoublyLinkedList &list)
{
DLinkNode *rear=head->prev;
rear->next = list.head->next;
list.head->next->prev = rear;
rear=list.head->prev;
rear->next =
8、 this->head;
this->head->prev = rear;
list.head->prev = list.head;
list.head->next = list.head;
}
上述函數(shù)功能是什么？以下調(diào)用語(yǔ)句的運(yùn)行結(jié)果是什么？
CirHDoublyLinkedList source("abcdef",6), list("xyz",3);
source.concat(list);
cout<<"source："<
9、()函數(shù)欲刪除當(dāng)前字符串對(duì)象中的所有空格字符。
void SString::trim() //刪除串對(duì)象中的所有空格字符
{ int i=0;
while (element[i]!=' ' && element[i]!='\0') //尋找第1個(gè)空格
i++; //i記住第1個(gè)空格下標(biāo)
for (int j=i; element[j]!='\0'; j++)
if
10、 (element[j]!=' ')
element[i++] = element[j]; //非空格字符向前移動(dòng)到空格字符位置
len = i;
}
① 對(duì)于以下調(diào)用語(yǔ)句，運(yùn)行結(jié)果是什么？正確的運(yùn)行結(jié)果是什么？
SString str(" a bc d e f xyz");
str.trim();
cout<<"str="<
11、late
class TriNode //二叉樹(shù)的三叉鏈表結(jié)點(diǎn)類
{
public:
T data; //數(shù)據(jù)域，保存元素
TriNode *parent, *left, *right; //指針域，分別指向父母、左、右孩子結(jié)點(diǎn)
//構(gòu)造結(jié)點(diǎn)，參數(shù)依次分別指定元素、左孩子和右孩子結(jié)點(diǎn)
TriNode(T data, TriNode *left=NUL
12、L, TriNode *right=NULL)
{
this->data = data;
this->left = left;
this->right = right;
}
};
三叉鏈表表示的二叉樹(shù)類TriBinaryTree及部分函數(shù)聲明如下：
class TriBinaryTree //二叉樹(shù)類（三叉鏈表）
{
public:
TriNode *root;
13、 //指向根結(jié)點(diǎn)
TriBinaryTree(TriBinaryTree &bitree); //拷貝構(gòu)造函數(shù)
private:
TriNode* copy(TriNode *p); //復(fù)制以p為根的子二叉樹(shù)
};
template
TriBinaryTree::TriBinaryTree(TriBinaryTree &bitree) //拷貝構(gòu)造函數(shù)
{
this->root = copy(bitree
14、.root);
}
//復(fù)制以p為根的子二叉樹(shù)，返回新建子樹(shù)的根結(jié)點(diǎn)
template
TriNode* TriBinaryTree::copy(TriNode *p)
{
TriNode *q=NULL;
if (p!=NULL)
{
q = new TriNode(p->data);
q->left = copy(p->left);
q->right = copy(p->right);
}
return q;
}
上
15、述函數(shù)中存在什么錯(cuò)誤？如何改正？
四. 程序設(shè)計(jì)題（14分，每小題7分）
1. 在帶頭結(jié)點(diǎn)的單鏈表類HSLinkedList中，增加以下成員函數(shù)：
void HSLinkedList::removeAll(HSLinkedList &list) //刪除所有與list匹配的子表
2. 求二叉樹(shù)中指定結(jié)點(diǎn)的層次。
一. 填空題（26分，每空2分）
1. 使數(shù)據(jù)類型的定義和實(shí)現(xiàn)分離，使一種定義有多種實(shí)現(xiàn)。
2. Node*table[4]; Node t
16、able[4];
3. "abac"
4. ABCDEF+*G/-H+*+IJ+K*-
5. 36
6. 1148
7. 7
8. 右單支二叉樹(shù)（包括空二叉樹(shù)、只有根結(jié)點(diǎn)的二叉樹(shù)）
9. 511
10. n*(n-1)/2
11.
12. {41* 41 34 10 54 24} 67 {78 69}
二. 問(wèn)答題（45分，每小題5分）
1. 模式串"abcaababc"改進(jìn)的next數(shù)組為
j
0
1
2
3
4
5
6
7
8
模式串
a
b
c
a
a
b
a
b
c
17、
" "中最長(zhǎng)相同的前后綴子串長(zhǎng)度k
-1
0
0
0
1
1
2
1
2
與比較
≠
≠
=
=
=
≠
=
=
改進(jìn)的next[j]
-1
0
0
-1
1
0
2
0
0
2. 棧和隊(duì)列都屬于線性表結(jié)構(gòu)，它們是兩種特殊的線性表，棧的插入和刪除操作都在線性表的一端進(jìn)行，所以棧的特點(diǎn)是“后進(jìn)先出”；而隊(duì)列的插入和刪除操作分別在線性表的兩端進(jìn)行，所以隊(duì)列的特點(diǎn)是“先進(jìn)先出”。深度優(yōu)先搜索遍歷算法需要使用棧作為輔助結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法需要使用隊(duì)列作為輔助結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)不需要移動(dòng)數(shù)
18、據(jù)元素，因?yàn)闂：完?duì)列均不能進(jìn)行中間插入、刪除操作。
順序隊(duì)列，當(dāng)入隊(duì)的元素個(gè)數(shù)（包括已出隊(duì)元素）超過(guò)數(shù)組容量時(shí)，隊(duì)列尾下標(biāo)越界，數(shù)據(jù)溢出。此時(shí)，由于之前已有若干元素出隊(duì)，數(shù)組前部已空出許多存儲(chǔ)單元，所以，這種溢出并不是因存儲(chǔ)空間不夠而產(chǎn)生的，稱之為假溢出。順序隊(duì)列之所以會(huì)產(chǎn)生假溢出現(xiàn)象，是因?yàn)轫樞蜿?duì)列的存儲(chǔ)單元沒(méi)有重復(fù)使用機(jī)制。解決的辦法是將順序隊(duì)列設(shè)計(jì)成循環(huán)結(jié)構(gòu)。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列不會(huì)出現(xiàn)假溢出。因?yàn)槊看卧厝腙?duì)，都要申請(qǐng)新結(jié)點(diǎn)，數(shù)據(jù)不會(huì)溢出。順序存儲(chǔ)結(jié)構(gòu)的棧不會(huì)出現(xiàn)假溢出。因?yàn)轫樞驐５拇鎯?chǔ)單元可以重復(fù)使用，如果數(shù)組容量不夠，則是數(shù)據(jù)溢出，而不是假溢出。
(3)
19、
(4)
(5)
.
(6)
，代價(jià)是45
(7)
(8)
希爾排序算法是不穩(wěn)定的，因?yàn)榕c距離較遠(yuǎn)的元素進(jìn)行比較，不能保證排序穩(wěn)定性。希爾排序算法僅適用于順序存儲(chǔ)結(jié)構(gòu)，因?yàn)榕c距離較遠(yuǎn)的元素進(jìn)行比較，需要利用隨機(jī)存儲(chǔ)特性。
（9）
三. 程序閱讀題（15分，每小題5分）
1. 將list鏈表合并連接到當(dāng)前鏈表最后，設(shè)置list鏈表為空
source：(a, b, c, d, e, f, x, y, z)
list：()
2. ①運(yùn)行結(jié)果為“abcdefxyz e f xyz”，正確的運(yùn)行結(jié)果是“abc
20、defxyz”。
② trim()函數(shù)首先尋找串的第一個(gè)空格字符，用i記住空格字符下標(biāo)；再遍歷串，將串中的非空格字符（用j記住其下標(biāo)）逐個(gè)向前移動(dòng)到空格字符位置（i下標(biāo)）；算法存在錯(cuò)誤，刪除后沒(méi)將字符串結(jié)束符'\0'向前移動(dòng)到len處，導(dǎo)致cout輸出仍然到'\0'，如下圖所示。
③ 改正：函數(shù)體最后增加以下一句：
element[len] = '\0';
3. 深拷貝創(chuàng)建二叉樹(shù)時(shí)，沒(méi)有為各結(jié)點(diǎn)建立指向父母結(jié)點(diǎn)的鏈。改正如下：
① 當(dāng)TriNode構(gòu)造函數(shù)不指定parent時(shí)
template
TriNode* Tr
21、iBinaryTree::copy(TriNode *p)
{
TriNode *q=NULL;
if (p!=NULL)
{ q = new TriNode(p->data); //創(chuàng)建結(jié)點(diǎn)，父母結(jié)點(diǎn)parent為空
q->left = copy(p->left); //復(fù)制左子樹(shù)，遞歸調(diào)用
if (q->left!=NULL)
q->left->parent = q; //為
22、左孩子設(shè)置parent鏈
q->right = copy(p->right); //復(fù)制右子樹(shù)，遞歸調(diào)用
if (q->right!=NULL)
q->right->parent = q; //為右孩子設(shè)置parent鏈
}
return q; //返回建立子樹(shù)的根結(jié)點(diǎn)
}
② 如果TriNode類聲明以下構(gòu)造函數(shù)，參數(shù)包括指定父母結(jié)點(diǎn)：
TriNode(T data, Tri
23、Node *parent=NULL, TriNode *left=NULL, TriNode *right=NULL)
則TriNode類深拷貝構(gòu)造函數(shù)可實(shí)現(xiàn)如下：
template
TriBinaryTree::TriBinaryTree(TriBinaryTree &bitree) //拷貝構(gòu)造函數(shù)，深拷貝
{ this->root = copy(bitree.root, NULL, 1);
}
//復(fù)制以p為根的子二叉樹(shù)，parent指向p的父母結(jié)點(diǎn)，返回新建子樹(shù)的根結(jié)點(diǎn)
template
Tr
24、iNode* TriBinaryTree::copy(TriNode *p, TriNode *parent)
{
TriNode *q=NULL;
if (p!=NULL)
{ q = new TriNode(p->data, parent); //創(chuàng)建結(jié)點(diǎn)，父母結(jié)點(diǎn)是parent
q->left = copy(p->left, p); //復(fù)制左子樹(shù)，遞歸調(diào)用
q->right = copy(p->right, p);
25、 //復(fù)制右子樹(shù)，遞歸調(diào)用
}
return q; //返回建立子樹(shù)的根結(jié)點(diǎn)
}
四. 程序設(shè)計(jì)題（14分，每小題7分）
以下給出參考程序，閱卷老師可根據(jù)實(shí)際情況評(píng)分，重點(diǎn)是表達(dá)算法思想。
1. 在帶頭結(jié)點(diǎn)的單鏈表類HSLinkedList中，增加以下成員函數(shù)，刪除所有與list匹配的子表。
template
void HSLinkedList::removeAll(HSLinkedLis
26、t &list)
{ Node *start=head->next, *front=head;
while (start!=NULL)
{ Node *p=start, *q=list.head->next;
while (p!=NULL && q!=NULL && p->data==q->data) //一次匹配
{ p=p->next;
q=q->next;
}
if (q!=NULL)
27、 //一次匹配失敗，再進(jìn)行下一次匹配
{ front=start;
start=start->next;
}
else //一次匹配成功，刪除一個(gè)子表
{ q=list.head->next;
while (q!=NULL) //刪除從start開(kāi)始與list匹配的子表
{ front->next = start
28、->next; //刪除start結(jié)點(diǎn)
delete start;
start=front->next;
q=q->next;
}
}
}
}
2. 求二叉樹(shù)中指定結(jié)點(diǎn)的層次。
一棵二叉樹(shù)中結(jié)點(diǎn)所在的層次定義：令根結(jié)點(diǎn)的層次為1，其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1。
① 在二叉鏈表存儲(chǔ)的二叉樹(shù)類BinaryTree中增加成員函數(shù)如下：
template
int BinaryTr
29、ee::getLevel(T x) //返回x結(jié)點(diǎn)所在的層次
{ //若空樹(shù)或未查找到x返回-1
if (root==NULL)
return -1;
return getLevel(root, 1, x); //令根結(jié)點(diǎn)的層次為1
}
template
int BinaryTree::getLevel(BinaryNode *p, in
30、t i, T x)
{ //在以p結(jié)點(diǎn)（層次為i）為根的子樹(shù)中求x結(jié)點(diǎn)所在層次
if (p!=NULL)
{ if (p->data==x)
return i; //查找成功
int level = getLevel(p->left, i+1, x); //在左子樹(shù)查找
if (level!=-1)
return level;
31、
return getLevel(p->right, i+1, x); //繼續(xù)在右子樹(shù)中查找
}
return -1; //查找不成功
}
② 在二叉鏈表結(jié)點(diǎn)類BinaryNode中增加表示結(jié)點(diǎn)層次的成員變量level，結(jié)點(diǎn)構(gòu)造函數(shù)聲明如下：
BinaryNode(T data, BinaryNode *left=NULL, BinaryNode *right=NULL, int level=0)
構(gòu)造二叉樹(shù)時(shí)設(shè)置每個(gè)結(jié)點(diǎn)的層次
32、屬性。例如，二叉樹(shù)類BinaryTree的一種構(gòu)造函數(shù)聲明如下：
template
BinaryTree::BinaryTree(T prelist[], int n) //以標(biāo)明空子樹(shù)的先根序列構(gòu)造一棵二叉樹(shù)
{ int i=0;
root=create(prelist, n, i, NULL, 1); //根結(jié)點(diǎn)的層次為1
}
//以標(biāo)明空子樹(shù)的先根次序遍歷序列創(chuàng)建一棵子樹(shù)，該子樹(shù)根結(jié)點(diǎn)是prelist[i]，
//根結(jié)點(diǎn)層次是level，其父母結(jié)點(diǎn)由parent指向，返回創(chuàng)建子樹(shù)的
33、根結(jié)點(diǎn)指針
template
BinaryNode* BinaryTree::create(T prelist[], int n, int &i, int level)
{ BinaryNode *p=NULL;
if (i(elem, NULL, NULL, level); //創(chuàng)建結(jié)點(diǎn)，層次是level
p->left = create(
34、prelist, n, i, level+1); //創(chuàng)建左子樹(shù)
p->right = create(prelist, n, i, level+1); //創(chuàng)建右子樹(shù)
}
}
return p;
}
BinaryTree類的getLevel(p)成員函數(shù)聲明如下，算法同查找。
template
int BinaryTree::getLevel(T x) //返回值為x結(jié)點(diǎn)所在的層次，若空樹(shù)或未查找到x返回-1
{ BinaryN
35、ode *find=search(x); //查找
if (find==NULL)
return -1;
return find->level;
}
在二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)時(shí)，以插入結(jié)點(diǎn)為根的子樹(shù)中所有結(jié)點(diǎn)的層次也隨之改變，因此，BinaryTree類需要提供以下setLevel()方法動(dòng)態(tài)維護(hù)層次屬性。
//設(shè)置以p結(jié)點(diǎn)（層次為level）為根的子樹(shù)中所有結(jié)點(diǎn)的層次
template
void BinaryTree::setLevel(BinaryNode *p, int level)
{ if (p!=NULL)
{ p->level = level;
setLevel(p->left, level+1);
setLevel(p->right, level+1);
}
}
南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級(jí)加答案
