PAGE第1頁共10頁P(yáng)AGE1山西財(cái)經(jīng)大學(xué)2008—2009學(xué)年第2學(xué)期期末算法與數(shù)據(jù)結(jié)構(gòu)課程試卷（A卷）題號一二三四五總分分?jǐn)?shù)評卷人復(fù)核人1、本卷考試形式為閉卷，考試時(shí)間為兩小時(shí)。2、考生不得將裝訂成冊的試卷拆散，不得將試卷或答題卡帶出考場。3、考生只允許在密封線以外答題，答在密封線以內(nèi)的將不予評分。4、考生答題時(shí)一律使用藍(lán)色、黑色鋼筆或圓珠筆（制圖、制表等除外）。5、考生禁止攜帶手機(jī)、耳麥等通訊器材。否則，視為作弊。一、單項(xiàng)選擇題（共10小題，每題1分，共計(jì)10分）二、判斷題（共10小題，每題1分，共計(jì)10分）三、簡答題（共4小題，每題5分，共計(jì)20分）四、應(yīng)用題（共8小題，1-6小題必做，7、8任選一，1-2每小題5分，3-8每小題6分，共計(jì)40分）五、算法設(shè)計(jì)題（1、2小題任選一，3、4小題任選一，每題10分，共計(jì)20分）

本題得分單項(xiàng)選擇題（共10小題，每題1分，共計(jì)10本題得分答題要求：（請將正確的選項(xiàng)填在題后的括號中）1．若某線性表最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則下列的存儲方式中最節(jié)省時(shí)間的是()。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙向鏈表D．僅有尾指針的單循環(huán)鏈表2.下面給出的算法段是要把一個p所指新結(jié)點(diǎn)，插入到非空雙向鏈表中，作為該雙鏈中q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，能正確完成要求的算法段是（）。A．p->llink=q->llink;B．q->llink=p;p->rlink=q;p->rlink=q;q->llink->rlink=p;q->llink->rlink=p;q->llink=p;p->llink=q->llink;C．p->rlink=q;D．p->rlink=q;p->llink=q->llink;p->llink=q->llink;q->llink=p;q->rlink=p;q->llink->rlink=p;q->llink->rlink=p;3．下列選項(xiàng)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A．棧B.隊(duì)列C.完全二叉樹D.堆4．判定一個循環(huán)隊(duì)列Q(最多元素為m0)為滿隊(duì)列的條件是()。A．Q.front!=Q.rearB．Q.front==Q.rearC．Q.front!=(Q.rear+1)%m0D．Q.front==(Q.rear+1)%m05．串的長度是()。A．串中不同字母的個數(shù)B．串中不同字符的個數(shù)C．串中所含字符的個數(shù)，且大于0D．串中所含字符的個數(shù)6．?dāng)?shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時(shí)，元素A[7][5]6．刪除二叉排序樹中的一個結(jié)點(diǎn)，再重新插入進(jìn)去，一定能得到原來的二叉排序樹。()7．采用散列法存儲，負(fù)載因子越大，發(fā)生碰撞的可能性也越大。()8．若一棵樹中某結(jié)點(diǎn)的度為1，則該結(jié)點(diǎn)僅有一棵子樹。()9．如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。()10．對任意一個圖，從它的某個頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點(diǎn)。()本題得分三、簡答題（共4小題，每題5分，共計(jì)20本題得分答題要求：（第2、3題請寫出中間過程，只寫結(jié)果不得分）1.請簡述棧和隊(duì)列的相同和不同之處。2.已知完全二叉樹的第8層有10個結(jié)點(diǎn)，則整個二叉樹的結(jié)點(diǎn)數(shù)最多為？3.什么是二叉排序樹？如何在二叉排序樹上實(shí)施查找操作？4.直接插入排序和快速排序兩種算法的穩(wěn)定性如何?請寫出原因。本題得分應(yīng)用題（1-6小題必做，7、8任選一，1-2每小題5分，3-8每小題6分，共計(jì)40本題得分答題要求：（請盡量寫出中間過程）1.設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1，n(n-1)/2]中，對上三角部分的任一元素ai,j(i<j)，求它在一組數(shù)組B中的下標(biāo)位置k的值？bacfdehbacfdehg(1)請畫出它的順序存儲表示(2)寫出它的中序遍歷序列(3)畫出它的后序線索二叉樹。3.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdcefgh，中序遍歷的結(jié)點(diǎn)訪問順序是cbdagfeh，請畫出該二叉樹。4.以數(shù)據(jù)集｛3,5,9,14,16,25,33｝為結(jié)點(diǎn)權(quán)值(1)請構(gòu)造的哈夫曼樹。(2)并求出它的帶權(quán)路徑長度。5.哈希表長為11，請給出對序列{7，18，40，35，9，33，28，37，90}進(jìn)行散列，按照哈希函數(shù)H(key)＝keyMOD11，及線性線性探測再散列處理沖突，請給出處理的過程及結(jié)果。6．已知序列{30，8，25，15，78，97，65，43，72}，采用堆排序法對該序列作升序排序。建立的初始堆應(yīng)是大頂堆還是小頂堆？建初始堆時(shí)應(yīng)從哪一個位置開始篩選？請畫出建成的初始堆。7．求出下面AOE網(wǎng)中的關(guān)鍵路徑。要求標(biāo)明每個頂點(diǎn)的最早和最遲發(fā)生時(shí)間，并畫出關(guān)鍵路徑。10104997a1bcdegf6513268．求出下圖的一棵最小生成樹，要求給出過程和所依據(jù)的是哪一種算法。81068106596142538763437512本題得分五、算法設(shè)計(jì)題（本題得分任選一，每題10分，共計(jì)20分）答題要求：（在寫出算法之前先簡要寫出算法思想；在算法中盡可能寫一些注釋信息。不按要求只寫算法不得分。）單鏈表存儲結(jié)構(gòu)如下：typedefstructLnode{Elemtypedata;StructLnode*next;}Lnode,*Linklist;試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除最小值結(jié)點(diǎn)的算法。voiddelete（Linklist&L）請編寫對不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，要求算法用L返回逆置后的鏈表的頭指針。二叉鏈表存儲表示定義如下：typedefstructBiTNode{TelemType