數(shù)據(jù)結構習題.doc

數(shù)據(jù)結構習題習題一一、選擇題1、數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象以及它們之間的（B）和運算的學科。 A結構 B關系 C運算 D算法2、在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（C）。 A動態(tài)結構和靜態(tài)結構 B緊湊結構和非緊湊結構 C線性結構和非線性結構 D邏輯結構和存儲結構3、線性表的邏輯順序和存儲順序總是一致的，這種說法（B）。 A正確 B不正確 C無法確定 D以上答案都不對4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的輸人與輸出關系 C分析算法的有效性以求改進 D分析算法的易懂性二、填空題1、數(shù)據(jù) 是信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、存儲、加工和處理，數(shù)據(jù) 是對能夠有效的輸人到計算機中并且能夠被計算機處理的符號的總稱。例如，數(shù)學中所用到的整數(shù)和實數(shù)，文本編輯所用到的字符串等。 2、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有些情況下也稱為元素、結點、頂點、記錄等。3、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單元，是具有獨立含義的最小標識單位。例如構成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之為_數(shù)據(jù)項。 4、簡而言之，數(shù)據(jù)結構是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。 5、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)之間的邏輯關系。邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與具體存儲無關，是獨立于計算機的。因此邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。 6、數(shù)據(jù)的存儲結構指數(shù)據(jù)元素及其關系在計算機存儲器內的表示。存儲結構是邏輯結構在計算機里的實現(xiàn)，也稱之為映像。 7、數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作。它定義在數(shù)據(jù)的邏輯結構之上，每種邏輯結構都有一個數(shù)據(jù)的運算。常用的有：查找、排序、插人、刪除、更新等操作。 8、數(shù)據(jù)邏輯結構可以分為四種基本的類型，集合結構中的元素除了僅僅只是同屬于一個集合_，不存在什么關系。 9、數(shù)據(jù)邏輯結構的四種基本類型中，線性結構_中的元素是一種一對一的關系，這種結構的特征是：若結構是非空集，則有且只有一個開始結點和一個終端結點，并且所有結點最多只能有一個直接前驅和一個直接后繼。 10、數(shù)據(jù)邏輯結構的四種基本類型中，樹形結構中的元素是一種一對多的關系。 11、圖型結構或圖狀結構是一種多對多的關系。在這種邏輯結構中，所有結點均可以有多個前驅和多個后繼。 12、有時也可將樹型結構、集合和圖型結構稱為非線性結構，這樣數(shù)據(jù)的邏輯結構就可以分為線性結構和非線性結構兩大類。 13、順序存儲方式是指邏輯上相鄰的結點被存儲到物理上也相鄰的存儲單元中。這種存儲結構只存儲結點的數(shù)值，不存儲結點之間的關系，結點之間的關系是通過存儲單元的相鄰關系隱含的表示出來的。 14、鏈接存儲方式是種存儲方法，不要求邏輯上相鄰的結點在物理上也相鄰，即數(shù)據(jù)元素可以存儲在任意的位置上。 15、索引存儲方式又可以分為稠密索引和稀疏索引。若每個結點在索引表中都有一個索引項，則該種索引存儲方式稱為稠密索引_；若一組結點在索引表中只對應一個索引項，則索引存儲方式稱為稀疏索引。在稠密索引中，索引項的地址指示結點所在的位置，而稀疏索引中，索引項的地址指示一組結點的起始位置。 16、散列存儲方式是利用結點關鍵字的值直接計算出該結點存儲單元地址，然后將結點按某種方式存人該地址的一種方法。 17、所謂算法（Algorithm）是對特定問題求解方法和步驟的一種描述，它是指令的一組有限序列，其中每個指令表示一個或多個操作。18、算法的有窮_性是指算法必須能夠在執(zhí)行有限個步驟之后結束，并且每個步驟都必須在有窮的時間內完成。 19、算法的確定性是指算法中的每一個步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到相同的輸出結果。 20、算法的可行性又稱為算法的能行性，是指算法中描述的操作是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限_次來實現(xiàn)，即算法的具體實現(xiàn)應該能夠被計算機執(zhí)行。 21、判斷一個算法的好壞主要以下幾個標準：正確性，可讀性_、健壯性、效率。 22、算法分析是對一種算法所消耗的計算機資源的估算，其中包括計算機運行時間的長短和所占據(jù)空間的大小。 23、空間復雜度（SPace ComPlexity）也是度量一個算法好壞的標準，它所描述的是算法在運行過程中所占用存儲空間的大小。三、判斷題 1、順序存儲方式只能用于存儲線性結構。（）樹型結構也可以用順序方式進行存儲。 2、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位。 3、算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言描述，則算法實際上就是程序了。（）算法用各種計算機語言描述表現(xiàn)為一個程序，但是不等于程序，程序邏輯不一定能滿足有窮性。 4、數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合。（對）5、數(shù)據(jù)的邏輯結構是指各元素之間的邏輯關系，是用戶根據(jù)需要而建立的。（對） 6、數(shù)據(jù)結構、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結構、結點、數(shù)據(jù)域。（對） 7、數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機中實際的存儲形式。（對） 8、具有存取任一元素的時間相等這一特點的存儲結構稱為隨機存取結構。（對）四、綜合題 1、用大O形式表示下面算法的時間復雜度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； O(mn)。 2、寫出下面算法的時間復雜度： i0； s=0； while(sn） i+; s+=i; O() 3、寫出以下算法的時間復雜度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k） cijaik*bkj; O(mnt)。4、寫出下面算法的時間復雜度：i=1;while（in） i=i*3; log3(n)。5、求下面函數(shù)中各條語句的頻度和算法的時間復雜度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）； O() 習題二一、選擇題 1在一個長度為n的順序表中刪除第i個元素（0i=0）個數(shù)據(jù)元素的_有限序列。其中n為數(shù)據(jù)元素的個數(shù)，定義為線性表的長度。當n為零時的表稱為空表。4所謂順序表（Sequential LISt）是線性表的順序存儲結構，它是將線性表中的結點按其邏輯順序依次存放在內存中一組連續(xù)的存儲單元中，使線性表中相鄰的結點存放在地址相鄰的存儲單元中。5單鏈表不要求邏輯上相鄰的存儲單元在物理上也一定要相鄰。它是分配一些任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，這些存儲單元可以分散在內存中的任意的位置上，它們在物理上可以是一片連續(xù)的存儲單元，也可以是不連續(xù)的。因此在表示線性表這種數(shù)據(jù)結構時，必須在存儲線性表元素的同時，也存儲線性表的邏輯關系。6線性表的鏈式存儲結構的每一個結點（Node）需要包括兩個部分：一部分用來存放元素的數(shù)據(jù)信息，稱為結點的數(shù)據(jù)域；另一部分用來存放元素的指向直接后繼元素的指針(即直接后繼元素的地址信息)，稱為指針域或鏈域。7線性鏈表的邏輯關系是通過每個結點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種非順序存儲結構，又稱為非順序映像。8如果將單鏈表最后一個結點的指針域改為存放鏈表中的頭結點的地址值，這樣就構成了循環(huán)鏈表。9為了能夠快速地查找到線性表元素的直接前驅，可在每一個元素的結點中再增加一個指向其前驅的指針域，這樣就構成了雙向鏈表。10雙向鏈表某結點的指針P，它所指向結點的后繼的前驅與前驅的后繼都是p所指向的結點本身。11在單鏈表中，刪除指針P所指結點的后繼結點的語句是P-next=p-next-next_。12在雙循環(huán)鏈表中，刪除指針P所指結點的語句序列是P-prior-nextp-next及P-next-prior=P-prior _。13單鏈表是線性表的鏈接存儲表示。14可以使用雙鏈表表示樹形結構。15向一個長度為n的向量的第i個元素(lin+1）之前插人一個元素時，需向后移動n-i+1個元素。16刪除一個長度為n的向量的第i個元素（lin）時，需向前移動n-i個元素。17在單鏈表中，在指針P所指結點的后面插人一個結點S的語句序列是S-next=P-next; P-next=S18在雙循環(huán)鏈表中，在指針P所指結點前插人指針S所指的結點，需執(zhí)行語句p-prior-next=S;s-prior=p-prior;s-next=p;p-prior=s;19取出廣義表A（x，（a，b，c，d）中原子c的函數(shù)是head(tail(tail(head(tail(head(A)。20在一個具有n個結點的有序單鏈表中插人一個新結點并使之仍然有序的時間復雜度為O(n)。21寫出帶頭結點的雙向循環(huán)鏈表L為空表的條件(L=L-Next) & (L=L-Prior)。22線性表、棧和隊列都是線性_結構。23向棧中插人元素的操作是先移動棧頂針，再存人元素。三、判斷題1線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。（錯）2在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的第一個數(shù)據(jù)結點。(錯) 3順序存儲的線性表不可以隨機存取。（錯） 4單鏈表不是一種隨機存儲結構。（對）5順序存儲結構線性表的插入和刪除運算所移動元素的個數(shù)與該元素的位置無關。(錯) 6順序存儲結構是動態(tài)存儲結構，鏈式存儲結構是靜態(tài)存儲結構。（錯）7線性表的長度是線性表所占用的存儲空間的大小。（錯）8雙循環(huán)鏈表中，任意一結點的后繼指針均指向其邏輯后繼。（錯）9線性表的惟一存儲形式是鏈表。（錯）四、綜合題1編寫一個將帶頭結點單鏈表逆置的算法。void reverse_list( linklist * head )/*逆置帶頭結點的單鏈表*/linklist *s, *p;p=head-next;/*p指向線性表的第一個元素*/head-next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p-next;s-next=head-next;head-next=s; /*將s結點插入逆表*/ /*reverse_list*/2ha和hb分別是兩個按升序排列的、帶頭結點的單鏈表的頭指針，設計一個算法，把這兩個單鏈表合并成一個按升序排列的單鏈表，并用hC指向它的頭結點。linklist *combine_list( linklist *ha, linklist *hb )/*ha, hb分別是兩個按升序排列的,帶有頭結點的單鏈表的頭指針，設計一個算法，把這兩個單鏈表合并成一個按升序排列的單鏈表,并用hc指向它的頭結點*/linklist *hc, *pa, *pb, *pc, *p, *q, *r;hc=(linklist *)malloc(sizeof(linklist); /*建立hc頭結點*/p=hc;pa=ha-next;free(ha); /*釋放ha頭結點*/pb=hb-next;free(hb);/*釋放hb頭結點*/while (pa!=NULL & pb!=NULL )q=(linklist *)malloc (sizeof (linklist); /*產(chǎn)生新結點*/if (pb-datadata)q-data=pb-data;pb=pb-next;elseq-data=pa-data;pa=pa-next;if (pa-data=pb-data) /*將相同的元素刪除*/r=pb;pb=pb-next;free(r);p-next=q; /*將結點鏈入c鏈表*/p=q;while(pa!=NULL)/*a鏈表非空*/q=(linklist *)malloc (sizeof (linklist);q-data=pa-data;pa=pa-next;p-next=q;p=q;while(pb!=NULL) /*b鏈表非空*/q=(linklist *)malloc (sizeof (linklist);q-data=pb-data;pb=pb-next;p-next=q;p=q;p-next=NULL;return(hc); /*返回*/3有一個帶頭結點的單鏈表，頭指針為head，編寫一個算法countlist（）計算所有數(shù)據(jù)域為X的結點的個數(shù)（不包括頭結點）。int count_list(linklist *head )/*在帶頭結點的單鏈表中計算所有數(shù)據(jù)域為x的結點的個數(shù)*/linklist *p;int n;p=head-next; /*p指向鏈表的第一個結點*/n=0;while (p!=NULL)if (p-data=x)n+;p=p-next;return(n);/*返回結點個數(shù)*/ /*count_list*/4在一個帶頭結點的單鏈表中，頭指針為head，它的數(shù)據(jù)域的類型為整型，而且按由小到大的順序排列，編寫一個算法insertxlist（），在該鏈表中插人值為x的元素，并使該鏈表仍然有序linklist *insertx_list(linklist *head, int x)/*在帶頭結點的單鏈表中插入值為x的元素，使該鏈表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*建立數(shù)據(jù)域為x的結點*/s-data=x;s-next=NULL;if (head-next=NULL | xnext-data ) /*若單鏈表為空或x小于鏈表第一個結點的數(shù)據(jù)域*/s-next=head-next;head-next=s;elseq=head-next;p=q-next;while( p != NULL & xp-data )q=p;p=p-next;s-next=p;q-next=s; /*if*/ /*insertx_list*/。5在一個帶頭結點的單鏈表中，head為其頭指針，p指向鏈表中的某一個結點，編寫算法swapinlist（），實現(xiàn)p所指向的結點和p的后繼結點相互交換。linklist *swapin_list(linklist *head, linklist *p)/*在帶頭結點的單鏈表中，實現(xiàn)p所指向的結點和p的后繼結點相互交換*/linklist *q, *r, *s;q=p-next; /*q為p的后繼*/if (q !=NULL) /*若p有后繼結點*/if (p=head) /*若p指向頭結點*/head=head-next;s=head-next;head-next=p;p-next=s;else /*p不指向頭結點*/r=head; /*定位p所指向結點的前驅*/while (r-next != p)r=r-next;r-next=q; /*交換p和q所指向的結點*/p-next=q-next;q-next=p;return(head);else /*p不存在后繼*/return(NULL);/*swapin_list*/6有一個帶頭結點的單鏈表，所有元素值以非遞減有序排列，head為其頭指針，編寫算法deldylist（）將linklist *deldy_list(linklist *head)/*在帶頭結點的非遞減有序單鏈表，將該鏈表中多余的元素值相同的結點刪除*/linklist *q;if (head-next!= NULL)/*判斷鏈表是否為空*/p=head-next;while (p-next != NULL )if ( p-data != p-next-data )p=p-next;else q=p-next;/*q指向p的后繼*/p-next=q-next; /*刪除q所指向的結點*/free(q); /*釋放結點空間*/ /*while*/ /*if*/return(head); /*deldy_list*/該鏈表中多余元素值相同的結點刪除。7在帶頭結點的單鏈表中，設計算法dellistmaxmin，刪除所有數(shù)據(jù)域大于min，而小于max的元素。linklist *dellist_maxmin(linklist *head, int min, int max )linklist *p, *q;q=head;p=head-next;while(p!=NULL) /*結點不空*/if (p-datadata=max) /*不滿足刪除條件*/q=p;p=p-next;else/*滿足刪除條件*/q-next=p-next;free(p);q=q-next; /*dellist_maxmin*/8設計一個將雙鏈表逆置的算法invertdblinklist（），其中頭指針為head，結點數(shù)據(jù)域為data，兩個指針域分別為prior和next。將雙鏈表逆置的算法invert_dblinklist的算法如下所示：void invert_dblinklist( linklist *head )/*將head指向的雙鏈表逆置*/dblinklist *p, *q;p=head;doq=p-next;p-next=p-prior;p-prior=q;p=q;while( p!=head ) /*invert_dblinklist*/習題三一、選擇題 l一個棧的序列是：a，b，c，d，e，則棧的不可能輸出的序列是（C）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一個棧的輸人序列是1，2，3，n，輸出序列的第一個元素是n，則第k個輸出元素是（ C）。 Ak Bn-k-1 Cn-k+1 D不確定3判定一個棧S（最多有n個元素）為空的條件是（ B ）。 AS-top！0 BS-top= =0 CS-top!=n DS-top= =n4判定一個棧S（最多有n個元素）為滿的條件是（D ）。 AS-top!=0 BS-top= =0 CS-top!=n DS-top= =n5向一個棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執(zhí)行語句（ B ）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一個帶頭結點、棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執(zhí)行語句（ C ）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一個隊列Q（最多有n個元素）為空的條件是（ C ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一個隊列Q（最多有n個元素）為滿的條件是（A）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一個循環(huán)隊列Q（最多有n個元素）為空的條件是（ A ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n10判定一個循環(huán)隊列Q（最多有n個元素）為滿的條件是（ C ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，則插入一個結點*S的操作是（ C ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結點的操作是（ A ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13棧與隊列都是（ C ）。 A鏈式存儲的線性結構 B鏈式存儲的非線性結構 C限制存取點的線性結構 D限制存取點的非線性結構 14若進棧序列為l，2，3，4，則（ C ）不可能是一個出棧序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫人該緩沖區(qū)，而打印機則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應該是一個（ B ）結構。 A堆棧 B隊列 C數(shù)組 D線性表二、填空回1棧（stack）是限定在表尾一端進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為棧頂，而另一端稱為棧底。不含元素的棧稱為空棧。2在棧的運算中，棧的插人操作稱為進?；蛉霔５膭h除操作稱為退?；虺鰲?。3根據(jù)棧的定義，每一次進棧的元素都在原棧頂元素之上，并成為新的棧頂元素；每一次出棧的元素總是當前的棧頂元素，因此最后進棧的元素總是最先出棧，所以棧也稱為后進先出線性表，簡稱為LIFO表。4棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有順序和鏈式_兩種存儲結構，分別稱為、順序棧_和_鏈棧。5當棧滿的時候，再進行人棧操作就會產(chǎn)生溢出，這種情況的溢出稱為上溢_；當棧空的時候，如果再進行出棧操作，也會溢出，這種情況下的溢出稱為下溢。6棧的鏈式存儲結構簡稱為鏈棧，是一種_特殊的單鏈表。7人們日常計算用到的表達式都被稱為中綴表達式，這是由于這種算術表達式的運算符被置于兩個操作數(shù)中間。8計算機中通常使用后綴表達式，這是一種將運算符置于兩個操作數(shù)后面的算術表達式。這種表達式是由波蘭科學家謝維奇提出的，因此又稱為波蘭式。9隊列（Queue）也是一種特殊的線性表_，但它與棧不同，隊列中所有的插人均限定在表的一端進行，而所有的刪除則限定在表的另一端進行。允許插人的一端稱為隊尾，允許刪除的一端稱為隊頭。10隊列的特點是先進先出，因此隊列又被稱為先進先出的線性表，或稱為FIFO表。11隊列的順序存儲結構又稱為順序隊列，是用一組地址連續(xù)的存儲單元依次存放隊列中的元素。12由于隊列中的元素經(jīng)常變化，對于隊列的刪除和插人分別在隊頭和隊尾進行，因此需要設置兩個指針分別指向隊頭元素和隊尾元素，這兩個指針又稱為隊頭指針和隊尾指針。13循環(huán)順序隊列（Circular Sequence Queue）經(jīng)常簡稱為循環(huán)隊列，它是將存儲順序隊列的存儲區(qū)域看成是一個首尾相連的一個環(huán)，即將隊首和隊尾元素連接起來形成一個環(huán)形表。首尾相連的狀態(tài)是通過數(shù)學上的、取模運算來實現(xiàn)的。14在算法或程序中，當一個函數(shù)直接調用自己或通過一系列語句間接調用自己的時候，則稱這個函數(shù)為遞歸函數(shù)，也稱為自調用函數(shù)。函數(shù)直接調用自己，則稱為直接遞歸調用；當一個函數(shù)通過另一個函數(shù)來調用自己則稱為間接遞歸調用。15在循環(huán)隊列中規(guī)定：當Q-rear= =Q-front的時候循環(huán)隊列為空_， 當（Q-rear+1）MAXSIZEfront的時候循環(huán)隊列為滿。16用鏈表方式表示的隊列稱為鏈隊列。17已知棧的輸人序列為1，2，3，n，輸出序列為a1，a2，an，符合a2= =n的輸出序列共有n-1。18一個棧的輸人序列是12345，則棧的輸出序列為43512是不可能的（填是否可能）。19一個棧的輸人序列是12345，則棧的輸出序列為12345是可能的（填是否可能）。20設sq1maxsize為一個順序存儲的棧，變量top指示棧頂元素的位置，則作入棧操作的條件是top!=maxsize。21設sq1maxsize為一個順序存儲的棧，變量top指示棧頂元素的位置，如果把棧頂元素彈出并送到X中，則需執(zhí)行語句x=sqtop; top=top-1。22棧的特性是先進后出。23對棧進行退棧時的操作是先取出元素，后移動棧頂指針。24設s1max為一個順序存儲的棧，變量top指示棧頂位置，棧為滿的條件是top=max。25設鏈棧的棧頂指針為top，則棧非空的條件是top!=nil。26已知循環(huán)隊列用數(shù)組data1.n存儲元素值，用f，r分別作為頭尾指針， 則當前元素個數(shù)為(n+r-f)mod n。27在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個位置。（前一個或后一個）28隊列中允許進行刪除的一端稱為隊首。29鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表（1n），尾指針指向該單鏈表的第n個元素。30設雙向鏈表鏈列為lq，lq的頭指針為lq.Front，尾指針為lq.Rear，則隊列為空的條件是lq-front=lq-rear。31從循環(huán)隊列中刪除一個元素，其操作是先取出一個元素，后移動棧頂指針。32隊列中允許進行插入的一端稱為隊尾。三、判斷題1棧和隊列都是限制存取點的線性結構。對 ）2不同的人棧和出棧組合可能得到相同輸出序列。錯誤：不同的入棧和出棧組合得到不同輸出序列。 ）3消除遞歸一定要用棧。（錯誤：某些情況如尾遞歸可以轉換為遞推的形式。）4循環(huán)隊列是順序存儲結構。（正確） 5循環(huán)隊列不會產(chǎn)生溢出。（錯誤：循環(huán)隊列不會產(chǎn)生假溢出 ）6循環(huán)隊列滿的時候rear= =front。（ 錯誤 ）7在對鏈隊列（帶頭結點）做出隊操作時不會改變front指針的值。（正確）四、綜合題1設有4個元素A、B、C和D進棧，給出它們所有可能的出棧秩序。A、B、C、DA、B、D、CA、C、B、DA、C、D、BA、D、C、BB、A、C、DB、A、D、CB、C、A、DB、C、D、AB、D、C、AC、B、A、DC、B、D、AC、D、B、AD、C、B、A2輸入n個10以內的數(shù)，每輸入k（0=k=9），就把它插人到第k號隊列中。最后把10個隊列中的非空隊列按隊列序號以從小到大的順序串接成一條鏈，并輸出該鏈中的所有元素。#include #define MAX 10#define N 100 struct node int data; struct node *next;struct hnode struct node *link; queueMAX;main() int AN,n,i,first=1; struct node *p,*s,*head; printf(數(shù)值個數(shù)n:); scanf(%d,&n); for (i=0;iMAX;i+) /*隊列初始化*/ queuei.link=NULL; for (i=0;in;i+)/*用戶輸入數(shù)據(jù)*/doprintf(第%d個數(shù):,i+1);scanf(%d,&Ai); while (Ai9); for(i=0;idata=Ai;s-next=NULL;if (queueAi.link=NULL) /*是相應隊列的第一個結點*/ queueAi.link=s; else /*不是相應隊列的第一個結點*/ p=queueAi.link;while (p-next!=NULL) p=p-next; /*p指向該鏈表的最后一個結點*/p-next=s; head=(struct node *)malloc (sizeof (struct node); /*建立新的總鏈表頭結點*/ head-next=NULL; for (i=0;inext = queuei.link;first=0;p=head;while (p-next!=NULL) p=p-next; /*p指向最后結點*/ else /*不是鏈入總鏈表的第一個鏈表*/ p-next=queuei.link; p=queuei.link; while (p-next!=NULL) p=p-next; printf(n顯示所有元素:n); if (head-next!=NULL) /*p指向總鏈表的首結點*/ p=head-next;while (p!=NULL)printf(%d ,p-data);p=p-next;3假設用循環(huán)單鏈表實現(xiàn)循環(huán)隊列，該隊列只使用一個尾指針rear，其相應的存儲結構和基本操作算法如下：(l) 初始化隊列 initqueue (Q)：建立一個新的空隊列 Q。(2) 人隊列enqueue (Q，x)：將元素 x插人到隊列 Q中。(3) 出隊列delqueue (Q)：從隊列Q中退出一個元素。(4) 取隊首元素gethead (Q)：返回當前隊首元素。(5) 判斷隊列是否為空：emptyqueue (Q)。(6) 顯示隊列中元素：dispqueue (Q)。/*只有一個指針rear的鏈式隊的基本操作*/#include typedef char elemtype;struct node /*定義鏈隊列結點*/elemtype data;struct node *next;typedef struct queue /*定義鏈隊列數(shù)據(jù)類型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊列*/ Q=(struct queue *)malloc(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指向第一個結點*/Q-rear-next=s; /*將s鏈接到隊尾*/Q-rear=s; /*Q-rear指向隊尾*/s-next=p; void delqueue(LinkQueue *Q) /*出隊算法*/ struct node *t; if (Q-rear=NULL) printf(隊列為空!n);return(0); else if (Q-rear-next=Q-rear) /*只有一個結點時*/ t=Q-rear;Q-rear=NULL; else /*有多個結點時*/ t