數(shù)據(jù)結(jié)構(gòu) 形成性考核答案(本)作業(yè)1-4

作業(yè)1機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?？梢?jiàn)，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示。盡管因采用的同，但可通過(guò)結(jié)點(diǎn)的內(nèi)部信息，找到其相鄰的結(jié)點(diǎn)，從而保留了邏輯結(jié)構(gòu)的特點(diǎn)。采用的存儲(chǔ)結(jié)構(gòu)不同，對(duì)數(shù)據(jù)的操作在靈活性，算法復(fù)雜度等方面差別較大。答：順序結(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的要求內(nèi)存中存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素2）由于難以估計(jì)間，往往使存儲(chǔ)空間不能得到充分利用3）表的容量難以擴(kuò)充。放表示結(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入和刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。刪除操作，則采用鏈表。答：數(shù)據(jù)元素的結(jié)點(diǎn)；頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。答：帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別主要體現(xiàn)在其結(jié)構(gòu)上和算法操作上。結(jié)點(diǎn)。是其他結(jié)點(diǎn)，算法步驟都相同。不帶頭結(jié)點(diǎn)結(jié)點(diǎn)還是其他結(jié)點(diǎn)。因?yàn)閮煞N情況的算法步驟不同。（1）p->data=i（2）p->next=NULL（3）q->next=p（4）q=p（1）head=p（2）q=p（3）p->next=NULL（4）p->next=q->next（5）q->next=p（1）p=q->next（2）q->next=p->next1--線性表?xiàng)Ｊ欠駶Ms->top=MAXSIZE-1棧頂指針棧頂對(duì)應(yīng)的數(shù)19d,e,f性表的任何位置進(jìn)行插入和刪除操作。線性表可以在線性表的任何位置進(jìn)行插入和刪除操作。一般不設(shè)置頭結(jié)點(diǎn)。答：（1）棧的操作特點(diǎn)是后進(jìn)先出，因此輸出序列有：A入，A出，B入，B出，C入C出，輸出序列為ABC。A入，A出，B入，C入，C出，B出，輸出序列為ACB。A入，B入，B出，A出，C入，C出，輸出序列為BAC。A入，B入，B出，C入，C出，A出，輸出序列為BCA。A入，B入，C入，C出，B出，A出，輸出序列為CBA。棧，再把A出棧A不在棧頂位置最后把B出棧，所以序列CAB不可能由輸入序列A，B，C通過(guò)棧得到。（2）按照上述方法，可能的輸出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的輸出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD答：應(yīng)是SXSSXSXX。各操作結(jié)果如下：X1出棧輸出序列：1答：從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧。之后可以有以下幾種情況：（1）B出棧，A出棧，E入棧，E出棧，輸出序列為：CDBAE。（2）B出棧，E入棧，E出棧，A出棧，輸出序列為CDBEA。（3）E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA答：廣義表是線性表的的推廣，它也是n(n>0)個(gè)元素a1,a2…ai…an的有限序列，其中ai或者是原子或者是一個(gè)廣義表。所以，廣義表是一種遞歸特殊情況，當(dāng)ai都是原子時(shí)，廣義表退化成線性表。算法設(shè)計(jì)如下：{};{{}voidenqueue(LinkQueue*Q,elemtypex){if(Q->rear==NULL)/*原為空隊(duì)時(shí)*/{}else/{p=Q->rear->next;/*p指向第一個(gè)結(jié)點(diǎn)*/Q->rear=s;/*Q->rea}}{if(Q->rear==NULL){printf("隊(duì)列為空!\n");}elseif(Q->rear->next==Q->rear)/*只有一個(gè)結(jié)點(diǎn)時(shí)*/{}{t=Q->rear->next;/*t指向第一個(gè)結(jié)Q->rear->next=t->next;/*}}elemtypegethead(LinkQue{if(Q->rear==NULL)printf("隊(duì)列為空!\n");return(Q->rear->next->dat}intemptyqueue(LinkQueue*Q){if(Q->rear==NULL)return(1);/*為空,則返回tr}voiddispqueue(LinkQueue*Q){printf("隊(duì)列元素:");{p=p->next;}printf("%c\n",p->data);}2--棧、隊(duì)列、遞歸程序設(shè)計(jì)2n歷的結(jié)果。（1）二叉樹(shù)圖形表示如下：AACBCBDFEDFEHIG\JHIG\JKKMLML□由□得單支結(jié)點(diǎn)數(shù)為1□對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一個(gè)樹(shù)葉結(jié)點(diǎn)，即序號(hào)為n的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn)即為最后一個(gè)非終端結(jié)點(diǎn)，（1）先序序列和中序序列相同的二叉樹(shù)為空樹(shù)或任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹(shù)（2）中序和后序序列相同的二叉樹(shù)為空樹(shù)或任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹(shù)（3）先序和后序序列相同的二叉樹(shù)為空樹(shù)或僅有一個(gè)（1）哈夫曼樹(shù)如圖B-4所示。0010o1030200 ADAD23（3）每個(gè)字符的哈夫曼編碼為：A:100,B:11,C:1010,D:000,E:0010,F:10110,G:10111,H:0011,I:（1）深度優(yōu)先遍歷：v1,v2,v3,v8,v5,v7,v4,v6廣度優(yōu)先遍歷：v1,v2,v4,v6,(2)G的拓?fù)湫蛄袨椋簐1,v2,v4,v6,v5,v5,v□g1的圖示和圖g1的鄰接表如下圖所示。v1v1v4v2v4v2v5v53v3□圖G的鄰接矩陣如下圖所示：010100110024^145^45^123^23^24^145^45^123^23^v1v2v3v4v5defineNULL0typedefstructbtnode{{/*復(fù)制一棵二叉樹(shù)*/if(p!=NULL){t=(bitnode*)malloc(sizeof(bitnot->lchild=CopyTree(p->lchilt->rchild=CopyTree(p->rchilintBTreeLeafCount(structBTreeNo{elseif(BT->left==NULL&&BT->right==NULL)return1;elsereturnBTreeLeafCount(BT->left)+BTreeLeafCount(BT-}3--棧、隊(duì)列、遞歸程序設(shè)計(jì)各趟的結(jié)果。答：時(shí)各趟的結(jié)果。答：列作升序排列時(shí)的每一趟結(jié)果。（2）以二叉樹(shù)描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5答：\\77777(3)平均查找長(zhǎng)度=（1*1+2*2+3（1）52244663377（1）□j>=0（2）□a[j]（3）□j--（4）□temp（1）j<=n-1（2）i<=n-j（4）a[i+1]=temp（5）□當(dāng)某趟冒泡中沒(méi)有出現(xiàn)交換則已排好序結(jié)束循環(huán)。折半查找算法如下；intBinary_Search(NODEa[],intn,intk)/*在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-1*/{{elseif(a[mid].key<k)}}/*查找成功，返回查找到的記錄的下標(biāo)*//*取后半查找區(qū)間*//*取前半查找區(qū)間*//*查找失敗*/2.編寫順序查找算法