2023年河北工程大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(含答案)

2023期末試卷A〔有答案〕一、選擇題1、用有向無環(huán)圖描述表達式(A+B)*((A+B)／/A)，至少需要頂點的數(shù)目為〔 〕。A.5B.6C.8D.92、將兩個各有N個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是〔 〕。A.NB.2N-1C.2ND.N-1表中，增加一個頭結(jié)點是為了〔 〕。A.使單鏈表至少有一個結(jié)點B. 標(biāo)識表結(jié)點中首結(jié)點的位置C.便利運算的實現(xiàn)D. 說明單鏈表是線性表的鏈?zhǔn)酱鎯?、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是〔 〕。A.〔rear-front+m〕%mB.rear-front+1C.rear-front-1D.rear-front5、在以下表述中，正確的選項是〔 〕含有一個或多個空格字符的串稱為空格串對n〔n>0〕個頂點的網(wǎng)，求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹選擇排序算法是不穩(wěn)定的平衡二叉樹的左右子樹的結(jié)點數(shù)之差確實定值不超l6、關(guān)鍵5，8，12，19，28，20，15，22是小根堆〔最小堆〕，插入關(guān)鍵字3，調(diào)整后的小根堆是〔 〕。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、假設(shè)一棵二叉樹的前序遍歷序列a，e，b，d，c，后序遍歷序列b，c，d，e，a，則根結(jié)點的孩子結(jié)點〔 〕。A．只有eB．有e、bC ．有e、cD ．無法確定8、在下述結(jié)論中，正確的有〔 〕。①只有一個結(jié)點的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度一樣的滿二叉樹。A.①②③B.⑦③④C.②④D.①④9、每個結(jié)點的度或者0或者為2的二叉樹稱為正則二叉樹。n個結(jié)點的正則二叉樹中有〔 〕個葉子。2 nB. 〔n－1〕/2C.log n+1D.〔n＋1〕2 10、下面關(guān)于B和B+樹的表達中，不正確的選項是〔 〕A.B樹和B+樹都是平衡的多叉樹B.B 樹和B+樹都可用于文件的索引構(gòu)造C.B樹和B+樹都能有效地支持挨次檢索D.B 樹和B+樹都能有效地支持隨機檢索二、填空題11、挨次查找n個元素的挨次表，假設(shè)查找成功，則比較關(guān)鍵字的次數(shù)最多為 次；當(dāng)使用監(jiān)視哨時，假設(shè)查找失敗，則比較關(guān)鍵字的次數(shù)為 。12、在有n個頂點的有向圖中，每個頂點的度最大可達 。13、數(shù)據(jù)構(gòu)造是研討數(shù)據(jù)的 和 對與這種構(gòu)造定義相應(yīng)的 ，設(shè)計出相應(yīng)的 。14、n個頂點的有向圖用鄰接矩陣array表示，下面是其拓撲排序算法，試補充完整。注：(1)圖的頂0開頭計。indegree是有n個重量的一維數(shù)組，放頂點的入度，函數(shù)crein用于計算頂點入度。有三個函數(shù)push(data)，pop，check其含義為數(shù)據(jù)data入棧，出棧和測試棧是否空(不空返回l，否0)。15、在雙向循環(huán)鏈表中，向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是 、 、 、 。〔S，〔m，’ww’〕，REPLACE〔S，V，m〕= 。17、在挨次存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是 。18、以下程序是快速排序的非遞歸算法，請?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。三、推斷題19、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引挨次存取方法是一種便利的文件組織方法。〔 〕鍵字查找。〔 〕他廣義表所共享?！?〕22、棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an假設(shè)ai=n〔1≤i≤n〕則有：ai>ai+1>…>an。〔 〕23、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列?！?〕24、對于有n個結(jié)點的二叉樹，其高度為log2n?！?〕25、線性表承受鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的?！?〕26、外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進展排序，因此排序所花的?！?〕27、當(dāng)轉(zhuǎn)變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵路徑。〔 〕28、承受線性探測法處理散列時的沖突，當(dāng)從哈希表刪除一個記錄時，不應(yīng)將這個記錄的所在位置置空，由于這會影響以后的查找?！?〕四、簡答題29、對于具有n個葉結(jié)點且全部非葉結(jié)點都有左、右孩子的二叉樹。(1)試問這種二叉樹的結(jié)點總數(shù)是多少?試證明1〕。

2〔li-〕=1。其中：li表示第i結(jié)層號設(shè)結(jié)層號為30、將以下由三棵樹組成的森林轉(zhuǎn)換為二叉樹〔只要求給出轉(zhuǎn)換結(jié)果〕。31、一個帶有表頭結(jié)點的單鏈表，結(jié)點構(gòu)造為假設(shè)該鏈表只給出了頭指針list。在不轉(zhuǎn)變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點〔k為正整數(shù)〕。假設(shè)查找成功，算法輸出該結(jié)點的data域的值1；否則0。要求：描述算法的根本設(shè)計思想。具體實現(xiàn)步驟。依據(jù)設(shè)計思想和實現(xiàn)步驟，承受程序設(shè)計語言描述算法〔使用C或CJAVA語言實現(xiàn)〕，關(guān)鍵之處請給出簡要注釋。五、算法設(shè)計題32、設(shè)A[1..100]是一個記錄構(gòu)成的數(shù)組，B[1..100]是一個整數(shù)數(shù)組，其值介于l～100之間，現(xiàn)要求按B[1..100]的內(nèi)容調(diào)A中記錄的次序，比方當(dāng)B[1]=11時，則要求將A[1]的內(nèi)容調(diào)A[11]中去。規(guī)定可使用的附加空間為O〔1〕。33、請用流程圖或高級語言表示算法。有向圖有n個頂點，請寫算法，依據(jù)用戶輸入的數(shù)對建立該有向圖的鄰接表。即承受用戶輸入的<vi，vj>(以其中之一為0標(biāo)志完畢)，對于每條這樣的邊，申請一個結(jié)點，并插入到的單鏈表中，如此反復(fù)，直到將圖中全部邊處理完畢。提示：先產(chǎn)生鄰n個頭結(jié)點(其結(jié)點數(shù)值1n)。34、設(shè)A和B均為下三角矩陣，每一個都有n行n列。因此在下三角區(qū)域中各有nn+1/設(shè)數(shù)組，它有n行n+1一個方案，將兩個矩陣A和B中的下三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于C的上三角區(qū)域中。ijij并給出計算A的矩陣元素a，和B的矩陣元素b在C中的存放位置下標(biāo)的公式。ijij35、以三元組表存儲的稀疏矩陣A，B非零元個數(shù)分別為m和n。試用類PASCAL語言寫簡單為〔m+〕陣B陣AA足夠大，不另加關(guān)心空間。要求描述所用構(gòu)造。參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】D10、【答案】C二、填空題11、【答案】n；n+112、【答案】2(n-1)13、【答案】規(guī)律構(gòu)造；物理構(gòu)造；操作〔運算〕；算法14、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0【解析】有向圖用鄰接矩陣表示時，頂點i的入度等于第i列的全部元素之和。拓撲排序過程：首先將入度0的頂點全部進棧。然后彈出棧頂結(jié)點，并將與彈出的頂點相連的頂點的入度減一，然后推斷這些頂點的入度是否為零，假設(shè)為零，連續(xù)進棧，重復(fù)這些操作，完成拓撲排序。。16、【答案】’xyxyxywwy’17、【答案】++a*b3*4-cd；18【解析】中綴式相當(dāng)于中序遍歷，前綴式相當(dāng)于前序遍歷，后綴式相當(dāng)于后序遍歷。18、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的根本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬删植?，其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小，則可分別對這兩局部記錄連續(xù)進展排序，以到達整個序列有序。三、推斷題19、【答案】×20、【答案】√21、【答案】√22、【答案】×23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：〔1〕依據(jù)二叉樹中度2的結(jié)點個數(shù)等于葉結(jié)1的性質(zhì)n個葉結(jié)點且非葉子結(jié)點均有左子樹的二叉樹的結(jié)2n-1?！?〕證明：當(dāng)i=1時，2-〔1-1〕=20=1，公式成立。設(shè)i=n-1時公式成立，證明當(dāng)i=n時公式仍成立。設(shè)某葉結(jié)點的層號t，當(dāng)將該結(jié)點變?yōu)閮?nèi)部結(jié)點，從而再增加兩個葉結(jié)點時這兩個葉結(jié)點的層號都是t+1，對于公式的變化，是削減了一個原來的葉結(jié)點，增加了兩個葉結(jié)點，反映到公式中，由于2-〔t-1〕=2-〔t+1-1〕+2-〔t+1-1〕，所以結(jié)果不變，這就證明當(dāng)i=n時公式仍成立。證畢。30、答：森林轉(zhuǎn)換為二叉樹分以下三步：連線〔將兄弟結(jié)點相連，各樹的根看作兄弟〕?！?〕〔3〕

切線〔保存最左邊子女為獨生子女，將其他子女分支切掉〕。旋轉(zhuǎn)〔以最左邊樹的根為軸，順時針向下旋45度〕。所以由上面三棵樹轉(zhuǎn)換得到的二叉樹如下圖：31、答：〔1〕算法的根本設(shè)計思想定義兩個指針變pq，初始時均指向頭結(jié)點的下一個結(jié)點。p指針沿鏈表移動p指針移動到第k個結(jié)點時，q指針開頭與p指針同步移動p指針移動到鏈表最終一個結(jié)點時，由于pqkq指針?biāo)冈貫榈筴個