數(shù)據(jù)結(jié)構(gòu)期末試卷復(fù)習(xí)題錦

一、填空題〔每空1分，共22分〕1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為〔D,R〕，其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。2、一個(gè)算法的效率可分為時(shí)間效率和空間效率。3、向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。4、在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。5、在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6、向棧中壓入元素的操作是先移動(dòng)棧頂指針，后存入元素。7、不包含任何字符〔長(zhǎng)度為0〕的串稱為空串；由一個(gè)或多個(gè)空格〔僅由空格符〕組成的串稱為空白串。8、假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。A的起始存儲(chǔ)位置〔基地址〕為1000，那么數(shù)組A的體積〔存儲(chǔ)量〕為288B；末尾元素A57的第一個(gè)字節(jié)地址為1282；假設(shè)按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為(8+4)×6+1000=1072；假設(shè)按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為(6×7＋4)×6＋1000〕＝1276。9、設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，那么此完全二叉樹(shù)有500個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。10、線性有序表〔a1，a2，a3，…，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索8次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比擬次數(shù)是7。11、散列法存儲(chǔ)的根本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷題〔每題1分，共10分〕〔×〕1.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)?！病痢?.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹(shù)的深度?！病獭?.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式?！病痢?.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，那么不存在非空右子樹(shù)?！病痢?.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，那么它的第i層上最多能有2i－1個(gè)結(jié)點(diǎn)?！病痢?.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算時(shí)機(jī)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)?！病獭?.用二叉鏈表法〔link-rlink〕存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。〔√〕8.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。〔×〕9.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰?！病痢?0.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。三、單項(xiàng)選擇題〔每題2分，共18分〕〔C〕1．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：〔A〕存儲(chǔ)結(jié)構(gòu)〔B〕邏輯結(jié)構(gòu)〔C〕順序存儲(chǔ)結(jié)構(gòu)〔D〕鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)〔B〕2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，那么第5個(gè)元素的地址是〔A〕110〔B〕108〔C〕100〔D〕120〔A〕3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O〔1〕的操作是：訪問(wèn)第i個(gè)結(jié)點(diǎn)〔1≤i≤n〕和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)〔2≤i≤n〕在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)〔1≤i≤n〕刪除第i個(gè)結(jié)點(diǎn)〔1≤i≤n〕將n個(gè)結(jié)點(diǎn)從小到大排序〔B〕4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素〔A〕8〔B〕63.5〔C〕63〔D〕7〔A〕4.判定一個(gè)隊(duì)列QU〔最多元素為m0〕為滿隊(duì)列的條件是_______Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1〔B〕6.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；〔A〕順序〔B〕鏈?zhǔn)健睠〕星式〔D〕網(wǎng)狀〔D〕7.線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:〔A〕必須是連續(xù)的〔B〕局部地址必須是連續(xù)的〔C〕一定是不連續(xù)的〔D〕連續(xù)或不連續(xù)都可以〔B〕8．線性表Ｌ在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)?！玻痢承杞?jīng)常修改Ｌ中的結(jié)點(diǎn)值〔Ｂ〕需不斷對(duì)Ｌ進(jìn)行刪除插入〔Ｃ〕Ｌ中含有大量的結(jié)點(diǎn)〔Ｄ〕Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜〔C〕9.假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)p1=n，那么pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定四、簡(jiǎn)答題〔10分〕1、如下圖的有向圖，請(qǐng)給出該圖的:頂點(diǎn)1234頂點(diǎn)123456入度出度鄰接矩陣；鄰接表；〔4〕逆鄰接表。2、線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，假設(shè)它以鏈接方式存儲(chǔ)在以下100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)〔占2個(gè)字節(jié)〕和指針〔占2個(gè)字節(jié)〕組成，如下所示：05U17X23V31Y47Z^^100120其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？五、寫(xiě)出以下程序段的輸出結(jié)果〔棧的元素類型SElemType為char〕?！?〕voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;push(S,x);push(S,’a’);push(S,y);pop(S,x);push(S,’t’);push(S,x);pop(S,x);push(S,’t’);push(S,x);pop(S,x);push(S,’s’);while(!StackEmpty(S)){pop(S,y);printf(y);};printf(x);}結(jié)果：__stack___________________〔2〕寫(xiě)出以下程序段的輸出結(jié)果〔隊(duì)列中的元素類型QElemType為char〕。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}結(jié)果：______char_______________略答：X=116Y=0Z=100首址=108末址=112六、解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)那么：【[〔2,3〕，6],(7,10)】,……19,21,32010101213210101106010101213210101106123〔40〕〔60〕192132〔28〕〔11〕7106〔5〕23方案比擬：字母編號(hào)對(duì)應(yīng)編碼字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10+/方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼六、閱讀分析題〔10分〕指出以下算法中的錯(cuò)誤和低效〔即費(fèi)時(shí)〕之處，并將它改寫(xiě)為一個(gè)既正確又高效的算法。StatusDeleteK(SqList&a,inti,intk){StatusDeleteK(SqList&a,inti,intk){//本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<1||k<0||i+k>a.length)returnINFEASIBLE;//參數(shù)不合法else{for(count=1;count<k;count++){//刪除一個(gè)元素for(j=a.length;j>=i+1;j--)a.elem[j-1]=a.elem[j];a.length--;}returnOK;}//DeleteK注：上題涉及的類型定義如下：注：上題涉及的類型定義如下：#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存儲(chǔ)空間基址Intlength;//當(dāng)前長(zhǎng)度Intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList;答：錯(cuò)誤有兩處：參數(shù)不合法的判別條件不完整。例如表長(zhǎng)為10，假設(shè)從第一位置〔i=1〕刪除10個(gè)元素〔k=10〕,要求合理但會(huì)被判為非法。合法的入口參數(shù)條件為〔0<i≤a.length〕^(0≤k≤a.length-i)應(yīng)將if(i<1||k<0||i+k>a.length)returnINFEASIBLE改為：if(！〔〔0<i≤a.length〕^(o≤k≤a.length-i)〕)returnINFEASIBLE第二個(gè)FOR語(yǔ)句中，元素前移的次序錯(cuò)誤。應(yīng)將for(j=a.length;j>=i+1;j--)a.elem[j-1]=a.elem[j];改為for(j>=i+1;j=a.length;j++)a.elem[j-1]=a.elem[j];6.假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比擬兩種方案的優(yōu)缺點(diǎn)。五、算法設(shè)計(jì)〔在以下算法的橫線內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句或表達(dá)式。〕1、直接選擇排序voidselectsort(intR[])//按遞增序?qū)[0]~R[n-1]進(jìn)行直接選擇排序{inti,j,k,temp;for(i=0;i<=;i++){k=i;for(j=;j<=n-1;j++)if(R[j]R[k])k=j;if〔〕{temp=R[i];R[i]=;R[k]=temp;}}}2、中序遍歷二叉樹(shù)設(shè)二叉樹(shù)用二叉鏈表表示，以t為根指針，二叉鏈表結(jié)點(diǎn)的類型為node；棧s的元素類型為指向node的指針類型,棧容量m足夠大。中序遍歷的非遞歸算法如下：structnode{chardata;node*lc,*rc;};voidpreorder(node*t){node*s[m]，*p=t;inttop=-1； //置?？誨o{while(p!=NULL){s[++top]=;;}if(top!=-１)｛p=s[top--]；；；}}while((———————)||(p!=NULL));}《數(shù)據(jù)結(jié)構(gòu)》試卷B(開(kāi)一頁(yè))站點(diǎn)________專業(yè)年級(jí)________姓名_________學(xué)號(hào)_________成績(jī)_________填空題〔每空1分，共15分〕1.向量、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。3.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。4.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)n/2元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)與該元素在表中的位置有關(guān)。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，那么比擬一次查找成功的結(jié)點(diǎn)數(shù)為1；比擬兩次查找成功的結(jié)點(diǎn)數(shù)為；比擬四次查找成功的結(jié)點(diǎn)數(shù)為；平均查找長(zhǎng)度為。二、判斷正誤〔判斷以下概念的正確性，并作出簡(jiǎn)要的說(shuō)明?！场裁款}1分，共10分〕〔〕1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型?！病?.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用?！病?.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。〔〕4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表?！病?.線性表的邏輯順序與存儲(chǔ)順序總是一致的〔〕6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)?！病?.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。〔〕8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端?！病?.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)?！病?0.一個(gè)棧的輸入序列是12345，那么棧的輸出序列不可能是12345。三、單項(xiàng)選擇題〔每題1分，共20分〕〔〕1．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：〔A〕存儲(chǔ)結(jié)構(gòu)〔B〕邏輯結(jié)構(gòu)〔C〕順序存儲(chǔ)結(jié)構(gòu)〔D〕鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)〔〕2.假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)p1=n，那么pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定〔〕3.判定一個(gè)棧ST〔最多元素為m0〕為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0〔〕4設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角局部〔如以下圖所示〕按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角局部中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j〔〕5．具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1〔〕6.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A．5B.6C.7D.87.數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對(duì)于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但E的方法；而D是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表 ③順序存儲(chǔ)非線性表 ④非順序存儲(chǔ)線性表B： ①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①順序查找②循環(huán)查找 ③條件查找 ④二分法查找D：①順序查找②隨機(jī)查找 ③二分法查找 ④分塊查找E：①效率較低的線性查找②效率較低的非線性查找 ③效率較高的非線性查找④效率較高的線性查找答案：A＝B＝C＝D＝E＝8.散列法存儲(chǔ)的根本思想是根據(jù)A來(lái)決定B，碰撞〔沖突〕指的是C，處理碰撞的兩類主要方法是D。供選擇的答案A，B：①存儲(chǔ)地址②元素的符號(hào)③元素個(gè)數(shù)④關(guān)鍵碼值⑤非碼屬性⑥平均檢索長(zhǎng)度⑦負(fù)載因子⑧散列表空間C:①兩個(gè)元素具有相同序號(hào)②兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同③不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址④負(fù)載因子過(guò)大⑤數(shù)據(jù)元素過(guò)多D：①線性探查法和雙散列函數(shù)法②建溢出區(qū)法和不建溢出區(qū)法③除余法和折疊法 ④拉鏈法和開(kāi)地址法答案：A＝B＝C＝D＝9.考慮具有如下性質(zhì)的二叉樹(shù)：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的值都大于其左子樹(shù)上的一切結(jié)點(diǎn)的值。并小于等于其右子樹(shù)上的一切結(jié)點(diǎn)的值?，F(xiàn)把9個(gè)數(shù)1，2，3，…，8，9填入以下圖所示的二叉樹(shù)的9個(gè)結(jié)點(diǎn)中，并使之具有上述性質(zhì)。此時(shí)，n1的值是A，n2的值是B，n9的值是C?，F(xiàn)欲把放入此樹(shù)并使該樹(shù)保持前述性質(zhì)，增加的一個(gè)結(jié)點(diǎn)可以放在D或E。供選擇的答案A～C：①1②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面③n9下面④n6下面⑤n1與n2之間⑥n2與n4之間⑦n6與n9之間⑧n3與n6之間答案：A＝B＝C＝D＝E＝四、簡(jiǎn)答題〔每題5分，共25分〕1.說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。試寫(xiě)出如下圖的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’那么不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？4.試比擬順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？5.給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。五、閱讀理解〔每題5分，共20分〕1、L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，請(qǐng)寫(xiě)出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語(yǔ)句序列。2、閱讀以下算法，假設(shè)有錯(cuò)，改正之。BiTreeInSucc(BiTreeq){BiTreeInSucc(BiTreeq){//q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針，//本函數(shù)返回指向*q的后繼的指針。r=q->rchild;if(!r->rtag)while(!r->rtag)r=r->rchild;returnr;}//ISucc寫(xiě)出以下程序段的輸出結(jié)果〔隊(duì)列中的元素類型QElemType為char〕。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}簡(jiǎn)述以下算法的功能〔棧和隊(duì)列的元素類型均為int〕。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}六、算法設(shè)計(jì)〔每題5分，共15分。至少要寫(xiě)出思路〕寫(xiě)出在順序存儲(chǔ)結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。編寫(xiě)程序，將假設(shè)干整數(shù)從鍵盤(pán)輸入，以單鏈表形式存儲(chǔ)起來(lái)，然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)〔其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn)〕。試寫(xiě)一個(gè)算法，判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。一、填空題〔每空1分，共15分〕1.向量、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。3.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。4.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置有關(guān)。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。8.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，那么比擬一次查找成功的結(jié)點(diǎn)數(shù)為1；比擬兩次查找成功的結(jié)點(diǎn)數(shù)為2；比擬四次查找成功的結(jié)點(diǎn)數(shù)為8；平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度＝O〔log2n〕<5次〔25〕。但具體是多少次，那么不應(yīng)當(dāng)按照公式來(lái)計(jì)算〔即〔21×log221〕/20＝4.6次并不正確！〕。因?yàn)檫@是在假設(shè)n＝2m-1的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為＝〔1＋2×2＋4×3＋8×4＋5×5〕＝74；ASL＝74/20=3.7?。。《⑴袛嗾`〔判斷以下概念的正確性，并作出簡(jiǎn)要的說(shuō)明。〕〔每題1分，共10分〕〔×〕1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。〔×〕2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。〔√〕3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)?！病獭?.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已?！病痢?.線性表的邏輯順序與存儲(chǔ)順序總是一致的〔×〕6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已?！病獭?.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式?！病獭?.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端?！病痢?.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句不對(duì)。〔×〕10.一個(gè)棧的輸入序列是12345，那么棧的輸出序列不可能是12345。錯(cuò)，有可能。三、單項(xiàng)選擇題〔每題1分，共20分〕〔C〕1．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：〔A〕存儲(chǔ)結(jié)構(gòu)〔B〕邏輯結(jié)構(gòu)〔C〕順序存儲(chǔ)結(jié)構(gòu)〔D〕鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)〔C〕2.假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)p1=n，那么pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的〔事實(shí)上題目已經(jīng)說(shuō)明了〕，那么輸入順序必定是1，2，3，…，n，那么出棧的序列是n，…，3，2，1。〔假設(shè)不要求順序出棧，那么輸出序列不確定〕〔B〕3、判定一個(gè)棧ST〔最多元素為m0〕為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0(B)4、設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角局部〔如以下圖所示〕按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角局部中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j〔C〕5．具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1〔C〕6.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A．5B.6C.7D.87、答案：A＝④B＝②C＝④D＝①E＝③8、答案：A＝④B＝①C＝③D＝④9、答案：A＝⑦B＝④C＝⑥D(zhuǎn)＝②E＝⑥四、簡(jiǎn)答題〔每題4分，共20分〕1.說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)那么不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令存放及其他運(yùn)算等等。2.試寫(xiě)出如下圖的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’那么不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量〔j--〕從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。假設(shè)正文在機(jī)內(nèi)已是順序存儲(chǔ)，那么直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)?！驳褩Ｊ窍葴p后壓還是……〕假設(shè)正文是單鏈表形式存儲(chǔ)，那么等同于隊(duì)列，需開(kāi)輔助空間，可以從鏈?zhǔn)组_(kāi)始入棧，全部壓入后再依次輸出。4.試比擬順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：①順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰〔邏輯與物理統(tǒng)一〕；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大〔＝1？〕，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小〔<1〕，存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。假設(shè)線性表的長(zhǎng)度變化不大，且其主要操作是查找，那么采用順序表；假設(shè)線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，那么采用鏈表。5.給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫(huà)出二叉樹(shù)B，并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，那么所有元素都將被唯一確定，問(wèn)題得解。D ACFEGBHI五、閱讀理解〔每題5分，共20分。至少要寫(xiě)出思路〕答：此題答案不唯一，但假設(shè)從已給定序列中挑選，那么限制頗多。(7)Q=P;P結(jié)點(diǎn)，那么不必P結(jié)點(diǎn)，那么不必“順藤摸瓜”，直接鏈接即可。S->next=P->next;(1)P->next=S;(8)while(P->next!=Q)P=P->next;(10)P=Q;(4)S->next=P->next;P->next=S;2、答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag＝1時(shí)說(shuō)明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag＝0時(shí)說(shuō)明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)領(lǐng)先左再根再右，所以應(yīng)當(dāng)找左子樹(shù)直到葉子處。r=r->lchild;直到LTag=1；應(yīng)改為：while(!r->Ltag)r=r->Lchild;BiTreeInSucc(BiTreeq){BiTreeInSucc(BiTreeq){//q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針，//本函數(shù)返回指向*q的后繼的指針。r=q->rchild;//應(yīng)改為r=q；if(!r->rtag)while(!r->rtag)r=r->rchild;//應(yīng)改為while(!r->Ltag)r=r->Lchild;returnr;//應(yīng)改為returnr->rchild；}//ISucc寫(xiě)出以下程序段的輸出結(jié)果〔隊(duì)列中的元素類型QElemType為char〕。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}答：輸出為“char”。簡(jiǎn)述以下算法的功能〔棧和隊(duì)列的元素類型均為int〕。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。invsl(n,a)invsl(n,a)intn;ETa[];{intk;ETt;for(k=1;k<=n/2;k++){t=a[k-1];a[k-1]=a[n-k];a[n-k]=t;}return;}六、算法設(shè)計(jì)〔每題5分，共15分。至少要寫(xiě)出思路〕1、輸入：長(zhǎng)度為n的線性表數(shù)組A(1:n)輸出：逆轉(zhuǎn)后的長(zhǎng)度為n的線性表數(shù)組A(1:n)。C語(yǔ)言描述如下〔其中ET為數(shù)據(jù)元素的類型〕：2.假設(shè)一個(gè)數(shù)組squ[m]存放循環(huán)隊(duì)列的元素。假設(shè)要使這m個(gè)分量都得到利用，那么需另一個(gè)標(biāo)志tag，以tag為0或1來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空”還是“滿”。試編寫(xiě)相應(yīng)的入隊(duì)和出隊(duì)的算法。解：這就是解決隊(duì)滿隊(duì)空的三種方法之①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空〔其他兩種見(jiàn)簡(jiǎn)答題〕；思路：一開(kāi)始隊(duì)空，設(shè)tag=0，假設(shè)從rear一端加到與front指針相同時(shí)，表示入隊(duì)已滿，那么令tag=1；假設(shè)從front一端加到與rear指針相同時(shí)，那么令tag=0，表示出隊(duì)已空。3.試寫(xiě)一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。答：編程如下：intPalindrome_Test()//判別輸入的字符串是否回文序列,是那么返回1,否那么返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{Push(S,c);EnQueue(Q,c);//同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)

}while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;

}//Palindrome_Test數(shù)據(jù)結(jié)構(gòu)考試試卷〔C〕班級(jí)：_________學(xué)號(hào)__________姓名___________〔注意：試卷總分值100，時(shí)間100分鐘，請(qǐng)考生將答案做于試卷答題紙上，違者以零分處理〕填空題：(每空1分，共20分)數(shù)據(jù)結(jié)構(gòu)通常有四種根本的結(jié)構(gòu)，分別是：〔幾何結(jié)構(gòu)〕、〔線性結(jié)構(gòu)〕、〔數(shù)型結(jié)構(gòu)〕、〔圖或網(wǎng)型結(jié)構(gòu)〕。數(shù)據(jù)元素在計(jì)算機(jī)中的兩種不同的存儲(chǔ)結(jié)構(gòu)是：〔順序存儲(chǔ)〕和〔鏈?zhǔn)酱鎯?chǔ)〕。算法的五個(gè)重要特性：〔有窮性〕〔確定性〕〔可行性〕〔輸入〕和〔輸出〕。隊(duì)和棧都是線性表，棧的操作特性是：〔先進(jìn)后出〕，隊(duì)的操作特性是〔先進(jìn)先出〕假設(shè)二維數(shù)組a[6][5]中每個(gè)元素占4個(gè)字節(jié)，在按行存儲(chǔ)的情況下a[2][2]的第一個(gè)字節(jié)的地址是1022，那么a[3][4]的第一個(gè)字節(jié)的地址是〔1050〕，而數(shù)組的第一個(gè)元素a[0][0]的第一個(gè)字節(jié)的地址是〔〕，最后一個(gè)元素a[6][5]的第一個(gè)字節(jié)的地址是〔〕。設(shè)s[1..maxsize]為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂位置，棧為空的條件是〔top==1〕，棧為滿的條件是〔top==maxsize+1〕。用e〔i〕表示活動(dòng)最早開(kāi)始時(shí)間，l〔i〕表示活動(dòng)最遲開(kāi)始時(shí)間。那么關(guān)鍵路徑是〔〕，關(guān)鍵活動(dòng)是〔〕。單項(xiàng)選擇題〔每空一選 每選2分 共20分〕：今有一空棧S，對(duì)以下待進(jìn)棧的數(shù)據(jù)元素序列a，b，c，d，e，f依次進(jìn)棧，不會(huì)出現(xiàn)的出棧序列是〔C〕A．f，e，d，c，b，a B．c，b，a，e，d，fC．e，c，b，d，a，f D．a(chǎn)，b，c，f，e，d現(xiàn)有一廣義表LS=〔a，〔b，c〕，d〕，GetHead〔LS〕=〔〕，GetTail〔LS〕=〔〕。A．a(chǎn) B．〔a〕 C．〔b，c〕，d D．〔〔b，c〕，d〕3〕對(duì)于關(guān)鍵字值序列〔101，12，11，18，61，15，7，18，25，100〕，用篩選法建堆，必須從關(guān)鍵字值為〔〕的結(jié)點(diǎn)開(kāi)始。A．100 B.101 C.15 D.614〕以下說(shuō)法正確的選項(xiàng)是：〔〕哈希表是解決排序的方法圖的結(jié)點(diǎn)關(guān)系是任意的，在拓?fù)渑判蛑?，弧頭結(jié)點(diǎn)可能會(huì)出現(xiàn)在弧尾結(jié)點(diǎn)之前圖的廣度優(yōu)先搜索算法中采用了遞歸樹(shù)是圖的一種特殊形式5〕任何一個(gè)無(wú)向連通圖的最小生成樹(shù)〔〕。A．只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在6〕將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為24的結(jié)點(diǎn)的右孩子編號(hào)為〔〕。A. 48 B. 49 C. 50 D. 257〕折半查找要求查找表中各元素的關(guān)鍵字值必須是〔〕排列。 A．遞增或遞減 B. 遞增 C. 遞減 D. 無(wú)序8〕鏈表不具有的特點(diǎn)是().A．不必事先估計(jì)存儲(chǔ)空間 B. 插入刪除不需要移動(dòng)元素C. 可隨機(jī)訪問(wèn)任一元素 D. 所需空間與線性表長(zhǎng)度成正比9〕串是〔〕。A．不少于一個(gè)字母的序列 B.任意個(gè)字母的序列C. 不少于一個(gè)字符的序列 D.有限個(gè)字符的序列三、圖型題〔共40分〕1〕寫(xiě)出圖中二叉樹(shù)的先序、中序、后序遍歷?！?分〕 A BCDEFGHIJ2〕森林轉(zhuǎn)換成與之對(duì)應(yīng)的二叉樹(shù)?！?分〕A EIBCDFGJH3〕出結(jié)點(diǎn)權(quán)值，請(qǐng)將之建立一棵赫夫曼樹(shù)，并編出赫夫曼編碼?！?分〕{15，26，37，4，12，30，6，9，22}4〕普里姆算法畫(huà)出下網(wǎng)從頂點(diǎn)A出發(fā)生成最小生成樹(shù)的過(guò)程 〔7分〕A3D6974F8E123B5C5〕將以下圖進(jìn)行拓?fù)渑判颉矊?xiě)出三種序列〕〔6分〕V3V4V5V6V7V1V8V2V9V11V10V12快速排序?qū)σ唤M數(shù)由小到大進(jìn)行排列，寫(xiě)出每趟的排序結(jié)果?！?分〕{58，16，11，95，72，8，23，49，69}算法設(shè)計(jì)題：〔共20分〕寫(xiě)一算法將單鏈表中第I個(gè)結(jié)點(diǎn)與第I+1個(gè)結(jié)點(diǎn)交換位置。〔10分〕寫(xiě)出前序遍歷二叉樹(shù)的非遞歸算法?！?0分〕答案(C)填空題：〔20分〕1、集合結(jié)構(gòu)，線性結(jié)構(gòu)，樹(shù)型結(jié)構(gòu)，圖或網(wǎng)型結(jié)構(gòu)2、順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)3、有窮性，確定性，可行性，輸入，輸出4、現(xiàn)進(jìn)后出，先進(jìn)先出5、1050，998，11146、top==1，top=maxsize+17、在AOE-網(wǎng)中，從起點(diǎn)到匯點(diǎn)路徑長(zhǎng)度最長(zhǎng)的路徑為關(guān)鍵路徑。e〔i〕=l〔i〕的活動(dòng)。二、單項(xiàng)選擇題：〔20分〕123456789CADDDBBACD三、圖型題〔共40分,〕1〕 先序：ABDEGJCFHI 中序：DBGJEACHFI 后序：DJGEBHIFCA2〕3〕4〕A3D7FE123BC5〕 1 2 3 4 5 6 7 8 9 12 10 11 1 2 3 4 8 9 12 6 10 5 7 11 2 1 3 4 8 9 12 6 10 5 7 116〕49 16 11 23 8 58 72 95 69 8 23 16 11 49 58 69 72 95 8 23 16 11 49 58 69 72 95 8 11 16 23 49 58 69 72 95四、算法設(shè)計(jì)題：(僅供參考)statusexchange(p){p=head->next;while(p&&i>0){q=p; p=p->next; i=i-1;}if(i=0) {q->next=p->next;p->next=p->next->next;q->next->next=p;}}statusmidorder()bitt,status(*visit)(telemtype)){initstack(s);p=t;while(p||!stackempty(s)){if(p){visit(p->data);push(s,p);p=p->lchild;}else{pop(s,p);p=p->rchild;}}數(shù)據(jù)結(jié)構(gòu)考試試卷〔D〕班級(jí)：_________學(xué)號(hào)__________姓名___________〔注意：試卷總分值100，時(shí)間100分鐘，請(qǐng)考生將答案做于試卷答題紙上，違者零分論處〕填空題〔每個(gè)空格1分，共20分,錯(cuò)填或不填均無(wú)分〕據(jù)結(jié)構(gòu)通常有四種根本的結(jié)構(gòu)，分別是：〔〕、〔〕、〔〕、〔〕。數(shù)據(jù)元素在計(jì)算機(jī)中的兩種不同的存儲(chǔ)結(jié)構(gòu)：〔〕和〔〕。在線性結(jié)構(gòu)中，開(kāi)始結(jié)點(diǎn)〔〕前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有〔〕前驅(qū)結(jié)點(diǎn)。設(shè)有一個(gè)空棧，現(xiàn)輸入序列為E，D，C，B，A，經(jīng)過(guò)push，push，pop，push，pop，push，pop后，棧頂元素是〔〕。在隊(duì)列中入隊(duì)操作由〔〕指針進(jìn)行控制，出隊(duì)操作由〔〕指針進(jìn)行控制。一維數(shù)組的元素起始地址LOC[6]=1000，元素長(zhǎng)度為4，LOC[3]的起始地址為〔〕。廣義表 ((a,b),c,d,(e,f))的表尾是〔〕。具有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)共有〔〕個(gè)結(jié)點(diǎn)。強(qiáng)連通分量是〔〕圖的極大連通子圖。n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多有〔〕條。用迪杰斯特拉算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按照路徑長(zhǎng)度〔〕次序來(lái)得到最短路徑。希爾排序?qū)儆凇病撑判?，快速排序?qū)儆凇病撑判?，堆排序?qū)儆凇病撑判?。單?xiàng)選擇題〔共15小題，每題2分，共30分〕1、在〔〕運(yùn)算中，使用順序表比鏈表好。A、插入 B、根據(jù)序號(hào)查找 C、刪除 D、根據(jù)元素值查找2、在一個(gè)單鏈表中，*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，假設(shè)在*q和*p之間插入結(jié)點(diǎn)*s，那么執(zhí)行〔〕。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、設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次入棧，如果6個(gè)元素的先后出棧順序是s2,s3,s4,s6,s5,s1，那么棧的容量至少應(yīng)該是〔〕。A、2 B、3 C、5 D、64、以下結(jié)論正確的選項(xiàng)是〔〕。空串和空格串是相同的 B、“TEL”是“telephone”的子串C、空串是0個(gè)字符的串 D、空串長(zhǎng)度為15、稀疏矩陣的一般的壓縮方法有〔〕。A、二維數(shù)組 B、廣義表 C、三元組表 D、一維數(shù)組6、深度為5的二叉樹(shù)至多有〔〕個(gè)結(jié)點(diǎn)。A、16 B、31 C、15 D、307、將一顆有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上往下，從左往右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為〔〕。A、98 B、99 C、49 D、508、最短路徑算法可用〔〕實(shí)現(xiàn)。A、普里姆算法 B、迪杰斯特拉算法 C、哈夫曼算法 D、哈希算法9、通常把查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的〔〕作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。A、BST B、WPL C、ASL D、BFS10、設(shè)有10000個(gè)無(wú)序的元素，希望以最快的速度挑選出其中前10個(gè)最大的元素，最好選用的排序方法是〔〕。A、堆排序 B、起泡排序 C、快速排序 D、基數(shù)排序11、計(jì)算機(jī)算法必須具備輸入輸出和〔〕A、計(jì)算方法 B、排序方法 C、解決問(wèn)題的有限運(yùn)算步驟 D、程序設(shè)計(jì)方法12、樹(shù)最適合用來(lái)表示〔〕A、有序數(shù)據(jù)元素 B、無(wú)序數(shù)據(jù)元素C、現(xiàn)有元素之間具有分支層次關(guān)系的數(shù)據(jù) D、元素之間無(wú)聯(lián)系的數(shù)據(jù)13、完全二叉樹(shù)〔〕二叉樹(shù)A、一定是滿 B、可能是滿 C、不是 D、一定不是14、以下說(shuō)法正確的選項(xiàng)是：〔〕哈希表是解決排序的方法圖的結(jié)點(diǎn)關(guān)系是任意的，在拓?fù)渑判蛑校☆^結(jié)點(diǎn)可能會(huì)出現(xiàn)在弧尾結(jié)點(diǎn)之前圖的廣度優(yōu)先搜索算法中采用了遞歸樹(shù)是圖的一種特殊形式15、由普通樹(shù)轉(zhuǎn)換成二叉樹(shù)是非空的二叉樹(shù)，那么轉(zhuǎn)換后的二叉樹(shù)〔〕A、根結(jié)點(diǎn)無(wú)右子樹(shù) B、根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)C、根結(jié)點(diǎn)可能有左右子樹(shù) D、各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹(shù)三、解答題〔本大題共5小題，每題6分，共30分〕：將圖中的森林轉(zhuǎn)換成與之對(duì)應(yīng)的一棵二叉樹(shù)?！?分〕某密碼電文由8個(gè)字母組成，每個(gè)字母在電文中出現(xiàn)的頻率分別是：{7、19、2、6、32、3、21、10}，將這8個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼樹(shù)，并寫(xiě)出其編碼?！?分〕所示為無(wú)向連通網(wǎng)，要求用普里姆〔Prim〕算法構(gòu)造出它的最小生成樹(shù)?！?分〕寫(xiě)出有向圖中三種不同的拓?fù)渑判蛐蛄??！?分〕對(duì)以下一組關(guān)鍵字{46、58、15、45、90、18、10、62}按非遞減序進(jìn)行快速排序，試寫(xiě)出快速排序的每一趟的排序結(jié)果。〔6分〕四、算法題?！脖敬箢}共2小題，每題10分，共20分〕寫(xiě)出單鏈表中的結(jié)點(diǎn)的就地逆置算法。〔10分〕寫(xiě)出中序遍歷二叉樹(shù)的非遞歸算法。〔10分〕數(shù)據(jù)結(jié)構(gòu)考試試卷〔B〕班級(jí)：_________學(xué)號(hào)__________姓名___________〔注意：試卷總分值100，時(shí)間100分鐘，請(qǐng)考生將答案做于試卷答題紙上，違者以零分處理〕一、單項(xiàng)選擇題〔本大題共15小題，每題2分，共30分〕在每題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1．算法指的是〔

〕

A．計(jì)算機(jī)程序

B．解決問(wèn)題的計(jì)算方法

C．排序算法

D．解決問(wèn)題的有限運(yùn)算序列2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址〔

〕

A．必須是不連續(xù)的

B．連續(xù)與否均可

C．必須是連續(xù)的

D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3. 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)〔〕。A．只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在4 .對(duì)于關(guān)鍵字值序列〔101，12，11，18，61，15，7，18，25，100〕，用篩選法建堆，必須從關(guān)鍵字值為〔〕的結(jié)點(diǎn)開(kāi)始。A．100 B.101 C.15 D.615．設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，那么執(zhí)行出隊(duì)操作后其頭指針front值為〔

〕

A．front=front+1

B．front=(front+1)%(m-1)

C．front=(front-1)%m

D．front=(front+1)%m6．如下陳述中正確的選項(xiàng)是〔

〕

A．串是一種特殊的線性表

B．串的長(zhǎng)度必須大于零

C．串中元素只能是字母

D．空串就是空白串7．一個(gè)非空廣義表的表頭〔

〕

A．不可能是子表

B．只能是子表

C．只能是原子

D．可以是子表或原子8. 以下說(shuō)法正確的選項(xiàng)是：〔〕哈希表是解決排序的方法圖的結(jié)點(diǎn)關(guān)系是任意的，在拓?fù)渑判蛑?，弧頭結(jié)點(diǎn)可能會(huì)出現(xiàn)在弧尾結(jié)點(diǎn)之前圖的廣度優(yōu)先搜索算法中采用了遞歸樹(shù)是圖的一種特殊形式9．n個(gè)頂點(diǎn)的連通圖至少有______條邊?！?.0分〕A.n-1B.n C.n+1D.010．用某種排序方法對(duì)關(guān)鍵字序列〔25，84，21，47，15，27，68，35，20〕進(jìn)行排序時(shí)，序列的變化情況如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

那么所采用的排序方法是〔

〕A．選擇排序

B．希爾排序

C．快速排序

D．歸并排序11.高度為h的二叉樹(shù)的結(jié)點(diǎn)最多是多少〔〕

A.2h＋1B.2h－1C.2h+1－1D.2h12.對(duì)于下面二叉樹(shù)，按后序遍歷所得的結(jié)點(diǎn)序列為_(kāi)__________。

A、1234567B、1245367 C、4526731D、4251637

13. 哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL等于___________。

A、除根以外的所有結(jié)點(diǎn)的權(quán)植之和B、所有結(jié)點(diǎn)權(quán)值之和