數(shù)據(jù)結(jié)構(gòu)(本)期末復(fù)習(xí)指導(dǎo)

1、 數(shù)據(jù)結(jié)構(gòu)（本）期末復(fù)習(xí)指導(dǎo)第一部分 課程考核說(shuō)明一、考核說(shuō)明數(shù)據(jù)結(jié)構(gòu)（本）是中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)（本科）專業(yè)的一門統(tǒng)設(shè)必修、學(xué)位課程。4學(xué)分，72學(xué)時(shí)，其中實(shí)驗(yàn)24學(xué)時(shí)，開(kāi)設(shè)一學(xué)期。課程主要內(nèi)容包括：數(shù)據(jù)結(jié)構(gòu)和算法的基本概念、線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹(shù)和圖、查找和排序等。目的是使學(xué)生通過(guò)該課程的學(xué)習(xí)，深入地理解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及有關(guān)算法，掌握基本的程序設(shè)計(jì)技能，學(xué)會(huì)編制高效可靠的程序，為學(xué)習(xí)后續(xù)課程奠定基礎(chǔ)?，F(xiàn)將有關(guān)考核的幾個(gè)問(wèn)題說(shuō)明如下：1考核對(duì)象2007年秋季起入學(xué)的計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）學(xué)生。2考核依據(jù)以數(shù)據(jù)結(jié)構(gòu)（本）課程教學(xué)大綱為依據(jù)編制，考核

2、說(shuō)明是本課程形成性考核和終結(jié)性考試命題的基本依據(jù)。3考核方式采用形成性考核和終結(jié)性考試相結(jié)合的方式。4課程總成績(jī)的記分方法課程總成績(jī)按百分制記分，其中形成性考核所占的比例為30%，終結(jié)性考試占70。60分為合格，可以獲得課程學(xué)分。本課程的學(xué)位課程學(xué)分為70分，即課程總成績(jī)達(dá)到70分及以上者有資格申請(qǐng)專業(yè)學(xué)位。5形成性考核的要求、形式及手段形成性考核主要考核學(xué)生形成性作業(yè)和實(shí)驗(yàn)的完成情況，占課程總成績(jī)的30%。形成性考核以作業(yè)冊(cè)的形式下發(fā)，由各地電大根據(jù)學(xué)生作業(yè)和實(shí)驗(yàn)的完成情況進(jìn)行考核。中央電大將不定期隨機(jī)抽檢各地電大學(xué)生的形成性作業(yè)及課程實(shí)驗(yàn)報(bào)告。6終結(jié)性考試的要求及方式（1） 考試要求考核要

3、求分為了解、理解和掌握三個(gè)層次：了解：是指（1）學(xué)習(xí)本課程主干知識(shí)點(diǎn)所需要的概念、方法、預(yù)備知識(shí)和相關(guān)內(nèi)容。（2）就大部分學(xué)生目前的知識(shí)結(jié)構(gòu)和基礎(chǔ)理解和掌握有一定困難，有待今后進(jìn)一步學(xué)習(xí)的內(nèi)容。（3）在主干知識(shí)點(diǎn)基礎(chǔ)上拓展的內(nèi)容。這部分不屬考核的主要內(nèi)容。理解：是指要求學(xué)生準(zhǔn)確全面領(lǐng)會(huì)的概念、方法和思路等。相關(guān)內(nèi)容是本課程的主干知識(shí)點(diǎn)，要求學(xué)生能融匯貫通，并能利用所學(xué)知識(shí)分析解決相關(guān)問(wèn)題。這部分是考核的主要范圍。掌握：是指本課程最重要的知識(shí)點(diǎn)，能充分體現(xiàn)本課程的教學(xué)要求，要求學(xué)生在理解所學(xué)知識(shí)的基礎(chǔ)上能靈活應(yīng)用。能結(jié)合課程的不同知識(shí)點(diǎn)解決綜合性的問(wèn)題和簡(jiǎn)單應(yīng)用問(wèn)題。這部分是考核的重點(diǎn)內(nèi)容。（2

4、） 考核方式中央電大統(tǒng)一命題，閉卷考試。（3）組卷原則在考核說(shuō)明所規(guī)定的內(nèi)容和要求之內(nèi)命題。在教學(xué)內(nèi)容范圍之內(nèi)，按照理論聯(lián)系實(shí)際原則，考察學(xué)生對(duì)所學(xué)知識(shí)應(yīng)用能力的試題，不屬于超綱。試題的難易程度和題量適當(dāng)，按難易程度分為易、中、難三個(gè)層次：易占25%，中占45%，難占30%。題量安排以大多數(shù)考生能在規(guī)定的考試時(shí)間內(nèi)做完并有一定時(shí)間檢查為原則。（4）試題類型及試卷結(jié)構(gòu)試題題型有單項(xiàng)選擇題、填空題、綜合題和程序填空題四種題型。試卷結(jié)構(gòu)如下：?jiǎn)雾?xiàng)選擇題：每小題2分，共30分填空題： 每小題2分，共24分綜合題： 每小題10分，共30分程序填空題：每空2分，共16分共100分 （5）答題時(shí)限答題時(shí)限為

5、90分鐘。 二、考核內(nèi)容和要求 第1章 緒論（2學(xué)時(shí)）考核知識(shí)點(diǎn)1數(shù)據(jù)結(jié)構(gòu)的基本概念2算法和算法分析的基本概念考核要求1理解數(shù)據(jù)結(jié)構(gòu)的基本概念2掌握邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的概念及相互關(guān)系3掌握本書(shū)介紹的四種基本結(jié)構(gòu)的特點(diǎn)4理解算法及其特性5了解算法分析的一般概念第2章 線性表（8學(xué)時(shí)）考核知識(shí)點(diǎn)1線性表的定義、邏輯結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作和應(yīng)用 3雙向鏈表、循環(huán)鏈表的原理和相關(guān)操作考核要求1理解線性表的定義及兩種存儲(chǔ)結(jié)構(gòu)2理解線性表順序存儲(chǔ)的特點(diǎn)、實(shí)現(xiàn)方法和應(yīng)用。3掌握順序表的基本操作（包括建立鏈表、遍歷鏈表、刪除、插入、查找）和應(yīng)用。特別要求能夠利

6、用鏈表的操作和相關(guān)的程序設(shè)計(jì)技術(shù)編制有一定難度的程序。4了解雙向鏈表、循環(huán)鏈表的原理和相關(guān)操作。第3章 棧和隊(duì)列（6學(xué)時(shí)）考核知識(shí)點(diǎn)1棧的定義、棧的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）和基本操作、棧的應(yīng)用2隊(duì)列的定義、隊(duì)列的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）、隊(duì)列的應(yīng)用3循環(huán)隊(duì)列的概念和實(shí)現(xiàn)方法考核要求1掌握棧和隊(duì)列的操作特點(diǎn)2理解順序棧、順序隊(duì)列的基本操作3了解在實(shí)際編程中棧和隊(duì)列的不同應(yīng)用。理解循環(huán)隊(duì)列的概念、實(shí)現(xiàn)方法。掌握循環(huán)隊(duì)列判空、判滿的條件4能按照后續(xù)章節(jié)（例如二叉樹(shù)、排序等）的要求利用遞歸程序設(shè)計(jì)技術(shù)實(shí)現(xiàn)相關(guān)算法第4章 串（2學(xué)時(shí)）考核知識(shí)點(diǎn)1串類型定義、C語(yǔ)言中字符串的特點(diǎn)和處理方法2串

7、的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3串的基本運(yùn)算和實(shí)現(xiàn)方法考核要求1理解串的定義和存儲(chǔ)方法2了解串的基本操作和相關(guān)算法3掌握用C語(yǔ)言處理字符串的語(yǔ)法規(guī)則第5章 數(shù)組和廣義表（2學(xué)時(shí)）考核知識(shí)點(diǎn)1數(shù)組的定義和存儲(chǔ)結(jié)構(gòu)2特殊矩陣和稀疏矩陣的存儲(chǔ)結(jié)構(gòu)3廣義表的定義和存儲(chǔ)結(jié)構(gòu)考核要求1了解數(shù)組的存儲(chǔ)結(jié)構(gòu)。2掌握特殊矩陣進(jìn)行壓縮存儲(chǔ)的下標(biāo)轉(zhuǎn)換公式。3理解稀疏矩陣的壓縮存儲(chǔ)原理。4掌握利用三元組表示稀疏矩陣的方法。5了解廣義表的概念和存儲(chǔ)結(jié)構(gòu)。第6章 樹(shù)和二叉樹(shù)（10學(xué)時(shí)）考核知識(shí)點(diǎn)1樹(shù)的基本概念2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)3二叉樹(shù)的遍歷和線索二叉樹(shù)4哈夫曼樹(shù)及其應(yīng)用考核要求1了解樹(shù)和二叉樹(shù)的定義2掌握二叉樹(shù)的基本

8、性質(zhì)，能利用相關(guān)性質(zhì)解決簡(jiǎn)單計(jì)算問(wèn)題3了解二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)4掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、相關(guān)操作5掌握二叉樹(shù)的有關(guān)算法并能編程實(shí)現(xiàn)6掌握利用遍歷序歷構(gòu)造二叉樹(shù)的規(guī)則和具體步驟7掌握哈夫曼樹(shù)的定義、性質(zhì)和構(gòu)造方法8了解哈夫曼樹(shù)的應(yīng)用第7章 圖（6學(xué)時(shí)）考核知識(shí)點(diǎn)1圖的基本概念2圖的存儲(chǔ)結(jié)構(gòu)3圖的遍歷4最小生成樹(shù)和最短路徑?？己艘?了解圖的基本概念2掌握?qǐng)D的存儲(chǔ)方法（鄰接矩陣、鄰接表）3掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷的規(guī)則和步驟4理解在連通圖中求最小生成樹(shù)的方法。了解求圖的最短路徑等相關(guān)算法及其應(yīng)用第8章 查找（6學(xué)時(shí)）考核知識(shí)點(diǎn)1線性表的查找（順序查找、折半查找、分塊查找）。2二叉排序樹(shù)的查

9、找。3哈希表（哈希表的定義、哈希函數(shù)的構(gòu)造、處理沖突的方法、哈希表的查找和分析）?？己艘?了解查找的相關(guān)概念。2掌握順序表的查找方法、步驟、程序?qū)崿F(xiàn)、時(shí)間復(fù)雜度和平均查找長(zhǎng)度。3掌握在有序的順序表上進(jìn)行折半查找的方法、步驟、程序?qū)崿F(xiàn)。4掌握折半查找的判定樹(shù)的構(gòu)造方法。能利用判定樹(shù)求平均查找長(zhǎng)度。5掌握二叉排序樹(shù)的確切定義，掌握建立二叉排序樹(shù)的步驟和方法。理解在二叉排序樹(shù)中進(jìn)行輸入、刪除操作的規(guī)則。6了解哈希表的相關(guān)概念和原理，了解常用哈希函數(shù)的構(gòu)造和處理沖突的方法。理解哈希函數(shù)和哈希表的關(guān)系及在查找中的應(yīng)用。第9章 排序（6學(xué)時(shí)）考核知識(shí)點(diǎn)1插入排序（直接插入排序、希爾排序）2交換排序（冒泡

10、排序、快速排序）3選擇排序（簡(jiǎn)單選擇排序、堆排序）4歸并排序考核要求1掌握教材中介紹的各種排序算法的基本原理、步驟。2能針對(duì)小規(guī)模具體實(shí)例，按相關(guān)排序算法的規(guī)則人工完成排序；能通過(guò)分析排序的中間結(jié)果判斷所用的排序算法。3能正確理解相關(guān)排序算法的程序?qū)嵗?，并重點(diǎn)掌握算法中的關(guān)鍵步驟和關(guān)鍵語(yǔ)句。4掌握堆和特殊的完全二叉樹(shù)的對(duì)應(yīng)關(guān)系。掌握建堆、篩選算法和完全二叉樹(shù)相關(guān)操作的對(duì)應(yīng)關(guān)系。三、試題類型及答案一、單項(xiàng)選擇題（每小題2分，共30分）1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。A. 邏輯 B. 物理 C. 存儲(chǔ) D. 邏輯與物理2.下述各類表中可以隨機(jī)訪問(wèn)的是（ ）。A. 單向鏈表

11、 B. 雙向鏈表 C.單向循環(huán)鏈表 D.順序表3.在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，從前到后依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（ ）。A. 21 B. 20 C. 19 D. 254.元素2，4，6按順序依次進(jìn)棧，則該棧的不可能的輸出序列是（ ）。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45.一個(gè)隊(duì)列的入隊(duì)序列是5，6，7，8，則隊(duì)列的輸出序列是（ ）。A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多種情況6. 串函數(shù)StrCmp（“d”，“D”）的值為（ ）。 A0 B1 C-1 D37在一個(gè)單鏈表中，p、q分別指向表

12、中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語(yǔ)句（ ）。 Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 8.設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)一共有（ ）個(gè)結(jié)點(diǎn)。A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1)9.對(duì)如圖1所示二叉樹(shù)進(jìn)行中序遍歷，結(jié)果是（ ）。A. dfebagc B. defbagc C. defbacg D.dbaefcg圖1cbcdefga 10 . 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（ ）。A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在11設(shè)有一個(gè)1

13、0階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ ）。A33 B32 C85 D4112 . 一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（ ）。 A31，29，37，85，47，70 B29，31，37，47，70，85C31，29，37，70，47，85 D31，29，37，47，70，8513 . 對(duì)n個(gè)元素進(jìn)行冒泡排序，要求按升序排列，程序中設(shè)定某一趟冒泡沒(méi)有出現(xiàn)元素交換，就結(jié)束排序過(guò)程。對(duì)某n個(gè)元素的排序共進(jìn)

14、行了3n-6次元素間的比較就完成了排序，則（ ）。A.原序列是升序排列B.原序列是降序排列C.對(duì)序列只進(jìn)行了2趟冒泡D. 對(duì)序列只進(jìn)行了3趟冒泡14在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行（ ）。A.x=top-data;top=top-next; B. top=top-next ; x=top;C.x=top;top=top-next ; D. x=top-data;15串函數(shù)StrCat（a,b）的功能是進(jìn)行串（ ）。 A比較 B復(fù)制 C賦值 D連接 二、填空題（每小題2分，共24分）1在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的新結(jié)點(diǎn)，應(yīng)執(zhí)行s-nex

15、t=p-next；和_操作。2根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃開(kāi)、 、 、 四類基本結(jié)構(gòu)。3在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi)。 (結(jié)點(diǎn)的指針域?yàn)閚ext)4._遍歷二叉排序樹(shù)可得到一個(gè)有序序列。5.一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有_個(gè)葉結(jié)點(diǎn)。6.如圖1所示的二叉樹(shù)，其中序遍歷序列為_(kāi) _。efgibachd 圖17.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的_、_和_三項(xiàng)信息。8 . 有一個(gè)有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值

16、為82的結(jié)點(diǎn)，經(jīng)_次比較后查找成功。9 .圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不是唯一的。此斷言是_的。(回答正確或不正確) 10哈希法既是一種存儲(chǔ)方法，又是一種 。1144.在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_次。12棧和隊(duì)列的操作特點(diǎn)分別是_和 _。三、綜合題（每小題10分，共30分）1已知序列11，19，5，4，7，13，2，10 ，（1）試給出用歸并排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。（2）對(duì)上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉樹(shù)描述建堆過(guò)程）。2設(shè)有序表為（

17、13，19，25，36，48，51，63，84，91，116，135，200），元素的下標(biāo)依次為1,2,12. （1）說(shuō)出有哪幾個(gè)元素需要經(jīng)過(guò)3次元素間的比較才能成功查到（2）畫(huà)出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)結(jié)點(diǎn)用下標(biāo)表示）（3）設(shè)查找元素5，需要進(jìn)行多少次元素間的比較才能確定不能查到.3 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù).（2）說(shuō)明如何通過(guò)序列的二叉排序樹(shù)得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果.四、程序填空題（每空2分，共16分）1以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)行冒泡排序，完成程序

18、中的空格部分，其中n是元素個(gè)數(shù)，程序按升序排列。Void bsort (NODE a , int) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break; 程序中flag的功能是（5） 7以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域?yàn)閐ata，其數(shù)據(jù)類型為字符型，BT指向根結(jié)點(diǎn)）。Void Postorder (

19、struct BTree Node *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 試題答案；一、單項(xiàng)選擇題（每小題2分，共30分）1A 2D 3B 4B 5A 6C 7C 8B 9A 10A 11A 12D 13D 14A 15D二、填空題（每小題2分，共24分）1.p-next=s; 2.集合、線性、樹(shù)形、圖狀 3. f=f-next;4.中序5.n6. dgbaechhif 7.行號(hào)、列號(hào)、元素值8.4次9.正確10查找方法113次12先進(jìn)后出 先進(jìn)先出三、綜合題（每小題10分，共30分）1(1) 初始 11，19，5，4，7，13，2，10第一趟 11，194，

20、57，132，10第二趟 4，5，11，192，7，10，13 第三趟 2，4，5，7，10，11，13，19135101119724(2)2101151974137131013191125419247105112 (1)13,36,63,135 471285211110639(2) (3)3次53(12)中序遍歷中序 2，3，4，5，6，7，14，16，18四、程序填空題（每空2分，共16分）1（1）j=n-1（2）inext= =head Dhead-next= =NULL3鏈表所具備的特點(diǎn)是（ ）。A可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B占用連續(xù)的存儲(chǔ)空間C插入刪除元素的操作

21、不需要移動(dòng)元素結(jié)點(diǎn) D可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)4非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。 Ap-next = =NULL Bp= =NULL Cp= =head Dp-next= =head 5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 A物理 B邏輯 C存儲(chǔ) D邏輯與物理 6算法的時(shí)間復(fù)雜度與（ ）有關(guān)。 A所使用的計(jì)算機(jī) B計(jì)算機(jī)的操作系統(tǒng) C算法本身 D數(shù)據(jù)結(jié)構(gòu)7設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前插入一個(gè)元素（也就是插入元素作為新表的第i個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ ）。 An-i+1 Bn-i Cn-i-1 Di8設(shè)有一

22、個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 An-i+1 Bn-i Cn-i-1 Di9在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語(yǔ)句是（ ）。 Ap=q-next Bp-next=q Cq-next=NULL Dp-next=q-next10在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。 Ap=snext Bpnext=snext; Csnext=pnext; pnext=s; Dpnext= s; snext= pnext11從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保

23、存被刪結(jié)點(diǎn)的植，則執(zhí)行（ ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;12在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。 Ar=fnext; Br=rnext; Cf=fnext; Df=rnext;13在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（ ）。 Af-next=s; f=s; Bs-next=r;r=s; Cr-next=s;r=s; Ds-next=f;f=s;14元素1，3，5，7按順序

24、依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A7，5，3，1 B7，5，1，3C3，1，7，5 D1，3，5，7 15設(shè)有一個(gè)18階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a10,8在一維數(shù)組B中的下標(biāo)是（ ）。A18 B45 C53 D58 16在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用（ ）個(gè)字節(jié)。 A4 B3 C6 D1217一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有（ ）個(gè)指針域?yàn)榭铡?An Bn+1 Cn-1 Dn-218在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為

25、（ ）。 A2i B2i-1 C2i+1 D2i+219設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（ ）個(gè)非葉結(jié)點(diǎn)。 An B2n Cn-1 Dn+1 20一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（ ）個(gè)結(jié)點(diǎn)。 A4 B6 C16 D821一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。 A30 B20 C21 D2322在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ ）倍。 A3 B2 C2.5 D1.5 23已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caedfcb Daebcfd

26、bdfeca 圖124已知如圖3所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5 圖325在有序表1，3，8，13，33，42，46，63，76，78，86，97，100中，用折半查找值86時(shí)，經(jīng)（ ）次比較后查找成功。A3 B4 C6 D8 26對(duì)二叉排序樹(shù)進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。 A按層次 B后序 C中序 D前序27有一個(gè)長(zhǎng)度為12的有序表，按折半查找對(duì)

27、該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A37/12 B39/12 C41/12 D35/1228設(shè)已有m個(gè)元素有序，在未排好序的序列中挑選第m+1個(gè)元素，并且只經(jīng)過(guò)一次元素的交換就使第m+1個(gè)元素排序到位，該方法是（ ）。 A折半排序 B冒泡排序 C歸并排序 D簡(jiǎn)單選擇排序29一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（ ）。 A40，38，46，79，56，84 B40，38，46，84，56，79 C40，38，46，56，79，84 D38，40，46，56，79，8430一組記錄的關(guān)鍵

28、字序列為（47，80，57，39，41，46），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。 A39，47，46，80，41，57 B39，41，46，80，47，57C41，39，46，47，57，80 D39，80，46，47，41，57二填空題1把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_(kāi) _結(jié)構(gòu)。2算法的5個(gè)特征為_(kāi)。3結(jié)構(gòu)中的數(shù)據(jù)元素存在 的關(guān)系稱為樹(shù)形結(jié)構(gòu)。4要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi)和 _ 。5求兩個(gè)n階矩陣的乘積，算法的基本操作和時(shí)間復(fù)雜度分別為_(kāi)和_ _。6在一個(gè)單向鏈表

29、中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s-next=p-next;和 的操作。7設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，若p-next= = head，則p所指結(jié)點(diǎn)為 。8在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則可以用操作_。9設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p-next= =NULL,通過(guò)操作_,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。10向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s-next=h; 和 操作。(結(jié)點(diǎn)的指針域?yàn)閚ext)11從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)

30、點(diǎn)的值，可執(zhí)行 和h=h-next; (結(jié)點(diǎn)的指針域?yàn)閚ext) 。12在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為r-next=s;和 (結(jié)點(diǎn)的指針域?yàn)閚ext)。13在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi)。 (結(jié)點(diǎn)的指針域?yàn)閚ext)14.兩個(gè)串相等的充分必要條件是_ _。15對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的_、_和_三項(xiàng)信息。16在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是_、 、 。17一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有_個(gè)葉結(jié)點(diǎn)。18一棵二叉樹(shù)中有

31、2n-2條邊（結(jié)點(diǎn)間的連線），其中每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有_個(gè)非葉結(jié)點(diǎn)。19中序遍歷二叉排序樹(shù)可得到一個(gè) 。20如圖1所示的二叉樹(shù)，其中序遍歷序列為_(kāi) _。gfabdecefgibachd圖1圖221如圖1所示的二叉樹(shù)，其先序遍歷序列為_(kāi)。22如圖1所示的二叉樹(shù)，其后序遍歷序列為_(kāi)。23如圖2所示的二叉樹(shù)，其前序遍歷序列為_(kāi)。24哈希函數(shù)是記錄關(guān)鍵字值與該記錄存儲(chǔ)地址之間所構(gòu)造的對(duì)應(yīng)關(guān)系。25圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_的。(回答正確或不正確) 26n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_趟冒泡，第j趟冒泡要進(jìn)行_次元素間的比較。三、綜合題1設(shè)一組記

32、錄的關(guān)鍵字序列為（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并畫(huà)出中間過(guò)程）（1）以二叉樹(shù)描述6個(gè)元素的初始堆（2）以二叉樹(shù)描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個(gè)元素、4個(gè)元素的堆2已知序列11，19，5，4，7，13，2，10 （1）試給出用歸并排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。（2）對(duì)上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉樹(shù)描述建堆過(guò)程）。3一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84）（1）利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過(guò)程，要求以升序排列）（2）對(duì)上述序列用堆排

33、序的方法建立大根堆，要求以二叉樹(shù)逐次描述建堆過(guò)程。4設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120) ,元素的下標(biāo)依次為1,2,3,，11. （1）畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)用下標(biāo)表示）（2）說(shuō)明成功查找到元素40需要經(jīng)過(guò)多少次比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？5設(shè)查找表為(16,15,20,53,64,7), (1)用冒泡法對(duì)該表進(jìn)行排序（要求升序排列），要求寫(xiě)出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？ (2)在排序后的有序表的基礎(chǔ)上，畫(huà)出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的

34、判定樹(shù).(要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn))(3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長(zhǎng)度.6（1）如果二叉樹(shù)中任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值，則該樹(shù)為二叉排序樹(shù)，這種說(shuō)法是否正確？若認(rèn)為正確，則回答正確，若認(rèn)為不正確，則舉例說(shuō)明。 （2）設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù).7 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù).（2）說(shuō)明如何由序列的二叉排序樹(shù)得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果.8(1)“一棵二叉樹(shù)若它的根結(jié)點(diǎn)的

35、值大于左子樹(shù)所有結(jié)點(diǎn)的值，小于右子樹(shù)所有結(jié)點(diǎn)的值，則該樹(shù)一定是二叉排序樹(shù)”。該說(shuō)法是否正確，若認(rèn)為正確，則回答正確，若認(rèn)為不正確則說(shuō)明理由？(2)設(shè)有查找表7，16，4，8，20，9，6，18，5，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù). 對(duì)上述二叉樹(shù)給出后序遍歷的結(jié)果.9 (1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2) 一棵哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？10（1）對(duì)給定權(quán)值2，1，3，3，4，5，構(gòu)造哈夫曼樹(shù)。（2）同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹(shù)，使兩棵哈夫曼樹(shù)有不同的高度，并分別求兩棵樹(shù)的帶權(quán)路徑長(zhǎng)度。giabce

36、hfd11如圖所示的二叉樹(shù) （1）給出中序遍歷序列 （2）給出先序遍歷序列 （3）給出后序遍歷序列四、程序填空題1以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)行冒泡排序完成程序中的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; ;j+); flag=0; for(i=1; ;i+) if(ai.keyai+1.key)flag=1; temp=ai; ; ;if(flag= =0)break; 程序中flag的功能是 2以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程

37、序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。NODE *create(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= ; ;pnext=NULL; /*建立頭結(jié)點(diǎn)*/for(i=1; idata=i; p-next=NULL; q-next= ; ;return(head);3以下是用頭插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，要求結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為n,n-1,1，完成程序中空格部分。NODE *create2(n)NODE *head , *p, *q; int i; p=

38、(NODE*)malloc(sizeof(NODE);p-next=NULL;head= ; ;for(i=1; idata=i; if(i= =1) p-next=NULL; else p-next= ;q-next= ;return(head);4設(shè)線性表為（6，10，16，4），以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾結(jié)點(diǎn)*/head= ;a.next=&b;b.next

39、=&c;c.next=&d; ; /*以上結(jié)束建表過(guò)程*/p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/do printf(“%dn”, ); ; while( );5以下程序是先序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void Preorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 6以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void

40、Inorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 7以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void Postorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 8以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 void Inorder (struct BTreeNode *BT)ef

41、abcdif(BT!=NULL) （1） ; （2） ;Inorder(BT-right);利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是 ;綜合練習(xí)題答案一、單項(xiàng)選擇題1C 2D 3C 4D 5B 6C 7A 8B 9D 10C 11A 12C 13C 14B 15C 16A 17B 18A 19C 20A 21C 22B 23C 24A 25B 26C 27A 28D 29C 30B二、填空題物理（存儲(chǔ)） 有窮性、確定性、可行性、零個(gè)或多個(gè)輸入、一個(gè)或多個(gè)輸入3樹(shù)形 4n-1,O(n) 5乘法，O(n3) 6s-next=p-next; 7head 8q-next=p-next; 9p-next=head; 10s-next=h; 11h=h-next; 12r-next=s; 13f=f-next;14串長(zhǎng)度相