2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)歷年考試高頻考點(diǎn)試題附帶答案

2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)歷年考試高頻考點(diǎn)試題附帶答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(共25題)1.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i（1≤i≤n），則它的左孩子結(jié)點(diǎn)的編號(hào)為（），右孩子結(jié)點(diǎn)的編號(hào)為（），雙親結(jié)點(diǎn)的編號(hào)為（）2.如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。3.以孩子兄弟表示法做存儲(chǔ)結(jié)構(gòu)，求樹中結(jié)點(diǎn)x的第i個(gè)孩子。4.在高級(jí)語言中，不可以定義結(jié)構(gòu)體類型的指針變量。5.算法分析的兩個(gè)主要方面是（）。A、空間復(fù)雜度和時(shí)間復(fù)雜度B、正確性和簡(jiǎn)單性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6.隊(duì)列操作的原則是（）。A、先進(jìn)先出B、后進(jìn)先出C、只能進(jìn)行插入D、只能進(jìn)行刪除7.對(duì)順序表的優(yōu)缺點(diǎn)，以下說法錯(cuò)誤的是（）A、無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)C、插入和刪除運(yùn)算較為方便D、由于要求占用連續(xù)空間，所以存儲(chǔ)分配只能預(yù)先進(jìn)行（靜態(tài)分配）8.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為（）。不允許插入和刪除運(yùn)算的一端稱為（）。9.程序越短，程序運(yùn)行的時(shí)間就越少。10.假設(shè)R是集合M上的一個(gè)關(guān)系，R的定義是什么？對(duì)實(shí)際問題而言，其含義是什么？11.在樹的概念中，下列選項(xiàng)中關(guān)于樹的兄弟描述正確的是（）A、雙親是同一個(gè)結(jié)點(diǎn)B、雙親是不同的結(jié)點(diǎn)C、在樹中不同的層D、都不對(duì)12.廣義表（f?，h?，（a?，b，d，c），d?，e?，（（i?，j），k?））的長(zhǎng)度是（）。13.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb14.結(jié)點(diǎn)的層次15.設(shè)散列表表長(zhǎng)m=14，散列函數(shù)H（k）=kmod11。表中已有15、38、61、84四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素49的存儲(chǔ)地址是（）。A、8B、3C、5D、916.數(shù)據(jù)結(jié)構(gòu)里，以下字符串處理函數(shù)中，返回值不是char的是（）。A、strcatB、strcmpC、strcpyD、strlen17.序列3，1，7，18，6，9，13，12經(jīng)一趟歸并排序的結(jié)果為（）。18.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）。A、98B、99C、50D、4819.已知一個(gè)無向圖的鄰接表如圖所示，要求：畫出該無向圖20.已知哈希表地址空間為A[0..8]，哈希函數(shù)為H（k）=k?mod?7，采用線性探測(cè)再散列處理沖突。若依次將數(shù)據(jù)序列：76，45，88，21，94，77，17存入該散列表中則元素17存儲(chǔ)的下標(biāo)為（）。A、0B、1C、2D、3E、4F、5G、6H、721.以下程序是前序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 22.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（） A、AB、BC、CD、D23.樹的后跟遍歷24.對(duì)一組記錄（5，8，9，2，12，7，56，44，39）進(jìn)行直接插入排序（由小到大排序），當(dāng)把第6個(gè)記錄7插入有序表，為尋找插入位置需比較（）次。25.從有序表(14，20，33，45，54，72，87，96)中，分別用二分查找法查找45和54元素時(shí)，其查找長(zhǎng)度分別為（）和（）第2卷一.參考題庫(共25題)1.假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判定樹高度為（），判定樹中前5層的結(jié)點(diǎn)數(shù)為（），最后一層的結(jié)點(diǎn)數(shù)為（）。2.對(duì)于一個(gè)棧，給出輸入項(xiàng)A，B，C。如果輸入項(xiàng)順序?yàn)锳，B，C所組成，則全部可能的輸出項(xiàng)有（）種，不可能的輸出項(xiàng)為（）。3.數(shù)據(jù)結(jié)構(gòu)里，線性結(jié)構(gòu)有：順序表、鏈表、棧、隊(duì)列。4.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為（）。A、?nB、?2nC、?eD、?2e5.已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對(duì)該數(shù)據(jù)序列進(jìn)行排序，寫出插入排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序以及二路歸并排序每趟的結(jié)果。6.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。A、abcd+-B、abc+*d-C、abc*+d-D、-+*abcd7.在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是（）。A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表8.順序表插入、刪除分別需要移動(dòng)（）個(gè)元素。A、n-iB、n-i+1C、n-1D、n-29.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（） 10.假定一個(gè)順序表的長(zhǎng)度為40，并假定查找每個(gè)元素的概率都相同，則在查找成功情況下的平均查找長(zhǎng)度（），在查找不成功情況下的平均查找長(zhǎng)度（）。11.下列關(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ù)12.對(duì)于右圖所示的樹： 寫出按層遍歷得到的結(jié)點(diǎn)序列。13.在無向圖G的鄰接矩陣A中，若A[i，j]等于1，則A[j，i]等于（）A、i+jB、i-jC、1D、014.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。15.單鏈表的主要優(yōu)點(diǎn)是（）A、便于隨機(jī)查詢B、存儲(chǔ)密度高C、邏輯上相鄰的元素在物理上也是相鄰的D、插入和刪除比較方便16.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系都相同。17.假設(shè)用于通信的電文由字符集{a，b，c，d，e，f，g，h}中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，試為這8個(gè)字母進(jìn)行哈夫曼編碼。請(qǐng)回答：求出此哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL。18.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。A、head==NULLB、head->next==NULLC、head->next!=NULLD、head!=NULL19.已知一棵度為m的樹中有：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？20.哈夫曼樹是指（）的二叉樹。21.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。22.樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A、每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B、一對(duì)一C、多對(duì)多D、一對(duì)多23.設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長(zhǎng)度為（） A、AB、BC、CD、D24.已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC（A[0][0]），則A[i][j]的地址是（）。25.從存儲(chǔ)結(jié)構(gòu)上可以把數(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)第3卷一.參考題庫(共25題)1.數(shù)據(jù)結(jié)構(gòu)里，空格串與空串是一樣的概念。2.下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（）。A、求節(jié)點(diǎn)的度B、拓?fù)渑判駽、求最短路徑D、求關(guān)鍵路徑3.數(shù)據(jù)結(jié)構(gòu)里，結(jié)構(gòu)體數(shù)組，即定義數(shù)組的每個(gè)元素都是一個(gè)結(jié)構(gòu)體類型的。4.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)。5.數(shù)組A[1‥40，1‥30]采用三元組表示，設(shè)數(shù)組元素與下標(biāo)均為整型，則在非零元素個(gè)數(shù)小于（）時(shí)，才能節(jié)省存儲(chǔ)空間。A、1200B、401C、399D、4006.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素算法的時(shí)間復(fù)雜度（）。A、O（log2n）B、O（1）C、O（n）D、O（n2）7.已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da1，則第I個(gè)結(jié)點(diǎn)的地址為（）。A、da1+（I-1）*mB、da1+I*mC、da1-I*mD、da1+（I+1）*m8.（1）?設(shè)計(jì)二次多項(xiàng)式ax2+bx+c的一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分為多項(xiàng)式的三個(gè)系數(shù)項(xiàng)a、b、c；操作部分包括：初始化數(shù)據(jù)成員a、b、c，實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加，給定x求多項(xiàng)式的值，求方程ax2 +bx+c=0的兩個(gè)實(shí)根，按照ax**2+bx+c的格式輸出二次多項(xiàng)式。??? （2）?假定數(shù)據(jù)成員a、b、c定義如下： ?????? 請(qǐng)寫出上述各操作的具體實(shí)現(xiàn)。9.有一個(gè)100×90的稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（）。A、20B、66C、18000D、3310.畫出下圖所示有向圖的所有強(qiáng)連通分量。 11.函數(shù)重載要求（）、（）或（）有所不同。12.設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為（）在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為（）13.證明任何一棵滿二叉樹T中的分支數(shù)B滿足B=2(N0-1)（其中N0為葉子結(jié)點(diǎn)數(shù)）。14.對(duì)于線性表（18，25，63，50，42，32，90）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為0的元素有（）個(gè)，散列地址為5的元素有（）個(gè)。15.數(shù)據(jù)結(jié)構(gòu)里，二叉樹中的結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)。16.下列關(guān)于圖遍歷的說法不正確的是（）。A、連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B、圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征C、非連通圖不能用深度優(yōu)先搜索法D、圖的遍歷要求每一頂點(diǎn)僅被訪問一次17.在一個(gè)單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）。A、p->next=p->next->next；B、p=p->next；p->next=p->next->next；C、p=p->next；D、p=p->next->next；18.假定一個(gè)待散列存儲(chǔ)的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長(zhǎng)度。19.在一個(gè)無向圖中，若兩頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑上的頂點(diǎn)數(shù)為（）。A、?kB、?k+1C、?k+2D、?2k20.已知一個(gè)無向圖的鄰接表如圖所示，要求：根據(jù)鄰接表，分別寫出用DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）算法從頂點(diǎn)V0開始遍歷該圖后所得到的遍歷序列。21.有向樹22.假設(shè)有60行70列的二維數(shù)組a[1…60，1…70]以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32，58]的存儲(chǔ)地址為。（無第0行第0列元素）（）A、16902B、16904C、14454D、答案A，B，C均不對(duì)23.順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（）。A、鏈表B、數(shù)組C、循環(huán)鏈表D、變量24.下述（）是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？A、存儲(chǔ)密度大B、插入運(yùn)算方便C、刪除運(yùn)算方便D、可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示25.兩個(gè)非遞增有序的順序表可以（）成一個(gè)非遞增有序的順序表。A、合并B、插入C、刪除D、修改第1卷參考答案一.參考題庫1.參考答案:2i；2i+1；i/2（或i/2）2.參考答案:錯(cuò)誤3.參考答案:先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于x的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域firstchild找到值為x結(jié)點(diǎn)的第一個(gè)孩子，再沿右兄弟域rightsib找到值為x結(jié)點(diǎn)的第i個(gè)孩子并返回指向這個(gè)孩子的指針。 樹的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如下： 具體算法如下： 4.參考答案:錯(cuò)誤5.參考答案:A6.參考答案:A7.參考答案:C8.參考答案:棧頂棧底9.參考答案:錯(cuò)誤10.參考答案:如果R是對(duì)集合M自身的笛卡爾積所取的一個(gè)子集，那么我們就說“R是集合M上的一個(gè)關(guān)系”。對(duì)實(shí)際問題而言，它表示的是集合M中元素的某種相關(guān)性。例如，對(duì)于參加一個(gè)羽毛球比賽的運(yùn)動(dòng)員集合，可以用一個(gè)二元關(guān)系表示出各場(chǎng)比賽的勝負(fù)關(guān)系。對(duì)于一組課程的集合，可以用一個(gè)二元關(guān)系表示出各門課程之間的先修和后續(xù)關(guān)系等等。11.參考答案:A12.參考答案:613.參考答案:D14.參考答案:從樹根開始定義，根結(jié)點(diǎn)為第1層，它的子結(jié)點(diǎn)為第2層，以此類推。15.參考答案:A16.參考答案:B,D17.參考答案:1，3，7，18，6，9，12，1318.參考答案:A19.參考答案:20.參考答案:F21.參考答案:22.參考答案:C23.參考答案:若樹非空，則按從左到右的順序遍歷根結(jié)點(diǎn)的每一棵子樹，之后再訪問根結(jié)點(diǎn)。其訪問順序與其對(duì)應(yīng)的二叉樹的中序遍歷相同。24.參考答案:425.參考答案:1；3第2卷參考答案一.參考題庫1.參考答案:6；31；192.參考答案:5；CAB3.參考答案:正確4.參考答案:A5.參考答案:用上述排序方法的每趟結(jié)果如下： 6.參考答案:B7.參考答案:D8.參考答案:A,B9.參考答案:log2n10.參考答案:20.5；4111.參考答案:C12.參考答案:abcdefghijklm13.參考答案:C14.參考答案:正確15.參考答案:D16.參考答案:正確17.參考答案:18.參考答案:B19.參考答案:設(shè)該樹的總結(jié)點(diǎn)數(shù)為n， 則n=n0+n1+n2+……+nm 又：n=分枝數(shù)+1=0×n0+1×n1+2×n2+……+m×nm+1由上述兩式可得： N.0=n2+2n3+……+（m-1）nm+120.參考答案:帶權(quán)路徑長(zhǎng)度最小21.參考答案:錯(cuò)誤22.參考答案:D23.參考答案:B24.參考答案:Loc(A[0][0])+(i*N+j)*k25.參考答案:C第3卷參考答案一.參考題庫1.參考答案:錯(cuò)誤2.參考答案:B3.參考答案:正確4.參考答案:前驅(qū)；后繼5.參考答案:D6.參考答案:C