數(shù)據(jù)結(jié)構(gòu)期末考試模擬試題

1、、填空題（每空1分，共20分）1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D是的有限集合，R是D上的有限集合。2、一個(gè)算法的效率可用、來衡量。3、向一個(gè)長度為n的向量的第i個(gè)元素（1<i<n+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)4、具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)是個(gè)。5、一般情況下，快速排序的時(shí)間復(fù)雜度是。6、向棧中壓入元素的操作是先，后。7、稱為空串；稱為空白串。&采用三元組表存儲(chǔ)稀疏矩陣，三元是指。9、具有10個(gè)結(jié)點(diǎn)的完全二叉樹，其深度是o10、線性有序表（ai,a2,a3,，a?。）是從小到大排列的，對(duì)一個(gè)給定的值k,用二分法檢索表中與k相等的元素，在查找不成功

2、的情況下，最多需要檢索次。11、散列法（哈希）存儲(chǔ)的基本思想是由決定數(shù)據(jù)的存儲(chǔ)地址。12、具有n個(gè)頂點(diǎn)的無向圖，最多有條邊；如果該圖是一個(gè)連通圖，那它最少有條邊；其生成樹有條邊。13、每個(gè)結(jié)點(diǎn)的平衡因子的二叉排序樹稱為平衡二叉樹，中序遍歷該樹可得到o14、二、判斷題（正確的畫，錯(cuò)誤的畫X;每題1分，共10分）1、隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。2、根據(jù)二叉樹的先序和中序遍歷結(jié)果，可唯一確定該二叉樹。3、棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。4、二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。5、一個(gè)有向無環(huán)圖進(jìn)行拓?fù)渑判?，結(jié)果可

3、能不唯一。6、鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。試卷B共七頁第5頁7、用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針域中有n+1個(gè)為空指針。&具有2個(gè)結(jié)點(diǎn)的二叉樹有2種形態(tài)。9、線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也一定不相鄰。10、順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。三、單項(xiàng)選擇題（每小題2分，共30分）1、算法分析的目的是oA、分析算法的易讀性B、研究算法中輸入和輸出的關(guān)系C、 分析算法的效率，以求改進(jìn)D、 找出合理的數(shù)據(jù)結(jié)構(gòu)2、對(duì)圖進(jìn)行深度優(yōu)先搜索時(shí)，使用的輔助存儲(chǔ)結(jié)構(gòu)是oA、棧B、

4、隊(duì)列C、鏈表D、數(shù)組3、在一個(gè)單鏈表中，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行A、 s->link=p;p->next=s;B、 s->link=p->link;p->link=s;Cs->link=p->link;p=s;D、p->link=s;s->link=p;curre nt為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測4、在循環(huán)鏈表中，first為指向鏈表表頭的指針,current是否達(dá)到鏈表表尾的語句是A、current->1ink=NULL、first->link=currentC、first=current、current->1

5、ink=first5、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址A、必須是連續(xù)的、部分地址是連續(xù)的C、定是不連續(xù)的、連續(xù)與否均可以6、比較次數(shù)與序列的原始狀態(tài)（原始排列）無關(guān)的排序方法是排序方法。7、A、插入B、選擇C、冒泡D、快速如果結(jié)點(diǎn)a有3個(gè)兄弟，而且b為a的雙親，貝Ub的度為A、3B、4D、2&進(jìn)棧序列為（A,B,C），不可能的出棧序列是A、(A, B, C) B、(C, B, A)C、(A, C, B)D、(C, A, B)9、不穩(wěn)定的排序方法是A選擇排序C、快速排序、直接插入排序、基數(shù)排序10、設(shè)單鏈表中指針 P指著結(jié)點(diǎn)a,若要?jiǎng)h除a之后的結(jié)點(diǎn)（若存在） ，則需要修改指針的操作A、p-&

6、gt;next=p->next->nextB、 p=p->nextC、 p= p->next->nextD、 p_>next=p11、對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行次比 較。A、 10B、 14C、 15D、2512、具有n個(gè)頂點(diǎn)的完全無向圖,條 邊。A、n(n-l)n(n +1)C、n(nT)/2n(n+l)/213、采用分塊查找方法進(jìn)行查找,既要有利于數(shù)據(jù)文件的動(dòng)態(tài)變化，又要具有良好的查找效率,數(shù)據(jù)文件應(yīng)選擇A、塊內(nèi)、塊間順序存儲(chǔ)結(jié)構(gòu)C、塊內(nèi)順序、塊間鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、塊內(nèi)、塊間鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、塊內(nèi)鏈?zhǔn)?、塊間順序存儲(chǔ)結(jié)構(gòu)14、已知A=(

7、a,b),那么GetHead(GetHead(GetTai1(B)=B=(A,A),15、一個(gè)D、(A)n*n的對(duì)稱矩陣，若以行為主序壓縮存入一維數(shù)組，數(shù)組的容量為、(n+1 ) *( n+1 ) /2A、n*nBn*n/2C、n*（n+1）/2四、解答題（共30分）1、已知如圖所示的帶權(quán)圖求每個(gè)頂點(diǎn)的度（本小題2分）畫出該圖對(duì)應(yīng)的鄰接矩陣（本小4分）題求該圖的最小生成樹（本小題4分）2、根據(jù)查找表（19,14,23,01,68,20,84,27構(gòu)造一棵二叉排序樹（本小題4分）計(jì)算查找成功時(shí)的平均查找長度（本小3分）題中序遍歷所得的二叉樹（本小題4分）試卷B共七頁將該樹轉(zhuǎn)換成對(duì)應(yīng)的森林（本小題

8、4分）3、對(duì)集合（19,14,23,01,68,20,84,27）,以19為樞軸元素，畫出一趟快速排序的過程試卷B共七頁第9頁(本小題5分)五、算法設(shè)計(jì)題(共10分)1、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表上刪除第i個(gè)結(jié)點(diǎn)(本小題6分)。statusDel_LinkList(LinkList&L,inti,ElemType&e)(P二L;2、將折半查找算法補(bǔ)充完整(本小題4分)。intSearch_Half(SSTablest,KeyTypekey)low=l;high=st.Length;while()mid二；if(st.elemmid.key=key)returnmid;elseif(

9、st.elemmid.key<key)；else；return0;)參考答案一、填空題（每空1分，共20分）1、數(shù)據(jù)兀素，關(guān)系2、時(shí)間復(fù)雜度，空間復(fù)雜度3、ni+l4、 2n-l5、 nlogn6、將元素置于棧頂，棧頂指針加17、不包含任何字符的字符串，僅由空格字符組成的字符串&元素的行號(hào)、列號(hào)、值9、410、511、哈希函數(shù)12、n(n-l)/2,n-l,n-l1、(2分)15#5 # 3 #0 3 4 43 0 # 24 # 0 54 2 5 0TD(v4)=3TD(v5)=3 TD (v6) =313、絕對(duì)值不超過1,非遞減排列的有序序列二、判斷題（每題1分，共10分）2、3、5、7正確，其余的錯(cuò)。三、單選（每題2分，共30分）CABDDBBDCABCDCC四、解答題(30分)(4分)0220155#3#(427TD(vl)=3TD(v2)=3TD(v3)=5(4分)ASL=(l+2*2+3*3+4*2)/8二11/4(3分)01,14,19,20,23,27,68,844分)試卷B共七頁第12頁19T1141m23206884T1273、（5分）五、算法設(shè)計(jì)題（6+4分）1、j=0；while(p->next&&j<l-l)p=p-&