2023《數(shù)據(jù)結構》期末試卷（A卷）

本文格式為Word版，下載可任意編輯——2023《數(shù)據(jù)結構》期末試卷（A卷）2023A卷2023－2023年春季學期計算機科學與技術、軟件工程、網絡工程專業(yè)《數(shù)據(jù)結構》期末試卷（A卷）卷面總分：100分答題時間：120分鐘專業(yè)年級班級姓名學號題一二三四五六七八九十總分號得分一、單項選擇題（本大題共15小題，每題1分，共15分答案寫在答題卡上）123456789101112131415答題卡題號答案1.設n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間繁雜度是()。x=2;while(x0）。A．表元素B．數(shù)據(jù)元素C．字符D．數(shù)據(jù)項3.對于順序存儲的線性表，訪問結點和增加、刪除結點的時間繁雜度為()。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)4.設棧的輸入序列是1，2，3，4,則()不可能是其出棧序列。A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2

5.設棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進入棧S。若每個元素出棧后馬上進入隊列Q，且7個元素出隊的順序是b,d,c,f,e,a,g，則棧S的容量至少是()。

A.4B.3C.2D.1

6.為解決計算機主機與打印機之間速度不匹配問題，尋常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的規(guī)律結構應當是()。

A.棧B.隊列C.樹D.串7.串是一種特別的線性表，下面哪個表達表達了這種特別性()。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.數(shù)據(jù)元素可以是多個字符D.可以鏈接存儲

8.已知一棵完全二叉樹的第6層（設根是第1層）有8個葉結點，則該完全二叉樹的結點個數(shù)最多是()。

A.119B.111C.52D.399.一個具有1025個結點的二叉樹的高h為()。A．10至1024之間B．11至1025之間C.10D.1110.設森林F中有三棵樹，第一，其次，第三棵樹的結點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是()。A．M1+M2B．M2+M3CM3D.M1

11.設無向圖的頂點個數(shù)為n，則該圖最多有()條邊。

A．n-1B．n2C．n(n+1)/2D．n(n-1)/212.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為()。

A.(n-1)/2B.n/2C.nD.(n+1)/213.分別以以下序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是()。

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)

14.一組記錄的關鍵字為{46、79、56、38、40、84},則利用快速排序的方法,以第一個記錄為樞軸得到的一次劃分結果是()A.38、40、46、56、79、84B.40、38、46、79、56、84C.40、38、46、56、79、84D.40、38、46、84、56、7915.在以下排序方法中,()方法可能出現(xiàn)這種狀況：在最終一趟開始之前,所有的元素都不在其最終應在的正確位置上。A.快速排序B.冒泡排序C.插入排序D.堆排序二、判斷題（本大題共5小題，每題1分，共5分正確的打“√〞，錯誤打“×〞），1.所謂一個排序算法是否穩(wěn)定,是指該算法在各種狀況下的時間效率是否相差不大。()2.知道鏈表中結點的指針就可以訪問該結點，所以鏈表是隨機存取結構。()3.非空廣義表的取尾操作的結果是除去廣義表第一個元素后的剩余元素。()4.圖的鄰接矩陣存儲結構所占空間只與圖的頂點的個數(shù)有關，和邊數(shù)無關。()5.具有n個關鍵字的有序表的判定樹的樹形是唯一的，而其二叉排序樹的樹形取決于輸入次序。()三、應用題（本大題共6小題，各題的分數(shù)在小題中給出，共60分）1.（5分）求串’ababaaababaa’的next函數(shù)值。j12345678910ababaaababt串next[j]2.（15分）已知一個森林的先序序列和后序序列如下:先序序列：ABDECFHIG后序序列：DBEAHFICG請（1）構造出該森林，（2）并畫出該森林對應的二叉樹，（3）寫出對二叉樹遍歷的后序序列。

3.（10分）已知有向圖G的頂點是編號1－5，其鄰接矩陣如下。請畫出其從頂點1開始遍歷的（1）深度優(yōu)先生成樹和（2）寬度優(yōu)先生成樹。

4.（10分）設有序表L=(5,7,9,12,16,19,25,47,63,76,82,90)。（1）畫出該有序表的判定樹，（2）求其查找成功時的平均查找長度，（3）求其查找失敗時的平均查找長度，（4）查找47時需經過哪幾個結點。

5.（10分）已知一組關鍵字（46,58,15,45,90,18,10,62,65,95）。試（1）畫出按大根堆建立初始堆（只要結果堆，不必寫出詳細過程），（2）將輸出堆頂元素的剩余元素重新調成堆。

6.（10分）設有待排序元素如下：15,13,20,18,12,60。下面是用不同排序方法進行一趟排序的結果，請分別在各趟排序結果前的括號內填寫用的是什么排序方法。

一趟（）的排序結果為：12，13，15，18，20，60一趟（）的排序結果為：13，15，18，12，20，60一趟（）的排序結果為：13，15，20，18，12，60一趟（）的排序結果為：13，15，18，20，12，60一趟（）的排序結果為：12，13，20，18，15，60

四、算法設計題（本大題共3小題，第1和2題各7分，第3題6分，共20分）

注意：算法中所用數(shù)據(jù)結構均可引用教科書中的定義，不必重新定義。1.設la是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素仍舊遞增有序。

DLinkedListDInsert(DLinkedListla,ElemTypex)∥在遞增有序的雙向循環(huán)鏈表la中插入元素x，使表中元素仍舊遞增有序{

}

2.設有順序放置的n個桶,每個桶中裝有一粒礫石,每粒礫石的顏色是紅、白、藍之一。要求重新安排,使得紅色礫石在前,白色礫石居中,藍色礫石居后。對每粒礫石的顏色只能觀測一次,且只允許交換操作來調整礫石的位置。voidQkSort(rectyper[],intn)

∥r為有n個紅、白和蘭色的礫石的順序表,

∥本算法按紅色礫石在前,白色居中,蘭色在最終進行排序{}

3.設二叉排序樹上結點的值是互不一致的整數(shù),試編寫按遞減順序輸出二叉排序樹算法。

voidInvertOrder(BSTreebt)

∥按遞減次序輸出二叉排序樹bt結點的值{

}∥InvertOrder

}

2.設有順序放置的n個桶,每個桶中裝有一粒礫石,每粒礫石的顏色是紅、白、藍之一。要求重新安排,使得紅色礫石在前,白色礫石居中,藍色礫石居后。對每粒礫石的顏色只能觀測一次,且只允許交換操作來調整礫石的位置。voidQkSort(rectyper[],intn)

∥r為