南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級加答案

《南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級加答案》由會員分享，可在線閱讀，更多相關(guān)《南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級加答案（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)09 一. 填空題（26分，每空2分） 1. 聲明抽象數(shù)據(jù)類型的目的是________________________________________。 2. 已知結(jié)點類Node有data和next域，下列數(shù)據(jù)存儲結(jié)構(gòu)聲明分別為 __________________________________和_____________________________________。 3. 已知SString s1("aababbabac"),s2("aba");，執(zhí)行下列語句后，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á)式為______________________。 5. 設(shè)一個順序循環(huán)隊列容量為60，當(dāng)front=47，rear=23時，該隊列有__________個元素。 6. 已知二維數(shù)組a[10][8]采用行主序存儲，數(shù)組首地址是1000，每個元素占用4字節(jié)，則數(shù)組元素a[4][5]的存儲地址是__________________________。 7. 已知一棵完全二叉樹的根（第0個）結(jié)點層次為1，則

3、第100個結(jié)點的層次為_______。 8. 中根遍歷序列和后根遍歷序列相反的二叉樹是_________________________________。 9. 由256個權(quán)值構(gòu)造一棵哈夫曼樹，則該二叉樹共有________________結(jié)點。 10. 由n個頂點組成的無向連通圖，最多可以有_____________________條邊。 11. 10個元素的排序數(shù)據(jù)序列采用折半查找的平均查找長度 是（寫出算式）_____________________________________________________。 12. 已知關(guān)鍵字序列為{67,41,34,10,6

4、9,24,78,54,41*}，采用快速排序算法按升序排序，以第一個元素為基準(zhǔn)值，其第一趟排序后的關(guān)鍵字序列為____________________________。 二. 問答題（45分，每小題5分） 1. 已知目標(biāo)串為"aabcbabcaabcaababc"，模式串為"abcaababc"，寫出模式串改進(jìn)的next數(shù)組；畫出KMP算法的匹配過程，給出字符比較次數(shù)。 2. 什么是棧和隊列？兩者有何異同？什么情況下需要使用?；蜿犃?？采用順序存儲結(jié)構(gòu)的棧和隊列，在進(jìn)行插入、刪除操作時需要移動數(shù)據(jù)元素嗎？為什么？什么是隊列的假溢出？為什么順序存儲結(jié)構(gòu)隊列會出現(xiàn)假溢出？怎樣解決隊列的假

5、溢出問題？鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列會出現(xiàn)假溢出嗎？順序存儲結(jié)構(gòu)的棧會出現(xiàn)假溢出嗎？為什么？ 3. 已知一棵二叉樹中根次序遍歷序列為GCBHKAMFDJE，后根次序遍歷序列為CBGHMAJEDFK，畫出這棵二叉樹并進(jìn)行中序線索化。 4. 設(shè)一段正文由字符集{A,B,C,D,E,F,G,H}組成，其中每個字符在正文中的出現(xiàn)次數(shù)依次為{23,5,17,4,9,31,29,18}，采用哈夫曼編碼對這段正文進(jìn)行壓縮存儲，畫出所構(gòu)造的哈夫曼樹，并寫出每個字符的哈夫曼編碼。 5. 刪除以下帶權(quán)無向圖中的頂點D，畫出刪除D后圖的鄰接矩陣表示和鄰接表表示。 6. 構(gòu)造以下帶權(quán)無向圖的最小生成樹，

6、并給出該最小生成樹的代價。 7. 已知關(guān)鍵字序列為{16,74,60,43,54,90,46,31,29,88,71,64,50}，散列表長度為11，采用除留余數(shù)法的散列函數(shù)為hash(k)=k % 11，畫出采用鏈地址法構(gòu)造的散列表，計算 （寫出算式）。 8. 畫出對關(guān)鍵字序列{93,17,56,42,78,15,42*,25,19}進(jìn)行希爾排序（升序）的每一趟排序過程，說明希爾排序算法的穩(wěn)定性并解釋原因，以及希爾排序適用于什么存儲結(jié)構(gòu)。 9. 將關(guān)鍵字序列{29,10,25,26,58,12,31,18,47}用篩選法分別建成一個最大堆和一個最小堆，寫出兩個堆序列并畫出其對

7、應(yīng)的完全二叉樹。 三. 程序閱讀和改錯題（15分，每小題5分） 1. 閱讀以下函數(shù)，回答問題。 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)用語句的運行結(jié)果是什么？ CirHDoublyLinkedList source("abcdef",6), list("xyz",3); source.concat(list); cout<<"source："<

9、()函數(shù)欲刪除當(dāng)前字符串對象中的所有空格字符。 void SString::trim() //刪除串對象中的所有空格字符 { int i=0; while (element[i]!=' ' && element[i]!='\0') //尋找第1個空格 i++; //i記住第1個空格下標(biāo) for (int j=i; element[j]!='\0'; j++) if

10、 (element[j]!=' ') element[i++] = element[j]; //非空格字符向前移動到空格字符位置 len = i; } ① 對于以下調(diào)用語句，運行結(jié)果是什么？正確的運行結(jié)果是什么？ SString str(" a bc d e f xyz"); str.trim(); cout<<"str="<

11、late class TriNode //二叉樹的三叉鏈表結(jié)點類 { public: T data; //數(shù)據(jù)域，保存元素 TriNode *parent, *left, *right; //指針域，分別指向父母、左、右孩子結(jié)點 //構(gòu)造結(jié)點，參數(shù)依次分別指定元素、左孩子和右孩子結(jié)點 TriNode(T data, TriNode *left=NUL

12、L, TriNode *right=NULL) { this->data = data; this->left = left; this->right = right; } }; 三叉鏈表表示的二叉樹類TriBinaryTree及部分函數(shù)聲明如下： class TriBinaryTree //二叉樹類（三叉鏈表） { public: TriNode *root;

13、 //指向根結(jié)點 TriBinaryTree(TriBinaryTree &bitree); //拷貝構(gòu)造函數(shù) private: TriNode* copy(TriNode *p); //復(fù)制以p為根的子二叉樹 }; template TriBinaryTree::TriBinaryTree(TriBinaryTree &bitree) //拷貝構(gòu)造函數(shù) { this->root = copy(bitree

14、.root); } //復(fù)制以p為根的子二叉樹，返回新建子樹的根結(jié)點 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ù)中存在什么錯誤？如何改正？ 四. 程序設(shè)計題（14分，每小題7分） 1. 在帶頭結(jié)點的單鏈表類HSLinkedList中，增加以下成員函數(shù)： void HSLinkedList::removeAll(HSLinkedList &list) //刪除所有與list匹配的子表 2. 求二叉樹中指定結(jié)點的層次。 一. 填空題（26分，每空2分） 1. 使數(shù)據(jù)類型的定義和實現(xiàn)分離，使一種定義有多種實現(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. 右單支二叉樹（包括空二叉樹、只有根結(jié)點的二叉樹） 9. 511 10. n*(n-1)/2 11. 12. {41* 41 34 10 54 24} 67 {78 69} 二. 問答題（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、 " "中最長相同的前后綴子串長度k -1 0 0 0 1 1 2 1 2 與比較 ≠ ≠ = = = ≠ = = 改進(jìn)的next[j] -1 0 0 -1 1 0 2 0 0 2. 棧和隊列都屬于線性表結(jié)構(gòu)，它們是兩種特殊的線性表，棧的插入和刪除操作都在線性表的一端進(jìn)行，所以棧的特點是“后進(jìn)先出”；而隊列的插入和刪除操作分別在線性表的兩端進(jìn)行，所以隊列的特點是“先進(jìn)先出”。深度優(yōu)先搜索遍歷算法需要使用棧作為輔助結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法需要使用隊列作為輔助結(jié)構(gòu)。采用順序存儲結(jié)構(gòu)的棧和隊列，在進(jìn)行插入、刪除操作時不需要移動數(shù)

18、據(jù)元素，因為棧和隊列均不能進(jìn)行中間插入、刪除操作。 順序隊列，當(dāng)入隊的元素個數(shù)（包括已出隊元素）超過數(shù)組容量時，隊列尾下標(biāo)越界，數(shù)據(jù)溢出。此時，由于之前已有若干元素出隊，數(shù)組前部已空出許多存儲單元，所以，這種溢出并不是因存儲空間不夠而產(chǎn)生的，稱之為假溢出。順序隊列之所以會產(chǎn)生假溢出現(xiàn)象，是因為順序隊列的存儲單元沒有重復(fù)使用機制。解決的辦法是將順序隊列設(shè)計成循環(huán)結(jié)構(gòu)。 鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列不會出現(xiàn)假溢出。因為每次元素入隊，都要申請新結(jié)點，數(shù)據(jù)不會溢出。順序存儲結(jié)構(gòu)的棧不會出現(xiàn)假溢出。因為順序棧的存儲單元可以重復(fù)使用，如果數(shù)組容量不夠，則是數(shù)據(jù)溢出，而不是假溢出。 (3)

19、 (4) (5) . (6) ，代價是45 (7) (8) 希爾排序算法是不穩(wěn)定的，因為與距離較遠(yuǎn)的元素進(jìn)行比較，不能保證排序穩(wěn)定性。希爾排序算法僅適用于順序存儲結(jié)構(gòu)，因為與距離較遠(yuǎn)的元素進(jìn)行比較，需要利用隨機存儲特性。 （9） 三. 程序閱讀題（15分，每小題5分） 1. 將list鏈表合并連接到當(dāng)前鏈表最后，設(shè)置list鏈表為空 source：(a, b, c, d, e, f, x, y, z) list：() 2. ①運行結(jié)果為“abcdefxyz e f xyz”，正確的運行結(jié)果是“abc

20、defxyz”。 ② trim()函數(shù)首先尋找串的第一個空格字符，用i記住空格字符下標(biāo)；再遍歷串，將串中的非空格字符（用j記住其下標(biāo)）逐個向前移動到空格字符位置（i下標(biāo)）；算法存在錯誤，刪除后沒將字符串結(jié)束符'\0'向前移動到len處，導(dǎo)致cout輸出仍然到'\0'，如下圖所示。 ③ 改正：函數(shù)體最后增加以下一句： element[len] = '\0'; 3. 深拷貝創(chuàng)建二叉樹時，沒有為各結(jié)點建立指向父母結(jié)點的鏈。改正如下： ① 當(dāng)TriNode構(gòu)造函數(shù)不指定parent時 template TriNode* Tr

21、iBinaryTree::copy(TriNode *p) { TriNode *q=NULL; if (p!=NULL) { q = new TriNode(p->data); //創(chuàng)建結(jié)點，父母結(jié)點parent為空 q->left = copy(p->left); //復(fù)制左子樹，遞歸調(diào)用 if (q->left!=NULL) q->left->parent = q; //為

22、左孩子設(shè)置parent鏈 q->right = copy(p->right); //復(fù)制右子樹，遞歸調(diào)用 if (q->right!=NULL) q->right->parent = q; //為右孩子設(shè)置parent鏈 } return q; //返回建立子樹的根結(jié)點 } ② 如果TriNode類聲明以下構(gòu)造函數(shù)，參數(shù)包括指定父母結(jié)點： TriNode(T data, Tri

23、Node *parent=NULL, TriNode *left=NULL, TriNode *right=NULL) 則TriNode類深拷貝構(gòu)造函數(shù)可實現(xiàn)如下： template TriBinaryTree::TriBinaryTree(TriBinaryTree &bitree) //拷貝構(gòu)造函數(shù)，深拷貝 { this->root = copy(bitree.root, NULL, 1); } //復(fù)制以p為根的子二叉樹，parent指向p的父母結(jié)點，返回新建子樹的根結(jié)點 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é)點，父母結(jié)點是parent q->left = copy(p->left, p); //復(fù)制左子樹，遞歸調(diào)用 q->right = copy(p->right, p);

25、 //復(fù)制右子樹，遞歸調(diào)用 } return q; //返回建立子樹的根結(jié)點 } 四. 程序設(shè)計題（14分，每小題7分） 以下給出參考程序，閱卷老師可根據(jù)實際情況評分，重點是表達(dá)算法思想。 1. 在帶頭結(jié)點的單鏈表類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 //一次匹配成功，刪除一個子表 { q=list.head->next; while (q!=NULL) //刪除從start開始與list匹配的子表 { front->next = start

28、->next; //刪除start結(jié)點 delete start; start=front->next; q=q->next; } } } } 2. 求二叉樹中指定結(jié)點的層次。 一棵二叉樹中結(jié)點所在的層次定義：令根結(jié)點的層次為1，其他結(jié)點的層次是其父母結(jié)點的層次加1。 ① 在二叉鏈表存儲的二叉樹類BinaryTree中增加成員函數(shù)如下： template int BinaryTr

29、ee::getLevel(T x) //返回x結(jié)點所在的層次 { //若空樹或未查找到x返回-1 if (root==NULL) return -1; return getLevel(root, 1, x); //令根結(jié)點的層次為1 } template int BinaryTree::getLevel(BinaryNode *p, in

30、t i, T x) { //在以p結(jié)點（層次為i）為根的子樹中求x結(jié)點所在層次 if (p!=NULL) { if (p->data==x) return i; //查找成功 int level = getLevel(p->left, i+1, x); //在左子樹查找 if (level!=-1) return level;

31、 return getLevel(p->right, i+1, x); //繼續(xù)在右子樹中查找 } return -1; //查找不成功 } ② 在二叉鏈表結(jié)點類BinaryNode中增加表示結(jié)點層次的成員變量level，結(jié)點構(gòu)造函數(shù)聲明如下： BinaryNode(T data, BinaryNode *left=NULL, BinaryNode *right=NULL, int level=0) 構(gòu)造二叉樹時設(shè)置每個結(jié)點的層次

32、屬性。例如，二叉樹類BinaryTree的一種構(gòu)造函數(shù)聲明如下： template BinaryTree::BinaryTree(T prelist[], int n) //以標(biāo)明空子樹的先根序列構(gòu)造一棵二叉樹 { int i=0; root=create(prelist, n, i, NULL, 1); //根結(jié)點的層次為1 } //以標(biāo)明空子樹的先根次序遍歷序列創(chuàng)建一棵子樹，該子樹根結(jié)點是prelist[i]， //根結(jié)點層次是level，其父母結(jié)點由parent指向，返回創(chuàng)建子樹的

33、根結(jié)點指針 template BinaryNode* BinaryTree::create(T prelist[], int n, int &i, int level) { BinaryNode *p=NULL; if (i(elem, NULL, NULL, level); //創(chuàng)建結(jié)點，層次是level p->left = create(

34、prelist, n, i, level+1); //創(chuàng)建左子樹 p->right = create(prelist, n, i, level+1); //創(chuàng)建右子樹 } } return p; } BinaryTree類的getLevel(p)成員函數(shù)聲明如下，算法同查找。 template int BinaryTree::getLevel(T x) //返回值為x結(jié)點所在的層次，若空樹或未查找到x返回-1 { BinaryN

35、ode *find=search(x); //查找 if (find==NULL) return -1; return find->level; } 在二叉樹中插入一個結(jié)點時，以插入結(jié)點為根的子樹中所有結(jié)點的層次也隨之改變，因此，BinaryTree類需要提供以下setLevel()方法動態(tài)維護層次屬性。 //設(shè)置以p結(jié)點（層次為level）為根的子樹中所有結(jié)點的層次 template void BinaryTree::setLevel(BinaryNode *p, int level) { if (p!=NULL) { p->level = level; setLevel(p->left, level+1); setLevel(p->right, level+1); } }