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

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

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

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