數據結構課程課后習題答案-資料下載頁

　　

【正文】 的映射關系：bi,j在一維數組A中的下標為i～n+j，bj,i在一維數組A中的下標為jn+i。對應的算法如下：void trans(ElemType A[], int n){ int i, j。 ElemType tmp。 for (i=0。in。i++) for (j=0。ji。j++) { tmp=A[i*n+j]。 A[i*n+j]=A[j*n+i]。 A[j*n+i]=tmp。 }}（3）如果矩陣A中存在這樣的一個元素A[i][j]滿足條件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。設計一個算法求出mn的矩陣A的所有馬鞍點。解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，則該元素A[i][j]便是馬鞍點，找出所有這樣的元素，即找到了所有馬鞍點。實現程序如下：include define m 3define n 4void minmax(int A[m][n]){ int i, j, have=0。 int min[m], max[n]。 for (i=0。im。i++) //計算出每行的最小值元素，放入min[m]之中 { min[i]=A[i][0]。 for (j=1。jn。j++) if (A[i][j]min[i]) min[i]=A[i][j]。 } for (j=0。jn。j++) //計算出每列的最大值元素，放入max[1..n]之中 { max[j]=A[0][j]。 for (i=1。im。i++) if (A[i][j]max[j]) max[j]=A[i][j]。 } for (i=0。im。i++) //判定是否為馬鞍點 for (j=0。jn。j++) if (min[i]==max[j]) { printf((%d, %d):%d\n, i, j, A[i][j])。//顯示馬鞍點 have=1。 } if (!have) printf(沒有鞍點\n)。}void main(){ int a[m][n]。 int i, j。 for (i=0。im。i++) for (j=0。jn。j++) scanf(%d, amp。a[i][j])。 minmax(a)。 //調用minmax()找馬鞍點}（4）設有二維數組A[m][n]，其元素為整數，每行每列都按從小到大有序，試給出一個算法求數組中值為x的元素的行號i和列號j。設值x在A中存在，要求比較次數不多于m+n次。解：由于算法要求比較次數不多于m+n次，因此不能按行掃描數組的每一元素，否則比較次數在最壞情況下可達mn次。根據該數組的特點可從矩陣右上角按副對角線方向向左下角查找，算法如下：int find(int a[M][N],int x,int m,int n){ int i=0,j=n1,flag=0。 while (im amp。amp。 j=0) if (a[i][j]!=x) if (a[i][j]x) j。 //修改列號 else i++。 //修改行號 else //a[i][j]==x { flag=1。 break。 } return flag。}上機實驗題5采用一維動態數組模擬二維數組的操作，即將一個二維數組的元素存放在一個一維數組中，一維數組的空間根據二維數組的大小動態分配。設計一個算法實現兩個二維數組的相加運算。并用相關數據進行測試。解：對應的程序如下：include include typedef int ElemType。typedef struct{ ElemType *p。 //存放二維數組元素 int m,n。 //存放二維數組的行數和列數} Mat2。void InitMat(Mat2 amp。M,int x,int y) //初始化二維數組M{ =x。 =y。 =(ElemType *)malloc(x*y*sizeof(ElemType))。}int Setij(Mat2 amp。M,int i,int j,ElemType x) //置二維數組(i,j)位置值為x{ int k。 if (i=0 amp。amp。 i amp。amp。 j=0 amp。amp。 j) { k=i*+j。 [k]=x。 return 1。 //成功賦值返回1 } else return 0。 //參數錯誤返回0}int Getij(Mat2 M,int i,int j,ElemType amp。x) //取二維數組(i,j)位置值并賦給x{ int k。 if (i=0 amp。amp。 i amp。amp。 j=0 amp。amp。 j) { k=i*+j。 x=[k]。 return 1。 //成功取值返回1 } else return 0。 //參數錯誤返回0}void DispMat(Mat2 M) //輸出二維數組{ int i,j,k。 for (i=0。i。i++) { for (j=0。j。j++) { k=i*+j。 printf(%3d,[k])。 } printf(\n)。 }}int AddMat(Mat2 A,Mat2 B,Mat2 amp。C) //兩個二維數組相加運算{ int i,j。 ElemType x,y。 if (!= || !=) return 0。 //兩數組行列數不同返回0 for (i=0。i。i++) for (j=0。j。j++) { Getij(A,i,j,x)。 Getij(B,i,j,y)。 Setij(C,i,j,x+y)。 } return 1。}void DestroyMat(Mat2 M) //銷毀二維數組M{ free()。}void main(){ Mat2 A,B,C。 InitMat(A,2,3)。 Setij(A,0,0,1)。 Setij(A,0,1,1)。 Setij(A,0,2,1)。 Setij(A,1,0,1)。 Setij(A,1,1,1)。 Setij(A,1,2,1)。 printf(A:\n)。 DispMat(A)。 InitMat(B,2,3)。 Setij(B,0,0,2)。 Setij(B,0,1,2)。 Setij(B,0,2,2)。 Setij(B,1,0,2)。 Setij(B,1,1,2)。 Setij(B,1,2,2)。 printf(B:\n)。 DispMat(B)。 InitMat(C,2,3)。 printf(C=A+B\n)。 AddMat(A,B,C)。 printf(C:\n)。 DispMat(C)。 DestroyMat(A)。 DestroyMat(B)。 DestroyMat(C)。}練習題61. 單項選擇題（1）樹最適合用來表示（ ）。 答：C（2）樹是結點的有限集合，它（ ① ）根結點，記為T。其余的結點分成為m（m≥0）個（ ② ）的集合TT…、Tm，每個集合又都是樹，此時結點T稱為Ti的雙親結點，Ti稱為T的子樹（1≤i≤m）。一個結點的子樹個數為該結點的（ ③ ）。①： ②： ③： （或度） 答：①A ②A ③C（3）二叉樹（ ① ）。在完全的二叉樹中，若一個結點沒有（ ② ），則它必定是葉子結點。每棵樹都能唯一地轉換成與它對應的二叉樹，由一棵樹轉換成的二叉樹中，一個結點N的左孩子是N在原樹里對應結點的（ ③ ），而N的右孩子是它在原樹里對應結點的（ ④ ）。①： ②： ③～④： 答：①B ②A ③A ④C（4）把一棵樹轉換為二叉樹后，這棵二叉樹的形態是（ ）。 ，但根結點都沒有左孩子 ，但根結點都沒有右孩子答：A（5）假定一棵度為3的樹中結點數為50，則其最小高度為（ ）。A. 3 B. 4 C. 5 D. 6答：C（6）若一棵度為7的樹有7個度為2的結點，有6個度為3的結點，有5個度為4的結點，有4個度為5的結點，有3個度為6的結點，有2個度為7的結點，該樹一共有（ ）個葉子結點。A. 35 B. 28 C. 77 D. 78答：D（7）下列敘述中，正確的是（ ）。 D. 二叉樹中每個結點的度均為2答：B（8）深度為5的二叉樹至多有（ ）個結點。A. 16 B. 32 答：C（9）對一個滿二叉樹，有m個葉子結點，n個結點，深度為h，則（ ）。A. n=h+m B. h+m=2n C. m=h1 D. n=2h1答：D（10）完全二叉樹中，編號為i的結點的層次是（ ）。A. i B. 233。log2i249。 C. 235。log2(i+1) D. C. 235。log2i+1答：D（11）一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（ ）。A. 250 B. 501 C. 254 D. 505 答：B（12）一棵有124個葉結點的完全二叉樹，最多有（ ）個結點。A. 247 B. 248 C. 249 D. 250答：B（13）若唯一確定一棵二叉樹，只需要知道該二叉樹的（ ）。A. 先序序列 B. 中序序列C. 中序和后序序列 D. 先序和后序序列答：C（14）一棵二叉樹的先序遍歷序列和其后序遍歷序列正好相反，則該二叉樹一定是（ ）。 答：D（15）一棵二叉樹的后序遍歷序列為D、A、B、E、C，中序遍歷序列為D、E、B、A、C，則先序遍歷序列為（ ）。、C、B、E、D 、E、C、B、A、E、A、B、C 、E、D、B、A答：D（16）在線索化二叉樹中，p所指結點沒有左子樹的充要條件是（ ）。lchild == NULL ltag==1ltag==1且plchild==NULL 答：B（17）根據使用頻率為5個字符設計的哈夫曼編碼不可能是（ ）。A. 111,110,10,01,00 B. 000,001,010,011,1C. 100,11,10,1,0 D. 001,000,01,11,10答：C2. 填空題（1）由3個結點所構成的二叉樹有（ ）種形態。答：5（2）一棵深度為6的滿二叉樹有（ ① ）個分支結點和（ ② ）個葉子結點。答：①31 ②32（3）設一棵完全二叉樹有700個結點，則共有（ ）個葉子結點。答：350（4）設一棵完全二叉樹具有1000個結點，則此完全二叉樹有（ ① ）個葉子結點，有（ ② ）個度為2的結點，有（ ③ ）個單分支結點。答：①500 ②499 ③1（5）一棵二叉樹的第i（i≥1）層最多有（ ）個結點。答：2i1（6）深度為h的完全二叉樹至少有（ ① ）個結點，至多有（ ② ）個結點，若按自上而下，從左到右次序給結點編號（從1開始），則編號最小的葉子結點的編號是（ ③ ）。答：① 2h1 ② 2h1 ③ 2h1。（7）對含有n個結點的二叉樹進行中序遞歸遍歷，該算法平均空間復雜度為（ ）。答：O(n)（8）用5個權值{3,2,4,5,1}構造的哈夫曼（Huffman）樹的帶權路徑長度是（ ）。答：333. 簡答題（1）一棵度為2的樹與一棵二叉樹有何區別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的，即在一般樹中若某結點只有一個孩子，就無需區分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。另外，一棵度為2的樹至少有3個結點，而一棵二叉樹的結點個數可以為0。（2）試求含有n0個葉子結點的完全二叉樹的總結點數。答：由二叉樹的性質可知，n2=n01，在完全二叉樹中，度為1的結點數n1至多為1，所以具有n0個葉子結點的完全二叉樹結點數是n0+(n01)+1=2n0或2n01。（3）某二叉樹的結點數據采用順序存儲結構如下：1234567891011121314151617181920EAFDHCGIB① 畫出該二叉樹；② 寫出結點值為D的雙親結點及左、右子樹。③ 將此二叉樹還原為森林。答：① 。 一棵二叉樹 二叉樹還原成的森林② 結點值為D的結點的雙親結點為結點值為A的結點，其左子樹為以C為根結點的子樹，其右子樹為空。③ 。（4）證明完全二叉樹的每棵子樹也都是完全二叉樹。證明：讓T是一棵完全二叉樹，S是它的一棵子樹。由子樹定義可知，S是由T中某個結點及其所有子孫