1線性鏈表不具有的特點(diǎn)是

1、第3題圖1. 線性鏈表不具有的特點(diǎn)是（A.隨機(jī)訪問(wèn)B.不必事先估計(jì)所需存儲(chǔ)空間大小2. C.插入與刪除時(shí)不必移動(dòng)元素D.所需空間與線性表長(zhǎng)度成正比設(shè)一個(gè)棧的輸入序列為1,2,3,4,則輸出序列不可能是（）。4. A.1,2,3,4B.4,3,2,1C.1,3,2,4D.4,1,2,33.下列排序算法中，（）排序在每趟結(jié)束后不一定能選出一個(gè)元素放到其排好序的最終位置上。A.歸并B.冒泡C.選擇D.堆下列序列中，（）是執(zhí)行第一趟快速排序后得到的序列（排序的關(guān)鍵字類(lèi)型是字符串）。A.da,ax,eb,de,bbffha,gcB.cd,eb,ax,daffha,gc,bbC.gc,ax,eb,cd,b

2、bffda,haD.ax,bb,cd,daffeb,gc,ha設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A1010,采用壓縮存儲(chǔ)方式按行將矩陣中下三角部分的元素存入一維數(shù)組B中，A00存入B0中，貝UA85在B中（）位置。A.32B.33C.416.下面哪一種圖的鄰接矩陣肯定是對(duì)稱(chēng)矩陣()。A.有A圖B.無(wú)向圖C.AOV網(wǎng)7. 具有2008個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為（）。8. A.9B.10C.11D.12關(guān)鍵路徑是邊表示活動(dòng)的網(wǎng)（AOE網(wǎng)）中的（）。A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑9. C.最長(zhǎng)的回路D.最短的回路一個(gè)廣義表為（a,（a,b）,d,e,（i,j）,k），則該廣義表的長(zhǎng)度為

3、（）。10. A.不確定B.8C.5D.6設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0n-1,其頭尾指針?lè)謩e為f和r,則其元素個(gè)數(shù)為（）。A.r-fB.r-f+1C.（r-f）modn+1D.（r-f+n）modn1.算法具有的五個(gè)重要特性是：有窮性，確定性，,輸入和輸出。2. 一組記錄的關(guān)鍵字為（45,80,55,40,42,85）,則利用堆排序的方法建立的初始堆為對(duì)如下無(wú)向圖G,從結(jié)點(diǎn)V1出發(fā)，寫(xiě)出一個(gè)按深度優(yōu)先遍歷圖的結(jié)點(diǎn)序列:3. 寫(xiě)出右上圖中的一個(gè)拓?fù)溆行蛐蛄小?. 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度分別為。6.平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是。7.假定對(duì)線性表R1.60進(jìn)

4、行分塊查找，共分為10塊，每塊長(zhǎng)度等于6。若假定查找索引表和塊均用順序查找的方法，則查找每一個(gè)元素的平均查找長(zhǎng)度為。8.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為37的雙親結(jié)點(diǎn)編號(hào)為。9. 設(shè)有一個(gè)字符串s='science',其非空子串的數(shù)目是有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有條弧。一棵二叉樹(shù)的先序序列和中序序列分別如下，先序序列:ABCDEFGHIJ中序序列：CBDEAGIHJF（1）畫(huà)出該二叉樹(shù)。（3分）1. （2）寫(xiě)出其后序序列。（3分）給出用Kruskal算法構(gòu)造下列帶權(quán)圖的最小生成樹(shù)的過(guò)程。2. 已知

5、一個(gè)長(zhǎng)度為12的表（6,8,4,12,2,10,7,3,9,1,11,5）。（1）將表中的元素依次插入到一個(gè)初始為空的二叉排序樹(shù)中，畫(huà)出該二叉排序樹(shù)并求其在等概率下的平均查找長(zhǎng)度。（3分）（2）若先對(duì)表中的記錄排序，構(gòu)成有序表后再對(duì)其進(jìn)行折半查找，畫(huà)出判定樹(shù)并求其在等概率下的平均查找長(zhǎng)度。（3分）已知哈希表地址空間為0.10,哈希函數(shù)為H（key）=keyMOD11,采用鏈地址法處理沖突,將下面數(shù)據(jù)序列依次插入該哈希表中，并求出在等概率下查找成功時(shí)的平均查找長(zhǎng)度。12,24,1,34,38,44,27,22。假定用于通信的電文僅由8個(gè)字母a,b,c,d,e,d,f,g,h組成，各個(gè)字母在電文中

6、出現(xiàn)的頻率分別為5,23,3,6,10,11,36,4。要求:（1）以這些頻率作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造Huffman樹(shù)。（2分）9. 在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為（2）試為這8個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼。（2分）Abcdefgh（3）計(jì)算出電文總長(zhǎng)度。（2分）1. 有兩個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，鏈表頭指針?lè)謩e為a和b。編寫(xiě)一個(gè)過(guò)程將鏈表b鏈到鏈表a之后，鏈接后的鏈表仍保持循環(huán)鏈表形式。2. 試編寫(xiě)一個(gè)計(jì)算二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)的算法。要求二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3. 請(qǐng)寫(xiě)出監(jiān)視哨設(shè)在高下標(biāo)端的插入排序算法。0621.具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為()A.log

7、2nC.log2n+1B.log2nD.log2n+12.一個(gè)棧的進(jìn)棧序列是a,A.abcdeC.decbab,c,d,e,貝U棧的不可能的輸出序列是B.edcbaD.dceab()3. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同且連續(xù)，稱(chēng)之為（）A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4. 對(duì)二叉排序樹(shù)的左子樹(shù)中所有結(jié)點(diǎn)與右子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字大小關(guān)系是（）A.小于B.大于C.等于D.不小于5. 按照二叉樹(shù)的定義，具有3個(gè)節(jié)點(diǎn)的二叉樹(shù)種（）A.2B.3C.4D.56. 廣義表（a）的表尾是（）A.aB.（a）C.（）D.（a）7. 設(shè)有兩個(gè)串p和q,求在q在p中首次

8、出現(xiàn)的位置的運(yùn)算稱(chēng)為（）A.模式匹配B.連接C.求子串D.求串長(zhǎng)8. 弓I入二叉線索樹(shù)的目的是（）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹(shù)的遍歷結(jié)果唯一A.不確定B.2n-1C.2nD.2n+1與單鏈表相比，雙向鏈表的優(yōu)點(diǎn)之一是A.插入、刪除更簡(jiǎn)單B.可以進(jìn)行隨機(jī)訪問(wèn)C.可以省略表頭指針或表尾指針D.訪問(wèn)前后相鄰結(jié)點(diǎn)更方便1. Prim算法適合求的網(wǎng)的最小生成樹(shù)，而Kruskal算法適用于求的網(wǎng)的最小生成樹(shù)。2.循環(huán)單鏈表L為空的條件是。3.在對(duì)隊(duì)列中，新插入的元素只能插入到。4.平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是。5.

9、一個(gè)有序表1,3,9,12,32,41,45,62,75,77,82,95,99,當(dāng)采用折半查找法查找關(guān)鍵字為82的元素時(shí)，次比較后查找成功。3. 設(shè)二維數(shù)組A610,每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放數(shù)組元素，A00的存儲(chǔ)地址是860,則A35的存儲(chǔ)地址是。4. 可以進(jìn)行拓?fù)渑判虻?定是。8.求單鏈表長(zhǎng)度算法的時(shí)間復(fù)雜度是。9. 在直接插入排序、希爾排序、直接選擇排序、快速排序、堆排序和歸并排序中，平均比較次數(shù)最少的排序方法是。1. 已知一個(gè)二叉樹(shù)的中序遍歷序列為DGBAECF,后序遍歷序列為GDBEFCA,請(qǐng)給出：（3）畫(huà)出該二叉樹(shù)。（3分）（4）寫(xiě)出其后序序列。（3分）.對(duì)關(guān)

10、鍵字序列11,78,10,1,3,2,4,21構(gòu)造哈希表，取散列地址為HT0.10,散列函數(shù)為H（K）=K%11,試用線性探查法沖突，畫(huà)出相應(yīng)的哈希表，并分別求查找成功和不成功時(shí)的平均查找長(zhǎng)度。3. 已知關(guān)鍵字序列503,87,512,61,908,170,897,275,653,462,采用快速排序算法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。4. 從一棵空樹(shù)開(kāi)始，逐個(gè)讀入并插入下列關(guān)鍵字：40,28,6,72,100,3,54,1,80,91,38請(qǐng)首先建立二叉排序樹(shù)，然后刪除節(jié)點(diǎn)72,并給出刪除節(jié)點(diǎn)72后的二叉樹(shù)。5. 給定權(quán)集W=2,3,4,7,8,9,試構(gòu)造關(guān)于W的一棵哈夫曼樹(shù)，并求帶權(quán)路

11、徑長(zhǎng)度WPL。(1分)1. 有一個(gè)有序單鏈表（從小到大排序），表頭指針為L(zhǎng),設(shè)計(jì)一個(gè)算法向該單鏈表中插入一個(gè)元素為x的結(jié)點(diǎn)，并使插入后鏈表仍然有序。2. 二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，試編寫(xiě)算法求二叉樹(shù)的深度。3.二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)按層次順序（同層自左向右）遍歷二叉樹(shù)的算法。1253（1分）3.（1）二叉排序樹(shù)為:答案、選擇題（每小題2分，共20分）1.A2.D3.A4.A5.C6.B7.C8.A9.C10.D911等概率下平均查找長(zhǎng)度ASL=(1+2*2+3*4+4*3+5*2)/12=13/4=3.25(2)排序后進(jìn)行折半查找的判定樹(shù)為：639-1'、.4-7112581

12、012等概率下平均查找長(zhǎng)度ASL=(1+2*2+3*4+4*5)/12=37/123.08第1頁(yè)(共3頁(yè))（2分）（1分）(2分)(1分)二、填空題(每小題2分，共20分)1.可行性2.(85,80,55,40,42,45)4.1,2,3,5,6,4(答案不惟一)63.V1,V2,V3,V5,V4,V6,V7,V8(答案不惟一)5.0(1)和0(n)6.T,0,110.n4.哈希函數(shù)值為：（1分）H（12）=1H（24）=2H（1）=1H(34)=1H(38)=5H(44)=0H(27)=5H(22)=0、解答下列各題（每小題6分，共30分）后序序列：CEDBIJHGFA（

13、3分）（2分）（1分）5.(1)Huffman樹(shù)為：(2分)(2分)V6abcdEfgH3456（2）其huffman編碼為（2分）注：此題答案不唯一，只要滿(mǎn)足哈夫曼編碼的要求都可。1001(3) 電文總碼數(shù)為4*5+2*23+4*3+4*6+3*10+3*11+2*36+4*4=253(2分)四、算法設(shè)計(jì)(每小題10分，共30分)說(shuō)明：每小題中：1. 思路正確3分2. 算法正確5分3. 算法完整2分typedefstructLNode(ElemTypedata;structLNode*next;LNode,*LinkList;voidConnect(LinkLista,LinkListb)(

14、將循環(huán)鏈表b鏈在循環(huán)鏈表a之后的算法，鏈表a和b均不帶頭結(jié)點(diǎn)LinkListp;p=a;先令指針p指向鏈表a的第一個(gè)結(jié)點(diǎn)while(p->next<>a)p=p->next;找到鏈表a的最后一個(gè)結(jié)點(diǎn)p->next=b;將鏈表b鏈到a的最后一個(gè)結(jié)點(diǎn)之后第2頁(yè)(共3頁(yè))p=b;令指針p指向鏈表b的第一個(gè)結(jié)點(diǎn)while(p->next<>b)p=p->next;找到鏈表b的最后一個(gè)結(jié)點(diǎn)p->next=a;令鏈表b的最后一個(gè)結(jié)點(diǎn)指向合并后的鏈表的表頭TypedefstructBiTNode(TelemTypedata;StructBiTNod

15、e*lchild,*rchild;BiTNode,*BiTree;voidleaf(BiTreeT)(采用二叉鏈表存貯二叉樹(shù)，n為全局變量，用于累加二叉樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)。本算法在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)第一次被調(diào)用時(shí)，n=0if(T)(若二叉樹(shù)為空，結(jié)束返回/若二叉樹(shù)不為空，在先序遍歷二叉樹(shù)的過(guò)程中，統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)if(T->lchild=null&&T->rchild=null)n=n+1;leaf(T->lchild);leaf(T->rchild);/if/leaftypedefstruct(KeyTypekey;InfoT

16、ypeotherinfo;RedType;typedefstruct(RedTyperMAXSIZE+1;intlength;SqList;voidInsert_Sort1(SqList&L)/監(jiān)視哨設(shè)在高下標(biāo)端的插入排序算法(k=L.length;for(i=k-1;i;-i)/從后向前逐個(gè)插入排序if(L.ri.key>L.ri+1.key)(L.rk+1.key=L.ri.key;/監(jiān)視哨for(j=i+1;L.rk+1.key>L.rj.key;+j)L.rj-1=L.r田;/前移L.rj-1=L.rk+1;/插入/Insert_Sort1B一、選擇題(每小題1分，

17、共10分)1-5CDCBD6-10CAADD二、填空題(每空2分，共20分)邊稠密，邊稀疏L->next=L;隊(duì)尾-1,0,141000無(wú)環(huán)圖O(n)快速排序三、解答題(每小題6分，共30分)1.(1)二叉樹(shù)是：28384054721008091(4分)(4分)刪除72后:（2）后序序列為：GDBEFCA(2分)40282.解：首先求出散列地址，據(jù)此得到哈希表見(jiàn)下圖。546381001178132421100123456789108091(2分)查找成功的平均比較次數(shù)為：ASL=(1+1+2+1+3+2+8+1)/8=2.375查找不成功的平均查找長(zhǎng)度為：ASLunsucc=(8+7+6

18、+5+4+3+2+1+1+1+9)/114.2735.構(gòu)造的哈夫曼樹(shù)為:3318153.每趟快速排序的結(jié)果如下:4628727561170503897908653512170872756146261871702756187(4分)加權(quán)路徑長(zhǎng)度WPL=80（2分）四、算法設(shè)計(jì)題（每小題10分，共30分）512653897908653排序后：61871702754625035126538979084.二叉排序樹(shù):5121.voidListInsert(Linklist&L,intx)Linklist*p,*q;q=L;p=q->next;while(p&x>p->data)q=p;p=p->next;s=(Linklist)malloc(sizeof(LNode);s->data=x;s->next=p;q->next=s;2.intBtDepth(BitreeT)(intlchilddep,rchilddep;if(T)return(0);else(lchilddep=