數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）學(xué)習(xí)通超星期末考試章節(jié)答案2024年設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示,若設(shè)頭指針,則入隊(duì)出隊(duì)操作的時(shí)間為何?若只設(shè)尾指針呢?

答案:若只設(shè)頭指針,則入隊(duì)出隊(duì)操作的時(shí)間為O(n)。若只設(shè)尾指針,則入隊(duì)出隊(duì)操作的時(shí)間為O(1)。循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判別它的空和滿?

答案:循環(huán)隊(duì)列的優(yōu)點(diǎn)是:避免假上溢現(xiàn)象發(fā)生,不會(huì)造成存儲(chǔ)空間的浪費(fèi)。判別循環(huán)隊(duì)列空和滿的方法很多,比如:(1)設(shè)置標(biāo)志變量flag,在Q->front==Q->rear的情況下,根據(jù)flag的值確定是空還是滿。(2)一個(gè)元素的空間閑置不用,通過(guò)條件(Q->rear+1)%QueueSize==Q->front判斷是否隊(duì)空,Q->front==Q->rear判斷是否隊(duì)滿。(3)設(shè)置一個(gè)計(jì)數(shù)器用來(lái)記錄元素的個(gè)數(shù),根據(jù)其值判斷是空還是滿。無(wú)表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是()。

答案:Q.front==NULL帶頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是()。

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

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

答案:1,2,3,4假設(shè)以數(shù)組A[60]存放循環(huán)隊(duì)列的元素,其頭指針是front=47,當(dāng)前隊(duì)列有50個(gè)元素,則隊(duì)列的尾指針值為()。

答案:37若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前rear和front的值分別為0和3時(shí),當(dāng)從隊(duì)列中刪除一個(gè)元素,再加上兩個(gè)元素后,rear和front的值分別為()。

答案:2和4設(shè)循環(huán)隊(duì)列的容量為50(序號(hào)從0到49),現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后,有front=29,rear=11,循環(huán)隊(duì)列中的元素個(gè)數(shù)是()。

答案:32設(shè)循環(huán)隊(duì)列的容量為50(序號(hào)從0到49),現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后,有front=11,rear=29,循環(huán)隊(duì)列中的元素個(gè)數(shù)是()。

答案:18設(shè)以數(shù)組A[0...m-1]存放循環(huán)隊(duì)列,front指向隊(duì)頭元素,rear指向隊(duì)尾元素的下一個(gè)位置,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為()。

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

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

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

答案:入隊(duì)引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是()。

答案:出隊(duì)假上溢現(xiàn)象通常出現(xiàn)在()。

答案:順序隊(duì)列的入隊(duì)操作過(guò)程中可能發(fā)生假上溢現(xiàn)象的存儲(chǔ)結(jié)構(gòu)是()。

答案:順序隊(duì)列在隊(duì)列中,允許進(jìn)行刪除操作的一端稱(chēng)為()。

答案:隊(duì)頭在隊(duì)列中,允許進(jìn)行插入操作的一端稱(chēng)為()。

答案:隊(duì)尾隊(duì)列的特點(diǎn)是()。

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

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

答案:先進(jìn)先出在一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中,只有k度結(jié)點(diǎn)和葉子結(jié)點(diǎn),求該樹(shù)中含有的k度結(jié)點(diǎn)和葉子結(jié)點(diǎn)的個(gè)數(shù)。

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

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

答案:5在一棵度為3的含有16個(gè)結(jié)點(diǎn)的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為1的結(jié)點(diǎn)個(gè)數(shù)為()。

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

答案:只在y的位置上出現(xiàn)的結(jié)點(diǎn)在樹(shù)的集合表示{(x,y)|結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親}中,根結(jié)點(diǎn)一定是()。

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

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

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

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

答案:a高度為h的完全二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)?至多有多少個(gè)結(jié)點(diǎn)?

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

答案:10結(jié)點(diǎn)數(shù)為20的二叉樹(shù)最小深度為()。

答案:5結(jié)點(diǎn)數(shù)為20的二叉樹(shù)的最大深度為()。

答案:20設(shè)完全二叉樹(shù)有n個(gè)結(jié)點(diǎn),則其深度為()。

答案:∟lgn」+1除第一層外,滿二叉樹(shù)中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的()。

答案:2倍若一棵二叉樹(shù)有11個(gè)葉子結(jié)點(diǎn),則該二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)是()。

答案:10三個(gè)結(jié)點(diǎn)的二叉樹(shù)共有()種。

答案:5二叉樹(shù)共有()種基本形態(tài)。

答案:5在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中,共有()個(gè)指針域?yàn)榭铡?/p>

答案:n+1在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中,共有()個(gè)指針域用來(lái)指示結(jié)點(diǎn)的左、右孩子。

答案:n-1已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn),則該樹(shù)中共有()個(gè)非葉子結(jié)點(diǎn)。

答案:384已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn),則該樹(shù)中共有()個(gè)葉子結(jié)點(diǎn)。

答案:384已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn),則該樹(shù)中共有()個(gè)2度結(jié)點(diǎn)。

答案:383在含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中,1度結(jié)點(diǎn)的個(gè)數(shù)至多為()。

答案:1在含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中,葉子結(jié)點(diǎn)的個(gè)數(shù)為()。

答案:n-[n/2]設(shè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)ki的編號(hào)為i(3<2i+1答案:2i+1/star3/origin/8ac0f7c47d21f6f79fd48a2b6030208d.png

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

）（2）寫(xiě)出該二叉樹(shù)的后序序列。（

）

答案:該二叉樹(shù)的后序序列為：DHEBIFCA已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA。（1）請(qǐng)畫(huà)出此二叉樹(shù)。（

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

）

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

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

）

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

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

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

答案:先序序列和后序序列在含有3個(gè)結(jié)點(diǎn)a,b,c的二叉樹(shù)中,前序序列為abc且后序序列為cba的二叉樹(shù)有()棵。

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

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

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

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

答案:樹(shù)中只有一個(gè)根結(jié)點(diǎn)對(duì)含有()個(gè)結(jié)點(diǎn)的非空二叉樹(shù),采用任何一種遍歷方式,其結(jié)點(diǎn)訪問(wèn)序列均相同。

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

答案:DHEBFJIGCAn個(gè)頂點(diǎn)的非強(qiáng)連通圖中至多含有()個(gè)強(qiáng)連通分量。

答案:nn個(gè)頂點(diǎn)的非強(qiáng)連通圖中至少含有()個(gè)強(qiáng)連通分量。

答案:2n個(gè)頂點(diǎn)的強(qiáng)連通圖中含有()個(gè)強(qiáng)連通分量。

答案:1n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()條有向邊。

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

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

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

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

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

答案:都連通的無(wú)向圖在無(wú)向圖中,若從頂點(diǎn)a到頂點(diǎn)b存在(),則稱(chēng)a與b之間是連通的。

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

答案:E'中的邊所關(guān)聯(lián)的頂點(diǎn)均在V'中且G'也是一個(gè)圖/star3/origin/ca347fc0792eebaba7a466e2f76dfaa9.png

答案:無(wú)向圖或有向圖設(shè)有向圖中所有頂點(diǎn)的入