2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試參考題庫含答案

“人人文庫”水印下載源文件后可一鍵去除，請(qǐng)放心下載！（圖片大小可任意調(diào)節(jié)）2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試參考題庫含答案“人人文庫”水印下載源文件后可一鍵去除，請(qǐng)放心下載！第1卷一.參考題庫(共75題)1.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是（）。A、插入、刪除操作更簡(jiǎn)單B、可以進(jìn)行隨機(jī)訪問C、可以省略表頭指針或表尾指針D、順序訪問相鄰結(jié)點(diǎn)更靈活2.已知關(guān)鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后得到的小根堆是（）A、3，5，12，8，28，20，15，22，19B、3，5，12，19，20，15，22，8，28C、3，8，12，5，20，15，22，28，19D、3，12，5，8，28，20，15，22，193.什么叫二維數(shù)組的行序優(yōu)先存儲(chǔ)？什么叫二維數(shù)組的列序優(yōu)先存儲(chǔ)？4.有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的（）。5.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D，R），其中D是（）的有限集合，R是D上的（）有限集合。6.已知一個(gè)有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)折半查找值為90的元素時(shí)，經(jīng)過（）次比較后查找成功。A、2B、3C、4D、57.一個(gè)雙向棧S是在同一向量空間內(nèi)實(shí)現(xiàn)的兩個(gè)棧，它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計(jì)初始化InitStack（S）、入棧Push（S，i，x）和出棧Pop（S，i）等算法，其中i為0或1，用以表示棧號(hào)。8.下列排序算法中，（）算法可能會(huì)出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序9.鏈棧與順序棧相比有一個(gè)明顯的優(yōu)點(diǎn)，即（）A、插入操作更加方便B、通常不會(huì)出現(xiàn)棧滿的情況C、不會(huì)出現(xiàn)棧空的情況D、刪除操作更加方便10.一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。11.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（）個(gè)結(jié)點(diǎn)。A、2nB、n+lC、2n-1D、2n+l12.設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A[9][3][5][8]時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占4個(gè)字節(jié)，a[3][1][2][5]的存儲(chǔ)地址是（）。13.定義字符數(shù)組正確的是（）。A、chars[]="Student"；B、chars[7]="Student"；C、chars[7]={’S’，’t’，’u’，’d’，’e’，’n’，’t’}；D、chars[]={"Student"}；14.向一個(gè)棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行（）和（）操作。15.如果只想得到一個(gè)序列中第k個(gè)最小元素之前的部分排序序列，最好采用什么排序方法？為什么？對(duì)于序列{57，40，38，11，13，34，48，75，25，6，19，9，7}，得到其第4個(gè)最小元素之前的部分序列{6，7，9，11}，使用所選擇的排序算法時(shí)，要執(zhí)行多少次比較？16.設(shè)棧的輸入序列是（1、2、3、4），則（）不可能是其出棧序列。A、1243B、2134C、1432D、4312E、321417.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）A、2hB、2h-1C、2h+1D、h+118.在所有結(jié)點(diǎn)的權(quán)都相等的情況下，只有最下面兩層結(jié)點(diǎn)的度數(shù)可以小于2，其他結(jié)點(diǎn)的度數(shù)必須等于2的二叉排序樹才是最佳二叉樹。19.當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。20.單鏈表中刪除p指針指向結(jié)點(diǎn)的后繼（假設(shè)存在）的時(shí)間復(fù)雜度是（）。A、O（1）B、O（n）C、O（nn）D、以上都不對(duì)21.什么是算法的漸近時(shí)間復(fù)雜度？如何分析一個(gè)算法的漸近時(shí)間復(fù)雜度？22.設(shè)無向圖G（如圖所示），給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。 23.設(shè)有串S1=’Ianastudent’,S2=’st’,其index(S1,S2)=（）24.假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)的概率為5％、25％、4％、7％、9％、12％、30％、8％，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。25.數(shù)據(jù)的（）包括查找、插入、刪除、更新、排序等操作類型。A、邏輯結(jié)構(gòu)B、存儲(chǔ)結(jié)構(gòu)C、算法描述D、基本運(yùn)算26.（）結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。27.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須（）。A、以順序方式存儲(chǔ)B、以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C、以鏈?zhǔn)椒绞酱鎯?chǔ)D、以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列28.對(duì)比順序表與單鏈表，說明順序表與單鏈表的主要優(yōu)點(diǎn)和主要缺點(diǎn)。29.既希望查找速度快又便于線性表動(dòng)態(tài)變化的查找方法有（）A、順序查找B、折半查找C、索引順序查找D、哈希法查找30.指出下述程序段的功能是什么？ 31.簡(jiǎn)述在順序棧的棧頂插入一個(gè)元素的操作過程。32.二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。A、C、=D、!=33.棧的使用非常廣泛，在進(jìn)制轉(zhuǎn)換、括號(hào)匹配、表達(dá)式求值等算法都能用到。34.在無向圖中定義頂點(diǎn)vi與vj之間的路徑為從vi到vj的一個(gè)（）。A、頂點(diǎn)序列B、邊序列C、權(quán)值總和D、邊的條數(shù)35.設(shè)一哈希表表長(zhǎng)M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=KMODP（P<=M），為使函數(shù)具有較好性能，P應(yīng)選（）36.帶頭結(jié)點(diǎn)head的雙循環(huán)鏈表為空表的條件是（）或（）37.在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改指針的操作是（）。A、p->next=q；q->prior=p；p->next->prior=q；q->next=q；B、p->next=q；p->next->prior=q；q->prior=p；q->next=p->next；C、q->prior=p；q->next=p->next；p->next->prior=q；p->next=q；D、q->next=p->next；q->prior=p；p->next=q；p->next=q；38.冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)39.線索二叉鏈表是利用（）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。A、lchildB、dataC、rchildD、root40.已知如圖所示的無向網(wǎng)，請(qǐng)給出： ①鄰接矩陣； ②鄰接表；? ③最小生成樹。 41.凡能被計(jì)算機(jī)存儲(chǔ)、加工的對(duì)象通稱為（）42.設(shè)head為單循環(huán)鏈表L的頭結(jié)點(diǎn)，則L為空表的條件是（）43.順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（）。44.設(shè)計(jì)算法判定一棵二叉樹是否為二叉排序樹。45.數(shù)據(jù)結(jié)構(gòu)里，算法的特性包含輸入、輸出、有窮性、（）和可行性。A、確定性B、二義性C、多變性D、模糊性46.對(duì)具有n個(gè)元素的有序表采用二分查找法，則算法的時(shí)間復(fù)雜性為（）A、O（n）B、O（n2）C、O（1）D、O（log2n）47.執(zhí)行下面程序段時(shí)，執(zhí)行S語句的次數(shù)為（） A、n2B、n2/2C、n（n+1）D、n（n+1）/248.關(guān)于字符串描述正確的是（）。A、字符串可以為空串B、字符串的長(zhǎng)度計(jì)算’/0’在內(nèi)C、字符串比較函數(shù)strcmp返回值類型是charD、字符串求長(zhǎng)度使用strcat49.散列技術(shù)的查找效率主要取決于散列函數(shù)和處理沖突的方法。50.在一棵樹中，（）結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)（），可以有任意多個(gè)（）結(jié)點(diǎn)。51.非空左斜樹的先序遍歷序列和后序遍歷序列正好相反。52.在一個(gè)表頭指針為ph的單鏈表中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則應(yīng)執(zhí)行（）操作。A、ph=p；p-＞next=phB、p-＞next=Ph；p=phC、p-＞next=ph-＞next；ph=pD、p-＞next=ph-＞next；ph-＞next=p53.下列選項(xiàng)中關(guān)于棧的刪除操作描述正確的是（）。A、棧的刪除操作叫做出棧B、棧的刪除操作叫做彈棧C、棧的刪除操作叫做壓棧D、棧的刪除操作叫做進(jìn)棧54.鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取55.已知一組待排序的記錄關(guān)鍵字初始排列如下：45，34，87，25，67，43，11，66，27，78?。（）是初始堆（大堆頂）。A、27，34，11，25，45，43，87，66，67，78B、87，78，45，66，67，43，11，25，27，34C、11，43，34，25，45，66，27，67，87，78D、11，43，34，45，25，66，87，67，27，78E、34，45，25，67，43，11，66，27，78，87F、87，45，11，25，34，78，27，66，67，43G、27，34，11，25，43，45，67，66，87，78H、34，11，27，25，43，78，45，67，66，8756.在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮模ǎ┻M(jìn)行查找任何一個(gè)元素。57.如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè)，采用（）方法最好。A、起泡排序B、堆排序C、錦標(biāo)賽排序D、快速排序58.計(jì)算機(jī)算法指的是（）A、計(jì)算方法B、調(diào)度方法C、排序方法D、解決某一問題的有限運(yùn)算序列59.排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個(gè)記錄交換的排序方法，稱為（）。A、希爾排序B、歸并排序C、插入排序D、選擇排序60.線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。61.廣義表運(yùn)算式HEAD（TAIL（（a，b，c），（x，y，z）））的結(jié)果是：（）。62.當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素。63.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）。64.假定一個(gè)待散列存儲(chǔ)的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長(zhǎng)度。65.在等概率情況下，一棵平衡樹的ASL為（）A、O（1）B、O（log2n?）C、O（（log2n）2）D、O（nlog2n）66.設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。A、快速排序B、堆排序C、歸并排序D、插入排序67.當(dāng)一個(gè)線性表經(jīng)常進(jìn)行存取操作而很少進(jìn)行插入和刪除操作時(shí)，則采用（）存儲(chǔ)結(jié)構(gòu)為宜，相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用（）存儲(chǔ)結(jié)構(gòu)為宜。68.的深度是（）69.對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）A、表達(dá)變得簡(jiǎn)單B、對(duì)矩陣元素的存取變得簡(jiǎn)單C、去掉矩陣中的多余元素D、減少不必要的存儲(chǔ)空間70.設(shè)高度為h的二叉數(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）A、2hB、2h-1C、2h+1D、h+171.假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。72.對(duì)于兩棵具有相同記錄集合而具有不同形態(tài)的二叉搜索樹，按中序遍歷得到的結(jié)點(diǎn)序列是相同的。73.數(shù)據(jù)結(jié)構(gòu)里，實(shí)參和形參的關(guān)系（）。A、實(shí)參傳給形參B、實(shí)參的類型要與形參一致C、實(shí)參的個(gè)數(shù)要與實(shí)參一致D、實(shí)參的名稱要與形參的一致74.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（）A、n，eB、e，nC、2n，eD、n，2e75.表達(dá)式求值是（）應(yīng)用的一個(gè)典型例子。第2卷一.參考題庫(共75題)1.設(shè)哈希（散列）表表長(zhǎng)為15（哈希地址為0~14），哈希函數(shù)為H（key）=key%11，沖突處理采用線性探測(cè)Hi=（H（key）+1）%11，則將一列數(shù)15，20，26，30，35，40存儲(chǔ)該哈希表，元素40的哈希地址為（）2.可由一個(gè)尾指針唯一確定的鏈表有（）、（）、（）。3.下列排序算法中（）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A、快速排序B、shell排序C、堆排序D、冒泡排序4.數(shù)據(jù)結(jié)構(gòu)里，以下是算法的特性是（）。A、有窮性B、數(shù)據(jù)C、其它D、以上都不對(duì)5.中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。6.某二叉樹的中序遍歷序列為：DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為（）。7.設(shè)哈希函數(shù)H（K）=3?K?mod?11，哈希地址空間為0～10，對(duì)關(guān)鍵字序列（32，13，49，24，38，21，4，12），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時(shí)和查找失敗時(shí)的平均查找長(zhǎng)度ASLsucc和ASLunsucc。? ①?線性探測(cè)法；? ②?鏈地址法。8.字符串“abcd321ABCD”的子串是（）。A、“21ABC”B、“abcABCD”C、abcDD、“321a”9.假定利用數(shù)組a[m]順序存儲(chǔ)一個(gè)棧，用top表示棧頂指針，用top==0表示棧滿，該數(shù)組所能存儲(chǔ)的棧的最大長(zhǎng)度為m，當(dāng)（）時(shí)，再做退棧運(yùn)算會(huì)發(fā)生“下溢”。A、top?==?m-1B、top?==?0C、top?==?mD、top?==?110.在對(duì)n個(gè)元素進(jìn)行起泡排序的過程中，最好情況下的時(shí)間復(fù)雜度為：（）A、.O（n3）B、O（n2）C、O（n）D、O（1）11.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)入隊(duì)一個(gè)元素，再出隊(duì)兩個(gè)元素后，rear和front的值分別為：（）A、?1和5B、?2和4C、?4和2D、?5和112.圖的（）優(yōu)先搜索遍歷算法是一種遞歸算法，圖的（）優(yōu)先搜索遍歷算法需要使用隊(duì)列。13.數(shù)據(jù)結(jié)構(gòu)里，算法的輸出可以是1到N個(gè)，意味著算法必須有輸出。14.一個(gè)子串在包含它的主串中的位置是指（）。A、子串的最后那個(gè)字符在主串中的位置B、子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置C、子串的第一個(gè)字符在主串中的位置D、子串的第一個(gè)字符在主串中首次出現(xiàn)的位置15.設(shè)有一個(gè)長(zhǎng)度為35的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素作為新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（）A、30B、31C、5D、616.設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。17.數(shù)據(jù)結(jié)構(gòu)里，下面關(guān)于字符數(shù)組描述正確的是（）A、gets（）讀取的字符串，其長(zhǎng)度沒有限制，以敲回車鍵結(jié)束。B、puts（）函數(shù)，該函數(shù)一次只能輸出一個(gè)字符串C、strcmp（）函數(shù)，字符串1小于字符串2，函數(shù)返回值整數(shù)-1D、strcpy（）函數(shù)功能是進(jìn)行字符串連接.18.不是數(shù)據(jù)的邏輯結(jié)構(gòu)是（）A、散列結(jié)構(gòu)B、線性結(jié)構(gòu)C、樹結(jié)構(gòu)D、圖結(jié)構(gòu)19.在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。A、31B、32C、33D、1620.順序查找時(shí)間為O（n），二分查找時(shí)間為O（log2n），散列查找時(shí)間為O（1），為什么有高效率的查找方法而不放棄低效率的方法？21.將二叉排序樹T按前序遍歷序列依次插入初始為空的二叉排序樹T’中，則T與T’是相同的，這種說法是否正確？22.關(guān)鍵字序列為（47，7，29，11，16，92，22，8，3，50，37，89，94，21），哈希函數(shù)為：Hash(key)=keymod11，用拉鏈表處理沖突。23.設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19；②front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？24.數(shù)據(jù)結(jié)構(gòu)中，度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：（）。A、事后統(tǒng)計(jì)方法B、事前分析估算的方法C、空間復(fù)雜度分析法D、漸近式分析方法25.二維數(shù)組A的元素都是6個(gè)字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圈從1到10。從供選擇的答案中選出正確答案。若A按行存放，元素A[8，5]的起始地址與A按列存放時(shí)的元素（）的起始地址一致。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]26.字符串的長(zhǎng)度是指（）A、串中不同字符的個(gè)數(shù)B、串中不同字母的個(gè)數(shù)C、串中所含字符的個(gè)數(shù)D、串中不同數(shù)字的個(gè)數(shù)27.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（）。A、希爾排序B、冒泡排序C、插入排序D、選擇排序28.簡(jiǎn)述二叉樹的常用操作及各操作的含義。29.設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（）A、r-fB、r-f+lC、（r-f）?mod?（n+1）D、（r-f+n）?mod?n30.為了方便地對(duì)圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其中數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用（）。A、順序存儲(chǔ)B、鏈?zhǔn)酱鎯?chǔ)C、索引存儲(chǔ)D、散列存儲(chǔ)31.用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。32.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的（）結(jié)構(gòu)和（）結(jié)構(gòu)。33.數(shù)據(jù)結(jié)構(gòu)里，樹是一種特殊的一對(duì)多的邏輯結(jié)構(gòu)，當(dāng)一個(gè)結(jié)點(diǎn)也沒有時(shí)，它就稱為（）。A、滿樹B、空樹C、二叉樹D、多叉樹34.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是（）和（）35.在所有排序方法中，（）排序方法采用的是二分法的思想。36.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A、動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)37.完全二叉樹的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)。38.在動(dòng)態(tài)查找表中，（）既擁有類似折半查找的特性，又采用了鏈接存儲(chǔ)結(jié)構(gòu)。39.假定front和rear分別為一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針，則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為（）。40.已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。41.構(gòu)造哈希函數(shù)的方法有（）、（）、（）42.對(duì)圖所示的無向圖，依次輸入各邊：（v1，v2）、（v1，v4）、（v2，v3）、（v3，v4）、（v3，v5），請(qǐng)回答下列各問： 寫出該無向圖的二元組表示。43.在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為（）A、63B、64C、6D、744.一棵無向連通圖的生成樹是其極大的連通子圖45.單鏈表的查找很方便，直接可以獲得任何一個(gè)元素。46.數(shù)據(jù)的邏輯結(jié)構(gòu)可以形式的用一個(gè)二元組B=（K，R）來表示，其中K是（）R是*（）。47.已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，nk個(gè)度為k的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？48.假定一組記錄為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的過程中，含有兩個(gè)或兩個(gè)以上元素的排序區(qū)間的個(gè)數(shù)為（）個(gè)。49.n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣存儲(chǔ)，回答下列問題： ⑴圖中有多少條邊？ ⑵任意兩個(gè)頂點(diǎn)i和j是否有邊相連？ ⑶任意一個(gè)頂點(diǎn)的度是多少？50.在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，至少需要（）趟完成。A、1B、nC、n-1D、n/251.具有N（N-1）/2條邊的無向圖成為（）。52.含n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過（）。A、1B、n/2C、n-1D、n53.己知輸入序列為1234，則輸入受限僅由一端輸入但輸出不受限兩端均可輸出的雙端隊(duì)列不可以得到（）輸出序列。A、4231B、1324C、3214D、4213E、234154.設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（）A、5，3，4，6，1，2B、3，2，5，6，4，1C、3，1，2，5，4，6D、1，5，4，6，2，355.數(shù)據(jù)結(jié)構(gòu)里，順序存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的（）。A、邏輯結(jié)構(gòu)B、存儲(chǔ)結(jié)構(gòu)C、操作D、沒有關(guān)系56.（）可以看做是從具體問題抽象出來的數(shù)學(xué)模型。57.二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，所以二叉樹是一種特殊的樹。58.一個(gè)數(shù)組元素a[i]與（）的表示等價(jià)。A、*（a+i）B、a+iC、*a+iD、&a+i59.已知一個(gè)堆為（12，15，40，38，26，52，48，64），若需要從堆中依次刪除四個(gè)元素，請(qǐng)給出每刪除一個(gè)元素后堆的狀態(tài)。60.編寫算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法。61.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要（）條邊。62.循環(huán)鏈表的結(jié)點(diǎn)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是結(jié)點(diǎn)間的連接方式不同。63.樹的后根遍歷序列等同于與該樹對(duì)應(yīng)的二叉樹的哪種序列？（）A、?前序序列B、?中序序列C、?后序序列D、?層序序列64.哈夫曼樹是其樹的帶權(quán)路徑長(zhǎng)度（）的二叉樹。65.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)。66.數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容之間有什么聯(lián)系和區(qū)別？67.在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫（）域，另一個(gè)叫（）域。68.設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元存放一個(gè)字符）?，F(xiàn)要求從此串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，m＜s，t＜（s-m），并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計(jì)此刪除算法。69.列舉幾個(gè)字符串的其他操作。70.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H（k）=k%P，則P通常情況下最好選擇（）A、99B、97C、91D、9371.深度為90的滿二叉樹，第11層有（）個(gè)結(jié)點(diǎn)。72.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（）條邊。A、n（n-1）/2B、n（n-1）C、n（n+1）/2D、（n-1）/273.某無向圖的鄰接矩陣A=，可以看出，該圖共有（）個(gè)頂點(diǎn)。A、3B、6C、9D、以上答案均不正確74.滿二叉樹是（）。A、所有的分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。B、所有的分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在最后兩層上。C、所有的分支結(jié)點(diǎn)只存在左子樹，并且所有葉子都在最后兩層上。D、都不對(duì)75.直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（n）。第1卷參考答案一.參考題庫1.參考答案：D2.參考答案：A3.參考答案：所謂行序優(yōu)先存儲(chǔ)，其基本思想為：從第1行的元素開始按順序存儲(chǔ)，第1行元素存儲(chǔ)完成后，再按順序存儲(chǔ)第2行的元素，然后依次存儲(chǔ)第3行，……直到最后一行的所有元素存儲(chǔ)完畢為止。而列序優(yōu)先存儲(chǔ)即為：依次按順序存儲(chǔ)第1列，第2列，……直到最后一列的所有元素存儲(chǔ)完畢為止。4.參考答案：出度5.參考答案：數(shù)據(jù)元素關(guān)系6.參考答案：A7.參考答案：雙向棧其實(shí)和單向棧原理相同，只是在一個(gè)向量空間內(nèi)，好比是兩個(gè)頭對(duì)頭的棧放在一起，中間的空間可以充分利用。雙向棧的算法設(shè)計(jì)如下： //雙向棧的棧結(jié)構(gòu)類型與以前定義略有不同 8.參考答案：D9.參考答案：B10.參考答案：正確11.參考答案：C12.參考答案：178413.參考答案：A,B,C,D14.參考答案：P->link=top；top=p15.參考答案：采用堆排序最合適，依題意可知只需取得第k個(gè)最小元素之前的排序序列時(shí)，堆排序的時(shí)間復(fù)雜度Ο（n+klog2n），若k≤nlog2n，則得到的時(shí)間復(fù)雜性是Ο（n）。 對(duì)于上述序列得到其前4個(gè)最小元素，使用堆排序?qū)崿F(xiàn)時(shí)，執(zhí)行的比較次數(shù)如下：初始建堆：比較20次，得到6； 第一次調(diào)整：比較5次，得到7； 第二次調(diào)整：比較4次，得到9； 第三次調(diào)整：比較5次，得到11。16.參考答案：D17.參考答案：B18.參考答案：正確19.參考答案：正確20.參考答案：A21.參考答案：算法的漸近時(shí)間復(fù)雜度是對(duì)算法的時(shí)間效率的度量。也就是對(duì)一個(gè)算法執(zhí)行所需要的時(shí)間進(jìn)行分析。一個(gè)算法執(zhí)行所需要的具體時(shí)間與所使用的計(jì)算機(jī)系統(tǒng)的軟、硬件性能及問題的規(guī)模等因素有關(guān)。為了比較算法本身的時(shí)間性能，應(yīng)該采用能夠反映算法本身的時(shí)間性能的度量。實(shí)際上，通常算法運(yùn)行所需要的時(shí)間T是問題規(guī)模n的函數(shù)，可記為T（n）。所謂算法的漸近時(shí)間復(fù)雜度，是當(dāng)問題規(guī)模充分大時(shí)，算法運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)的度量。因?yàn)樵鲩L(zhǎng)率的上限對(duì)算法的比較更具意義，所以經(jīng)常分析的是算法運(yùn)行時(shí)間的增長(zhǎng)率的上限，這就是算法的時(shí)間復(fù)雜度的大O表示，也常簡(jiǎn)稱為算法的時(shí)間復(fù)雜度。 為了分析一個(gè)算法的時(shí)間復(fù)雜度，一般情況下需要考察算法中基本語句的執(zhí)行次數(shù)，找出其與問題規(guī)模n的函數(shù)關(guān)系f（n），從而得到算法的漸近時(shí)間復(fù)雜度。所謂基本語句是執(zhí)行次數(shù)與算法的執(zhí)行次數(shù)成正比的語句，它是算法中的關(guān)鍵操作。算法的基本語句大多包含在循環(huán)和遞歸結(jié)構(gòu)中，對(duì)于單循環(huán)結(jié)構(gòu)，循環(huán)體中的簡(jiǎn)單語句就是基本語句，其執(zhí)行次數(shù)的大O表示就是該算法段的漸近時(shí)間復(fù)雜度；對(duì)于并列的循環(huán)結(jié)構(gòu)，要先分析各個(gè)循環(huán)結(jié)構(gòu)的漸近時(shí)間復(fù)雜度，然后利用大O表示法的加法規(guī)則求出算法的時(shí)間復(fù)雜度；對(duì)于多層嵌套的循環(huán)結(jié)構(gòu)，最內(nèi)層循環(huán)中的簡(jiǎn)單語句就是算法的基本語句，要自外向內(nèi)逐層分析各層循環(huán)的漸近時(shí)間復(fù)雜度，再利用大O表示法的乘法規(guī)則來求出算法的漸近時(shí)間復(fù)雜度。對(duì)于遞歸結(jié)構(gòu)，則可以根據(jù)遞歸過程遞推出基本語句的執(zhí)行次數(shù)，進(jìn)而得到它的大O表示。總之，只要分析求出算法中關(guān)鍵操作的執(zhí)行次數(shù)與問題規(guī)模的函數(shù)關(guān)系，也就得到了該次數(shù)的大O表示，從而也就求出了算法的漸近時(shí)間復(fù)雜度。22.參考答案：23.參考答案：824.參考答案：25.參考答案：D26.參考答案：樹型27.參考答案：B28.參考答案：頭指針是鏈表的一個(gè)標(biāo)識(shí)，它用來指向帶頭結(jié)點(diǎn)的鏈表中的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)是在鏈表的第一個(gè)數(shù)據(jù)元素之前附加的一個(gè)結(jié)點(diǎn)，它的作用是使對(duì)第一個(gè)結(jié)點(diǎn)的操作和其它結(jié)點(diǎn)一致，表空與非空時(shí)處理一致，不需要特殊處理，簡(jiǎn)化了操作。29.參考答案：D30.參考答案：程序段的功能是利用tmp棧將一個(gè)非空棧S1的所有元素按原樣復(fù)制到一個(gè)棧S2當(dāng)中去。31.參考答案：在插入元素之前，首先要判斷棧是否為滿，如果棧滿，返回“沾滿無法插入”等錯(cuò)誤提示信息；否則讓top指針（指向當(dāng)前順序棧的棧頂）向后移動(dòng)一個(gè)元素空間（元素大?。?，將要插入的元素放入top指針指向的內(nèi)存單元中。32.參考答案：A33.參考答案：正確34.參考答案：A35.參考答案：9736.參考答案：head->next=haed->prior；head->next=head37.參考答案：C38.參考答案：錯(cuò)誤39.參考答案：C40.參考答案：41.參考答案：數(shù)據(jù)42.參考答案：head->next=head43.參考答案：用元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。44.參考答案：對(duì)二叉排序樹來講，其中序遍歷序列為一個(gè)遞增序列。因此，對(duì)給定二叉樹進(jìn)行中序遍歷，如果始終能夠保證前一個(gè)值比后一個(gè)值小，則說明該二叉樹是二叉排序樹。 具體算法如下： 45.參考答案：A46.參考答案：D47.參考答案：D48.參考答案：A49.參考答案：錯(cuò)誤50.參考答案：樹根；雙親（或前驅(qū)）；孩子（或后繼）51.參考答案：正確52.參考答案：D53.參考答案：A,B54.參考答案：錯(cuò)誤55.參考答案：B56.參考答案：頭結(jié)點(diǎn)57.參考答案：B58.參考答案：D59.參考答案：D60.參考答案：錯(cuò)誤61.參考答案：(x,y,z)62.參考答案：正確63.參考答案：使空表和非空表統(tǒng)一，算法處理一致64.參考答案：散列函數(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 65.參考答案：B66.參考答案：B67.參考答案：順序；鏈接68.參考答案：469.參考答案：D70.參考答案：B71.參考答案： 72.參考答案：正確73.參考答案：A,B,C74.參考答案：D75.參考答案：棧第2卷參考答案一.參考題庫1.參考答案：72.參考答案：循環(huán)鏈表；循環(huán)雙鏈表；雙鏈表3.參考答案：B4.參考答案：A5.參考答案：正確6.參考答案：DABEC7.參考答案：8.參考答案：A9.參考答案：C10.參考答案：C11.參考答案：A12.參考答案：深度；廣度13.參考答案：正確14.參考答案：D15.參考答案：B16.參考答案：其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。 17.參考答案：A,B,C18.參考答案：A19.參考答案：A20.參考答案：衡量算法的標(biāo)準(zhǔn)有很多，時(shí)間復(fù)雜度只是其中之一。盡管有些算法時(shí)間性能很好，但是其他方面可能就存在著不足。比如散列查找的時(shí)間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。 二分查找也是有代價(jià)的，因?yàn)槭孪缺仨殞?duì)整個(gè)查找區(qū)間進(jìn)行排序，而排序也是費(fèi)時(shí)的，所以常應(yīng)用于頻繁查找的場(chǎng)合。對(duì)于順序查找，盡管效率不高，但卻比較簡(jiǎn)單，常用于查找范圍較小或偶而進(jìn)行查找的情況。21.參考答案：正確22.參考答案：23.參考答案：用隊(duì)列長(zhǎng)度計(jì)算公式：（N＋r－F)%N ①L=（40＋19－11）%40=8②L=（40＋11－19）%40=3224.參考答案：A,B25.參考答案：B26.參考答案：C27.參考答案：C28.參考答案：創(chuàng)建一棵空二叉樹：創(chuàng)建一棵沒有任何結(jié)點(diǎn)的二叉樹。在順序表示中，根據(jù)樹的深度為結(jié)點(diǎn)分配內(nèi)存；在二叉鏈表表示中，將指向根結(jié)點(diǎn)的指針賦值為NULL。 刪除一棵二叉樹：將二叉樹各結(jié)點(diǎn)所占據(jù)的內(nèi)存釋放。 清空二叉樹：將二叉樹的所有結(jié)點(diǎn)刪除，使之成為一棵空二叉樹。 以指定元素值創(chuàng)建根結(jié)點(diǎn)：創(chuàng)建根結(jié)點(diǎn)，并以指定值作為根結(jié)點(diǎn)的元素值。 將一個(gè)結(jié)點(diǎn)作為指定結(jié)點(diǎn)的左