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

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

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

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