2023年大學試題(計算機科學)-數(shù)據(jù)結(jié)構(gòu)考試歷年重點考核試題含答案

2023年大學試題(計算機科學)-數(shù)據(jù)結(jié)構(gòu)考試歷年重點考核試題含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(共50題)1.二叉排序樹2.中綴算術(shù)表達式3+4/（25-（6+15））*8所對應的后綴算術(shù)表達式為（）。3.在一個長度為n的順序表中，向第i個元素（1≤i≤n+1）之前插入一個新元素時，需要向后移動（）個元素。 A、AB、BC、CD、D4.對于記錄序列A[1]~A[n]可按如下如下方法實現(xiàn)奇偶交換排序：第一趟對所有的奇數(shù)i，將A[i]和A[i+1]進行比較，第二趟對所有的偶數(shù)i，將A[i]和A[i+1]進行比較，每次比較時若A[i]>A[i+1]，則將二者交換，然后重復上述排序過程，直至整個數(shù)組有序。編寫算法實現(xiàn)上述奇偶交換排序。5.已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列。 a.在P結(jié)點后插入S結(jié)點的語句序列是（）。 b.在P結(jié)點前插入S結(jié)點的語句序列是（）。 c.在表首插入S結(jié)點的語句序列是（）。 d.在表尾插入S結(jié)點的語句序列是（）。 （1）P->next=S； （2）P->next=P->next->next； （3）P->next=S->next； （4）S->next=P->next； （5）S->next=L； （6）S->next=NULL； （7）Q=P； （8）while（P->next!=Q）P=P->next； （9）while（P->next!=NULL）P=P->next； （10）P=Q； （11）P=L； （12）L=S； （13）L=P；6.抽象數(shù)據(jù)類型7.對于采用順序存儲結(jié)構(gòu)的串S，編寫一個函數(shù)刪除其值等于ch的所有字符。8.基數(shù)排序9.設有森林?B=（D，S），???? D={A，B，C，D，E，F(xiàn)，G，H，I，J}，?r∈S? r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F(xiàn)〉，〈G，H〉，〈G，I〉，〈I，J〉}??請回答：畫出與森林對應的二叉樹的邏輯結(jié)構(gòu)圖示。10.用線性表的順序結(jié)構(gòu)來描述一個城市的設計和規(guī)劃合適嗎？為什么？11.請列舉出一些可以用棧和隊列表示的實際問題。12.給定結(jié)點的關(guān)鍵字序列為：47，7，29，11，16，92，22，8，3，哈希表的長度為11。設散列函數(shù)為：H（K）=K%11。試畫出平方探測再散列解決沖突時所構(gòu)造的散列表，并求出其平均查找長度。13.單循環(huán)鏈表14.簡述基數(shù)排序的具體步驟。15.設有森林B=（D，S）， D={A，B，C，D，E，F(xiàn)，G，H，I，J}，r∈S r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F(xiàn)〉，〈G，H〉，〈G，I〉，〈I，J〉}請回答：寫出此二叉樹的前序、中序、后序遍歷序列。16.（1）一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56）利用堆排序（堆頂元素是最小元素）的方法建立初始堆（要求以完全二叉樹描述?）。 （2）對關(guān)鍵字序列（56，51，71，54，46，106）利用快速排序，以第一個關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。 （3）一組記錄的關(guān)鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方法，分別給出（1，1）歸并、（2，2）歸并、（4，4）歸并的結(jié)果序列。17.循環(huán)順序隊列的存儲結(jié)構(gòu)圖示及C語言描述？ 18.編寫一個雙向起泡的排序算法，即相鄰兩趟向相反方向起泡。19.簡述二路歸并排序的具體步驟。20.設數(shù)據(jù)結(jié)構(gòu)A=（D，R），其中則數(shù)據(jù)結(jié)構(gòu)A是（）A、線性結(jié)構(gòu)B、樹型結(jié)構(gòu)C、圖型結(jié)構(gòu)D、集合21.設某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（） A、AB、BC、CD、D22.選擇排序23.假設一個算術(shù)表達式中可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)。24.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是（） 25.的深度是（）26.編寫一個算法，利用棧的基本運算返回指定棧中的棧底元素。27.已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？28.簡述邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系.29.執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？ 30.簡述各種查找算法的適用范圍。31.一個帶權(quán)無向圖的最小生成樹是否一定唯一？在什么情況下構(gòu)造出的最小生成樹可能不唯一？32.物理結(jié)構(gòu)（存儲結(jié)構(gòu)）33.什么是順序表？什么是棧？什么是隊列？34.用開放地址法的二次探測再散列方法Hi=（H（key）+di）mod10（di=12，22，32，…，）解決沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計算查找成功的平均查找長度。35.寫出下列程序段的運行結(jié)果（棧中的元素類型是char）： 36.對給定的j（137.設線性表，A=（a1，a2，…，am）B=（b1，b2，…，bn），試寫一個按下列規(guī)則合并A，B為線性表C的算法，即使得 C=（a1，b1，…，am，bm，bm+1，…，bn）當m≤n時； C=（a1，b1，…，an，bn，an+1，…，am）當時m＞n時。 線性表A，B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。38.依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 （1）對該二叉樹進行查找，成功查找到38，和46各要進行多少次元素間的比較？ （2）給出按后序遍歷該二叉排序樹的序列。39.下圖的拓撲序列是（）。 A、5、2、3、4、6B、2、3、6、4、5C、5、6、2、3、4D、2、3、5、6、440.堂兄弟41.設計算法按前序次序打印二叉樹中的葉子結(jié)點。42.循環(huán)隊列43.對于如圖所示的帶權(quán)無向圖，用圖示說明： 利用Kruskal算法構(gòu)造最小生成樹的過程44.在程序設計中，可采用下列三種方法實現(xiàn)輸出和輸入： （1）通過scanf和printf語句； （2）通過函數(shù)的參數(shù)顯式傳遞； （3）通過全局變量隱式傳遞。 試討論這三種方法的優(yōu)缺點。45.有向完全圖46.設如下圖所示的二叉樹B的存儲結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點結(jié)構(gòu)為：（lchild，data，rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：假定二叉樹B共有n個結(jié)點，試分析算法traversal（root）的時間復雜度。47.假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設一個隊尾指針rear，試填空完成向循環(huán)隊列中插入一個元素為x的結(jié)點的函數(shù)。 48.已知一組記錄為（46，74，53，14，26，38，86，65，27，34），給出采用冒泡排序法進行排序時每一趟的排序結(jié)果。49.指出以下算法中的錯誤和低效之處，并將它改寫為一個既正確又高效的算法。 50.歸并排序第1卷參考答案一.參考題庫1.正確答案: 一棵二叉樹或是空二叉樹或是具有以下性質(zhì)的二叉樹：左子樹上所有關(guān)鍵字均小于根結(jié)點的關(guān)鍵字，右子樹所有結(jié)點關(guān)鍵字大于根結(jié)點的關(guān)鍵字。左子樹和右子樹又各是一棵二叉排序樹。2.正確答案: 3.正確答案:B4.正確答案:具體算法如下： 5.正確答案: a.（4）（1） b.（7）（11）（8）（4）（1） c.（5）（12） d.（9）（1）（6）6.正確答案: 是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。7.正確答案:從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下： 8.正確答案: 基數(shù)排序是借助“分配”和“收集”兩種操作對單邏輯關(guān)鍵字進行排序的一種內(nèi)排序方法。9.正確答案: 10.正確答案: 不合適。因為一個城市的設計和規(guī)劃涉及非常多的項目，很復雜，經(jīng)常需要修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應其需要，故是不合適的。11.正確答案: 所有“后進先出”（LIFO，LastInFirstOut）的實際問題都可以用棧表示。棧的應用主要有：數(shù)制的轉(zhuǎn)換、括號的匹配檢查、行編輯處理、表達式求解、走迷宮以及高級語言中函數(shù)的嵌套調(diào)用和遞歸的實現(xiàn)等。 所有“先進先出”（FIFO，F(xiàn)irstInFirstOut）的實際問題都可以用隊列表示。如日常中的排隊問題，隊列的應用主要有：操作系統(tǒng)中各種資源請求排隊和各種緩沖區(qū)的先進先出管理，各種應用系統(tǒng)中的事件規(guī)劃和事件模擬，樹的層次遍歷和圖的廣度優(yōu)先遍歷等。12.正確答案:平方探測再散列解決沖突時所構(gòu)造的散列表。 13.正確答案: 是單鏈表的另一種形式，它是一個首尾相接的鏈表，表中最后一個結(jié)點的指針域由null改為指向頭結(jié)點或線性表的第一個結(jié)點，整個鏈表形成了一個環(huán)。14.正確答案: 15.正確答案: 前序遍歷序列：ABECFDGHIJ 中序遍歷序列：EBFCDAHJIG 后序遍歷序列：EFDCBJIHGA16.正確答案: 17.正確答案: 18.正確答案:19.正確答案: 20.正確答案:A21.正確答案:C22.正確答案: 每一趟在未排序的記錄中選擇最小的記錄作為有序序列部分的下一個記錄。23.正確答案:假設表達式已存入字符數(shù)組A[n]中，具體算法如下：24.正確答案:nlog2n25.正確答案:426.正確答案: 27.正確答案: 28.正確答案: 數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。29.正確答案: 30.正確答案: 各種查找算法的適用范圍： A.順序查找雖然查找效率最低，但其對待查找數(shù)據(jù)集合的存儲結(jié)構(gòu)無特別要求，在對數(shù)據(jù)集合進行增、刪、改等操作時效率較高，因此，根據(jù)那些不需要經(jīng)常作查找操作的關(guān)鍵字進行查找時，一般采用順序查找算法。若經(jīng)常作查找操作，則應使用效率較高的其他查找算法。 B.折半查找和分塊查找主要適用于數(shù)據(jù)集合增、刪、改等操作較少的情況；二叉排序樹查找則適用于數(shù)據(jù)集合變化較頻繁的情況。 C.哈希查找雖然在理論上具有最短的平均查找長度，但它占用的存儲空間較多，且在實際中只有哈希函數(shù)構(gòu)造得好才能達到常量級的平均查找長度。而要想構(gòu)造出好的哈希函數(shù)，必須以大量數(shù)據(jù)為基礎，因此，哈希查找主要適用于數(shù)據(jù)分布已知的情況。31.正確答案: 一個帶權(quán)無向圖的最小生成樹不一定是唯一的。從Kruskal算法構(gòu)造最小生成樹的過程可以看出，當從圖中選擇當前權(quán)值最小的邊時，如果存在多條這樣的邊，并且這些邊與已經(jīng)選取的邊構(gòu)成回路，此時這些邊就不可能同時出現(xiàn)在一棵最小生成樹中，對這些邊的不同選擇結(jié)果可能會產(chǎn)生不同的最小生成樹。32.正確答案: 物理結(jié)構(gòu)又稱為數(shù)據(jù)的存儲結(jié)構(gòu)，是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的映像（表示），即數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲方法。33.正確答案: 當線性表采用順序存儲結(jié)構(gòu)時，即為順序表。 棧是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入與刪除操作只能在這種線性表的同一端進行（即棧頂），因此，棧具有先進后出、后進先出的特點。 隊列也是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入在表的一端進行，數(shù)據(jù)的刪除在表的另一端進行，因此隊列具有先進先出，后進后出的特點。34.正確答案:35.正確答案:程序段的運行結(jié)果為stack。37.正確答案: 38.正確答案: （1）4次；3次 （2）5，40，38，46，20，64，5239.正確答案:C40.正確答案: 同一層上不同雙親的結(jié)點，互稱堂兄弟。41.正確答案:本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。為此，將前序遍歷 算法中的訪問操作改為條件打印即可。算法如下： 42.正確答案: 在隊列的順序存儲結(jié)構(gòu)中，把存儲空間的首尾邏輯上相連，構(gòu)成一個環(huán)，使得存儲空間上只要有空余的地址，就可以繼續(xù)進行入隊列操作，極大利用了物理空間。用頭部和尾部兩個指示器表示隊列頭和隊列尾，插入在尾部進行，刪除在頭部進行。43.正確答案:44.正確答案: （1）用scanf和printf直接進行輸入輸出的好處是形象、直觀，但缺點是需要對其進行格式控制，較為煩瑣，如果出現(xiàn)錯誤，則會引起整個系統(tǒng)的崩潰。 （2）通過函數(shù)的參數(shù)傳遞進行輸入輸出，便于實現(xiàn)信息的隱蔽，減少出錯的可能。 （3）通過全局變量的隱式傳遞進行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護較為困難。45.