2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-數(shù)據(jù)結(jié)構(gòu)歷年考試高頻考點(diǎn)試題附帶答案

2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-數(shù)據(jù)結(jié)構(gòu)歷年考試高頻考點(diǎn)試題附帶答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(kù)(共25題)1.廣度遍歷2.設(shè)計(jì)一個(gè)算法，功能是在帶頭結(jié)點(diǎn)的單鏈表head中刪除數(shù)據(jù)域值最小的結(jié)點(diǎn)。 3.有向圖如下圖所示，畫出鄰接矩陣和鄰接表。 4.將關(guān)鍵字（45，87，30，33，63，27，51，76）依次插入到一棵初始為空的二叉排序樹中。請(qǐng)回答：畫出對(duì)應(yīng)的二叉排序樹。5.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是（） A、AB、BC、CD、D6. 的結(jié)果串為（）A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF7.試找出滿足下列條件的所有二叉樹： （1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。8.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）A、0243165B、0135642C、0123465D、01234569.某無(wú)向圖的鄰接矩陣如下所示，則該圖中有（）條邊，有（）個(gè)頂點(diǎn)。 10.利用棧的基本操作，寫一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法intStackSize（SeqStackS），并說(shuō)明S為何不作為指針參數(shù)？11.編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。12.假定一個(gè)待散列存儲(chǔ)的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長(zhǎng)度。13.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為則數(shù)據(jù)結(jié)構(gòu)A是（）A、線性結(jié)構(gòu)B、樹型結(jié)構(gòu)C、物理結(jié)構(gòu)D、圖型結(jié)構(gòu)14.二路歸并排序的時(shí)間復(fù)雜度為（） A、AB、BC、CD、D15.寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型。16.沖突17.設(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〉}??請(qǐng)回答：畫出與森林對(duì)應(yīng)的二叉樹的邏輯結(jié)構(gòu)圖示。18.用線性表的順序結(jié)構(gòu)來(lái)描述一個(gè)城市的設(shè)計(jì)和規(guī)劃合適嗎？為什么？19.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（） A、AB、BC、CD、D20.稀疏多項(xiàng)式采用的順序存儲(chǔ)結(jié)構(gòu)SqPoly定義為： 采用上題給定的條件和存儲(chǔ)結(jié)構(gòu)，編寫求P（x）=Pn1（x）-Pn2（x）的算法，將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的算法的時(shí)間復(fù)雜度。21.如果希望循環(huán)隊(duì)列中的元素都能得到利用，則需設(shè)置一個(gè)標(biāo)志域tag，并以tag的值為0和1來(lái)區(qū)分，尾指針和頭指針值相同時(shí)的隊(duì)列狀態(tài)是“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)列和出隊(duì)列的算法，并從時(shí)間和空間角度討論設(shè)標(biāo)志和不設(shè)標(biāo)志這兩種方法的使用范圍（如當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí)，哪一種方法較好）。22.將如圖所示的二叉樹轉(zhuǎn)換為樹。 23.設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。堆排序24.空間復(fù)雜度25.在下面的程序段中，寫出對(duì)ｘ的賦值語(yǔ)句的頻度。（表示為n的函數(shù)） 第2卷一.參考題庫(kù)(共25題)1.在程序設(shè)計(jì)中，常用下列三種不同的出錯(cuò)處理方式： （1）用exit語(yǔ)句終止執(zhí)行并報(bào)告錯(cuò)誤； （2）以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回； （3）設(shè)置一個(gè)整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。 試討論這三種方法各自的優(yōu)缺點(diǎn)。2.求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。3.線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？4.已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：ACDBGIHFE和ABCDEFGHI。請(qǐng)畫出該二叉樹，并寫出它的前序遍歷的序列。5.分析以下各程序段，并用大O記號(hào)表示其執(zhí)行時(shí)間。 6.在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength（L）運(yùn)算。7.簡(jiǎn)述常用的四種哈希函數(shù)及其計(jì)算規(guī)則。8.對(duì)輸入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；當(dāng)k=6時(shí)，使用置換-選擇算法，寫出建立的初始敗者樹及生成的初始?xì)w并段。9.已知一個(gè)無(wú)向圖的鄰接表如圖所示，要求：畫出該無(wú)向圖10.有七個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL。11.試將下列遞推過(guò)程改寫為遞歸過(guò)程。 12.寫出下列程序段的運(yùn)行結(jié)果（棧中的元素類型是char）： 13.原地工作14.最小生成樹15.最短路徑16.設(shè)有10000個(gè)記錄，通過(guò)分塊劃分為若干子表并建立索引，那么為了提高查找效率，每一個(gè)子表的大小應(yīng)設(shè)計(jì)為多大？17.強(qiáng)連通分量18.在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成下列程序填空。 19.設(shè)語(yǔ)句x++的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（） A、O（1）B、O（n2）C、O（n）D、O（n3）20.希爾排序21.設(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〉}請(qǐng)回答：請(qǐng)畫出此二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)的圖示并給出C語(yǔ)言描述。22.若進(jìn)隊(duì)的序列為：A，B，C，D，則出隊(duì)的序列是（）。 A、AB、BC、CD、D23.（1）一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56）利用堆排序（堆頂元素是最小元素）的方法建立初始堆（要求以完全二叉樹描述?）。 （2）對(duì)關(guān)鍵字序列（56，51，71，54，46，106）利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。 （3）一組記錄的關(guān)鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方法，分別給出（1，1）歸并、（2，2）歸并、（4，4）歸并的結(jié)果序列。24.已知一組元素的排序碼為： （46，74，16，53，14，26，40，38，86，65，27，34）利用直接選擇排序方法寫出每次選擇和交換后的排列結(jié)果。25.設(shè)一個(gè)有向圖為G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，請(qǐng)回答下列各問(wèn)：對(duì)（2）中的鄰接矩陣，給出從頂點(diǎn)v2出發(fā)的DFS序列和DFS生成樹。第3卷一.參考題庫(kù)(共25題)1.從如圖所示的鄰接矩陣可以看出，該圖共有（）個(gè)頂點(diǎn)。如果是有向圖，該圖共有（）條弧；如果是無(wú)向圖，則共有（）條邊。2.已知一組元素的排序碼為： （46，74，16，53，14，26，40，38，86，65，27，34）利用堆排序的方法寫出在構(gòu)成初始堆和利用堆排序的過(guò)程中，每次篩運(yùn)算后的排列結(jié)果，并畫出初始堆所對(duì)應(yīng)的完全二叉樹。3.對(duì)于下面的帶權(quán)圖，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為（）。 4.前綴編碼5.廣義表6.分析以下程序段的時(shí)間復(fù)雜度。 7.假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。8.寫出下圖中全部可能的拓?fù)渑判蛐蛄小?9.靜態(tài)查找表10.平衡二叉樹11.順序查找12.拉鏈法（鏈地址法）13.設(shè)A=（a1，…，am和B=（b1，…，bn）均為順序表，Aˊ和Bˊ分別為A和B中除去最大共同前綴后的子表。若Aˊ=Bˊ空表，則A=B；若Aˊ=空表，而Bˊ≠空表，或者兩者均不為空表，且Aˊ的首元小于Bˊ的首元，則A＜B；否則A＞B。試寫一個(gè)比較A，B大小的算法。14.試編寫算法，計(jì)算的i!*2i值并存入數(shù)組a[0..arrsize-1]的第i-1個(gè)分量中（i=1，2，…，n）。假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint，則當(dāng)n>arrsize或?qū)δ硞€(gè)k（1≤k≤n），使k!·2k＞maxint時(shí)，應(yīng)按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。15.線索二叉樹16.下列圖的拓?fù)湫蛄惺牵ǎ?A、5、2、3、4、6B、5、2、3、6、4C、5、6、4、2、3D、2、3、4、5、617.畫出下列每個(gè)廣義表的帶表頭附加結(jié)點(diǎn)的鏈接存儲(chǔ)結(jié)構(gòu)圖并分別計(jì)算出它們的長(zhǎng)度和深度。 （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）））18.連通分量19.設(shè)一組初始記錄關(guān)鍵字序列為（45，80，48，40，22，78），則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。20.已知如圖所示的一個(gè)網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)生過(guò)程。 21.設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（）條邊。 A、AB、BC、CD、D22.已知數(shù)據(jù)序列{10，18，4，3，6，12，9，15}，寫出二路歸并排序的每一趟排序結(jié)果。23.下面程序段的時(shí)間復(fù)雜度為（） A、O（m2）B、O（n2）C、O（m*n）D、O（m+n）24.已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。 A、abecdfB、aecbdfC、aebcfdD、aedfcb25.設(shè)有森林如圖所示，請(qǐng)回答： 畫出該二叉樹的中序線索二叉鏈表的圖示并給出C語(yǔ)言描述。第1卷參考答案一.參考題庫(kù)1.參考答案: 按層次編歷方式，從某一點(diǎn)V0開始遍歷它的所有鄰接點(diǎn)V1，V2……，再依次訪問(wèn)V1，V2..的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，直到所有的點(diǎn)均遍歷完成。2.參考答案:3.參考答案:4.參考答案: 5.參考答案:D6.參考答案:D7.參考答案: （1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹； （2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹； （3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。8.參考答案:C9.參考答案:9；610.參考答案: 上述算法的目的只要得到S棧的結(jié)點(diǎn)個(gè)數(shù)就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對(duì)原來(lái)的棧中元素進(jìn)行任何改變。系統(tǒng)會(huì)把原來(lái)的棧按值傳遞給形參，函數(shù)只對(duì)形參進(jìn)行操作，最后返回元素個(gè)數(shù)。11.參考答案:12.參考答案: 散列函數(shù)：H（K）=k%m其中依題意得m=13 H（32）=32%13=6 H（5）=75%13=10 H（29）=29%13=3 H（63）=63%13=11 H（8）=48%13=9 H（94）=94%13=3（沖突） 設(shè)d0=H（K）=H（94）=3 d1=（d0+1）%m=（3+1）%13=4 H（25）=25%13=12 H（46）=46%13=7 H（18）=18%13=5 H（70）=70%13=5（沖突） 設(shè)d0=H（K）=H（70）=5 d1=（d0+1）%m=（5+1）%13=6（沖突） d2=（d1+1）%m=（6+1）%13=7（沖突） d3=（d2+1）%m=（7+1）%13=8 ASL=（8*1+1*2+1*4）/10=1.4 13.參考答案:B14.參考答案:C15.參考答案:16.參考答案: 散列函數(shù)可能會(huì)把兩個(gè)或以上的不同關(guān)鍵字映射到同一地址，這種情況為沖突。17.參考答案: 18.參考答案: 不合適。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。19.參考答案:A20.參考答案: 21.參考答案: 22.參考答案:第一步，加線。第二步，抹線。第三步，調(diào)整。過(guò)程如圖所示。23.參考答案:24.參考答案: S（n）定義為該算法所耗費(fèi)的村粗空間，是問(wèn)題規(guī)模n的函數(shù)。25.參考答案: 1+（1+2+（1+2+3）+…+（1+2+…+n）=n（n+1）（n+2）/6???O（n3）第2卷參考答案一.參考題庫(kù)1.參考答案: （1）exit常用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。 （2）以函數(shù)的返回值判斷正確與否常用于子程序的測(cè)試，便于實(shí)現(xiàn)程序的局部控制。 （3）用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類型，便于迅速確定錯(cuò)誤。2.參考答案:3.參考答案: 線性結(jié)構(gòu)元素之間的關(guān)系是一對(duì)一的，在線性結(jié)構(gòu)中只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其他的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。而非線性結(jié)構(gòu)則沒(méi)有這個(gè)特點(diǎn)，元素之間的關(guān)系可以是一對(duì)多的或多對(duì)多的。4.參考答案:恢復(fù)的二叉樹為： 5.參考答案:⑴基本語(yǔ)句是k=k+10*i，共執(zhí)行了n-2次，所以T（n）=O（n）。 ⑵基本語(yǔ)句是k=k+10*i，共執(zhí)行了n次，所以T（n）=O（n）。 ⑶分析條件語(yǔ)句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T（n）=O（n）。 ⑷設(shè)循環(huán)體共執(zhí)行T（n）次，每循環(huán)一次，循環(huán)變量y加1，最終T（n）=y，即： T.n）+1）2≤n，所以T（n）=O（n1/2）。 ⑸x++是基本語(yǔ)句，所以6.參考答案:7.參考答案: 除余法：選取一個(gè)適當(dāng)?shù)恼麛?shù)p（通常p為不大于哈希表存儲(chǔ)空間尺寸的最大素?cái)?shù)），以元素的關(guān)鍵字值k除以p，得到的余數(shù)作為元素的存儲(chǔ)地址，即h（k）=k%p。 數(shù)字分析法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲(chǔ)空間地址碼位數(shù)多、每一位的取值范圍及關(guān)鍵字的取值分布情況預(yù)先知道，則可以對(duì)元素關(guān)鍵字的各位進(jìn)行分析，去掉分布較集中的位、保留分布較均勻的位。 折疊法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲(chǔ)空間地址碼位數(shù)多，但關(guān)鍵字的取值分布情況未知，則可以用折疊法將關(guān)鍵字分為幾段（除了最后一段位數(shù)可以少一些，其他各段的位數(shù)均等于存儲(chǔ)空間地址碼位數(shù)），并將所有段的值做疊加求和運(yùn)算，將疊加和的最高位進(jìn)位舍去后取剩余部分作為元素的存儲(chǔ)地址。 平方取中法：對(duì)元素的關(guān)鍵字值求平方，并取中間幾位作為元素的存儲(chǔ)地址。8.參考答案:9.參考答案:10.參考答案: 11.參考答案: 12.參考答案:程序段的運(yùn)行結(jié)果為stack。13.參考答案: 算法執(zhí)行時(shí)，若額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。14.參考答案: 一個(gè)帶權(quán)連通無(wú)向圖的生成樹中邊的權(quán)值之和最小的那個(gè)叫做此圖的最小生成樹。15.參考答案: 帶權(quán)圖中，從一個(gè)頂點(diǎn)V0到另一個(gè)頂點(diǎn)V1的一條路徑上所經(jīng)過(guò)邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長(zhǎng)度，其中最短的那條稱作最短路徑。此路徑的長(zhǎng)度稱為從v到u的距離。16.參考答案:每個(gè)子表的大小應(yīng)為。17.參考答案: 有向圖的極大強(qiáng)連通子圖，稱為有向圖的強(qiáng)連通分量。18.參考答案:19.參考答案:D20.參考答案: 是插入排序的一種，又叫縮小增量排序，先按增量進(jìn)行分組，組內(nèi)插入排序，然后每次縮短增量，再進(jìn)行分