數(shù)據(jù)結(jié)構(gòu)作業(yè)點(diǎn)評(píng)2

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)點(diǎn)評(píng)2作業(yè)2重點(diǎn)掌握的知識(shí)點(diǎn)有：1、棧和隊(duì)列是運(yùn)算受限制的線性表；2、棧的特點(diǎn)：后進(jìn)先出；3、隊(duì)列的特點(diǎn)先進(jìn)先出。單項(xiàng)選擇題答案如下，供參考：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 填空題也是強(qiáng)調(diào)了如上那些知識(shí)點(diǎn)。所以在做這類(lèi)作業(yè)題時(shí)，重點(diǎn)還是掌握這些知識(shí)點(diǎn)。填空題答案如下，供參考：1后進(jìn)先出2下一個(gè)3增1 增14假上溢5 棧是否滿 s-top=MAXSIZE-1 棧頂指針 棧頂對(duì)應(yīng)的數(shù)

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

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

4、把C出棧，再把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，CABD3用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到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個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個(gè)？答：從題中可知，要使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，CDEBA4寫(xiě)出以下運(yùn)算式的后綴算術(shù)運(yùn)算式 3

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

7、綜合題點(diǎn)評(píng)：這類(lèi)題是考查學(xué)生綜合分析問(wèn)題的能力。在掌握基礎(chǔ)知識(shí)，特別是重點(diǎn)知識(shí)的基礎(chǔ)上，對(duì)習(xí)題的題意分析透徹，然后從問(wèn)題的切入點(diǎn)進(jìn)行解題。題1分析如下：出隊(duì)序列是e2,e4,e3,e6,e5,e1的過(guò)程： 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出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，所以棧S的容量至少是3。題2的算法設(shè)計(jì)如下：/*只有一個(gè)指針rear的鏈?zhǔn)疥?duì)的基本操作*/#include typedef char elemtype;struct node /*定義鏈隊(duì)列結(jié)點(diǎn)*/elemtype data;struct node *next;typedef struct queue /*定義鏈隊(duì)列數(shù)據(jù)類(lèi)型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊(duì)列*/ Q=(struct queue *)malloc(

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

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