數據結構復習提要

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

2、生的專業(yè)基礎課程之一，該課程是后續(xù)課程如操作系統(tǒng)、計算機網絡等課程的先修課程，在整個教學體系中占據非常重要的地位。該課程主要討論在軟件開發(fā)中如何進行數據結構和算法的設計。因此，用抽象數據類型以及面向對象的方法組織、存儲各種類型的數據是本課程的重點，也是學員需要掌握的重點。面向對象方法以及結構化技術都是建立高質量軟件的技術，通過《數據結構》課程的學習和實踐，可以加深對這些先進軟件開發(fā)方法的理解和體會。因此，《數據結構》課程的任務是按照軟件

3、工程思想，介紹用面向過程和面向對象方法進行數據設計和程序設計的基本思想，在必要的課程實踐中逐步熟練掌握。通過本課程的學習，應達到知識和技能兩方面的目標：1、知識方面：從數據結構的類定義和對象的使用，以及存儲表示和操作的實現兩個層次，系統(tǒng)地學習和掌握常用的基本數據結構(包括數組、順序表、多項式、字符串、鏈表、棧與隊列、優(yōu)先級隊列、廣義表、樹與森林、二叉樹、堆、集合、圖、搜索結構、索引結構、散列結構等)及其不同的實現，了解并掌握分析、比較和

4、選擇不同數據結構、不同存儲結構、不同算法的原則和方法，為后續(xù)課程的學習打好基礎。2、技能方面：系統(tǒng)地學習和掌握對象類的設計方法和面向對象的程序設計風格，在不同的存儲結構上實現的算法的設計思想，從中體會和掌握選擇結構的方法和算法設計的思考方式及技巧，提高分析問題和解決問題的能力。二、考核要求1、命題依據命題依據是電大計算機科學與技術專業(yè)本科生《數據結構教學大綱》。2、考核要求本課程考核的重點是考察學員對各種數據結構的理解程度和基于這些數據

5、結構進行算法設計的能力。具體考核要求分為幾個層次：?理解：要求學員理解各種數據結構的層次、各種數據結構的特點、各種數據結構設計的基本思想。?掌握：要求學員能較好地理解和運用一兩個知識點進行簡單的算法設計。?綜合應用：要求學員能綜合運用多個知識點的內容進行比較復雜的應用程序開發(fā)。3、命題原則?在教學大綱和考核說明所規(guī)定的目的、要求和內容范圍之內命題。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：?起泡排序?堆排序?錦標賽排序?快速排序F：?求子串?模式匹配?串替換?串連接G：?80?100?240?270H：?棧?隊列?循環(huán)隊列?優(yōu)先隊列I：?4321?2431?1234?3214J：?(frontrear1)%m?(rearfront1)%m

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

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