2024年大學(xué)試題(計算機科學(xué))-數(shù)據(jù)結(jié)構(gòu)考試近5年真題集錦（頻考類試題）帶答案

（圖片大小可自由調(diào)整）2024年大學(xué)試題(計算機科學(xué))-數(shù)據(jù)結(jié)構(gòu)考試近5年真題集錦（頻考類試題）帶答案第I卷一.參考題庫(共100題)1.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進行排序，請寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）2.已知L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列。 a.刪除P結(jié)點的直接后繼結(jié)點的語句序列是（）。 b.刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是（）。 c.刪除P結(jié)點的語句序列是（）。 d.刪除首元結(jié)點的語句序列是（）。 e.刪除尾元結(jié)點的語句序列是（）。 （1）P=P->next； （2）P->next=P； （3）P->next=P->next->next； （4）P=P->next->next； （5）while（P!=NULL）P=P->next； （6）while（Q->next!=NULL）{P=Q；Q=Q->next；} （7）while（P->next!=Q）P=P->next； （8）while（P->next->next!=Q）P=P->next； （9）while（P->next->next!=NULL）P=P->next； （10）Q=P； （11）Q=P->next； （12）P=L； （13）L=L->next； （14）free（Q）；3.用5個權(quán)值{3，2，4，5，1}構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是（）4.用第二種方法，即少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設(shè)計置空隊，判隊空，判隊滿、出隊、入隊及取隊頭元素等六個基本操作的算法。5.待排序的序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當(dāng)進行了兩趟選擇后，結(jié)果序列為（）。6.中綴表達式3*（X+2）-5所對應(yīng)的后綴表達式為（）。7.將如圖所示的森林轉(zhuǎn)換成二叉樹。 8.堆是一個完全二叉樹。9.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。A、2B、3C、4D、610.設(shè)計順序查找算法，將哨兵設(shè)在下標(biāo)高端。11.對機器語言而言，存儲結(jié)構(gòu)是具體的。一般至在（）層次上討論存儲機構(gòu)。12.廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。13.在一個具有n個頂點的有向完全圖中包含有（）條邊A、n（n-1）/2B、n（n-1）C、n（n+1）/2D、n214.棧是實現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。15.數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（）A、正確B、錯誤C、前句對，后句錯D、后句對16.對于一個圖G，若邊集E（G）為有向邊的集合，則該圖為（）。17.已知指針p指向單鏈表中某個結(jié)點，則語句p->next=p->next->next的作用（）。18.無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復(fù)雜度均相同為（）19.散列表的地址區(qū)間為0-17，散列函數(shù)為H（K）=Kmod17。采用線性探測法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。存放元素59需要搜索的次數(shù)是（）。A、2B、3C、4D、520.當(dāng)利用大小為N的數(shù)組存儲循環(huán)隊列時，該隊列的最大長度是（）。A、N-2B、N-1C、ND、N+121.數(shù)據(jù)結(jié)構(gòu)里，實參和形參的關(guān)系（）。A、實參傳給形參B、實參的類型要與形參一致C、實參的個數(shù)要與實參一致D、實參的名稱要與形參的一致22.數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用（）的實現(xiàn)。23.如果進棧的元素序列為A，B，C，D，則可能得到的出棧序列有多少種？寫出全部的可能序列。24.設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）A、3B、4C、5D、625.在線索化二叉樹中，t所指節(jié)點沒有左子樹的充要條件是（）A、t-＞left=NULLB、t-＞ltag=1C、t-＞ltag=1且t-＞left=NULLD、以上都不對26.假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（）個。A、?15B、?16C、?17D、?4727.簡述多關(guān)鍵字文件的作用。28.設(shè)有森林?B=（D，S），???? D={A，B，C，D，E，F(xiàn)，G，H，I，J}，?r∈S? r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F(xiàn)〉，〈G，H〉，〈G，I〉，〈I，J〉}??請回答：畫出與森林對應(yīng)的二叉樹的邏輯結(jié)構(gòu)圖示。29.有回路的有向圖不能完成拓撲排序。30.編寫算法,將一個頭指針為head不帶頭結(jié)點的單鏈表改造為一個單向循環(huán)鏈表，并分析算法的時間復(fù)雜度。31.數(shù)據(jù)結(jié)構(gòu)里，關(guān)于遍歷二叉樹描述正確的是（）。A、二叉樹不可以被遍歷B、二叉樹的遍歷方式有：先序遍歷、中序遍歷、后序遍歷、按層次遍歷C、二叉樹的特殊形式如只有左子樹的情況，是不能遍歷的D、完全二叉樹是不能進行遍歷的32.從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱為（）。A、歸并排序B、選擇排序C、交換排序D、插入排序33.棧的插入和刪除操作在（）。A、棧底B、棧頂C、任意位置D、指定位置34.分塊查找（索引查找）35.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。36.對下列二叉樹進行前序遍歷的結(jié)果為（） A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ37.結(jié)點的帶權(quán)路徑長度38.子串在主串中的位置指的是該子串的最后一個字符在主串中的位置。39.向量、棧和隊列都是（）結(jié)構(gòu)，可以在向量的（）位置插入和刪除元素；對于棧只能在（）插入和刪除元素；對于隊列只能在（）和（）刪除元素。40.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素（包括主對角線上所有元素）依次存放于一維數(shù)組B[1..（n（n+1））/2]中，則在B中確定aij（i＜j）的位置k的關(guān)系為（）。A、i*（i-1）/2+jB、j*（j-1）/2+iC、i*（i+1）/2+jD、j*（j+1）/2+i41.利用逐點插入法建立序列{50，72，43，85，75，20，35，45，65，30}對應(yīng)的二叉排序樹以后，查找元素35要進行（）元素間的比較。A、4次B、5次C、7次D、10次42.試用權(quán)集合{12，4，5，6，1，2}構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。43.已知關(guān)鍵碼序列為（Jan，F(xiàn)eb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec），散列表的地址空間為0~16，設(shè)散列函數(shù)為H（x）=，其中i為關(guān)鍵碼中第一個字母在字母表中的序號，采用線性探測法和鏈地址法處理沖突，試分別構(gòu)造散列表，并求等概率情況下查找成功的平均查找長度。44.在索引表中，每個索引項至少包含（）和（）等信息45.已知下列各種初始狀態(tài)（長度為n）的元素，試問當(dāng)利用直接插入排序進行排序時，至少需要進行多少次比較（要求排序后的記錄由小到大順序排列）？ ⑴關(guān)鍵碼從小到大有序（key1…>keyn）。 ⑶奇數(shù)關(guān)鍵碼順序有序，偶數(shù)關(guān)鍵碼順序有序（key1<key3<…，key2key4…）。 ⑷前半部分元素按關(guān)鍵碼順序有序，后半部分元素按關(guān)鍵碼順序有序，即：（key1<key2<…<keym，keym+1< keym+2<…）46.括號匹配算法中，掃描到左括號要進棧，掃描到右括號要（）。A、出棧B、進棧C、不操作D、以上都不對47.畫出廣義表的頭尾鏈表存儲結(jié)構(gòu)。48.關(guān)于特殊二叉樹的遍歷，下列選項中說法正確的是（）。A、完全二叉樹不能進行遍歷B、完全二叉樹可以進行遍歷C、完全二叉樹不可以進行遍歷D、滿二叉樹不是完全二叉樹49.在具有n個單元的循環(huán)隊列中，隊滿時共有（）個元素。50.假設(shè)以順序存儲結(jié)構(gòu)實現(xiàn)一個雙向棧，即在一維數(shù)組的存儲空間中存在著兩個棧，它們的棧底分別設(shè)在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧tws的三個操作：初始化inistack（tws）、入棧push（tws，i，x）和出棧pop（tws，i）的算法，其中i為0或1，用以分別指示設(shè)在數(shù)組兩端的兩個棧，并討論按過程（正/誤狀態(tài)變量可設(shè)為變參）或函數(shù)設(shè)計這些操作算法各有什么有缺點。51.設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為（） A、O（1）B、O（n2）C、O（n）D、O（n3）52.表達式求值算法需要兩個棧，它們分別是下列哪些（），分別用于存儲數(shù)據(jù)和符號。A、數(shù)據(jù)棧B、符號棧C、中間結(jié)果棧D、漢字棧53.數(shù)據(jù)結(jié)構(gòu)里，結(jié)構(gòu)體數(shù)組的下標(biāo)不是從（）開始的。A、0B、1C、2D、354.稀疏矩陣一般的壓縮存儲方法有兩種，即（）。A、二維數(shù)組和三維數(shù)組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表55.連通圖G的生成樹是一個包含G的所有n個頂點和n-1條邊的子圖。56.利用簡單選擇排序?qū)個記錄進行排序，最壞情況下，記錄交換的次數(shù)為（）。57.當(dāng)待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復(fù)雜性的主要因素。58.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A、可以順序存儲B、數(shù)據(jù)元素是一個字符C、可以鏈式存儲D、數(shù)據(jù)元素可以是多個字符59.一個子串在包含它的主串中的位置是指（）。A、子串的最后那個字符在主串中的位置B、子串的最后那個字符在主串中首次出現(xiàn)的位置C、子串的第一個字符在主串中的位置D、子串的第一個字符在主串中首次出現(xiàn)的位置60.線索鏈表中的rtag域值為（）時，表示該結(jié)點無右孩子，此時（）域為指向該結(jié)點后繼線索的指針。61.分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是冒泡算法，最費時間的是（）算法。62.由二叉樹的后序和（）遍歷序列，可以唯一確定一棵二叉樹。63.單鏈表的主要優(yōu)點是（）A、便于隨機查詢B、存儲密度高C、邏輯上相鄰的元素在物理上也是相鄰的D、插入和刪除比較方便64.已知一關(guān)鍵碼序列為：3，87，12，61，70，97，26，45。試根據(jù)堆排序原理，填寫完整下示各步驟結(jié)果。 65.直接選擇排序是一種穩(wěn)定的排序方法。66.數(shù)據(jù)元素是數(shù)據(jù)的基本的單位，它（）A、只能有一個數(shù)據(jù)項組成B、至少有二個數(shù)據(jù)項組成C、可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D、至少有一個數(shù)據(jù)項為指針類型67.下圖為一棵3階B-樹。在該樹上插入元素的B-樹是（）。 A、aB、bC、cD、d68.線性結(jié)構(gòu)之隊列的應(yīng)用包括哪些（）。A、消息的緩存B、操作系統(tǒng)的作業(yè)調(diào)度C、離散事件的模擬D、進制轉(zhuǎn)換69.下列選項中是定義結(jié)構(gòu)體類型的指針變量的格式不正確的是（）。A、struct結(jié)構(gòu)名指針變量名B、struct結(jié)構(gòu)名變量名C、static結(jié)構(gòu)名指針變量名D、struct指針變量名結(jié)構(gòu)名70.數(shù)據(jù)的存儲結(jié)構(gòu)被分為（）、（）、（）和（）四種。71.散列表表長m=14，散列函數(shù)為h（k）=k%11，表中已有4個記錄，如果用二次探測再散列處理沖突，關(guān)鍵字為49的記錄的存儲地址是（）。 A、8B、3C、5D、972.當(dāng)利用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為（）A、?N-2B、?N-1C、?ND、?N+173.若要把n個頂點連接為一個連通圖，則至少需要（）條邊。A、?nB、?n+1C、?n-1D、?2n74.對有18個元素的有序表作二分（折半）查找，則查找A[3]的比較序列的下標(biāo)為（）。A、?1、2、3B、?9、5、2、3C、?9、5、3D、?9、4、2、375.在n個結(jié)點的單鏈表中，查找第i個元素，和修改第i個元素的時間復(fù)雜度都是（）。A、O（1）B、O（n）C、O（nn）D、都不對76.下述幾種排序方法中，要求內(nèi)存最大的是（）。A、希爾排序B、快速排序C、歸并排序D、堆排序77.編寫一個算法判斷s2是否是s1的子串。78.在循環(huán)雙鏈表的p結(jié)點之后插入s結(jié)點的操作是（）A、AB、BC、CD、D79.假定對線性表(38,25,74,52,48)進行哈希存儲，采用H(K)=K%7作為哈希函數(shù)，采用線性探測法處理沖突，則平均查找長度為（）80.在完全二叉樹中，若一個結(jié)點是葉子結(jié)點，則它沒有（）A、兄弟結(jié)點B、父結(jié)點C、左子結(jié)點和右子結(jié)點D、左子結(jié)點、右子結(jié)點和兄弟結(jié)點81.什么是順序表？什么是棧？什么是隊列？82.當(dāng)各邊上的權(quán)值（）時，BFS算法可用來解決單源最短路徑問題。A、均相等B、均互不相等C、不一定相等D、均相等或均不等83.程序越短，程序運行的時間就越少。84.S="morning"，執(zhí)行求子串函數(shù)SubStr（S，2，2）后的結(jié)果為（）。A、"mo"B、"or"C、"in"D、"ng"85.線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表。86.假設(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；}87.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為（）。A、8B、63.5C、63D、788.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A、一對一B、一對多C、多對多D、每一個元素都有一個直接前驅(qū)和一個直接后繼89.畫出下列每個廣義表的帶表頭附加結(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）））90.采用三元組表存儲稀疏矩陣，是為了（）。A、節(jié)省存取時間B、節(jié)省存儲空間C、提高對矩陣元素的訪問速度D、提高對矩陣運算的可靠性91.如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（）。A、1B、2C、3D、492.已知如下圖所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb93.（）中任何兩個結(jié)點之間都沒有邏輯關(guān)系。A、集合B、圖狀結(jié)構(gòu)C、樹型結(jié)構(gòu)D、線性結(jié)構(gòu)94.一個算法應(yīng)該是（）。A、程序B、問題求解步驟的描述C、要滿足五個基本特性D、A和C95.在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序為穩(wěn)定排序96.設(shè)有二維數(shù)組a[5][6]，每個元素占相鄰的8個字節(jié)，存儲器按字節(jié)編址，已知a的起始地址是1000，試計算按行序優(yōu)先時，元素a[3][5]的起始地址。97.簡述樹、二叉樹、滿二叉樹和完全二叉樹的結(jié)構(gòu)特性。98.廣義表運算式HEAD（TAIL（（a，b，c），（x，y，z）））的結(jié)果是：（）。99.設(shè)有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為（）。100.（）既對數(shù)據(jù)施加的操作。第I卷參考答案一.參考題庫1.參考答案： 2.參考答案： a.（11）（3）（14） b.（10）（12）（8）（3）（14） c.（10）（12）（7）（3）（14） d.（12）（11）（3）（14） e.（9）（11）（3）（14）3.參考答案：334.參考答案：算法設(shè)計如下： 5.參考答案：1，2，4，8，3，5，96.參考答案：3*2+*57.參考答案：8.參考答案：正確9.參考答案：B10.參考答案：將哨兵設(shè)置在下標(biāo)高端，表示從數(shù)組的低端開始查找，在查找不成功的情況下，算法自動在哨兵處終止。具體算法如下： 11.參考答案：高級語言12.參考答案：錯誤13.參考答案：B14.參考答案：正確15.參考答案：B16.參考答案：有向圖17.參考答案：刪除p的后繼結(jié)點18.參考答案：O（1）19.參考答案：C20.參考答案：C21.參考答案：A,B,C22.參考答案：計算機語言23.參考答案：24.參考答案：B25.參考答案：B26.參考答案：B27.參考答案：多關(guān)鍵字文件是既包含主關(guān)鍵字索引、又包含多個次關(guān)鍵字索引的文件。在實際中，不僅會根據(jù)主關(guān)鍵字做查找，同時也會根據(jù)一系列次關(guān)鍵字做查找，此時使用多關(guān)鍵字文件可以提高查找效率。28.參考答案： 29.參考答案：正確30.參考答案： voidlinklist_c（Lnode*heaD. {Lnode*p；p=head； if（!p）returnERROR； while（p->next!=NULL） p=p->next； p->next=head； } 設(shè)單鏈表的長度（數(shù)據(jù)結(jié)點數(shù)）為N，則該算法的時間主要花費在查找鏈表最后一個結(jié)點上（算法中的while循環(huán)），所以該算法的時間復(fù)雜度為O（N）。31.參考答案：B32.參考答案：D33.參考答案：B34.參考答案： 分塊查找以前兩個為基礎(chǔ)，將待查記錄分成若干塊，每塊的關(guān)鍵字無序，但每塊的關(guān)鍵字的最大值有序，查找時，先查找到待查記錄所在的塊，再在塊內(nèi)進行順序查找。找塊時，即可以用折半查找，也可用順序查找。35.參考答案：536.參考答案：C37.參考答案： 該結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積。38.參考答案：錯誤39.參考答案：線性任何棧頂隊尾隊首40.參考答案：B41.參考答案：A42.參考答案： WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=6943.參考答案：H.Jan）=10/2=5，H（Feb）=6/2=3，H（Mar）=13/2=6，H（Apr）=1/2=0 H.May）=13/2=6，H（Jun）=10/25，H（Jul）=10/25，H（Aug）=1/2=0 H.Sep）=19/2=8，H（Oct）=15/2=7，H（Nov）=14/2=7，H（Dec）=4/2=2 采用線性探測法處理沖突，得到的閉散列表如下： 平均查找長度=（1+1+1+1+2+4+5+2+3+5+6+1）/12=32/12 采用鏈地址法處理沖突，得到的開散列表如下： 平均查找長度=（1×7+2×4+3×1）/12=18/12 44.參考答案：關(guān)鍵碼；關(guān)鍵碼對應(yīng)的記錄在存儲器中的位置45.參考答案：依題意，最好情況下的比較次數(shù)即為最少比較次數(shù)。 ⑴插入第i（2≤i≤n）個元素的比較次數(shù)為1，因此總的比較次數(shù)為：1+1+……+1=n-1 ⑵插入第i（2≤i≤n）個元素的比較次數(shù)為i，因此總的比較次數(shù)為：2+3+……+n=（n-1）（n+2）/2 ⑶比較次數(shù)最少的情況是所有記錄關(guān)鍵碼按升序排列，總的比較次數(shù)為：n-1 ⑷在后半部分元素的關(guān)鍵碼均大于前半部分元素的關(guān)鍵碼時需要的比較次數(shù)最少，總的比較次數(shù)為：n-146.參考答案：A47.參考答案：48.參考答案：B49.參考答案：n-150.參考答案： 51.參