大學(xué)試題(計算機科學(xué))-數(shù)據(jù)結(jié)構(gòu)筆試（2018-2023年）真題摘選含答案

長風(fēng)破浪會有時，直掛云帆濟滄海。大學(xué)試題(計算機科學(xué))-數(shù)據(jù)結(jié)構(gòu)筆試（2018-2023年）真題摘選含答案（圖片大小可自由調(diào)整）卷I一.參考題庫(共30題)1.設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。2.編寫算法求給定結(jié)點在二叉排序樹中所在的層數(shù)。3.記錄的關(guān)鍵字序列為：63，90，70，55，67，42，98，83，10，45，58，則畫出構(gòu)造一棵二叉排序樹的過程。4.設(shè)有二維數(shù)組A（6×8），每個元素占6個字節(jié)存儲，順序存放，A的起地址為1000，計算： （1）數(shù)組A的體積（即存儲量）； （2）數(shù)組的最后一個元素A??的起地址； （3）按行優(yōu)先存放時，元素A1，4的起地址； （4）按列優(yōu)先存放時，元素A4，7的起地址。5.用線性表的順序結(jié)構(gòu)來描述一個城市的設(shè)計和規(guī)劃合適嗎？為什么？6.已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。7.已知一組元素的排序碼為： （46，74，16，53，14，26，40，38，86，65，27，34）利用直接選擇排序方法寫出每次選擇和交換后的排列結(jié)果。8.請列舉出一些可以用棧和隊列表示的實際問題。9.設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。10.簡述多重表文件和倒排文件兩種多關(guān)鍵字文件的組織方法。11.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（） A、AB、BC、CD、D12.假設(shè)線性表采用順序存儲結(jié)構(gòu)，表中元素值為整型。閱讀算法f2，設(shè)順序表L=（3，7，3，2，1，1，8，7，3），寫出執(zhí)行算法f2后的線性表L的數(shù)據(jù)元素，并描述該算法的功能。voidf2（SeqList*L）{inti，j，k；k=0；for（i=0；ilength；i++）{for（j=0；jdata[i]!=L->data[j]；j++）；if（j==k）{if（k!=i）L->data[k]=L->data[i]；k++；}}L->length=k；}13.深度為k的完全二叉樹中最少有（）個結(jié)點。 A、AB、BC、CD、D14.已知有向圖如下所示，請寫出該圖所有的拓?fù)湫蛄小?15.設(shè)計算法判定一棵二叉樹是否為二叉排序樹。16.畫出下列每個廣義表的帶表頭附加結(jié)點的鏈接存儲結(jié)構(gòu)圖并分別計算出它們的長度和深度。 （1）A=（（）） （2）B=（a，b，c） （3）C=（a，（b，（c））） （4）D=（（a，b），（c，d）） （5）E=（a，（b，（c，d）），（e）） （6）F=（（a，（b，（），c），（（d），e）））17.簡述Floyd算法的作用和具體步驟。18.對下面數(shù)據(jù)表，寫出采用SHELL排序算法排序的每一趟的結(jié)果，并標(biāo)出數(shù)據(jù)移動情況。 （125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。19.散列表20.沖突21.已知一棵具有n個結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的A[1]～A[n]元素中，試編寫一個算法打印出編號為i的結(jié)點的雙親和所有孩子。22.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔槪羔樧兞縮指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（） A、AB、BC、CD、D23.判斷下列各對函數(shù)f（n）和g（n），當(dāng)n→∞時，哪個函數(shù)增長更快？ 24.設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。25.設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對。（提示：對表達(dá)式進行掃描，凡遇到’（’就進棧，遇’）’就退掉棧頂?shù)摹ā?，表達(dá)式被掃描完畢，棧應(yīng)為空。26.查找27.已知一組記錄為（46，74，53，14，26，38，86，65，27，34），給出采用堆排序法進行排序時每一趟的排序結(jié)果。28.下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。 29.寫出快速排序的非遞歸調(diào)用算法。30.試找出滿足下列條件的所有二叉樹： （1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。卷I參考答案一.參考題庫1.參考答案:2.參考答案:根據(jù)題目要求采用遞歸方法，從根結(jié)點開始查找結(jié)點p，若待查結(jié)點是根結(jié)點，則深度為1，否則到左子樹（或右子樹）上去找，查找深度加1。 具體算法如下： 3.參考答案:4.參考答案:5.參考答案: 不合適。因為一個城市的設(shè)計和規(guī)劃涉及非常多的項目，很復(fù)雜，經(jīng)常需要修改、擴充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。6.參考答案:7.參考答案: 8.參考答案: 所有“后進先出”（LIFO，LastInFirstOut）的實際問題都可以用棧表示。棧的應(yīng)用主要有：數(shù)制的轉(zhuǎn)換、括號的匹配檢查、行編輯處理、表達(dá)式求解、走迷宮以及高級語言中函數(shù)的嵌套調(diào)用和遞歸的實現(xiàn)等。 所有“先進先出”（FIFO，F(xiàn)irstInFirstOut）的實際問題都可以用隊列表示。如日常中的排隊問題，隊列的應(yīng)用主要有：操作系統(tǒng)中各種資源請求排隊和各種緩沖區(qū)的先進先出管理，各種應(yīng)用系統(tǒng)中的事件規(guī)劃和事件模擬，樹的層次遍歷和圖的廣度優(yōu)先遍歷等。9.參考答案: 10.參考答案: 多重表文件是將索引方法和鏈接方法相結(jié)合的一種文件組織方式，對主關(guān)鍵字建立的索引稱為主索引，對每個需做查詢操作的次關(guān)鍵字建立的索引稱為次索引。在多重表文件中，記錄通常按主關(guān)鍵字順序排列，同時將具有相同次關(guān)鍵字值的記錄鏈接成一個鏈表，并將此鏈表的頭指針、鏈表長度及次關(guān)鍵字作為對應(yīng)次索引表中的索引項。 與多重表文件不同，倒排文件中具有相同次關(guān)鍵字的記錄之間不進行鏈接，而是在對次關(guān)鍵字建立的索引中列出具有該次關(guān)鍵字值的所有記錄的物理地址。倒排文件中的次關(guān)鍵字索引稱為倒排表，倒排表與主文件一起就構(gòu)成了倒排文件。11.參考答案:C12.參考答案: （3，7，2，1，8）刪除順序表中重復(fù)的元素13.參考答案:B14.參考答案: 拓?fù)渑判蛉缦拢?v1,v2,v4,v6,v5,v3,v7,v8v1,v2,v4,v6,v5,v7,v3,v8 v1,v2,v6,v4,v5,v3,v7,v8v1,v2,v6,v4,v5,v7,v3,v8 v1,v6,v2,v4,v5,v3,v7,v8v1,v6,v2,v4,v5,v7,v3,v815.參考答案:對二叉排序樹來講，其中序遍歷序列為一個遞增序列。因此，對給定二叉樹進行中序遍歷，如果始終能夠保證前一個值比后一個值小，則說明該二叉樹是二叉排序樹。 具體算法如下： 16.參考答案: 17.參考答案: 18.參考答案:19.參考答案: 是根據(jù)關(guān)鍵字而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。散列表建立了關(guān)鍵字和存儲地址指間的一種直接映射關(guān)系。20.參考答案: 散列函數(shù)可能會把兩個或以上的不同關(guān)鍵字映射到同一地址，這種情況為沖突。21.參考答案: 22.參考答案:C23.參考答案: （1）g（n）快 （2）g（n）快 （3）f（n）快 （4）f（n）快24.參考答案:本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。為此，將前序遍歷 算法中的訪問操作改為條件打印即可。算法如下： 25.參考答案:根據(jù)提示，可以設(shè)計算法如下： 26.參考答案: 在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。27.參考答案:28.參考答案: 依次為： 29.參考答案:先調(diào)用劃分函數(shù)Quickpass（劃分函數(shù)同教材），以確定中間位置，然后再借助棧分別對中間元素的左、右兩邊的區(qū)域進行快速排序。 30.參考答案: （1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹； （2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹； （3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。卷II一.參考題庫(共30題)1.以孩子兄弟表示法做存儲結(jié)構(gòu)，求樹中結(jié)點x的第i個孩子。2.對給定文件（28，07，39，10，65，14，61，17，50，21）選擇第一個元素28進行劃分，寫出其快速排序第一遍的排序過程。3.設(shè)計兩個有序單鏈表的合并排序算法。4.在操作序列EnQueue（1）、EnQueue（3）、DeQueue、EnQueue（5）、EnQueue（7）、DeQueue、EnQueue（9）之后，隊頭元素和隊尾元素分別是什么？（EnQueue（k）表示整數(shù)k入隊，DeQueue表示隊頭元素出隊）。5.對于右圖所示的樹： 寫出先根遍歷得到的結(jié)點序列。6.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是（） 7.在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0].next，則該線性表為（）。 8.給定一組記錄，其關(guān)鍵碼為字母。記錄按照下面的順序插入一棵空的B—樹中：C，S，D，T，A，M，P，I，B，W，N，G，V，R，K，E，H，O，L，J。請畫出插入這些記錄后的3階B—樹。9.數(shù)據(jù)類型10.設(shè)一組初始記錄關(guān)鍵字序列為（15，17，18，22，35，51，60），要求計算出成功查找時的平均查找長度。11.歸并排序12.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。 13.簡述圖的基本操作及各操作的含義。14.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1，…，an）逆置為（an，…，a1）。15.什么叫平均查找長度？寫出平均查找長度的定義16.設(shè)P1和P2是兩個單鏈表，他們的元素都遞增有序，指出下面函數(shù)F的功能。 17.設(shè)關(guān)鍵字序列（k1，k2，…，kn-1）是堆，設(shè)計算法將關(guān)鍵字序列（k1，k2，…，kn-1，x）調(diào)整為堆。18.設(shè)查找表為（7，15，21，22，40，58，68，80，88，89，120），元素的下標(biāo)依次為1，2，3，……，11。 （1）畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用下標(biāo)表示） （2）說明成功查找到元素40需要經(jīng)過多少次比較？ （3）求在等概率條件下，成功查找的平均比較次數(shù)？19.已知數(shù)據(jù)序列{10，18，4，3，6，12，9，15}，寫出二路歸并排序的每一趟排序結(jié)果。20.模式匹配21.設(shè)一個有向圖為G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，請回答下列各問：對（2）中的鄰接矩陣，給出從頂點v2出發(fā)的BFS序列和BFS生成樹。22.兩個字符串分別為： 的結(jié)果是（）。23.編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。24.畫出含三個結(jié)點的無序樹。25.寫出在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。26.有一個早晨7點到晚上11點營業(yè)的連鎖店，叫7-11店。一次，一位顧客在該店選了4樣?xùn)|西，付款時，營業(yè)員計算后說：“總共是7.11元?！鳖櫩烷_玩笑說：“哦？難道因為你們是7-11店，所以我就要付7.11元嗎？”營業(yè)員沒有聽出是在開玩笑，便回答說：“當(dāng)然不是，我是把4樣?xùn)|西的價格相乘才得出結(jié)果的！”顧客非常吃驚，說：“你怎么把它們相乘呢？，應(yīng)該把它們相加才對！”營業(yè)員聽后，忙說：“噢，對不起，我今天頭非常疼，所以按錯計算器的鍵了。”并趕緊把4樣?xùn)|西的價格相加重算了一遍，但結(jié)果令兩個人都十分驚訝：總和還是7.11元。請設(shè)計一個算法計算這四樣?xùn)|西的價格各是多少？27.已知一有向圖的鄰接表存儲結(jié)構(gòu)如下，則根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點V1出發(fā)，不能得到的頂點序列是（）。 A、V1，V2，V3，V5，V4B、V1，V3，V4，V5，V2C、V1，V2，V4，V5，V3D、V1，V4，V3，V5，V228.閱讀下面程序，并回答有關(guān)問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。簡要說明程序功能。29.設(shè)線性表以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data。完成程序中空格部分。 30.假設(shè)用于通信的電文由字符集{a，b，c，d，e，f，g，h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，試為這8個字母進行哈夫曼編碼。請回答：寫出依此哈夫曼樹對各個字母的哈夫曼編碼。卷II參考答案一.參考題庫1.參考答案:先在鏈表中進行遍歷，在遍歷過程中查找值等于x的結(jié)點，然后由此結(jié)點的最左孩子域firstchild找到值為x結(jié)點的第一個孩子，再沿右兄弟域rightsib找到值為x結(jié)點的第i個孩子并返回指向這個孩子的指針。