數(shù)據(jù)結(jié)構(gòu)與算法試卷A答案

《數(shù)據(jù)結(jié)構(gòu)與算法》期末試卷本卷共3頁第4頁專業(yè)：專業(yè)：年級/班級：姓名：學(xué)號(hào)：裝訂線內(nèi)不要答題地理信息系統(tǒng)、測繪工程、地理科學(xué)專業(yè)（本）11級《數(shù)據(jù)結(jié)構(gòu)與算法》A卷（時(shí)間120分鐘）題號(hào)一二三四五六七八總分分值3010103020100得分選擇題（每題1.5分，共30分）1、下面哪一個(gè)不是線性表的特性（D）A.除第一個(gè)元素外，每個(gè)元素都有前驅(qū)B.除最后一個(gè)元素外，每個(gè)元素都有后繼C.線性表是數(shù)據(jù)的有限序列D.線性表的長度為n，并且n不等于02、在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行（C）A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;3、若線性表采用鏈?zhǔn)酱鎯?chǔ)，則表中各元素的存儲(chǔ)地址（D）A.必須是連續(xù)的B.部分地址是連續(xù)的C.一定是不連續(xù)的D.不一定是連續(xù)的4、串是（D）A.一些符號(hào)構(gòu)成的序列B.一些字母構(gòu)成的序列C.一個(gè)以上字符構(gòu)成的序列D.任意有限個(gè)字符構(gòu)成的序列5、設(shè)輸入的序列為1、2、3、4，則借助于一個(gè)棧可以得到的輸出序列是（A）A.1342B.3142C.4312D.41236、棧和隊(duì)列都是（C）A.順序存儲(chǔ)的線性表B.鏈?zhǔn)酱鎯?chǔ)的線性表C.限制插入和刪除位置的線性表D.限制插入和刪除的非線性表7、將8階對稱矩陣A的下三角部分逐行存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占4個(gè)字節(jié)，下標(biāo)下界都為0，則A[7][4]的地址為（D）A.35B.36C.3400D.11288、有100個(gè)結(jié)點(diǎn)的完全二叉樹，由根開始從上到下，從左到右對結(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)為1，則編號(hào)43的結(jié)點(diǎn)的左孩子的編號(hào)是（D）A.50B.48C.98D.869、對一顆n個(gè)結(jié)點(diǎn)的樹，則該樹中結(jié)點(diǎn)的度之和為（B）A.nB.n-1C.n+1D.不確定10、霍夫曼樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為（A）A.0B.1C.2D.不確定11、具有n個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為（D）A.nB.n-1C.n+1D.n（n-1）/212、有n個(gè)頂點(diǎn)的連通圖的最小生成樹有（A）條邊A.n-1B.nC.n+1D.不確定13、以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，其深度優(yōu)先遍歷和廣度優(yōu)先遍歷的時(shí)間復(fù)雜度都為（D）A.O(e)B.O(n)C.O(n-e)D.O(n+e)14、下列排序算法中，第一趟排序結(jié)束后，其最大或最小元素一定在其最終位置上的算法是（D）A.歸并排序B.直接插入排序C.快速排序D.起泡排序15、快速排序的平均時(shí)間復(fù)雜度為（C）A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)16、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其內(nèi)（C）數(shù)據(jù)項(xiàng)。A、只能包括一個(gè)B、不包含C、可以包含多個(gè)D、必須包含多個(gè)17、算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為（A）A、正確性B、易讀性C、健壯D、高效率18、棧是限定在（C）處進(jìn)行插入或刪除操作的線性表。A、端點(diǎn)B、棧底C、棧頂D、中間19、隊(duì)列是限定在（C）進(jìn)行插入操作的線性表。A、端點(diǎn)B、隊(duì)頭C、隊(duì)尾D、中間20、隊(duì)列的特點(diǎn)是（A）A、先進(jìn)先出B、后進(jìn)先出C、先進(jìn)后出D、不進(jìn)不出二、判讀正誤題（每題1分，共10分）（√）1、O(1)+O(1)=O(1)（√）2、順序表可以對存儲(chǔ)其中的數(shù)據(jù)進(jìn)行排序操作，鏈表也能進(jìn)行排序操作（×）3、因?yàn)闂Ｊ且环N線性表，所以線性表的所有操作都適用于棧（√）4、隊(duì)列的“假溢出”現(xiàn)象是可以解決的（×）5、兩個(gè)稀疏矩陣的和仍為稀疏矩陣（√）6、滿二叉樹是完全二叉樹（×）7、后序遍歷一個(gè)二叉樹等于中序遍歷其對應(yīng)的樹（×）8、霍夫曼樹是完全二叉樹（√）9、有n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有n個(gè)非零元素（×）10、對n個(gè)記錄進(jìn)行直接插入排序，其平均時(shí)間復(fù)雜度為O（nlog2n）三、算法閱讀填空題（每題5分，共10分）1、寫出算法劃線語句的執(zhí)行次數(shù)和x的結(jié)果x=0;for(i=0;i<10;i++){for(j=0;j<=i;j++)x=x+1;}執(zhí)行次數(shù)55次x的結(jié)果552、循環(huán)隊(duì)列入隊(duì)intenqueue(cqueue*cq,ElemTypex){if((cq->rear+1)%MAXCSIZE==cq->front)return0;cq->base[cq->rear]=x;cq->rear=(cq->rear+1)%MAXSIZE;return1;}四、計(jì)算操作題（每題10分，共30分）1、給定如圖1所示的帶圈無向圖G1.畫出該圖的鄰接表存儲(chǔ)結(jié)構(gòu)；畫出該圖的鄰接矩陣；給出prim算法構(gòu)造最小生成樹過程圖1答：圖的鄰接表為：不帶權(quán)值扣2分。圖的鄰接矩陣表示為：不帶權(quán)值或權(quán)值都為1扣2分。Prim算法構(gòu)造過程：結(jié)點(diǎn)1為初始點(diǎn)。2、已知一顆二叉樹的中序遍歷序列和后序遍歷序列分別為：中序：CBEDAFIGH，后序：CEDBIFHGA。試畫出這顆二叉樹，并寫出其先序遍歷序列。答：此樹為：此樹的先序遍歷序列為：ABCDEGFIH3、設(shè)權(quán)值集合W={10、4、8、13、5、18}，以W為基礎(chǔ)，建立一顆霍夫曼樹，并求出其WPL的值。答：此樹的建立過程如下圖所示：W={10,4,8,13,5,18}12346WPL=18*2+8*3+(4+5)*4+(10+13)*2=142五、算法設(shè)計(jì)題（每題10分，共20分）1、編寫算法，刪除單鏈表L中p指針指向結(jié)點(diǎn)的直接前驅(qū)。typedefintElemType;typedefstructNode{

ElemTypedata;

structNode*next;}LinkList//一級指針也可以。但p必須是指針變量，非指針扣1分。voidDelPreNode(LinkList*L,LinkList*p);voidDelPreNode(LinkList**L,LinkList*p)

{

LinkList**q=L;

while(q&&*q){

if((*q)->next==p){

*q=p->next;

free(p);

}(*q)=(*q)->next;

}

}2、設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)在順序表上的起泡排序。參考答案：#defineMAXSIZE20//排序表的最大容量enumBOOL{False,True};//可以是int表示typedefstruct//定義排序表的結(jié)構(gòu){intelemword[MAXSIZE];//數(shù)據(jù)元素關(guān)鍵字intcount;//表中當(dāng)前元素的個(gè)數(shù)}SeqList;voidBubbleSort(SeqList&L){//對順序表L做起泡排序。inti,j,t;BOO