《數(shù)據(jù)結(jié)構(gòu)樣卷答案09級.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、南京工程學(xué)院試題評分標(biāo)準(zhǔn)及參考答案(樣)共7頁第1頁2010/2011學(xué)年第2學(xué)期課程所屬部門：計(jì)算機(jī)工程學(xué)院課程名稱：數(shù)據(jù)結(jié)構(gòu)使用班級：計(jì)算機(jī)專業(yè)2009級各班制作人：葉核亞、黃緯2011年5月24日一.填空題（26分，每空2分）（1）使數(shù)據(jù)類型的定義和實(shí)現(xiàn)分離，使一種定義有多種實(shí)現(xiàn)。（2）Node*table[4];Nodetable[4];（3）"abac"（4）ABCDEF+*G/-H+*+IJ+K*-（5）36（6）1148（7）7（8）右單支二叉樹（包括空二叉樹、只有根結(jié)點(diǎn)的二叉樹）（9）511（10）n*(n-1)/2（11）（12

2、）{41*4134105424}67{7869}二.問答題（45分，每小題5分）（1）模式串"abcaababc"改進(jìn)的next數(shù)組為j012345678模式串a(chǎn)bcaababc""中最長相同的前后綴子串長度k-100011212與比較≠≠===≠==改進(jìn)的next[j]-100-110200（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)先搜索遍歷算法需要使

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

4、順序棧的存儲單元可以重復(fù)使用，如果數(shù)組容量不夠，則是數(shù)據(jù)溢出，而不是假溢出。（3）（4）（5）（6），代價(jià)是45（7）（8）希爾排序算法是不穩(wěn)定的，因?yàn)榕c距離較遠(yuǎn)的元素進(jìn)行比較，不能保證排序穩(wěn)定性。希爾排序算法僅適用于順序存儲結(jié)構(gòu)，因?yàn)榕c距離較遠(yuǎn)的元素進(jìn)行比較，需要利用隨機(jī)存儲特性。（9）三.程序閱讀題（15分，每小題5分）（1）將list鏈表合并連接到當(dāng)前鏈表最后，設(shè)置list鏈表為空source：(a,b,c,d,e,f,x,y,z)list：()（2）①運(yùn)行結(jié)果為“abcdefxyzefxyz”，正確的運(yùn)行結(jié)果是“abcdefxyz”。②trim()函

5、數(shù)首先尋找串的第一個(gè)空格字符，用i記住空格字符下標(biāo)；再遍歷串，將串中的非空格字符（用j記住其下標(biāo)）逐個(gè)向前移動到空格字符位置（i下標(biāo)）；算法存在錯(cuò)誤，刪除后沒將字符串結(jié)束符'