（圖片大小可任意調(diào)節(jié)）2023年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)考試歷年參考核心考點(diǎn)薈萃附答案第一卷一.參考題庫(共20題)1.已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。2.下列廣義表用圖來表示時(shí)，分支結(jié)點(diǎn)最多的是（）。A、L=（（x，（a，B）），（x，（a，B），y））B、A=（s，（a，B））C、B=（（x，（a，B），y））D、D=（（a，B），（c，（a，B），D）3.數(shù)據(jù)結(jié)構(gòu)里，數(shù)據(jù)的邏輯結(jié)構(gòu)有哪些（）。A、集合結(jié)構(gòu)B、線性結(jié)構(gòu)C、圖形結(jié)構(gòu)D、樹形結(jié)構(gòu)4.若一棵滿二叉樹含有121個(gè)結(jié)點(diǎn)，則該樹的深度為（）。5.簡(jiǎn)述二叉鏈表表示和三叉鏈表表示的二叉樹中結(jié)點(diǎn)的結(jié)構(gòu)。6.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。A、6B、7C、8D、97.下列關(guān)于串的敘述中，不正確的是（）。A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運(yùn)算D、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)8.一個(gè)棧的入棧序列是A、B、C、D、E，五個(gè)元素都入棧后，首次出棧的元素是（）。A、AB、EC、BD、D9.指出下述程序段的功能是什么？ 10.由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（）A、23B、37C、44D、4611.數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和（）兩種方法衡量其效率。12.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為（）個(gè)，其中（）個(gè)用于鏈接孩子結(jié)點(diǎn)，（）個(gè)空閑著。13.串的長(zhǎng)度是指（）。A、串中所含不同字母的個(gè)數(shù)B、串中所含字符的個(gè)數(shù)C、串中所含不同字符的個(gè)數(shù)D、串中所含非空格字符的個(gè)數(shù)14.廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。15.下列圖的深度優(yōu)先遍歷序列為（）。 A、ABCDEFGHB、ABDHECFGC、ABEDHCFGD、ABCFGEDH16.由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費(fèi)的時(shí)間多。17.設(shè)一組初始記錄關(guān)鍵字序列為（345，253，674，924，627），則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。A、3B、4C、5D、818.數(shù)據(jù)結(jié)構(gòu)里，棧和隊(duì)列都是（）。A、操作受限的線性結(jié)構(gòu)B、先進(jìn)先出的線性結(jié)構(gòu)C、后進(jìn)先出的線性結(jié)構(gòu)D、以上都不對(duì)19.已知廣義表L=（（x，y，z），a，（u，t，w）），從L表中取出的原子項(xiàng)ASCII碼最大的運(yùn)算是（）。A、head（tail（tail（L）））B、tail（head（head（tail（L））））C、head（tail（tail（head（L））））D、head（tail（tail（tail（L））））20.對(duì)具有n個(gè)元素的有序表采用二分查找法，則算法的時(shí)間復(fù)雜性為（）A、O（n）B、O（n2）C、O（1）D、O（log2n）第二卷一.參考題庫(共20題)1.假定利用數(shù)組a[N]順序存儲(chǔ)一個(gè)棧，用top表示棧頂元素的下標(biāo)位置，用top==-1表示?？眨胻op==N-1表示棧滿，則該數(shù)組所能存儲(chǔ)的棧的最大長(zhǎng)度為（）A、N?-?1B、NC、N+1D、N十22.試將折半查找的算法改寫成遞歸算法。3.中綴表達(dá)式3*（X+2）-5所對(duì)應(yīng)的后綴表達(dá)式為（）。4.每次從無序子表中取出一個(gè)元素，把它插入到有序子表中的適當(dāng)位置，此種排序方法叫做（）排序；每次從無序子表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做（）排序。5.下列對(duì)于線性鏈表的描述中正確的是（）。A、存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的B、存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的6.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、順序表7.快速排序法是一種穩(wěn)定性排序法。8.簡(jiǎn)述直接插入排序的具體步驟。9.算法的時(shí)間復(fù)雜性越好，可讀性就越差；反之，算法的可讀性越好，則時(shí)間復(fù)雜性就越差。10.數(shù)據(jù)結(jié)構(gòu)里，算法的空間復(fù)雜度是不能衡量算法存儲(chǔ)量的高低的。11.一個(gè)稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。12.在一棵二叉排序樹上按（）遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。13.若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用（）方法。A、直接插入排序B、歸并排序C、堆排序D、快速排序14.在等概率情況下，順序表的插入操作要移動(dòng)（）結(jié)點(diǎn)。A、全部B、一半C、三分之一D、四分之一15.簡(jiǎn)述磁盤的邏輯結(jié)構(gòu)。16.N個(gè)結(jié)點(diǎn)的m階B樹至少包含（）個(gè)關(guān)鍵字。A、（m-1）*nB、nC、（「m/2」-1）*（n-1）+1D、n*「m/2」-1）17.的深度是（）18.在最壞的情況下，查找成功時(shí)二叉排序樹的平均查找長(zhǎng)度（）A、小于順序表的平均查找長(zhǎng)度B、大于順序表的平均查找長(zhǎng)度C、與順序表的平均查找長(zhǎng)度相同D、無法與順序表的平均查找長(zhǎng)度比較19.寫出算法的功能。intfun（sqstring*s，sqstring*t，intstart）{inti=start-1，j=0；while（ilen&&jlen）if（s->data[i]==t->data[j]）{i++；j++；}else{i=i-j+1；j=0；}if（j>=t->len）returni-t->len+1；elsereturn-1；}20.已知某森林的二叉樹如下所示，試畫出它所表示的森林。 第三卷一.參考題庫(共20題)1.從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，最壞情況下的時(shí)間復(fù)雜性為（）。A、O（n）B、O（1）C、O（log2n）D、O（n2）2.元素11，13，15，17按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A、17，15，13，11B、11，13，15，17C、17，15，11，13D、13，11，17，153.一裸樹上的任何結(jié)點(diǎn)（不包括根本身）稱為根的（）。若B是A的子孫.則稱A是B的（）。4.什么是廣義表？廣義表與線性表的區(qū)別是什么？5.設(shè)二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（）。A、p+[i*n+j-1]*kB、p+[（i-1）*n+j-1]*kC、p+[（j-1）*n+i-1]*kD、p+[j*n+i-1]*k6.在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成下列程序填空。 7.子程序調(diào)用過程中，需要把運(yùn)行現(xiàn)場(chǎng)的數(shù)據(jù)保存到（）中，返回主調(diào)函數(shù)在從中間取出。A、棧B、圖C、二叉樹D、隊(duì)列8.把算法的工作量大小和實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少分別稱為算法的（）和（）A、可實(shí)現(xiàn)性B、時(shí)間復(fù)雜度C、困難度D、計(jì)算有效性E、可行性F、高效性G、空間復(fù)雜度9.二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，結(jié)構(gòu)定義如下，試設(shè)計(jì)一個(gè)遞歸算法計(jì)算一棵給定二叉樹的葉子結(jié)點(diǎn)數(shù)。 10.一個(gè)廣義表的深度等于（）嵌套的最大層數(shù)。11.設(shè)散列表的長(zhǎng)度為16，散列函數(shù)為H（k）=k%13，用線性探測(cè)法處理沖突，依次插入關(guān)鍵字：19，01，13，23，24，55，20，84，27，68，11，10，77。請(qǐng)回答：畫出散列表示意圖并給出查找每個(gè)關(guān)鍵字時(shí)需要比較的次數(shù)。12.某完全二叉樹共有200個(gè)結(jié)點(diǎn)，則該二叉樹中有（）個(gè)度為1的結(jié)點(diǎn)。13.從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱為（）排序法。14.外部排序15.堆中所有非終端結(jié)點(diǎn)的值均小于或等于（大于或等于）左右子樹的值。16.具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊。A、NB、n（n-1）C、n（n+1）D、n217.假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素，同時(shí)以rear和length分別只是循環(huán)隊(duì)列中的隊(duì)尾位置和隊(duì)列中的所含元素的個(gè)數(shù)，則該循環(huán)的隊(duì)列的對(duì)空條件為（）。18.無向圖G=（V，E），其中V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A、a，b，e，c，d，fB、a，c，f，e，b，dC、a，e，b，c，f，dD、a，e，d，f，c，b19.若對(duì)n個(gè)元素進(jìn)行直接插入排序，則進(jìn)行任一趟排序的過程中，為尋找插入位置而需要的時(shí)間復(fù)雜度為（）A、O（1）B、O（n）C、O（n2）D、O（log2n）20.對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點(diǎn)。第一卷參考答案一.參考題庫1.正確答案:二叉樹的構(gòu)造過程如圖5-12所示。 2.正確答案:A3.正確答案:A,B,C,D4.正確答案:75.正確答案:在二叉鏈表表示中，雙親結(jié)點(diǎn)有指向其孩子結(jié)點(diǎn)的指針，而孩子結(jié)點(diǎn)不包含指向其雙親結(jié)點(diǎn)的指針；在三叉鏈表表示中，雙親結(jié)點(diǎn)有指向其孩子結(jié)點(diǎn)的指針，而孩子結(jié)點(diǎn)也包含指向其雙親結(jié)點(diǎn)的指針。6.正確答案:B7.正確答案:B8.正確答案:B9.正確答案:程序段的功能是利用tmp棧將一個(gè)非空棧S1的所有元素按原樣復(fù)制到一個(gè)棧S2當(dāng)中去。10.正確答案:C11.正確答案:空間復(fù)雜度12.正確答案:2n；n-1；n+113.正確答案:B14.正確答案:錯(cuò)誤15.正確答案:B16.正確答案:錯(cuò)誤17.正確答案:A18.正確答案:A19.正確答案:C20.正確答案:D第二卷參考答案一.參考題庫1.正確答案:B2.正確答案:3.正確答案:3*2+*54.正確答案:插入；選擇5.正確答案:A6.正確答案:D7.正確答案:錯(cuò)誤8.正確答案:直接插入排序是一種簡(jiǎn)單排序算法，其具體步驟為： A.初始已排序區(qū)為空，將第一個(gè)待排序的元素插入到已排序區(qū)中。 B.將后繼每一個(gè)待排序的元素依次取出，并按照關(guān)鍵字大小將其插入到已排序區(qū)中的適當(dāng)位置，使該序列仍然有序。 C.重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。9.正確答案:錯(cuò)誤10.正確答案:錯(cuò)誤11.正確答案:錯(cuò)誤12.正確答案:中序13.正確答案:B14.正確答案:B15.正確答案:磁盤的結(jié)構(gòu)如下： A.一個(gè)磁盤包含若干個(gè)盤片，所有盤片組成了盤片組；每個(gè)盤片有上下兩面，稱為盤面；每個(gè)盤面上有很多同心圓形式的磁道，數(shù)據(jù)就存放在這些磁道上；每個(gè)磁道又可以劃分為若干段，稱為扇區(qū)，一個(gè)扇區(qū)就是一次讀寫的最小數(shù)據(jù)量。 B.每個(gè)盤面都配有一個(gè)讀寫磁頭，通過讀寫磁頭可以對(duì)磁道上的數(shù)據(jù)進(jìn)行讀寫操作；所有讀寫磁頭都安裝在動(dòng)臂上，通過動(dòng)臂可以將讀寫磁頭移動(dòng)到任一磁道上；所有盤面上具有相同半徑的磁道就構(gòu)成了圓柱面，一個(gè)磁盤上圓柱面的個(gè)數(shù)就是一個(gè)盤面上的磁道數(shù)，同一時(shí)刻所有讀寫磁頭都位于一個(gè)圓柱面上。 C.主軸帶動(dòng)所有盤面高速旋轉(zhuǎn)，使得讀寫磁頭可以訪問到一個(gè)磁道上的所有扇區(qū)。16.正確答案:C17.正確答案:418.正確答案:C19.正確答案:串的模式匹配算法20.正確答案:第三卷參考答案一.參考題庫1.正確答案:A2.正確答案:C3.正確答案:子孫；祖先4.正確答案:廣義表又稱列表，是由n（n≥0）個(gè)元素組成的有窮序列：GL=（e1，e2，……en），但與線性表不同