2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)考試近5年真題集錦（頻考類試題）帶答案

（圖片大小可自由調(diào)整）2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)考試近5年真題集錦（頻考類試題）帶答案第I卷一.參考題庫(共100題)1.若L是splist類型的順序表，則表中的第i個數(shù)據(jù)元素是（）。2.對于結(jié)點類型為LNode的單鏈表，編寫出下列算法： 統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。3.快速排序方法在（）情況下最不利于發(fā)揮其長處。A、要排序的數(shù)據(jù)量太大B、要排序的數(shù)據(jù)中有多個相同值C、要排序的數(shù)據(jù)已基本有序D、要排序的數(shù)據(jù)個數(shù)為奇數(shù)4.樹的定義具有遞歸性。5.數(shù)據(jù)結(jié)構(gòu)里，關(guān)于傳遞描述正確的是（）。A、值傳遞傳遞的是變量的值B、地址傳遞傳遞的是一個地址C、值傳遞時，實參不會隨著形參的變化而變化D、地址傳遞時，實參會隨著形參的變化而變化6.一個圖的廣度優(yōu)先搜索樹是惟一的7.具有n個頂點的有向無環(huán)圖最多有多少條邊？8.棧和隊列的共同點是（）。A、都是樹形結(jié)構(gòu)B、都是限制存取點的線性結(jié)構(gòu)C、都是線性結(jié)構(gòu)D、都不對9.序列12，10，13，11，16，14，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是（）10.n個結(jié)點無向完全圖的的邊數(shù)為（），n個結(jié)點的生成樹的邊數(shù)為（）。11.假定一組記錄為(46,79,56,64,38,40,84,43)，在冒泡排序的過程中進行第一趟排序時，元素79將最終下沉到其后第（）個元素的位置。12.序列14，12，15，13，18，16，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是（）13.二叉樹中每個結(jié)點的兩棵子樹是有序的。14.所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。15.下列選項中是C語言中的計算字符串長度的是（）。A、strcpyB、strcatC、strcmpD、strlen16.具有3個結(jié)點的二叉樹的有（）種不同形態(tài)。A、6B、5C、3D、417.根據(jù)數(shù)據(jù)結(jié)構(gòu)的類型的定義分析算法： if語句中的條件應(yīng)為什么？18.棧與隊列都是操作受限的線性表。19.設(shè)n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（）。A、?n在m右方B、?n在m左方C、?n是m的祖先D、?n是m的子孫20.假定一棵二叉樹的結(jié)點數(shù)為18個，則它的最小高度（）A、4B、5C、6D、1821.簡述ISAM文件的組織方法。22.數(shù)組a經(jīng)初始化char?a[]=“English”；a[7]中存放的是（）。23.設(shè)一個帶頭結(jié)點的單向鏈表的頭指針為head，設(shè)計算法，將鏈表的記錄，按照data域的值遞增排序。24.四種排序（）的空間復(fù)雜度最大。A、快速排序B、冒泡排序C、希爾排序D、堆25.對于長度為20的順序表，若采用二分查找法，則查找第八個元素的查找長度（）A、2B、3C、4D、526.給定排序碼的序列{39、33、13、15、58、41、27、46、23}。請回答：采用希爾（Shell）排序（步長分別為5，3，1），寫出各趟排序結(jié)果。27.下列選項中是用來定義結(jié)構(gòu)體的關(guān)鍵字是（）。A、structB、functionC、staticD、stack28.在m階B-樹中每個結(jié)點上至少有個關(guān)鍵字，最多有m個關(guān)鍵字。29.索引順序文件既能進行（）存取，又能進行（）存取，因而是最常用的文件組織方法之一，通常用（）結(jié)構(gòu)來組織索引。30.圖G的生成樹是該圖的一個極小連通子圖31.對一個有向圖進行拓撲排序，一定可以將圖的所有頂點按其關(guān)鍵碼大小排列到一個拓撲有序的序列中。32.非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（）。33.設(shè)一棵二叉樹結(jié)點的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結(jié)點是（）。34.具有10個葉子結(jié)點的二叉樹中有（）個度為2的結(jié)點。A、8B、9C、10D、1135.棧的操作，入棧又叫壓棧，一般用（）代替。A、pushB、popC、outD、in36.對稀疏矩陣進行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A共有38個零元素，其相應(yīng)的三元組表共有（）個元素。37.數(shù)據(jù)結(jié)構(gòu)里，下面關(guān)于串的的敘述中，哪一個是不正確的？（）A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運算D、串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?8.有窮性是算法的特性。39.散列表的查找效率取決于散列表造表時選取的散列函數(shù)和處理沖突的方法。40.簡述常用的四種哈希函數(shù)及其計算規(guī)則。41.已知一組記錄為（46，74，53，14，26，38，86，65，27，34），給出采用堆排序法進行排序時每一趟的排序結(jié)果。42.算法的效率用時間復(fù)雜度來衡量。43.以單鏈表為存儲結(jié)構(gòu)，寫一個直接選擇排序算法。44.在一個單向鏈表中，在p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行s->next=p->next；和（）A、p=sB、p->next=s->nextC、p=s->nextD、p->next=s45.試編寫算法實現(xiàn)鏈表的就地逆置（不增加存儲空間），即把鏈表A中的數(shù)據(jù)元素（a1，a2，…，an）逆置為（an，an-1，…，a1）。46.二叉排序樹刪除一個結(jié)點后，仍是二叉排序樹。47.二叉樹必須有左子樹和右子樹，不能只有右子樹。48.已知指針p指向單鏈表中某個結(jié)點，則語句p->next=p->next->next的作用（）。49.下面（）可以判斷出一個有向圖中是否有環(huán)（回路）。A、廣度優(yōu)先遍歷B、拓撲排序C、求最短路徑D、求關(guān)鍵路徑50.簡述順序表和鏈表存儲方式的特點。51.雖然關(guān)鍵字序列的順序不一樣，但依次生成的二叉排序樹是一樣的。52.對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數(shù)為（）。A、?3B、?4C、?5D、?653.具有n個結(jié)點的完全二叉樹若按層次從上到下，從左到右對其編號（根結(jié)點為1），則編號最大的分支結(jié)點序號是（），編號最小的分支結(jié)點序號是（），編號最大的葉子結(jié)點序號是（），編號最小的葉子結(jié)點序號是（）54.在一個堆的順序存儲中，若一個元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為（），右孩子元素的下標(biāo)為（）。55.若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A、快速排序B、堆排序C、歸并排序D、直接插入排序56.在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的（）、（）和（）三項。57.若二叉排序樹中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點。58.下列排序算法中，（）不能保證每趟排序至少能將一個元素放到其最終的位置上。A、希爾排序B、快速排序C、冒泡排序D、堆排序59.假定一個待哈希存儲的線性表為（32，75，29，63，48，94，25，36，18，70，49，80），哈希地址空間為HT[12]，若采用除留余數(shù)法構(gòu)造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長度。60.數(shù)據(jù)結(jié)構(gòu)里，函數(shù)調(diào)用是，形參傳給實參，是單向傳遞的。61.下列選項中是結(jié)構(gòu)體普通變量或指針變量引用其成員時使用時的符號的是（）。A、->符號B、.符號C、->>符號D、#符號62.數(shù)據(jù)結(jié)構(gòu)里，二叉樹不可以是空二叉樹。63.數(shù)據(jù)結(jié)構(gòu)涉及哪幾個方面？64.設(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ù)？65.拓撲排序是指結(jié)點的值是有序排序的。66.若一組記錄的排序碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7967.在對n個元素進行冒泡排序的過程中，至少需要（）趟完成。A、1B、nC、n-1D、n/268.設(shè)在鏈?zhǔn)酱鎯Φ木€性表中，設(shè)結(jié)點結(jié)構(gòu)為datalink，欲在p結(jié)點后插入一個結(jié)點q的關(guān)鍵步驟為（）。A、q->link=p->link；p->link=q；B、p->link=q->link；p->link=q；C、q->link=p->link；q->link=p；D、p->link=q->link；q->link=p；69.設(shè)有一順序棧，元素1，2，3，4，5依次進棧，如果出棧順序是2，4，3，5，1則棧的容量至少是：（）A、1B、2C、3D、470.在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的地址即可；因此，單鏈表是一種隨機存取結(jié)構(gòu)。71.拉鏈法（鏈地址法）72.當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為（）。A、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D、數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同73.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a85的地址為（）74.數(shù)據(jù)結(jié)構(gòu)里，函數(shù)參數(shù)為哪項時，參數(shù)傳遞屬于地址傳遞。（）A、數(shù)組B、float型C、char型D、int型75.設(shè)有一個已按各元素值排好序的線性表，長度為125，用折半查找與給定值相等的元素，若查找成功，則至少需要比較（）次，至多需比較（）次。76.權(quán)值為{1，2，6，8}的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。A、18B、28C、19D、2977.抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)78.已知如下所示長度為12的表：（Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。79.假定一個順序循環(huán)隊列存儲于數(shù)組a[n]中，其隊首和隊尾指針分別用front和rear表示，則判斷隊滿的條件為（）A、（rear?-?1）％?n?==?frontB、（rear?+?1）％?n?==?frontC、（front?-?1）％?n?==?rearD、（front?+?1）％?n?==?rear80.對于一個圖G，若邊集合E（G）為無向邊的集合，則稱該圖為（）。81.數(shù)據(jù)結(jié)構(gòu)里，二叉樹中的結(jié)點都是度為2的結(jié)點。82.簡述堆的定義和堆的構(gòu)建過程。83.若一棵滿二叉樹含有121個結(jié)點，則該樹的深度為（）。84.在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒有（）。A、左孩子結(jié)點B、右孩子結(jié)點C、左孩子和右孩子結(jié)點D、左孩子結(jié)點，右孩子結(jié)點和兄弟結(jié)點85.如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（）。A、完全圖B、連通圖C、有回路D、一棵樹86.圖的廣度優(yōu)先搜索類似于樹的（）次序遍歷。A、先根B、中根C、后根D、層次87.對于雙目操作符，其重載函數(shù)帶有（）個參數(shù)，其中至少有一個為（）的類型。88.設(shè)G1=（V1，E1）和G2=（V2，E2）為兩個圖，如果V1V2，E1E2則稱（）。A、G1是G2的子圖B、G2是G1的子圖C、G1是G2的連通分量D、G2是G1的連通分量89.在下面冒泡排序算法中填入適當(dāng)內(nèi)容，以使該算法在發(fā)現(xiàn)有序時能及時停止。 bubble（R） RectypeR[n]； {inti，j，exchang； Rectypetemp； i=1； do {exchang=False； for（j=n；j>=??i+1；j--） if（R[j]<r[j-1]{temp=R[j-1]； R[j-1]=R[j]； R[j]=temp； exchang=True； } （）； }while（exchang=False）； }</r[j-1]90.假設(shè)表達式有單字母變量和雙目四則運算符構(gòu)成。試寫一個算法，將一個通常書寫形式且書寫正確的表達式轉(zhuǎn)換為逆波蘭表達式。91.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（） A、AB、BC、CD、D92.散列表中解決沖突的兩種方法是（）和（）93.對給定的序號j（1＜j＜n），要求在無序記錄A[1]~A[n]中找到按關(guān)鍵碼從小到大排在第j位上的記錄，試?yán)每焖倥判虻膭澐炙枷朐O(shè)計算法實現(xiàn)上述查找。94.在一非空二叉樹的中，根結(jié)點的右邊只有（）上的所有結(jié)點。95.設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。96.在線性表的單鏈表存儲中，若一個元素所在結(jié)點地址為p，則其后繼結(jié)點的地址為（）97.下列四個序列中，（）是堆。A、75，65，30，15，25，45，20，10B、75，65，45，10，30，25，20，15C、75，45，65，30，15，25，20，10D、75，45，65，10，25，30，20，1598.編寫循環(huán)隊列入隊和出隊的算法。99.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要（）條邊。100.簡述森林轉(zhuǎn)換為二叉樹的具體步驟。第I卷參考答案一.參考題庫1.參考答案：Lelem[i-1]2.參考答案：3.參考答案：C4.參考答案：正確5.參考答案：A,B,C,D6.參考答案：錯誤7.參考答案：具有n個頂點的有向無環(huán)圖最多有n×（n—1）/2條邊。 這是一個拓撲排序相關(guān)的問題。—個有向無環(huán)圖至少可以排出一個拓撲序列，不妨設(shè)這n個頂點排成的拓撲序列為v1，v2，v3，?，vn，那么在這個序列中，每個頂點vi只可能與排在它后面的頂點之間存在著以vi為弧尾的弧，最多有n-i條，因此在整個圖中最多有（n-1）+（n-2）+?+2+1=n×（n-1）/2條邊。8.參考答案：B,C9.參考答案：10，12，11，13，14，1610.參考答案：n(n-1)/2；n-111.參考答案：412.參考答案：12，14，13，15，16，1813.參考答案：正確14.參考答案：錯誤15.參考答案：D16.參考答案：B17.參考答案：S.top=?=S.MaxSize-1118.參考答案：正確19.參考答案：B20.參考答案：B21.參考答案：在ISAM文件中，每個柱面的磁道被分為3個部分： A.一部分磁道作為記錄存儲的基本的區(qū)，其中每一磁道將記錄按主關(guān)鍵字大小進行有序順序存儲。 B.一部分磁道作為記錄存儲的溢出區(qū)，在一個已滿磁道中插入新記錄時，就會產(chǎn)生溢出的記錄（即該磁道容納不下的記錄），這些溢出記錄以鏈表形式存儲在溢出區(qū)中。 C.一部分磁道作為索引區(qū)，用于存儲磁道索引表。與基本的區(qū)和溢出區(qū)相對應(yīng)，表中的每一索引項又由基本索引項和溢出索引項組成?；舅饕椨脕泶娣呕镜膮^(qū)一個磁道中記錄的最大關(guān)鍵字值和第一個記錄的位置；溢出索引項用來存放從該磁道溢出記錄的最大關(guān)鍵字值和該磁道在溢出區(qū)中的第一個溢出記錄的位置。22.參考答案：字符串的結(jié)束符23.參考答案：voidassending（Lnode*heaD. {Lnode*p，*q，*r，*s； p=head->next；q=p->next；p->next=NULL； while（q） {r=q；q=q->next； if（r->datadatA. {r->next=p；head->next=r；p=r；} else {while（!p&&r->data>p->datA. {s=p；p=p->next；} r->next=p；s->next=r；} p=head->next；} }24.參考答案：A25.參考答案：C26.參考答案：27.參考答案：A28.參考答案：錯誤29.參考答案：順序；二分；樹30.參考答案：錯誤31.參考答案：錯誤32.參考答案：p->next=head33.參考答案：E、F、H34.參考答案：B35.參考答案：A36.參考答案：437.參考答案：B38.參考答案：錯誤39.參考答案：正確40.參考答案：除余法：選取一個適當(dāng)?shù)恼麛?shù)p（通常p為不大于哈希表存儲空間尺寸的最大素數(shù)），以元素的關(guān)鍵字值k除以p，得到的余數(shù)作為元素的存儲地址，即h（k）=k%p。 數(shù)字分析法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲空間地址碼位數(shù)多、每一位的取值范圍及關(guān)鍵字的取值分布情況預(yù)先知道，則可以對元素關(guān)鍵字的各位進行分析，去掉分布較集中的位、保留分布較均勻的位。 折疊法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲空間地址碼位數(shù)多，但關(guān)鍵字的取值分布情況未知，則可以用折疊法將關(guān)鍵字分為幾段（除了最后一段位數(shù)可以少一些，其他各段的位數(shù)均等于存儲空間地址碼位數(shù)），并將所有段的值做疊加求和運算，將疊加和的最高位進位舍去后取剩余部分作為元素的存儲地址。 平方取中法：對元素的關(guān)鍵字值求平方，并取中間幾位作為元素的存儲地址。41.參考答案：42.參考答案