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

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

1、南京工程學(xué)院試卷（樣）共 8 頁(yè) 第1頁(yè)2010 /2011 學(xué)年 第 2 學(xué)期 課程所屬部門： 計(jì)算機(jī)工程學(xué)院 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 考試方式： 閉卷 使用班級(jí)： 計(jì)算機(jī)專業(yè)2009級(jí)各班 命題人：葉核亞、黃緯 教研室主任審核： 主管領(lǐng)導(dǎo)批準(zhǔn)： 班級(jí) 學(xué)號(hào) 姓名 題號(hào)一二三四五總分得分本題得分一. 填空題（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.substrin

2、g(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è)一個(gè)順序循環(huán)隊(duì)列容量為60，當(dāng)front=47，rear=23時(shí)，該隊(duì)列有_個(gè)元素。6. 已知二維數(shù)組a108采用行主序存儲(chǔ)，數(shù)組首地址是1000，每個(gè)元素占用4字節(jié)，則數(shù)組元素a45的存儲(chǔ)地址是_。7. 已知一棵完全二叉樹的根（第0個(gè)）結(jié)點(diǎn)層次為1，則第100個(gè)結(jié)點(diǎn)的層次為_。8. 中根遍歷序列和后根遍歷序列相反的二叉樹是_。9. 由256個(gè)權(quán)值構(gòu)造一棵哈夫曼樹，則該二叉樹共有_結(jié)點(diǎn)。10. 由n個(gè)頂點(diǎn)組成的無(wú)向連

3、通圖，最多可以有_條邊。11. 10個(gè)元素的排序數(shù)據(jù)序列采用折半查找的平均查找長(zhǎng)度是（寫出算式）_。12. 已知關(guān)鍵字序列為67,41,34,10,69,24,78,54,41*，采用快速排序算法按升序排序，以第一個(gè)元素為基準(zhǔn)值，其第一趟排序后的關(guān)鍵字序列為_。二. 問(wèn)答題（45分，每小題5分）1. 已知目標(biāo)串為aabcbabcaabcaababc，模式串為abcaababc，寫出模式串改進(jìn)的next數(shù)組；畫出KMP算法的匹配過(guò)程，給出字符比較次數(shù)。2. 什么是棧和隊(duì)列？?jī)烧哂泻萎愅?？什么情況下需要使用?；蜿?duì)列？采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)需要移動(dòng)數(shù)據(jù)元素嗎？為什么？什么

4、是隊(duì)列的假溢出？為什么順序存儲(chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出？怎樣解決隊(duì)列的假溢出問(wèn)題？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出嗎？順序存儲(chǔ)結(jié)構(gòu)的棧會(huì)出現(xiàn)假溢出嗎？為什么？3. 已知一棵二叉樹中根次序遍歷序列為GCBHKAMFDJE，后根次序遍歷序列為CBGHMAJEDFK，畫出這棵二叉樹并進(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ǔ)，畫出所構(gòu)造的哈夫曼樹，并寫出每個(gè)字符的哈夫曼編碼。5. 刪除以下帶權(quán)無(wú)向圖中的頂點(diǎn)D，畫出刪除D后圖的鄰接矩陣表示和鄰接表表示。6. 構(gòu)造

5、以下帶權(quán)無(wú)向圖的最小生成樹，并給出該最小生成樹的代價(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，畫出采用鏈地址法構(gòu)造的散列表，計(jì)算（寫出算式）。8. 畫出對(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è)最小堆，寫出兩個(gè)堆序列并畫出其對(duì)應(yīng)的完全

6、二叉樹。三. 程序閱讀和改錯(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 = this-head; this-head-prev = rear; list.head-prev = list.head; list.head-

7、next = list.head; 上述函數(shù)功能是什么？以下調(diào)用語(yǔ)句的運(yùn)行結(jié)果是什么？CirHDoublyLinkedList source(abcdef,6), list(xyz,3);source.concat(list);coutsource：sourcelist：list;2. 下列trim()函數(shù)欲刪除當(dāng)前字符串對(duì)象中的所有空格字符。void SString:trim() /刪除串對(duì)象中的所有空格字符 int i=0; while (elementi!= & elementi!=0) /尋找第1個(gè)空格 i+; /i記住第1個(gè)空格下標(biāo) for (int j=i; elementj!=0

8、; j+) if (elementj!= ) elementi+ = elementj; /非空格字符向前移動(dòng)到空格字符位置 len = i; 對(duì)于以下調(diào)用語(yǔ)句，運(yùn)行結(jié)果是什么？正確的運(yùn)行結(jié)果是什么？SString str( a bc d e f xyz);str.trim();coutstr=strendl; trim()函數(shù)怎樣實(shí)現(xiàn)所求功能？算法存在什么錯(cuò)誤？ 如何改正？3. 已知三叉鏈表表示的二叉樹結(jié)點(diǎn)類TriNode聲明如下：template class TriNode /二叉樹的三叉鏈表結(jié)點(diǎn)類 public: T data; /數(shù)據(jù)域，保存元素 TriNode *parent, *l

9、eft, *right; /指針域，分別指向父母、左、右孩子結(jié)點(diǎn) /構(gòu)造結(jié)點(diǎn)，參數(shù)依次分別指定元素、左孩子和右孩子結(jié)點(diǎn) TriNode(T data, TriNode *left=NULL, TriNode *right=NULL) this-data = data; this-left = left; this-right = right; ;三叉鏈表表示的二叉樹類TriBinaryTree及部分函數(shù)聲明如下：class TriBinaryTree /二叉樹類（三叉鏈表） public: TriNode *root; /指向根結(jié)點(diǎn) TriBinaryTree(TriBinaryTree &b

10、itree); /拷貝構(gòu)造函數(shù) private: TriNode* copy(TriNode *p); /復(fù)制以p為根的子二叉樹;template TriBinaryTree:TriBinaryTree(TriBinaryTree &bitree) /拷貝構(gòu)造函數(shù) this-root = copy(bitree.root);/復(fù)制以p為根的子二叉樹，返回新建子樹的根結(jié)點(diǎn)template TriNode* TriBinaryTree:copy(TriNode *p) TriNode *q=NULL; if (p!=NULL) q = new TriNode(p-data); q-left = c

11、opy(p-left); q-right = copy(p-right); return q; 上述函數(shù)中存在什么錯(cuò)誤？如何改正？四. 程序設(shè)計(jì)題（14分，每小題7分） 1. 在帶頭結(jié)點(diǎn)的單鏈表類HSLinkedList中，增加以下成員函數(shù)： void HSLinkedList:removeAll(HSLinkedList &list) /刪除所有與list匹配的子表2. 求二叉樹中指定結(jié)點(diǎn)的層次。 南京工程學(xué)院試卷 共 8 頁(yè) 第 2 頁(yè) 本題得分 南京工程學(xué)院試卷 共 8 頁(yè) 第 3 頁(yè) 南京工程學(xué)院試卷 共 8 頁(yè) 第 4 頁(yè) 南京工程學(xué)院試卷 共 8 頁(yè) 第 5 頁(yè) 本題得分 南京工程

12、學(xué)院試卷 共 8 頁(yè) 第 6 頁(yè) 南京工程學(xué)院試卷 共 8 頁(yè) 第 7 頁(yè) 南京工程學(xué)院試卷 共 8 頁(yè) 第 8 頁(yè) 本題得分南京工程學(xué)院試題評(píng)分標(biāo)準(zhǔn)及參考答案(樣) 共7頁(yè) 第 1 頁(yè) 2010 / 2011 學(xué)年第 2 學(xué)期課程所屬部門： 計(jì)算機(jī)工程學(xué)院 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 使用班級(jí)：計(jì)算機(jī)專業(yè)2009級(jí)各班 制作人：葉核亞、黃緯 2011年5月24日五. 填空題（26分，每空2分）1. 使數(shù)據(jù)類型的定義和實(shí)現(xiàn)分離，使一種定義有多種實(shí)現(xiàn)。2. Node* table4;Node table4;3. abac4. ABCDEF+*G/-H+*+IJ+K*-5. 366. 11487. 78

13、. 右單支二叉樹（包括空二叉樹、只有根結(jié)點(diǎn)的二叉樹）9. 51110. n*(n-1)/211. 12. 41* 41 34 10 54 24 67 78 69六. 問(wèn)答題（45分，每小題5分）1. 模式串a(chǎn)bcaababc改進(jìn)的next數(shù)組為j012345678模式串a(chǎn)bcaababc中最長(zhǎng)相同的前后綴子串長(zhǎng)度k-100011212與比較=改進(jìn)的nextj-100-1102002. 棧和隊(duì)列都屬于線性表結(jié)構(gòu)，它們是兩種特殊的線性表，棧的插入和刪除操作都在線性表的一端進(jìn)行，所以棧的特點(diǎn)是“后進(jìn)先出”；而隊(duì)列的插入和刪除操作分別在線性表的兩端進(jìn)行，所以隊(duì)列的特點(diǎn)是“先進(jìn)先出”。深度優(yōu)先搜索遍歷算

14、法需要使用棧作為輔助結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法需要使用隊(duì)列作為輔助結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)不需要移動(dòng)數(shù)據(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ì)

15、出現(xiàn)假溢出。因?yàn)轫樞驐５拇鎯?chǔ)單元可以重復(fù)使用，如果數(shù)組容量不夠，則是數(shù)據(jù)溢出，而不是假溢出。3. （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é)果是“abcdefxyz”。 tri

16、m()函數(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ù)體最后增加以下一句： elementlen = 0;3. 深拷貝創(chuàng)建二叉樹時(shí)，沒(méi)有為各結(jié)點(diǎn)建立指向父母結(jié)點(diǎn)的鏈。改正如下： 當(dāng)TriNode構(gòu)造函數(shù)不指定parent時(shí)template TriNode* TriBinaryTree:copy(TriNode *p) TriNode *q=NULL; if (p!=NULL) q = new Tri

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

18、 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為根的子二叉樹，parent指向p的父母結(jié)點(diǎn)，返回新建子樹的根結(jié)點(diǎn)template TriNode* TriBinaryTree:copy(TriNode *p, TriNode *parent) TriNode *q=NULL; if (p

19、!=NULL) q = new TriNode(p-data, parent); /創(chuàng)建結(jié)點(diǎn)，父母結(jié)點(diǎn)是parent q-left = copy(p-left, p); /復(fù)制左子樹，遞歸調(diào)用 q-right = copy(p-right, p); /復(fù)制右子樹，遞歸調(diào)用 return q; /返回建立子樹的根結(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(H

20、SLinkedList &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) /一次匹配失敗，再進(jìn)行下一次匹配 front=start; start=start-next; else /一次匹配成功，刪除一個(gè)子表 q=list.head-next; while (q!=NULL) /刪除從star

21、t開始與list匹配的子表 front-next = start-next; /刪除start結(jié)點(diǎn) delete start; start=front-next; q=q-next; 2. 求二叉樹中指定結(jié)點(diǎn)的層次。一棵二叉樹中結(jié)點(diǎn)所在的層次定義：令根結(jié)點(diǎn)的層次為1，其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1。 在二叉鏈表存儲(chǔ)的二叉樹類BinaryTree中增加成員函數(shù)如下：template int BinaryTree:getLevel(T x) /返回x結(jié)點(diǎn)所在的層次 /若空樹或未查找到x返回-1 if (root=NULL) return -1; return getLevel(root, 1

22、, x); /令根結(jié)點(diǎn)的層次為1template int BinaryTree:getLevel(BinaryNode *p, int i, T x) /在以p結(jié)點(diǎn)（層次為i）為根的子樹中求x結(jié)點(diǎn)所在層次 if (p!=NULL) if (p-data=x) return i; /查找成功 int level = getLevel(p-left, i+1, x); /在左子樹查找 if (level!=-1) return level; return getLevel(p-right, i+1, x); /繼續(xù)在右子樹中查找 return -1; /查找不成功 在二叉鏈表結(jié)點(diǎn)類BinaryNo

23、de中增加表示結(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è)置每個(gè)結(jié)點(diǎn)的層次屬性。例如，二叉樹類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é)點(diǎn)的層次為1 /以標(biāo)明空子樹的先根次序遍歷序列創(chuàng)

24、建一棵子樹，該子樹根結(jié)點(diǎn)是prelisti， /根結(jié)點(diǎn)層次是level，其父母結(jié)點(diǎn)由parent指向，返回創(chuàng)建子樹的根結(jié)點(diǎn)指針template BinaryNode* BinaryTree:create(T prelist, int n, int &i, int level) BinaryNode *p=NULL; if (in) T elem = prelisti+; if (elem!=NULL) p = new BinaryNode(elem, NULL, NULL, level); /創(chuàng)建結(jié)點(diǎn)，層次是level p-left = create(prelist, n, i, level+

25、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é)點(diǎn)所在的層次，若空樹或未查找到x返回-1 BinaryNode *find=search(x); /查找 if (find=NULL) return -1; return find-level;在二叉樹中插入一個(gè)結(jié)點(diǎn)時(shí)，以插入結(jié)點(diǎn)為根的子樹中所有結(jié)點(diǎn)的層次也隨之改變，因此，BinaryTree類

26、需要提供以下setLevel()方法動(dòng)態(tài)維護(hù)層次屬性。 /設(shè)置以p結(jié)點(diǎn)（層次為level）為根的子樹中所有結(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); 共7頁(yè) 第 2 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案 共7頁(yè) 第 3 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案 共7頁(yè) 第 4 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案 共7頁(yè) 第 5 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案 共7頁(yè) 第 6 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案 共7頁(yè) 第 7 頁(yè)南京工程學(xué)院評(píng)分標(biāo)準(zhǔn)及參考答案