計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬試卷1（共272題）

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬試卷1（共7套）（共272題）計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬試卷第1套一、單選題(本題共34題，每題1.0分，共34分。)1、下面是一個(gè)求最小生成樹的算法，其中G是連通無向圖，T是所求的生成樹。T;=G;WhileT中存在回路dobegin在T中找一條權(quán)值最大的邊e；T：=T一[e]；(T中去掉e邊)End．試問該算法是哪一種求最小生成樹的算法?()A、Prim(普里姆)算法B、Kruskal(克魯斯卡爾算法)C、羅巴赫算法D、其他算法標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由算法可以看出使用的是Knlskal算法。2、鄰接表是圖的一種()。A、順序存儲(chǔ)結(jié)構(gòu)B、鏈接存儲(chǔ)結(jié)構(gòu)C、索引存儲(chǔ)結(jié)構(gòu)D、散列存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：圖的鄰接表存儲(chǔ)結(jié)構(gòu)是一種鏈接存儲(chǔ)結(jié)構(gòu)。3、下面試圖對(duì)圖中路徑進(jìn)行定義，說法正確的是()。A、由頂點(diǎn)和相鄰頂點(diǎn)序列構(gòu)成的邊所形成的序列B、由不同頂點(diǎn)所形成的序列C、由不同邊所形成的序列D、上述定義都不是標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：由圖的定義可知，B與c是錯(cuò)誤的。4、無向圖中項(xiàng)點(diǎn)個(gè)數(shù)為n，那么邊數(shù)最多為()。A、n一1B、n(n-1)／2C、n(n+1)／2D、n2標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：無向圖中有n個(gè)頂點(diǎn)，如果每?jī)蓚€(gè)頂點(diǎn)之間均是相互連通的，那么此時(shí)無向圖中的邊數(shù)最多，為凡(n一1)／2。5、在一個(gè)具有n(n＞0)個(gè)頂點(diǎn)的連通無向圖中，至少需要的邊數(shù)是()。A、nB、n+1C、n-1D、n／2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。所以具有n個(gè)頂點(diǎn)的連通無向圖至少有n一1條邊。6、以下敘述中正確的是()。I．對(duì)有向圖G，如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖Ⅱ．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存訪問過的頂點(diǎn)Ⅲ．圖的深度優(yōu)先搜索中一般要采用棧來暫存訪問過的頂點(diǎn)A、I，ⅡB、Ⅱ，ⅢC、I，ⅢD、I，Ⅱ，Ⅲ標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：I的敘述是錯(cuò)誤的，因?yàn)槿绻邢驁D構(gòu)成雙向有向環(huán)時(shí)，則從任一頂點(diǎn)出發(fā)均能訪問到每個(gè)頂點(diǎn)，但該圖卻非完全圖。Ⅱ、Ⅲ的敘述顯然是正確的。7、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中()。A、第i行非∞的元素之和B、第i列非∞的元素之和C、第i行非∞且非0的元素個(gè)數(shù)D、第i列非∞且非0的元素個(gè)數(shù)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：有向圖的鄰接矩陣中，0和∞表示的都不是有向邊，而入度是由鄰接矩陣的列中元素計(jì)算出來的。8、在一個(gè)無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的()倍。A、1／2B、1C、2D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在無向圖中，一條邊計(jì)入兩個(gè)頂點(diǎn)的度數(shù)。9、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的()算法。A、前序遍歷B、中序遍歷C、后序遍歷D、按層遍歷標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：由圖的深度優(yōu)先遍歷算法和二叉樹的前序遍歷可知選A。10、任何一個(gè)無向連通圖()最小生成樹。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：無向連通圖應(yīng)有一棵或多棵最小生成樹。11、判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用的是()。A、求關(guān)鍵路徑的方法B、求最短路徑的迪杰斯特拉方法C、深度優(yōu)先遍歷算法D、廣度優(yōu)先遍歷算法標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：當(dāng)有向圖中無回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序(退出DFSTra—verse算法)即為逆向的拓?fù)湫蛄小?2、有n個(gè)頂點(diǎn)e條邊的無向圖，采用鄰接表存儲(chǔ)時(shí)，有()個(gè)表頭結(jié)點(diǎn)，有()個(gè)鏈表結(jié)點(diǎn)。A、n，2eB、n，2e+1C、n-1，2eD、n-1，2e+1標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)鄰接表的結(jié)構(gòu)，無向圖對(duì)應(yīng)的鄰接表有n個(gè)表頭結(jié)點(diǎn)，有2e個(gè)鏈表結(jié)點(diǎn)(每條邊對(duì)應(yīng)兩個(gè)鏈表結(jié)點(diǎn))。13、對(duì)于由n個(gè)頂點(diǎn)組成的有向完全圖來說，圖中共包含()條邊，對(duì)于由n個(gè)頂點(diǎn)組成的無向完全圖來說，圖中共包含()條邊。A、n，n(n一1)B、n，n(n—1)／2C、2n，n(n—1)D、n(n一1)，n(n一1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：由完全圖的定義可知本題答案為D。14、在一個(gè)()圖中尋找拓?fù)湫蛄械倪^程稱為()。A、有向，拓?fù)渑判駼、無向，拓?fù)渑判駽、有向，最短路徑搜索D、無向，最短路徑搜索標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：尋找拓?fù)湫蛄芯褪峭負(fù)渑判?，只能?duì)有向圖進(jìn)行拓?fù)渑判颉?5、用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)vi和vj之間是否有長(zhǎng)度為m的路徑相連，則只要檢查()的第i行第j列的元素是否為零即可。A、mAB、AC、AmD、Am-1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的鄰接矩陣存儲(chǔ)。在圖的鄰接矩陣中，兩點(diǎn)之間有邊，則值為1，否則為0。本題只要考慮Am=A×A×…×A(m個(gè)A矩陣相乘后的乘積矩陣)中(i，j)的元素值是否為0就行了。16、當(dāng)各邊上的權(quán)值()時(shí)，BFS算法可用來解決單源最短路徑問題。A、均相等B、均互不相等C、不一定相等D、不確定標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的BFS算法。BFS是從根結(jié)點(diǎn)開始，沿著樹的寬度遍歷樹的結(jié)點(diǎn)，如果所有結(jié)點(diǎn)均被訪問，則算法中止。當(dāng)各邊上的權(quán)值相等時(shí)，計(jì)算邊數(shù)即可，所以選A。17、下面關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的敘述中正確的是()。A、用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)B、用鄰接矩陣存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)C、用鄰接表存儲(chǔ)圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)D、用鄰接表存儲(chǔ)圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：鄰接矩陣法的基本思想是對(duì)于有n個(gè)頂點(diǎn)的圖，用一維數(shù)組Vexs[n]存儲(chǔ)頂點(diǎn)信息，用二維數(shù)組A[n][n]存儲(chǔ)頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在Vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素A[i][j]存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。鄰接表法的基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。第i個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊(對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧)。18、在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)vi在頂點(diǎn)vj之前，則下列情形不可能出現(xiàn)的是()。A、G中有弧＜vi，vj＞B、G中有一條從vi到vj的路徑C、G中沒有弧＜vi，vj＞D、G中有一條從vj到vi的路徑標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的拓?fù)渑判?。根?jù)拓?fù)渑判虻亩x，若頂點(diǎn)vi與頂點(diǎn)vj有一條弧，則拓?fù)湫蛄兄许旤c(diǎn)vi必在頂點(diǎn)vj之前。若有一條從vj到vi的路徑，則頂點(diǎn)vi不可能在頂點(diǎn)vj之前。所以應(yīng)選D。19、以下關(guān)于圖的說法中正確的是()。I．一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等Ⅱ．用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)Ⅲ．無向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的A、I，ⅡB、Ⅱ，ⅢC、I，ⅢD、僅有Ⅱ標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：說法I是正確的，鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中的邊的個(gè)數(shù)。說法Ⅱ是正確的，鄰接矩陣的空間復(fù)雜度為O(n2)，與邊的個(gè)數(shù)無關(guān)。說法Ⅲ是錯(cuò)誤的，有向圖的鄰接矩陣不一定是不對(duì)稱的，例如，有向完全圖的鄰接矩陣就是對(duì)稱的。20、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是()。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C、所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D、某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是圖的關(guān)鍵路徑。在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具有最大路徑長(zhǎng)度(該路徑上的各個(gè)活動(dòng)所持續(xù)的時(shí)間之和)的路徑稱為關(guān)鍵路徑，并且不只一條。關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。A、C、D的說法都正確。但任何一個(gè)關(guān)鍵活動(dòng)提前完成，不一定會(huì)影響關(guān)鍵路徑，所以根據(jù)題意應(yīng)選B。21、一個(gè)二部圖的鄰接矩陣A是一個(gè)()類型的矩陣。A、n×n矩陣B、分塊對(duì)稱矩陣C、上三角矩陣D、下三角矩陣標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是二部圖的定義與存儲(chǔ)。二部圖定義為：若能將無向圖G=的頂點(diǎn)集V劃分成兩個(gè)子集V1和V2(V1∩V2=)，使得G中任何一條邊的兩個(gè)端點(diǎn)一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖。由于其特點(diǎn)，其存儲(chǔ)矩陣必為分塊對(duì)稱的，所以選B。22、求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為()。A、O(n)B、O(n+c)C、O(n2)D、O(n3)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：暫無解析23、下列4組含C1—C7的結(jié)點(diǎn)序列中，()是下圖所示的有向圖的拓?fù)湫蛄?。A、C1，C2，C6，C7，C5，C4，C3B、C1，C2，C6，C3，C4，C5，C7C、C1，C4，C2，C3，C5，C6，C7D、C5，C7，C4，C1，C2，C3，C6標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：考查拓?fù)渑判虻乃惴āＲ?開頭的拓?fù)渑判蜻^程，如下圖所示：以5開頭的拓?fù)渑判蜻^程，答案中的過程如下圖所示：24、如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有()棵生成樹。A、n2B、nC、n—1D、1標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：因?yàn)閚個(gè)頂點(diǎn)構(gòu)成的環(huán)共有n條邊，去掉其中任意一條便是一棵生成樹，共有n種情況，所以可以有n棵不同的生成樹。25、如下圖所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有()個(gè)。①aebfdc②acfdeb③aedfcb④aefdbc⑤aecfdbA、5B、4C、3D、2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：本題中，符合深度優(yōu)先遍歷順序的是1和5，其他三個(gè)序列均不符合。26、無向圖G有23條邊，度為4的頂點(diǎn)有5個(gè)，度為3的頂點(diǎn)有4個(gè)，其余都是度為2的頂點(diǎn)，則圖G最多有()個(gè)頂點(diǎn)。A、11B、12C、15D、16標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：由于在具有n個(gè)頂點(diǎn)e條邊的無向圖中，有，故可求得度為2的頂點(diǎn)數(shù)為7個(gè)，從而最多有16個(gè)頂點(diǎn)。27、對(duì)AOE網(wǎng)絡(luò)中有關(guān)關(guān)鍵路徑的敘述中，正確的是()。A、從開始頂點(diǎn)到完成頂點(diǎn)的具有最大長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最短時(shí)間B、從開始頂點(diǎn)到完成頂點(diǎn)的具有最小長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最短時(shí)間C、從開始頂點(diǎn)到完成頂點(diǎn)的具有最大長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最長(zhǎng)時(shí)間D、從開始頂點(diǎn)到完成頂點(diǎn)的具有最小長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最長(zhǎng)時(shí)間標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查關(guān)鍵路徑的定義。關(guān)鍵路徑：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(路徑上各活動(dòng)持續(xù)時(shí)間之和)。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。28、以下關(guān)于圖的敘述中，正確的是()。A、強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有弧B、圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點(diǎn)數(shù)C、無向圖的連通分量指無向圖中的極大連通子圖D、假設(shè)有圖G={V，{E}}，頂點(diǎn)集V’∈V，E’∈E，則V’和{E’}構(gòu)成G的子圖標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有路徑，但未必有弧，A錯(cuò)誤。圖與樹的區(qū)別是邏輯上的，而不是邊數(shù)的區(qū)別，圖的邊數(shù)也可能小于樹的邊數(shù)。若E’中的邊對(duì)應(yīng)的頂點(diǎn)不是V’中的元素時(shí)，則V’和{E’}無法構(gòu)成圖，D錯(cuò)誤。29、假設(shè)有n個(gè)頂點(diǎn)e條邊的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)v相關(guān)的所有邊的時(shí)間復(fù)雜度為()。A、O(n)B、O(e)C、O(n+e)D、O(ne)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：刪除與某項(xiàng)點(diǎn)v相關(guān)的所有邊的過程如下：先刪除下標(biāo)為v的頂點(diǎn)表結(jié)點(diǎn)的單鏈表，出邊數(shù)最多為n—1，對(duì)應(yīng)時(shí)間復(fù)雜度為O(n)，再掃描所有邊表結(jié)點(diǎn)，刪除所有的入邊，對(duì)應(yīng)時(shí)間復(fù)雜度為O(e)。故總的時(shí)間復(fù)雜度為O(n+e)。30、若G是一個(gè)具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G的結(jié)點(diǎn)數(shù)至少是()。A、11B、10C、9D、8標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：n個(gè)頂點(diǎn)構(gòu)成的無向圖中，邊數(shù)≤n(n一1)／2，將e=36代入，有n≥9，現(xiàn)已知無向圖是非連通的，則n至少為10。31、已知有向圖G=(V，A)，其中V={a，b，c，d，e}，A={，，，，，}。對(duì)該圖進(jìn)行拓?fù)渑判颍旅嫘蛄兄胁皇峭負(fù)渑判虻氖?)。A、a，d，c，b，eB、d，a，b，c，eC、a，b，d，c，eD、a，b，c，d，e標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：選項(xiàng)D中，刪去a、b及其對(duì)應(yīng)的出邊后，c的入度不為0，因此有邊，故不是拓?fù)湫蛄小＿x項(xiàng)A、B、C均為拓?fù)湫蛄小＝獯鸨绢愵}時(shí)，建議讀者根據(jù)邊集合畫出草圖。32、用有向無環(huán)圖描述表達(dá)式(A+B)*((A+B)／A)，至少需要頂點(diǎn)的數(shù)目為()。A、5B、6C、8D、9標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是有向無環(huán)圖的定義。有向無環(huán)圖是一個(gè)無環(huán)的有向圖，可以用來表示公共子表達(dá)式，本題中出現(xiàn)的5個(gè)字符作為5個(gè)頂點(diǎn)，其中A+B和A可共用，所以至少5個(gè)即可，選A。33、鄰接多重表的存儲(chǔ)結(jié)構(gòu)和十字鏈表類似，也是由頂點(diǎn)表和邊表組成，每一條邊用一個(gè)結(jié)點(diǎn)表示，其頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)和邊表結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：關(guān)于圖中各個(gè)域的說明，不正確的是()。A、vertex存儲(chǔ)的是結(jié)點(diǎn)的數(shù)值域的內(nèi)容B、firstedge域指示第一條依附于該頂點(diǎn)的邊C、mark指向下一條依附于結(jié)點(diǎn)的邊D、info為指向和邊相關(guān)的各種信息的指針域標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：頂點(diǎn)表由兩個(gè)域組成，vertex域存儲(chǔ)和該頂點(diǎn)相關(guān)的信息，firstedge域指示第一條依附于該頂點(diǎn)的邊。邊表結(jié)點(diǎn)由六個(gè)域組成：mark為標(biāo)記域，用以標(biāo)記該條邊是否被搜索過；ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置；iIink指向下一條依附于頂點(diǎn)ivex的邊；jlink指向下一條依附于頂點(diǎn)jvex的邊：info為指向和邊相關(guān)的各種信息的指針域。34、以下關(guān)于十字鏈表的說法中，不正確的是()。A、十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、行指針row為矩陣中的行位置，列指針col為矩陣中的列位置C、數(shù)值val為矩陣中的值D、right指針指向矩陣中的行位置，down指針指向矩陣中的列位置標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：right指向右側(cè)的一個(gè)非零元素，down指向下側(cè)的一個(gè)非零元素。二、綜合應(yīng)用題(本題共15題，每題1.0分，共15分。)35、證明：具有n個(gè)頂點(diǎn)和多于n一1條邊的無向連通圖G一定不是樹。標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的定義。具有n個(gè)頂點(diǎn)n—1條邊的無向連通圖是自由樹，即沒有確定根結(jié)點(diǎn)的樹，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n一1條，因一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹(在圖論中樹定義為無回路的連通圖)。知識(shí)點(diǎn)解析：暫無解析36、證明：對(duì)有向圖的頂點(diǎn)適當(dāng)?shù)鼐幪?hào)，可使其鄰接矩陣為下三角形且主對(duì)角線為全0的充要條件是該圖為無環(huán)圖。標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是無環(huán)圖的定義。根據(jù)題意，該有向圖頂點(diǎn)編號(hào)的規(guī)律是讓弧尾頂點(diǎn)的編號(hào)大于弧頭頂點(diǎn)的編號(hào)。由于不允許從某頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角線元素均為0。先證明該命題的充分條件。由于弧尾頂點(diǎn)的編號(hào)均大于弧頭頂點(diǎn)的編號(hào)，在鄰接矩陣中，非零元素(A[i][j]=1)自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點(diǎn)編號(hào)大于弧尾頂點(diǎn)編號(hào)的弧，否則，就必然存在環(huán)路。(對(duì)該類有向無環(huán)圖頂點(diǎn)編號(hào)，應(yīng)按頂點(diǎn)出度順序編號(hào)。)知識(shí)點(diǎn)解析：暫無解析37、關(guān)于圖(Graph)的一些問題：(1)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?最少有多少條邊?(2)表示有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素?是否為稀疏矩陣?標(biāo)準(zhǔn)答案：(1)n(n—1)，n(2)106，不一定是稀疏矩陣提示：此題考查的知識(shí)點(diǎn)是圖的相關(guān)術(shù)語(yǔ)。(1)在有向圖G中，如果對(duì)于每一對(duì)vi，vj，屬于V，vi不等于vj，從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖。最多邊是所有的頂點(diǎn)每對(duì)之間都有邊，邊數(shù)為n(n一1)；最少只有一個(gè)方向有邊，為n。(2)元素個(gè)數(shù)為矩陣的大小，即106，稀疏矩陣的定義是非零個(gè)數(shù)遠(yuǎn)小于該矩陣元素個(gè)數(shù)，且分布無規(guī)律，不一定稀疏。知識(shí)點(diǎn)解析：暫無解析38、如何對(duì)有向圖中的頂點(diǎn)號(hào)重新安排可使得該圖的鄰接矩陣中所有的1都集中到對(duì)角線以上?標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖頂點(diǎn)度數(shù)?？梢园锤黜旤c(diǎn)的出度進(jìn)行排序。n個(gè)頂點(diǎn)的有向圖，其頂點(diǎn)最大出度是n一1，最小出度為0。這樣排序后，出度最大的頂點(diǎn)編號(hào)為1，出度最小的頂點(diǎn)編號(hào)為n之后，進(jìn)行調(diào)整，即若存在弧，而頂點(diǎn)j的出度大于頂點(diǎn)i的出度，則將j的編號(hào)排在頂點(diǎn)i的編號(hào)之前。知識(shí)點(diǎn)解析：暫無解析39、假定圖G=(V，E)是有向圖，V={1，2，…，N}，N≥1，G以鄰接矩陣方式存儲(chǔ)，G的鄰接矩陣為A，即A是一個(gè)二維數(shù)組。如果i到j(luò)有邊，則A[i，j]=1，否則A[i，j]=0。請(qǐng)給出一個(gè)算法思想，該算法能判斷G是否是非循環(huán)圖(即G中是否存在回路)，要求算法的時(shí)間復(fù)雜性為O(n2)。標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。采用深度優(yōu)先遍歷算法，在執(zhí)行DFS(v)時(shí)，若在退出DFS(v)前碰到某頂點(diǎn)u，其鄰接點(diǎn)是已經(jīng)訪問的頂點(diǎn)v，則說明v的子孫u有到v的回邊，即說明有環(huán)；否則，無環(huán)。知識(shí)點(diǎn)解析：暫無解析40、對(duì)一個(gè)圖進(jìn)行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些?標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。遍歷不唯～的因素有：開始遍歷的頂點(diǎn)不同；存儲(chǔ)結(jié)構(gòu)不同；在鄰接表情況下鄰接點(diǎn)的順序不同。知識(shí)點(diǎn)解析：暫無解析41、G=(V，E)是一個(gè)帶有權(quán)的連通圖，如圖所示。(1)什么是G的最小生成樹?(2)G如圖所示，請(qǐng)找出G的所有最小生成樹。標(biāo)準(zhǔn)答案：(1)無向連通圖的生成樹包含圖中全部n個(gè)頂點(diǎn)，以及足以使圖連通的n—1條邊。而最小生成樹則是各邊權(quán)值之和最小的生成樹。(2)最小生成樹有兩棵。下面給出頂點(diǎn)集合和邊集合，編以三元組(Vi，Vj，W)形式，其中W代表權(quán)值。V(G)={1，2，3，4，5}E1(G)={(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)}；E2(G)={(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)}知識(shí)點(diǎn)解析：暫無解析42、對(duì)于如下的加權(quán)有向圖，給出算法Dijkstra產(chǎn)生的最短路徑的支撐樹，設(shè)頂點(diǎn)A為源點(diǎn)，并寫出生成過程。標(biāo)準(zhǔn)答案：頂點(diǎn)A到頂點(diǎn)B、C、D、E的最短路徑依次是3、18、38、43，按Dijkstra所選頂點(diǎn)過程是B、C、D、E。支撐樹的邊集合為{，，，}，具體分析如下表所示。知識(shí)點(diǎn)解析：暫無解析43、(1)對(duì)于有向無環(huán)圖，敘述求拓?fù)溆行蛐蛄械牟襟E。(2)對(duì)于以下的圖，寫出它的4個(gè)不同的拓?fù)溆行蛐蛄?。?biāo)準(zhǔn)答案：(1)對(duì)有向圖，求拓?fù)湫蛄胁襟E為：①在有向圖中選一個(gè)沒有前驅(qū)(即入度為零)的頂點(diǎn)并輸出。②在圖中刪除該頂點(diǎn)及所有以它為尾的弧。③重復(fù)①和②步，直至全部頂點(diǎn)輸出，這時(shí)拓?fù)渑判蛲瓿?；否則，圖中存在環(huán)，拓?fù)渑判蚴　?2)從入度為O的頂點(diǎn)開始，當(dāng)有多個(gè)頂點(diǎn)可以輸出時(shí)，將其按序從上往下排列，這樣不會(huì)丟掉～種拓?fù)湫蛄小捻旤c(diǎn)1開始的可能的拓?fù)湫蛄袨?2345678、12354678、13456278、13546278。提示：此題考查的知識(shí)點(diǎn)是拓?fù)渑判颉ＶR(shí)點(diǎn)解析：暫無解析44、試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑(i≠j)。(注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。)標(biāo)準(zhǔn)答案：算法1：intvisited[]=0：／／全局變量，訪問數(shù)組初始化intdfs(AdjListg，vi){／／以鄰接表存儲(chǔ)的有向圖g，判斷vi到vj是否有通路，返回1或0visited[vi]=1；／／visited是訪問數(shù)組，設(shè)頂點(diǎn)的信息就是頂點(diǎn)編號(hào)P=g[vi]．firstarc；／／第一個(gè)鄰接點(diǎn)while(P!=null){j=p一>adjvex；if(vj==j){flag=1；return(1)；}／／vi和vj有通路if(visited[j]==0)dfs(g，j)；P=P一>next：}／／whileif(!flag)return(0)；}算法2：輸出vi到vj的路徑，其思想是用一個(gè)棧存放遍歷的頂點(diǎn)，遇到頂點(diǎn)vj時(shí)輸出路徑。voiddfs(AdjListg，inti){／／頂點(diǎn)vi和頂點(diǎn)vj間是否有路徑，如有，則輸出inllop=0，stack[]；／／stack是存放頂點(diǎn)編號(hào)的棧visited[i]=1；／／visited數(shù)組在進(jìn)入dfs前已初始化stack[++top]=i；P=g[i]．firstarc；／／求第一個(gè)鄰接點(diǎn)while(P){if(p一>adjvex==j){stack[++top]=j；printf(”頂點(diǎn)vi和vj的路徑為：＼n”)；for(i=1；i<=top；i++)printf(”％4d”，stack[i])；exit(0)：}elseif(visited[p一>adjvex]==0){dfs(g，g一>adjvex)；top一一；P=p一>next；}}}算法3：非遞歸算法求解。intJudge(AdjListg，inti，j){／／判斷n個(gè)頂點(diǎn)以鄰接表示的有向圖g中，頂點(diǎn)vi各vj是否有路徑，／／有則返回1，否則返回O。for(i=1；i<=n；i++)visited[i]=0i／／訪問標(biāo)記數(shù)組初始化intstack[]，top=0；stack[++top]=vi；while(top>0){k=stack[top一一]；P=g[k]．firstarc；while(P!=null&&visited[p一>adjvex]==1)p=p一>next；／／查第k個(gè)鏈表中第一個(gè)未訪問的弧結(jié)點(diǎn)if(P==null)top一一：else{i=p一>adjvex；if(i==j)return(1)；／／頂點(diǎn)vi和vj間有路徑else{visited[i]=1；stack[++top]=i；}}}whilereturn(0)；}／／頂點(diǎn)vi和vj間無通路知識(shí)點(diǎn)解析：暫無解析45、假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有向回路，若存在，則以頂點(diǎn)序列的方式輸出該回路(找到一條即可)。(注意：圖中不存在頂點(diǎn)到自己的弧)標(biāo)準(zhǔn)答案：用鄰接矩陣存儲(chǔ)時(shí)，可用以下方法實(shí)現(xiàn)：voidPrint(intv，intstart){／／輸出從頂點(diǎn)start開始的回路for(i：1；i<=n：i++)if(g[v][i]!=0&&visited[i]==1){／／若存在邊(v，i)，且頂點(diǎn)i的狀態(tài)為1printf(”％d．t，V)；if(i==start)printf(”＼n”)：elsePrint(i，start)：break；}／／if}／／Printvoiddfs(intv){visited[v]=i；for(j=1；j<=n；j++)if(g[v][j]!=0)／／存在邊(v，j)if(visited[j]!=1){if(!visited[j])dfs(j)；}／／ifelse{cycle=1；Print(j，j)：}visited[v]=2：}voidfind_cycle(){／／判斷是否有回路，有則輸出鄰接矩陣。visited數(shù)組為全局變量for(i=1；i<=n；i++)visited[i]=0；for(i=1；i<=n；i++)if(!visited[i])dfs(i)：}知識(shí)點(diǎn)解析：暫無解析46、已有鄰接表表示的有向圖，請(qǐng)編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡(jiǎn)單路徑，若有則打印出該路徑上的頂點(diǎn)。標(biāo)準(zhǔn)答案：voidAllpath(AdjListg，vertypeU，vertypev){／／求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡(jiǎn)單路徑，初始調(diào)用形式inttop=0，S[]：S[++top]=u；visited[U]=1；while(top>0||P){P=g[S[top]]．firstarc；／／第一個(gè)鄰接點(diǎn)while(Pf=null&&visited[p一>adjvex]==1)P=p->next；／／下一個(gè)訪問鄰接點(diǎn)表if(P==null)top--：／／退棧else{i=p一>adjvex;／／取鄰接點(diǎn)(編號(hào))if(i==V){／／找到從u到v的一條簡(jiǎn)單路徑，輸出for(k=1；k<=top；k++)printf(”％3d”，s[k])：printf(tt％3d＼n”，v)：}／／ifelse{visited[i]=1；s[++top]=i；}／／else深度優(yōu)先遍歷}／／else}／／while}知識(shí)點(diǎn)解析：暫無解析47、“破圈法”是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請(qǐng)給出用“破圈法”求解給定的帶權(quán)連通無向圖的一棵最小代價(jià)生成樹的詳細(xì)算法，并用程序?qū)崿F(xiàn)你所給出的算法。(注意：圈就是回路)標(biāo)準(zhǔn)答案：voidSpnTree(AdjListg){／／用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價(jià)生成樹typedefstruct{inti，j，w：}node；／／設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整數(shù)nodeedge[]；scanf(”％d％d”，&e，&n)；／／輸入邊數(shù)和項(xiàng)點(diǎn)數(shù)for(i=1；i<=e；i++)／／輸入e條邊：頂點(diǎn)，權(quán)值seanf(”％d％d％d”，&edge[i]．i，&edge[i]．j，&edge[i]．W)；for(i=2；i<=e；i++){／／按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序edge[0]=edge[i]；j=i一1；while(edge[j]．W=n){／／破圈，直到邊數(shù)e=n一1if(connect(k))／／刪除第k條邊若仍連通fedge[k]．W=0；eg--；}／／測(cè)試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++；／／下條邊}／／while}connect()是測(cè)試圖是否連通的函數(shù)，可用DFS函數(shù)或BFS函數(shù)實(shí)現(xiàn)，若是連通圖，一次進(jìn)入DFS函數(shù)或BFS函數(shù)就可遍歷完全部頂點(diǎn)，否則，因?yàn)閯h除該邊而使原連通圖成為兩個(gè)連通分量時(shí)，該邊不應(yīng)刪除。“破圈”結(jié)束后，可輸出edge中W不為0的n一1條邊。知識(shí)點(diǎn)解析：暫無解析48、設(shè)計(jì)一個(gè)算法求圖的中心點(diǎn)。設(shè)v是有向圖G的一個(gè)頂點(diǎn)，把v的偏心度定義為：MAx{從ω到v的最短距離{ω屬于V(G)}如果v是有向圖G中具有最小偏心度的頂點(diǎn)，則稱頂點(diǎn)v是G的中心點(diǎn)。標(biāo)準(zhǔn)答案：設(shè)C是有向圖G的鄰接矩陣，求最小偏心度的頂點(diǎn)的步驟如下：(1)利用Floyd算法求出每對(duì)頂點(diǎn)之間的最短路徑矩陣A；(2)對(duì)矩陣A求出每列i的最大值，得到頂點(diǎn)i的偏心度；(3)在這n個(gè)頂點(diǎn)的偏心度中，求出最小偏心度的頂點(diǎn)k，即為圖G的中心點(diǎn)。對(duì)應(yīng)的算法如下：intCenter(MGraph&G)}intA[MAXV][MAXV]，B[MAXV]；inti，j，k，m；for(i=0；i知識(shí)點(diǎn)解析：暫無解析49、對(duì)于一個(gè)使用鄰接表存儲(chǔ)的有向圖G，可以利用深度優(yōu)先遍歷方法，對(duì)該圖中結(jié)點(diǎn)進(jìn)行拓?fù)渑判?。其基本思想是：在遍歷過程中，每訪問一個(gè)頂點(diǎn)，就將其鄰接到的頂點(diǎn)的入度減1，并對(duì)其未訪問的、入度為0的鄰接到的頂點(diǎn)進(jìn)行遞歸。(1)給出完成上述功能的圖的鄰接表定義。(2)定義在算法中使用的全局輔助數(shù)組。(3)寫出在遍歷圖的同時(shí)進(jìn)行拓?fù)渑判虻乃惴ā?biāo)準(zhǔn)答案：(1)鄰接表定義typedefstructArcNode{intadjvex;structArcNode*next；}ArcNode；typedefstructVNode{vertypedata；ArcNode*firstarc：}VNode，AdjList[MAX]；(2)全局?jǐn)?shù)組定義intvisited[]=0；finished[]=0；flag=1；／／flag測(cè)試拓?fù)渑判蚴欠癯晒rcNode*final=null：／／final是指向頂點(diǎn)鏈表的指針，初始化為0(3)算法voiddfs(AdjListg，vertypeV){／／以頂點(diǎn)v開始深度優(yōu)先遍歷有向圖g，頂點(diǎn)信息就是頂點(diǎn)編號(hào)ArcNode*t：／／指向邊結(jié)點(diǎn)的臨時(shí)變量printf(”％d”，V)；visited[v]=1；P=g[v]．firstarc；while(P!=null){j=p一>adjvex；if(visited[j]==l&&finished[j]==0)flag=0；／／dfs結(jié)束前出現(xiàn)回邊elseif(visited[j]==0){dfs(g，j)；finished[j]=1；}P=P一>next：}／／whilet=(ArcNode*)malloc(sizeof(ArcNode))；／／申請(qǐng)邊結(jié)點(diǎn)t一>adjvex=v：t一>next=final；final=t；／／將該頂點(diǎn)插入鏈表}／／dfs結(jié)束intdfs_Topsort(Adjlistg){／／對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖進(jìn)行拓?fù)渑判颍負(fù)涑晒Ψ祷?，否則返回0i=1：while(flag&&i<=n)if(visited．[i]==0){dfs(g，i)；finished[i]=1；}／／ifreturn(flag)；}知識(shí)點(diǎn)解析：暫無解析計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬試卷第2套一、單選題(本題共22題，每題1.0分，共22分。)1、在下面關(guān)于樹的相關(guān)概念的敘述中，正確的是()。A、只有一個(gè)結(jié)點(diǎn)的二叉樹的度為1B、二叉樹的度一定為2C、二叉樹的左右子樹可任意交換D、深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：只有一個(gè)結(jié)點(diǎn)的二叉樹的度為零。二叉樹的度可以為0、1、2：二叉樹的左右子樹不能任意交換。2、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D／E，后綴形式為ABC*+DE／一，其前綴形式為()。A、一A+B*C／DEB、一A+B*CD／EC、-+*ABC／DED、-+A*BC／DE標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)題目給出的中綴和后綴表達(dá)式可以得到其算術(shù)表達(dá)式為：(A+B*C)一D／E，前綴表達(dá)式：-+A*BC／DE。3、算術(shù)表達(dá)式a+b*(c+d／e)轉(zhuǎn)為后綴表達(dá)式后為()。A、ab+cde／*B、abcde／+*+C、abcde／*++D、abcde*／++標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)表達(dá)式a+b*(c+d／e)可知其后綴表達(dá)式為abcde／+*+。4、某二叉樹的先序遍歷序列為IJKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列是()。A、JLKMNOIB、LKNJOMIC、LKJNOMID、LKNOJMI標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：由先序和中序遍歷序列確定一棵二叉樹，再給出這棵二叉樹的后序遍歷序列。由此圖可以確認(rèn)后序遍歷的序列為L(zhǎng)KJNOMI。5、設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為P，P的右子樹結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是()。A、m-nB、m-n-1C、n+1D、條件不足，無法確定標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：F對(duì)應(yīng)的二叉樹共有m個(gè)結(jié)點(diǎn)，右子樹上n個(gè)，左子樹上有(m一n一1)個(gè)，第一株樹包括根和左子樹，共(m一n)個(gè)。6、二叉樹若用順序方法存儲(chǔ)，則下列四種算法中運(yùn)算時(shí)間復(fù)雜度最小的是()。A、先序遍歷二叉樹B、判斷兩個(gè)指定位置的結(jié)點(diǎn)是否在同一層上C、層次遍歷二叉樹D、根據(jù)結(jié)點(diǎn)的值查找其存儲(chǔ)位置標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：選項(xiàng)A、C、D運(yùn)算的時(shí)間復(fù)雜度都是O(n)，而選項(xiàng)B的運(yùn)算的時(shí)間復(fù)雜度為O(1)，因?yàn)閷?duì)于指定位置p和q的兩個(gè)結(jié)點(diǎn)，判斷是否在同一層上，只需判斷兩者[log2p]=[log2q]是否成立。7、設(shè)某二叉樹中只有度為0和度為2的結(jié)點(diǎn)，如果此二叉樹的高度為100，那么此二叉樹中所包含的結(jié)點(diǎn)數(shù)最少為()。A、188B、200C、199D、201標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：除根結(jié)點(diǎn)層只有1個(gè)結(jié)點(diǎn)外，其他各層均有兩個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)總數(shù)=2×(100一1)+1=199。8、樹是結(jié)點(diǎn)的有限集合，一棵樹中有()根結(jié)點(diǎn)。A、有0個(gè)或1個(gè)B、有0個(gè)或多個(gè)C、有且只有一個(gè)D、有1個(gè)或1個(gè)以上標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)樹的基本定義可知，每個(gè)樹只能有且只有一個(gè)根結(jié)點(diǎn)。9、下列二叉排序樹中，滿足平衡二叉樹定義的是()。A、

B、

C、

D、

標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：考查平衡二叉樹的定義。根據(jù)平衡二叉樹的定義有，任意結(jié)點(diǎn)的左右子樹高度差的絕對(duì)值不超過1。而其余三個(gè)選項(xiàng)均可以找到不符合的結(jié)點(diǎn)。10、把樹的根結(jié)點(diǎn)的層數(shù)定義為1，其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上I。設(shè)T是一棵二叉樹，Ki和Kj是T中子結(jié)點(diǎn)數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們所在的層數(shù)分別為λKi和λKj，當(dāng)關(guān)系式|λKi一λKj|≤1一定成立時(shí)，則稱T為一棵()。A、滿二叉樹B、二叉查找樹C、平衡二叉樹D、完全二叉樹標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：此題干的敘述符合平衡二叉樹的定義。11、設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是()。A、M1B、M1+M2C、M3D、M2+M3標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，第一棵樹的根結(jié)點(diǎn)作為此二叉樹的根結(jié)點(diǎn)，第一棵樹除根結(jié)點(diǎn)外其他結(jié)點(diǎn)時(shí)此二叉樹的左子樹。二叉樹的右子樹為第二棵樹和第二棵樹構(gòu)成的，因此結(jié)點(diǎn)數(shù)為M2+M3。12、若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是()。A、10B、11C、16D、不確定標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)可知，度為0的結(jié)點(diǎn)個(gè)數(shù)比度為2結(jié)點(diǎn)個(gè)數(shù)多一個(gè)，即n0=n2+1。13、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有()個(gè)度為2的結(jié)點(diǎn)。A、8B、9C、10D、11標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)n0=n2+1，可知度為2的結(jié)點(diǎn)個(gè)數(shù)為9。14、在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為O的結(jié)點(diǎn)數(shù)為()個(gè)。A、4B、5C、6D、7標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：一棵度為3的樹，總結(jié)點(diǎn)數(shù)n=n0+n1+n2+n3，而總分支總數(shù)為n0×0+n1×2+n2×1+n3×2，由于分支總數(shù)加1為結(jié)點(diǎn)總數(shù)，可得出n0=6。15、已知一棵二叉樹，共有n個(gè)結(jié)點(diǎn)，那么此二叉樹的高度為()。A、nlog2nB、log2nC、[log2n]+1D、不確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：已知一棵二叉樹共有n個(gè)結(jié)點(diǎn)，但二叉樹的形式?jīng)]有給出，因此，二叉樹的高度不能確定。16、已知一棵二叉樹，第m層上最多含有結(jié)點(diǎn)數(shù)為()。A、2mB、2m-1一1C、2m-1D、2m-1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，二叉樹的第m層上最多有2m-1。17、有關(guān)二叉樹下列說法正確的是()。A、二叉樹就是度為2的樹B、一棵二叉樹的度可以小于2C、二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D、二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查二叉樹的概念。18、一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是()。A、CABDEFGB、ABCDEFGC、DACEFBGD、BAECFDG標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由題可得A為根結(jié)點(diǎn)，并且B為A的孩子結(jié)點(diǎn)。選項(xiàng)A，C應(yīng)為A的左孩子，其前序序列應(yīng)為AC……。選項(xiàng)B，當(dāng)B為A的右孩子，C為B的右孩子時(shí)，滿足題目要求。選項(xiàng)C，類似選項(xiàng)A，其前序序列應(yīng)為AD……。選項(xiàng)D，B為A的左孩子，C為A的右子樹的根，E為C的左子樹，F(xiàn)DG為C的右子樹，其前序序列應(yīng)為ABEC……。19、已知一個(gè)二叉樹有1025個(gè)結(jié)點(diǎn)，那么由此推斷二叉樹的高h(yuǎn)為()。A、11B、10C、11～1025D、10～1024標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：右完全二叉樹中1025＞210，即最少需要11層，最多需要有1025層。20、一棵完全二叉樹，共有n個(gè)結(jié)點(diǎn)，那么，其葉結(jié)點(diǎn)數(shù)共有()個(gè)。A、n／2B、nC、(n-1)／2D、(n+1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此問題可以利用二叉樹及完全二叉樹的性質(zhì)來求解。設(shè)i、j、k分別為度為0、1、2的結(jié)點(diǎn)數(shù)目，則n=i+j+k。根據(jù)二叉樹的性質(zhì)有i=k+1，即k=i一1，代入上式，得n=2i+j—1，即i=(n-j+1)／2。由于完全二又樹中最多只有一個(gè)度為1的結(jié)點(diǎn)，同時(shí)考慮到i為整數(shù)，(1)當(dāng)j=0時(shí)，此時(shí)n=i+k=2k+1為奇數(shù)，則i=(n+1)／2；(2)當(dāng)j=1時(shí)，此時(shí)n=i+k+1=2k+2為偶數(shù)，則i=(n+1)／2向下取整。所以選D。21、()的遍歷仍需要棧的支持。A、前序線索樹B、中序線索樹C、后序線索樹D、中序線索樹和前序線索樹標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：由于后序遍歷先訪問子樹后訪問根結(jié)點(diǎn)，從本質(zhì)上要求運(yùn)行棧中存放祖先的信息，即使對(duì)二叉樹進(jìn)行后序線索化，仍然不能脫離棧的支持對(duì)此二叉樹進(jìn)行遍歷。22、已知一棵二叉樹高度為h，在此二叉樹中只有度為0和度為2的結(jié)點(diǎn)，那么這棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少為()。A、2hB、2h一1C、2h+1D、h+1標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：暫無解析二、綜合應(yīng)用題(本題共7題，每題1.0分，共7分。)23、已知一個(gè)二叉樹，用二叉鏈表形式存儲(chǔ)，給出此二叉樹建立過程算法(可不描述結(jié)構(gòu)體)。標(biāo)準(zhǔn)答案：二叉樹是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。二叉樹建立過程如下：BiTreeCreat(){／／建立二叉樹的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu)ElemTypex：BiTreebt；scanf(”％d”，&x)；／／本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0)bt=null；elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt一>data=x：bt一>lchild=Creat()；bt一>rchild=Creat()：}elseerror(”輸入錯(cuò)誤”)；return(bt)；}／／結(jié)束BiTree知識(shí)點(diǎn)解析：暫無解析24、判別給定的二叉樹是否是完全二叉樹，并給出設(shè)計(jì)的算法(可不描述結(jié)構(gòu)體)。標(biāo)準(zhǔn)答案：判斷此二又樹是否為完全二叉樹的算法設(shè)計(jì)如下：intJudgeComplete(BiTreebt){／／判斷二叉樹是否是完全二叉樹，如是，返回1；否則，返回0inttag=0；BiTreeP=bt，Q[]：／／Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大if(P==null)return1：QueueInit(Q)；Queueln(Q，P)；／／初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while(!QueueEmpty(Q)){P=QueueOut(Q)：／／出隊(duì)if(p一>lchild&&!tag)QueueIn(Q，P一>lchild)；／／左孩子入隊(duì)else{if(P一>lehild)retum0：／／前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空elsetag=1；／／首次出現(xiàn)結(jié)點(diǎn)為空if(p一>rchild&＆!tag)Queueln(Q，P一>rchild)；／／右孩子入隊(duì)elseif(p一>rchild)return0；elsetag=1：}}／／whilereturn1；}／／JudgeComplete知識(shí)點(diǎn)解析：暫無解析25、以孩子一兄弟表示法存儲(chǔ)的森林的葉子結(jié)點(diǎn)數(shù)(要求描述結(jié)構(gòu))。標(biāo)準(zhǔn)答案：當(dāng)森林(樹)以孩子兄弟表示法存儲(chǔ)時(shí)，若結(jié)點(diǎn)沒有孩子(fch=null)，則它必是葉子，總的葉子結(jié)點(diǎn)個(gè)數(shù)是孩子子樹(fch)上的葉子數(shù)和兄弟(nsib)子樹上葉結(jié)點(diǎn)個(gè)數(shù)之和。typedefstructnode{elemTypedata；／／數(shù)據(jù)域structnode*fch，*nsib；／／孩子與兄弟域}*Tree；intLeaves(Treet){／／計(jì)算以孩子一兄弟表示法存儲(chǔ)的森林的葉子數(shù)if(t)if(t一>fch=：null)／／若結(jié)點(diǎn)無孩子，則該結(jié)點(diǎn)必是葉子return(1+Leaves(t->nsib))；／／返回葉子結(jié)點(diǎn)和其兄弟子樹中的葉子結(jié)點(diǎn)數(shù)elsereturn(Leaves(t->fch)+Leaves(t->nsib))；／／孩子子樹和兄弟子樹中葉子數(shù)之和}知識(shí)點(diǎn)解析：暫無解析26、已知一棵二叉樹的前序序列為：A，B，D，G，J，E，H，C，F(xiàn)，I，K，L；中序序列為：D，J，G，B，E，H，A，C，K，I，L，F(xiàn)。(1)寫出該二又樹的后序序列。(2)畫出該二叉樹。(3)求該二叉樹的高度以及該二叉樹中度為2、1、0的結(jié)點(diǎn)個(gè)數(shù)。標(biāo)準(zhǔn)答案：此題只需從前序序列、中序序列得到唯一確定的二叉樹即可。(1)J，G，D，H，E，B，K，L，I，F(xiàn)，C，A。(2)二叉樹的形式如下圖所示：(3)高度是5，度為0的結(jié)點(diǎn)個(gè)數(shù)為4，度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3。知識(shí)點(diǎn)解析：暫無解析27、有n個(gè)結(jié)點(diǎn)的二叉樹，已知葉結(jié)點(diǎn)個(gè)數(shù)為n0。(1)寫出求度為1的結(jié)點(diǎn)的個(gè)數(shù)的n1的計(jì)算公式。(2)若此樹是深度為k的完全二叉樹，寫出n為最小的公式。(3)若二叉樹中僅有度為0和度為2的結(jié)點(diǎn)，寫出求該二叉樹結(jié)點(diǎn)個(gè)數(shù)n的公式。標(biāo)準(zhǔn)答案：(1)設(shè)度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n=n0+n1+n2。由二叉樹的性質(zhì)n0=n2+1，n=2n0+n1一1，所以度為1的結(jié)點(diǎn)的個(gè)數(shù)n1=n+1一2n0；(2)當(dāng)樹是深度為k的完全二叉樹時(shí)，n的最小值min(n)=2k-1。(3)當(dāng)二叉樹中只有度為0和度為2的結(jié)點(diǎn)時(shí)，n=2n0一1(其中n為樹中的總結(jié)點(diǎn)數(shù)，n0為度為0的結(jié)點(diǎn)數(shù)目)。知識(shí)點(diǎn)解析：暫無解析28、已知一棵樹的結(jié)點(diǎn)表示如下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，畫出對(duì)應(yīng)的二叉樹。標(biāo)準(zhǔn)答案：相應(yīng)的樹如下圖所示：樹到二叉樹的轉(zhuǎn)換規(guī)則如下：(1)樹的根結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)；(2)每個(gè)結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)(最左的子樹)作為該結(jié)點(diǎn)的左孩子；(3)每個(gè)結(jié)點(diǎn)的右孩子為在樹中與該結(jié)點(diǎn)的左孩子鄰近的兄弟，所有具有兄弟關(guān)系的結(jié)點(diǎn)用指針鏈接起來。轉(zhuǎn)換成二叉樹如下圖所示：知識(shí)點(diǎn)解析：暫無解析29、在一棵表示有序集S的二叉搜索樹(binarysearchtree)中，任意一條從根到葉結(jié)點(diǎn)的路徑將S分為3部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合S1；在該路徑上的結(jié)點(diǎn)中的元素組成的集合S2；在該路徑右邊結(jié)點(diǎn)中的元素組成的集合S3。S=S1∪S2∪S3。若對(duì)于任意的a∈S1，b∈S2，c∈S3，是否總有a≤b≤c?為什么?標(biāo)準(zhǔn)答案：不是。如下圖所示的二叉搜索樹：取從4到12的路徑，則S1={1，2，3，7}，S2={4，8，10，12}，S3為空集，取S1中的元素7和S2中的元素4，令a=7，b=4，有a＞b。則上述命題不成立。知識(shí)點(diǎn)解析：暫無解析計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)）模擬試卷第3套一、單選題(本題共24題，每題1.0分，共24分。)1、若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為()。A、(n—1)／2B、n／2C、(n+1)／2D、n標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是順序查找長(zhǎng)度ASL的計(jì)算。假設(shè)表長(zhǎng)度為n，那么查找第i個(gè)數(shù)據(jù)元素需進(jìn)行n—i+1次比較，即Ci=n—i+1。又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1／n，則順序查找算法的平均查找長(zhǎng)度為：所以應(yīng)選C。順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表，平均比較次數(shù)為((1))，二分法查找只適用于查找順序存儲(chǔ)的有序表，平均比較次數(shù)為((2))。在此假定N為線性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。2、(1)A、N+1B、2log2NC、log2ND、N／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：暫無解析3、(2)A、N+1B、2log2NC、log2ND、N／2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是各類查找算法的比較次數(shù)計(jì)算。順序查找法用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗，其ASL=(n+1)／2，即查找成功時(shí)的平均比較次數(shù)約為表長(zhǎng)的一半。二分法查找過程可用一個(gè)稱為判定樹的二叉樹描述，由于判定樹的葉子結(jié)點(diǎn)所在層次之差最多為1，故n個(gè)結(jié)點(diǎn)的判定樹的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相等，均為[log2n]+1。這樣，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過[log2n]+1。所以，(1)應(yīng)選擇D，(2)應(yīng)選C。4、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為()。A、鏈接方式存儲(chǔ)，元素?zé)o序B、鏈接方式存儲(chǔ)，元素有序C、順序方式存儲(chǔ)，元素?zé)o序D、順序方式存儲(chǔ)，元素有序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是折半查找的特點(diǎn)。折半查找要求順序存儲(chǔ)且元素有序，所以應(yīng)選D。5、具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為()。A、3．1B、4C、2．5D、5標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是折半查找的思想。把關(guān)鍵字按完全二叉樹的形式畫出查找樹，按結(jié)點(diǎn)高度計(jì)算比較次數(shù)。12個(gè)結(jié)點(diǎn)可以畫出高度為4的完全二叉樹，1層1個(gè)結(jié)點(diǎn)比較1次，2層2個(gè)結(jié)點(diǎn)比較2次，3層4個(gè)結(jié)點(diǎn)比較3次，4層5個(gè)結(jié)點(diǎn)比較4次，37／12=3．1，應(yīng)選A。6、折半查找的時(shí)間復(fù)雜性為()。A、O(n2)B、O(n)C、O(nlog2n)D、O(log2n)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是折半查找的效率。其查找效率與比較次數(shù)有關(guān)，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過[log2n]+1，所以其效率為O(log2n)，應(yīng)選D。7、當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為()。A、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊C、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊D、數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個(gè)數(shù)需相同標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：分塊查找是將數(shù)據(jù)分成若干塊，塊間有序，塊內(nèi)不必有序。8、下面函數(shù)的功能是實(shí)現(xiàn)分塊查找，空白處應(yīng)該添加的內(nèi)容是()。intBlkSearch(int*nz，intkey，intblock，intBLK，intlen){inti；block=block—1：if(len<=0){puts("表為空!")：return0：}if(BLK>len)BLK=len；for(i=block*BLK；i<(block+1)*BLK&&nz[i]!=0；i++){if(______){printf(”找到第％d個(gè)數(shù)是％d＼n”，i，key)；return0；}}printf(”＼n”)：printf(”查找結(jié)束＼n”)；return0；}A、nz[i]==keyB、nz[i]==BLKC、nz[i]==blockD、nz[i]==0標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：如果當(dāng)前的值與所查找關(guān)鍵字相等，則完成查找。二叉查找樹的查找效率與二叉樹的((1))有關(guān)，在((2))時(shí)其查找效率最低。9、(1)A、高度B、結(jié)點(diǎn)的多少C、樹形D、結(jié)點(diǎn)的位置標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無解析10、(2)A、結(jié)點(diǎn)太多B、完全二叉樹C、呈單枝樹D、結(jié)點(diǎn)太復(fù)雜標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉查找樹的查找效率與樹形有關(guān)，當(dāng)結(jié)點(diǎn)呈單枝樹排列時(shí)效率最低。11、在一棵高度為h的理想平衡二叉樹中，最少含有()個(gè)結(jié)點(diǎn)，最多含有()個(gè)結(jié)點(diǎn)。A、2h2h-1B、2h一12hC、2h+12h一1D、2h-12h一1標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：由平衡二叉樹的特性可知，一棵高度為h的理想平衡二叉樹中，含有結(jié)點(diǎn)數(shù)最少的情形是：前h一1層為滿二叉樹，第h層只有一個(gè)結(jié)點(diǎn)，因而結(jié)點(diǎn)總數(shù)為(2h-1一1)+1=2h-1。含有結(jié)點(diǎn)數(shù)最多的情形是：該樹是一棵高度為h的滿二叉樹，因而結(jié)點(diǎn)總數(shù)為2h一1。12、分別以下列序列構(gòu)造二叉排序樹，與用其他三個(gè)序列所構(gòu)造的結(jié)果不同的是()。A、(100，80，90，60，120，110，130)B、(100，120，110，130，80，60，90)C、(100，60，80，90，120，110，130)D、(100，80，60，90，120，130，110)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：分別根據(jù)給出的序列構(gòu)建平衡二叉樹，得出C與其他不同。13、關(guān)于B一樹，下列說法中不正確的是()。A、B一樹是一種查找樹B、所有的葉結(jié)點(diǎn)具有相同的高度C、2-3樹中，所有非葉子結(jié)點(diǎn)有l(wèi)或者3個(gè)孩子結(jié)點(diǎn)D、通常情況下，B一樹不是二叉樹標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：B一樹定義如下：一棵m階B一樹，或者是空樹，或者是滿足以下性質(zhì)的m叉樹：(1)根結(jié)點(diǎn)或者是葉子，或者至少有兩棵子樹，至多有m棵子樹。(2)除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有[m／2]棵子樹，至多有m棵子樹。(3)所有葉子結(jié)點(diǎn)都在樹的同一層上。(4)每個(gè)結(jié)點(diǎn)應(yīng)包含如下信息：(n，A0，K1，A1，K2，A2，…，Kn，An)。其中：Ki(1≤i≤n)是關(guān)鍵字，且Ki＜Ki+1(1≤i≤n一1)；Ai(i=0，1，…，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki，Ai所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki。n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且[m／2]—1≤n≤m一1，n+1為子樹的棵數(shù)。14、在含有15個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(guān)鍵字為28(存在該結(jié)點(diǎn))的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是()。A、30．36B、38，48，28C、48，18，38，28D、60，30，50，40，38，36標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：設(shè)Ni表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，有：N0=0，N1=1，N2=2；計(jì)算的公式為：Nh=Nh-1+Nh-2+1；N3=N2+N1+1=4；N4=N3+N2+1=7；N5=N4+N3+1=12；N6=N5+N4+1=20＞15。也就是說，高度為6的平衡二叉樹最少有20個(gè)結(jié)點(diǎn)，因此15個(gè)結(jié)點(diǎn)的平衡二叉樹的高度為5，而最小葉子結(jié)點(diǎn)的層數(shù)為3，所以選項(xiàng)D錯(cuò)誤。選項(xiàng)A在查找30后，指針應(yīng)該指向左孩子，而不是右孩子；選項(xiàng)B與選項(xiàng)A存在同樣的問題，因而選項(xiàng)A、B錯(cuò)誤。而選項(xiàng)C的查找路徑如下圖所示：15、下面關(guān)于m階B樹的說法中，正確的是()。①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹。②樹中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字。③所有葉子在同一層上。④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹結(jié)點(diǎn)分裂后，樹長(zhǎng)高一層。A、①②③B、②③C、②③④D、③標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)B樹定義可知只有③正確。16、下面關(guān)于B和B+樹的敘述中，不正確的是()。A、B樹和B+樹都是平衡的多叉樹B、B樹和B+樹都可用于文件的索引結(jié)構(gòu)C、B樹和B+樹都能有效地支持順序檢索D、B樹和B+樹都能有效地支持隨機(jī)檢索標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是B一樹和B+樹的定義。B+樹是應(yīng)文件系統(tǒng)所需而發(fā)展出的一種B一樹的變形樹。一棵m階的B+樹和m階的B一樹的差異在于：(1)有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字。(2)所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。(3)所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含其子樹(根結(jié)點(diǎn))中的最大(或最小)關(guān)鍵字。通常在B+樹上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。所以B+樹能有效地支持隨機(jī)檢索和順序檢索。顯然應(yīng)選C。17、m階B一樹是一棵()。A、m叉排序樹B、m叉平衡排序樹C、m-1叉平衡排序樹D、m+1叉平衡排序樹標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：此題考查的知識(shí)點(diǎn)是m階B一樹的定義。B一樹是一種平衡的多路排序樹，m階即m叉。應(yīng)選B。18、若對(duì)有18個(gè)元素的有序表做二分查找，則查找A[3]的比較序列的下標(biāo)為()。A、1，2，3B、9，4，2，3C、10，5，3D、9，2，3標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：二分查找判定樹如下圖所示，查找A[3]的比較序列的下標(biāo)為9，4，2，3，本題選D。[*42]19、有一個(gè)有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)用二分查找法查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)()次比較后查找成功。A、1B、2C、4D、8標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：n=13，R[11]=82，第1次與R(1+13)／2=7]=45比較，第2次與R(8+13)／2=10]=77比較，第3次與R[(11+13)／2=12]=95比較，第4次與R(10+12)／2=11]=85比較時(shí)成功，總共比較4次。20、采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊，則每塊分為()個(gè)結(jié)點(diǎn)最佳。A、9B、25C、6D、625標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：分塊查找時(shí)最佳塊數(shù)為。21、在有n個(gè)結(jié)點(diǎn)且為完全二叉樹的二叉排序樹中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)為()。A、O(n)B、P(log2n)C、O(nlog2n)D、O(n2)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：有n個(gè)結(jié)點(diǎn)且為完全二又樹的二叉排序樹的高度為log2n。22、對(duì)包含n個(gè)關(guān)鍵碼的散列表進(jìn)行檢索，平均檢索長(zhǎng)度為()。A、O(log2n)B、O(n)C、O(nlog2n)D、不直接依賴于n標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：對(duì)散列表進(jìn)行檢索，平均檢索長(zhǎng)度僅與裝填因子α有關(guān)，而與關(guān)鍵字個(gè)數(shù)n無關(guān)。23、在散列表上，每個(gè)地址單元所鏈接的同義詞表的()。A、鍵值相同B、元素值相同C、散列地址相同D、含義相同標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：由同義詞的定義可知本題答案為C。24、設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=keymod11。表中已有4個(gè)結(jié)點(diǎn)addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空，如用二次探測(cè)再散列法處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地址是()。A、8B、3C、5D、9標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：addr(49)=49mod11=5，沖突；h1=(5+1*1)mod11=6，仍沖突；h2=(5+2*2)mod11=9，所以本題答案為D。二、綜合應(yīng)用題(本題共19題，每題1.0分，共19分。)25、請(qǐng)編寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink—rlink法存儲(chǔ)。標(biāo)準(zhǔn)答案：根據(jù)二叉排序樹中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre(初值為null)和全局變量flag，初值為true。若非二叉排序樹，則置flag為false。#definetrue1#definefalse0tvpedefstructnode{datatypedata；structnode*llink，*rlink；}*BTree；voidJudgeBST(BTreet，intflag){／／判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論if(t!=null&&flag){JudgeBST(t一>llink，flag)；／／中序遍歷左子樹if(pre==null)pre=t；／／中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷elseif(pre一>datadata)pre=t；／／前驅(qū)指針指向當(dāng)前結(jié)點(diǎn)elseflag=false；／／不是二叉排序樹JudgeBST(t一>rlink，flag)；／／中序遍歷右子樹}}本題的另一算法是依照定義，二叉排序樹的左右子樹都是二叉排序樹，根結(jié)點(diǎn)的值大于左子樹中所有值而小于右子樹中所有值，即根結(jié)點(diǎn)大于左子樹的最大值而小于右子樹的最小值。算法如下：intJudgeBST(BTreet){／／判斷二叉樹t是否是二叉排序樹，若是，返回true，否則，返回falseif(t==null)returntrue；if(JudgeBST(t一>llink)&&JudgeBST(t一>rlink)){／／若左右子樹均為二叉排序樹m=max(t一>llink)；n=min(t->rlink)；／／左子樹中最大值和右子樹中最小值return(t一>data>m&&t一>datarlink!：null)p=p一>rlink；returnp一>data；}}intmin(BTreeP){／／求二叉樹右子樹的最小值if(P==null)returnmaxint；／／返回機(jī)器最大整數(shù)else{while(p一>llink!=null)P=P一>rlink：returnp一>data；}}知識(shí)點(diǎn)解析：暫無解析26、某個(gè)任務(wù)的數(shù)據(jù)模型可以抽象為給定的k個(gè)集合：S1，S2，…，Sk。其中Si(1≤i≤k)中的元素個(gè)數(shù)不定。在處理數(shù)據(jù)過程中將會(huì)涉及元素的查找和新元素的插入兩種操作，查找和插入時(shí)用一個(gè)二元組(i，x)來規(guī)定一個(gè)元素，i是集合的序號(hào)，x是元素值。設(shè)計(jì)一種恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存儲(chǔ)這k個(gè)集合的元素，并能高效地實(shí)現(xiàn)所要求的查找和插入操作。(1)構(gòu)造數(shù)據(jù)結(jié)構(gòu)，并且說明選擇的理由。(2)若一組數(shù)據(jù)模型為S1={10．2，1．7，4．8，16．2}，S2={1．7，8．4，0．5}，S3={4．8，4．2，3．6，2．7，5．1，3．9}，待插入的元素二元組為(2，11．2)和(1，5．3)，按你的設(shè)計(jì)思想畫出插入元素前后的數(shù)據(jù)結(jié)構(gòu)狀態(tài)。標(biāo)準(zhǔn)答案：借助于分塊查找思想，在建立數(shù)據(jù)順序表的同時(shí)，建立一索引表。數(shù)據(jù)表中按k個(gè)集合分塊(元素個(gè)數(shù)不一定相等)，索引表中有兩個(gè)域，一是各集合最后一個(gè)元素在數(shù)據(jù)表中的位置(一維數(shù)組中的下標(biāo))，二是集合的個(gè)數(shù)(k)。實(shí)現(xiàn)數(shù)據(jù)運(yùn)算時(shí)，根據(jù)給定的二元組(i，x)，首先在索引表中找到集合i的位置，然后在數(shù)據(jù)表中查找x。查到x，則查找成功，返回x在數(shù)據(jù)表中的位置，否則查找失敗。若要插入，則將數(shù)據(jù)表中的數(shù)據(jù)后移，插入x，同時(shí)修改索引表。typedefstruct{datatypedata；}rectype；typedefstruct{inta[]；／／a數(shù)組容量夠大，存儲(chǔ)各集合最后一個(gè)數(shù)據(jù)在數(shù)據(jù)表中的下標(biāo)intk；／／集合個(gè)數(shù)}index：inISetSearch_Insert(rectypeR[]，indexid，datatypeX，inti){／／數(shù)據(jù)表R，查找第i個(gè)集合的元素X，若查找成功，返回其位置;／／否則將其插入第i個(gè)集合if(i<1||i>id．k){printf(”無第％d個(gè)集合＼n”，i)；exit(0)：}if(i==1)first=0；／／first指向第i個(gè)集合在數(shù)據(jù)表的首址elsefirst=id．a(chǎn)[i—1]+1；last=id．a(chǎn)[i]；／／last是第i個(gè)集合在數(shù)據(jù)表中的末址for(j=first；jid．A[i]；j--)t／／查找失敗，將x插入數(shù)據(jù)表R[j+1]=R[j]；／／元素后移R[j+1]=x；／／將x插入到原第i個(gè)集合最后一個(gè)元素之后for(j=i;j≤k；j++)id．a(chǎn)[j]++；／／修改索引表中各集合最后一個(gè)元素的下標(biāo)}由于各集合元素個(gè)數(shù)不等，各塊長(zhǎng)度不等且塊間無序，索引表中用數(shù)組表示，數(shù)組中元素值是各集合最后一個(gè)元素在數(shù)據(jù)表中的下標(biāo)。按本算法插入(2，11．2)和(1，5．3)，數(shù)據(jù)表前后狀態(tài)如下：插入前，索引表中a數(shù)組的內(nèi)容是3，6，12，插入后修改為4，8，14。知識(shí)點(diǎn)解析：暫無解析27、假設(shè)K1,…，Kn是n個(gè)關(guān)鍵詞，試解答：(1)試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，…，Kn時(shí)，用算法建立一棵以LLINK—RLINK鏈接表示的二叉查找樹。(2)設(shè)計(jì)一個(gè)算法，打印出該二叉查找樹的嵌套括號(hào)表示結(jié)構(gòu)。假定該二叉查找樹的嵌套括號(hào)表示結(jié)構(gòu)為B(A，D(C，E))。標(biāo)準(zhǔn)答案：(1)非遞歸建立二叉排序樹，在二叉排序樹上插入的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。typedefstructnode{Elemtypedata；structnode*LLINK，*RLINK；}node*BiTree：voidCreate_BST(BiTreebst，datatypeK[]，intn){／／以存儲(chǔ)在數(shù)組K中的n個(gè)關(guān)鍵字，建立一棵初始為空的二又排序樹inti：BiTreeP，f：for(i=1；i<=n；i++){p=bst：f=null；／／在調(diào)用Create_BST時(shí)，bst=nullwhile(P!=null)if(P->dataRLINK；}／／f是P的雙親elseif(p一>data>K[i]){f=P；P=p一>LLINK；}S=(BiTree)malloc(sizeof(BiNode))；／／申請(qǐng)結(jié)點(diǎn)空間s->data=K[i];s->LLINK=null;s一>RLINK=null；if(f==null)bst：S；／／根結(jié)點(diǎn)elseif(S->datadata)f->LLINK=S；／／左子女elsef一>RLINK=s：／／右子樹根結(jié)點(diǎn)的值大于等于根結(jié)點(diǎn)的值}}(2)本題要求輸出遍歷二叉排序樹的嵌套括號(hào)表示。其算法思想是，若二叉排序樹非空，則輸出根結(jié)點(diǎn)，再輸出其左右子樹。在輸出其左右子樹前，要輸出左括號(hào)，在輸出其右子樹前要輸出逗號(hào)，在輸出其右子樹后要輸出右括號(hào)，在左右子樹均空情況下，則不輸出括號(hào)。voidPrint(BiTreet){／／以嵌套括號(hào)表示結(jié)構(gòu)打印二叉排序樹if(t!=null){printf(t一>data)；／／打印根結(jié)點(diǎn)值if(t一>LLINK||t一>LLINK)；／／左子女和右子女中至少有一個(gè)不空printf(”(”)；／／輸出左括號(hào)Print(t一>LLINK)i／／輸出左子樹的嵌套括號(hào)表示if(t一>RLINK)printf(”，”)；／／若右子樹不空，輸出逗號(hào)Print(t一>RLINK)；／／輸出右子樹的嵌套括號(hào)表示printf(”)”)；／／輸出右括號(hào)}}知識(shí)點(diǎn)解析：暫無解析28、寫出在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)的算法，使刪除后仍為二又排序樹。設(shè)刪除結(jié)點(diǎn)由指針p所指，其雙親結(jié)點(diǎn)由指針f所指，并假設(shè)被刪除結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子。描述上述算法。標(biāo)準(zhǔn)答案：voidDelete(BSTreet，P){／／在二叉排序樹t中，刪除f所結(jié)點(diǎn)的右孩子(由P所指向)if(P一>lchild==null){f一>rchild=P一>rchild；free(P)；}／／p無左子女else{／／用P左子樹中的最大值代替P結(jié)點(diǎn)的值q=p一>lchild；s=q；while(q一>rchild){s=q；q=q一>rchild；}／／查P左子樹中序序列最右結(jié)點(diǎn)if(s==p一>lchild)／／p左子樹的根結(jié)點(diǎn)無右子女{p一>data=s一>data；p一>lchild=s一>lchild；free(S)；}else{p一>data=q一>data；s一>rchild=q一>lchild；free(q)；}}}知識(shí)點(diǎn)解析：暫無解析29、已知二叉樹排序樹中某結(jié)點(diǎn)指針p，其雙親結(jié)點(diǎn)指針為fp，p為fp的左孩子。試編寫算法，刪除p所指結(jié)點(diǎn)。標(biāo)準(zhǔn)答案：本題用被刪結(jié)點(diǎn)右子樹中最小值(中序遍歷第一個(gè))結(jié)點(diǎn)代替被刪結(jié)點(diǎn)。w)idDelete(BSTreebst，P，fp){／／在二叉排序樹bst上，刪除fp所指結(jié)點(diǎn)的左子女(由P所指向)if(!p一>lchild){fp一>lchild=p一>rchild；free(P)；}／／p無左子女elseif(!p一>rchild){fp一>lchild=p一>lehild；flee(P)；}／／p無右子女else／／P有左子女和右子女{q=P一>rchild；s=q；／／用P右子樹中的最小值代替P結(jié)點(diǎn)的值while(q一>lchild){S=q；q=q一>lchild；}／／查P右子樹中序序列最左結(jié)點(diǎn)if(S==p一>rehild)／／p右子樹的根結(jié)點(diǎn)無左子女{p一>data=s一>data；p一>rchild=s一>rchild；frees)；}else{p一>data=q一>data；s一>lchild=q一>rchild；free(q