青島XX大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2期末試題及參考答案

教師試做時間出題教師房斐斐取題時間審核教研室主任出題單位使用班級考試日期考試成績期望值印刷份數(shù)規(guī)定完成時間交教學(xué)部印刷日期學(xué)號：姓名：班級：..........................................................密.......................................................封...........................................................線..........................................................專業(yè)年級班20~20學(xué)年第學(xué)期數(shù)據(jù)結(jié)構(gòu)課試卷試卷類型：復(fù)習(xí)題2卷題號一二三四五六七八九十總成績得分填空題（每空1分，共10分）數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D，R)，其中D是______________________的有限集合，R是D上的______________________有限集合。棧中元素的進(jìn)出原則是______________________。假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則末尾元素A57的第一個字節(jié)地址為；若按行存儲時，元素A14的第一個字節(jié)地址為。一棵具有257個結(jié)點的完全二叉樹，它的深度為。n個頂點e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為。線性有序表(a1,a2,a3,…,a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索次。設(shè)要將序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是______________________________________________。在堆排序、快速排序和歸并排序中，若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取______________________方法。選擇題（每題2分，共30分）（）1.算法分析的兩個主要方面是：（A）空間復(fù)雜性和時間復(fù)雜性（B）正確性和簡明性（C）可讀性和文檔性（D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（）2.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是：（A）訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）（B）在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）（C）刪除第i個結(jié)點（1≤i≤n）（D）將n個結(jié)點從小到大排序（）3．雙向循環(huán)鏈表的每個結(jié)點中包括兩個指針next和previous，分別指向該結(jié)點的后繼和前驅(qū)結(jié)點。現(xiàn)要刪除指針p所指向的結(jié)點，下面的操作序列中哪一個是正確的？（A）p-next-〉previous=p->previous;p->previous-〉next=p->next；（B）p->next-〉previous=p->next;p->previous-〉next=p->previous；（C）p->previous-〉next=p->previous;p->next-〉previous=p->next；（D）p->previous-〉next-〉next=p-next;p->next-〉previous=p->previous；（）4.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以（）5.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（Ａ）i（Ｂ）n=i（Ｃ）n-i+1（Ｄ）不確定（）6.數(shù)組Q[n]用來表示一個循環(huán)隊列，f為當(dāng)前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n（）7.判定一個棧ST（最多元素為m）為空的條件是（Ａ）ST->top<>0（Ｂ）ST->top=0（Ｃ）ST->top<>m（Ｄ）ST->top=m青島理工大學(xué)成教學(xué)院試卷紙共頁第1頁試題要求：1、試題后標(biāo)注本題得分；2、試卷應(yīng)附有評卷用標(biāo)準(zhǔn)答案，并有每題每步得分標(biāo)準(zhǔn)；3、試卷必須裝訂，拆散無效；4、試卷必須打印或用碳素筆楷書，以便譽(yù)??；5、考試前到指定地點領(lǐng)取試卷；6、各題之間應(yīng)適當(dāng)給學(xué)生留下答題的空間。學(xué)號；姓名：班級：..........................................................密.......................................................封..........................................................線.........................................................._學(xué)年第學(xué)期數(shù)據(jù)結(jié)構(gòu)課程試卷標(biāo)準(zhǔn)答案及評分標(biāo)準(zhǔn)復(fù)習(xí)題2卷注意：標(biāo)題請用宋體4號，內(nèi)容請用宋體5號。一、填空題(每空1分，共10分)數(shù)據(jù)元素；關(guān)系后進(jìn)先出1282；10729O(n+e)8HCQPAMSRDFXY堆排序單項選擇題(每空2分，共30分，多選漏選均不得分)1.A2.A3.A4.D5.C6.D7.B8.A9.D10.B11.C12.D13.A14.A15.D三、判斷題(每題1分，共10分)1.×2.×3.×4.√5.√6.√7.×8.×9.√10.√四、簡答題(共18分，意思正確給分)1.試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？（共4分）解答：①順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大，存儲空間利用率高。缺點：插入或刪除元素時不方便。②鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。?lt;1），存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2.把如圖所示的樹轉(zhuǎn)化成二叉樹。（共6分）ABECKFHDLGIMJ(3分)前序：ABEKLFGMCHIJD（1分）中序：KLEFMGBIJHCDA(1分)后序：LKMGFEJIHDCBA（1分）3.（共8分）10100（1）1010013961139611001001100C2172236251100C217223625C77111110C771111101100C6C51100C6C556345634C4C1C8CC4C1C8C3（4分）（2）c1c2c3c4c5c6c7c801101000000111001010110001（2分）（3）WPL=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4 =257（2分）頂點1234頂點123456入度出度1.(共5分)ABCDEFG（2分）GFEDCBA（3分）2．（共5分）解答：判斷輸入的字符序列是否“回文”。3.（共6分）解答：BiTreeInSucc(BiTreeq){//已知q是指向中序線索二叉樹上某個結(jié)點的指針，BiTreeInSucc(BiTreeq){//已知q是指向中序線索二叉樹上某個結(jié)點的指針，//本函數(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答：這是找結(jié)點后繼的程序。共有3處錯誤。當(dāng)rtag＝0時說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計算。中序遍歷應(yīng)當(dāng)先左再根再右，所以應(yīng)當(dāng)找左子樹直到葉子處。r=r->lchild;直到LTag=1；應(yīng)改為：while(!r->Ltag)r=r->Lchild;（共8分）intDepth(BiTreeT){//返回二叉樹的深度if(!T)depthval=0;else{m=Depth(T->lchild);n=Depth(T->rchild);depthval=1+(m>n?m:n);}returndepthval;}（共8分）intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸算法{if(low>high)return0;//查找不到時返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive（）8.判定一個隊列QU（最多元素為m）為滿隊列的條件是（Ａ）QU->rear－QU->front==m（Ｂ）QU->rear－QU->front－1==m（Ｃ）QU->front==QU->rear（Ｄ）QU->front==QU->rear+1（）9.設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：（Ａ）BCDEF（Ｂ）BCDEFG（Ｃ）BCPQRST（Ｄ）BCDEFEF（）10.具有12個結(jié)點的完全二叉樹有個度為2的結(jié)點。（Ａ）4（Ｂ）5（Ｃ）6（Ｄ）7（）11.具有n(n>0)個結(jié)點的完全二叉樹的深度為。（Ａ）log2(n)（Ｂ）log2(n)（Ｃ）log2(n)+1（Ｄ）log2(n)+1（）12.已知圖的鄰接矩陣如右圖，根據(jù)算法，則從頂點0出發(fā)，按深度優(yōu)先遍歷的結(jié)點序列是：（Ａ）0243156（Ｂ）0135642（Ｃ）0423165（Ｄ）0134256（）13.設(shè)哈希表長度為11，哈希函數(shù)為H（key）=keymod11。表中已有4個元素 H（15）=4； H（38）=5；H（61）=6； H（84）=7其余地址為空，若用二次探測再散列處理沖突，關(guān)鍵字為49的元素的地址是__________。（Ａ）3 （Ｂ）5 （Ｃ）8 （Ｄ）9（）14.假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為。（無第0行第0列元素）（Ａ）16902（Ｂ）16904（Ｃ）14454（Ｄ）答案A,B,C均不對（）15.廣度優(yōu)先遍歷類似于二叉樹的（Ａ）先序遍歷（B）中序遍歷（C）后序遍歷（D）層次遍歷判斷題（每題1分，共10分）（）1.鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機(jī)會自動地將后續(xù)的各個單元向前移動。（）2.線性表在物理存儲空間中也一定是連續(xù)的。（）3.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）4.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。（）5.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n-1個非空指針域。（）6.二叉樹中每個結(jié)點的兩棵子樹是有序的。（）7.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。（）8.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。（）9.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。()10.設(shè)有一稠密圖G，則G采用鄰接矩陣存儲較省空間。簡答題（共18分）試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？（4分）把如圖所示的樹轉(zhuǎn)化成二叉樹,并寫出其前序、中序、后序遍歷序列。（6分）假定用于通信的電文僅由8個字母c1,c2,c3,c4,c5,c6,c7,c8組成,各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。（共8分）（1）試構(gòu)造哈夫曼樹（4分）（2）試為這8個字母設(shè)計不等長Huffman編碼,（2分）（3）求其WPL值。（2分）青島理工大學(xué)成教學(xué)院試卷紙共頁第頁學(xué)號；姓名：班級：..........................................................密.......................................................封..........................................................線..........................................................算法理解題（共16分）1.閱讀算法，寫出該算法的結(jié)果(5分)main(){SqStackTpsq;inti;c