掌握:是指本課程最重要的知識點,能充分體現本課程的教學要求,要求學生在理解所學知識的基礎上能靈活應用。能結合課程的不同知識點解決綜合性的問題和簡單應用問題。
這部分是考核的重點內容。
(2) 考核方式
**電大統一命題,閉卷考試。
(3)組卷原則
在考核說明所規定的內容和要求之內命題。在教學內容範圍之內,按照理論聯絡實際原則,考察學生對所學知識應用能力的試題,不屬於超綱。
試題的難易程度和題量適當,按難易程度分為易、中、難三個層次:易佔25%,中佔45%,難佔30%。題量安排以大多數考生能在規定的考試時間內做完並有一定時間檢查為原則。
(4)試題型別及試卷結構
試題題型有單項選擇題、填空題、綜合題和程式填空題四種題型。試卷結構如下:
單項選擇題:每小題2分,共30分
填空題: 每小題2分,共24分
綜合題: 每小題10分,共30分
程式填空題:每空2分,共16分
共100分
(5)答題時限
答題時限為90分鐘。
二、考核內容和要求
第1章緒論(2學時)
[考核知識點]
1.資料結構的基本概念
2.演算法和演算法分析的基本概念
[考核要求]
1.理解資料結構的基本概念
2.掌握邏輯結構、物理結構的概念及相互關係
3.掌握本書介紹的四種基本結構的特點
4.理解演算法及其特性
5.了解演算法分析的一般概念
第2章線性表(8學時)
[考核知識點]
1.線性表的定義、邏輯結構、順序儲存結構、鏈式儲存結構
2.線性表在順序結構和鏈式結構上的基本操作和應用
3.雙向鍊錶、迴圈鍊錶的原理和相關操作
[考核要求]
1.理解線性表的定義及兩種儲存結構
2.理解線性表順序儲存的特點、實現方法和應用。
3.掌握順序表的基本操作(包括建立鍊錶、遍歷鍊錶、刪除、插入、查詢)和應用。特別要求能夠利用鍊錶的操作和相關的程式設計技術編制有一定難度的程式。
4.了解雙向鍊錶、迴圈鍊錶的原理和相關操作。
第3章棧和佇列(6學時)
[考核知識點]
1.棧的定義、棧的儲存結構(順序儲存、鏈式儲存)和基本操作、棧的應用
2.佇列的定義、佇列的儲存結構(順序儲存、鏈式儲存)、佇列的應用
3.迴圈佇列的概念和實現方法
[考核要求]
1.掌握棧和佇列的操作特點
2.理解順序棧、順序佇列的基本操作
3.了解在實際程式設計中棧和佇列的不同應用。理解迴圈佇列的概念、實現方法。掌握迴圈佇列判空、判滿的條件
4.能按照後續章節(例如二叉樹、排序等)的要求利用遞迴程式設計技術實現相關演算法
第4章串(2學時)
[考核知識點]
1.串型別定義、c語言中字串的特點和處理方法
2.串的順序儲存結構和鏈式儲存結構
3.串的基本運算和實現方法
[考核要求]
1.理解串的定義和儲存方法
2.了解串的基本操作和相關演算法
3.掌握用c語言處理字串的語法規則
第5章陣列和廣義表(2學時)
[考核知識點]
1.陣列的定義和儲存結構
2.特殊矩陣和稀疏矩陣的儲存結構
3.廣義表的定義和儲存結構
[考核要求]
1.了解陣列的儲存結構。
2.掌握特殊矩陣進行壓縮儲存的下標轉換公式。
3.理解稀疏矩陣的壓縮儲存原理。
4.掌握利用三元組表示稀疏矩陣的方法。
5.了解廣義表的概念和儲存結構。
第6章樹和二叉樹(10學時)
[考核知識點]
1.樹的基本概念
2.二叉樹的性質和儲存結構
3.二叉樹的遍歷和線索二叉樹
4.哈夫曼樹及其應用
[考核要求]
1.了解樹和二叉樹的定義
2.掌握二叉樹的基本性質,能利用相關性質解決簡單計算問題
3.了解二叉樹的順序儲存結構
4.掌握二叉樹的鏈式儲存結構、相關操作
5.掌握二叉樹的有關演算法並能程式設計實現
6.掌握利用遍歷序歷構造二叉樹的規則和具體步驟
7.掌握哈夫曼樹的定義、性質和構造方法
8.了解哈夫曼樹的應用
第7章圖(6學時)
[考核知識點]
1.圖的基本概念
2.圖的儲存結構
3.圖的遍歷
4.最小生成樹和最短路徑。
[考核要求]
1.了解圖的基本概念
2.掌握圖的儲存方法(鄰接矩陣、鄰接表)
3.掌握圖的深度優先和廣度優先遍歷的規則和步驟
4.理解在連通圖中求最小生成樹的方法。了解求圖的最短路徑等相關演算法及其應用
第8章查詢(6學時)
1.線性表的查詢(順序查詢、折半查詢、分塊查詢)。
2.二叉排序樹的查詢。
3.雜湊表(雜湊表的定義、雜湊函式的構造、處理衝突的方法、雜湊表的查詢和分析)。
[考核要求]
1.了解查詢的相關概念。
2.掌握順序表的查詢方法、步驟、程式實現、時間複雜度和平均查詢長度。
3.掌握在有序的順序表上進行折半查詢的方法、步驟、程式實現。
4.掌握折半查詢的判定樹的構造方法。能利用判定樹求平均查詢長度。
5.掌握二叉排序樹的確切定義,掌握建立二叉排序樹的步驟和方法。理解在二叉排序樹中進行輸入、刪除操作的規則。
6.了解雜湊表的相關概念和原理,了解常用雜湊函式的構造和處理衝突的方法。理解雜湊函式和雜湊表的關係及在查詢中的應用。
第9章排序(6學時)
[考核知識點]
1.插入排序(直接插入排序、希爾排序)
2.交換排序(氣泡排序、快速排序)
3.選擇排序(簡單選擇排序、堆排序)
4.歸併排序
[考核要求]
1.掌握教材中介紹的各種排序演算法的基本原理、步驟。
2.能針對小規模具體例項,按相關排序演算法的規則人工完成排序;能通過分析排序的中間結果判斷所用的排序演算法。
3.能正確理解相關排序演算法的程式例項,並重點掌握演算法中的關鍵步驟和關鍵語句。
4.掌握堆和特殊的完全二叉樹的對應關係。掌握建堆、篩選演算法和完全二叉樹相關操作的對應關係。
三、試題型別及答案
一、單項選擇題(每小題2分,共30分)
1.資料結構中,與所使用的計算機無關的是資料的( )結構。
a. 邏輯 b. 物理 c. 儲存d. 邏輯與物理
2.下述各類表中可以隨機訪問的是( )。
a. 單向鍊錶 b. 雙向鍊錶 c.單向迴圈鍊錶 d.順序表
3.在乙個長度為n的順序表中為了刪除第5個元素,從前到後依次移動了15個元素。則原順序表的長度為( )。
a. 21b. 20c. 19d. 25
4.元素2,4,6按順序依次進棧,則該棧的不可能的輸出序列是( )。
a. 6 4 2 b. 6 2 4 c. 4 2 6 d. 2 6 4
5.乙個佇列的入隊序列是5,6,7,8,則佇列的輸出序列是( )。
a. 5 6 7 8b. 8 7 6 5
c. 7 8 6 5d.可能有多種情況
6. 串函式strcmp(「d」,「d」)的值為( )。
a.0b.1c.-1d.3
7.在乙個單鏈表中,p、q分別指向表中兩個相鄰的結點,且q所指結點是p所指結點的直接後繼,現要刪除q所指結點,可用語句( )。
a.p=qnext b.pnext=q c.pnext=qnext d.qnext=null
8.設一棵哈夫曼樹共有n個非葉結點,則該樹一共有( )個結點。
a. 2*n-1 b. 2*n +1 c. 2*n d. 2*(n-1)
9.對如圖1所示二叉樹進行中序遍歷,結果是( )。
a. dfebagc b. defbagc c. defbacg
10 . 任何乙個無向連通圖的最小生成樹( )。
a.至少有一棵 b.只有一棵 c.一定有多棵 d.可能不存在
11.設有乙個10階的對稱矩陣a,採用壓縮儲存的方式,將其下三角部分以行序為主序儲存到一維陣列b中(陣列下標從1開始),則矩陣中元素a8,5在一維陣列b中的下標是( )。
a.33b.32c.85d.41
12 . 一組記錄的關鍵字序列為(37,70,47,29,31,85),利用快速排序,以第乙個關鍵字為分割元素,經過一次劃分後結果為( )。
a.31,29,37,85,47,70 b.29,31,37,47,70,85
c.31,29,37,70,47,85 d.31,29,37,47,70,85
13 . 對n個元素進行氣泡排序,要求按公升序排列,程式中設定某一趟冒泡沒有出現元素交換,就結束排序過程。對某n個元素的排序共進行了3n-6次元素間的比較就完成了排序,則( )。
a.原序列是公升序排列
b.原序列是降序排列
c.對序列只進行了2趟冒泡
d. 對序列只進行了3趟冒泡
14.在乙個棧頂指標為top的鏈棧中刪除乙個結點時,用x儲存被刪除的結點,應執行( )。
>data;top=top->next; b. top=top->next ; x=top;
>nextd. x=top->data;
15.串函式strcat(a,b)的功能是進行串( )。
a.比較 b.複製 c.賦值 d.連線
二、填空題(每小題2分,共24分)
1.在乙個單向鍊錶中p所指結點之後插入乙個s所指的新結點,應執行s->next=p->next;和______操作。
2.根據資料元素間關係的不同特性,通常可分為四類基本結構。
3.在乙個鏈隊中,設f和r分別為隊頭和隊尾指標,則刪除乙個結點的操作為結點的指標域為next)
4.________遍歷二叉排序樹可得到乙個有序序列。
資料結構題目說明
題目說明 1.運動會分數統計 限3人完成 任務 參加運動會有n個學校,學校編號為1 n。比賽分成m個男子專案,和w個女子專案。專案編號為男子1 m,女子m 1 m w。不同的專案取前五名或前三名積分 取前五名的積分分別為 7 5 3 2 1,前三名的積分分別為 5 3 2 哪些取前五名或前三名由學生...
資料結構本教學大綱
資料結構 本 課程教學大綱 第一部分大綱說明 一 課程的性質與任務 資料結構 本 是 廣播電視大學電腦科學與技術本科專業 專科起點 的統設必修 學位課程。本課程4學分,72學時,其中實驗24學時,開設一學期。資料結構 本 是計算機科學技術與專業的一門重要的專業基礎課。主要介紹如何合理地組織資料 有效...
《資料結構》實踐環節考核指導
讀過一本好書,像交了乙個益友。藏克家 一 型別 課程實驗考核 二 目的與要求 本課程的目的和任務是使學習者掌握各種常用的資料結構和典型演算法,為學習後續計算機專業課程提供必要的基礎,提高學習者運用資料結構解決實際問題的能力。本考核主要達到兩個目的 1 檢查學生對資料的邏輯結構 儲存結構以及演算法的理...