專升本數(shù)據(jù)結(jié)構(gòu)考前必看

1、1名詞解釋：棧和隊(duì)列棧是只允許在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出（LIFO）表。隊(duì)列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的元素最先離開（刪除），故隊(duì)列也常稱先進(jìn)先出（FIFO）表。2.假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出

2、判別給定序列是否合法的一般規(guī)則。（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說明?！敬鸢浮浚?）通常有兩條規(guī)則。第一是給定序列中S的個(gè)數(shù)和X的個(gè)數(shù)相等；第二是從給定序列的開始，到給定序列中的任一位置，S的個(gè)數(shù)要大于或等于X的個(gè)數(shù)。（2）可以得到相同的輸出元素序列。例如，輸入元素為A，B，C，則兩個(gè)輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對(duì)于合法序列ABC，我們使用本題約定的SXSX

3、SX操作序列；對(duì)于合法序列BAC，我們使用SSXXSX操作序列。3.如果輸入序列為123456，試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列：435612和135426，請(qǐng)說明為什么不能或如何才能得到?！敬鸢浮枯斎胄蛄袨?23456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1

4、；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。4.簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件?！敬鸢浮吭O(shè)順序存儲(chǔ)隊(duì)列用一維數(shù)組q[m]表示，其中m為隊(duì)列中元素個(gè)數(shù)，隊(duì)列中元素在向量中的下標(biāo)從0到m1。設(shè)隊(duì)頭指針為front，隊(duì)尾指針是rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。當(dāng)front等于

5、1時(shí)隊(duì)空，rear等于m1時(shí)為隊(duì)滿。由于隊(duì)列的性質(zhì)（“刪除”在隊(duì)頭而“插入”在隊(duì)尾），所以當(dāng)隊(duì)尾指針rear等于m1時(shí)，若front不等于1，則隊(duì)列中仍有空閑單元，所以隊(duì)列并不是真滿。這時(shí)若再有入隊(duì)操作，會(huì)造成假“溢出”。其解決辦法有二，一是將隊(duì)列元素向前“平移”（占用0至rearfront1）；二是將隊(duì)列看成首尾相連，即循環(huán)隊(duì)列（0..m1）。在循環(huán)隊(duì)列下，仍定義front=rear時(shí)為隊(duì)空，而判斷隊(duì)滿則用兩種辦法，一是用“犧牲一個(gè)單

6、元”，即rear1=front（準(zhǔn)確記是（rear1）%m=front，m是隊(duì)列容量）時(shí)為隊(duì)滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時(shí)導(dǎo)致front=rear為隊(duì)空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊(duì)滿。5.若以1、2、3、4作為雙端隊(duì)列的輸入序列，試分別求出以下條件的輸出序列：（1）能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列；（2）能由輸出受限的雙端隊(duì)列

7、得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列；（3）既不能由輸入受限雙端隊(duì)列得到，也不能由輸出受限雙端隊(duì)列得到的輸出序列?！敬鸢浮浚?）4132（2）4213（3）42311描述以下概念的區(qū)別：空格串與空串?！敬鸢浮靠崭袷且粋€(gè)字符，其II碼值是32。空格串是由空格組成的串，其長(zhǎng)度等于空格的個(gè)數(shù)?？沾遣缓魏巫址拇?，即空串的長(zhǎng)度是零。2設(shè)S1，S2為串，請(qǐng)給出使S1S2=S2S1成立的所有可能的條件（為連接符）?！敬鸢浮浚?）s1和

8、s2均為空串；（2）兩串之一為空串；（3）兩串串值相等（即兩串長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相同）。（4）兩串中一個(gè)串長(zhǎng)是另一個(gè)串長(zhǎng)（包括串長(zhǎng)為1僅有一個(gè)字符的情況）的數(shù)倍，而且長(zhǎng)串就好象是由數(shù)個(gè)短串經(jīng)過連接操作得到的。5.4應(yīng)用題1設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個(gè)元素占一個(gè)空間，問A[3][3]存放在什么位置？【答案】先序遍歷是“根左右”，中序遍歷是“左根右”，后序遍

9、歷是“左右根”。三種遍歷中只是訪問“根”結(jié)點(diǎn)的時(shí)機(jī)不同，對(duì)左右子樹均是按左右順序來遍歷的，因此所有葉子都按相同的相對(duì)位置出現(xiàn)。5試找出滿足下列條件的二叉樹：1）先序序列與后序序列相同；2）中序序列與后序序列相同；3）先序序列與中序序列相同；4）中序序列與層次序列相同；【答案】先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根”，根據(jù)以上原則，解答如下：1）若先序序列與后序序

10、列相同，則或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹。2）若中序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹。（3）若先序序列與中序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。（4）若中序序列與層次遍歷序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹6已知一棵二叉樹的中序序列和后序序列分別為GLDHBEIACJFK和LGHDIEBJKFCA（1）給出這棵二叉樹；（2）轉(zhuǎn)換為對(duì)應(yīng)的森林?！敬鸢浮?一棵非空

11、二叉樹其先序序列和后序序列正好相反，畫出二叉樹的形狀?！敬鸢浮肯刃蛐蛄惺恰案笥摇焙笮蛐蛄惺恰白笥腋保梢妼?duì)任意結(jié)點(diǎn)，若至多只有左子女或至多只有右子女，均可使先序序列與后序序列相反，圖示如下：8假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI中序序列為BCDAFEHIG。請(qǐng)畫出該二叉樹，并將其轉(zhuǎn)換為對(duì)應(yīng)的森林。【答案】按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分：左

12、子樹和右子樹。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)為左子樹的根；若右子樹為空，則層次序列中第三個(gè)結(jié)點(diǎn)為右子樹的根。對(duì)右子樹也作類似的分析。層次序列的特點(diǎn)是，從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。9已知一個(gè)森林的先序序列和后序序列如下，請(qǐng)構(gòu)造出該森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【答案】森林的先序序列和后序序列對(duì)應(yīng)其轉(zhuǎn)換的二叉樹的先序序列和中序序列，應(yīng)先據(jù)此構(gòu)造二叉樹，再構(gòu)造出森