數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄eercise.ppt

1、習(xí)題課,線性表： 1.描述以下概念的區(qū)別： 頭指針、頭結(jié)點、首結(jié)點。 2.順序表中邏輯上相鄰的元素物理位置 相鄰， 單鏈表中邏輯上相鄰的元素物理位置 相鄰。 3.已知P為單鏈表中的非首尾結(jié)點，在P結(jié)點后插入S結(jié)點的語句為： 。,s-next = p-next; p-next = s;,類型定義： 順序表： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList;,單鏈表 typedef struct Lnode Elem

2、Type data; Struct Lnode *next; Lnode, *LinkList; 4. 設(shè)順序表va中的數(shù)據(jù)元素遞增有序，試寫一算法， 將X插入到順序表的適當位置上，以保持該表的有序性。,Status SqInsert(SqList ,i=0; while (L.elemi=i; j-) L.elemj+1 = L.elemj; L.elemi=x; L.length +; return OK; /SqInsert,5.已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點，并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點連在另一個表的最后一

3、個結(jié)點后），假設(shè)指針hc指向連接后的鏈表的頭結(jié)點，并要求算法以盡可能短的時間完成連接運算。請分析你的算法的時間復(fù)雜度。,m,n,Status LinkListJoin(LinkList ha, LinkLis hb, LinkList 算法時間復(fù)雜度分析： 時間：min(m,n) , O(n)階,8. 試寫一算法，對單鏈表實現(xiàn)就地逆置 Status LinkConvert(LinkList ,1,2,3,1,2,p,q,9. 假設(shè)以兩個元素遞增有序排列的線性表A和B分別表示兩個集合（即同一個表中元素各不相同），現(xiàn)要求其并集C，并保持其元素遞增有序，要求使用單鏈表。,1,3,8,2,3,5,q,

4、p,t,s,Status assemjoin(LinkList ha, LinkList hb, LinkList ,case (t-data p-data) q=p; p=p-next; break; case (t-data data) /插入 t-next = p; q-next = t; q = t; t=s; s=s-next; break; /switch /while if (!p) q-next = t; return OK; /assemjoin hb集合和ha集合總比較次數(shù) n次，O(n),棧和隊列 類型定義： 順序棧 #define STACK_INIT_SIZE 100

5、; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack,順序循環(huán)隊列：#define MAXQSIZE 100; typedef struct QElemType *base; int front; int rear; SqQueue; 1.試寫一個算法，識別依次讀入的一個以 為結(jié)束符的字符序列是否形如序列1 SqBiTree bt; 鏈式存儲結(jié)構(gòu) Typedef struct BiTNode TElemType data; struct BiTNod

6、e *lchild, *rchild; BiTNode, *BiTree;,1.一個度為2的樹與一棵二叉樹有何區(qū)別？ 答：二叉樹的度小于等于2，二叉樹的子樹有左右之分，而度為2的樹的子樹不一定是有序的。 判斷以下是否二叉樹,2.一棵含有n個結(jié)點的k叉樹，可能達到的最大深度和最小深度各是多少？ 答：最大n, 最小logkn+1 3.證明：一個滿k叉樹上的葉子結(jié)點數(shù)n0和非葉子結(jié)點數(shù)n1之間滿足以下關(guān)系： n0=（k-1）n1+1 證明：設(shè)樹結(jié)點為n, 則n=n0+n1 因是滿k叉樹, 每個非葉子結(jié)點引 出k個分支，故有k*n1個分支。,除根外，每個分支引出一個結(jié)點，則樹共有k*n1 +1個結(jié)點。

7、 所以 n0+n1=k*n1+1 n0=(k-1)*n1+1 4. 找出滿足下列條件的二叉樹 1）先序和中序遍歷，得到的結(jié)點訪問順序一樣。 2）后序和中序遍歷，得到的結(jié)點訪問順序一樣。 3）先序和后序遍歷，得到的結(jié)點訪問順序一樣。 答：1）無左子樹 2）無右子樹 3）僅一個結(jié)點,5.畫出下列樹對應(yīng)的二叉樹,a,b,c,a,b,c,a,原則：森林的先序/中序遍歷，即對應(yīng)二叉樹的先序/中序 遍歷 先做二叉樹：,cbefdg,6. 畫出和下列已知序列對應(yīng)的森林F: 森林的先序次序訪問序列為：ABCDEFGHIJKL 森林的中序次序訪問序列為：CBEFDGAJIKLH,jiklh,a,jikl,b,e

8、fdg,c,h,b,h,c,d,i,a,ef,g,j,kl,b,h,c,d,i,a,g,j,e,f,k,l,二叉樹,先ABCDEFGHIJKL 中CBEFDGAJIKLH,b,h,c,d,i,g,j,e,f,k,l,a,森林,7.畫出和下列已知序列對應(yīng)的樹T 樹的先根次序訪問序列為：GFKDAIEBCHJ 樹的后根次序訪問序列為：DIAEKFCJHBG 思路：樹的先根為二叉樹的先序 樹的后根為二叉樹的中序 求出二叉樹然后化為樹,8.試利用棧的基本操作寫出先序遍歷的 非遞歸形式的算法 Status PreOrderTraverse (BiTree T, Status (*visit)(TElem

9、Type e) /采用非遞歸方法，遍歷二叉樹 T InitStack(S); Push(S,T); while (!StackEmpty(S) pop(S,p); if (!visit(-data) return ERROR; if (p-rchild) push(p-rchild); if (p-lchild) push(p-lchild); /while return OK; /PreOrderTraverse 考慮一下后序？,9. 編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。 Status PreOrderTraverse(BiTree T, int s) /s為葉子樹目，初值為0 if (T) if (!T-lchild) /PreOrderTraverse,10. 編寫按層次順序（同一層自左至右）遍歷二叉樹的算法 Status LevelTraverse(BiTree T, status (*visit)(TElemType e) InitQueue(Q); if (T) EnQueue(Q,T); while (!Q