數據結構（山東聯盟-濱州學院）智慧樹知到期末考試答案章節(jié)答案2024年山東航空學院

數據結構（山東聯盟-濱州學院）智慧樹知到期末考試答案+章節(jié)答案2024年山東航空學院所謂取廣義表的表尾就是返回廣義表中最后一個元素。

答案:錯從邏輯結構上看，n維數組的每個元素均屬于n個向量。（

）

答案:對huffman樹沒有度為1的結點。

答案:對棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。

答案:對一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關行下標與列下標的值互換，并把m和n的值互換，則就完成了Am*n的轉置運算。

答案:錯消除遞歸不一定需要使用棧。

答案:對在任何情況下，歸并排序都比簡單插入排序快。

答案:錯二叉排序樹刪除一個結點后，仍是二叉排序樹。（）

答案:對將關鍵字序列{7，8，30，11，18，9，14}，散列存儲到哈希表中，哈希表的存儲空間是一個下標從0開始的一維數組。處理沖突采用線性探測法。哈希函數為h(key)=(key×3)%表長，要求裝入因子為0.7。則成功查找的平均查找長度為

答案:1.14棧在（）中有所應用。

答案:前三個選項都有在一個鏈隊列中，假設f和r分別為隊頭和隊尾指針，則刪除元素（即出隊操作）的運算是（）。

答案:f=f->next;設線性表的順序存儲結構中，每個元素占用L個存儲單元，表的第1個元素的存儲地址為d，則第i個元素（1<=i<=n,n為表長）的存儲地址為（）

答案:d+(i-1)*L對一個頭指針為head的帶頭節(jié)點的單鏈表，判定該表為空表的條件是（）。

答案:head->next==NULL設有100個元素，用折半查找時，最大比較次數為（），最小比較次數為（）。

答案:71設要將序列{Q，H，C，Y，P，A，M，S，R，D，F，X}中的關鍵字按字母升序重新排序，下面（）是冒泡排序一趟掃描的結果。

答案:H，C，Q，P，A，M，S，R，D，F，X，Y若有a,b,c三個字符按照a,b,c的順序執(zhí)行入棧操作后，接著入隊列，則以下出隊列的序列不可能的是（

）。

答案:c,a,b利用二叉鏈表存儲樹,則根結點的右指針是(

)。

答案:空若給定的關鍵字集合為{20，15，14，18，21，36，40，10}，一趟快速排序結束時，關鍵字的排列順序為（）。

答案:10，15，14，18，20，36，40，21如果待排序序列中兩個數據元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。

答案:希爾排序以下各組序列不屬于堆的是（）。

答案:（100，85，40，77，80，60，66，98，82，10，20）從方法的穩(wěn)定性來比較，基數排序是穩(wěn)定的內排方法，所有時間復雜度為O（n2）的簡單排序法也是穩(wěn)定的。

答案:對如果有向圖的拓撲排序序列是唯一的，則圖中必定只有一個頂點的入度為0，一個頂點的出度為0。

答案:對二維數組是其數據元素為線性表的線性表（

）

答案:對對一個滿二叉樹,m個樹葉,n個結點,深度為h,則(

)。

答案:n=2h-1堆的形狀是一棵（）。

答案:完全二叉樹在下面冒泡排序算法中填入適當內容，使該算法在發(fā)現有序時能及時停止。void

BubbleSort

(int

R[],intn){

for(i=1;i答案:exchange

j>=i

exchange=true在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（）。

答案:訪問第i個結點(1<=i<=n)和求第j個結點的直接前驅(2<=j<=n)（

）是HASH查找的沖突處理方法。

答案:開放定址法適用于折半查找的表的存儲方式及元素排列要求是（）。

答案:順序存儲，元素有序廣義表((a,c,d),())的表尾是（）。

答案:(())堆是一種（）排序。

答案:選擇為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數據緩沖區(qū)。主機將要輸出的數據依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數據。該緩沖區(qū)的邏輯結構應該是（

）。

答案:隊列設有向圖G=(V,E)，頂點集V={V0,V1,V2,V3,}，邊集E={,,,}，若從頂點V0開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數是（）。

答案:5對一個算法的評價，不包括以下（）方面的內容。

答案:并行性對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關鍵字。

答案:4下列序列構造的二叉排序樹中，與其他三個序列構造結果不同的是_____

答案:100,60,80,90,120,110,130有鄰接矩陣A

=可以看出該圖共有()個頂點。(

)

答案:4從未排序序列中依次取出元素與已排序序列中的元素比較，將其放入已排序序列的正確位置上的方法，稱作（）。

答案:插入排序從空樹開始，依次插入52,26,14,32,71,60,93,58,24,41，構造一棵二叉排序樹。在查找60時進行比較的次數是____

答案:3用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時(

)。

答案:隊頭，隊尾指針都可能要修改廣義表（（a），a）的表頭是（）。

答案:(a)設計一個判別表達式中左，右括號是否配對出現的算法，采用（）數據結構最佳。

答案:棧一個廣義表可以為其它廣義表所共享。（

）

答案:對不論行優(yōu)先還是列優(yōu)先，二維數組的最后一個元素的存儲位置是一樣的。

答案:對在堆中執(zhí)行插入和刪除最小值運算都是只需O(logn)的時間

答案:對對一棵二叉排序樹按前序方法遍歷得出的結點序列是從小到大的序列。（）

答案:錯棧是實現過程和函數等子程序所必需的結構。

答案:對任何一個遞歸過程都可以轉換成非遞歸過程。

答案:對隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。

答案:錯快速排序被認為是在所有同數量級(O（logn）)的排序方法中，其平均性能最好。

答案:對對一組數據{2，12，16，88，5，10}進行排序，若前三趟排序結果如下：第一趟：{2，12，16，5，10，88}第二趟：{2，12，5，10，16，88}第三趟：{2，5，10，12，16，88}則采用的排序算法可能是（）。

答案:冒泡排序希爾排序的組內排序采用的是（

）。

答案:直接插入分別以下列序列構造二叉排序樹，與用其他三個序列所構造結果不同的是（）。

答案:100,60,80,90,120,110,130字符A,B,C依次進入一個棧,按出棧的先后順序組成不同的字符串,則至多可以組成()個不同的字符串。

答案:5循環(huán)隊列存儲在數組A[0..m-1]中，則入隊時的操作是（）。

答案:rear=(rear+1)%m下列關鍵字序列中，（）是堆。

答案:16,23,53,31,94,72某算法的語句執(zhí)行頻度為100n+nlog2(n+n2+8)，其時間復雜度表示為（）。

答案:O(n^2)采用多項式的非零項鏈式存儲表示法，如果兩個多項式的非零項分別為N1和N2個，最高項指數分別為M1和M2，則實現兩個多項式相加的時間復雜度是

答案:O(N1+N2)使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標頂點是

答案:5,2,3,6,413．下面給出的四種排序方法中，排序過程中的比較次數與排序方法無關的是。()

答案:選擇排序法一個有n個頂點的無向圖，最少有()個連通分量，最多有()個連通分量。（

）

答案:1

n設哈希表長為14，哈希函數是H(key)=key%11，表中已經有關鍵字15、38、61、84，現要將關鍵字為49的元素存儲到表中，用二次探測法解決沖突，則放入的位置是（）。

答案:9下列排序算法中，其中（）是穩(wěn)定的。

答案:歸并排序，冒泡排序給出一組關鍵字T={12，86，2，16，8，84，68，52，4，20，10}，對其進行非遞減排序，應用直接插入排序算法時第二趟排序后的序列是？

答案:2，4,12，86，16，8，84，68，52，20，10在對n個元素進行直接插入排序的過程中，共需要進行（）趟。

答案:n-1設棧S和隊列Q的初始狀態(tài)為空，元素e1,

e2,

e3,

e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4,

e3,

e6,

e5,

e1則棧S的容量至少應該是(

)。

答案:3有數據{53，30，37，12，45，24，96}，從空二叉樹開始逐步插入數據形成二叉排序樹，若希望高度最小，應選擇下列（）的序列輸入。

答案:37，24，12，30，53，45，96下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。

答案:[27，38，18]49[93，73]若廣義表S的表頭是空表，則S是一個空表。

答案:錯插入排序的基本思想是：每一趟在n-i+1個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。

答案:錯直接插入排序用監(jiān)視哨的作用是免去查找過程中每一步都要檢測整個表是否查找完畢，提高了查找效率。

答案:對線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表。(

)

答案:對若有一個葉子結點是某子樹的中序遍歷的最后一個結點，則它必須是該子樹的先序遍歷中的最后一個結點。

答案:對設Huffman樹的葉子結點數為m,則結點總數為2m-1。

答案:對二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。

答案:錯一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關行下標與列下標的值互換，并把m和n的值互換，則就完成了Am*n的轉置運算。()

答案:錯在用堆排序算法排序時，如果要進行增序排序，則需要采用“大根堆”。

答案:對數組不適合作為任何二叉樹的存儲結構。（

）

答案:錯假定對線性表(38,25,74,52,48)進行哈希存儲，采用H(K)=K%7作為哈希函數，采用線性探測法處理沖突，則平均查找長度為________。

答案:2用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用

來實現算法的。

答案:隊列在一個以head為頭的單循環(huán)鏈表中，p指針指向鏈表末尾的條件是（）。

答案:p->next=head下面關于哈希(Hash，雜湊)查找的說法正確的是(

)

答案:不存在特別好與壞的哈希函數，要視情況而定已知表頭元素為c的單鏈表在內存中的存儲狀態(tài)如下表所示現f存放于1014H處，并插入到單鏈表中，若f在邏輯上位于a和e之間，則a、e、f的鏈接地址依次是（）

答案:1014H,1004H,1010H一元稀疏多項式以循環(huán)單鏈表按降冪排列，結點有三個域：系數域coef，指數域exp和指針域next，現對鏈表求一階導數，鏈表的頭指針為h，頭結點的exp域為-1。請完成下面的算法。Derivative(linklisth){

q=h;p=h->next;

while(p!=h)

{

if(①)

{

q->next=p->next;

free(p);

p=q->next;

}

else

{p->coef=②;

p->exp--;

q=p;

}

③;

}}

答案:①p->exp==0

②p->coef*p->exp

③p=p->next有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當用二分法查找值82的結點時，（）次比較后查找成功。

答案:4當一個頂點數為n的有向圖用連接矩陣A表示時，頂點i的度是（

）。

答案:設無向圖的頂點個數為n，則該圖最多有（

）條邊。

答案:n（n-1）/2下列排序方法中穩(wěn)定的是(

)

答案:直接插入排序在一個以

h

為頭的單循環(huán)鏈表中,p

指針指向鏈尾的條件是(

)。

答案:p->next

==

h鏈表不具備的特點是（

）。

答案:可隨機訪問任意一個結點有一帶頭結點的循環(huán)鏈表，現將其頭指針改為尾指針rear，則該鏈表的首元結點和尾結點的存儲位置分別是（）。

答案:rear->next->next和rear鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（）。

答案:通常不會出現棧滿的情況某二叉樹的先序和后序遍歷序列正好相反，則該二叉樹一定是（）

答案:空或只有一個結點對下面的遞歸算法，調用P(3)的執(zhí)行結果是？。voidP(inti){

if(i>0)

{

printf(i);

P(i-1);

P(i-1);

}}

答案:3211211任何一個無向連通圖的最小生成樹

答案:一棵或多棵某二叉樹的先序和后序遍歷序列正好相反,則該二叉樹一定是(

)。

答案:深度等于其結點數一個具有1001個結點的完全二叉樹，其中葉子結點的個數是（）。

答案:501輸入10^5個只有一位數字的整數，可以用O(n)復雜度將其排序的算法是

答案:基數排序已知一棵完全二叉樹的第6層有8個葉子，則該完全二叉樹結點數最多是（）個。

答案:111線性表中，只有直接前驅而無后繼的元素是（）。

答案:尾元素對于含有n個頂點的帶權連通圖，它的最小生成樹是指圖中任意一個（）。

答案:由n個頂點構成的邊的權值之和最小的連通子圖下面關于哈希查找的說法正確的是（）。

答案:不存在特別好和特別壞的哈希函數，要視情況而定下面（）適合構造一個稠密圖G的最小生成樹。

答案:Prim算法對一組數據{84,45,20,10,16}排序，數據的排列次序在排序過程中的變化為:

(1){84,45,20,10,16}

(2){10,45,20,84,16}

(3){10,16,20,84,45}

(4){10,16,20,45,84}該排序算法是以下哪種（）

答案:簡單選擇排序如果無向完全圖G中有78條邊，則G的生成樹有（

）條邊。

答案:12(15，9，7，8，20，-1，4)進行排序，第一趟排序后的序列變?yōu)?-1，9，7，8，20，15，4)，則采用的排序方法是（

）。

答案:簡單選擇排序數據在計算機內存中的表示是指（）

答案:數據的存儲結構若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現的是（）。

答案:4，3，1，2，5快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。

答案:錯排序的穩(wěn)定性是指排序算法中的比較次數保持不變，且算法能夠終止。

答案:錯歸并排序中，歸并的趟數是（）。

答案:O(logn)堆肯定是一棵平衡二叉樹。

答案:錯下列排序算法中()排序在一趟結束后不一定能選出一個元素放在其最終位置上。

答案:歸并下列內部排序算法中：其比較次數與序列初態(tài)無關的算法是（）。

答案:二路歸并排序###簡單選擇排序設有1000個無序的元素，希望用最快的速度的選出其中前10個最大的元素，最好選用（）的排序法。

答案:堆排序排序趟數與序列的原始狀態(tài)有關的排序方法是()排序法。

答案:冒泡###快速歸并排序輔助存儲為O（1）。

答案:錯希爾排序又稱縮小增量排序，其最后一趟排序的增量為（

）。

答案:1從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（

）。

答案:選擇排序希爾排序是穩(wěn)定的排序算法。

答案:錯如果對n個元素進行直接選擇排序，則進行任一趟排序的進程中，為尋找最小值元素所需要的時間復雜度為（）

答案:O(n)一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）

答案:40，38，46，56，79，84對m個不同的關鍵字由小到大進行冒泡排序，當（

）時比較的次數最多。

答案:從大到小排列從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的排序方法稱為（）。

答案:插入排序n個結點的二叉排序樹有多種形態(tài)，其中高度最小的二叉排序樹是最佳的。

答案:對含有25個結點的二叉排序樹上，查找關鍵字為35的結點，則依次比較的關鍵字序列有可能是

答案:46,36,18,28,35完全二叉樹肯定是平衡二叉樹。

答案:錯當在一個有序順序存儲表中查找一個數據時，既可用折半查找，也可以用順序查找，但前者比后者的查找速度（）。

答案:大部分情況下快查找n個元素的有序表時，最有效的查找方法是（）。

答案:折半查找假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入哈希表中，至少要進行（）次探測。

答案:k(k+1)/2有n個數據存在在一維數組a中，進行順序查找時，這n個數據的排列有序或無序其平均查找長度不同。

答案:錯對包含N個元素的哈希表進行查找，平均查找長度為

答案:不確定將10個元素散列到長度為100000的哈希表中，則（）產生沖突。

答案:仍可能會二叉排序樹的左右子樹都是二叉排序樹。

答案:對對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數為()。

答案:4若根據查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計算哈希地址，則元素64的哈希地址為()。

答案:12若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為()。

答案:(n+1)/2對具有n個元素的有序表采用折半查找，則算法的時間復雜度為()。

答案:O(logn)從具有n個結點的二叉排序樹中查找一個元素時，在最壞情況下的時間復雜度為()。

答案:O(n)具有12個關鍵字的有序表，折半查找的平均查找長度是（）。

答案:3.1若根據查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為()。

答案:(d+1)%m使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加入到最小生成樹中的邊依次是（）

答案:(b,f),(b,d),(a,e),(c,e),(b,e)下列關于無向連通圖的敘述中，正確的是（）。所有頂點的度數之和是偶數邊數大于頂點數減1至少有一個頂點的度是1

答案:只有a在TopSort（拓撲排序）函數中，如果外循環(huán)還沒結束，就已經找不到“未輸出的入度為0的頂點”，則說明

答案:圖中必定存在回路在一個有權無向圖中，如果頂點b到頂點a的最短路徑長度是10，頂點c與頂點b之間存在一條長度為3的邊。那么下列說法中有幾句是正確的？I.

c與a的最短路徑長度就是13II.

c與a的最短路徑長度就是7III.

c與a的最短路徑長度不超過13IV.

c與a的最短路徑不小于7

答案:2句對一個無向圖進行深度優(yōu)先搜索時，得到的搜索序列是唯一的。

答案:錯在有向圖的鄰接表存儲結構中，頂點v在鏈表中出現的次數是（）。

答案:頂點v的入度下列選項中，不是如下有向圖的拓撲序列的是

答案:5,2,1,6,3,4對于一個有n個頂點，e條邊的有向圖，采用鄰接表存儲，對其進行廣度優(yōu)先搜索，算法的時間復雜度是（）。

答案:O(n+e)G是一個非連通無向圖，有28條邊，則G至少有（）個頂點。

答案:9n個頂點的完全有向圖含有邊的數目是（）。

答案:n(n-1)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的

倍。

答案:1已知有向圖G=(V,E)，其中V={V1，V2，V3，V4，V5，V6，V7},E={，,,,,,,,}，G的拓撲有序序列是（）。

答案:V1，V3，V4，V6，V2，V5，V7用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結點的個數有關，而與圖的邊數無關。

答案:對有n-1條邊的圖肯定都是生成樹。

答案:錯一個非空圖可以沒有邊，但不能沒有頂點。

答案:對如果有向圖的所有頂點可以構成一個拓撲排序，則說明該有向圖存在回路。

答案:錯某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF,則后序遍歷序列為（

)。

答案:GDBEHFCA設森林中有三棵樹,第一、二、三棵樹的結點個數分別為n1、n2、n3,那么將森林轉換成二叉樹后,其根結點的右子樹上有(

)個結點。

答案:n2+n3一個具有1025個結點的二叉樹的高h為(

)。

答案:11至1025之間設某棵二叉樹的高度為9,則該二叉樹上葉子結點最多有(

)。

答案:256如果一棵二叉樹中所有結點的值都大于其左子樹中的所有結點的值,且小于其右子樹中所有結點的值,現欲得到各個結點的遞增序列,采用的方法是(

)。

答案:中序遍歷由權值分別為

11、

8、

6、

2

、

5

的葉子結點生成一棵哈夫曼樹,它的帶權路徑長度為(

)。

答案:71若完全二叉樹的結點個數為100,則第60個結點的度為(

)。

答案:0如果一個完全二叉樹最底下一層為第六層(根為第一層)且該層共有8個葉結點,那么該完全二叉樹共有多少個結點?(

)

答案:39一棵二叉樹的高度為h,所有結點的度或為0或為2,則這棵二叉樹最少有(

)個結點。

答案:2h-1樹的基本遍歷策略分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹,其中結論(

)是正確的。

答案:樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同設n,m為一棵二叉樹上的兩個結點,在中序遍歷中

,n在m前的條件是(

)。

答案:n在m的左子樹上深度為5的二叉樹至多有(

)個結點。

答案:31某二叉樹中序序列為BDAECF,后序序列為DBEFCA,則二叉樹對應的森林包括(

)棵樹。

答案:3在只有度為0和度為2的二叉樹中

,設度為0的結點有n0個,度為2的結點有n2個,則有n0=n2+1。

答案:對任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序(

)。

答案:不發(fā)生改變二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。

答案:錯樹中所有結點的度之和等于所有結點數減1。

答案:對若一棵二叉樹具有10個度為2的結點,5個度為1的結點,則度為0的結點的個數是(

)。

答案:11二叉樹是非線性數據結構，所以

。

答案:順序存儲結構和鏈式存儲結構都能存儲設森林F中有4棵樹,第1、2、3、4棵樹的結點個數分別為n1、n2、n3、n4,當把森林F轉換成一棵二叉樹后,其根結點的左子樹中有n1個結點。

答案:錯對矩陣壓縮存儲是為了（）

答案:減少存儲空間下面說法不正確的是（）。

答案:廣義表的表頭總是一個廣義表操作取廣義表的表尾就是將廣義表中最后一個元素值返回。

答案:錯對于以行為主序的存儲結構來說．在數組A[c1..d1,c2..d2]中，c1和d1分別為數組A的第一維下標的下、上界，c2和d2分別為第二維下標的下、上界．每個數據元素占k個存儲單元，二維數組中任一元素a[i,j]的存儲位置可由（

）確定。

答案:Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×k設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第1個元素，其存儲地址為1，每個元素占用1個地址空間，則a85的地址為（）。

答案:33A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是

答案:j（j-1）/2+iGetHead

(

(p，h，w)

)=

答案:p已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項t的運算是（

）。

答案:head（tail(head（tail（tail（L）））)）有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，A[1][1]為第一元素，其存儲地址為1，每個元素占一個地址空間，則A[7][5]和A[5][6]的存儲地址分別為（）

答案:26

25某隊列允許在其兩端進行入隊操作，但只允許在一端進行出隊操作，若有元素a,b,c,d,e依次入隊后再進行出隊操作，則不可能得到的出隊序列是（）。

答案:d,b,c,a,e若已知一隊列用單向鏈表表示，該單向鏈表的當前狀態(tài)（含3個對象）是：1->2->3，其中x->y表示x的下一節(jié)點是y。此時，如果將對象4入隊，然后隊列頭的對象出隊，則單向鏈表的狀態(tài)是：（）。

答案:2->3->4通常使用隊列來處理函數或過程的調用。

答案:錯棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式

答案:對（

）的一個重要應用是在程序設計語言中實現遞歸。

答案:棧設有一個遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計算fact(n)需要調用該函數的次數為（

）。

答案:n+1有如下遞歸算法：int

fact(int

n){//n大于等于0

if(n<=0)

return

1;

else

return

n*fact(n-1);}則計算fact(n)需調用該函數的次數是（）。

答案:n+1輸入序列為ABC，若出棧的順序為CBA時，經過的棧操作為（

）。

答案:push,push,push,pop,pop,pop設abcdef以所給次序進棧，若在進棧操作時允許退棧，則下列得不到的序列為（）

答案:cabdef隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。

答案:對循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是(

)。

答案:(rear-front+m)%m若棧采用順序存儲方式存儲，兩棧共享空間A[1..m]，top[i]代表第i個棧（i=1,

2）的棧頂，棧1的底在A[1]，棧2的底在A[m]，則棧滿的條件是（）。

答案:top[1]+1=top[2]不論棧是用數組實現，還是用鏈表實現，入棧和出棧的時間復雜度均為O(n)。

答案:錯假定循環(huán)隊列的隊首和隊尾指針分別為front和rear，則判斷隊滿的條件為（）。

答案:(rear＋1)modMAXSIZE==front若已知一個棧的進棧序列是1，2，3……n，其輸出序列是p1，p2，p3，pn，

若p1=3，則p2為（）

答案:可能是2具有線性關系的集合中，若a，b是集合中的任意兩個元素，則必有a答案:錯在一個帶頭結點的雙向循環(huán)鏈表中,若要在p所指向的結點之前插入一個新結點,則需要相繼修