2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試歷年真題薈萃含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(kù)(共30題)1.設(shè)有一稀疏圖G，則G采用（）存儲(chǔ)比較節(jié)省空間。2.假定一個(gè)順序循環(huán)隊(duì)列存儲(chǔ)于數(shù)組A[n]中，其隊(duì)首和隊(duì)尾指針分別用front和rear表示，則判斷隊(duì)滿的條件是（）A、（rear-1）%n==frontB、（rear+1）%n==frontC、rear==（front-1）%nD、rear==（front+1）%n3.已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb4.快速排序法是一種穩(wěn)定性排序法。5.棧和隊(duì)列的特性是相同的，都是先進(jìn)先出。6.試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。7.設(shè)高度為h的二叉數(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）A、2hB、2h-1C、2h+1D、h+18.算法的時(shí)間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。9.簡(jiǎn)述基數(shù)排序的具體步驟。10.試推導(dǎo)含有12個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度，并畫出以棵這樣的樹。11.（）結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。12.數(shù)據(jù)結(jié)構(gòu)里，棧的使很廣泛，它可以再一端插入數(shù)據(jù)，再另一端刪除數(shù)據(jù)。13.設(shè)計(jì)在有序表A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。14.循環(huán)隊(duì)列15.樸素模式匹配算法，算法運(yùn)行時(shí)間為O（m*n）。16.一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有（）個(gè)結(jié)點(diǎn)17.若用數(shù)組S[0..n-1]作為兩個(gè)棧S1和S2的共同存儲(chǔ)結(jié)構(gòu)，對(duì)任何一個(gè)棧，只有當(dāng)S全滿時(shí)才不能作入棧操作。為這兩個(gè)棧分配空間的最佳方案是（）。A、S1的棧底位置為0，S2的棧底位置為n-1B、S1的棧底位置為0，S2的棧底位置為n/2-1C、S1的棧底位置為1，S2的棧底位置為nD、S1的棧底位置為1，S2的棧底位置為n/218.折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。19.對(duì)于順序表和單向鏈表，如何實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的操作？20.下列排序方法中（）方法是不穩(wěn)定的。A、冒泡排序B、基數(shù)排序法C、堆排序D、直接插入排序21.一個(gè)圖的（）表示法是惟一的。22.s1=“hello”，s2=“boy”，s1，s2連接后為（）23.（1）設(shè)有數(shù)據(jù)集合{50，39，17，83，111，14，65，13，91，102，49}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。 （2）一組記錄的關(guān)鍵字序列為（6，9，7，4，5，8），利用堆排序（堆頂元素是最小元素）的方法建立初始堆。（要求用完全二叉樹表示）24.隊(duì)列結(jié)構(gòu)不會(huì)出現(xiàn)溢出問題。25.如果從一無向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（）。26.數(shù)據(jù)結(jié)構(gòu)中順序存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的（）。A、邏輯結(jié)構(gòu)B、存儲(chǔ)結(jié)構(gòu)C、操作D、沒有關(guān)系27.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是（）。A、訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）B、在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C、刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D、將n個(gè)結(jié)點(diǎn)從小到大排序28.簡(jiǎn)單選擇排序算法的時(shí)間復(fù)雜度為O（N）。29.樹中某結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的（），子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的（），該結(jié)點(diǎn)稱為其子樹根結(jié)點(diǎn)的（）。30.在具有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，2n個(gè)孩子指針域中，只用到（）個(gè)域。A、nB、n-1C、n+1D、2n第1卷參考答案一.參考題庫(kù)1.參考答案:鄰接表2.參考答案:B3.參考答案:D4.參考答案:錯(cuò)誤5.參考答案:錯(cuò)誤6.參考答案:7.參考答案:B8.參考答案:錯(cuò)誤9.參考答案:10.參考答案:令Fk表示含有最少結(jié)點(diǎn)的深度為k的平衡二叉樹的結(jié)點(diǎn)樹目，則： F.1=1，F(xiàn)2=2，…，F(xiàn)n=Fn-2+Fn-1+1。含有12個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度為5，例如： 11.參考答案:樹型12.參考答案:錯(cuò)誤13.參考答案:14.參考答案:在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，把存儲(chǔ)空間的首尾邏輯上相連，構(gòu)成一個(gè)環(huán)，使得存儲(chǔ)空間上只要有空余的地址，就可以繼續(xù)進(jìn)行入隊(duì)列操作，極大利用了物理空間。用頭部和尾部?jī)蓚€(gè)指示器表示隊(duì)列頭和隊(duì)列尾，插入在尾部進(jìn)行，刪除在頭部進(jìn)行。15.參考答案:正確16.參考答案:2n－117.參考答案:A18.參考答案:錯(cuò)誤19.參考答案:20.參考答案:C21.參考答案:鄰接矩陣22.參考答案:helloboy23.參考答案:24.參考答案:錯(cuò)誤25.參考答案:連通26.參考答案:B27.參考答案:A28.參考答案:錯(cuò)誤29.參考答案:度；孩子；雙親30.參考答案:B第2卷一.參考題庫(kù)(共30題)1.選擇排序2.下列關(guān)于算法的時(shí)間復(fù)雜度陳述正確的是（）A、算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間B、算法的時(shí)間復(fù)雜度是指算法程序的長(zhǎng)度C、算法的時(shí)間復(fù)雜度是指算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D、算法的時(shí)間復(fù)雜度是指算法程序中的指令條數(shù)3.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有（）棵。4.若要在單鏈表結(jié)點(diǎn)*P后插入一結(jié)點(diǎn)*S，執(zhí)行的語句（）。5.在對(duì)n個(gè)元素進(jìn)行快速排序的過程中，最好情況下需要進(jìn)行（）躺。A、nB、n/2C、log2nD、2n6.結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是（）結(jié)構(gòu)。7.設(shè)有向無環(huán)圖G中的有向邊集合E={，，，}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ǎ〢、1，2，3，4B、2，3，4，1C、1，4，2，3D、1，2，4，38.對(duì)序列{15，9，7，8，20，-1，4，}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-l，4，8，20，9，7}則該次采用的增量是（）A、1B、4C、3D、29.抽象數(shù)據(jù)類型的是什么？它有什么特點(diǎn)？10.已知指針p指向單鏈表中某一結(jié)點(diǎn)，將新生成的由s所指結(jié)點(diǎn)加到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（）。A、s-＞next=p-＞next；p->next=s；B、（*p）.next=s；（*s）.next=（*p）.next；C、s-＞next=p-＞next；p-＞next=s-＞next；D、s-＞next=p+1；?p-＞next=s；11.字符串a(chǎn)1=〝BEIJING〞，a2=〝BEF〞，a3=〝BEFANG〞，a4=“BEFI〞最小的是（）A、a1B、a2C、a3D、a412.順序查找適用于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A、散列B、順序或者鏈?zhǔn)紺、壓縮D、索引13.有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來開成二叉排序樹，若希望高度最小，則應(yīng)選擇下面哪個(gè)序列輸入（）。A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，5314.矩陣中的行列數(shù)往往是不相等的。15.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先（），后（）。16.由一棵二叉樹的前序序列和后序序列可以唯一確定它。17.已知一組記錄為（46，74，53，14，26，38，86，65，27，34），給出采用快速排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。18.有向圖的極大強(qiáng)連通子圖稱為（）19.如果廣義表中的元素全部都是原子，這種廣義表就是線性表。20.數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。21.對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（）。A、正確性B、可行性C、健壯性D、輸入性22.一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。23.如果一個(gè)有向圖不存在（），則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄小?4.設(shè)順序存儲(chǔ)的線性表存儲(chǔ)結(jié)構(gòu)定義為： structsequnce {ELEMTPelem[MAXSIZE]； intlen；/*線性表長(zhǎng)度域*/ } 將下列簡(jiǎn)單插入算法補(bǔ)充完整。 voidinsert（structsequnce*p，inti，ELEMTPx） {v=*p； if（iv.len+1）printf（“Overflow“）； else{ for（j=v.len；（）；j--）（）； v.elem[i]=（）；v.len=（）； } }25.在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)度的量級(jí)為（）。A、O（n）B、O（1）C、O（n2）D、O（log?n）26.二叉搜索樹的查找——遞歸算法，請(qǐng)完成括號(hào)里的內(nèi)容。 27.一棵有19個(gè)結(jié)點(diǎn)的二叉樹，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹結(jié)構(gòu)中有（）個(gè)指針域?yàn)榭铡?8.shell排序29.對(duì)于一裸具有n個(gè)結(jié)點(diǎn)的二又樹.當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí).其二又鏈表中的指針城的總數(shù)為（）個(gè).其中（n-1）個(gè)用于鏈接孩子結(jié)點(diǎn)（）個(gè)空閑著。30.棧的插入和刪除操作在（）。A、棧底B、棧頂C、任意位置D、指定位置第2卷參考答案一.參考題庫(kù)1.參考答案:選擇排序是每一趟在n-i+1（i=1，2，3…n-1）個(gè)記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。其中最簡(jiǎn)單的是簡(jiǎn)單選擇排序。2.參考答案:C3.參考答案:14.參考答案:s->next=p->next;p->next=s5.參考答案:C6.參考答案:樹形7.參考答案:A8.參考答案:B9.參考答案:抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進(jìn)一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。 抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。10.參考答案:A11.參考答案:B12.參考答案:B13.參考答案:B14.參考答案:錯(cuò)誤15.參考答案:移動(dòng)隊(duì)首指針取出元素16.參考答案:錯(cuò)誤17.參考答案:18.參考答案:有向圖的強(qiáng)連通分量19.參考答案:正確20.參考答案:錯(cuò)誤21.參考答