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

1、鄭州大學(xué)現(xiàn)代遠(yuǎn)程教育數(shù)據(jù)結(jié)構(gòu)課程（本科）學(xué)習(xí)指導(dǎo)書(shū)郭純一編嗡&W*答融抬普，L<inm4Mre4dLCht.Hwhai1,th°課程內(nèi)容與基本要求“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門(mén)綜合性的專(zhuān)業(yè)基礎(chǔ)課。本課程將主要介紹數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)、非數(shù)值計(jì)算中常用的數(shù)據(jù)結(jié)構(gòu)（線(xiàn)性表、棧和隊(duì)列、用、樹(shù)和圖）和基本技術(shù)（查找和排序方法）三大部分。本課程要求學(xué)生在掌握線(xiàn)性表、棧和隊(duì)列、用、樹(shù)和二叉樹(shù)、圖等基本數(shù)據(jù)類(lèi)型的基礎(chǔ)上，會(huì)分析各種數(shù)據(jù)結(jié)構(gòu)的特性，會(huì)根據(jù)應(yīng)用需求為所涉及的數(shù)據(jù)合理選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，并能據(jù)此設(shè)計(jì)實(shí)現(xiàn)問(wèn)題的算法；還應(yīng)初步掌握算法的時(shí)間和空間效率的分析方法。

2、課程學(xué)習(xí)進(jìn)度與指導(dǎo)早1課程內(nèi)容學(xué)時(shí)分配學(xué)習(xí)指導(dǎo)（均以課件學(xué)習(xí)為主）代'K弟一早緒論4學(xué)時(shí)重點(diǎn)掌握基本概念和時(shí)間復(fù)雜度的計(jì)算方法代'K"*弟一早線(xiàn)性表10學(xué)時(shí)重點(diǎn)掌握順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)表示線(xiàn)性表的方法和操作的實(shí)現(xiàn)；結(jié)合具體例子理解編程實(shí)現(xiàn)一個(gè)問(wèn)題的2種方法第三章棧和隊(duì)列8學(xué)時(shí)重點(diǎn)掌握棧和隊(duì)列的特點(diǎn)以及它們各自的存儲(chǔ)表示，尤其是順序棧和循環(huán)隊(duì)列的實(shí)現(xiàn)；結(jié)合具體例子理解棧和隊(duì)列的應(yīng)用第四章用2學(xué)時(shí)重點(diǎn)掌握用的術(shù)語(yǔ)、用操作結(jié)果和/、同存儲(chǔ)結(jié)構(gòu)的特點(diǎn)第七章*樹(shù)和二叉樹(shù)10學(xué)時(shí)重點(diǎn)掌握二叉樹(shù)的定義、存儲(chǔ)、性質(zhì)、遍歷算法（遞歸）及應(yīng)用、線(xiàn)索化；掌握樹(shù)和森林與一叉樹(shù)的轉(zhuǎn)換以及Huff

3、man樹(shù)和Huffman編碼的構(gòu)造方法第八章圖8學(xué)時(shí)重點(diǎn)掌握?qǐng)D的術(shù)語(yǔ)、存儲(chǔ)、遍歷算法及應(yīng)用；掌握最小生成樹(shù)的2種構(gòu)造方法及特點(diǎn)、會(huì)求拓?fù)渑判蛐蛄泻蛦卧醋疃搪窂降诰耪?查找8學(xué)時(shí)重點(diǎn)掌握各種動(dòng)態(tài)查找表的構(gòu)造過(guò)程、性能分析、插入/刪除方法；掌握靜態(tài)查找表的順序、折半和分塊查找及ASL求法第十章*排序8學(xué)時(shí)掌握關(guān)于排序的術(shù)語(yǔ)及分類(lèi)方法；重點(diǎn)掌握插入排序、交換排序、選擇排序等對(duì)F序方法及其性能分析方法褥料學(xué)岷格管理中心第一章緒論一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解數(shù)據(jù)抽象和信息隱蔽原則2、掌握所有的基本概念和術(shù)語(yǔ)、掌握時(shí)間復(fù)雜度的計(jì)算方法、會(huì)用C語(yǔ)言描述抽象數(shù)據(jù)類(lèi)型和算法；能夠熟練使用C語(yǔ)言編寫(xiě)程序二、本章

4、重點(diǎn)、難點(diǎn)重點(diǎn)：基本概念和術(shù)語(yǔ)，C語(yǔ)言描述算法的方式，簡(jiǎn)單程序的時(shí)間復(fù)雜度的求法。難點(diǎn)：時(shí)間復(fù)雜度的計(jì)算方法和原則。三、章節(jié)練習(xí)（一）選擇題：1 .具有線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是A.圖B.樹(shù)C.集合D.棧2 .計(jì)算機(jī)算法是指。A.計(jì)算方法和運(yùn)算結(jié)果B.調(diào)度方法C.解決某一問(wèn)題的有限運(yùn)算系列D.排序方法3 .線(xiàn)性結(jié)構(gòu)中，最后一個(gè)結(jié)點(diǎn)有個(gè)后繼結(jié)點(diǎn)。A.0B.1C.任意多4 .算法分析的目的是。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的可讀性和可行性5 .具有非線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是oA.圖B.線(xiàn)性表C.申D.棧6 .算法具有5個(gè)特性：?輸入和輸出。A.穩(wěn)

5、定性、確定性、可行性B.有窮性、確定性、可行性C.有窮性、安全性、可行性D.有窮性、確定性、可移植性7 .設(shè)n為正整數(shù)。則下面程序段的時(shí)間復(fù)雜度為。i=1;k=0;while(i<=n-1)k+=10*i;恒醒性華岷網(wǎng)結(jié)理中心i+；)A.O(1)B.O(n)C.O(nlogn)D.O(n2)8 .設(shè)n為正整數(shù)。則下面程序段的時(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)(二)判斷題：1 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)兩大類(lèi)。()2 .任何一個(gè)

6、算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)則依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。()3 .數(shù)據(jù)元素是數(shù)據(jù)的不可分割的最小單位。()4 .算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度。()第二章線(xiàn)性表一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解線(xiàn)性表的邏輯結(jié)構(gòu)特性、順序表和鏈表表示線(xiàn)性表的優(yōu)缺點(diǎn)、循環(huán)鏈表和雙向鏈表的特點(diǎn)。2、掌握線(xiàn)性表的兩種存儲(chǔ)方式及其實(shí)現(xiàn)：熟練掌握順序表和鏈表的創(chuàng)建、插入元素、刪除元素以及定位等常用操作的實(shí)現(xiàn)算法并會(huì)求相應(yīng)算法的時(shí)間復(fù)雜度。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：線(xiàn)性表的特點(diǎn)、兩種表示方式及它們的運(yùn)算實(shí)現(xiàn)，會(huì)求算法的時(shí)間復(fù)雜度。難點(diǎn)：?jiǎn)捂湵斫Y(jié)構(gòu)、特點(diǎn)及其實(shí)現(xiàn)三、章節(jié)練習(xí)(一)選擇題：1 .順序表是

7、一種的存儲(chǔ)結(jié)構(gòu)，單鏈表是的存儲(chǔ)結(jié)構(gòu)。A.順序存取B.隨機(jī)存取C.索引存取2 .順序表中第一個(gè)元素的起始存儲(chǔ)地址為100,每個(gè)元素的長(zhǎng)度為4,則第五個(gè)if忡學(xué)配絡(luò)if理中心mt*AMpAflaItanraijr元素的起始地址是。A.105B.110C.116D.1203 .非空循環(huán)單鏈表（head為頭指針）的尾結(jié)點(diǎn)（由指針p所指示）應(yīng)滿(mǎn)足。A.p->next=NULL;B.p=NULL;C.p->next=head;D.p=head;4,若在線(xiàn)性表的任何位置上插入元素的概率是相等的，那么在長(zhǎng)度為n的順序表中插入一個(gè)元素時(shí)需平均移動(dòng)個(gè)元素。A.nB.（n-1）/2C.n/2D.（n+1

8、）/25 .在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的位置由指示，首元結(jié)點(diǎn)的存儲(chǔ)位置由指示，除首元結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由旨示。A.頭指針B.頭結(jié)點(diǎn)的指針域的指針C.前驅(qū)結(jié)點(diǎn)的指針域的指針6 .單鏈表的頭指針為p,若有頭結(jié)點(diǎn)，則表空的判斷條件是;若不帶頭結(jié)點(diǎn)，則表空的判斷條件是0A.p=NULLB.p->next=NULLC.p->next->next=NULL（二）判斷題：1 .在單鏈表中插入或刪除元素時(shí)是以結(jié)點(diǎn)的指針變化來(lái)反映邏輯關(guān)系的變化，因此不需要移動(dòng)元素。（）2 .順序表能夠以元素在計(jì)算機(jī)內(nèi)的物理位置的相鄰性來(lái)表示線(xiàn)性表中元素之間的邏輯關(guān)系。（）3 .在不帶頭結(jié)

9、點(diǎn)的非空單鏈表中，首元結(jié)點(diǎn)的存儲(chǔ)位置由頭指針指示，除首元結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由前驅(qū)結(jié)點(diǎn)的指針域的指針指示。（）（三）問(wèn)答題：1 .若線(xiàn)性表要求以最快的速度存取而表中元素變動(dòng)不大，則應(yīng)采取什么存儲(chǔ)結(jié)構(gòu)（順序或鏈?zhǔn)浇Y(jié)構(gòu)）？為什么？2 .若線(xiàn)性表經(jīng)常做插入/刪除操作，則應(yīng)采取什么存儲(chǔ)結(jié)構(gòu)？為什么？3 .在單鏈表中設(shè)置頭結(jié)點(diǎn)有什么作用？（四）算法題：1 .設(shè)帶頭結(jié)點(diǎn)的單鏈表（L為頭指針）中的數(shù)據(jù)元素遞增有序。設(shè)計(jì)算法，將x插入到鏈表的適當(dāng)位置上，并仍保持該表的有序性。2 .設(shè)順序表va中的數(shù)據(jù)元素遞增有序。設(shè)計(jì)算法，將x插入到順序表的適當(dāng)位置上，并仍保持該表的有序性。3 .設(shè)計(jì)算法，實(shí)現(xiàn)

10、單鏈表的就地逆置，即利用原表的存儲(chǔ)空間將線(xiàn)性表（ai,a2,a。逆置為（an,an-i,ai）。第三章棧和隊(duì)列一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解用棧和隊(duì)列解決實(shí)際問(wèn)題的方法。2、掌握棧和隊(duì)列的定義以及特性、它們的2種不同的存儲(chǔ)表示方法（特別是順序棧和循環(huán)隊(duì)列）以及各種常見(jiàn)操作（如入、出操作）在不同表示方式上的實(shí)現(xiàn)。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：棧和隊(duì)列的定義、各種表示和實(shí)現(xiàn)方法，加深對(duì)線(xiàn)性結(jié)構(gòu)的理解難點(diǎn)：循環(huán)隊(duì)列的表示及為解決循環(huán)隊(duì)列隊(duì)空、隊(duì)涉判斷條件相同而使用的不同實(shí)現(xiàn)方式；能在具體問(wèn)題中靈活運(yùn)用棧和隊(duì)列結(jié)構(gòu)。三、章節(jié)練習(xí)（一）選擇題：1 .一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列

11、是。A.edcbaB.decbaC.dceabD.abcde2 .棧和隊(duì)列的共同點(diǎn)是。A.都是后進(jìn)先出B.都是先進(jìn)先出C.都是只允許在端點(diǎn)處插入和刪除元素D.無(wú)共同點(diǎn)3 .一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是。A.4321B.1234C.1432D.32414 .棧的入棧序列是1,2,，n,輸出序列為p1,p2,中"若p1=n,則pi為<A.iB.n-iC.n-i+1D.不確定5 .隊(duì)列是限定在進(jìn)行插入，在進(jìn)行刪除的線(xiàn)性表。A.隊(duì)頭B.隊(duì)尾C.任意位置6 .循環(huán)隊(duì)列中，設(shè)隊(duì)列元素依次存放在Q0.m中，f、r分別指示隊(duì)頭元素位置和隊(duì)尾元素的下一個(gè)位置，約定存儲(chǔ)m

12、個(gè)元素時(shí)為隊(duì)滿(mǎn)。則隊(duì)列空的判定方法是，隊(duì)列滿(mǎn)的判定方法是。if忡學(xué)岷絡(luò)it理中心A.f=rB.（f+1）%（m+1）=rC.（r+1）%（m+1）=fD.（r+1）%m=f（二）判斷題：1 .若用戶(hù)無(wú)法估計(jì)所用隊(duì)列的最大長(zhǎng)度，則最好采用鏈隊(duì)列。（）2 .在鏈隊(duì)列上刪除隊(duì)頭元素時(shí)，只需修改頭結(jié)點(diǎn)中的指針，不必修改尾指針。（）3 .棧是限定僅在棧頂進(jìn)行插入或刪除操作的線(xiàn)性表。（）4 .隊(duì)列是限定在隊(duì)尾插入元素，在隊(duì)頭刪除元素的線(xiàn)性表。（）（三）問(wèn)答與算法題：1 .對(duì)于一個(gè)棧，若輸入序列依次為A,B,C,試給出所有可能的輸出序列。2 .假設(shè)將循環(huán)隊(duì)列定義為：以整型域變量front和length分別指

13、示循環(huán)隊(duì)列中隊(duì)頭元素位置和隊(duì)列中元素個(gè)數(shù)，指針elem指示存放隊(duì)列元素的連續(xù)空間的首地址，寫(xiě)出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。第四章申一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解用的抽象數(shù)據(jù)類(lèi)型的定義以及相關(guān)術(shù)語(yǔ)、理解用在文本編輯中的作用。2、掌握字符串的定義及各種基本操作的運(yùn)算結(jié)果以及用的各種存儲(chǔ)表示的特點(diǎn)。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：用的基本運(yùn)算、用的各種存儲(chǔ)表示和特點(diǎn)。繼續(xù)加深對(duì)線(xiàn)性結(jié)構(gòu)的理解難點(diǎn)：用的不同存儲(chǔ)結(jié)構(gòu)，區(qū)分它們和高級(jí)語(yǔ)言中用的存儲(chǔ)方式的不同。三、章節(jié)練習(xí)（一）選擇題：1 .設(shè)用s="IAMASTUDENT",則其用長(zhǎng)是。A.13B.14C.15D.162 .設(shè)s="

14、HEISAWORKER",t="WORKERMStrIndex（s,t,5）的返回值是。A.4B.5C.6D.9E.103 .申是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符4 .已知用s="ABCDEFGH,則s的所有不同子用的個(gè)數(shù)為。程仲學(xué)岷IS理中心5 .設(shè)用s="Iamateacher.',則s的第8個(gè)字符起、長(zhǎng)度為7的子用為<A."teacher."B."teacher"C."ateacher"D.&q

15、uot;teacher"6.設(shè)用s="student.",t=“good",則執(zhí)行StrInsert(s,1,t)后，s為A."goodstudent."B."goodstudent"C."goodstudent"D."goodteacher"（二）判斷題:空用和空格用是相同的2.如果兩個(gè)用含有相同的字符，則它們是相同的。3.4.第七章樹(shù)和二叉樹(shù)用的基本操作和線(xiàn)性表的一樣，都是以“單個(gè)元素”作為操作對(duì)象的。在用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)大小與存儲(chǔ)密度之間沒(méi)有關(guān)系。一、章節(jié)學(xué)習(xí)目標(biāo)

16、與要求1、理解樹(shù)、二叉樹(shù)和森林的概念，理解線(xiàn)索化二叉樹(shù)的特性、創(chuàng)建方法及在線(xiàn)索二叉樹(shù)上尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法；理解樹(shù)與森林的存儲(chǔ)方法。2、掌握二叉樹(shù)的性質(zhì)及表示；掌握二叉樹(shù)的各種遍歷方法（尤其是遞歸形式的）以及遍歷在實(shí)際問(wèn)題中的應(yīng)用；掌握樹(shù)及森林與二叉樹(shù)的轉(zhuǎn)換及遍歷方式的對(duì)應(yīng)；掌握Huffman樹(shù)的構(gòu)造方法以及構(gòu)造Huffman編碼的方法。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：二叉樹(shù)的性質(zhì)（及證明）、存儲(chǔ)結(jié)構(gòu)及各種遍歷算法，二叉樹(shù)的線(xiàn)索化過(guò)程，樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換關(guān)系，Huffman樹(shù)及Huffman編碼的構(gòu)造方法難點(diǎn)：各種遍歷算法的遞歸實(shí)現(xiàn)以及在具體問(wèn)題中能靈活運(yùn)用遍歷思想解題三、章節(jié)練習(xí)（一）選

17、擇題：1 .下列關(guān)于二叉樹(shù)的說(shuō)法中，正確的有。A.二叉樹(shù)的度為2B.二叉樹(shù)的度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任一個(gè)結(jié)點(diǎn)的度都為22 .任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先、中、后序遍歷序列中的相對(duì)次序。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)3 .下面幾個(gè)符號(hào)用編碼集合中，不是前綴編碼的是。A.0,10,110,1111B.11,10,001,101,0001C.00,010,0110,1000D.b,c,aa,ac,aba,abb,abc4 .二叉樹(shù)按某種順序線(xiàn)索化后，任意結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線(xiàn)索，這種說(shuō)法。A.正確B.不正確C.無(wú)法確定（二）判斷題：1

18、.哈夫曼樹(shù)是帶權(quán)葉子數(shù)目固定的二叉樹(shù)中帶權(quán)路徑長(zhǎng)度最小的。2 .根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有5種不同的形態(tài)。3 .深度為k的完全二叉樹(shù)至少有2k-1個(gè)結(jié)點(diǎn)，至多有2k1個(gè)結(jié)點(diǎn)。4 .具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)，其葉子結(jié)點(diǎn)個(gè)數(shù)為U個(gè)。25 .在哈夫曼樹(shù)中，通常權(quán)值較大的結(jié)點(diǎn)離根較遠(yuǎn)。（三）問(wèn)答題：1.下圖所示森林轉(zhuǎn)化為相應(yīng)的二叉樹(shù)，并在其上標(biāo)出中序全線(xiàn)索。2,證明：深度為k的二叉樹(shù)上至多有2k-1個(gè)結(jié)點(diǎn)（k>1）。3 .證明：任何一棵滿(mǎn)二叉樹(shù)中的分支數(shù)B滿(mǎn)足B=2（n。一1）,其中n。為葉子結(jié)點(diǎn)個(gè)數(shù)。4 .以數(shù)據(jù)集15,3,14,2,6,9,16,17為葉子的權(quán)值構(gòu)造Huffman

19、W,畫(huà)出此樹(shù)并計(jì)算其帶權(quán)路徑長(zhǎng)度。（四）算法題：1 .假設(shè)二叉排序樹(shù)（t為指向根結(jié)點(diǎn)的指針）中各元素值均不相同，設(shè)計(jì)一個(gè)遞歸算法按遞增順序輸出樹(shù)上各元素值。2 .編寫(xiě)遞歸算法，交換二叉鏈表存儲(chǔ)的二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)。3 .編寫(xiě)遞歸算法，求以二叉鏈表存儲(chǔ)的二叉樹(shù)的深度4 .設(shè)計(jì)遞歸算法計(jì)算以二叉鏈表存儲(chǔ)的二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)目第八章一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解圖的基本概念和術(shù)語(yǔ)。2、掌握?qǐng)D的鄰接矩陣和鄰接表2種表示方法；掌握?qǐng)D的兩種遍歷算法及其求解連通性問(wèn)題的方法；掌握用Prim算法和Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程和性能分析；掌握人0«的拓?fù)渑判蚍椒ǎú灰笏惴ǎ莆?/p>

20、用Dijkstra方法求解單源最短路徑問(wèn)題的方法（不要求算法）。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：圖的數(shù)組表示法和鄰接表表示法存儲(chǔ)結(jié)構(gòu)以及圖的兩種遍歷方式，求最小生成樹(shù)的兩種方法，AOVW的拓?fù)渑判蚍椒?，掌握單源最短路徑的求法難點(diǎn)：圖的兩種遍歷算法的實(shí)現(xiàn)以及在圖的連通性問(wèn)題中的應(yīng)用三、章節(jié)練習(xí)（一）選擇題：1.4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。A.6B.12C.16D.202 .無(wú)向圖的鄰接矩陣是一個(gè)。A.對(duì)稱(chēng)矩陣B.零矩陣C.對(duì)角矩陣D.上三角矩陣3 .圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的,圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的。A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷4 .對(duì),用Prim算法求最小生成樹(shù)

21、較為合適，而Kruskal算法適于構(gòu)造圖的最小生成樹(shù)。A.完全圖B.連通圖C.稀疏圖D.稠密圖5 .對(duì)于含n個(gè)頂點(diǎn)、e條邊的無(wú)向連通圖，利用Prim算法構(gòu)造最小生成樹(shù)的時(shí)問(wèn)復(fù)雜度,用Kruskal算法構(gòu)造最小生成樹(shù)的時(shí)間復(fù)雜度為A.O(n)B.O(nC.O(e)D.O(eloge)F.O(e（二）判斷題：1,若從無(wú)向圖的一個(gè)頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷可訪(fǎng)問(wèn)到圖中所有頂點(diǎn)，則該圖一定是連通圖。（）2,若從無(wú)向圖的一個(gè)頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷可訪(fǎng)問(wèn)到圖中所有頂點(diǎn)，則該圖一定是連通圖。（）3,任何有向圖的頂點(diǎn)都可以排成拓?fù)溆行蛐蛄?，而且拓?fù)湫蛄胁晃ㄒ?。（?,有n個(gè)頂點(diǎn)和n-1條邊的無(wú)向圖一定是生成樹(shù)

22、。（）5.一棵有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊。（）6,連通分量是無(wú)向圖的極大連通子圖，而生成樹(shù)是無(wú)向圖的極小連通子圖。（）（三）問(wèn)答及算法題：0101.一個(gè)圖的鄰接矩陣G,arcs=101,該圖有多少個(gè)頂點(diǎn)？如果是有：。1L向圖，該圖共有多少條??？如果是無(wú)向圖，該圖共有多少條邊？2,已知如右圖所示的有向圖，寫(xiě)出該圖的：（1）鄰接矩陣（2）一個(gè)可能的拓?fù)溆行蛐蛄校?）寫(xiě)出從1出發(fā)的深度優(yōu)先遍歷序列（4）寫(xiě)出從5出發(fā)的廣度優(yōu)先遍歷序列。3.假設(shè)有5項(xiàng)活動(dòng)C1C5,每項(xiàng)活動(dòng)要求的前驅(qū)活動(dòng)如下：C1:無(wú)；C2:C1,C3;C3:C1;C4:C3,C5C5:C2;試根據(jù)上述關(guān)系，畫(huà)出相應(yīng)的有向圖，

23、再寫(xiě)出一個(gè)拓?fù)渑判蛐蛄小?,基于圖的深度優(yōu)先遍歷策略寫(xiě)一算法，判斷以鄰接表方式存儲(chǔ)的無(wú)向圖中連通分量的個(gè)數(shù)。第九章查找一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解各種查找表的定義、各種查找方法的思想以及構(gòu)造查找表所依據(jù)的原則。2、掌握線(xiàn)性表表示的靜態(tài)查找表的順序查找和折半查找算法及其性能分析方法；掌握二叉排序樹(shù)的創(chuàng)建、查找、插入、刪除算法及其性能分析方法；掌握AVL樹(shù)的平衡化旋轉(zhuǎn)方法及其性能分析；掌握B-樹(shù)的插入和刪除時(shí)結(jié)點(diǎn)的分裂和合并方法；掌握Hash法的查找、構(gòu)造方法平均查找長(zhǎng)度的計(jì)算方法。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：各種樹(shù)結(jié)構(gòu)表示的動(dòng)態(tài)查找表和Hash表的構(gòu)造方法難點(diǎn)：二叉排序樹(shù)的刪除、AVL樹(shù)的旋轉(zhuǎn)處理

24、、B-樹(shù)的插入和刪除、Hash法的構(gòu)造以及各種查找表的平均查找長(zhǎng)度的計(jì)算方法三、章節(jié)練習(xí)(一)選擇題：1 .二叉排序樹(shù)可得到一個(gè)關(guān)鍵字的有序序列。A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷2 .用鏈地址法處理沖突構(gòu)造的散列表中，每個(gè)地址單元所鏈接的同義詞表中結(jié)點(diǎn)的相同。A.關(guān)鍵字B.元素值C.散列地址D.含義3 .利用折半查找方法在長(zhǎng)度為n的有序表中查找一個(gè)元素的平均查找長(zhǎng)度A.O(n2)B.O(nlogn)C.O(n)D.O(logn)4 .散列表的裝填因子越大，則發(fā)生沖突的可能性就。A.越小B.越大C.不確定5 .線(xiàn)性表中共有256個(gè)元素，采用分塊查找，若查找每個(gè)元素的概率相等，用順

25、序查找確定結(jié)點(diǎn)所在的塊，每塊有個(gè)元素時(shí)查找效率最佳。A.16B.20C.25D.2566 .用折半查找對(duì)長(zhǎng)度為7的有序表進(jìn)行查找，則等概率下查找成功時(shí)的平均查找長(zhǎng)度為。A.15/7B.17/7C.18/7D.19/77 .有序表(1,32,41,45,62,75,77,82,95,100),使用折半查找關(guān)鍵字為95的元素時(shí)，需要經(jīng)過(guò)次比較后才能查找成功。A.2B.3C.4D.5(二)判斷題：1 .折半查找和二叉排序樹(shù)的查找時(shí)間性能一樣。()2 .在任意一棵非空的二叉排序樹(shù)中，刪除某結(jié)點(diǎn)后又將其插入，則所得的二叉e琳#法學(xué)髓狀舞排序樹(shù)與刪除前的二叉排序樹(shù)形態(tài)相同。()3 .根據(jù)B-樹(shù)的定義，在9

26、階B-樹(shù)中，除根以外的任何一個(gè)非葉子結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均在59之間。()4 .折半查找時(shí)，要求線(xiàn)性表必須是有序的且以順序結(jié)構(gòu)存儲(chǔ)。()(三)問(wèn)答題：1.設(shè)有一組關(guān)鍵字序列19,1,23,14,55,20,84,27,68,11,40,(1)按表中元素順序構(gòu)造一棵二叉排序樹(shù)，畫(huà)出這棵樹(shù)，并求其在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。(2)從空樹(shù)開(kāi)始，按表中元素順序構(gòu)造一棵2_3t(3階B邛t),若此后再刪除55,84,畫(huà)出每一步執(zhí)行后2_3樹(shù)的狀態(tài)。2 .設(shè)散列函數(shù)H(key)=keyMOD7,用線(xiàn)性探測(cè)再散列法解決沖突。對(duì)關(guān)鍵字序歹113,28,72,5,16,8,7,11在地址空間為0-10

27、的散列區(qū)中建散列表，畫(huà)出此表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。3 .關(guān)鍵字序列：13,28,72,5,16,18,7,11,24,h(key)=keymod11,表長(zhǎng)為11,用線(xiàn)性探測(cè)再散列處理沖突，試填寫(xiě)下表并計(jì)算每個(gè)關(guān)鍵字的比較次數(shù)和等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。012345678910比較次數(shù)ASL=4.在地址空間為0-16的散列區(qū)中，對(duì)以下關(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)鍵字中第一個(gè)字母在字母表中的序號(hào)。畫(huà)出該散列表并求在

28、等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。第十章排序一、章節(jié)學(xué)習(xí)目標(biāo)與要求1、理解排序相關(guān)的定義以及排序方法的各種分類(lèi)，理解各種排序方法的基本思想和依據(jù)原則。2、掌握內(nèi)部排序的基本概念和性能分析方法；掌握插入排序、交換排序、選擇排序等內(nèi)排序的方法及其性能分析方法。二、本章重點(diǎn)、難點(diǎn)重點(diǎn)：各類(lèi)內(nèi)部排序方法所依據(jù)的原則、特點(diǎn)及典型算法。難點(diǎn)：希爾排序、快速排序、堆排序三、章節(jié)練習(xí)(一)選擇題：1,下列方法中，是穩(wěn)定的排序方法。A.堆排序B,希爾排序C,快速排序D,折半插入排序2,設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度選出其中前20個(gè)最大的元素,最好用排序方法。A,冒泡排序B,快速排序C,堆排序D,

29、希爾排序3 .下列序列中，是堆。A,12,35,20,60,40,30B,100,85,120,38,10,9,36C,1,5,6,24,7,3,4D,38,24,15,20,30,464 .在待排序的元素序列基本有序時(shí)，效率最高的排序方法是。A,插入排序B,選擇排序C,快速排序D,歸并排序5 .在下列排序方法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的A,堆排序B,起泡排序C,快速排序D,直接插入排序6 .對(duì)序列22,86,19,49,12,30,65,35,18進(jìn)行一趟排序后得到的結(jié)果為18,12,19,22,49,30,65,35,86,則其使用的排序方法為。A,插入排序B,選擇

30、排序C,快速排序D,起泡排序7,下列方法中，算法的時(shí)間復(fù)雜度為O(n2)。A,堆排序B,希爾排序C,快速排序D,直接插入排序8,對(duì)n個(gè)記錄的序列進(jìn)行堆排序，最壞情況下的時(shí)間復(fù)雜度為。A,O(logn)B,O(nlogn)C,O(n)D,O(n2)(二)判斷題：1,快速排序的速度在所有排序方法中是最快的，而且所需的附加空間也最少。()2,對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。()3.由于希爾排序的最后一趟與直接插入排序過(guò)程相同，所以前者一定比后者花費(fèi)格it理中心rwat的時(shí)間多。（）4.快速排序算法在待排序數(shù)據(jù)有序時(shí)最不利于發(fā)揮其長(zhǎng)處。（）（三）問(wèn)答題：1 .在快速排序過(guò)程中，通常取序列

31、中的第1個(gè)記錄作為樞軸，以它為“分界線(xiàn)”重排其余記錄。但當(dāng)初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判颍瑸楦倪M(jìn)之，應(yīng)如何選取樞軸記錄？2 .判斷以下序列是否是堆，若不是，把它調(diào)整為堆（要求記錄交換次數(shù)最少），寫(xiě)出調(diào)整后的序列。1 ）5,26,20,60,80,35,53,702 ）26,33,35,29,19,12,223 .已知關(guān)鍵字序列70,83,100,65,10,9,7,32,寫(xiě)出直接插入排序和快速排序每一趟結(jié)束時(shí)的關(guān)鍵字狀態(tài)。4 .設(shè)關(guān)鍵字集合為10,2,14,8,12,13,（1）寫(xiě)出用希爾排序方法對(duì)序列排序時(shí)每一趟結(jié)束時(shí)的關(guān)鍵字狀態(tài)。（2）用堆排序方法對(duì)其從小到

32、大排序，畫(huà)出堆排序的初態(tài)、建堆和排序過(guò)程中重建堆的過(guò)程。考試模擬題客觀(guān)題部分一、單項(xiàng)選擇題：（每空2分，共20分）1 .單鏈表是線(xiàn)性表的一種的存儲(chǔ)結(jié)構(gòu)。A.順序存取B.隨機(jī)存取C.索引存取2 .棧和隊(duì)列的共同點(diǎn)是。A.都是后進(jìn)先出B.都是先進(jìn)先出C.都是只允許在端點(diǎn)處插入和刪除元素D.無(wú)共同點(diǎn)3 .設(shè)s="HEISAWORKER",t="WORKER"則index（s,t,5）的返回值是。A.4B.5C.6D.9E.104 .用是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在。理獨(dú)學(xué)岷結(jié)管理中心iWaifA,可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C,可以鏈接存儲(chǔ)D,數(shù)據(jù)元

33、素可以是多個(gè)字符5 .樹(shù)最適合用來(lái)表示。A.有序數(shù)據(jù)元素B,無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D,元素之間無(wú)關(guān)聯(lián)的數(shù)據(jù)6 .4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。A.6B,12C,16D.207 .散列表的裝填因子越大，則發(fā)生沖突的可能性就。A,越小B,越大C,不確定8 .在長(zhǎng)度為n的有序表中折半查找一個(gè)元素的平均查找長(zhǎng)度是。A,O（n2）B,O（nlogn）C,O（n）D,O（logn）9,下列方法中，是不穩(wěn)定的排序方法。A,折半插入排序B,直接插入排序C,冒泡排序D,堆排序10. 二叉排序樹(shù)可得到一個(gè)關(guān)鍵字的有序序列。A.先序遍歷B,中序遍歷C,后序遍歷D,層序遍歷二、是非題：（每題1分

34、，共10分）（說(shuō)明：正確的選“A”，錯(cuò)誤選"B'）1 .線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）2 .空用和空格用是相同的。（）3 .圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)和后續(xù)都可以有任意多個(gè)。（）4 .快速排序算法在待排序數(shù)據(jù)有序時(shí)最不利于發(fā)揮其長(zhǎng)處。（）5 .連通網(wǎng)的最小生成樹(shù)是唯一的。（）6 .棧是FIFO的線(xiàn)性表。（）7 .由二叉樹(shù)的先序和后序遍歷序列不能唯一確定這棵二叉樹(shù)。（）8 .若從無(wú)向圖的一個(gè)頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷可訪(fǎng)問(wèn)到圖中的所有頂點(diǎn)，則該圖一定是連通圖。（）9 .折半查找方法要求查找表必須是關(guān)鍵字的有序表，但是對(duì)存儲(chǔ)結(jié)構(gòu)沒(méi)有限制。（）10 .在一棵非空二叉樹(shù)的中序

35、遍歷序列中，根結(jié)點(diǎn)的右邊只有其右子樹(shù)上的所有結(jié)點(diǎn)主觀(guān)題部分則應(yīng)采取什么存、簡(jiǎn)答題：(50分)1,若線(xiàn)性表要求以最快的速度存取而表中元素變動(dòng)不大,儲(chǔ)結(jié)構(gòu)(順序或鏈?zhǔn)浇Y(jié)構(gòu))？為什么？(10分)（10分）2,將下圖所示森林轉(zhuǎn)化為二叉樹(shù)并在其上標(biāo)出中序全線(xiàn)索33,已知如右圖所示的有向圖，寫(xiě)出該圖的：(1)鄰接矩陣(2)一個(gè)可能的拓?fù)溆行蛐蛄小?10分)對(duì)關(guān)鍵字序4.設(shè)散列函數(shù)H(key)=keyMOD7,用線(xiàn)性探測(cè)再散列法解決沖突。列13,28,72,5,16,8,7,9,11,29在地址空間為0-10的散列區(qū)中建散列表，回出此表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。（10分）5.對(duì)于序列26,

36、33,35,29,19,12,22,(1)判斷它是否是堆，若是，寫(xiě)出其是大頂堆還是小頂堆；若不是,把它調(diào)整為堆，寫(xiě)出調(diào)整的過(guò)程和調(diào)整后的序列。（5分）（5分）（10分）(2)寫(xiě)出對(duì)該序列進(jìn)行直接插入排序每一趟結(jié)束時(shí)的關(guān)鍵字狀態(tài)。、算法設(shè)計(jì)題：(20分)1、編寫(xiě)遞歸算法，計(jì)算二叉鏈表存儲(chǔ)的二叉樹(shù)的結(jié)點(diǎn)數(shù)目。2、基于圖的深度優(yōu)先遍歷策略寫(xiě)一算法,判斷以鄰接表方式存儲(chǔ)的無(wú)向圖中連通分量的個(gè)數(shù)。（10分）褥的同學(xué)岷格管理中心附：答案或答案要點(diǎn)第一章章節(jié)練習(xí)答案（一）選擇題：1.D2.C3.A4.C5.A6.B7.B8.D（二）判斷題：1.x2.V3.X4.V第二章章節(jié)練習(xí)答案（一）選擇題：1.B,A2

37、.C3.C4.C5.A,B,C6.B,A（二）判斷題：1.V2,V3,V（三）問(wèn)答題：1.應(yīng)采用順序結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取的存儲(chǔ)結(jié)構(gòu)，在順序表中存取任何元素所花的時(shí)間都一樣。而鏈表是順序存取的存儲(chǔ)結(jié)構(gòu)。2,應(yīng)采用鏈?zhǔn)浇Y(jié)構(gòu)。因?yàn)樵阪湵碇惺且越Y(jié)點(diǎn)的指針變化來(lái)反映邏輯關(guān)系的變化，因此不需要移動(dòng)元素，效率高。3.頭結(jié)點(diǎn)在位置上可視為首元結(jié)點(diǎn)的前驅(qū)，則做插入/輸出操作時(shí)，i=1（即插入或刪除白位置是1）時(shí)不需要做特別處理，否則i=1時(shí)需要修改頭指針。（四）算法題：1. statusinsert_L(LinkListL,ElemTypex)/*帶頭結(jié)點(diǎn)*/LinkListp,s;for(p=L;p-&

38、gt;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;2. statusinsert_Sq(SqList*va,ElemTypex)inti;if(va->length=va->listsize)exitOVERFLOW;絡(luò)it理中心for(i=va->length-1;i>=0&&am

39、p;va->elemi>x;-i)va->elemi+1=va->elemi;va->elemi+1=x;va->length+;returnOK;3. voidreverse(LinkListL)/*帶頭結(jié)點(diǎn)*/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.C2.C3.B4.C5.B,A6.A,C(二)判斷題：1.V2.X3.V4.V(三)問(wèn)答與算法題：1

40、 .所有可能的輸出序列有：ABC、ACB、BAC、BCA、CBA2 .算法：#defineMAXQSIZE100typedefstructElemType*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->

41、;length=0)returnERROR;*e=Q->elemQ->front;Q->length-;returnOK;)第四章章節(jié)練習(xí)答案(一)選擇題：1.B2,D3.B4.D5.B6.A(二)判斷題：1.X2,X3.X4.X第七章章節(jié)練習(xí)答案（一）選擇題：1.B2,A3.B4.B4.V5,義（三）問(wèn)答題：（二）判斷題：1,V2,V3,V®即業(yè)法學(xué)髓必舞2.證明：由于深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為二叉樹(shù)上每一層的最大結(jié)點(diǎn)數(shù)之和，而二叉樹(shù)上第i層的最大2點(diǎn)數(shù)為2i-10則kkZ(第i層的最大結(jié)點(diǎn)數(shù))=£2i-1=2k-1i1i43,證明：設(shè)no為葉子結(jié)點(diǎn)

42、個(gè)數(shù)，血為度為2的結(jié)點(diǎn)個(gè)數(shù),則由二叉樹(shù)的性質(zhì)2可知：n2=no-1又：滿(mǎn)二叉樹(shù)中只有度為2的結(jié)點(diǎn)和葉子結(jié)點(diǎn),所以滿(mǎn)二叉樹(shù)中的結(jié)點(diǎn)總數(shù)n=n2+no=2no1又：二叉樹(shù)中的分支數(shù)B=n1所以：B=2n011=2(n01)4.wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229(四)算法題：1. voidoutput(BiTreet)(if(t)output(t->lchild);printf(t->data);output(t->rchild);絡(luò)if理中心mu*匐HhhfAaItepnijr2. voidexchange(BiTreet)(BiT

43、reetemp;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->rchil

44、d)return1;returnleaf(t->lchild)+leaf(t->rchild);第八章章節(jié)練習(xí)答案(一)選擇題：1.A2.A3.D,A4.D,C5.B,D(二)判斷題：1.V2.V3.X4.X5.V6.V(三)問(wèn)答及算法題：1.圖中共有3個(gè)頂點(diǎn)，如果是有向圖，該圖共有5條弧；如果是無(wú)向圖,該圖共有3條邊。2.(1)鄰接矩陣:一。000000010000001001000000010001(2)可能的拓?fù)湫蛄袨?156234(注意4一定是最后一個(gè)，2一定在1和5后)(3)123456(4)562431(for(i=0;i<G.vexnum;i+)visitedi

45、=false;sum=0;for(i=0;i<G.vexnum;i+)if(!visitedi)sum+;dfs(G,i);returnsum;voiddfs(AlGraphG,inti)visitedi=true;for(p=G.verticesi.firstarc;p;p=p->nextarc)k=p->adjvex;if(!visitedk)dfs(G,k);)第九章章節(jié)練習(xí)答案(一)選擇題：1.B2,C3.D4.B5.A6.B7.B（三）問(wèn)答題:1.(DASL=(1+2*2+3*3+3*4+2*5)/11=36/11(2)2_3樹(shù):3.（二）判斷題：1.X2.X3.(

46、3)刪除55:刪除84:X4.12gl詞幣13|11n2.ASL=(1+1+1+2+5+1+1+4)/8=16/8=23、012345678910哈希表1113245287216187比較次數(shù)112112434ASL=(1+1+2+1+1+2+4+3+4)/9=19/94.用鏈地址法處理沖突：（注意鏈表的有序性）012345678910111213141516ASL=(7*1+4*2+1*3)/12=18/12第十章章節(jié)練習(xí)答案（一）選擇題：1.D2.C3.A4.A5.D6.C7.D8.B（二）判斷題：1.x2.V3.X4.V（三）問(wèn)答題：1 .應(yīng)依據(jù)“三者取中”的原則，比較第一個(gè)、最后一個(gè)和中間位置處記錄的關(guān)鍵字，取關(guān)鍵字居中