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