數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

1、第 1 章 緒論習(xí)題1簡述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲 結(jié)構(gòu)、抽象數(shù)據(jù)類型。2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，表達(dá)其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。3簡述邏輯結(jié)構(gòu)的四種根本關(guān)系并畫出它們的關(guān)系圖。4存儲結(jié)構(gòu)由哪兩種根本的存儲方法實現(xiàn)？5選擇題 1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D .內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的。A. 存儲結(jié)構(gòu)B存儲實現(xiàn)C.邏輯結(jié)構(gòu)D運算實現(xiàn) 3通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著

2、。A .數(shù)據(jù)具有同一特點B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C. 每個數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 4以下說法正確的選項是。A. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位B. 數(shù)據(jù)項是數(shù)據(jù)的根本單位C. 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D. 一些外表上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)5以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是。A. 順序隊列B. 鏈表C.有序表D.鏈棧 6以下數(shù)據(jù)結(jié)構(gòu)中， 是非線性數(shù)據(jù)結(jié)構(gòu)A.樹 B .字符串C .隊 D.棧6.試分析下面各程序段的時間復(fù)雜度。 1 x=90; y=100;whiley0ifx100x=x-10;y-;e

3、lse x+;2for i=0; in; i+for j=0; jm; j+aij=0;3s=0;for i=0; in; i+for(j=0; j n; j+)s+=Bij；sum=s;(4) i=1； while(i=n)i=i*3;(5) x=0;for(i=1; in; i+)for (j=1; jnext=p-next; p-next=s-next;D. s-next=p-next; p-next=s;(14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針()。A. p-next_prior=p_prior; p-prior-next=p-next;B. p_next=p-ne

4、xt-next; p_next-prior=p;C. p-prior-next=p; p_prior=p_prior-prior;D. p-prior=p-next-next; p-next=p-prior-prior;(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是()。A. p_next=q; q-prior=p; p_next-prior=q; q_next=q;B. p_next=q; p_next-prior=q; q-prior=p; q_next=p-next;C. q-prior=p; q_next=p-next; p_next-prio

5、r=q; p_next=q;D. q-prior=p; q_next=p-next; p_next=q; p_next-prior=q;2.算法設(shè)計題(1)將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩 個鏈表的存儲空間，不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)pa=La-n ext; pb=Lb-n ext;Lc=pc=La;想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到操作(A.C.(5)中,那么應(yīng)執(zhí)行)x=top-data;top=top-li nk

6、x=top;top=top-li nk；設(shè)有一個遞歸算法如下int fact(i nt n) B . top=top-link;x=top-link D . x=top-link ;線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu))僅修改尾指針D.頭、尾指針可能都要修改A0.m中，那么入隊時的操作為(B. rear=(rear+1)%(m-1)D.rear=(rear+1)%(m+1)曰D.(11) 用鏈接方式存儲的隊列，在進(jìn)行刪除運算時(A.僅修改頭指針C.頭、尾指針都要修改(12) 循環(huán)隊列存儲在數(shù)組A. rear=rear+1C. rear=(rear+1)%m(13) 最大容量為n的循環(huán)隊列，隊尾指針是rear，

7、隊頭是front，那么隊空的條件是()B.C. rear+1=frontD. (rear-l)% n=front都是先進(jìn)后出D.沒有共同點終止條件和遞歸局部 終止條件和迭代局部14 棧和隊列的共同點是。A.都是先進(jìn)先出B.C.只允許在端點處插入和刪除元素15 個遞歸算法必須包括。A.遞歸局部B.C.迭代局部D.2回文是指正讀反讀均相同的字符序列，如“abba和abdba均是回文，但“good不是回文。試寫一個算法判定給定的字符向量是否為回文。提示：將一半字符入棧根據(jù)提示，算法可設(shè)計為：10110100 B. 10010110 C. IIIOIOIO D. IIIOOIOO 通過對的分析，寫出一

8、個算法，判定所給的操作序列是否合法。假設(shè)合法，返回true，否那么返回false 假定被判定的操作序列已存入一維數(shù)組中。 A和D是合法序列，B和C是非法序列。 設(shè)被判定的操作序列已存入一維數(shù)組A中。int Judge char AM-1實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，rear+1%m=fro nt為隊滿。約定隊頭端入隊向下標(biāo)小的方向開展，隊尾端入隊向下標(biāo)大的方向開展。1 #define M隊列可能到達(dá)的最大長度typedef struct elemtp data

9、M;int fron t,rear; cycqueue;2elemtp delqueue cycqueue Q:n+1當(dāng) = D當(dāng) e円山刊時 100,仁100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10,那么LOC5,5=。A. 808B . 818C . 1010D. 10207 設(shè)有數(shù)組 Ai,j，數(shù)組的每個元素長度為 3字節(jié)，i的值為1到8，j的值為1 到10，數(shù)組從內(nèi)存首地址 BA開始順序存放，當(dāng)用以列為主存放時， 元素A5,8的存儲首地 址為。A. BA+141B . BA+180 C . BA+222 D . BA+2258 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為

10、主存儲，an為第一元素，其存儲地址為1,每個元素占一個地址空間，那么a85的地址為。A. 13B . 33C . 18D. 409 假設(shè)對n階對稱矩陣A以行序為主序方式將其下三角形的元素包括主對角線上所有元素依次存放于一維數(shù)組 B1.nn+1/2中，那么在B中確定am ij 的位置k的關(guān)系為()。A. i*(i-1)/2+jB. j*(j-1)/2+iC . i*(i+1)/2+j D. j*(j+1)/2+i(10) AN, N是對稱矩陣，將下面三角(包括對角線)以行序存儲到一維數(shù)組TN(N+1)/2(1)模式串nextval 函數(shù)值。t= abcaabbabcab 寫出用 KMP法求得的每

11、個字符對應(yīng)的next 和中，那么對任一上三角兀素aij對應(yīng)Tk的下標(biāo)k是()。A. i(i-1)/2+jB .j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1(11)設(shè)二維數(shù)組A1.m,1. n(即m行n列)按行存儲在數(shù)組B1. m*n中，那么二維數(shù)組兀素Ai,j 在一維數(shù)組B中的下標(biāo)為()。A. (i-1)*n +jB.(i-1)* n+j-1 C.i*(j-1)D.j*m+i-1(12)數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)()。A. 55B. 45C.36D.16(13)廣義表A=(a,b,(c,d),(e,(f,g)，那么 Head(Tail(Head(T

12、ail(Tail(A)的值為()。A. (g)B. (d)C.cD. d(14)廣義表(a,b,c,d)的表頭是(),表尾是()。A. aB. ( )C.(a,b,c,d)D . (b,c,d)(15)設(shè)廣義表L=(a,b,c)，貝U L的長度和深度分別為()。A. 1 和 1 B . 1 和 3C . 1 和 2D . 2 和 3模式串t的next和nextval值如下:j1 2 3 4 5 6 7 8 9 10 11 12t串a(chǎn) b c a a b b a b c a bn extj0 1 1 1 2 2 3 1 2 3 4 5n extvalj0 1 1 0 2 1 3 0 1 1 0

13、5(2) 設(shè) 目標(biāo)為 t= “ abcaabbabcabaacbacba ,模式為 p= “ abcabaa 計算模式p的naxtval函數(shù)值； 不寫出算法，只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。 p的nextval函數(shù)值為 0110132。 ( p的next函數(shù)值為 0111232 )。 利用KMP改良的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配

14、：abcaabbabcabaac bacba(成功)abcabaa(i=15,j=8)(3)數(shù)組A中，每個元素Ai,j的長度均為32個二進(jìn)位，行下標(biāo)從-1到9，列下標(biāo)從1到11,從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第 4 列所有元素至少需多少單元？ 數(shù)組按行存放時，元素A7,4 的起始地址是多少？ 數(shù)組按列存放時，元素A4,7 的起始地址是多少？每個元素 32 個二進(jìn)制位，主存字長 16 位，故每個元素占 2 個字長，行下標(biāo)可平移至 1 到 11。(1) 242(2)22(3)s+182( 4) s+1 42 請將香蕉banana用工

15、具H( ) Head( )，T( ) Tail() 從L中取出。 L=(apple,(orange,(strawberry,(banana),peach),pear)H( H(T( H( T( H( T( L)(5)寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件(字 符串中的合法字符為 A-Z 這 26 個字母和 0-9 這 10個數(shù)字)。void Count ()是字符串輸入結(jié)束標(biāo)志InvertStore(A);Ai+ = ch; m, 1.n含有 m*n 個整數(shù)。 寫一個算法判斷 a 中所有元素是否互不相同 ?輸出相關(guān)信息 (yes/no) ； 試分析算法的時間復(fù)雜度。

16、 題目分析 判斷二維數(shù)組中元素是否互不相同，只有逐個比擬 , 找到一對相等的元素， 就可結(jié)論為不是互不相同。 如何到達(dá)每個元素同其它元素比擬一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比擬一次(下面第一個循環(huán)控制變量 p 的 for 循環(huán))，然后同第 i+1 行及以后各行元素比擬一次，這就是循環(huán)控制變量 k 和 p 的二層 for 循環(huán)。 int JudgEqual(ing amn, int m,n)算法討論對數(shù)組中元素各比擬一次，比擬次數(shù)為n。最正確情況(已排好，正數(shù)在前，負(fù)數(shù)在后 ) 不發(fā)生交換，最差情況 ( 負(fù)數(shù)均在正數(shù)前面 ) 發(fā)生 n/2 次交換。用類 c 編寫，數(shù)組界 偶是

17、0.n-1 ?？臻g復(fù)雜度為 O(1).第 5 章 樹和二叉樹1選擇題( 1)把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是()。A.唯一的E.有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子(2) 由 3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？()A. 2 B . 3 C . 4D. 5(3) 一棵完全二叉樹上有 1001 個結(jié)點，其中葉子結(jié)點的個數(shù)是( )。A. 250B . 500 C . 254 D. 501(4) 一個具有 1025 個結(jié)點的二叉樹的高 h 為( )。A. 11 B . 10C. 11至 1025之間 D . 10 至 1024 之間(5) 深度為h的滿

18、m叉樹的第k層有()個結(jié)點。(仁k=h)A. mk-1B . mk-1C. mh-1D . mh-1(6) 利用二叉鏈表存儲樹，那么根結(jié)點的右指針是()。A.指向最左孩子B.指向最右孩子C .空 D .非空(7) 對二叉樹的結(jié)點從 1 開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子 的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()遍歷實現(xiàn)編號。A.先序B.中序C. 后序 D.從根開始按層次遍歷( 8)假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利 用( )遍歷方法最適宜。A.前序B .中序C .后序 D .按層次(9)在以下存儲形式中，

19、 ( )不是樹的存儲形式？A.雙親表示法 B .孩子鏈表表示法C .孩子兄弟表示法D.順序存儲表示法( 10)一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，那么該二叉樹一定滿足( )。A.所有的結(jié)點均無左孩子B.所有的結(jié)點均無右孩子C.只有一個葉子結(jié)點D.是任意一棵二叉樹( 11)某二叉樹的前序序列和后序序列正好相反，那么該二叉樹一定是()的二叉樹。A.空或只有一個結(jié)點B.任一結(jié)點無左子樹C.高度等于其結(jié)點數(shù)D.任一結(jié)點無右子樹(12) 假設(shè)X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，那么X的前驅(qū)為()。A. X的雙親B. X的右子樹中最左的結(jié)點C. X的左子樹 中最右結(jié)點D

20、. X的左子樹中最右葉結(jié)點(13) 引入二叉線索樹的目的是()。A.加快查找結(jié)點的前驅(qū)或后 繼的速度 B .為了能在二叉樹中方便的進(jìn)行插入與刪 除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一( 14)線索二叉樹是一種()結(jié)構(gòu)。A.邏輯B .(15)設(shè)F是一個森林, 右指針域為空的結(jié)點有(A. n-1 B邏輯和存儲C .物理D .線性B是由F變換得的二叉樹。假設(shè) F中有n個非終端結(jié)點，那么 B中 )個。n+12應(yīng)用題(1)試找出滿足以下條件的二叉樹先序序列與后序序列相同先序序列與中序序列相同n+2中序序列與后序序列相同中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是根一左子樹一右子樹 后序

21、遍歷順序是：(1)(2)(3)，中序遍歷“左子樹一根一右子樹“左子樹一右子樹一根，根據(jù)以上原那么，此題解答如下： 假設(shè)先序序列與后序序列相同，那么或為空樹，或為只有根結(jié)點的二叉樹 假設(shè)中序序列與后序序列相同，那么或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹. 假設(shè)先序序列與中序序列相同，那么或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹.(4) 假設(shè)中序序列與層次遍歷序列相同，那么或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹(2)設(shè)一棵二叉樹的先序序列：A B D F C E G H ，中序序列: 畫出這棵二叉樹。 畫出這棵二叉樹的后序線索樹。 將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹(或森林)。nullAM

22、H(3(3)為丿 V ) ? ? ? ? ?(1)假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別? 試為這8個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進(jìn)制表示的等長編碼方案。對于上述實例，比擬兩種方案的優(yōu)缺點。解：方案1;哈夫曼編碼 先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)那么:32【(2,3 ), 6, (7,10)】,19, 21,(100(192132(28)(17)(11)710 6(5)23字母編號對應(yīng)編碼出現(xiàn)頻率1110020031111041110510方案比擬:方案 1 的 WPL= 2+4+5+=+=方案

23、2 的 WPA 3+=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼(4)以下字符AB、C、DE、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹 HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightpare ntIchildrchild13000212000370004400052000680007110008000900010000110001200013000weightpare ntlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112終

24、態(tài)3.算法設(shè)計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法:(1)統(tǒng)計二叉樹的葉結(jié)點個數(shù)。int LeafNodeCou nt(BiTree T)if(T=NULL) return 0; D .圖C；隊列C.(9)用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常借助( A.棧B.隊列C.來實現(xiàn)算法。.圖(10)深度優(yōu)先遍歷類似于二叉樹的A.先序遍歷B .中序遍歷后序遍歷.層次遍歷(11)廣度優(yōu)先遍歷類似于二叉樹的A.先序遍歷B .中序遍歷后序遍歷D.層次遍歷(12)圖的BFS生成樹的樹高比 DFS生成樹的樹高(A.小B.相等C .小或相等大或相等(13)圖的鄰接矩陣如下圖，那么從頂點0出發(fā)按深度優(yōu)先遍

25、歷的結(jié)果是()。01111011001001A.0 2 4 3 1 5 61000100B.0 1 3 6 5 4 21100110C.0 1 3 4 2 5 61011010D.0 3 6 1 5 4 200011011100010圖鄰接矩陣0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是),按A. 0 1 3 2C. 0 3 2 1D. 0 1 2 3圖鄰接表15下面方法可以判斷出一個有向圖是否有環(huán)。A .深度優(yōu)先遍歷B.拓?fù)渑判駽 .求最短路徑2.應(yīng)用題1如下圖的有向圖，請給出: 每個頂點的入度和出度； 鄰接矩陣；鄰接表；逆鄰接表。.求關(guān)鍵路徑14圖的鄰接表如下圖，那么從頂點 深度優(yōu)先遍歷的結(jié)果是D(點23

26、4呂6A*321L22:出度0213130 0 0 0 O 1OO1OO 0 1 0 Q 0 1 0 0 10 11 1 0 0 0 0 0 J i 0 0 1 0.鄲接表連鄰接農(nóng)(2)如下圖的無向網(wǎng)，請給出: 鄰接矩陣； 鄰接表； 最小生成樹4 34553555 5976554976533226圖無向網(wǎng)a b c d efffffd5fd5fe7ff3Ag2Ah6Ag6A(3) 圖的鄰接矩陣如所示。試分別畫出自頂點1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。00 D0圖有向網(wǎng)4有向網(wǎng)如下圖，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑,完成表。V、終 點i=1i=2i=3i

27、=4i=5i=6b15(a,b)15b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,fLgcoco16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b5試對圖所示的 AOE網(wǎng)： 求這個工程最早可能在什么時 間結(jié)束； 求每個活動的最早開始時間和 最遲開始時間； 確定哪些活動是關(guān)鍵活動圖AOE-網(wǎng)【解答】按拓?fù)溆行虻捻樞?/p>

28、計算各個頂點的最早可能開始時間Ve和最遲允許開始時間VI。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間I，根據(jù)I - e = 0?來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。123456Ve01915293843Vl01915373843e00151919152938l170152719273738-e1700801280此工程最早完成時間為 43。關(guān)鍵路徑為3 算法設(shè)計題(1)分別以鄰接矩陣和鄰接表作為存儲結(jié)構(gòu)，實現(xiàn)以以下圖的根本操作: 增添一個新頂點v, lnsertVex(G, v); 刪除頂點v及其相關(guān)的邊，DeleteVex(G , v); 增加一條邊 ,InsertArc(G ,v,w); 刪除一條邊 ,DeleteArc(G ,v,w)。dj)j.adj=1;+;return OK;dj=0;5return OK;Status Delete_Arc(MGraph &G,char v,char w)dj) j.adj=0;return OK; 余算法請自行寫出 .Status Insert_Arc(ALGraph &G,char v,char w)irstarc;p;p=p