數(shù)據(jù)結構期末試卷復習題錦

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

{

InitStack(S);InitQueue(Q);

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

{Push(S,c);EnQueue(Q,c);//同時使用棧和隊列兩種結構

}while(!StackEmpty(S))

{

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

if(a!=b)returnERROR;

}

returnOK;

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

〕

A．計算機程序

B．解決問題的計算方法

C．排序算法

D．解決問題的有限運算序列2．線性表采用鏈式存儲時，結點的存儲地址〔

〕

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

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

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

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

〕

A．front=front+1

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

C．front=(front-1)%m

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

〕

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

B．串的長度必須大于零

C．串中元素只能是字母

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

〕

A．不可能是子表

B．只能是子表

C．只能是原子

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

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的二叉樹的結點最多是多少〔〕

A.2h＋1B.2h－1C.2h+1－1D.2h12.對于下面二叉樹，按后序遍歷所得的結點序列為___________。

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

13. 哈夫曼樹的帶權路徑長度WPL等于___________。

A、除根以外的所有結點的權植之和B、所有結點權值之和