數(shù)據(jù)結構試題及答案[教育試題]

1、數(shù)據(jù)結構試題（）參考答案 班別學號姓名成績一、單項選擇（每小題2分，共24分） 1.若某線性表的常用操作是取第i個元素及其前趨元素，則采用( A )存儲方式最節(jié)省時間A.順序表B.單鏈表C.雙鏈表D.單向循環(huán)2.串是任意有限個( B )A.符號構成的序列B.字符構成的序列 C.符號構成的集合D.字符構成的集合3.設矩陣A(aij,1=i,j=10)的元素滿足: aij0(i=j,1=i,j=10),aij =0 (ij,1=i,j=10) 若將A的所有非0元素以行為主序存于首地址為2000的存儲區(qū)域中，每個元素占4個單元,則元素A59的首地址為( C )A.2340B.2336C.2220D.

2、21604.如果以鏈表作為棧的存儲結構,則退棧操作時( D ) A.必須判別棧是否滿干 B.對棧不作任何判別 C.判別棧元素的類型 D.必須判別棧是否空5.設數(shù)組Data0.m作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為( A )A.front=(front+1)%(m+1) B.front=(front+1)% mC.rear=(rear+1)% mD. front=front+16.深度為6(根的層次為1)的二叉樹至多有( B )結點A.64B.63C.31D.32 7.將含100個結點的完全二叉樹從根這一層開始，每層從左至右依次對結點編號，

3、根結點的編號為1。編號為47的結點X的雙親的編號為( C )A.24B.25C.23D.2無法確定8.設有一個無向圖G=(V,E)和G=(V,E)，如果G為G的生成樹，則下面不正確的說法是( D )A.G為G的子圖 B.G為G的一個無環(huán)子圖C.G為G的極小連通子圖且V=V D.G為G的連通分量9.用線性探測法查找閉散列上，可能要探測多個散列地址，這些位置上的鍵值( D )A.一定都是同義詞B.一定都不是同義詞C.都相同D.不一定都是同義詞 10.二分查找要求被查找的表是( C )A.鍵值有序的鏈接表B.鏈接表但鍵值不一定有序表C.鍵值有序的順序表D.順序表但鍵值不一定有序表 11.當初始序列已

4、經按鍵值有序，用直接插入法對其進行排序，需要比較的次數(shù)為( B )A. n2B. n-1C. log2nD. nlog2n12.堆是一個鍵值序列K1,K2,.,Ki,.,Kn,對i=1,2,., n/2 ，滿足(A)A. Ki=K2i且Ki=K2i+1(2i+1=n)B.KiK2iK2i+1C. Ki=K2i或Ki=K2i+1(2i+1=n) D.Ki=K2i=K2i+1二、判斷題(正確的在括號內打V,錯的在括號內打X,每小題1分，共10分) 1.雙鏈表中至多只有一個結點的后繼指針為空( V )2.在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條

5、件是front=rear( X )3.對線性表進行插入和刪除操作時，不必移動結點。( X )4.隊可以作為對樹的層次遍歷的一種數(shù)據(jù)結構。( V )5.在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧。( X )6.對有向圖G，如果從任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。( X )7.二分查找法必需在有序表上進行。( V )8.向二叉排序樹中插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。( V )9.鍵值序列A,C,D,B,E,E,F是一個堆。( X )10.在二路歸并時，被歸并的兩個子序列中的關鍵字個數(shù)不一定相等。( V )

6、三、填空題(每空2分，共24分)1.設r指向單鏈表最后一個結點，要在最后一個結點之后插入s所指的結點，需執(zhí)行的三條語句是r-next=s ; r=s; r-next=NULL 。2.在帶頭結點單鏈表L中，表空的條件是 L-next=NULL 3.設一個鏈棧的棧頂指針為ls，棧中結點格式為 infolink ，棧空的條件是ls=NULL。若棧不空，則退棧操作為p=ls；ls=ls-link；free(p). 4.已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有12個葉子結點。5.樹有三種常用的存儲結構，即孩子鏈表法，孩子兄弟鏈表法和雙親表示法。6.n-1個頂點

7、的連通圖的生成樹有n-2條邊。7.一個有向圖G中若有弧、和，則在圖G的拓樸序列中，頂點Vi,Vj和Vk的相對位置為Vj-Vi-Vk。8.設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行排序(按遞增順序)，冒泡排序最省時間，快速排序最費時間。9.下面是將鍵值為X的結點插入到二叉排序樹中的算法，請在劃線處填上適當?shù)膬热?。typedefstruct node *pnodestruct node int key; pnode left,right;void searchinsert(int x; pnode t);/t為二叉排序樹根結點的指針/ if(t=NU

8、LL ) p=malloc(size); p-key=x; p-left=nil; p-right=nil; t=p;elseif (xkey)searchinsert(x,t-left) else searchinsert(x,t- right);四、應用題(本題共28分)1.給定權值5,10,12,15,30,40,構造相應的哈夫曼樹，要求寫出構造步驟。(4分)哈夫曼樹構造步驟:2.已知一表為(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),按表中順序依次插入初始為空的二叉排序樹，要求：(1)在右邊畫出建立的二叉排序樹。(4分)(2)求出在

9、等概率情況下查找成功的平均查找長度。(2分) ASLSU =(1+2*2+3*3+4*3+5*2+6)/12=42/12=3.53.下圖表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結城市間的公路，邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案.(4分) 4.已知一個無向圖的鄰接表為:(本題4分,每小題2分) (1)畫出這個圖。(2)以V1為出發(fā)點，對圖進行廣度優(yōu)先搜索，寫出所有可能的訪問序列。 V1-V2-V4-V5-V3 V1-V4-V2-V3-V55.設n個元素的有序表為R,K為一個給定的值，二分查找算法如下：int binsearch(sqlist R; keytype K:);l=1; h=n; suc=false;while (l=h)&(!suc) do mid=(l+h)/2;caseK=Rmid.key: suc=true;KRmid.key: l=mid+1end if (suc) return(mid) else return(0)將上述算法中劃線語句改為：Klchild, k,p ) ; pre(t-rchild, k,p ) ; 2.某單鏈表L的結點結構為 datanext ，結點個數(shù)至少3個，試畫出該鏈表的結構圖，并編寫算法判斷該鏈表的元素是否成等差關系，即:設各元素值依次為a1,a2,.,an,