南京工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)作業(yè)答案(全)

1、作業(yè) 11數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎答：簡單地說， 數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。2閱讀下列 C程序段，寫出相應(yīng)的執(zhí)行結(jié)果（每小題 4 分，共 8分）1)。 printf( “ Input x ” );2)。 long int fact(n)scanf( “ %d” ,&x);int n;if (x20) y=x;if(n1)f=n*fact(n-1);else if (x10) y=2*x;else f=1;if (x0&x30)printf(“x=%d,y=%d”,x,y);return(f

2、);else printf( “輸入數(shù)據(jù)錯！” );試寫出當(dāng) x 分別為 18， 8 時的執(zhí)行結(jié)果。main()答：運(yùn)行結(jié)果為： x=18， y=36int n;x=8 ，y=運(yùn)行前的值， 且從 x30 開始為數(shù)據(jù)錯long y;n=5;y=fact(n);printf( “ %d,% n”,n,y);3分析下面各程序段的時間復(fù)雜度2. s=0;1. for (i=0; in; i+)for i=0; in; i+)3. x=0;for (j=0; jm; j+)for(j=0; jn; j+)Aij=0;s+=Bij;sum=s;for(i=1; in; i+)for (j=1; j=n-i

3、; j+)x+;4. i=1;while(i=n)i=i*3;作業(yè) 21. 【嚴(yán)題集】 試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好答： 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（ 1），存儲空間利用率高。缺點(diǎn)：插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時很方便，使用靈活。缺點(diǎn)：存儲密度小（prior-next=P;(11) P-next-prior =P;(1)P-next=P-

4、next-next;(2)P-prior=P-prior-prior;(3) P-next=S;(12)P-next-prior=S;(4) P-prior=S;(13) P-prior-next=S;(5)S-next=P;(14) P-next-prior=P-prior(6)S-prior=P;(15)Q=P-next;(7) S-next= P-next;(16)Q= P-prior;(8) S-prior= P-prior;(17)free(P);(9) P-prior-next=p-next;(18)free(Q);解答：a. （12）（7）（3）（6）必須在 12和 7 的后面，

5、其余的順序可變b. （13）（8）（4）（5）同上c. （15）（1）（11）（18）不可變d. （16）（2）（10）（18）不可變e. （9）（14）（17）4. 編寫程序，將若干整數(shù)從鍵盤輸入，以單鏈表形式存儲起來，然后計(jì)算單鏈表中結(jié)點(diǎn)的 個數(shù)（其中指針 P 指向該鏈表的第一個結(jié)點(diǎn)） 。 注：統(tǒng)計(jì)結(jié)點(diǎn)個數(shù)是【省統(tǒng)考樣題】的要 求，也是教材 P60 4-6 計(jì)算鏈表長度的要求，編程又簡單，很容易作為考題。解： 編寫 C程序如下 （已上機(jī)通過 ）：全局變量及函數(shù)提前說明：#include #include typedef struct liuyuint data;struct liuyu*l

6、ink;test;liuyu *p,*q,*r,*head;int m=sizeof(test);void main ()/*第一步，從鍵盤輸入整數(shù)，不斷添加到鏈表*/int i;head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0;while (i!=-9999) printf(/ninput an integerstop by -9999:);scanf(%d,&i);p-data=i;/* input data is saved */p-link=(test*)malloc(m); /*m=sizeof(test);*/ q=p;p

7、=p-link;q- link=NULL;/*原先用 p-link=NULL 似乎 太晚！ */p=head; i=0;/*統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個數(shù)并打印出來 */while (p-link!=NULL)printf(%d,p-data);p=p-link;i+;printf(n node number=%dn,i-1 ）; /* 結(jié)點(diǎn)的個數(shù)不包括 -9999*/作業(yè) 31. 假設(shè)正讀和反讀都相同的字符序列為“回文”，例如， abba 和 abcba 是回文， abcde 和 ababab則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性答：線性表是隨機(jī)存

8、儲，可以實(shí)現(xiàn)，靠循環(huán)變量（j- ）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好， 要具體情況具體分析。 若正文在機(jī)內(nèi)已是順序存儲， 則直接用線性表從POP動作實(shí)現(xiàn)。（但堆棧是先減后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用 后壓還是全部壓入若正文是單鏈表形式存儲，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧， 后再依次輸出。2. 順序隊(duì)的“假溢出”是怎樣產(chǎn)生的如何知道循環(huán)隊(duì)列是空還是滿答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置， 這就叫“假溢出” 。采用循環(huán)隊(duì)列是解決假

9、溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三： 設(shè)置一個布爾變量以區(qū)別隊(duì)滿還是隊(duì)空； 浪費(fèi)一個元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個計(jì)數(shù)器記錄隊(duì)列中元素個數(shù)(即隊(duì)列長度)我們常采用法，即隊(duì)頭指針、隊(duì)尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是： f=rear隊(duì)滿標(biāo)志是： f=(r+1)%N3. 設(shè)循環(huán)隊(duì)列的容量為 40序號從 0 到 39)，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有 front=11 ， rear=19; front=19 ， rear=11 ；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個答：用 隊(duì)列長度計(jì)算公式：（N rf）% N L= （401911）%

10、 40=8 L= （401119）% 40=324. 試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文” 。答：編程如下：int Palindrome_Test() 設(shè)如下圖所示的二叉樹 B 的存儲結(jié)構(gòu)為二叉鏈表， root 為根指針，結(jié)點(diǎn)結(jié)構(gòu)為： （ lchild,data,rchild)。其中 lchild ， rchild 分別為指向左右孩子的指針，data 為字符型， root為根指針，試回答下列問題：(1). 對下列二叉樹 B，執(zhí)行下列算法 traversal(root) ，試指出其輸出結(jié)果；C的結(jié)點(diǎn)類型定義如下：struct nodechar data;struct no

11、de * lchild,rchild;C算法如下： void traversal（struct node *root） if （root）printf( “ %c” , root-data);traversal(root-lchild);printf( “ %c” , root-data);traversal(root-rchild);(2). 假定二叉樹 B 共有n 個結(jié)點(diǎn)，試分析算法 traversal(root)的時間復(fù)雜度。二叉樹解：這是“先根再左再根再右” ，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：特點(diǎn)： 每個結(jié)點(diǎn)肯定都會被打印兩次； 但出現(xiàn)的順序不同，其規(guī)律是： 凡是有左子樹的結(jié)點(diǎn)

12、，必間隔左子樹的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)； 如 A，B，D等結(jié)點(diǎn)。 反之馬上就會重復(fù)出現(xiàn)。如 C， E，F(xiàn)，G等結(jié)點(diǎn)。時間復(fù)雜度以訪問結(jié)點(diǎn)的次數(shù)為主，精確值為2*n ，時間漸近度為 O(n).2. 試寫出如圖所示的二叉樹分別按先序、答： DLR： A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A3. 把如圖所示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線 （包括度為 2的兄弟） , 并注意原有連線結(jié)點(diǎn)一律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子樹。BE CD4. 畫出和下列二叉樹相

13、應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。5. 編寫按層次順序同一層自左至右）遍歷二叉樹的算法（ 或 : 按層次輸出二叉樹中所有結(jié)解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個好辦法。這是一個循環(huán)算法，用 while 語句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(shù)。技巧之處： 當(dāng)根結(jié)點(diǎn)入隊(duì)后，會自然使得左、 右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時又會立即使得它的左右孩子結(jié)點(diǎn)入隊(duì)，以此產(chǎn)生了按層次輸出的效果。法一：level(liuyu*T)/* liuyu *T,*p,*q100;假設(shè) max已知 */int f,r;f=0; r=0;/* 置空隊(duì) */

14、r=(r+1)%max;qr=T;/*根結(jié)點(diǎn)進(jìn)隊(duì) */while(f!=r)/*隊(duì)列不空 */f=(f+1%max);p=qf;/*出隊(duì) */printf(%d,p-data);/* 打印根結(jié)點(diǎn) */if(p-lchild)r=(r+1)%max; qr=p-lchild;/* 若左子樹不空，則左子樹進(jìn)隊(duì) */if(p-rchild)r=(r+1)%max; qr=p-rchild;/* 若右子樹不空，則右子樹進(jìn)隊(duì) */return(0);法二：層序遍歷二叉樹的遞歸算法void LayerOrder(Bitree T)知如圖所示的有向圖，請給出該圖的每個頂點(diǎn)的入鄰接矩陣；鄰接表；/ 出度；4)

15、 逆鄰接表。答案：2. 請對下圖的無向帶權(quán)圖：1) 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；2) 寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。3. 已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4.基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn) vj的路徑( ij )。注意：算法中涉及的圖的基本操作必須在此存儲結(jié)構(gòu)上實(shí)現(xiàn)。int visitedMAXSIZE; irstarc;p;p=p-nextarc)k=p-adjvex;if(!visitedk&exist_path(k

16、,j) return 1;假定對有序表： ( 3，4，5，7， 24，30， 42，54，63， 72，87，95)進(jìn)行折半查找，試回答下列問題：1)畫出描述折半查找過程的判定樹；2)若查找元素 54，需依次與哪些元素比較若查找元素 90，需依次與哪些元素比較4)假定每個元素的查找概率相等，求查找成功時的平均查找長度。解：1)先畫出判定樹如下(注：mid= (1+12)/2=6)953 層共查找 12 2 44 24 54 72(2) 查找元素 54，需依次與 30, 63, 42, 54 等元素比較；(3) 查找元素 90，需依次與 30, 63,87, 95, 72等元素比較；4) 求 A

17、SL 之前，需要統(tǒng)計(jì)每個元素的查找次數(shù)。判定樹的前3=17 次；但最后一層未滿，不能用 8 4，只能用 5 4=20 次， 所以 ASL1/12 (1720) 37/12 2. 設(shè)哈希( Hash)表的地址范圍為 017，哈希函數(shù)為： H( K) K MOD 16 。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：10，24，32，17， 31，30，46，47，40，63，49)造出 Hash 表，試回答下列問題：1) 畫出哈希表的示意圖；2) 若查找關(guān)鍵字 63，需要依次與哪些關(guān)鍵字進(jìn)行比較若查找關(guān)鍵字 60，需要依次與哪些關(guān)鍵字比較4)假定每個關(guān)鍵字的查找概率相等，求查找成功時

18、的平均查找長度。解：1)畫表如下：3)查找 60, 首先要與 H(60)=60%16=12 號單元內(nèi)容比較，但因?yàn)?12 號單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以 應(yīng)當(dāng)只比較這一次即可。4) 對于黑色數(shù)據(jù)元素，各比較 1 次；共 6 次；對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。63” 需要 6 次，“ 49”需要 3 次，“ 40”需要2 次，“46”需要 3 次，“ 47”需要 3 次，所以 ASL=1/11（6233） 17/11= 3. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹。答：1712711162113驗(yàn)算方法：

19、用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，214. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié) 構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。若一棵非解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進(jìn)行判別： 空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn) 的值不大于右子樹的根的值，則是二叉排序樹”劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要 遵循（左小右大）原則） 。若要采用遞歸算法，建議您采用如下的函數(shù)首部：bool BisortTree(BiTree T, BiTr

20、ee&PRE)，其中 PRE為指向當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)的指針?；蛘咧苯哟鎯η膀?qū)的數(shù)值，隨時與當(dāng)前根結(jié)點(diǎn)比較） 一個漂亮的算法設(shè)計(jì)如下：int last=0 , flag=1 ;用某種排序方法對線性表 （ 25, 84，21,47,15,27,68,35,20 ）進(jìn)行排序時，元素序列的變化情況如下：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答：用的是快速排序方法。注

21、意每一趟要振蕩完全部元素才算一個中間結(jié)果。2. 對于整數(shù)序列 100，99，98， 3，2，1，如果將它完全倒過來，分別用冒泡排序和快速排序法，它們的比較次數(shù)和交換次數(shù)各是多少答：冒泡排序的比較和交換次數(shù)將最大，都是1+2+n-1=n(n-1)/2 5099=4545 次快速排序則看按什么數(shù)據(jù)來分子表。如果按 100 來分，則很慘，也會是 n（n-1）/2若按中間數(shù)據(jù) 50或 51來分表，則：第 1 輪能確定 1 個元素，即在 1個子表中比較和交換了n1 個元素； n（ 21-1）第 2 輪能再確定 2 個元素，即在2 個子表中比較和交換了n 3 個元素； n（ 2 -1 ）第 3 輪能再確定 4 個元素，即在4 個子表中比較和交換了n7 個元素； n（ 23-1 ）第 4 輪能再確定 8 個元素，即在8 個子表中比較和交換了n 15 個元素； n （ 2 -1 ）第 7 輪則能全部確定， （因?yàn)?27=128），第 6 輪能再確定 32 個元素，即在