數(shù)據(jù)結(jié)構(gòu)作業(yè)點評2

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)點評2作業(yè)2重點掌握的知識點有：1、棧和隊列是運算受限制的線性表；2、棧的特點：后進先出；3、隊列的特點先進先出。單項選擇題答案如下，供參考：1C 2B 3A 4C 5B 6A 7B 8C 9A 10C 11B 12C 13B 14B 15A 16C 17B 18A 19C 20D 21B 22D 23C 24B 25D 26A 27C 28D 29D 30C 31A 32D 填空題也是強調(diào)了如上那些知識點。所以在做這類作業(yè)題時，重點還是掌握這些知識點。填空題答案如下，供參考：1后進先出2下一個3增1 增14假上溢5 棧是否滿 s-top=MAXSIZE-1 棧頂指針 棧頂對應(yīng)的數(shù)

2、組元素 棧是否空 s-top=-1 棧頂元素 修改棧頂指針6bceda7終止條件 遞歸部分8LU-front=LU-rear9運算符 操作數(shù) ab+c/fde/-10s-next=h; 11h=h-next; 12r-next=s; 13f=f-next; 14字符 15順序存儲方式 鏈?zhǔn)酱鎯Ψ绞?160 空格字符的個數(shù) 17特殊 稀疏 18（） （） 2 19（d,e,f） 20串長度相等且對應(yīng)位置的字符相等 21i(i-1)/2+j 22行下標(biāo)、列下標(biāo)、非零元素值 問答題點評：1鏈棧中為何不設(shè)頭結(jié)點？答：因為鏈棧只在鏈頭插入和刪除結(jié)點，不可能在鏈表中間插入和刪除結(jié)點，算法實現(xiàn)很簡單，所以一

3、般不設(shè)置頭結(jié)點。2利用一個棧，則：（1）如果輸入序列由A，B，C組成，試給出全部可能的輸出序列和不可能的輸出序列。（2）如果輸入序列由A，B，C，D組成，試給出全部可能的輸出序列和不可能的輸出序列。答：（1）棧的操作特點是后進先出，因此輸出序列有：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，B，C組成的數(shù)據(jù)項，除上述五個不同的組合外，還有一個C，A，B組合。但不可能先

4、把C出棧，再把A出棧，（A不在棧頂位置），最后把B出棧，所以序列CAB不可能由輸入序列A，B，C 通過棧得到。（2）按照上述方法，可能的輸出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的輸出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD3用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應(yīng)的S和X操作串是什么？答：應(yīng)是SXSSXSXX。各操作結(jié)果如下：S 1入棧X 1出棧 輸出序列：1S

5、2入棧S 3入棧X 3出棧 輸出序列：13S 4入棧 X 4出棧 輸出序列：134X 2出棧 輸出序列：1342 4有5個元素，其入棧次序為：A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個？答：從題中可知，要使C第一個且D第二個出棧，應(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，CDEBA4寫出以下運算式的后綴算術(shù)運算式 3

6、x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；對應(yīng)的后綴算術(shù)運算式 3x2*x+1x/-5+ AB+C*DEF+/-G+5 簡述廣義表和線性表的區(qū)別和聯(lián)系。答：廣義表是線性表的的推廣，它也是n(n0)個元素a1 ,a2ai an的有限序列，其中ai或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當(dāng)ai都是原子時，廣義表退化成線性表。 程序填空題點評：這類題是通過多閱讀、理解程序和上機實踐，而不是通過背書上的程序。1（1）q-front-next=p-next;（2）free(p);（3）q-rear=q-front

7、綜合題點評：這類題是考查學(xué)生綜合分析問題的能力。在掌握基礎(chǔ)知識，特別是重點知識的基礎(chǔ)上，對習(xí)題的題意分析透徹，然后從問題的切入點進行解題。題1分析如下：出隊序列是e2,e4,e3,e6,e5,e1的過程： e1入棧（棧底到棧頂元素是e1） e2入棧（棧底到棧頂元素是e1,e2） e2出棧（棧底到棧頂元素是e1） e3入棧（棧底到棧頂元素是e1,e3） e4入棧（棧底到棧頂元素是e1,e3,e4） e4出棧（棧底到棧頂元素是e1,e3） e3出棧（棧底到棧頂元素是e1） e5入棧（棧底到棧頂元素是e1,e5） e6入棧（棧底到棧頂元素是e1,e5,e6） e6出棧（棧底到棧頂元素是e1,e5）

8、e5出棧（棧底到棧頂元素是e1） e1出棧（棧底到棧頂元素是空）棧中最多時有3個元素，所以棧S的容量至少是3。題2的算法設(shè)計如下：/*只有一個指針rear的鏈?zhǔn)疥牭幕静僮?/#include typedef char elemtype;struct node /*定義鏈隊列結(jié)點*/elemtype data;struct node *next;typedef struct queue /*定義鏈隊列數(shù)據(jù)類型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊列*/ Q=(struct queue *)malloc(

9、sizeof(struct queue); Q-rear=NULL; void enqueue(LinkQueue *Q,elemtype x) /*入隊算法*/ struct node *s,*p; s=(struct node *)malloc(sizeof(struct node); s-data=x; if (Q-rear=NULL) /*原為空隊時*/ Q-rear=s;s-next=s; else /*原隊不為空時*/ p=Q-rear-next; /*p指向第一個結(jié)點*/Q-rear-next=s; /*將s鏈接到隊尾*/Q-rear=s; /*Q-rear指向隊尾*/s-nex

10、t=p; void delqueue(LinkQueue *Q) /*出隊算法*/ struct node *t; if (Q-rear=NULL) printf(隊列為空!n);return(0); else if (Q-rear-next=Q-rear) /*只有一個結(jié)點時*/ t=Q-rear;Q-rear=NULL; else /*有多個結(jié)點時*/ t=Q-rear-next; /*t指向第一個結(jié)點*/Q-rear-next=t-next; /*引成循環(huán)鏈*/ free(t); elemtype gethead(LinkQueue *Q) /*取隊首元素算法*/ if (Q-rear=NULL) printf(隊列為空!n); else return(Q-rear-next-data); int emptyqueue(LinkQueue *Q) /*判斷隊列是否為空算法*/ if (Q-rear=NULL) return(1); /*為空,則返回true*/ else return(0); /*不