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

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

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

4、隊列C、鏈表D、數(shù)組3、在一個單鏈表中，在p之后插入s所指結(jié)點，則執(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為鏈表當前指針，在循環(huán)鏈表中檢測4、在循環(huán)鏈表中，first為指向鏈表表頭的指針,current是否達到鏈表表尾的語句是A、current->1ink=NULL、first->link=currentC、first=current、current->1

5、ink=first5、線性表采用鏈式存儲時，其地址A、必須是連續(xù)的、部分地址是連續(xù)的C、定是不連續(xù)的、連續(xù)與否均可以6、比較次數(shù)與序列的原始狀態(tài)（原始排列）無關的排序方法是排序方法。7、A、插入B、選擇C、冒泡D、快速如果結(jié)點a有3個兄弟，而且b為a的雙親，貝Ub的度為A、3B、4D、2&進棧序列為（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、設單鏈表中指針 P指著結(jié)點a,若要刪除a之后的結(jié)點（若存在） ，則需要修改指針的操作A、p-&

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

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

8、4分）3、對集合（19,14,23,01,68,20,84,27）,以19為樞軸元素，畫出一趟快速排序的過程試卷B共七頁第9頁(本小題5分)五、算法設計題(共10分)1、在一個帶頭結(jié)點的單鏈表上刪除第i個結(jié)點(本小題6分)。statusDel_LinkList(LinkList&L,inti,ElemType&e)(P二L;2、將折半查找算法補充完整(本小題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ù)兀素，關系2、時間復雜度，空間復雜度3、ni+l4、 2n-l5、 nlogn6、將元素置于棧頂，棧頂指針加17、不包含任何字符的字符串，僅由空格字符組成的字符串&元素的行號、列號、值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、絕對值不超過1,非遞減排列的有序序列二、判斷題（每題1分，共10分）2、3、5、7正確，其余的錯。三、單選（每題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分）五、算法設計題（6+4分）1、j=0；while(p->next&&j<l-l)p=p-&