棧1設有三個元素X,Y,Z順序進棧(進的過程中允許出棧),下列得不到的出棧排列是()。A、XYZB、YZXC、ZXYD、ZYX正確答案：C我的答案：C得分：14.2分2

向一個棧頂指針為hs的鏈棧中插入一個s結點時,應執行()。A、hs->next=s;B、s->next=hs;hs=s;C、s->next=hs->next;hs->next=s;D、s->next=hs;hs=hs->next;正確答案：B我的答案：B得分：14.2分3棧在()中應用。A、遞歸調用B、子程序調用C、表達式求值D、A,B,C正確答案：A我的答案：D得分：0.0分4棧的操作原則是()。A、先進先出B、后進先出C、先進后出D、不分順序正確答案：B我的答案：B得分：14.2分5一個棧的輸入序列為123…n,若輸出序列的第一個元素是n,輸出第i(1<=i<=n)個元素是()。A、不確定B、n-i+1C、iD、n-i正確答案：B我的答案：B得分：14.2分6鏈棧與順序棧相比,有一個比較明顯的優點,即()A、插入操作方便B、通常不會出現棧滿的情況C、不會出現棧空的情況D、刪除操作更方便正確答案：B我的答案：D得分：0.0分二.簡答題（共1題,14.8分）1假定有四個元素A,B,C,D依次進棧,進棧過程中允許出棧,試寫出所有可能的出棧序列。正確答案：共有14中可能的出棧序列","分別為:ABCD","ABDC","ACBD","ACDB","BACD","ADCB","BADC","BCAD","BCDA","BDCA","CBAD","CBDA","CDBA","DCBA。我的答案：DCBACDBABCDAABCDBACDACDBADCBBDCA批語隊列1若用一個大小為6的數組來實現循環隊列,且當前rear和front的值分別為0和3,當從隊列中刪除一個元素,再加入兩個元素后,rear和front的值分別為多少?()A、1和5B、2和4C、4和2D、5和1正確答案：B我的答案：B得分：6.2分2用鏈表方式存儲的隊列,在進行刪除運算時()。A、僅修改頭指針B、僅修改尾指針C、頭、尾指針都要修改D、頭、尾指針可能都要修改正確答案：D我的答案：D得分：6.2分3

隊列的操作原則是()。A、先進先出B、后進先出C、先進后出D、不分順序正確答案：A我的答案：A得分：6.2分4循環隊列的出隊操作為()。A、sq.front=(sq.front+1)%maxsizeB、sq.front=sq.front+1C、sq.rear=(sq.rear+1)%maxsizeD、sq.rear=sq.rear+1正確答案：A我的答案：A得分：6.2分5棧和隊列都是()。A、順序存儲的線性結構B、鏈式存儲的非線性結構C、限制存取點的線性結構D、限制存取點的非線性結構正確答案：C我的答案：C得分：6.2分6循環隊列的隊空條件為()。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.rear+1)%maxsize==sq.front+1C、sq.(rear+1)%maxsize==sq.frontD、sq.rear==sq.front正確答案：D我的答案：D得分：6.2分7循環隊列的隊滿條件為()。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.rear+1)%maxsize==sq.front+1C、sq.(rear+1)%maxsize==sq.frontD、sq.rear==sq.front正確答案：C我的答案：C得分：6.2分二.判斷題（共8題,49.6分）1

隊列和棧都是運算受限的線性表,只允許在表的兩端進行運算。()我的答案：×得分：6.2分正確答案：×2

通常使用隊列來處理函數或過程的調用。()我的答案：×得分：6.2分正確答案：×3

循環隊列通常用指針來實現隊列的頭尾相接。()我的答案：×得分：6.2分正確答案：×4

隊列是一種插入與刪除操作分別在表的兩端進行的線性表,是一種先進后出型結構。()我的答案：×得分：6.2分正確答案：×5棧與隊列是一種特殊操作的線性表。()我的答案：√得分：6.2分正確答案：√6棧和隊列的存儲方式,既可以是順序方式,又可以是鏈式方式。()我的答案：×得分：6.2分正確答案：×7棧和隊列都是線性表,只是在插入和刪除時受到了一些限制。()我的答案：×得分：6.2分正確答案：×8

循環隊列也存在空間溢出問題。()我的答案：√得分：6.2分正確答案：√三.簡答題（共1題,7.0分）1什么是隊列的上溢現象?一般有幾種解決方法,試簡述之。正確答案：在隊列的順序存儲結構中","設隊頭指針為front","隊尾指針為rear","隊列的容量(即存儲空間的大小)為maxnum。當有元素要加入隊列(即入隊)時","若rear=maxnum","則會發生隊列的上溢現象","此時就不能將該元素加入隊列。對于隊列","還有一種“假溢出”現象:即隊列中尚有足夠的空間","但元素卻不能入隊","一般是由于隊列的存儲結構或操作方式的選擇不當所致","可以用循環隊列解決。一般地","要解決隊列的上溢現象","可以用以下幾種方法:(1)可建立一個足夠大的存儲空間以避免溢出","但這樣做的缺點是:空間使用率低","浪費存儲空間。(2)要避免出現“假溢出”現象","可用以下方法解決:第一種:采用移動元素的方法。每當有一個新元素入隊","就將隊列中已有的元素向隊頭移動一個位置","假定空余空間足夠。第二種:每當刪除一個隊頭元素","則可依次移動隊列中的元素","總是使front智深指向隊列中的第一個位置。第三種:采用循環隊列方式","將隊頭、隊尾看作是一個首尾相接的循環隊列","即用循環數組實現","此時隊首仍在隊尾之前","作插入和刪除運算時仍遵循“先進先出”原則。我的答案：在隊列的順序結構中，設隊頭指針為front，隊尾指針為rear，隊列的容量(即存儲空間大小)為maxnum。當有元素要加入隊列時，若rear==maxnum則會發生隊列的上溢現象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結構或操作方式的選擇不當所致，可以用循環隊列解決。一般的，要解決隊列的上溢現象有以下幾種方法：(1)

可建立一個足夠大的存儲空間以避免假溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。(2)

要避免出現“假溢出”現象可以使用以下方法解決：第一種：采用移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當刪除一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。批語數組1假設以行序為主序存儲二維數組A=array[1…100,1…10],設每個數據元素占2個存儲單元,基地址為10,則LOC[5,5]=()。A、808B、818C、1010D、1020正確答案：B我的答案：B得分：6.2分2稀疏矩陣一般的壓縮存儲方法有兩種,即()。A、二維數組和三維數組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表正確答案：C我的答案：C得分：6.2分3已知二維數組A10×10中,元素a20的地址為560,每個元素占4個字節,則元素a10的地址為()。A、520B、522C、524D、518正確答案：A我的答案：A得分：6.2分4對稀疏矩陣進行壓縮存儲的目的是()。A、便于進行矩陣運算B、便于輸入和輸出C、節省存儲空間D、降低運算的時間復雜度正確答案：C我的答案：C得分：6.2分5數組A中,每個元素的長度為3個字節,行下標i從1到8,列下標j從1到10,從首地址SA開始連續存放在存儲器內,該數組按行存放時,元素A[8][5]的起始地址為()。A、SA+141B、SA+144C、SA+222D、SA+225正確答案：C我的答案：C得分：6.2分6通常對數組進行的兩種基本操作是()A、建立與刪除B、索引和修改C、查找與修改D、索引與查找正確答案：C我的答案：C得分：6.2分7

數組就是矩陣,矩陣就是數組,這種說法()。A、正確B、錯誤C、前句對,后句錯D、后句對正確答案：B我的答案：B得分：6.2分8設A是n*n的對稱矩陣,將A的對角線及對角線上方的元素以列序優先的方式存儲在一維數組B[1…n(n+1)/2]中,對上述任一元素aij(1≤i,j≤n,且i≤j)在B中的位置為()。A、i(i-1)/2+jB、j(j-1)/2+iC、j(j-1)/2+i-1D、i(i-1)/2+j-1正確答案：B我的答案：B得分：6.2分9設二維數組A[1…m,1…n](即m行n列)按行序優先存儲在數組B[1,…m*n]中,則二維數組元素A[i,j]在一維數組B中的下標為()。A、(i-1)*n+jB、(i-1)*n+j-1C、i*(j-1)D、j*m+i-1正確答案：A我的答案：A得分：6.2分二.判斷題（共7題,44.2分）1數組可看成線性結構的一種推廣,因此與線性表一樣,可對它進行增刪等操作。()我的答案：×得分：6.2分正確答案：×2矩陣中的數據元素可以是不同的數據類型。()我的答案：×得分：6.2分正確答案：×3對于不同的特殊矩陣應該采用不同的存儲方式。()我的答案：√得分：6.2分正確答案：√4稀疏矩陣壓縮存儲后,必會失去隨機存取功能。()我的答案：√得分：6.2分正確答案：√5數組可看作基本線性表的一種推廣,因此與線性表一樣,可以對它進行插入、刪除等操作。()我的答案：×得分：6.2分正確答案：×6矩陣中的行列數往往是不相等的。()我的答案：×得分：6.2分正確答案：×7數組是同類型數值的集合。()我的答案：×得分：7.0分正確答案：×

樹和二叉樹

1任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序()。A、不發生改變B、發生改變C、不能確定D、以上都不對正確答案：A

我的答案：A得分：

3.0分2線索二叉樹是一種()結構。A、邏輯B、邏輯和存儲C、物理D、線性正確答案：C

我的答案：C得分：

3.0分3

在完全二叉樹中,當i為奇數且不等于1時,結點i的左兄弟是結點(),否則沒有左兄弟。A、2i-1B、i+1C、2i+1D、i-1正確答案：D

我的答案：D得分：

3.0分4線索二叉樹中,結點p沒有左子樹的充要條件是()A、p->lc=NULLB、p->ltag=1C、p->ltag=1且p->lc=NULLD、以上都不對正確答案：B

我的答案：B得分：

3.0分5如果F是由有序樹T轉換而來的二叉樹,那么T中結點的前序就是F中結點的()。A、中序B、前序C、后序D、層次序正確答案：B

我的答案：B得分：

3.0分6已知一棵完全二叉樹的結點總數為9個,則最后一層的結點數為()。A、1B、2C、3D、4正確答案：B

我的答案：B得分：

3.0分7設n,m為一棵二叉樹上的兩個結點,在中序遍歷序列中n在m前的條件是()。A、n在m右方B、n在m左方C、n是m的祖先D、n是m的子孫正確答案：B

我的答案：B得分：

3.0分8在一棵二叉樹上第4層的結點數最多為()。A、2B、4C、6D、8正確答案：D

我的答案：D得分：

3.0分9假設在一個二叉樹中,雙分支結點數為15,單分支結點數為32,則葉子結點數為()個。A、15B、16C、17D、47正確答案：B

我的答案：B得分：

3.0分10某二叉樹T有n個結點,設按某種遍歷順序對T中的每個結點進行編號,編號值為1,2,…,n,且有如下性質:T中任一結點V,其編號等于左子樹上的最小編號減1,而V的右子樹的結點中,其最小編號等于V左子樹上結點的最大編號加1,這時按()編號。A、中序遍歷序列B、前序遍歷序列C、后序遍歷序列D、層次遍歷序列正確答案：B

我的答案：B得分：

3.0分11根據先序序列ABDC和中序序列DBAC確定對應的二叉樹,該二叉樹()。A、是完全二叉樹B、不是完全二叉樹C、是滿二叉樹D、不是滿二叉樹正確答案：A

我的答案：A得分：

3.0分12在樹中除根結點外,其余結點分成m(m≥0)個()的集合T1,T2,T3…Tm,每個集合又都是樹,此時結點T稱為Ti的父結點,Ti稱為T的子結點(1≤i≤m)。A、互不相交B、可以相交C、葉節點可以相交D、樹枝結點可以相交正確答案：A

我的答案：A得分：

3.0分13如果結點A有三個兄弟,而且B是A的雙親,則B的出度是()。A、3B、4C、5D、1正確答案：B

我的答案：B得分：

3.0分14欲在不使用棧的前提下實現任意二叉樹的后序遍歷的非遞歸算法,最佳方案是二叉樹采用()存儲結構。A、三叉鏈表B、廣義表C、二叉鏈表D、順序正確答案：A

我的答案：A得分：

3.0分二.判斷題（共16題,48.0分）1若有一個結點是某二叉樹子樹中序遍歷序列中的最后一個結點,則它必是該子樹前序遍歷序列中的最后一個結點。()我的答案：√

得分：

3.0分正確答案：√2

樹的子樹是無序的。()我的答案：×

得分：

3.0分正確答案：×3后序遍歷和中序遍歷與該樹對應的二叉樹,其結果不同。()我的答案：√

得分：

3.0分正確答案：√4二叉樹的前序遍歷中,任意結點均處在其子女結點之前。()我的答案：√

得分：

3.0分正確答案：√5樹的后序遍歷與其對應的二叉樹的后序遍歷序列相同。()我的答案：√

得分：

3.0分正確答案：√6線索二叉樹是一種邏輯結構。()我的答案：×

得分：

3.0分正確答案：×7霍夫曼樹的總結點個數(多于1時)不能為偶數。()我的答案：√

得分：

3.0分正確答案：√8霍夫曼樹一定是完全二叉樹。()我的答案：×

得分：

3.0分正確答案：×9滿二叉樹也是完全二叉樹。()我的答案：√

得分：

3.0分正確答案：√10根據任意一種遍歷序列即可唯一確定對應的二叉樹。()我的答案：√

得分：

3.0分正確答案：√11二叉樹中每個結點的度不能超過2,所以二叉樹是一種特殊的樹。()我的答案：×

得分：

3.0分正確答案：×12已知二叉