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

2023年大學試題(計算機科學)-數(shù)據(jù)結(jié)構(gòu)考試歷年真摘選題含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(共100題)1.在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為（），p*=j語句的執(zhí)行次數(shù)為（），該程序段的時間復雜度為（）。 2.二路歸并排序的時間復雜度為（） A、AB、BC、CD、D3.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是（）A、0243165B、0135642C、0123465D、01234564.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的物理結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？5.假設將循環(huán)隊列定義為：以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法（在出隊列的算法中要返回隊頭元素）。6.一份電文中有6種字符：A，B，C，D，E，F(xiàn)，它們的出現(xiàn)頻率依次為16，5，9，3，30，1，完成問題：（1）設計一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）（2）計算其帶權(quán)路徑長度WPL；7.以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格。 8.一組記錄的排序碼為（25，48，16，35，79，82，23，40），其中含有4個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為：（）。 A、AB、BC、CD、D9.假定一個待散列存儲的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。10.設計一個時間復雜度為O（n）的算法，實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個位置。11.設計一個算法，其功能為：利用直接插入排序的方法，將一組存儲在帶頭結(jié)點的單鏈表中的記錄遞增排序。請將算法補充完整。 12.采用兩種不同的算法，找出數(shù)組a[n]（n=2k，k≥1）中的最大元素，說明兩種算法所采用的設計方法及其特點。13.裴波那契（Fibonacci）數(shù)列的定義為：它的第1項和第2項均為1，以后各項為其前兩項之和。若裴波那契數(shù)列中的第n項用Fib（n）表示，則計算公式為： 試編寫出計算Fib（n）的遞歸算法和非遞歸算法，并分析它們的時間復雜度和空間復雜度。14.荷蘭國旗問題。要求重新排列一個由字符R，W，B（R代表紅色，W代表白色，B代表蘭色，這都是荷蘭國旗的顏色）構(gòu)成的數(shù)組，使得所有的R都排在最前面，W排在其次，B排在最后。為荷蘭國旗問題設計一個算法，其時間性能是O（n）。15.線索16.如下所示的有向圖，回答下面問題： （1）該圖是強連通的嗎？若不是，給出強連通分量。 （2）請給出圖的鄰接矩陣和鄰接表表示。17.設某帶頭結(jié)頭的單鏈表的結(jié)點結(jié)構(gòu)說明如下：typedefstructnodel{intdatastructnodel*next；}node；試設計一個算法：voidcopy（node*headl，node*head2），將以head1為頭指針的單鏈表復制到一個不帶有頭結(jié)點且以head2為頭指針的單鏈表中。18.簡要敘述棧和隊列的特點19.根據(jù)數(shù)據(jù)結(jié)構(gòu)的類型的定義分析算法： 根據(jù)此算法定義的數(shù)據(jù)結(jié)構(gòu)的類型，此算法的功能是什么？20.求子串函數(shù) 的結(jié)果是（）21.指出以下算法中的錯誤和低效之處，并將它改寫為一個既正確又高效的算法。 22.對給定文件（28，07，39，10，65，14，61，17，50，21）選擇第一個元素28進行劃分，寫出其快速排序第一遍的排序過程。23.滿二叉樹24.設無向圖G（如圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。 25.隊列26.假定查找有序表A[25]中每一元素的概率相等，試分別求出進行順序、二分查找每一元素時的平均查找長度。27.簡述樹、二叉樹、滿二叉樹和完全二叉樹的結(jié)構(gòu)特性。28.對于結(jié)點類型為LNode的單鏈表，編寫出下列算法： 統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。29.設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（） A、AB、BC、CD、D30.試利用循環(huán)隊列編寫求k階菲波那契序列中前n+1項的算法，要求滿足：fn≤max而fn+1＞max，其中max為某個約定的常數(shù)。（注意：本題所用循環(huán)隊列的容量僅為k，則在算法執(zhí)行結(jié)束時，留在循環(huán)隊列中的元素應是所求k階菲波那契序列中的最后k項）31.寫一算法實現(xiàn)單鏈表的逆置。32.串33.循環(huán)隊列的優(yōu)點是什么？在循環(huán)隊列中，僅依據(jù)頭尾指針相等，無法判斷隊列是“空”還是“滿”。要解決這個問題，常用的兩種方法是什么？34.子孫35.有一個早晨7點到晚上11點營業(yè)的連鎖店，叫7-11店。一次，一位顧客在該店選了4樣東西，付款時，營業(yè)員計算后說：“總共是7.11元?！鳖櫩烷_玩笑說：“哦？難道因為你們是7-11店，所以我就要付7.11元嗎？”營業(yè)員沒有聽出是在開玩笑，便回答說：“當然不是，我是把4樣東西的價格相乘才得出結(jié)果的！”顧客非常吃驚，說：“你怎么把它們相乘呢？，應該把它們相加才對！”營業(yè)員聽后，忙說：“噢，對不起，我今天頭非常疼，所以按錯計算器的鍵了?！辈②s緊把4樣東西的價格相加重算了一遍，但結(jié)果令兩個人都十分驚訝：總和還是7.11元。請設計一個算法計算這四樣東西的價格各是多少？36.指出下述程序段的功能是什么？ 37.將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉排序樹中，請畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。38.具有n個頂點的強連通圖至少有多少條邊？這樣的圖應該是什么形狀？39.數(shù)據(jù)40.設有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。41.設s=“IAMASTUDENT”，t=“GOOD”，q=“WORKER”。 求：StrLength（s），StrLength（t），SubStr（s，8，7），SubStr（t，2，1），StrIndex（s，“A”），StrIndex（s，t），StrRep（s，“STUDENT”，q），SubStr（SubStr（s，6，2），StrConcat（t，SubStr（s，7，8）））。42.shell排序43.設線性表，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均未顯式存儲。44.設圖的鄰接鏈表如下圖所示，則該圖有（）條邊。 A、4B、5C、10D、2045.寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型。46.設關鍵字序列為（71，12，88，53，11，25，65，27，16），散列函數(shù)為H（key）=key%7，采用鏈地址法解決沖突。請回答：畫出散列表示意圖（用頭插法向單鏈表中插入結(jié)點）。47.線索二叉樹48.簡述以下算法的功能（棧的元素類型SElemType為int）。 49.設一個有向圖為G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，請回答下列各問：對（2）中的鄰接矩陣，給出從頂點v2出發(fā)的DFS序列和DFS生成樹。50.對應圖，寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個。 51.簡述常用的四種哈希函數(shù)及其計算規(guī)則。52.假設用于通訊的電文僅由8個字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請為這8個字母設計哈夫曼編碼。53.已知一棵具有n個結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的A[1]～A[n]元素中，試編寫一個算法打印出編號為i的結(jié)點的雙親和所有孩子。54.簡述數(shù)據(jù)結(jié)構(gòu)中討論的三種經(jīng)典結(jié)構(gòu)的邏輯特征是什么？55.寫出下列用快排序?qū)ο铝行蛄羞M行兩次劃分的過程及結(jié)果。 56.設待排序的關鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關鍵字序列的狀態(tài)?？焖倥判?7.給定權(quán)值{8，12，4，5，26，16，9}，構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹，并計算其帶權(quán)路徑長度。58.在一棵深度為k的完全二叉樹中，所含結(jié)點個數(shù)不小于（）A、AB、BC、CD、D59.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹。60.（1）設根為第1層，對給定權(quán)值1，3，4，4，5，6，構(gòu)造深度為5的哈夫曼樹。 提示：構(gòu)造中當出現(xiàn)被選的結(jié)點值有多個相等時，可嘗試不同組合，以得到要求的樹的深度。 （2）求樹的帶權(quán)路徑長度。 （3）給出對上述哈夫曼樹中序遍歷得到的的序列 （4）一棵哈夫曼樹有n個非葉結(jié)點，構(gòu)造該樹共有多少個權(quán)重值？簡述理由？61.設有一個遞歸算法如下 試問計算x（x（8））時需要計算（）次x函數(shù)。A、8次B、9次C、16次D、18次62.對于List類型的線性表，編寫出下列算法。 從線性表中刪除具有給定值x的所有元素。63.假設以順序存儲結(jié)構(gòu)實現(xiàn)一個雙向棧，即在一維數(shù)組的存儲空間中存在著兩個棧，它們的棧底分別設在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧tws的三個操作：初始化inistack（tws）、入棧push（tws，i，x）和出棧pop（tws，i）的算法，其中i為0或1，用以分別指示設在數(shù)組兩端的兩個棧，并討論按過程（正/誤狀態(tài)變量可設為變參）或函數(shù)設計這些操作算法各有什么有缺點。64.已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：ACDBGIHFE和ABCDEFGHI。請畫出該二叉樹，并寫出它的前序遍歷的序列。65.連通圖66.已知一組元素的排序碼為： （46，74，16，53，14，26，40，38，86，65，27，34）利用快速排序的方法寫出每一層劃分后的排列結(jié)果，并畫出由此快速排序得到的二叉搜索樹。67.稀疏多項式采用的循環(huán)鏈表存儲結(jié)構(gòu)LinkedPoly定義為： 試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構(gòu)，編寫求其導函數(shù)的方法，要求利用原多項式中的結(jié)點空間存放其導函數(shù)多項式，同時釋放所有無用結(jié)點。68.散列函數(shù)69.設待排序的關鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關鍵字序列的狀態(tài)。二路歸并排序70.已知L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列。 a.刪除P結(jié)點的直接后繼結(jié)點的語句序列是（）。 b.刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是（）。 c.刪除P結(jié)點的語句序列是（）。 d.刪除首元結(jié)點的語句序列是（）。 e.刪除尾元結(jié)點的語句序列是（）。 （1）P=P->next； （2）P->next=P； （3）P->next=P->next->next； （4）P=P->next->next； （5）while（P!=NULL）P=P->next； （6）while（Q->next!=NULL）{P=Q；Q=Q->next；} （7）while（P->next!=Q）P=P->next； （8）while（P->next->next!=Q）P=P->next； （9）while（P->next->next!=NULL）P=P->next； （10）Q=P； （11）Q=P->next； （12）P=L； （13）L=L->next； （14）free（Q）；71.對于如圖所示的帶權(quán)無向圖，用圖示說明： 利用Prim算法從頂點a開始構(gòu)造最小生成樹的過程72.已知一個無向圖的鄰接表如圖所示，要求：畫出該無向圖73.假設以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結(jié)點，但不設頭指針。試設計相應的入隊和出隊的算法。74.用順序存儲結(jié)構(gòu)存儲串S，編寫算法刪除S中第i個字符開始的連續(xù)j個字符。75.已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點空間，并分析你的算法的時間復雜度。76.平衡因子77.試設計算法計算一棵給定二叉樹上所有結(jié)點數(shù)目。假設二叉樹的存儲結(jié)構(gòu)描述如下： 78.一棵樹有3度節(jié)點100個，2度節(jié)點200個，該樹有葉子節(jié)點多少個，該樹可以有多少個度為1的節(jié)點？79.已知一個稀疏矩陣如下圖所示： 給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示。80.以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點x的雙親。81.假設有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data，next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。82.已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時釋放被刪除結(jié)點空間。83.已知權(quán)值集合為{5，7，2，3，6，9}，要求給出哈夫曼樹，并計算帶權(quán)路徑長度WPL。84.單循環(huán)鏈表85.求解平方根的迭代函數(shù)定義如下： 其中，p是A的近似平方根，e是結(jié)果允許誤差。試寫出相應的遞歸算法，并消除遞歸。86.簡述二叉樹的四種遍歷方式及每一種遍歷方式中結(jié)點的訪問順序。87.希爾排序88.已知線性表A={a1、a2、……an}采用鏈接存儲結(jié)構(gòu)，其數(shù)據(jù)域由4個值域組成，假設依次為 定義單鏈表結(jié)點。89.設要將序列（Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X）中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是（）；初始步長為4的希爾（shell）排序一趟的結(jié)果是（）；歸并排序一趟掃描的結(jié)果是（）；快速排序一趟掃描的結(jié)果是（）；堆排序初始建堆的結(jié)果是（）。90.在程序設計中，可采用下列三種方法實現(xiàn)輸出和輸入： （1）通過scanf和printf語句； （2）通過函數(shù)的參數(shù)顯式傳遞； （3）通過全局變量隱式傳遞。 試討論這三種方法的優(yōu)缺點。91.算法設計的要求92.經(jīng)過下列棧的運算后EmptyStack（s）[判斷是否為空棧，是返回1，否返回0]的值是（）。 A、aB、bC、1D、093.簡述Floyd算法的作用和具體步驟。94.已知數(shù)據(jù)序列{12，02，16，30，28，10，17，20，06，18}，寫出希爾排序每一趟排序的結(jié)果。（設d=5、2、1）95.生成樹96.算法設計中的遞歸、窮舉、遞推和迭代等算法的基本思想是什么？97.已知如圖所示的無向網(wǎng)，請給出： ①鄰接矩陣； ②鄰接表；? ③最小生成樹。 98.已知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；99.結(jié)點的層次100.簡述順序文件的定義和分類。第1卷參考答案一.參考題庫1.正確答案:n；n（n+1）/2；O（n2）2.正確答案:C3.正確答案:C4.正確答案: 邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)定義了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的相互邏輯關系。數(shù)據(jù)的邏輯結(jié)構(gòu)包含下面兩個方面的信息： ①數(shù)據(jù)元素的信息； ②各數(shù)據(jù)元素之間的關系。 物理結(jié)構(gòu)：也叫儲存結(jié)構(gòu)，是指邏輯結(jié)構(gòu)的存儲表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式，包括結(jié)點的數(shù)據(jù)和結(jié)點間關系的存儲表示。 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的，一個操作算法的設計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采與的存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理時，針對不同問題，選擇合理的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)非常重要。5.正確答案: 6.正確答案: （1）樹形態(tài)： (2)帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=1297.正確答案: 8.正確答案:A9.正確答案: 散列函數(shù)：H（K）=k%m其中依題意得m=13 H（32）=32%13=6 H（5）=75%13=10 H（29）=29%13=3 H（63）=63%13=11 H（8）=48%13=9 H（94）=94%13=3（沖突） 設d0=H（K）=H（94）=3 d1=（d0+1）%m=（3+1）%13=4 H（25）=25%13=12 H（46）=46%13=7 H（18）=18%13=5 H（70）=70%13=5（沖突） 設d0=H（K）=H（70）=5 d1=（d0+1）%m=（5+1）%13=6（沖突） d2=（d1+1）%m=（6+1）%13=7（沖突） d3=（d2+1）%m=（7+1）%13=8 ASL=（8*1+1*2+1*4）/10=1.4 10.正確答案: 分析算法，第一次調(diào)用Reverse函數(shù)的時間復雜度為O（k），第二次調(diào)用Reverse函數(shù)的時間復雜度為O（n-k），第三次調(diào)用Reverse函數(shù)的時間復雜度為O（n），所以，總的時間復雜度為O（n）。11.正確答案: 12.正確答案: 13.正確答案: 遞歸算法： 遞歸算法的時間復雜度為O（2n），空間復雜度為O（n）；非遞歸算法的時間復雜度為O（n），空間復雜度為O（1）。14.正確答案:設立三個參數(shù)i、j、k，其中i以前的元素全部為紅色；j表示當前元素；k以后的元素全部為藍色。這樣，就可以根據(jù)j的顏色，把其交換到序列的前部或后部。 具體算法如下： 15.正確答案: 在二叉樹的存儲結(jié)構(gòu)中，必有N+1空域，利用這些空域存放某種遍歷的前驅(qū)和后繼，其中指向前驅(qū)和后繼的指針叫線索。16.正確答案: (1)是強連通圖 (2)鄰接矩陣和鄰接表為：17.正確答案: 一邊遍歷，一邊申請新結(jié)點，鏈接到head2序列中。18.正確答案: 棧和隊列都是插入和刪除操作的位置受限制的線性表。棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表19.正確答案: 向順序棧中推入一個元素。20.正確答案:July21.正確答案: 22.正確答案:23.正確答案: 一棵高度為h，并且含有2^h-1個結(jié)點的二叉樹稱為滿二叉樹。即每層都有最多的結(jié)點，葉子集中在二叉樹的最下一層且除葉子之外的每個結(jié)點度為2.24.正確答案:25.正確答案: 是一種受限線性表，是先進先出的線性表。26.正確答案: （1）順序查找： ASL=（1+2+3+…+25）/25=13 （2）二分查找： ASL=（1+2*2+4*3+8*4+10*5）/25=99/25=3.96 27.正確答案: 樹：只有最頂層的結(jié)點沒有前驅(qū)，其余結(jié)點都有且只有一個前驅(qū)；一個結(jié)點可以沒有后繼，也可以有一個或多個后繼。 二叉樹：一種特殊形態(tài)的樹，每個結(jié)點至多有兩個后繼。 滿二叉樹：一種特殊形態(tài)的二叉樹，除了最后一層的結(jié)點為葉子結(jié)點外其它結(jié)點都有左、右兩棵子樹的二叉樹。 完全二叉樹：一種特殊形態(tài)的二叉樹，其結(jié)點與相同深度的滿二叉樹中的結(jié)點編號完全一致，即對于深度為k的完全二叉樹，其前k-1層與深度為k的滿二叉樹的前k-1層完全一樣，只是在第k層上有可能缺少右邊若干個結(jié)點。28.正確答案: 29.正確答案:B30.正確答案: 31.正確答案:32.正確答案: 串是字符線性的有限集合。33.正確答案: 循環(huán)隊列的優(yōu)點有兩點：一是可以避免發(fā)生順序隊列的“假上溢”現(xiàn)象；二是充分利用隊列的存儲空間。 兩種判斷隊列是“空”還是“滿”的方法：一是約定少用一個元素空間；二是使用計數(shù)器size記錄當前隊列的實際長度。34.正確答案: 子孫結(jié)點以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。35.正確答案:36.正確答案:程序段的功能是利用棧T，將一個非空棧S中值等于m的元素全部刪去。37.正確答案:二叉排序樹如下圖所示，其平均查找長度=1+2×2+3×2+4×2=19/7 38.正確答案: 具有n個頂點的強連通圖至少有n條邊，這樣的圖是一個由n個頂點構(gòu)成的環(huán)。 強連通圖是相對于有向圖而言的。由于強連通圖要求圖中任何兩個頂點之間能夠相互連通，因此每個頂點至少要有一條以該頂點為弧頭的弧和一條以該頂點為弧尾的弧，每個頂點的入度和出度至少各為1，即頂點的度至少為2，這樣根據(jù)圖的頂點數(shù)、邊數(shù)以及各項點的度三者之間的關系計算可得：邊數(shù)=2×n/2=n。39.正確答案: 數(shù)據(jù)是描述客觀事物的符號，是能夠被計算機輸入，識別，處理的各種符號，是計算機化的信息。40.正確答案: 至少有14種。 ①全進之后再出情況，只有1種：4，3，2，1 ②進3個之后再出的情況，有3種，3，4，2，13，2，4，13，2，1，4 ③進2個之后再出的情況，有5種，2，4，3，12，3，4，12，1，3，42，1，4，32，1，3，4 ④進1個之后再出的情況，有5種，1，4，3，21，3，2，41，3，4，21，2，3，41，2，4，341.正確答案:42.正確答案: 它是插入排序的一種，又叫縮小增量排序，先按增量進行分組，組內(nèi)插入排序，然后每次縮短增量，再進行分組和組內(nèi)插入排序，直到增量為1時，進行最后一次排序止。43.正確答案: 44.正確答案:B45.正確答案:46.正確答案: 47.正確答案: 對二叉樹以某種次序進行遍歷并加上線索的過程叫做線索化。線索化了的二叉樹稱為線索二叉樹。48.正確答案: （1）棧中的數(shù)據(jù)元素逆置 （2）如果棧中存在元素e，將其從棧中清除49.正確答案: 50.正確答案:51.正確答案: 除余法：選取一個適當?shù)恼麛?shù)p（通常p為不大于哈希表存儲空間尺寸的最大素數(shù)），以元素的關鍵字值k除以p，得到的余數(shù)作為元素的存儲地址，即h（k）=k%p。 數(shù)字分析法：若元素的關鍵字由多位組成，且關鍵字的位數(shù)比存儲空間地址碼位數(shù)多、每一位的取值范圍及關鍵字的取值分布情況預先知道，則可以對元素關鍵字的各位進行分析，去掉分布較集中的位、保留分布較均勻的位。 折疊法：若元素的關鍵字由多位組成，且關鍵字的位數(shù)比存儲空間地址碼位數(shù)多，但關鍵字的取值分布情況未知，則可以用折疊法將關鍵字分為幾段（除了最后一段位數(shù)可以少一些，其他各段的位數(shù)均等于存儲空間地址碼位數(shù)），并將所有段的值做疊加求和運算，將疊加和的最高位進位舍去后取剩余部分作為元素的存儲地址。 平方取中法：對元素的關鍵字值求平方，并取中間幾位作為元素的存儲地址。52.正確答案: 53.正確答案: 54.正確答案: 三種經(jīng)典結(jié)構(gòu)：線性表、樹和圖。邏輯特征分別為： （1）線性表：一對一。有且僅有一個開始結(jié)點和一個終端結(jié)點，其余的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點和一個后繼結(jié)點。 （2）樹：一對多。有且僅有一個開始結(jié)點，可有若干個終端結(jié)點，其余的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點，可以有若干個后繼結(jié)點。 （3）圖：多對多?？捎腥舾蓚€開始結(jié)點和終端結(jié)點，其余的內(nèi)部結(jié)點可以有若干個前趨結(jié)點和若干個后繼結(jié)點。55.正確答案: 182621131721【37】8269774839555156.正確答案:57.正確答案:58.正確答案:D59.正確答案:60.正確答案: 61.正確答案:D62.正確答案: 63.正確答案: 64.正確答案:恢復的二叉樹為： 65.正確答案: 在無向圖中，如果對于圖中任意兩個頂點vi，vj∈V，vi和vj都是連通的，則稱該無向圖是連通圖。66.正確答案: 67.正確答案: 68.正確答案: 一個把查找表中的關鍵字映射成該關鍵字對應的地址的函數(shù)。69.正確答案:70.正確答案: a.（11）（3）（14） b.（10）（12）（8）（3）（14） c.（10）（12）（7）（3）（14） d.（12）（11）（3）（14） e.（9）（11）（3）（14）71.正確答案:72.正確答案:73.正確答案:出隊操作是在循環(huán)鏈表的頭部進行，相當于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結(jié)點之后插入一個結(jié)點。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。 入隊算法如下： 出隊算法如下： 74.正確答案:先判斷串S中要刪除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個位置。算法如下： 75.正確答案: 76.正確答案: 該結(jié)點的左子樹深度減去它的右子樹深度。77.正確答案:78.正確答案: N.0=n2+2n3+1 =200+2*100+1 =40179.正確答案: （（1，3，8），（2，1，4），（2，5，-7），（4，2，-3），（4，4，5），（4，6，6），（6，5，2），（7，2，1）） 80.正確答案:對二叉鏈表進行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親。具體算法如下： 81.正確答案:82.正確答案: voidDelete_list（Lnode*head，ElemTypex，ElemTypey） {Lnode*p，*q； if（!heaD.returnERROR； p=head；q=p； while（!p） {if（p->data>x）&&（p->dataif（p==heaD. {head=p->next；free（p）； p=head；q=p；} else {q->next=p->next；free（p）； p=q->next；} else {q=p；p=p->next；} } }83.正確答案: 樹形態(tài)： 帶權(quán)路徑長度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=7984.正確答案: 是單鏈表的另一種形式，它是一個首尾相接的鏈表，表中最后一個結(jié)點的指針域由null改為指向頭結(jié)點或線性表的第一個結(jié)點，整個鏈表形成了一個環(huán)。85.正確答案: 86.正確答案: 先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結(jié)點，再訪問根結(jié)點的左、右子樹；對于左、右子樹中的結(jié)點仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點，再訪問根結(jié)點的左、右子樹。 中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點左子樹，再訪問根結(jié)點，最后訪問右子樹；對于左、右子樹中的結(jié)點仍然是按照中序遍歷方式訪問。 后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點的左子樹，后訪問右子樹，最后訪問根結(jié)點；對于左、右子樹中的結(jié)點仍然是按照后序遍歷方式訪問。 逐層遍歷二叉樹：從第1層開始依次對每層中的結(jié)點按照從左至右的順序進行訪問。87.正確答案: 又稱縮小增量排序，先將整個記錄序列分割成若干子序列分別進行直接插入排序，待整個序列中記錄基本有序時，再對全體進行一次直接插入排序。