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

2023年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)考試歷年重點(diǎn)考核試題含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(共50題)1.線性表是n個元素的（）2.一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（）。A、1，2，3，4B、4，3，2，1C、1，4，3，2D、3，4，1，23.對于長度為n的順序存儲的有序表，若采用二分查找法，則對所有元素的最長查找長度為（）的值向下取整再加1。A、log2（n+1）B、n／2C、log2nD、（n+1）／24.對以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。 5.設(shè)有鍵值序列（k1，k2，…，kn），當(dāng)i>n/2時，任何一個子序列（ki，ki+1，…，kn）一定是堆。6.如果t中存在等于p的子串，就指出該子串在t中的位置，稱為匹配成功；否則稱為匹配失敗。7.將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（）。A、O（1）B、O（n）C、O（m）D、O（m+n）8.從一棵二叉排序樹中查找一個元素時，若元素的值等于根結(jié)點(diǎn)的值，則表明（），若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向（）查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向（）查找。9.已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：ACDBGIHFE和ABCDEFGHI。請畫出該二叉樹，并寫出它的前序遍歷的序列。10.當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用（）存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用（）存儲結(jié)構(gòu)為宜。11.設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data，link），且first為指向鏈表表頭的指針，current為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測current是否達(dá)到鏈表表尾的語句是（）。A、current->link=nullB、first->link=currentC、first=currentD、current->link=first12.深度為3的二叉樹最多有（）個結(jié)點(diǎn)。A、7B、8C、5D、613.設(shè)哈希函數(shù)H（K）=3?K?mod?11，哈希地址空間為0～10，對關(guān)鍵字序列（32，13，49，24，38，21，4，12），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。? ①?線性探測法；? ②?鏈地址法。14.以折半查找方法在一個查找表上進(jìn)行查找時，該查找表必須組織成（）存儲的（）表15.樹的帶權(quán)路徑長度最小的二叉樹中必定沒有度為1的結(jié)點(diǎn)。16.找出所有滿足下列條件的二叉樹： （1）它們在先序遍歷和中序遍歷時，得到的遍歷序列相同； （2）它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；? （3）它們在先序遍歷和后序遍歷時，得到的遍歷序列相同17.下列與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）A、棧B、散列表C、雙鏈表D、二叉樹18.將關(guān)鍵字（45，87，30，33，63，27，51，76）依次插入到一棵初始為空的二叉排序樹中。請回答：若在二叉排序樹中插入新的關(guān)鍵字60，則為尋找插入位置，分別與哪些關(guān)鍵字進(jìn)行比較。19.對于一個有向圖，不用拓?fù)渑判?，如何判定圖中是否存在環(huán)？20.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為（）。不允許插入和刪除運(yùn)算的一端稱為（）。21.評價排序算法優(yōu)劣的主要標(biāo)準(zhǔn)是（）和（）22.一個遞歸算法必須包括（）。A、遞歸部分B、終止條件和遞歸部分C、迭代部分D、終止條件和迭代部分23.設(shè)哈希表的地址范圍為0～17，哈希函數(shù)為：H（key）=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問題：假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。24.在棧這種數(shù)據(jù)結(jié)構(gòu)中，棧能插入刪除的一端稱為棧頂。25.對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的三項信息是（）、（）、（）。26.計算二叉樹上單分支結(jié)點(diǎn)數(shù)目。假設(shè)二叉樹的存儲結(jié)構(gòu)描述如下： 27.二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（）個字節(jié)。28.設(shè)散列表的長度為16，散列函數(shù)為H（k）=k%13，用線性探測法處理沖突，依次插入關(guān)鍵字：19，01，13，23，24，55，20，84，27，68，11，10，77。請回答：畫出散列表示意圖并給出查找每個關(guān)鍵字時需要比較的次數(shù)。29.對于雙目操作符，其重載函數(shù)帶有（）個參數(shù)，其中至少有一個為（）的類型。30.一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。31.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（）32.（）排序方法使鍵值大的記錄逐漸下沉，使鍵值小的記錄逐漸上浮。33.二叉樹可以是空二叉樹。34.二叉樹中每個結(jié)點(diǎn)有兩個子結(jié)點(diǎn)，而對一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。35.證明：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無環(huán)圖的鄰接矩陣中主對角線以下的元素全部為0。36.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點(diǎn)序列。 37.頂點(diǎn)表示活動，邊表示活動之間的先后關(guān)系的有向圖為頂點(diǎn)活動網(wǎng)稱為（）。38.已知數(shù)據(jù)序列{53，36，48，36，60，7，18，41}，寫出采用簡單選擇排序的每一趟排序結(jié)果。39.帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。40.折半查找法適用于（）。A、有序順序表B、有序單鏈表C、有序順序表和有序單鏈表都可以D、無限制41.對給定的j（142.已知指針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；43.樹若不是空樹，則有一個結(jié)點(diǎn)叫做什么，它沒有前驅(qū)（）。A、葉子B、根結(jié)點(diǎn)C、樹叉D、終端結(jié)點(diǎn)44.寫出運(yùn)行下列程序段的輸出結(jié)果。 45.下列四個說法哪個正確？（）A、堆棧是在兩端操作、先進(jìn)后出的線性表B、堆棧是在一端操作、先進(jìn)先出的線性表C、隊列是在一端操作、先進(jìn)先出的線性表D、隊列是在兩端操作、先進(jìn)先出的線性表46.計算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是（），第二種是（）47.消除遞歸不一定需要使用棧。48.堆排序是一種（）排序。A、插入B、選擇C、交換D、歸并49.對于長度為n的線性表，若采用分塊查找（假定總塊數(shù)和每塊長度均接近，用順序查找確定所在塊），則時間復(fù)雜性為多少？50.數(shù)據(jù)結(jié)構(gòu)里，已知product是結(jié)構(gòu)體類型，下列選項中是定義含有十個元素是該類型的數(shù)組格式正確的是（）。A、structproducta[10]；B、structproducta{10}；C、structproducta；D、structproducta（10）；第1卷參考答案一.參考題庫1.正確答案:有限序列2.正確答案:A3.正確答案:C4.正確答案:5.正確答案:正確6.正確答案:正確7.正確答案:C8.正確答案:查找成功；左子樹；右子樹9.正確答案:恢復(fù)的二叉樹為： 10.正確答案:順序；鏈接11.正確答案:D12.正確答案:A13.正確答案:14.正確答案:順序；有序15.正確答案:正確16.正確答案:（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹； （2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹； （3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點(diǎn)的二叉樹。17.正確答案:D18.正確答案:若在二叉排序樹中插入新的關(guān)鍵字60，則為尋找插入位置，分別與關(guān)鍵字45,87,63,51進(jìn)行比較。19.正確答案:對于無向圖，如果在深度優(yōu)先遍歷中遇到回邊，則必定存在環(huán)。對于有向圖，如果從有向圖的某個頂點(diǎn)v出發(fā)的遍歷，在DFS(v)結(jié)束之前出現(xiàn)了一條從頂點(diǎn)u指向v的回邊，則此有向圖必定存在環(huán)。因為u在深度優(yōu)先生成樹上是v的子樹，即存在u到v的路徑，現(xiàn)在又出現(xiàn)一條從u指向v的弧，則它們必然構(gòu)成一條回路。20.正確答案:棧頂棧底21.正確答案:時間復(fù)雜性；算法需要的附加空間22.正確答案:B23.正確答案:對于黑色數(shù)據(jù)元素，各比較1次；共6次；?對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/1124.正確答案:正確25.正確答案:行下標(biāo)；列下標(biāo)；數(shù)組元素26.正確答案:27.正確答案:54028.正確答案:29.正確答案:2；用戶自定義30.正確答案:錯誤31.正確答案:2、332.正確答案:冒泡33.正確答案:正確34.正確答案:錯誤35.正確答案:任意n個結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個拓?fù)湫蛄小ＴO(shè)拓?fù)湫蛄袨関0v1v2…vn-1，我們來證明此時的鄰接矩陣A為上三角矩陣。證明采用反證法。 假設(shè)此時的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄?，vi的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。36.正確答案:DLR：A?B?D?F?J?G?K?C?