數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提要

1、1《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)提要清華大學(xué)計(jì)算機(jī)系殷人昆《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。用數(shù)字計(jì)算機(jī)解決任何應(yīng)用問題都離不開數(shù)據(jù)表示和數(shù)據(jù)處理，使用面向?qū)ο蠹夹g(shù)開發(fā)軟件，數(shù)據(jù)表示更成為軟件構(gòu)成的基礎(chǔ)。而數(shù)據(jù)表示和數(shù)據(jù)處理的核心問題之一就是數(shù)據(jù)結(jié)構(gòu)及其操作的實(shí)現(xiàn)。這正是《數(shù)據(jù)結(jié)構(gòu)》課程的內(nèi)容。從這個(gè)意義上來說《數(shù)據(jù)結(jié)構(gòu)》課程在知識(shí)學(xué)習(xí)和技能培養(yǎng)兩個(gè)方面都處于關(guān)鍵地位。一、課程要求《數(shù)據(jù)結(jié)構(gòu)》是電大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科

2、生的專業(yè)基礎(chǔ)課程之一，該課程是后續(xù)課程如操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等課程的先修課程，在整個(gè)教學(xué)體系中占據(jù)非常重要的地位。該課程主要討論在軟件開發(fā)中如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)。因此，用抽象數(shù)據(jù)類型以及面向?qū)ο蟮姆椒ńM織、存儲(chǔ)各種類型的數(shù)據(jù)是本課程的重點(diǎn)，也是學(xué)員需要掌握的重點(diǎn)。面向?qū)ο蠓椒ㄒ约敖Y(jié)構(gòu)化技術(shù)都是建立高質(zhì)量軟件的技術(shù)，通過《數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)和實(shí)踐，可以加深對(duì)這些先進(jìn)軟件開發(fā)方法的理解和體會(huì)。因此，《數(shù)據(jù)結(jié)構(gòu)》課程的任務(wù)是按照軟件

3、工程思想，介紹用面向過程和面向?qū)ο蠓椒ㄟM(jìn)行數(shù)據(jù)設(shè)計(jì)和程序設(shè)計(jì)的基本思想，在必要的課程實(shí)踐中逐步熟練掌握。通過本課程的學(xué)習(xí)，應(yīng)達(dá)到知識(shí)和技能兩方面的目標(biāo)：1、知識(shí)方面：從數(shù)據(jù)結(jié)構(gòu)的類定義和對(duì)象的使用，以及存儲(chǔ)表示和操作的實(shí)現(xiàn)兩個(gè)層次，系統(tǒng)地學(xué)習(xí)和掌握常用的基本數(shù)據(jù)結(jié)構(gòu)(包括數(shù)組、順序表、多項(xiàng)式、字符串、鏈表、棧與隊(duì)列、優(yōu)先級(jí)隊(duì)列、廣義表、樹與森林、二叉樹、堆、集合、圖、搜索結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)等)及其不同的實(shí)現(xiàn)，了解并掌握分析、比較和

4、選擇不同數(shù)據(jù)結(jié)構(gòu)、不同存儲(chǔ)結(jié)構(gòu)、不同算法的原則和方法，為后續(xù)課程的學(xué)習(xí)打好基礎(chǔ)。2、技能方面：系統(tǒng)地學(xué)習(xí)和掌握對(duì)象類的設(shè)計(jì)方法和面向?qū)ο蟮某绦蛟O(shè)計(jì)風(fēng)格，在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的算法的設(shè)計(jì)思想，從中體會(huì)和掌握選擇結(jié)構(gòu)的方法和算法設(shè)計(jì)的思考方式及技巧，提高分析問題和解決問題的能力。二、考核要求1、命題依據(jù)命題依據(jù)是電大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生《數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱》。2、考核要求本課程考核的重點(diǎn)是考察學(xué)員對(duì)各種數(shù)據(jù)結(jié)構(gòu)的理解程度和基于這些數(shù)據(jù)

5、結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)的能力。具體考核要求分為幾個(gè)層次：?理解：要求學(xué)員理解各種數(shù)據(jù)結(jié)構(gòu)的層次、各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、各種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的基本思想。?掌握：要求學(xué)員能較好地理解和運(yùn)用一兩個(gè)知識(shí)點(diǎn)進(jìn)行簡(jiǎn)單的算法設(shè)計(jì)。?綜合應(yīng)用：要求學(xué)員能綜合運(yùn)用多個(gè)知識(shí)點(diǎn)的內(nèi)容進(jìn)行比較復(fù)雜的應(yīng)用程序開發(fā)。3、命題原則?在教學(xué)大綱和考核說明所規(guī)定的目的、要求和內(nèi)容范圍之內(nèi)命題。3B：?必須是連續(xù)的?部分地址必須是連續(xù)的?一定是不連續(xù)的?可連續(xù)可不連續(xù)C：?n?n2?

6、(n1)2?(n1)2D：?s→link=p→linkp→link=s?p→link=ss→link=q?p→link=s→links→link=p?q→link=ss→link=pE：?起泡排序?堆排序?錦標(biāo)賽排序?快速排序F：?求子串?模式匹配?串替換?串連接G：?80?100?240?270H：?棧?隊(duì)列?循環(huán)隊(duì)列?優(yōu)先隊(duì)列I：?4321?2431?1234?3214J：?(frontrear1)%m?(rearfront1)%m

7、?(frontrearm)%m?(rearfrontm)%m二、閱讀理解題[給出下列遞歸過程的執(zhí)行結(jié)果](1)voidunknown(intw)if(w)unknown(w1)f(inti=1i=wi)coutwcoutendl調(diào)用語句為unknown(4)。(2)voidunknown(intn)coutn%10if(int(n10))unknown(int(n10))調(diào)用語句為unknown(582)。(3)intunknown(i

8、ntm)intvalueif(!m)value=3elsevalue=unknown(m1)5returnvalue執(zhí)行語句為coutunknown(3)。三、填空題設(shè)單鏈表結(jié)構(gòu)為structListNodeintdataListNodelink下面的程序是以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二路歸并排序的算法要求鏈表不另外占用存儲(chǔ)空間排序過程中不移動(dòng)結(jié)點(diǎn)中的元素只改各鏈結(jié)點(diǎn)中的指針排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。在初始狀態(tài)下所有待排序記錄鏈接在