2010年數(shù)據(jù)結(jié)構(gòu)期末考試試卷答案

蝸牛在線更多免費(fèi)學(xué)習(xí)資料等待您的光臨！數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A）一、選擇題（每小題2分，共24分）1．計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(A)A.數(shù)據(jù)B.數(shù)據(jù)元素D.數(shù)據(jù)類型C.數(shù)據(jù)結(jié)構(gòu)2．棧和隊(duì)列都是（A）A．限制存取位置的線性結(jié)構(gòu)B．順序存儲(chǔ)的線性結(jié)構(gòu)C．鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)D．限制存取位置的非線性結(jié)構(gòu)3．鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(DA.插入操作更加方便)B.刪除操作更加方便D.不會(huì)出現(xiàn)上溢的情況C.不會(huì)出現(xiàn)下溢的情況4．采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可分別簡(jiǎn)稱為(B)A.主串和子串B.順序串和鏈串C.目標(biāo)串和模式串D.變量串和常量串5．一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是：BA.110C.100B.108D.1206．串是一種特殊的線性表，其特殊性體現(xiàn)在：BA.可以順序存儲(chǔ)C.可以鏈接存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符D.數(shù)據(jù)元素可以是多個(gè)字符7．設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為：CA.2hB.2h-1D.h+1C.2h+1軟件開(kāi)發(fā)網(wǎng)8．樹(shù)的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹(shù)的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)叫做這棵樹(shù)對(duì)應(yīng)的二叉樹(shù)。下列結(jié)論哪個(gè)正確？AA.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同B.樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同C.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同D.以上都不對(duì)9．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有多少邊？CA.nB.n(n-1)D.2nC.n(n-1)/210．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的多少倍?CA.1/2C.2B.1D.411．當(dāng)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)時(shí)，若樹(shù)中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，則新結(jié)點(diǎn)將成為（A）A．左子樹(shù)的葉子結(jié)點(diǎn)C．右子樹(shù)的葉子結(jié)點(diǎn)B．左子樹(shù)的分支結(jié)點(diǎn)D．右子樹(shù)的分支結(jié)點(diǎn)軟件開(kāi)發(fā)網(wǎng)12．對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是(D)A.35和41C.15和44B.23和39D.25和51二、已知某棵二叉樹(shù)的前序遍歷結(jié)果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結(jié)果為D,B,G,E,A,H,F,I,J,C。請(qǐng)畫(huà)出二叉的具體結(jié)構(gòu)。（注意要寫(xiě)出具體步驟）（10分）原理見(jiàn)課本128頁(yè)三、有圖如下，請(qǐng)寫(xiě)出從頂點(diǎn)；C0-C1-C3-C4-C5-C2：C0-C1-C2-C3-C4-C5c0出發(fā)的深度優(yōu)先及寬度優(yōu)先遍歷的結(jié)果。(10分)深度優(yōu)先寬度優(yōu)先四、有圖如下，按Kruskal算法求出其最小生成樹(shù)。要求寫(xiě)出完整的步驟。（10分）原理見(jiàn)課本250頁(yè)五、給定線性表（12，23，45，66，76，88，93，103，166），值12，93，166的過(guò)程。并寫(xiě)出二分查找的算法。（20分）012345678試寫(xiě)出在其上進(jìn)行二分查找關(guān)鍵字12234566768893103166過(guò)程：mid=(0+8)/2=4high=3,low=0mid=1high=0,low=0mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8low=8mid=8算法：見(jiàn)課本84頁(yè)上六、知單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為Datanext下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L進(jìn)行簡(jiǎn)單選擇排序，使得L中的元素按值從小到大排列。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。(可用文字說(shuō)明該算法的基本思想及執(zhí)行的過(guò)程，10分)voidSelectSort(LinkedListL){LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL){min=p;q=p->next;while(q!=NULL){if(q=q->next;}(2))min=q;if((3)){rcd=p->data;p->data=min->data;min->data=rcd;}(4);}}本題不會(huì)。嘿嘿。。。。七、一個(gè)完整的算法應(yīng)該具有哪幾個(gè)基本性質(zhì)？分別簡(jiǎn)要說(shuō)明每一性質(zhì)的含意。(5分)輸入：四個(gè)基本性質(zhì)：1.輸入：有零個(gè)或多個(gè)有外部提供的量作為算法的輸入2：輸出：算法產(chǎn)生至少一個(gè)量作為輸出3.：確定性：組成算法的每條指令是清晰的，無(wú)歧異的。4.：有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的八、何謂隊(duì)列的"假溢"現(xiàn)象？如何解決？（5分）隊(duì)列的假溢現(xiàn)象是指數(shù)組實(shí)現(xiàn)的順