云南廣播電視大學職業(yè)技術(shù)學院五年制高職教育2004

1、云南廣播電視大學職業(yè)技術(shù)學院五年制高職教育2004 2005 學年度第一學期計算機應用專業(yè) 2001 、2002 級第七、五學期數(shù)據(jù)結(jié)構(gòu)期末復習指導責任教師 伍嘉一、期末復習的基本要求：本課程期末復習的總要求為： 理解：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)算法的時間量度等基本概念；線性表、單向鏈表的基本概念 及其特點；單鏈表中插入或刪除一個元素的基本操作；棧的概念；順序棧的特點；隊列的基本運算；鏈接 方式存儲隊列的刪除運算；二叉樹的概念及特點。掌握：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點；單向鏈表中附加一個頭結(jié)點的作用；線性表的鏈示存儲結(jié) 構(gòu)；棧和隊列的區(qū)別等。熟練掌握：順序表（有序）插入元素的算法

2、；先序、中序、后序、遍歷二叉樹。二、命題原則及題型： 1命題原則：考試立足于主教材及學習指導手冊，各章節(jié)教學要求中的熟練掌握部分為重點考核內(nèi)容， 掌握部分為主要考核內(nèi)容，了解部分的內(nèi)容占的比例較少或不作考試內(nèi)容。2題型及題量：填空題（ 20 空，20 分）、單選題（ 10 題，30 分）、簡答題（ 5題，30 分）、算法題（ 2 題， 20 分）。三、各章復習要點：第一章 緒論理解：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)算法的時間量度等基本概念。第二章 線性表 理解：線性表、單向鏈表的基本概念及其特點；單鏈表中插入或刪除一個元素的基本操作。掌握：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點；單向鏈表中附加一

3、個頭結(jié)點的作用；線性表的順序存儲結(jié) 構(gòu)；線性表的鏈示存儲結(jié)構(gòu)等。熟練掌握：順序表（有序）插入元素的算法。第三章 棧和隊列 理解：棧和隊列的概念；順序棧的特點；隊列的基本運算；鏈接方式存儲隊列的刪除運算。掌握：棧和隊列的區(qū)別等。第六章 樹 理解：二叉樹的概念及特點。熟練掌握：先序、中序、后序、遍歷二叉樹。第八章 查找 理解：二分法查找。熟練掌握：順序查找的函數(shù)算法；折半查找的函數(shù)算法。第九章 排序熟練掌握：直接插入排序、冒泡排序、快速排序的原理。四、期末復習題一、填空題1、數(shù)據(jù)是描述客觀事物的以及所有能輸入到計算機中并被計算機處理的的總稱。2、是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮

4、和處理。，是數(shù)據(jù)的一個子集。4、線性表是指個具有相同類型數(shù)據(jù)元素 （ 或稱結(jié)點 ）的有限序列，可表示為 （a1 ，a2 ，ai ， an） 。 其 中 ， ai 代 表， （a1 稱 為 表 頭（或），an 稱為表尾（ 或),ai (0 <i<n) 稱為 ai +1ai+1ai稱為線性表的長度，長度為的線性表稱為空表，記為的增大，算法執(zhí)行時，簡稱時間復雜用來存放一個數(shù)5 、算法的時間量度記作，表示隨著間的增長率和 的增長率相同， 稱做度。6、為表示相鄰數(shù)據(jù)元素之間的邏輯關(guān)系，將每個存儲結(jié)點分為兩個域：據(jù)元素的自身信息；用來存放該數(shù)據(jù)元素直接后繼的存儲位置。這樣，可以通過 中存放的信

5、息 （ 稱為 ） 將 n 個結(jié)點連接成一個鏈表， 即成為線性表的鏈式存儲結(jié)構(gòu)。由于這種存儲結(jié)構(gòu)中每個結(jié)點只有一個指針域，故又將其稱為 或 。7、 若 S 為一棧， 則為空棧，意為滿棧。為棧底元素，為棧頂元素。二、單選題1、以下數(shù)據(jù)結(jié)構(gòu)中 （） 是一個線性結(jié)構(gòu)。A. 有向圖B. 棧C. 線索二叉樹D. B 樹2、在一個單鏈表中，若要向表中第 i個結(jié)點前（用p指向i的前一結(jié)點）插入一個由指針 s指向的結(jié)點, 則執(zhí)行 （ ） 。A. s->next =p; p->next=s;B. s->next=p->next; p->next =s;C. p->next=s;

6、 p=s->next;D. p->next=s->next; s->next=p;A. p->next =p;B. p->next=p->next->next;C. p->next=s; p=s->next;D. p->next=s->next; s->next=p;4、（) 是順序存儲方式的優(yōu)點。A. 存儲密度大B. 插入運算方便C. 刪除運算方便D. 以上全部5、（) 不是隊列的基本運算。A. 從隊尾插入一個新元素B. 從隊列中刪除第 i 個元素D. 讀取隊頭元素的值C.判斷一個隊列是否為空三、簡答題1、試對棧和隊列進行比較2、單向鏈表中附加一個頭結(jié)點的作用。3、假定一棵二叉樹如圖所示，分別寫出對它進行先序、中序、后序、遍歷的結(jié)果。4、與普通樹比較，二叉樹有什么特點？四、算法題1、 寫出折半查找的函數(shù)算法。其功能是在