2023年大學試題(計算機科學)-數(shù)據(jù)結(jié)構考試歷年高頻考點試題含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(共50題)1.簡述結(jié)點的權、結(jié)點的帶權路徑長度、樹的帶權路徑長度等基本術語的含義。2.在二叉樹的順序存儲結(jié)構中，實際上隱含著雙親的信息，因此可和三叉鏈表對應。假設每個指針域占4個字節(jié)，每個信息域占k個字節(jié)。試問：對于一棵有n個結(jié)點的二叉樹，且在順序存儲結(jié)構中最后一個節(jié)點的下標為m，在什么條件下順序存儲結(jié)構比三叉鏈表更節(jié)省空間？3.二次聚集4.設定串采用順序存儲結(jié)構，寫出對串s1和串s2比較大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分別表示s1＜s2，s1=s2和s1＞s2。5.試寫一個判別給定二叉樹是否為二叉排序樹的算法，設此二叉樹以二叉鏈表作存儲結(jié)構。且樹中結(jié)點的關鍵字均不同。6.將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉排序樹中，請畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。7.對圖所示的無向圖，依次輸入各邊：（v1，v2）、（v1，v4）、（v2，v3）、（v3，v4）、（v3，v5），請回答下列各問： （2）畫出該圖的鄰接表（頭插法建表）存儲結(jié)構圖示。8.設待排序的關鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關鍵字序列的狀態(tài)?？焖倥判?.下面程序段的時間復雜度為（） 10.已知如下所示長度為12的表：（Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）按表中元素順序構造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。11.假設有兩個按元素遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構。請編寫算法，將表A和表B歸并成一個按元素值非遞減有序（允許值相同）排列的線性表C，并要求利用原表（即表A和表B）的結(jié)點空間存放表C。12.對于List類型的線性表，編寫出下列算法： 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。13.包含n個結(jié)點的二叉樹，高度最大為（），高度最小為（）。14.已知某哈希表的裝載因子小于1，哈希函數(shù)H（key）為關鍵字（標識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關鍵字的算法。15.雙向鏈表16.數(shù)據(jù)的存儲結(jié)構17.下列是順序存儲線性表排序的算法問：此算法的時間復雜性為（）。 A、O（n）???B、（n2）???C、（n*i）???D、（n*j）18.下面程序段的時間復雜性的量級為（） A、O（1）B、O（n）C、O（n2）D、O（n3）19.設計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。20.棧上的基本運算有哪些？21.簡述分塊查找對待查找數(shù)據(jù)集合的要求及分塊查找的具體步驟。22.設順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性23.已知有一個單向循環(huán)鏈表，其每個結(jié)點中含三個域：pre，data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點的指針域，pre也為指針域，但它的值為空，試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)點的指針域。24.以下函數(shù)為直接選擇排序算法，對a[1],a[2],…a[n]中的記錄進行直接選擇排序，完成程序中的空格。 25.算法中R[n+1]的作用是什么？ 26.將如圖所示的樹轉(zhuǎn)換為二叉樹。 27.已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？28.已知權值集合為{5，7，2，3，6，9}，要求給出哈夫曼樹，并計算帶權路徑長度WPL。29.具有什么特征的數(shù)據(jù)結(jié)構被稱為棧和隊列？先進后出、棧頂、棧底、先進先出、隊頭、隊尾的概念是什么？30.深度優(yōu)先搜索（DFS）31.已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。畫出二叉樹的形態(tài)。32.試編寫如下定義的遞歸函數(shù)的遞歸算法，并根據(jù)算法畫出求g（5，2）時棧的變化過程。 33.快速排序34.順序表的定義如下： 其中ElemType的含義是：通用數(shù)據(jù)類型；size的含義是：（）。35.在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0].next，則該線性表為（）。 36.指出下述程序段的功能是什么？ 37.設計順序查找算法，將哨兵設在下標高端。38.編寫算法求給定結(jié)點在二叉排序樹中所在的層數(shù)。39.原地工作40.假定一個待哈希存儲的線性表為（32，75，29，63，48，94，25，36，18，70，49，80），哈希地址空間為HT[12]，若采用除留余數(shù)法構造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長度。41.簡述數(shù)據(jù)結(jié)構中討論的三種經(jīng)典結(jié)構的邏輯特征是什么？42.簡述以下算法的功能。 43.下面程序的時間復雜度為（）。 x=0； for（i=1；i<n；i++）for（j=i+1；j<=n；j++） x++；</n；i++） A、O（）B、O（n2）C、O（1）D、O（n）44.下面算法是判斷字符串是否為回文（即正讀和倒讀相同），試完成程序填空。 45.外部排序46.已知一組元素為（46，25，78，62，12，37，70，29），畫出按元素排列順序輸入生成的一棵二叉搜索樹。47.將下面圖5-16所示的樹轉(zhuǎn)換為二叉樹，圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林。 48.已知P結(jié)點是某雙向鏈表的中間結(jié)點，試從下列提供的答案中選擇合適的語句序列。 a.在P結(jié)點后插入S結(jié)點的語句序列是（）。 b.在P結(jié)點前插入S結(jié)點的語句序列是（）。 c.刪除P結(jié)點的直接后繼結(jié)點的語句序列是（）。 d.刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是（）。 e.刪除P結(jié)點的語句序列是（）。 （1）P->next=P->next->next； （2）P->priou=P->priou->priou； （3）P->next=S； （4）P->priou=S； （5）S->next=P； （6）S->priou=P； （7）S->next=P->next； （8）S->priou=P->priou； （9）P->priou->next=P->next； （10）P->priou->next=P； （11）P->next->priou=P； （12）P->next->priou=S； （13）P->priou->next=S； （14）P->next->priou=P->priou； （15）Q=P->next； （16）Q=P->priou； （17）free（P）； （18）free（Q）；49.完成從一維數(shù)組A[n]上進行快速排序的遞歸算法。 50.有七個帶權結(jié)點，其權值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點構造一棵哈夫曼樹，并計算出帶權路徑長度WPL。第1卷參考答案一.參考題庫1.正確答案: 結(jié)點的權和結(jié)點的帶權路徑長度：在實際應用中，往往給樹中的結(jié)點賦予一個具有某種意義的實數(shù)，該實數(shù)就稱為是結(jié)點的權。結(jié)點的帶權路徑長度是指從樹根到該結(jié)點的路徑長度與結(jié)點的權的乘積。 2.正確答案: 3.正確答案: 指在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象。4.正確答案:5.正確答案:6.正確答案:二叉排序樹如下圖所示，其平均查找長度=1+2×2+3×2+4×2=19/7 7.正確答案: 8.正確答案:9.正確答案:O(n)10.正確答案:11.正確答案:12.正確答案: 13.正確答案: n；14.正確答案:15.正確答案: 線性表采用鏈式存儲時，每個結(jié)點除一個數(shù)據(jù)域外，包含兩個指針域，一個指向該結(jié)點的直接后繼，一個指向該結(jié)點的直接前驅(qū)，這種方式構成的鏈表，即為雙向鏈表。16.正確答案: 指數(shù)據(jù)結(jié)構在計算機中的表示，也成物理結(jié)構。主要有順序存儲、連接存儲、索引存儲、散列存儲。17.正確答案:B18.正確答案:D19.正確答案:20.正確答案: 21.正確答案: 22.正確答案: voidInsert_sq（Sqlistva[]，ElemTypex） {inti，j，n； n=length（va[]）； if（x>=va[i]） va[n]=x； else {i=0； while（x>va[i]）i++； for（j=n-1；j>=I；j--） va[j+1]=va[j]； va[i]=x；} n++； }23.正確答案: 24.正確答案: 25.正確答案: 哨兵。避免邊界檢測，提高程序運行效率。26.正確答案:27.正確答案: 28.正確答案: 樹形態(tài)： 帶權路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=7929.正確答案: 棧：一種插入和刪除都只能在表的同一端進行的線性表。 隊列：一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。 先進后出：元素是以e1，e2，……en順序進入數(shù)據(jù)結(jié)構，以相反的順序即en，en-1，……e1離開數(shù)據(jù)結(jié)構。 棧頂：允許進行插入和刪除操作的一端。 棧底：棧中與棧頂相對的另一端。 先進先出：元素是以e1，e2，……en順序進入數(shù)據(jù)結(jié)構，以相同的順序即e1，e2，……en。離開數(shù)據(jù)結(jié)構。 隊頭：允許刪除操作的一端。 隊尾：允許插入操作的一端。30.正確答案: 類似樹的先序遍歷，在圖中任選一個頂點作為出發(fā)頂點V0，訪問V0后，依次從V0的沒被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索。直到與V0所連通的所有頂點均被訪問。如果，此時圖中還有頂點尚未訪問，則從剩余的頂點中再任選一個頂點作為出發(fā)頂點V0，重復上述過程，直到圖中全部頂點均被訪問為止。31.正確答案: 32.正確答案: 33.正確答案: 快速排序的基本思想是把當前待排序的記錄，存放到整個表排好序后，它應當在的最終位置上。將原來的待排序表分割成兩部分，其中一部分表中的關鍵字均比另一部分表中的關鍵字小。然后，分別對兩部分表用同樣的方式進行排序，直到整個表排好序。34.正確答案:順序表中元素的個數(shù)35.正確答案:（38，56，25，60，42，74）36.正確答案:這段程序的功能是將隊列1的所有元素復制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2，然后再把隊列2的元素復制到隊列1中。37.正確答案:將哨兵設置在下標高端，表示從數(shù)組的低端開始查找，在查找不成功的情況下，算法自動在哨兵處終止。具體算法如下： 38.正確答案:根據(jù)題目要求采用遞歸方法，從根結(jié)點開始查找結(jié)點p，若待查結(jié)點是根結(jié)點，則深度為1，否則到左子樹（或右子樹）上去找，查找深度加1。 具體算法如下： 39.正確答案: 算法執(zhí)行時，若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。40.正確答案:41.正確答案: 三種經(jīng)典結(jié)構：線性表、樹和圖。邏輯特征分別為： （1）線性表：一對一。有且僅有一個開始結(jié)點和一個終端結(jié)點，其余的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點和一個后繼結(jié)點。 （2）樹：一對多。有且僅有一個開始結(jié)點，可有若干個終端結(jié)點，其余的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點，可以有若干個后繼結(jié)點。 （3）圖：多對多?？捎腥舾蓚€開始結(jié)點和終端結(jié)點，其余的內(nèi)部結(jié)點可以有若干個前趨結(jié)點和若干個后繼結(jié)點。42.正確答案: （1）如果L的長度不小于2，將L的首元結(jié)點變成尾元結(jié)點。 （2）將單循環(huán)鏈表拆成兩個單循環(huán)鏈表。43.