鄭州大學(xué)遠(yuǎn)程教育學(xué)院數(shù)據(jù)結(jié)構(gòu)試題及答案

鄭州大學(xué)現(xiàn)代遠(yuǎn)程教育《數(shù)據(jù)結(jié)構(gòu)》課程（本科）學(xué)習(xí)指導(dǎo)書郭純一編■課程內(nèi)容與基本要求“數(shù)據(jù)結(jié)構(gòu)"在計算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。本課程將主要介紹數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語、非數(shù)值計算中常用的數(shù)據(jù)結(jié)構(gòu)（線性表、棧和隊列、串、樹和圖）和基本技術(shù)（查找和排序方法）三大部分.本課程要求學(xué)生在掌握線性表、棧和隊列、串、樹和二叉樹、圖等基本數(shù)據(jù)類型的基礎(chǔ)上，會分析各種數(shù)據(jù)結(jié)構(gòu)的特性，會根據(jù)應(yīng)用需求為所涉及的數(shù)據(jù)合理選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)和存儲結(jié)構(gòu)，并能據(jù)此設(shè)計實現(xiàn)問題的算法;還應(yīng)初步掌握算法的時間和空間效率的分析方法.■課程學(xué)習(xí)進(jìn)度與指導(dǎo)早節(jié)課程內(nèi)容學(xué)時分配學(xué)習(xí)指導(dǎo)（均以課件學(xué)習(xí)為主）第一章緒論4學(xué)時重點掌握基本概念和時間復(fù)雜度的計算方法第二章*線性表10學(xué)時重點掌握順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)表示線性表的方法和操作的實現(xiàn)；結(jié)合具體例子理解編程實現(xiàn)一個問題的2種方法第三章棧和隊列8學(xué)時重點掌握棧和隊列的特點以及它們各自的存儲表示，尤其是順序棧和循環(huán)隊列的實現(xiàn)；結(jié)合具體例子理解棧和隊列的應(yīng)用第四章串2學(xué)時重點掌握串的術(shù)語、串操作結(jié)果和不同存儲結(jié)構(gòu)的特點第七章大樹和二叉樹10學(xué)時重點掌握二叉樹的定義、存儲、性質(zhì)、遍歷算法（遞歸）及應(yīng)用、線索化；掌握樹和森林與二叉樹的轉(zhuǎn)換以及Huffman樹和Huffman編碼的構(gòu)造方法第八章圖8學(xué)時重點掌握圖的術(shù)語、存儲、遍歷算法及應(yīng)用；掌握最小生成樹的2種構(gòu)造方法及特點、會求拓?fù)渑判蛐蛄泻蛦卧醋疃搪窂降诰耪?查找8學(xué)時重點掌握各種動態(tài)查找表的構(gòu)造過程、性能分析、插入/刪除方法；掌握靜態(tài)查找表的順序、折半和分塊查找及ASL求法第十章大排序8學(xué)時掌握關(guān)于排序的術(shù)語及分類方法；重點掌握插入排序、交換排序、選擇排序等內(nèi)排序方法及其性能分析方法夠滿州土典蜀昌強(qiáng)第_章緒論-、章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解數(shù)據(jù)抽象和信息隱蔽原則2、 掌握所有的基本概念和術(shù)語、掌握時間復(fù)雜度的計算方法、會用C語言描述抽象數(shù)據(jù)類型和算法；能夠熟練使用C語言編寫程序二、 本章重點、難點重點:基本概念和術(shù)語,C語言描述算法的方式，簡單程序的時間復(fù)雜度的求法。難點：時間復(fù)雜度的計算方法和原則。三、 章節(jié)練習(xí)（一）選擇題：具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是.A.圖B。樹C.集合D。棧計算機(jī)算法是指。A.計算方法和運(yùn)算結(jié)果 B。調(diào)度方法C.解決某一問題的有限運(yùn)算系列 D.排序方法線性結(jié)構(gòu)中，最后一個結(jié)點有個后繼結(jié)點。A.0B。1C.任意多算法分析的目的是.A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中輸入和輸出的關(guān)系C。分析算法的效率以求改進(jìn)D.分析算法的可讀性和可行性具有非線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是。A。圖B.線性表C。串D。棧算法具有5個特性：、、、輸入和輸出。A.穩(wěn)定性、確定性、可行性B。有窮性、確定性、可行性C。有窮性、安全性、可行性D。有窮性、確定性、可移植性設(shè)n為正整數(shù)。則下面程序段的時間復(fù)雜度為。i=1;k=0;while（i〈=n-1）{@k+=10*i;i++；}A。O(1)B.O(n)C.O(nlogn)D.O(n2)設(shè)n為正整數(shù)。則下面程序段的時間復(fù)雜度為。k=0；for(i=1；i<=n；i++){for(j=i;j〈=n;j++) @k++;}A.O(1)B.O(n)C.O(nlogn)D.O(n2)判斷題：在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)兩大類。()任何一個算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)則依賴于所采用的TOC\o"1-5"\h\z存儲結(jié)構(gòu)。 ()數(shù)據(jù)元素是數(shù)據(jù)的不可分割的最小單位。 ()算法分析的兩個主要方面是時間復(fù)雜度和空間復(fù)雜度。 ()第二章 線性表一、 章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解線性表的邏輯結(jié)構(gòu)特性、順序表和鏈表表示線性表的優(yōu)缺點、循環(huán)鏈表和雙向鏈表的特點。2、 掌握線性表的兩種存儲方式及其實現(xiàn)：熟練掌握順序表和鏈表的創(chuàng)建、插入元素、刪除元素以及定位等常用操作的實現(xiàn)算法并會求相應(yīng)算法的時間復(fù)雜度.二、 本章重點、難點重點:線性表的特點、兩種表示方式及它們的運(yùn)算實現(xiàn)，會求算法的時間復(fù)雜度.難點：單鏈表結(jié)構(gòu)、特點及其實現(xiàn)三、 章節(jié)練習(xí)選擇題：順序表是一種的存儲結(jié)構(gòu)，單鏈表是的存儲結(jié)構(gòu)。A。順序存取 B。隨機(jī)存取 C。索引存取順序表中第一個元素的起始存儲地址為100,每個元素的長度為4,則第五個夠滿州土典蜀昌強(qiáng)元素的起始地址是。A。105B.110C.116D。120非空循環(huán)單鏈表（head為頭指針）的尾結(jié)點（由指針p所指示）應(yīng)滿足。A。p一〉next==NULL；B.p==NULL;C。p->next==head;D.p==head；若在線性表的任何位置上插入元素的概率是相等的，那么在長度為n的順序表中插入一個元素時需平均移動個元素。A。n B.（n—1）/2 C.n/2 D.（n+1）/2在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的位置由指示，首元結(jié)點的存儲位置由指示,除首元結(jié)點外，其它任一元素結(jié)點的存儲位置由指示。A。頭指針B.頭結(jié)點的指針域的指針 C。前驅(qū)結(jié)點的指針域的指針單鏈表的頭指針為p,若有頭結(jié)點，則表空的判斷條件是;若不帶頭結(jié)點，則表空的判斷條件是。A。p==NULLB。p—>next==NULL C.p->next->next==NULL（二）判斷題：在單鏈表中插入或刪除元素時是以結(jié)點的指針變化來反映邏輯關(guān)系的變化，因TOC\o"1-5"\h\z此不需要移動元素。 （）順序表能夠以元素在計算機(jī)內(nèi)的物理位置的相鄰性來表示線性表中元素之間的邏輯關(guān)系. （）在不帶頭結(jié)點的非空單鏈表中，首元結(jié)點的存儲位置由頭指針指示，除首元結(jié)點外，其它任一元素結(jié)點的存儲位置由前驅(qū)結(jié)點的指針域的指針指示。 （）（三）問答題：若線性表要求以最快的速度存取而表中元素變動不大，則應(yīng)采取什么存儲結(jié)構(gòu)（順序或鏈?zhǔn)浇Y(jié)構(gòu)）？為什么？若線性表經(jīng)常做插入/刪除操作，則應(yīng)采取什么存儲結(jié)構(gòu)？為什么？在單鏈表中設(shè)置頭結(jié)點有什么作用？（四）算法題：設(shè)帶頭結(jié)點的單鏈表（L為頭指針）中的數(shù)據(jù)元素遞增有序。設(shè)計算法，將x插入到鏈表的適當(dāng)位置上，并仍保持該表的有序性。設(shè)順序表va中的數(shù)據(jù)元素遞增有序.設(shè)計算法，將x插入到順序表的適當(dāng)位置上，并仍保持該表的有序性。3。 設(shè)計算法，實現(xiàn)單鏈表的就地逆置，即利用原表的存儲空間將線性表（氣,氣，…，a）逆置為（a，a,…，a）.n nn-1 1第三章棧和隊列一、 章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解用棧和隊列解決實際問題的方法。2、 掌握棧和隊列的定義以及特性、它們的2種不同的存儲表示方法（特別是順序棧和循環(huán)隊列）以及各種常見操作（如入、出操作）在不同表示方式上的實現(xiàn)。二、 本章重點、難點重點：棧和隊列的定義、各種表示和實現(xiàn)方法，加深對線性結(jié)構(gòu)的理解難點:循環(huán)隊列的表示及為解決循環(huán)隊列隊空、隊滿判斷條件相同而使用的不同實現(xiàn)方式;能在具體問題中靈活運(yùn)用棧和隊列結(jié)構(gòu).三、 章節(jié)練習(xí)（一）選擇題：一個棧的入棧序列是a，b，c，d,e，則棧的不可能的輸出序列是。A。edcbaB.decbaC。dceab D。abcde棧和隊列的共同點是.A。都是后進(jìn)先出B.都是先進(jìn)先出C。都是只允許在端點處插入和刪除元素 D.無共同點一個隊列的入隊序列是{1，2,3,4），則隊列的輸出序列是.A.{4321}B.{1234}C。{1432）D。{3241}棧的入棧序列是1，2，…,n，輸出序列為p1,p2，???pn，若p1=n，則pi為A.iB.n—iC。n-i+1D。不確定隊列是限定在進(jìn)行插入，在進(jìn)行刪除的線性表。A.隊頭B。隊尾C。任意位置循環(huán)隊列中，設(shè)隊列元素依次存放在Q[0°.m]中,f、r分別指示隊頭元素位置和隊尾元素的下一個位置，約定存儲m個元素時為隊滿。則隊列空的判定方法是，隊列滿的判定方法是.A.f==rB。（f+1）%（m+1）==rC。（r+1）%（m+1）==fD.（r+1）%m==f（二）判斷題：若用戶無法估計所用隊列的最大長度，則最好采用鏈隊列.（）在鏈隊列上刪除隊頭元素時，只需修改頭結(jié)點中的指針，不必修改尾指針.（）棧是限定僅在棧頂進(jìn)行插入或刪除操作的線性表。 （）隊列是限定在隊尾插入元素，在隊頭刪除元素的線性表.（）（三）問答與算法題：對于一個棧，若輸入序列依次為{A,B,C},試給出所有可能的輸出序列。假設(shè)將循環(huán)隊列定義為：以整型域變量front和length分別指示循環(huán)隊列中隊頭元素位置和隊列中元素個數(shù)，指針elem指示存放隊列元素的連續(xù)空間的首地址，寫出相應(yīng)的入隊列和出隊列的算法.第四章串一、 章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解串的抽象數(shù)據(jù)類型的定義以及相關(guān)術(shù)語、理解串在文本編輯中的作用。2、 掌握字符串的定義及各種基本操作的運(yùn)算結(jié)果以及串的各種存儲表示的特點。二、 本章重點、難點重點：串的基本運(yùn)算、串的各種存儲表示和特點。繼續(xù)加深對線性結(jié)構(gòu)的理解難點：串的不同存儲結(jié)構(gòu)，區(qū)分它們和高級語言中串的存儲方式的不同。三、 章節(jié)練習(xí)（一）選擇題：設(shè)串s="IAMASTUDENT”，則其串長是。A。13B。14C。15D。16設(shè)s=”HEISAWORKER"，t=”WORKER”.則StrIndex（s,t,5）的返回值是A。4B。5C。6D.9E.10串是一種特殊的線性表，其特殊性體現(xiàn)在.

夠滿州土典蜀昌強(qiáng)A?？梢皂樞虼鎯。數(shù)據(jù)元素是一個字符C.可以鏈接存儲 D.數(shù)據(jù)元素可以是多個字符4。已知串s=”ABCDEFGH',則s的所有不同子串的個數(shù)為A.8B。9C。36D。375。設(shè)串s=”Iamateacher?！瑒ts的第8個字符起、長度為7的子串為A。"teacher."B。"teacher”C."ateacher"D."teacher"設(shè)串s="student.",t=“good設(shè)串s="student.",t=“good"，則執(zhí)行StrInsert(s,1,t)后，s為A."goodstudento B。"goodstudent"C。"goodstudent" D。"goodteacher"（二）判斷題：空串和空格串是相同的. （）2o如果兩個串含有相同的字符，則它們是相同的。（）3o串的基本操作和線性表的一樣，都是以“單個元素”作為操作對象的。（）在串的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，結(jié)點大小與存儲密度之間沒有關(guān)系。 （）第七章樹和二叉樹第七章樹和二叉樹一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解樹、二叉樹和森林的概念，理解線索化二叉樹的特性、創(chuàng)建方法及在線索二叉樹上尋找某結(jié)點的前驅(qū)和后繼的方法;理解樹與森林的存儲方法.2、 掌握二叉樹的性質(zhì)及表示;掌握二叉樹的各種遍歷方法（尤其是遞歸形式的）以及遍歷在實際問題中的應(yīng)用；掌握樹及森林與二叉樹的轉(zhuǎn)換及遍歷方式的對應(yīng)；掌握Huffman樹的構(gòu)造方法以及構(gòu)造Huffman編碼的方法。二、 本章重點、難點重點:二叉樹的性質(zhì)（及證明）、存儲結(jié)構(gòu)及各種遍歷算法，二叉樹的線索化過程，樹和森林與二叉樹的轉(zhuǎn)換關(guān)系，Huffman樹及Huffman編碼的構(gòu)造方法難點:各種遍歷算法的遞歸實現(xiàn)以及在具體問題中能靈活運(yùn)用遍歷思想解題三、 章節(jié)練習(xí)（一）選擇題：下列關(guān)于二叉樹的說法中，正確的有。Ao二叉樹的度為2B.二叉樹的度可以小于2C。二叉樹中至少有一個結(jié)點的度為2 D.二叉樹中任一個結(jié)點的度都為2任何一棵二叉樹的葉子結(jié)點在先、中、后序遍歷序列中的相對次序。A。不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對下面幾個符號串編碼集合中，不是前綴編碼的是。A。{0,10,110,1111}B.{11,10,001,101,0001）C。{00,010，0110,1000）D.{b,c，aa,ac,aba,abb,abc}二叉樹按某種順序線索化后，任意結(jié)點均有指向其前驅(qū)和后繼的線索，這種說法。A。正確B。不正確C.無法確定（二） 判斷題：TOC\o"1-5"\h\z1。 哈夫曼樹是帶權(quán)葉子數(shù)目固定的二叉樹中帶權(quán)路徑長度最小的. （）2。 根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹有5種不同的形態(tài)。 （）3。 深度為k的完全二叉樹至少有2k—1個結(jié)點，至多有2k—1個結(jié)點。 （）4。 具有n個結(jié)點的滿二叉樹，其葉子結(jié)點個數(shù)為1個. （）25。 在哈夫曼樹中，通常權(quán)值較大的結(jié)點離根較遠(yuǎn)。 （）（三） 問答題：下圖所示森林轉(zhuǎn)化為相應(yīng)的二叉樹，并在其上標(biāo)出中序全線索.證明：深度為k的二叉樹上至多有2k-1個結(jié)點（kN1）。證明：任何一棵滿二叉樹中的分支數(shù)B滿足B=2（n0—1），其中n。為葉子結(jié)點個數(shù)。以數(shù)據(jù)集{15，3,14，2，6，9，16，17}為葉子的權(quán)值構(gòu)造Huffman樹，畫出此樹并計算其帶權(quán)路徑長度。（四）算法題：1。 假設(shè)二叉排序樹（t為指向根結(jié)點的指針）中各元素值均不相同，設(shè)計一個遞歸算法按遞增順序輸出樹上各元素值。編寫遞歸算法，交換二叉鏈表存儲的二叉樹中每個結(jié)點的左、右子樹.3。 編寫遞歸算法，求以二叉鏈表存儲的二叉樹的深度。設(shè)計遞歸算法計算以二叉鏈表存儲的二叉樹的葉子結(jié)點數(shù)目。第八章圖一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、 理解圖的基本概念和術(shù)語.2、 掌握圖的鄰接矩陣和鄰接表2種表示方法;掌握圖的兩種遍歷算法及其求解連通性問題的方法；掌握用Prim算法和Kruskal算法構(gòu)造最小生成樹的過程和性能分析；掌握AOV網(wǎng)的拓?fù)渑判蚍椒ǎú灰笏惴ǎ?，掌握用Dijkstra方法求解單源最短路徑問題的方法（不要求算法）。二、 本章重點、難點重點：圖的數(shù)組表示法和鄰接表表示法存儲結(jié)構(gòu)以及圖的兩種遍歷方式，求最小生成樹的兩種方法,AOV網(wǎng)的拓?fù)渑判蚍椒ǎ莆諉卧醋疃搪窂降那蠓y點：圖的兩種遍歷算法的實現(xiàn)以及在圖的連通性問題中的應(yīng)用三、 章節(jié)練習(xí)（一）選擇題：1.4個頂點的無向完全圖有 __條邊.A。6 B.122.無向圖的鄰接矩陣是一個 C。16 D.20_。A.對稱矩陣 B。零矩陣C。對角矩陣 D。上三角矩陣3.圖的廣度優(yōu)先遍歷算法類似于二叉樹的 ,圖的深度優(yōu)先遍歷算法類似于二叉樹的。A。先序遍歷 B.中序遍歷C。后序遍歷D.層序遍歷4。對，用Prim算法求最小生成樹較為合適，而Kruskal算法適于構(gòu)造圖的最小生成樹.A。完全圖B。連通圖C.稀疏圖D.稠密圖ea拽四噩卷敏Le—■齒二i1—1■Mw—Liwi— 5。對于含n個頂點、e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹的時間復(fù)雜度，用Kruskal算法構(gòu)造最小生成樹的時間復(fù)雜度為A。O（n）B.O（n2） C。O（e）D.O（eloge）F.O（e2）（二）判斷題：1。 若從無向圖的一個頂點出發(fā)進(jìn)行廣度優(yōu)先遍歷可訪問到圖中所有頂點，則該TOC\o"1-5"\h\z圖一定是連通圖。 （）若從無向圖的一個頂點出發(fā)進(jìn)行深度優(yōu)先遍歷可訪問到圖中所有頂點，則該圖一定是連通圖。 （）3。 任何有向圖的頂點都可以排成拓?fù)溆行蛐蛄?，而且拓?fù)湫蛄胁晃ㄒ弧＃ǎ?。 有n個頂點和n-1條邊的無向圖一定是生成樹。 （）一棵有n個頂點的生成樹有且僅有n—1條邊。 （）連通分量是無向圖的極大連通子圖，而生成樹是無向圖的極小連通子圖。（）（三）問答及算法題：一010一1。 一個圖的鄰接矩陣G.arcs=i01，該圖有多少個頂點?如果是有011向圖，該圖共有多少條弓瓜？如果是無向圖，該圖共有多少條邊？TOC\o"1-5"\h\z2。 已知如右圖所示的有向圖，寫出該圖的： -> 誦（1）鄰接矩陣（2）一個可能的拓?fù)溆行蛐蛄校?） /寫出從1出發(fā)的深度優(yōu)先遍歷序列（4）寫出從5出①發(fā)的廣度優(yōu)先遍歷序列。3。 假設(shè)有5項活動C1?C5，每項活動要求的前驅(qū)活動如下：C1：無；C2：C1,C3;C3：C1； C4：C3,C5 C5：C2;試根據(jù)上述關(guān)系，畫出相應(yīng)的有向圖，再寫出一個拓?fù)渑判蛐蛄小?。 基于圖的深度優(yōu)先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數(shù)。第九章查找1、 理解各種查找表的定義、各種查找方法的思想以及構(gòu)造查找表所依據(jù)的原則.2、 掌握線性表表示的靜態(tài)查找表的順序查找和折半查找算法及其性能分析方法;掌握二叉排序樹的創(chuàng)建、查找、插入、刪除算法及其性能分析方法；掌握AVL樹的平衡化旋轉(zhuǎn)方法及其性能分析;掌握B一樹的插入和刪除時結(jié)點的分裂和合并方法;掌握Hash法的查找、構(gòu)造方法平均查找長度的計算方法。二、 本章重點、難點重點:各種樹結(jié)構(gòu)表示的動態(tài)查找表和Hash表的構(gòu)造方法難點：二叉排序樹的刪除、AVL樹的旋轉(zhuǎn)處理、B一樹的插入和刪除、Hash法的構(gòu)造以及各種查找表的平均查找長度的計算方法三、 章節(jié)練習(xí)(一)選擇題：二叉排序樹可得到一個關(guān)鍵字的有序序列。A.先序遍歷B.中序遍歷C.后序遍歷 D。層序遍歷用鏈地址法處理沖突構(gòu)造的散列表中，每個地址單元所鏈接的同義詞表中結(jié)點的相同。A。關(guān)鍵字B.元素值C。散列地址 D。含義利用折半查找方法在長度為n的有序表中查找一個元素的平均查找長度是。A。O(n2) B.O(nlogn)C.O(n)D.O(logn)散列表的裝填因子越大，則發(fā)生沖突的可能性就.A。越小 B。越大 C。不確定線性表中共有256個元素，采用分塊查找，若查找每個元素的概率相等，用順序查找確定結(jié)點所在的塊，每塊有個元素時查找效率最佳。A。16B。20C。25D.256用折半查找對長度為7的有序表進(jìn)行查找，則等概率下查找成功時的平均查找長度為。A.15/7B.17/7C。18/7D。19/7有序表(1，32,41，45，62，75,77,82,95，100)，使用折半查找關(guān)鍵字為95的元素時，需要經(jīng)過次比較后才能查找成功。A。2B。3C。4Do5（二）判斷題：TOC\o"1-5"\h\z折半查找和二叉排序樹的查找時間性能一樣。 （）2o在任意一棵非空的二叉排序樹中，刪除某結(jié)點后又將其插入，則所得的二叉排序樹與刪除前的二叉排序樹形態(tài)相同. （）根據(jù)B一樹的定義，在9階B-樹中，除根以外的任何一個非葉子結(jié)點中的關(guān)鍵字?jǐn)?shù)目均在5?9之間。 （）4。 折半查找時，要求線性表必須是有序的且以順序結(jié)構(gòu)存儲。 （）（三）問答題：1o設(shè)有一組關(guān)鍵字序列｛19,1,23,14,55,20,84,27,68,11,40｝,（1） 按表中元素順序構(gòu)造一棵二叉排序樹，畫出這棵樹，并求其在等概率情況下查找成功時的平均查找長度。（2） 從空樹開始，按表中元素順序構(gòu)造一棵2_3樹（3階B_樹），若此后再刪除55,84,畫出每一步執(zhí)行后2_3樹的狀態(tài).2o設(shè)散列函數(shù)H（key）=keyMOD7,用線性探測再散列法解決沖突。對關(guān)鍵字序列｛13,28,72,5,16,8,7,11｝在地址空間為0-10的散列區(qū)中建散列表，畫出此表，并求等概率情況下查找成功時的平均查找長度。3o關(guān)鍵字序列：13,28,72,5,16,18,7,11,24,h（key）=keymod11,表長為11,用線性探測再散列處理沖突，試填寫下表并計算每個關(guān)鍵字的比較次數(shù)和等概率情況下查找成功時的平均查找長度.012 3 4 5 6 7 8 910哈希表 比較次數(shù)ASL=在地址空間為0—16的散列區(qū)中，對以下關(guān)鍵字序列（Jan,Feb,Mar,Apr,May，June,July,Aug,Sep,Oct,Nov,Dec）按鏈地址法處理沖突構(gòu)造散列表，設(shè)散列函數(shù)H（x）=i/2,其中i為關(guān)鍵字中第一個字母在字母表中的序號。畫出該散列表并求在等概率情況下查找成功時的平均查找長度。第十章排序

1、 理解排序相關(guān)的定義以及排序方法的各種分類，理解各種排序方法的基本思想和依據(jù)原則。2、 掌握內(nèi)部排序的基本概念和性能分析方法；掌握插入排序、交換排序、選擇排序等內(nèi)排序的方法及其性能分析方法。二、 本章重點、難點重點：各類內(nèi)部排序方法所依據(jù)的原則、特點及典型算法.難點：希爾排序、快速排序、堆排序三、 章節(jié)練習(xí)選擇題：1。 下列方法中,是穩(wěn)定的排序方法.A.堆排序B。希爾排序C.快速排序D。折半插入排序2。 設(shè)有1000個無序的元素，希望用最快的速度選出其中前20個最大的元素,最好用排序方法。A素,最好用排序方法。A。冒泡排序B.快速排序下列序列中，是堆.A。{12,35,20,60,40,30}C.{1,5,6,24,7,3,4}C。堆排序D。希爾排序B。 {100,85,120,38,10,9,36)D.{38,24,15,20,30,46}在待排序的元素序列基本有序時，效率最高的排序方法是.人.插入排序B.選擇排序C.快速排序D.歸并排序在下列排序方法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是。A.堆排序B。起泡排序C.快速排序D。直接插入排序6。 對序列{22,86,19,49,12,30,65,35,18)進(jìn)行一趟排序后得到的結(jié)果為{18,12,19,22,49,30,65,35,86},則其使用的排序方法為.A。插入排序 B.選擇排序C?？焖倥判駾。起泡排序7。 下列方法中，算法的時間復(fù)雜度為O(n2)。A。堆排序B.希爾排序 C。快速排序 D。直接插入排序8。 對n個記錄的序列進(jìn)行堆排序，最壞情況下的時間復(fù)雜度為。A。O(logn)B.O(nlogn)C。O(n) D.O(n2)量頊祖*罰*蜀（二） 判斷題：快速排序的速度在所有排序方法中是最快的，而且所需的附加空間也最少。（）TOC\o"1-5"\h\z對一個堆按層次遍歷，不一定能得到一個有序序列. （）由于希爾排序的最后一趟與直接插入排序過程相同，所以前者一定比后者花費(fèi)的時間多。 （）快速排序算法在待排序數(shù)據(jù)有序時最不利于發(fā)揮其長處。 （）（三） 問答題：在快速排序過程中，通常取序列中的第1個記錄作為樞軸，以它為“分界線〃重排其余記錄。但當(dāng)初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼懟癁槠鹋菖判?，為改進(jìn)之，應(yīng)如何選取樞軸記錄？判斷以下序列是否是堆，若不是,把它調(diào)整為堆（要求記錄交換次數(shù)最少），寫出調(diào)整后的序列。1） {5，26，20,60,80，35，53，70}2） {26,33,35，29，19，12,22}已知關(guān)鍵字序列{70,83，100，65，10，9,7，32},寫出直接插入排序和快速排序每一趟結(jié)束時的關(guān)鍵字狀態(tài)。設(shè)關(guān)鍵字集合為{10，2，14,8，12,13}，（1）寫出用希爾排序方法對序列排序時每一趟結(jié)束時的關(guān)鍵字狀態(tài)。（2）用堆排序方法對其從小到大排序，畫出堆排序的初態(tài)、建堆和排序過程中重建堆的過程?？荚嚹M題客觀題部分一、單項選擇題：（每空2分，共20分）單鏈表是線性表的一種的存儲結(jié)構(gòu)。A。順序存取 B。隨機(jī)存取C。索引存取棧和隊列的共同點是。A.都是后進(jìn)先出 B。都是先進(jìn)先出C。都是只允許在端點處插入和刪除元素 D。無共同點最*4仕苦囂罰鑫設(shè)s="HEISAWORKER",t=”WORKER"o則index（s,t,5）的返回值是.A。4B。5C.6D。9E。10串是一種特殊的線性表，其特殊性體現(xiàn)在。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C?？梢枣溄哟鎯?D。數(shù)據(jù)元素可以是多個字符樹最適合用來表示。A.有序數(shù)據(jù)元素B。無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無關(guān)聯(lián)的數(shù)據(jù)4個頂點的無向完全圖有條邊。A.6B。12C.16D。20散列表的裝填因子越大，則發(fā)生沖突的可能性就。A.越小 B.越大 C。不確定在長度為n的有序表中折半查找一個元素的平均查找長度是。A。O（n2） B.O（nlogn） C.O（n） D.O（logn）下列方法中，是不穩(wěn)定的排序方法.A.折半插入排序 B.直接插入排序 C。冒泡排序D。堆排序二叉排序樹可得到一個關(guān)鍵字的有序序列。A.先序遍歷 B。中序遍歷 C.后序遍歷 D。層序遍歷二、是非題：（每題1分，共10分）（說明：正確的選“A〃,錯誤選“B”）TOC\o"1-5"\h\z線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。 （）空串和空格串是相同的。 （）圖結(jié)構(gòu)中，每個結(jié)點的前驅(qū)和后續(xù)都可以有任意多個。 （）快速排序算法在待排序數(shù)據(jù)有序時最不利于發(fā)揮其長處。（）連通網(wǎng)的最小生成樹是唯一的。 （）棧是FIFO的線性表。 （）由二叉樹的先序和后序遍歷序列不能唯一確定這棵二叉樹。（）若從無向圖的一個頂點出發(fā)進(jìn)行廣度優(yōu)先遍歷可訪問到圖中的所有頂點，則該圖一定是連通圖。 （）

折半查找方法要求查找表必須是關(guān)鍵字的有序表，但是對存儲結(jié)構(gòu)沒有限制。 （）在一棵非空二叉樹的中序遍歷序列中，根結(jié)點的右邊只有其右子樹上的所有結(jié)點。 （）主觀題部分一、簡答題：（50分）1。若線性表要求以最快的速度存取而表中元素變動不大，則應(yīng)采取什么存儲結(jié)構(gòu)（順序或鏈?zhǔn)浇Y(jié)構(gòu)）？為什么？（10分）將下圖所示森林轉(zhuǎn)化為二叉樹并在其上標(biāo)出中序全線索。（10分）(10(10已知如右圖所示的有向圖，寫出該圖的：（1）鄰接矩陣（2）一個可能的拓?fù)溆行蛐蛄小７郑┰O(shè)散列函數(shù)H（key）=keyMOD7,用線性探測再散列法解決沖突。對關(guān)鍵字序列｛13,28,72,5,16,8,7,9,11,29｝在地址空間為0—10的散列區(qū)中建散列表，畫出此表，并求等概率情況下查找成功時的平均查找長度.（10分）對于序列｛26,33,35,29,19,12,22｝,（1）判斷它是否是堆，若是，寫出其是大頂堆還是小頂堆；若不是，把它調(diào)整為堆，寫出調(diào)整的過程和調(diào)整后的序列. （5分）（2）寫出對該序列進(jìn)行直接插入排序每一趟結(jié)束時的關(guān)鍵字狀態(tài)。（5分）二、算法設(shè)計題：（20分）1、 編寫遞歸算法，計算二叉鏈表存儲的二叉樹的結(jié)點數(shù)目.（10分）2、 基于圖的深度優(yōu)先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數(shù)。 （10分）附：答案或答案要點第一章章節(jié)練習(xí)答案（一）選擇題：1.D2.C3.A（二）判斷題：1.x4.C5.2." 3.Ax6.B7.4."B 8.D第二章章節(jié)練習(xí)答案（一）選擇題：1.B，A 2.C3.C4.C5.A,B,C6.B，A（二）判斷題：1."2."3."（三） 1可答題：應(yīng)采用順序結(jié)構(gòu)。因為順序表是隨機(jī)存取的存儲結(jié)構(gòu)，在順序表中存取任何元素所花的時間都一樣。而鏈表是順序存取的存儲結(jié)構(gòu)。應(yīng)采用鏈?zhǔn)浇Y(jié)構(gòu).因為在鏈表中是以結(jié)點的指針變化來反映邏輯關(guān)系的變化,因此不需要移動元素，效率高.頭結(jié)點在位置上可視為首元結(jié)點的前驅(qū)，則做插入/輸出操作時，i=1（即插入或刪除的位置是1）時不需要做特別處理，否則i=1時需要修改頭指針.（四） 算法題：statusinsert_L（LinkListL，ElemTypex）{/*帶頭結(jié)點*/LinkListp，s;for（p=L;p-＞next&&p一＞next一＞data〈x；p=p-〉next）；s=（LinkList）malloc（sizeof（LNode））；if（!s） returnOVERFLOW；s一＞data=x； s一＞next=p一＞next;p-＞next=s；returnOK;}statusinsert_Sq（SqList*va,ElemTypex）{inti;夠滿州土典蜀昌強(qiáng)if(va->length==va-〉listsize)exitOVERFLOW;for(i=va—〉length-1;i>=0&&va—〉elem[i]>x;-—i)va->elem[i+1]=va->elem[i];va一〉elem[i+1]=x;va-〉length++;returnOK;}voidreverse(LinkListL){/*帶頭結(jié)點*/LinkListp;p=L—〉next;L—>next=NULL；for(;p;p=p->next){q=p-〉next；p—>next=L—>next；L->next=p;}}第三章章節(jié)練習(xí)答案選擇題：1。C 2。C3。B4。C5。B,A 6.A,C判斷題：1." 2.X3." 4."問答與算法題：所有可能的輸出序列有:{ABC}、{ACB}、{BAC}、{BCA}、{CBA}算法：#defineMAXQSIZE100typedefstruct{ElemType*elem;intfront;intlength;}CycQueue;

statusEnQueue(CycQueue*Q,ElemTypee)if(Q—〉length==MAXQSIZE)returnERROR;Q->elem[(Q-〉front+Q—>length)%MAXQSIZE]=e;Q—>length++;returnOK;}statusDeQueue(CycQueue*Q,ElemType大e){if(Q—〉length==0)returnERROR;*e=Q->elem[Q—〉front];Q->length ;returnOK；}第四章章節(jié)練習(xí)答案（一）選擇題：1。（一）選擇題：1。B2.D3.B4.D5。B6。A(二)判斷題：1.X2.(二)判斷題：1.X2.X3.X4°X第七章章節(jié)練習(xí)答案3.B4.B4。V5。（一） 選擇題3.B4.B4。V5。（一） 選擇題：1。B 2。A（二） 判斷題：1.V 2。"（三） 問答題：1.HULL證明：由于深度為k的二叉樹的最大結(jié)點數(shù)為二叉樹上每之和，而二叉樹上第i層的最大結(jié)點數(shù)為2i—證明：由于深度為k的二叉樹的最大結(jié)點數(shù)為二叉樹上每之和，而二叉樹上第i層的最大結(jié)點數(shù)為2i—。則層的最大結(jié)點數(shù)E（第i層的最大結(jié)點數(shù)）=￡2「i=2k-13。證明:設(shè)n0為葉子結(jié)點個數(shù),n2為度為2的結(jié)點個數(shù)，則由二叉樹的性質(zhì)2可知：n2=n0—1又：滿二叉樹中只有度為2的結(jié)點和葉子結(jié)點，所以滿二叉樹中的結(jié)點總數(shù)n=n2+n0=2/—1又：二叉樹中的分支數(shù)B=n—1所以：B=2n0—1—1=2(n0—1)4.wpl=(16+17)*2+(9+14+15)*3+6大4+(2+3)大5=229算法題：voidoutput(BiTreet){if(t){output(t-〉lchild)；printf(t-〉data);output(t-〉rchild)；量頊祖*罰*蜀}}2。 voidexchange(BiTreet){BiTreetemp；if(t){temp=t-〉lchild;t—>lchild=t->rchild;t->rchild=temp；exchange(t—>lchild);exchange(t—〉rchild)；}}3。 intdepth(BiTreet){intl,r；if(!t)return0;l=depth(t-〉lchild)；r=depth(t—>rchild);return(l〉=r?l：r)+1；}4。 voidleaf(BiTreet){if(!t)return0;if(!t—>lchild&&!t->rchild)return1；returnleaf(t—>lchild)+leaf(t—〉rchild)；}第八章章節(jié)練習(xí)答案選擇題：1°A 2°A 3。D,A4.D,C5.B,D判斷題：1.V2." 3.X4.X5." 6."(三)問答及算法題：

夠項吼JI巽蜀（注意4一定是最后一個,2一定在1和5后）（注意4一定是最后一個,2一定在1和5后）「010000-0010002。（1）鄰接矩陣：000100000000010001_000100_該圖共有3條邊.（2）可能的拓?fù)湫蛄袨?156234(3)123456(4)(4)562431{for(i=0;ivGvexnum； i++)visited[i]=false;sum=0；for(i=0;ivG。vexnum；i++)if(!visited[i]){sum++； dfs(G,i)；}returnsum;}voiddfs(AlGraphG,inti){visited[i]=true;for(p=Gvertices[i].firstarc;p； p=p->nextarc){k=p一>adjvex;?l■M11ISS5OLrww^fatal■'-Iif(if(!visited[k])dfs(G,k);第九章章節(jié)練習(xí)答案（一）選擇題：1.B2°C3.D4.B5.A6.B7。B（二） 判斷題：1°X 2.X3。X 4。"（三） 問答題：1。(1)ASL=(1+2大2+3*3+3*4+2*5)/11=36/11⑵2_3樹:((3)刪除55:刪除84：01234567S9102887216751311

2.ASL=(1+1+1+2+5+1+1+411125114/8=16/8=23。3、012345678910哈希表1113245287216187比較次數(shù)112112434ASL=(1+1+2+1+1+2+4+3+4)/9=19/9用鏈地址法處理沖突：(注意鏈表的有序性)口12 3 45E7 89 1011121314ISMIA| |A| ] ：A]AAAAAAaASL=（7*1+4*2+1*3）/12=18/12第十章章節(jié)練習(xí)答案（一） 選擇題：1.D 2.C 3°A 4.A 5.D 6.C 7°D8.B（二） 判斷題：1°X 2.V3.X4.V（三） 問答題：應(yīng)依據(jù)“三者取中"的原則，比較第一個、最后一個和中間位置處記錄的關(guān)鍵字，取關(guān)鍵字居中值的記錄作為樞軸記錄。第一個序列是堆第二個序列不是堆。調(diào)整為堆后的序列為{35,33,26,29,19,12,22}初始序列:70,83,100,65,10,9,7,32直接插入排序每一趟結(jié)束時的關(guān)鍵字狀態(tài)：第一趟：（70,83）,100,65,10,9,7,32第二趟:（70,83,100）,65,10,9,7,32第三趟：（65,70,83,100）,10,9,7,32夠,眼決典蜀昌強(qiáng)第四趟：(10,65,