數據結構（C語言描述）學習通超星期末考試章節答案2024年設長度為n的鏈隊用單循環鏈表表示,若設頭指針,則入隊出隊操作的時間為何?若只設尾指針呢?

答案:若只設頭指針,則入隊出隊操作的時間為O(n)。若只設尾指針,則入隊出隊操作的時間為O(1)。循環隊列的優點是什么?如何判別它的空和滿?

答案:循環隊列的優點是:避免假上溢現象發生,不會造成存儲空間的浪費。判別循環隊列空和滿的方法很多,比如:(1)設置標志變量flag,在Q->front==Q->rear的情況下,根據flag的值確定是空還是滿。(2)一個元素的空間閑置不用,通過條件(Q->rear+1)%QueueSize==Q->front判斷是否隊空,Q->front==Q->rear判斷是否隊滿。(3)設置一個計數器用來記錄元素的個數,根據其值判斷是空還是滿。無表頭結點的鏈隊列Q為空的條件是()。

答案:Q.front==NULL帶頭結點的鏈隊列Q為空的條件是()。

答案:Q.front==Q.rear在鏈隊列執行入隊操作()。

答案:限制在鏈表尾進行操作一個隊列的入隊序列是1,2,3,4,則隊列的可能輸出序列是()。

答案:1,2,3,4假設以數組A[60]存放循環隊列的元素,其頭指針是front=47,當前隊列有50個元素,則隊列的尾指針值為()。

答案:37若用一個大小為6的數組來實現循環隊列,且當前rear和front的值分別為0和3時,當從隊列中刪除一個元素,再加上兩個元素后,rear和front的值分別為()。

答案:2和4設循環隊列的容量為50(序號從0到49),現經過一系列的入隊和出隊運算后,有front=29,rear=11,循環隊列中的元素個數是()。

答案:32設循環隊列的容量為50(序號從0到49),現經過一系列的入隊和出隊運算后,有front=11,rear=29,循環隊列中的元素個數是()。

答案:18設以數組A[0...m-1]存放循環隊列,front指向隊頭元素,rear指向隊尾元素的下一個位置,則當前隊列中的元素個數為()。

答案:(rear-front+m)%m已知循環隊列的存儲空間大小為m,隊頭指針front指向隊頭元素,隊尾指針rear指向隊尾元素的下一個位置,則從隊列中刪除元素時,修改指針的操作是()。

答案:front=(front+1)%m;已知循環隊列的存儲空間大小為m,隊頭指針front指向隊頭元素,隊尾指針rear指向隊尾元素的下一個位置,則向隊列中插入新元素時,修改指針的操作是()。

答案:rear=(rear+1)%m;引起循環隊列隊尾位置發生變化的操作是()。

答案:入隊引起循環隊列隊頭位置發生變化的操作是()。

答案:出隊假上溢現象通常出現在()。

答案:順序隊列的入隊操作過程中可能發生假上溢現象的存儲結構是()。

答案:順序隊列在隊列中,允許進行刪除操作的一端稱為()。

答案:隊頭在隊列中,允許進行插入操作的一端稱為()。

答案:隊尾隊列的特點是()。

答案:只允許在表的一端進行插入,在另一端進行刪除下列關于隊列的敘述中,錯誤的是()。

答案:在鏈隊列中進行入隊操作時要判斷隊列是否為滿隊列操作數據的原則是()。

答案:先進先出在一棵含有n個結點的樹中,只有k度結點和葉子結點,求該樹中含有的k度結點和葉子結點的個數。

答案:設k度結點和葉子結點的個數分別為nk和n0,則孩子結點總數為n-1=knk,因此,nk=(n-1)/k。又由于n=n0+nk,所以,n0=n-nk=n-(n-1)/k。已知一棵度為m的樹中有n1個度為1的結點,n2個度為2的結點,...,nm個度為m的結點,問該樹中有多少片葉子?

答案:設該樹中的葉子數為n0個。該樹中的總結點數為n個,則有:n=n0+n1+n2+…+nm另一方面,1度結點有一個孩子,2度結點有兩個孩子,...,m度結點有m個孩子,故樹中孩子結點總數是:nl+2?n2+...+m?nm,而樹中只有根結點不是任何結點的孩子,故樹中的結點總數又可表示為:n=nl+2?n2+...+m?nm+1綜合以上兩個式子得到:n0=1+0?n1+1?n2+2?n3+...+(m-1)?nm即葉子結點數共有:1+n2+2?n3+...+(m-1)?nm個。在一棵度為3的含有16個結點的樹中,度為2的結點個數是2,度為0的結點個數是7,則度為1的結點個數是()。

答案:5在一棵度為3的含有16個結點的樹中,度為3的結點個數為2,度為2的結點個數為1,則度為1的結點個數為()。

答案:7在樹的集合表示{(x,y)|結點x是結點y的雙親}中,葉結點一定是()。

答案:只在y的位置上出現的結點在樹的集合表示{(x,y)|結點x是結點y的雙親}中,根結點一定是()。

答案:只在x的位置上出現的結點樹可以用集合{(x,y)|結點x是結點y的雙親}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},則樹T的深度是()。

答案:4樹可以用集合{(x,y)|結點x是結點y的雙親}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},則樹T的度是()。

答案:3樹可以用集合{(x,y)|結點x是結點y的雙親}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},則樹T的葉結點的個數是()。

答案:4樹可以用集合{(x,y)|結點x是結點y的雙親}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},則樹T的根結點是()。

答案:a高度為h的完全二叉樹至少有多少個結點?至多有多少個結點?

答案:(1)高度為h的完全二叉樹，其前h-1層是滿二叉樹，第h層只有1個結點時，結點數最少。前h-1層是滿二叉樹共有2h-1-1個結點，因此，至少有2h-1個結點。(2)高度為h的完全二叉樹是滿二叉樹時，結點數最多。因此，至多有2h-1個結點。一棵含999個結點的完全二叉樹的深度為()。

答案:10結點數為20的二叉樹最小深度為()。

答案:5結點數為20的二叉樹的最大深度為()。

答案:20設完全二叉樹有n個結點,則其深度為()。

答案:∟lgn」+1除第一層外,滿二叉樹中每一層結點個數是上一層結點個數的()。

答案:2倍若一棵二叉樹有11個葉子結點,則該二叉樹中度為2的結點個數是()。

答案:10三個結點的二叉樹共有()種。

答案:5二叉樹共有()種基本形態。

答案:5在具有n個結點的二叉鏈表中,共有()個指針域為空。

答案:n+1在具有n個結點的二叉鏈表中,共有()個指針域用來指示結點的左、右孩子。

答案:n-1已知一棵完全二叉樹中共有768結點,則該樹中共有()個非葉子結點。

答案:384已知一棵完全二叉樹中共有768結點,則該樹中共有()個葉子結點。

答案:384已知一棵完全二叉樹中共有768結點,則該樹中共有()個2度結點。

答案:383在含有n個結點的完全二叉樹中,1度結點的個數至多為()。

答案:1在含有n個結點的完全二叉樹中,葉子結點的個數為()。

答案:n-[n/2]設含有n個結點的完全二叉樹的結點ki的編號為i(3<2i+1答案:2i+1/star3/origin/8ac0f7c47d21f6f79fd48a2b6030208d.png

答案:ABDECF;先序遍歷順序存儲的完全二叉樹已知二叉樹的先序序列和中序序列分別為ABDEHCFI和DBHEACIF。（1）畫出該二叉樹的二叉鏈表存儲表示。（

）（2）寫出該二叉樹的后序序列。（

）

答案:該二叉樹的后序序列為：DHEBIFCA已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA。（1）請畫出此二叉樹。（

）（2）給出該二叉樹的先序遍歷序列。（

）

答案:該二叉樹的先序遍歷序列為：ABCDEFGH已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF。(1)請畫出此二叉樹。（

）(2)給出該二叉樹的后序遍歷序列。（

）

答案:略;該二叉樹的后序遍歷序列為：GHDBEIFCA/star3/origin/491a42b1b1e0a2b9ea75f4b4ff824ce3.png

答案:RNL遍歷序列為:FCEABD已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是deabc,它的前序遍歷序列是()。

答案:cedba已知二叉樹的()不能唯一確定一棵二叉樹。

答案:先序序列和后序序列在含有3個結點a,b,c的二叉樹中,前序序列為abc且后序序列為cba的二叉樹有()棵。

答案:4在任意一棵二叉樹的前序序列和后序序列中,各葉子之間的相對次序關系()。

答案:都相同若一棵二叉樹的后序遍歷序列與中序遍歷序列相同,則該二叉樹可能的形狀是()。

答案:樹中非葉結點均只有左子樹若一棵二叉樹的前序遍歷序列與中序遍歷序列相同,則該二叉樹可能的形狀是()。

答案:樹中非葉結點均只有右子樹若一棵二叉樹的前序遍歷序列與后序遍歷序列相同,則該二叉樹可能的形狀是()。

答案:樹中只有一個根結點對含有()個結點的非空二叉樹,采用任何一種遍歷方式,其結點訪問序列均相同。

答案:1/star3/origin/b10a192fe6326825429fcf4297b63c39.png

答案:DHEBFJIGCAn個頂點的非強連通圖中至多含有()個強連通分量。

答案:nn個頂點的非強連通圖中至少含有()個強連通分量。

答案:2n個頂點的強連通圖中含有()個強連通分量。

答案:1n個頂點的強連通圖中至少含有()條有向邊。

答案:nn個頂點的非連通圖中至多含有()個連通分量。

答案:nn個頂點的非連通圖中至少含有()個連通分量。

答案:2n個頂點的連通圖中含有()個連通分量。

答案:1一個具有n個頂點的無向連通圖至少有()條邊。

答案:n-1連通圖是指圖中任意兩個頂點之間()。

答案:都連通的無向圖在無向圖中,若從頂點a到頂點b存在(),則稱a與b之間是連通的。

答案:一條路徑設G=(V,E)是一個圖,V'是V的子集,E'是E的子集,如果()則G'=(V',E')為G的子圖。

答案:E'中的邊所關聯的頂點均在V'中且G'也是一個圖/star3/origin/ca347fc0792eebaba7a466e2f76dfaa9.png

答案:無向圖或有向圖設有向圖中所有頂點的入