最新數(shù)據(jù)結(jié)構(gòu)形成性考核答案作業(yè)1-4-在線瀏覽
2024-08-08 04:51本頁面
【正文】 1．簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計與實現(xiàn)？答：若用結(jié)點表示某個數(shù)據(jù)元素，則結(jié)點與結(jié)點之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)?？梢姡瑪?shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系，而數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機中的存儲表示。采用的存儲結(jié)構(gòu)不同，對數(shù)據(jù)的操作在靈活性，算法復(fù)雜度等方面差別較大。答：順序結(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。優(yōu)點：插入和刪除元素時很方便，使用靈活。3．什么情況下用順序表比鏈表好？答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動態(tài)操作。4．解釋頭結(jié)點、第一個結(jié)點（或稱首元結(jié)點）、頭指針這三個概念的區(qū)別？答：頭結(jié)點是在鏈表的開始結(jié)點之前附加的一個結(jié)點；第一個結(jié)點（或稱首元結(jié)點）是鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點；頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。 答：帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表的區(qū)別主要體現(xiàn)在其結(jié)構(gòu)上和算法操作上。在操作上，帶頭結(jié)點的單鏈表的初始化為申請一個頭結(jié)點。不帶頭結(jié)點的單鏈表，其算法步驟要分別考慮插入或刪除的位置是第一個結(jié)點還是其他結(jié)點。四、程序填空題1．（1）pdata=i（2）pnext=NULL（3）qnext=p（4）q=p2．（1）head=p（2）q=p（3）pnext=NULL（4）pnext=qnext（5）qnext=p3．（1）p=qnext（2）qnext=pnext五、完成：實驗1――線性表根據(jù)實驗要求（見教材P201202）認(rèn)真完成本實驗，并提交實驗報告。 11．h=hnext。 13．f=fnext。答：棧是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。4．利用一個棧，則：（1）如果輸入序列由A，B，C組成，試給出全部可能的輸出序列和不可能的輸出序列。答：（1）棧的操作特點是后進先出，因此輸出序列有：A入，A出，B入，B出，C入C出，輸出序列為ABC。A入，B入，B出，A出，C入，C出，輸出序列為BAC。A入，B入，C入，C出，B出，A出，輸出序列為CBA。但不可能先把C出棧，再把A出棧，（A不在棧頂位置），最后把B出棧，所以序列CAB不可能由輸入序列A，B，C 通過棧得到。不可能的輸出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5．用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應(yīng)的S和X操作串是什么？答：應(yīng)是SXSSXSXX。之后可以有以下幾種情況：（1）B出棧，A出棧，E入棧，E出棧，輸出序列為：CDBAE。（3）E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA7．寫出以下運算式的后綴算術(shù)運算式⑴ 3x2+x1/x+5⑵ (A+B)*CD/(E+F)+G答；對應(yīng)的后綴算術(shù)運算式⑴ 3x2^*x+1x/5+⑵ AB+C*DEF+/G+8． 簡述廣義表和線性表的區(qū)別和聯(lián)系。所以，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當(dāng)ai都是原子時，廣義表退化成線性表。（2）free(p)。2．算法設(shè)計如下：/*只有一個指針rear的鏈?zhǔn)疥牭幕静僮?/include typedef char elemtype。 struct node *next。typedef struct queue /*定義鏈隊列數(shù)據(jù)類型*/{ struct node *rear。void initqueue(LinkQueue *Q)/*初始化隊列*/{ Q=(struct queue *)malloc(sizeof(struct queue))。} void enqueue(LinkQueue *Q,elemtype x) /*入隊算法*/{ struct node *s,*p。 sdata=x。 snext=s。 /*p指向第一個結(jié)點*/ Qrearnext=s。 /*Qrear指向隊尾*/ snext=p。 if (Qrear==NULL) { printf(隊列為空!\n)。 } else if (Qrearnext==Qrear) /*只有一個結(jié)點時*/ { t=Qrear。 } else /*有多個結(jié)點時*/ { t=Qrearnext。 /*引成循環(huán)鏈*/ } free(t)。 else return(Qrearnextdata)。 /*為空,則返回true*/ else return(0)。 printf(隊列元素:)。 p=pnext。}六、完成：實驗2――棧、隊列、遞歸程序設(shè)計根據(jù)實驗要求（見教材P203）認(rèn)真完成本實驗，并提交實驗報告。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結(jié)點，左
試題試卷相關(guān)推薦
鄂ICP備17016276號-1