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

數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題--劉楚雄--exercise2024/3/11數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise類型定義：順序表：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise單鏈表typedefstructLnode{ElemTypedata;StructLnode*next;}Lnode,*LinkList;4.設(shè)順序表va中的數(shù)據(jù)元素遞增有序，試寫(xiě)一算法，將X插入到順序表的適當(dāng)位置上，以保持該表的有序性。數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseStatusSqInsert(SqList&va,ElemTypex){//線性表va的元素依次和數(shù)據(jù)元素x比較，//找到第一個(gè)比它大的元素后，之后所有//數(shù)據(jù)后移，X元素放入。L=va;if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercisei=0;while(L.elem[i]<x&&i<L.length)i++;if(i==L.length)L.elem[i]=x;//插在最后else{//插在中間for(j=L.length;j>=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;}L.length++;returnOK;}//SqInsert數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise5.已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。試寫(xiě)一算法將這兩個(gè)鏈表連接在一起（即令其中一個(gè)表的首元結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)點(diǎn)后），假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。mn數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseStatusLinkListJoin(LinkListha,LinkLishb,LinkList&hc){//將ha,hb鏈表中長(zhǎng)的一條鏈在短的一條后//面，并放入hc中ifm>n{hc=hb;p=hb;q=ha->next;}else{hc=ha;p=ha;q=hb->next;}while(!p->next)p=p->next;p->next=q;returnok;}算法時(shí)間復(fù)雜度分析：時(shí)間：min(m,n),O(n)階數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise8.試寫(xiě)一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置StatusLinkConvert(LinkList&h){//假設(shè)有頭結(jié)點(diǎn)，h為指向頭結(jié)點(diǎn)的指針,//只需將頭結(jié)點(diǎn)后結(jié)點(diǎn)依次加入新鏈，//加入總是放在新鏈的首元素位置上p=h->next;q=p->next;while(p){p->next=h->next;h->next=p;p=q;q=q->next;returnOK;}

12312pq數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise9.假設(shè)以兩個(gè)元素遞增有序排列的線性表A和B分別表示兩個(gè)集合（即同一個(gè)表中元素各不相同），現(xiàn)要求其并集C，并保持其元素遞增有序，要求使用單鏈表。

138235qpts數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseStatusassemjoin(LinkListha,LinkListhb,LinkList&hc){//集合以ha為基礎(chǔ)，將hb中不同的元素//加入，并保持遞增有序hc=ha;p=ha->next;q=hc;t=hb->next;s=t->next;while(p&&t){switch{case(t->data==p->data){free(t);t=s;s=s->next;q=p;p=p->next;break;}數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercisecase(t->data>p->data){q=p;p=p->next;break;}case(t->data<p->data)//插入{t->next=p;q->next=t;q=t;t=s;s=s->next;break;}}//switch}//whileif(!p)q->next=t;returnOK;}//assemjoinhb集合和ha集合總比較次數(shù)n次，O(n)數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise棧和隊(duì)列類型定義：順序棧#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise順序循環(huán)隊(duì)列：#defineMAXQSIZE100;typedefstruct{QElemType*base;intfront;intrear;}SqQueue;1.試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以@為結(jié)束符的字符序列是否形如‘序列1&序列2‘模式的字符序列。其中序列1和序列2中都不含字符’&‘,且序列2是序列1的逆序列。如‘a(chǎn)+b&b+a’

數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseintsymmetry(){//使用棧，對(duì)讀入的字符在&之前的都//壓棧，之后彈棧并和讀入數(shù)比較，直//到?？詹⑶易x入數(shù)為@是對(duì)稱，否則//為不對(duì)稱。InitStack(s);scanf(ch);while(ch<>“&”){push(s,ch);scanf(ch);}scanf(ch);while(ch<>“@”&&!empey(s)){pop(s,x);if(ch==x)scanf(ch);elsereturn0;}//while數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseif(ch==“@”&&empty(s))return1;elsereturn0;}//symmetry2.在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)輸出受限的雙端循環(huán)隊(duì)列的入列和出列（只允許隊(duì)頭出列）算法。設(shè)每個(gè)元素表示一個(gè)待處理的作業(yè)，元素值表示作業(yè)的預(yù)算時(shí)間。入隊(duì)列采取簡(jiǎn)化的短作業(yè)優(yōu)先原則，若一個(gè)新提交的作業(yè)的預(yù)計(jì)執(zhí)行時(shí)間小于隊(duì)頭和隊(duì)尾作業(yè)的平均時(shí)間，則插入在隊(duì)頭，否則插入在隊(duì)尾。數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseStatusEnQueue(SqQueue&Q,QElemTypee){//插入受限，小于平均時(shí)間插入隊(duì)頭，否則//插入隊(duì)尾if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊(duì)列滿t=Q.base[Q.front]+Q.base[(Q.rear-1+MAXQSIZE)%MAXQSIZE]/2if(e<t){if(Q.front==0)Q.front=MAXQSIZE-1;elseQ.front=Q.front–1;Q.base[Q.front]=e;}else{Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}returnOK;}//EnQueue數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exerciseStatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise樹(shù)和二叉樹(shù)二叉樹(shù)：每個(gè)結(jié)點(diǎn)最多不超過(guò)2子的有向樹(shù)性質(zhì)：1.在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。2.深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。4.n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2n+1。數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise順序存儲(chǔ)結(jié)構(gòu)#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)TypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise1.一個(gè)度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：二叉樹(shù)的度小于等于2，二叉樹(shù)的子樹(shù)有左右之分，而度為2的樹(shù)的子樹(shù)不一定是有序的。判斷以下是否二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise2.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，可能達(dá)到的最大深度和最小深度各是多少？答：最大n,最小logkn+13.證明：一個(gè)滿k叉樹(shù)上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系：n0=（k-1）n1+1證明：設(shè)樹(shù)結(jié)點(diǎn)為n,則n=n0+n1因是滿k叉樹(shù),每個(gè)非葉子結(jié)點(diǎn)引出k個(gè)分支，故有k*n1個(gè)分支。數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise除根外，每個(gè)分支引出一個(gè)結(jié)點(diǎn)，則樹(shù)共有k*n1+1個(gè)結(jié)點(diǎn)。所以n0+n1=k*n1+1n0=(k-1)*n1+14.找出滿足下列條件的二叉樹(shù)1）先序和中序遍歷，得到的結(jié)點(diǎn)訪問(wèn)順序一樣。2）后序和中序遍歷，得到的結(jié)點(diǎn)訪問(wèn)順序一樣。3）先序和后序遍歷，得到的結(jié)點(diǎn)訪問(wèn)順序一樣。答：1）無(wú)左子樹(shù)2）無(wú)右子樹(shù)3）僅一個(gè)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise5.畫(huà)出下列樹(shù)對(duì)應(yīng)的二叉樹(shù)

abcabc數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercisea原則：森林的先序/中序遍歷，即對(duì)應(yīng)二叉樹(shù)的先序/中序遍歷先做二叉樹(shù)：cbefdg6.畫(huà)出和下列已知序列對(duì)應(yīng)的森林F:森林的先序次序訪問(wèn)序列為：ABCDEFGHIJKL森林的中序次序訪問(wèn)序列為：CBEFDGAJIKLHjiklhajiklbefdgch數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercisebhcdiaefgjklbhcdiagjefkl二叉樹(shù)先ABCDEFGHIJKL中CBEFDGAJIKLH數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercisebhcdigjefkla森林7.畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T樹(shù)的先根次序訪問(wèn)序列為：GFKDAIEBCHJ樹(shù)的后根次序訪問(wèn)序列為：DIAEKFCJHBG思路：樹(shù)的先根為二叉樹(shù)的先序樹(shù)的后根為二叉樹(shù)的中序求出二叉樹(shù)然后化為樹(shù)數(shù)據(jù)結(jié)構(gòu)課堂練習(xí)題劉楚雄exercise8.試?yán)脳５幕静僮鲗?xiě)出先序遍歷的非遞歸形式的算法StatusPreOrderTraverse(BiTreeT,