修改后的習(xí)題.doc

數(shù)據(jù)結(jié)構(gòu)習(xí)題習(xí)題一一、選擇題1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的操作對象以及它們之間的（）和運(yùn)算的學(xué)科。 A結(jié)構(gòu) B關(guān)系 C運(yùn)算 D算法2、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。 A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)3、線性表的邏輯順序和存儲(chǔ)順序總是一致的，這種說法（）。 A正確 B不正確 C無法確定 D以上答案都不對4、算法分析的目的是（）。 A找出算法的合理性 B研究算法的輸人與輸出關(guān)系 C分析算法的有效性以求改進(jìn) D分析算法的易懂性二、填空題1、_是信息的載體，是對客觀事物的符號(hào)表示，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)、加工和處理，_是對能夠有效的輸人到計(jì)算機(jī)中并且能夠被計(jì)算機(jī)處理的符號(hào)的總稱。例如，數(shù)學(xué)中所用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串等。 2、數(shù)據(jù)元素是數(shù)據(jù)的_，有些情況下也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。3、_是數(shù)據(jù)不可分割的最小單元，是具有獨(dú)立含義的最小標(biāo)識(shí)單位。例如構(gòu)成一個(gè)數(shù)據(jù)元素的字段、域、屬性等都可稱之為_。 4、簡而言之，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)之間的_，即數(shù)據(jù)的_。 5、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的_。邏輯結(jié)構(gòu)是從_上描述數(shù)據(jù)，它與具體存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的_。 6、數(shù)據(jù)的_指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。_是邏輯結(jié)構(gòu)在計(jì)算機(jī)里的實(shí)現(xiàn)，也稱之為映像。 7、_是指對數(shù)據(jù)施加的操作。它定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個(gè)_。常用的有：查找、排序、插人、刪除、更新等操作。 8、數(shù)據(jù)邏輯結(jié)構(gòu)可以分為四種基本的類型，_結(jié)構(gòu)中的元素除了僅僅只是同屬于一個(gè)_，不存在什么關(guān)系。 9、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中，_中的元素是一種一對一的關(guān)系，這種結(jié)構(gòu)的特征是：若結(jié)構(gòu)是非空集，則有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只能有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 10、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中，_中的元素是一種一對多的關(guān)系。 11、圖型結(jié)構(gòu)或圖狀結(jié)構(gòu)是一種_的關(guān)系。在這種邏輯結(jié)構(gòu)中，所有結(jié)點(diǎn)均可以有多個(gè)前驅(qū)和多個(gè)后繼。 12、有時(shí)也可將樹型結(jié)構(gòu)、集合和圖型結(jié)構(gòu)稱為_，這樣數(shù)據(jù)的邏輯結(jié)構(gòu)就可以分為_和_兩大類。 13、_方式是指邏輯上相鄰的結(jié)點(diǎn)被存儲(chǔ)到物理上也相鄰的存儲(chǔ)單元中。這種存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的數(shù)值，不存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系，結(jié)點(diǎn)之間的關(guān)系是通過存儲(chǔ)單元的相鄰關(guān)系隱含的表示出來的。 14、_方式是種存儲(chǔ)方法，不要求邏輯上相鄰的結(jié)點(diǎn)在物理上也相鄰，即數(shù)據(jù)元素可以存儲(chǔ)在任意的位置上。 15、索引存儲(chǔ)方式又可以分為_和_。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該種索引存儲(chǔ)方式稱為_；若一組結(jié)點(diǎn)在索引表中只對應(yīng)一個(gè)索引項(xiàng)，則索引存儲(chǔ)方式稱為_。在一中，索引項(xiàng)的地址指示結(jié)點(diǎn)所在的位置，而一中，索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始位置。 16、_方式是利用結(jié)點(diǎn)關(guān)鍵字的值直接計(jì)算出該結(jié)點(diǎn)存儲(chǔ)單元地址，然后將結(jié)點(diǎn)按某種方式存人該地址的一種方法。 17、所謂算法（Algorithm）是對特定問題求解方法和步驟的一種描述，它是指令的一組_，其中每個(gè)指令表示一個(gè)或多個(gè)操作。18、算法的_性是指算法必須能夠在執(zhí)行有限個(gè)步驟之后結(jié)束，并且每個(gè)步驟都必須在有窮的時(shí)間內(nèi)完成。 19、算法的_性是指算法中的每一個(gè)步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到_的輸出結(jié)果。 20、算法的_性又稱為算法的能行性，是指算法中描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行_次來實(shí)現(xiàn)，即算法的_應(yīng)該能夠被計(jì)算機(jī)執(zhí)行。 21、判斷一個(gè)算法的好壞主要以下幾個(gè)標(biāo)準(zhǔn)：_、_、_、_。 22、算法分析是對一種算法所消耗的計(jì)算機(jī)資源的估算，其中包括計(jì)算機(jī)_的長短和_的大小。 23、空間復(fù)雜度（SPace ComPlexity）也是度量一個(gè)算法好壞的標(biāo)準(zhǔn)，它所描述的是算法在運(yùn)行過程中所占用_的大小。三、判斷題 1、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（） 2、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（） 3、算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言描述，則算法實(shí)際上就是程序了。（） 4、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。（）5、數(shù)據(jù)的邏輯結(jié)構(gòu)是指各元素之間的邏輯關(guān)系，是用戶根據(jù)需要而建立的。（） 6、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。（） 7、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲(chǔ)形式。（） 8、具有存取任一元素的時(shí)間相等這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。（）四、綜合題 1、用大O形式表示下面算法的時(shí)間復(fù)雜度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； 2、寫出下面算法的時(shí)間復(fù)雜度： i0； s=0； while(sn） i+; s+=i; 3、寫出以下算法的時(shí)間復(fù)雜度： 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;4、寫出下面算法的時(shí)間復(fù)雜度：i=1;while（in） i=i*3;5、求下面函數(shù)中各條語句的頻度和算法的時(shí)間復(fù)雜度：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）；習(xí)題二一、選擇題 1在一個(gè)長度為n的順序表中刪除第i個(gè)元素（0i=0）個(gè)數(shù)據(jù)元素的_。其中n為數(shù)據(jù)元素的個(gè)數(shù)，定義為線性表的_。當(dāng)n為零時(shí)的表稱為_。4所謂順序表（Sequential LISt）是線性表的_，它是將線性表中的結(jié)點(diǎn)按其_依次存放在內(nèi)存中一組連續(xù)的存儲(chǔ)單元中，使線性表中相鄰的結(jié)點(diǎn)存放在_的存儲(chǔ)單元中。5單鏈表不要求邏輯上相鄰的存儲(chǔ)單元在物理上也一定要相鄰。它是分配一些_的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素，這些存儲(chǔ)單元可以分散在內(nèi)存中的_的位置上，它們在物理上可以是一片連續(xù)的存儲(chǔ)單元，也可以是_的。因此在表示線性表這種數(shù)據(jù)結(jié)構(gòu)時(shí)，必須在存儲(chǔ)線性表元素的同時(shí)，也存儲(chǔ)線性表的。6線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)結(jié)點(diǎn)（Node）需要包括兩個(gè)部分：一部分用來存放元素的數(shù)據(jù)信息，稱為結(jié)點(diǎn)的_；另一部分用來存放元素的指向直接后繼元素的指針(即直接后繼元素的地址信息)，稱為_或_。7線性鏈表的邏輯關(guān)系是通過每個(gè)結(jié)點(diǎn)指針域中的指針來表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種_存儲(chǔ)結(jié)構(gòu)，又稱為_。8如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中的頭結(jié)點(diǎn)的地址值，這樣就構(gòu)成了_。9為了能夠快速地查找到線性表元素的直接前驅(qū)，可在每一個(gè)元素的結(jié)點(diǎn)中再增加一個(gè)指向其前驅(qū)的指針域，這樣就構(gòu)成了_。10雙向鏈表某結(jié)點(diǎn)的指針P，它所指向結(jié)點(diǎn)的后繼的前驅(qū)與前驅(qū)的后繼都是p_。11在單鏈表中，刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是_。12在雙循環(huán)鏈表中，刪除指針P所指結(jié)點(diǎn)的語句序列是P-prior-nextp-next及_。13單鏈表是_的鏈接存儲(chǔ)表示。14可以使用_表示樹形結(jié)構(gòu)。15向一個(gè)長度為n的向量的第i個(gè)元素(lin+1）之前插人一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。16刪除一個(gè)長度為n的向量的第i個(gè)元素（lin）時(shí)，需向前移動(dòng)_個(gè)元素。17在單鏈表中，在指針P所指結(jié)點(diǎn)的后面插人一個(gè)結(jié)點(diǎn)S的語句序列是_。18在雙循環(huán)鏈表中，在指針P所指結(jié)點(diǎn)前插人指針S所指的結(jié)點(diǎn)，需執(zhí)行語句_。19取出廣義表A（x，（a，b，c，d）中原子c的函數(shù)是_。20在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插人一個(gè)新結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度為_。21寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件_。22線性表、棧和隊(duì)列都是_結(jié)構(gòu)。23向棧中插人元素的操作是先移動(dòng)棧_針，再存人元素。三、判斷題1線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（）2在具有頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指向鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。( ) 3順序存儲(chǔ)的線性表不可以隨機(jī)存取。（） 4單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。（）5順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除運(yùn)算所移動(dòng)元素的個(gè)數(shù)與該元素的位置無關(guān)。() 6順序存儲(chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu)。（）7線性表的長度是線性表所占用的存儲(chǔ)空間的大小。（）8雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。（）9線性表的惟一存儲(chǔ)形式是鏈表。（）四、綜合題1編寫一個(gè)將帶頭結(jié)點(diǎn)單鏈表逆置的算法。2ha和hb分別是兩個(gè)按升序排列的、帶頭結(jié)點(diǎn)的單鏈表的頭指針，設(shè)計(jì)一個(gè)算法，把這兩個(gè)單鏈表合并成一個(gè)按升序排列的單鏈表，并用hC指向它的頭結(jié)點(diǎn)。3有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，頭指針為head，編寫一個(gè)算法countlist（）計(jì)算所有數(shù)據(jù)域?yàn)閄的結(jié)點(diǎn)的個(gè)數(shù)（不包括頭結(jié)點(diǎn)）。4在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，頭指針為head，它的數(shù)據(jù)域的類型為整型，而且按由小到大的順序排列，編寫一個(gè)算法insertxlist（），在該鏈表中插人值為x的元素，并使該鏈表仍然有序。5在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，head為其頭指針，p指向鏈表中的某一個(gè)結(jié)點(diǎn)，編寫算法swapinlist（），實(shí)現(xiàn)p所指向的結(jié)點(diǎn)和p的后繼結(jié)點(diǎn)相互交換。6有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，所有元素值以非遞減有序排列，head為其頭指針，編寫算法deldylist（）將該鏈表中多余元素值相同的結(jié)點(diǎn)刪除。7在帶頭結(jié)點(diǎn)的單鏈表中，設(shè)計(jì)算法dellistmaxmin，刪除所有數(shù)據(jù)域大于min，而小于max的元素。8設(shè)計(jì)一個(gè)將雙鏈表逆置的算法invertdblinklist（），其中頭指針為head，結(jié)點(diǎn)數(shù)據(jù)域?yàn)閐ata，兩個(gè)指針域分別為prior和next。習(xí)題三一、選擇題 l一個(gè)棧的序列是：a，b，c，d，e，則棧的不可能輸出的序列是（）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一個(gè)棧的輸人序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第k個(gè)輸出元素是（ ）。 Ak Bn-k-1 Cn-k+1 D不確定3判定一個(gè)棧S（最多有n個(gè)元素）為空的條件是（ ）。 AS-top！0 BS-top= =0 CS-top!=n DS-top= =n4判定一個(gè)棧S（最多有n個(gè)元素）為滿的條件是（ ）。 AS-top!=0 BS-top= =0 CS-top!=n DS-top= =n5向一個(gè)棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（ ）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一個(gè)帶頭結(jié)點(diǎn)、棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（ ）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一個(gè)隊(duì)列Q（最多有n個(gè)元素）為空的條件是（ ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一個(gè)隊(duì)列Q（最多有n個(gè)元素）為滿的條件是（）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一個(gè)循環(huán)隊(duì)列Q（最多有n個(gè)元素）為空的條件是（ ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n10判定一個(gè)循環(huán)隊(duì)列Q（最多有n個(gè)元素）為滿的條件是（ ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)*S的操作是（ ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，刪除一個(gè)結(jié)點(diǎn)的操作是（ ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13棧與隊(duì)列都是（ ）。 A鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu) C限制存取點(diǎn)的線性結(jié)構(gòu) D限制存取點(diǎn)的非線性結(jié)構(gòu) 14若進(jìn)棧序列為l，2，3，4，則（ ）不可能是一個(gè)出棧序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫人該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。 A堆棧 B隊(duì)列 C數(shù)組 D線性表二、填空回1棧（stack）是限定在_一端進(jìn)行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為_，而另一端稱為_。不含元素的棧稱為_。2在棧的運(yùn)算中，棧的插人操作稱為_或_，棧的刪除操作稱為_或_。3根據(jù)棧的定義，每一次進(jìn)棧的元素都在原_之上，并成為新的_；每一次出棧的元素總是當(dāng)前的_，因此最后進(jìn)棧的元素總是_，所以棧也稱為_線性表，簡稱為_表。4棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有_和_兩種存儲(chǔ)結(jié)構(gòu)，分別稱為_和_。5當(dāng)棧滿的時(shí)候，再進(jìn)行人棧操作就會(huì)產(chǎn)生_，這種情況的溢出稱為_；當(dāng)?？盏臅r(shí)候，如果再進(jìn)行出棧操作，也會(huì)_，這種情況下的溢出稱為_。6棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為_，是一種_。7人們?nèi)粘Ｓ?jì)算用到的表達(dá)式都被稱為_，這是由于這種算術(shù)表達(dá)式的運(yùn)算符被置于兩個(gè)操作數(shù)中間。8計(jì)算機(jī)中通常使用_，這是一種將運(yùn)算符置于兩個(gè)操作數(shù)后面的算術(shù)表達(dá)式。這種表達(dá)式是由波蘭科學(xué)家謝維奇提出的，因此又稱為_。9隊(duì)列（Queue）也是一種_，但它與棧不同，隊(duì)列中所有的插人均限定在表的一端進(jìn)行，而所有的刪除則限定在表的另一端進(jìn)行。允許插人的一端稱為_，允許刪除的一端稱為_。10隊(duì)列的特點(diǎn)是_，因此隊(duì)列又被稱為_的線性表，或稱為_表。11隊(duì)列的_又稱為_，是用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的元素。12由于隊(duì)列中的元素經(jīng)常變化，對于隊(duì)列的刪除和插人分別在隊(duì)頭和隊(duì)尾進(jìn)行，因此需要設(shè)置兩個(gè)指針分別指向_和_，這兩個(gè)指針又稱為_和_。13循環(huán)順序隊(duì)列（Circular Sequence Queue）經(jīng)常簡稱為_，它是將存儲(chǔ)順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的一個(gè)環(huán)，即將隊(duì)首和隊(duì)尾元素連接起來形成一個(gè)環(huán)形表。首尾相連的狀態(tài)是通過數(shù)學(xué)上的_來實(shí)現(xiàn)的。14在算法或程序中，當(dāng)一個(gè)函數(shù)直接調(diào)用自己或通過一系列語句間接調(diào)用自己的時(shí)候，則稱這個(gè)函數(shù)為，也稱為_。函數(shù)直接調(diào)用自己，則稱為_；當(dāng)一個(gè)函數(shù)通過另一個(gè)函數(shù)來調(diào)用自己則稱為_。15在循環(huán)隊(duì)列中規(guī)定：當(dāng)Q-rear= =Q-front的時(shí)候循環(huán)隊(duì)列為_， 當(dāng)（Q-rear+1）MAXSIZEfront的時(shí)候循環(huán)隊(duì)列為_。16用鏈表方式表示的隊(duì)列稱為_。17已知棧的輸人序列為1，2，3，n，輸出序列為a1，a2，an，符合a2= =n的輸出序列共有_。18一個(gè)棧的輸人序列是12345，則棧的輸出序列為43512是_（填是否可能）。19一個(gè)棧的輸人序列是12345，則棧的輸出序列為12345是_（填是否可能）。20設(shè)sq1maxsize為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，則作入棧操作的條件是_。21設(shè)sq1maxsize為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，如果把棧頂元素彈出并送到X中，則需執(zhí)行語句_。22棧的特性是_。23對棧進(jìn)行退棧時(shí)的操作是先取出元素，后移動(dòng)_。24設(shè)s1max為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂位置，棧為滿的條件是_。25設(shè)鏈棧的棧頂指針為top，則棧非空的條件是_。26已知循環(huán)隊(duì)列用數(shù)組data1.n存儲(chǔ)元素值，用f，r分別作為頭尾指針， 則當(dāng)前元素個(gè)數(shù)為_。27在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_位置。（前一個(gè)或后一個(gè)）28隊(duì)列中允許進(jìn)行刪除的一端稱為_。29鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表（1n），尾指針指向該單鏈表的第_個(gè)元素。30設(shè)雙向鏈表鏈列為lq，lq的頭指針為lq.Front，尾指針為lq.Rear，則隊(duì)列為空的條件是_。31從循環(huán)隊(duì)列中刪除一個(gè)元素，其操作是先取出一個(gè)元素，后移動(dòng)_。32隊(duì)列中允許進(jìn)行插入的一端稱為_。三、判斷題1棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。（ ）2不同的人棧和出棧組合可能得到相同輸出序列。（ ）3消除遞歸一定要用棧。（ ）4循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)。（ ）5循環(huán)隊(duì)列不會(huì)產(chǎn)生溢出。（ ）6循環(huán)隊(duì)列滿的時(shí)候rear= =front。（ ）7在對鏈隊(duì)列（帶頭結(jié)點(diǎn)）做出隊(duì)操作時(shí)不會(huì)改變front指針的值。（）四、綜合題1設(shè)有4個(gè)元素A、B、C和D進(jìn)棧，給出它們所有可能的出棧秩序。2輸入n個(gè)10以內(nèi)的數(shù)，每輸入k（0=k=9），就把它插人到第k號(hào)隊(duì)列中。最后把10個(gè)隊(duì)列中的非空隊(duì)列按隊(duì)列序號(hào)以從小到大的順序串接成一條鏈，并輸出該鏈中的所有元素。3假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列，該隊(duì)列只使用一個(gè)尾指針rear，其相應(yīng)的存儲(chǔ)結(jié)構(gòu)和基本操作算法如下：(l) 初始化隊(duì)列 initqueue (Q)：建立一個(gè)新的空隊(duì)列 Q。(2) 人隊(duì)列enqueue (Q，x)：將元素 x插人到隊(duì)列 Q中。(3) 出隊(duì)列delqueue (Q)：從隊(duì)列Q中退出一個(gè)元素。(4) 取隊(duì)首元素gethead (Q)：返回當(dāng)前隊(duì)首元素。(5) 判斷隊(duì)列是否為空：emptyqueue (Q)。(6) 顯示隊(duì)列中元素：dispqueue (Q)。4“回文”是指一個(gè)字符串從頭讀到尾和從尾讀到頭都一樣。假設(shè)字符串是從輸人設(shè)備一次一個(gè)字節(jié)的讀人，并且讀到字符“”的時(shí)候表示結(jié)束。請用棧和隊(duì)列編寫一個(gè)算法判斷一個(gè)字符串是否回文。5假設(shè)表達(dá)式中有三種括號(hào)：圓括號(hào)“（）”、方括號(hào)“ ”和花括號(hào)“ ”用C語言編寫程序判斷讀人的表達(dá)式中不同括號(hào)是否正確配對，假定讀人的表達(dá)式以”#”結(jié)束。6用C語言編寫背包問題的算法。背包問題的描述是：假設(shè)有n件質(zhì)量分別為w1，w2，wn的物品和一個(gè)最多能裝載總質(zhì)量是T的背包，問能否從這n件物品中選擇若干件物品裝人背包，并且使被選物品的總質(zhì)量