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

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

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

3、SX操作序列；對于合法序列BAC，我們使用SSXXSX操作序列。3.如果輸入序列為123456，試問能否通過棧結(jié)構(gòu)得到以下兩個序列：435612和135426，請說明為什么不能或如何才能得到。【答案】輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（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.簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。【答案】設(shè)順序存儲隊列用一維數(shù)組q[m]表示，其中m為隊列中元素個數(shù)，隊列中元素在向量中的下標(biāo)從0到m1。設(shè)隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當(dāng)front等于

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

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

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

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

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

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

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

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