在日常的學(xué)習(xí)、工作、生活中，肯定對各類范文都很熟悉吧。相信許多人會覺得范文很難寫？以下是小編為大家收集的優(yōu)秀范文，歡迎大家分享閱讀。
數(shù)據(jù)結(jié)構(gòu)資源篇一
課程編號：030816 適用專業(yè)：教育技術(shù)學(xué) 總學(xué)時數(shù)：64
學(xué) 分：4 編制單位：茂名學(xué)院理學(xué)院教育與信息技術(shù)系 編制時間：2008年6月20日
一、課程地位、性質(zhì)和任務(wù)
《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計算機相關(guān)學(xué)科專業(yè)的基礎(chǔ)課程中的一門重要的核心課程。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據(jù)問題設(shè)計和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計應(yīng)用程序打下基礎(chǔ)。
本課程以提高學(xué)生的計算機應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計高效的算法，提高程序設(shè)計能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學(xué)生的程序設(shè)計能力。
二、與其他課程的關(guān)系
先修課：程序設(shè)計基礎(chǔ)、離散數(shù)學(xué)、計算機組成原理、計算機文化基礎(chǔ)
三、教學(xué)內(nèi)容、課時安排和基本要求
（一）教學(xué)部分 第1章 緒論（2學(xué)時）1.1什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語
1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)
1.4 算法和算法分析（算法及其設(shè)計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解
基本要求：
了解：抽象數(shù)據(jù)類型，算法設(shè)計方法與算法分析。
掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、算法的基本概念；問題求解的方法與步驟 重點：數(shù)據(jù)結(jié)構(gòu)和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標(biāo)準(zhǔn)和評價方法，最壞情況和平均情況的區(qū)分。
第2章 線性表（8學(xué)時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)
2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表）2.4 一元多項式的表示及相加
基本要求：
了解：兩種存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)）及一元多項式的表示及相加。
掌握：要求熟練掌握處理線性表的各種算法。為后繼章節(jié)的學(xué)習(xí)打基礎(chǔ)。重點：各種算法。難點：鏈表的理解。
第3章 棧與隊列（4學(xué)時）
3.1 棧（定義，棧的表示和實現(xiàn)）
3.2 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號匹配的檢驗，行編輯程序，迷宮求解，表達(dá)式求值）
3.3 棧與遞歸的實現(xiàn)
3.4 隊列及其實現(xiàn)（定義，鏈隊列，循環(huán)隊列）3.5 *離散事件模擬
教學(xué)要求：熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。棧和隊列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)。
基本要求：
了解： 棧和隊列的定義及其實現(xiàn)。
掌握： 熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。重點： 棧和隊列的算法實現(xiàn)。難點： 棧和隊列的算法實現(xiàn)。
第4章 串（2學(xué)時）4.1 串類型的定義
4.2 串的表示和實現(xiàn)（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進(jìn)算法）4.4 串操作應(yīng)用舉例（文本編輯，建立詞索引表）
基本要求：
了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應(yīng)用。
第5章 數(shù)組（2學(xué)時）5.1 數(shù)組的定義
5.2 數(shù)組的順序表示和實現(xiàn)
5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結(jié)構(gòu) 5.6 m元多項式的表示
5.7 廣義表的遞歸算法（求廣義表的深度，復(fù)制廣義表，建立廣義表的存儲結(jié)構(gòu)）
基本要求：
了解：了解作為抽象數(shù)據(jù)類型的數(shù)組和c語言的數(shù)組。認(rèn)識到數(shù)組可以作為順序存儲結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實現(xiàn)。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。
掌握：掌握基本概念和算法。重點：算法。
難點：廣義表的遞歸算法。
第6章 樹與二叉樹（15學(xué)時）6.1 樹的定義和基本術(shù)語
6.2 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲結(jié)構(gòu)）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）
6.4 樹和森林（樹的存儲結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷）6.5 樹與等價問題
6.6 赫夫曼樹及其應(yīng)用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數(shù)
基本要求：
了解：理解樹與森林的定義與術(shù)語。
掌握：熟練掌握二叉樹性質(zhì)和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構(gòu)造的方法和算法。重點： 樹的存儲結(jié)構(gòu)和遍歷算法。難點：哈夫曼樹構(gòu)造的方法和算法
第7章 圖（11學(xué)時）7.1 圖的定義和術(shù)語
7.2 圖的存儲結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索）
7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關(guān)節(jié)點和重連通分量）
7.5 有向無環(huán)圖及其應(yīng)用（拓?fù)渑判?，關(guān)鍵路徑）
7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：
了解：圖的基本概念和相關(guān)術(shù)語。
掌握：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。掌握最小生成樹、最短路徑和活動網(wǎng)算法的思想。
重點：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。難點：圖的遍歷算法，最短路徑算法。
第8章 查找（8學(xué)時）
9.1 靜態(tài)查找表（順序表，有序表，靜態(tài)樹表，索引順序表）9.2 動態(tài)查找表（二叉排序樹和平衡二叉樹，b_樹和b+樹，鍵樹）9.3 哈希表（定義，構(gòu)造方法，處理沖突的方法，查找及其分析）
基本要求：
了解： 各種查找法的基本概念及實現(xiàn)的基本思想。
掌握：熟練掌握搜索結(jié)構(gòu)的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現(xiàn)。難點：哈希表查找算法。
第9章 內(nèi)部排序（8學(xué)時）10.1 概述
10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序
10.6 基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?0.7 排序算法分析
基本要求：
了解：基數(shù)排序，排序算法分析方法
掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內(nèi)部排序算法
難點：基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?BR> 第10章 *外部排序（2學(xué)時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現(xiàn) 11.4 置換-選擇排序 11.5 最佳歸并樹
基本要求：
了解：外部排序的基本概念和相關(guān)術(shù)語。
掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現(xiàn) 第11章 算法設(shè)計的一般方法（2學(xué)時）
1．重點
（1）有效算法的概念，問題固有難度的概念；
（2）遞歸法；分治法；平衡原則；貪心法；動態(tài)規(guī)劃的基本原理；（3）搜索-回溯法的基本原理和本質(zhì).2．難點
（1）問題固有難度的概念；
（2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。
（二）實驗、實習(xí)部分
課程安排五個類別的實驗，實驗時數(shù)為12課時，其中： 實驗
一、線性鏈表及運算 2課時 實驗
二、棧和隊列 2課時 實驗
三、樹和二叉樹 4課時 實驗
四、圖及其應(yīng)用 2課時 實驗
五、查找與排序 2課時
四、課程考核方式
閉卷考試70%、平時作業(yè)與實驗30%
五、建議教材和教學(xué)參考書 參考教材：
1、《數(shù)據(jù)結(jié)構(gòu)》（c語言描述）高等教育出版社 耿國華主編
2、《數(shù)據(jù)結(jié)構(gòu)》（c語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者
3、《數(shù)據(jù)結(jié)構(gòu)題集》（c語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者
4、《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及解析（第二版）西安電子科技大學(xué)出版社 高一凡
六、說明
1、因課時安排少，教學(xué)內(nèi)容多。建議采用多媒體教學(xué)。
2、由于本課程內(nèi)容較多，在實際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。
數(shù)據(jù)結(jié)構(gòu)資源篇二
數(shù)據(jù)結(jié)構(gòu)】二叉排序樹的建立，查找，插入和刪除實踐題 /*sy53.c*/
#include
#include
typedef int keytype;
typedef struct node{
keytype key;
struct node *lchild,*rchild;
}bstnode;
typedef bstnode *bstree;
bstree createbst(void);
void searchbst(bstree t,keytype key);
void insertbst(bstree *tptr,keytype key);
void delbstnode(bstree *tptr,keytype key);
void inorderbst(bstree t);
main()
{bstree t;
char ch1,ch2;
keytype key;
printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);
t=createbst();
ch1='y';
while(ch1=='y' || ch1=='y')
{printf(“請選擇下列操作：n”);
printf(“1------------------更新二叉排序樹存儲n”);
printf(“2------------------二叉排序樹上的查找n”);
printf(“3------------------二叉排序樹上的插入n”);
printf(“4------------------二叉排序樹上的刪除n”);
printf(“5------------------二叉排序樹中序輸出n”);
printf(“6------------------退出n”);
scanf(“n%c”,&ch2);
switch(ch2)
{case '1':t=createbst();break;
case '2':printf(“n請輸入要查找的數(shù)據(jù)：”);
scanf(“n%d”,&key);
searchbst(t,key);
printf(“查找操作完畢。n”);break;
case '3': printf(“n請輸入要插入的數(shù)據(jù)：”);
scanf(“n%d”,&key);
insertbst(&t,key);
printf(“插入操作完畢。n”);break;
case '4': printf(“n請輸入要刪除的數(shù)據(jù)：”);
scanf(“n%d”,&key);
delbstnode(&t,key);
printf(“刪除操作完畢。n”);break;
case '5': inorderbst(t);
printf(“n二叉排序樹輸出完畢。n”);break;
case '6':ch1='n';break;
default:ch1='n';
}
}
}
bstree createbst(void)
{bstree t;
keytype key;
t=null;
printf(“請輸入一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“%d”,&key);
while(key)
{insertbst(&t,key);
printf(“請輸入下一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“n%d”,&key);
}
return t;
}
void searchbst(bstree t, keytype key)
{ bstnode *p=t;
while(p)
{if(p->key==key)
{printf(“已找到n”);
return;
}
p=(key
key)? p->lchild:p->rchild;
}
printf(“沒有找到n”);
}
void insertbst(bstree *t,keytype key)
{bstnode *f,*p;
p=(*t);
while(p)
{if(p->key==key)
{printf(“樹中已有key不需插入n”);
return;
}
f=p;
p=(key
key)?p->lchild:p->rchild;
}
p=(bstnode*)malloc(sizeof(bstnode));
p->key=key;
p->lchild=p->rchild=null;
if((*t)==null)(*t)=p;
else if(key
key)f->lchild=p;
else f->rchild=p;
}/*insertbst*/
void delbstnode(bstree *t,keytype key)
{bstnode *parent=null, *p, *q,*child;
p=*t;
while(p)
{if(p->key==key)break;
parent=p;
p=(key
key)?p->lchild:p->rchild;
}
if(!p){printf(“沒有找到要刪除的結(jié)點n”);return;}
q=p;
if(q->lchild && q->rchild)
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;
if(!parent)*t=child;
else {if(p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
if(p!=q)
q->key=p->key;
}
free(p);
}
void inorderbst(bstree t){ if(t!=null)
{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}
}
數(shù)據(jù)結(jié)構(gòu)資源篇三
數(shù)據(jù)結(jié)構(gòu)參考題目
一、選擇
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）
a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復(fù)雜度為（）for(i=0;i
next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.兩個字符串相等的條件是（）
a.串的長度相等 b.含有相同的字符集
c.都是非空串 d.串的長度相等且對應(yīng)的字符相同 5．若以s和x分別表示進(jìn)棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（）
xx sx sx xx 6.已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進(jìn)行排序時，前兩趟排序的結(jié)果為
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序
8.已知散列表的存儲空間為t[0..16]，散列函數(shù)h（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關(guān)鍵字：t[5]=39，t[6]=57和t[7]=7，則下一個關(guān)鍵字23插入的位置是（）
a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個子表，整個矩陣看成是一個廣義表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為dout，則所有頂點的入度之和為（）
-1 +1 d.n 11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）a線性結(jié)構(gòu) b.樹形結(jié)構(gòu) c.線性結(jié)構(gòu)和樹型結(jié)構(gòu) d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)
12．棧的插入和刪除操作在()進(jìn)行。
a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）a.24 b.71 c.48 d.53 14．一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關(guān)于棧和隊列的說法中正確的是（）
a．棧和隊列都是線性結(jié)構(gòu) b.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu) c.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu) d.棧和隊列都不是線性結(jié)構(gòu) 16．關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（）a．順序存儲比鏈?zhǔn)酱鎯ι僬伎臻g b.順序存儲比鏈?zhǔn)酱鎯Χ嗾伎臻g
c.順序存儲和鏈?zhǔn)酱鎯Χ家笳加谜麎K存儲空間 d.鏈?zhǔn)酱鎯Ρ软樞虼鎯﹄y于擴充空間
17．已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；
18．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時，s語句被執(zhí)行的次數(shù)為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結(jié)點的時間復(fù)雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）
a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．關(guān)于串的敘述中，正確的是（）a．空串是只含有零個字符的串 b.空串是只含有空格字符的串
c.空串是含有零個字符或含有空格字符的串
d.串是含有一個或多個字符的有窮序列
23．在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）
a．front==rear
b.(front+1)%m==rear
+1==front
d.(rear+1)%m==front 24．設(shè)有二維數(shù)組
?1????a［n］［n］表示如下：?23456??????????，則a［i］［i］（0≤i≤n-1）的d.i2/2 值為（）
a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）
ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）
-1 c.n(m-1)d.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）a.矩陣中非全零元素的行數(shù)等于圖中的頂點數(shù)
b.第i行上與第i列上非零元素總和等于頂點vi的度數(shù) c.矩陣中的非零元素個數(shù)等于圖的邊數(shù)
d.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等
29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）a.1 b.2 c.3 d.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）
a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81
二、填空題
1.數(shù)據(jù)是計算機加工處理的對象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面()。
3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進(jìn)先出的線性表（）。
5.從循環(huán)鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的前驅(qū)結(jié)點（）。6.單鏈表設(shè)置頭結(jié)點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）。
9.從非循環(huán)鏈表的某一結(jié)點出發(fā)，既能找到它的后繼結(jié)點，又能找到它的前驅(qū)結(jié)點（）。
10.單鏈表結(jié)點的指針域是用來存放其直接后繼結(jié)點的首地址的（）
11.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象（）。
12.用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。
13.在非線性結(jié)構(gòu)中，至少存在一個元素不止一個直接前驅(qū)或不止一個直接后驅(qū)（）。14.樹的最大特點是一對多的層次結(jié)構(gòu)（）。15.隊列的特點是先進(jìn)先出（）。
16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨立于計算機（）。18.線性表簡稱為”順序表”。（）
19.對數(shù)據(jù)的任何運算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點出發(fā)，可以找到表中的所有結(jié)點（）。21.棧是一種先進(jìn)先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。
27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型（）。
28.線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進(jìn)后出的線性表（）。
30.將插入和刪除限定在表的同一端進(jìn)行的線性表是隊列（）。
三、畫圖題
1.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={a,b,c,d,e,f,g,h,i,j} r={,,
,
,
,
,
,
,
} 3．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={1,2,3,4,5} r={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) k={0,1,2,3,4,5,6,7} r={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}
四、運算題
1．已知一個圖的頂點集v和邊集h分別為：
v＝{0，1，2，3，4，5，6，7}
e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。
2.一個線性表為b=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為ht[0..12]，散列函數(shù)為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。
平均查找長度：（寫出計算過程）
3．已知一個圖的頂點集v和邊集h分別為：
v＝{0，1，2，3，4，5，6，7}
e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發(fā)）
____
__，___
_，___
___，__
____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：
前序： 中序： 后序：
5.設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。
五、編程題
1.請編寫一個算法，實現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：
int search_bin(keytype k,sstable st){ 3.請編寫一個算法，實現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點）。linklist *invertlink(linklist *h){
數(shù)據(jù)結(jié)構(gòu)資源篇四
實驗：線性表的基本操作
【實驗?zāi)康摹?BR> 學(xué)習(xí)掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的設(shè)計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法。
【實驗內(nèi)容】
1.順序表的實踐
1)建立4個元素的順序表s=sqlist[]={1，2，3，4，5}，實現(xiàn)順序表建立的基本操作。
2)在sqlist []={1，2，3，4，5}的元素4和5之間插入一個元素9，實現(xiàn)順序表插入的基本操作。
3)在sqlist []={1，2，3，4，9，5}中刪除指定位置（i=5）上的元素9，實現(xiàn)順序表的刪除的基本操作。2.單鏈表的實踐
3.1)建立一個包括頭結(jié)點和4個結(jié)點的（5，4，2，1）的單鏈表，實現(xiàn)單鏈表建立的基本操作。
2)將該單鏈表的所有元素顯示出來。
3)在已建好的單鏈表中的指定位置（i=3）插入一個結(jié)點3，實現(xiàn)單鏈表插入的基本操作。
4)在一個包括頭結(jié)點和5個結(jié)點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結(jié)點，實現(xiàn)單鏈表刪除的基本操作。5)實現(xiàn)單鏈表的求表長操作。
【實驗步驟】
1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中，碰到的第一個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。通過學(xué)習(xí)我知道了對線性表進(jìn)行建立、插入、刪除，同時單鏈表也是進(jìn)行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復(fù)雜度均為0（n）.通過這次的學(xué)習(xí)，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念。總之，這次實驗我找到了自己的不足之處，以后會努力的。
實驗二：棧的表示與實現(xiàn)及棧的應(yīng)用
【實驗?zāi)康摹?BR> （1）掌握棧的順序存儲結(jié)構(gòu)及其基本操作的實現(xiàn)。（2）掌握棧后進(jìn)先出的特點，并利用其特性在解決實際問題中的應(yīng)用。（3）掌握用遞歸算法來解決一些問題?！緦嶒瀮?nèi)容】
1.編寫程序，對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，輸出與其等值的八進(jìn)制數(shù)。
2.編寫遞歸程序，實現(xiàn)n！的求解。3.編寫遞歸程序，實現(xiàn)以下函數(shù)的求解。
n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1
4.編寫程序，實現(xiàn)hanoi塔問題?！緦嶒灢襟E】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
通過這次的學(xué)習(xí)我掌握了棧這種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭端稱為棧底（botton）；棧又稱為后進(jìn)先出（last in first out）的線性表,簡稱lifo結(jié)構(gòu)，因為它的修改是按后進(jìn)先出的原則進(jìn)行的。
加上這個實驗，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學(xué)習(xí)有很大的作用，可以說這是學(xué)習(xí)以后知識的總要基礎(chǔ)。
實驗三：二叉樹的建立及遍歷
【實驗?zāi)康摹?BR> （1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法?！緦嶒瀮?nèi)容】
1.編寫程序，實現(xiàn)二叉樹的建立，并實現(xiàn)先序、中序和后序遍歷。如：輸入先序序列abc###de###，則建立如下圖所示的二叉樹。
并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實驗步驟】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
這次試驗是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實驗中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數(shù)的計算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗不太好做，期間出現(xiàn)了很多邏輯錯誤，變量初始化的問題等，不過經(jīng)過仔細(xì)排查最后都一一解決了。
實驗四：查找與排序
【實驗?zāi)康摹?BR> （1）掌握折半查找算法的實現(xiàn)。（2）掌握冒泡排序算法的實現(xiàn)?！緦嶒瀮?nèi)容】
1.編寫折半查找程序，對以下數(shù)據(jù)查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.編寫冒泡排序程序，對以下數(shù)據(jù)進(jìn)行排序。49，38，65，97，76，13，27，49 【實驗步驟】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
（1）查找算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st){ int i,n;
=
(elemtype*)
malloc(elemtype));
if(!)return(overflow);
printf(“輸入元素個數(shù)和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
(maxnum*sizeof
scanf(“%d”,&[i]);}
= n;
return ok;} int seq_search(sstable st,elemtype key){
int i;
[0]=key;
for(i=;[i]!=key;--i);
return i;} int binarysearch(sstable st,elemtype key){
int mid,low,high,i=1;
low=1;
high=;
while(low<=high)
{
mid=(low+high)/2;
if([mid]==key)
return mid;
else if(key
high=mid-1;
else
}
return 0;} void main(){ sstable st;initlist(st);
elemtype key;int n;printf(“ key= ”);
scanf(“%d”,&key);
printf(“nn”);
/*printf(“after seqsearch:: ”);
n=seq_search(st,key);
printf(“position is in %d nn”,n);*/
printf(“after binary search::”);
n=binarysearch(st,key);
low=mid+1;if(n)printf(“position is in %d nn”,n);else
} 實驗結(jié)果如下所示：
（2）排序算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;
(elemtype));
if(!)return(overflow);
printf(“輸入元素個數(shù)和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
scanf(“%d”,&[i]);}
= n;
return ok;} void sort(sstable st){
int i,j,t;
for(i=1;i
for(j=i+1;j<=;j++)
if([i]>[j]){ t=[i];=
(elemtype*)
malloc
(maxnum*sizeof
}
} [i]=[j];[j]=t;void display(sstable st){ int i;
for(i=1;i<=;i++){
printf(“%d
”,[i]);}
} void main(){
sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 實驗結(jié)果如下所示：
【實驗心得】
通過這次實驗,我明白了程序里的折半查找和冒泡查找.其實排序可以有很多種，但是其目的應(yīng)該都是為了能夠在海量的數(shù)據(jù)里迅速查找到你要的數(shù)據(jù)信息，折半查找是種比較快的方式，但前提是要是有 序的排序才可以。對于有序表，查找時先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較，若相等，則查找成功；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進(jìn)行折半查找；否則在前半部分進(jìn)行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實際上死先確定待查找元素所在的區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。算法中需要用到三個變量，low表示區(qū)域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.
數(shù)據(jù)結(jié)構(gòu)資源篇一
課程編號：030816 適用專業(yè)：教育技術(shù)學(xué) 總學(xué)時數(shù)：64
學(xué) 分：4 編制單位：茂名學(xué)院理學(xué)院教育與信息技術(shù)系 編制時間：2008年6月20日
一、課程地位、性質(zhì)和任務(wù)
《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計算機相關(guān)學(xué)科專業(yè)的基礎(chǔ)課程中的一門重要的核心課程。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據(jù)問題設(shè)計和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計應(yīng)用程序打下基礎(chǔ)。
本課程以提高學(xué)生的計算機應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計高效的算法，提高程序設(shè)計能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學(xué)生的程序設(shè)計能力。
二、與其他課程的關(guān)系
先修課：程序設(shè)計基礎(chǔ)、離散數(shù)學(xué)、計算機組成原理、計算機文化基礎(chǔ)
三、教學(xué)內(nèi)容、課時安排和基本要求
（一）教學(xué)部分 第1章 緒論（2學(xué)時）1.1什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語
1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)
1.4 算法和算法分析（算法及其設(shè)計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解
基本要求：
了解：抽象數(shù)據(jù)類型，算法設(shè)計方法與算法分析。
掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、算法的基本概念；問題求解的方法與步驟 重點：數(shù)據(jù)結(jié)構(gòu)和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標(biāo)準(zhǔn)和評價方法，最壞情況和平均情況的區(qū)分。
第2章 線性表（8學(xué)時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)
2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表）2.4 一元多項式的表示及相加
基本要求：
了解：兩種存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)）及一元多項式的表示及相加。
掌握：要求熟練掌握處理線性表的各種算法。為后繼章節(jié)的學(xué)習(xí)打基礎(chǔ)。重點：各種算法。難點：鏈表的理解。
第3章 棧與隊列（4學(xué)時）
3.1 棧（定義，棧的表示和實現(xiàn)）
3.2 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號匹配的檢驗，行編輯程序，迷宮求解，表達(dá)式求值）
3.3 棧與遞歸的實現(xiàn)
3.4 隊列及其實現(xiàn)（定義，鏈隊列，循環(huán)隊列）3.5 *離散事件模擬
教學(xué)要求：熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。棧和隊列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)。
基本要求：
了解： 棧和隊列的定義及其實現(xiàn)。
掌握： 熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。重點： 棧和隊列的算法實現(xiàn)。難點： 棧和隊列的算法實現(xiàn)。
第4章 串（2學(xué)時）4.1 串類型的定義
4.2 串的表示和實現(xiàn)（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進(jìn)算法）4.4 串操作應(yīng)用舉例（文本編輯，建立詞索引表）
基本要求：
了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應(yīng)用。
第5章 數(shù)組（2學(xué)時）5.1 數(shù)組的定義
5.2 數(shù)組的順序表示和實現(xiàn)
5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結(jié)構(gòu) 5.6 m元多項式的表示
5.7 廣義表的遞歸算法（求廣義表的深度，復(fù)制廣義表，建立廣義表的存儲結(jié)構(gòu)）
基本要求：
了解：了解作為抽象數(shù)據(jù)類型的數(shù)組和c語言的數(shù)組。認(rèn)識到數(shù)組可以作為順序存儲結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實現(xiàn)。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。
掌握：掌握基本概念和算法。重點：算法。
難點：廣義表的遞歸算法。
第6章 樹與二叉樹（15學(xué)時）6.1 樹的定義和基本術(shù)語
6.2 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲結(jié)構(gòu)）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）
6.4 樹和森林（樹的存儲結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷）6.5 樹與等價問題
6.6 赫夫曼樹及其應(yīng)用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數(shù)
基本要求：
了解：理解樹與森林的定義與術(shù)語。
掌握：熟練掌握二叉樹性質(zhì)和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構(gòu)造的方法和算法。重點： 樹的存儲結(jié)構(gòu)和遍歷算法。難點：哈夫曼樹構(gòu)造的方法和算法
第7章 圖（11學(xué)時）7.1 圖的定義和術(shù)語
7.2 圖的存儲結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索）
7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關(guān)節(jié)點和重連通分量）
7.5 有向無環(huán)圖及其應(yīng)用（拓?fù)渑判?，關(guān)鍵路徑）
7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：
了解：圖的基本概念和相關(guān)術(shù)語。
掌握：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。掌握最小生成樹、最短路徑和活動網(wǎng)算法的思想。
重點：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。難點：圖的遍歷算法，最短路徑算法。
第8章 查找（8學(xué)時）
9.1 靜態(tài)查找表（順序表，有序表，靜態(tài)樹表，索引順序表）9.2 動態(tài)查找表（二叉排序樹和平衡二叉樹，b_樹和b+樹，鍵樹）9.3 哈希表（定義，構(gòu)造方法，處理沖突的方法，查找及其分析）
基本要求：
了解： 各種查找法的基本概念及實現(xiàn)的基本思想。
掌握：熟練掌握搜索結(jié)構(gòu)的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現(xiàn)。難點：哈希表查找算法。
第9章 內(nèi)部排序（8學(xué)時）10.1 概述
10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序
10.6 基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?0.7 排序算法分析
基本要求：
了解：基數(shù)排序，排序算法分析方法
掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內(nèi)部排序算法
難點：基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑?BR> 第10章 *外部排序（2學(xué)時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現(xiàn) 11.4 置換-選擇排序 11.5 最佳歸并樹
基本要求：
了解：外部排序的基本概念和相關(guān)術(shù)語。
掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現(xiàn) 第11章 算法設(shè)計的一般方法（2學(xué)時）
1．重點
（1）有效算法的概念，問題固有難度的概念；
（2）遞歸法；分治法；平衡原則；貪心法；動態(tài)規(guī)劃的基本原理；（3）搜索-回溯法的基本原理和本質(zhì).2．難點
（1）問題固有難度的概念；
（2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。
（二）實驗、實習(xí)部分
課程安排五個類別的實驗，實驗時數(shù)為12課時，其中： 實驗
一、線性鏈表及運算 2課時 實驗
二、棧和隊列 2課時 實驗
三、樹和二叉樹 4課時 實驗
四、圖及其應(yīng)用 2課時 實驗
五、查找與排序 2課時
四、課程考核方式
閉卷考試70%、平時作業(yè)與實驗30%
五、建議教材和教學(xué)參考書 參考教材：
1、《數(shù)據(jù)結(jié)構(gòu)》（c語言描述）高等教育出版社 耿國華主編
2、《數(shù)據(jù)結(jié)構(gòu)》（c語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者
3、《數(shù)據(jù)結(jié)構(gòu)題集》（c語言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者
4、《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及解析（第二版）西安電子科技大學(xué)出版社 高一凡
六、說明
1、因課時安排少，教學(xué)內(nèi)容多。建議采用多媒體教學(xué)。
2、由于本課程內(nèi)容較多，在實際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。
數(shù)據(jù)結(jié)構(gòu)資源篇二
數(shù)據(jù)結(jié)構(gòu)】二叉排序樹的建立，查找，插入和刪除實踐題 /*sy53.c*/
#include
#include
typedef int keytype;
typedef struct node{
keytype key;
struct node *lchild,*rchild;
}bstnode;
typedef bstnode *bstree;
bstree createbst(void);
void searchbst(bstree t,keytype key);
void insertbst(bstree *tptr,keytype key);
void delbstnode(bstree *tptr,keytype key);
void inorderbst(bstree t);
main()
{bstree t;
char ch1,ch2;
keytype key;
printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);
t=createbst();
ch1='y';
while(ch1=='y' || ch1=='y')
{printf(“請選擇下列操作：n”);
printf(“1------------------更新二叉排序樹存儲n”);
printf(“2------------------二叉排序樹上的查找n”);
printf(“3------------------二叉排序樹上的插入n”);
printf(“4------------------二叉排序樹上的刪除n”);
printf(“5------------------二叉排序樹中序輸出n”);
printf(“6------------------退出n”);
scanf(“n%c”,&ch2);
switch(ch2)
{case '1':t=createbst();break;
case '2':printf(“n請輸入要查找的數(shù)據(jù)：”);
scanf(“n%d”,&key);
searchbst(t,key);
printf(“查找操作完畢。n”);break;
case '3': printf(“n請輸入要插入的數(shù)據(jù)：”);
scanf(“n%d”,&key);
insertbst(&t,key);
printf(“插入操作完畢。n”);break;
case '4': printf(“n請輸入要刪除的數(shù)據(jù)：”);
scanf(“n%d”,&key);
delbstnode(&t,key);
printf(“刪除操作完畢。n”);break;
case '5': inorderbst(t);
printf(“n二叉排序樹輸出完畢。n”);break;
case '6':ch1='n';break;
default:ch1='n';
}
}
}
bstree createbst(void)
{bstree t;
keytype key;
t=null;
printf(“請輸入一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“%d”,&key);
while(key)
{insertbst(&t,key);
printf(“請輸入下一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“n%d”,&key);
}
return t;
}
void searchbst(bstree t, keytype key)
{ bstnode *p=t;
while(p)
{if(p->key==key)
{printf(“已找到n”);
return;
}
p=(key
key)? p->lchild:p->rchild;
}
printf(“沒有找到n”);
}
void insertbst(bstree *t,keytype key)
{bstnode *f,*p;
p=(*t);
while(p)
{if(p->key==key)
{printf(“樹中已有key不需插入n”);
return;
}
f=p;
p=(key
key)?p->lchild:p->rchild;
}
p=(bstnode*)malloc(sizeof(bstnode));
p->key=key;
p->lchild=p->rchild=null;
if((*t)==null)(*t)=p;
else if(key
key)f->lchild=p;
else f->rchild=p;
}/*insertbst*/
void delbstnode(bstree *t,keytype key)
{bstnode *parent=null, *p, *q,*child;
p=*t;
while(p)
{if(p->key==key)break;
parent=p;
p=(key
key)?p->lchild:p->rchild;
}
if(!p){printf(“沒有找到要刪除的結(jié)點n”);return;}
q=p;
if(q->lchild && q->rchild)
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;
if(!parent)*t=child;
else {if(p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
if(p!=q)
q->key=p->key;
}
free(p);
}
void inorderbst(bstree t){ if(t!=null)
{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}
}
數(shù)據(jù)結(jié)構(gòu)資源篇三
數(shù)據(jù)結(jié)構(gòu)參考題目
一、選擇
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）
a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復(fù)雜度為（）for(i=0;i
next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.兩個字符串相等的條件是（）
a.串的長度相等 b.含有相同的字符集
c.都是非空串 d.串的長度相等且對應(yīng)的字符相同 5．若以s和x分別表示進(jìn)棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（）
xx sx sx xx 6.已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進(jìn)行排序時，前兩趟排序的結(jié)果為
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序
8.已知散列表的存儲空間為t[0..16]，散列函數(shù)h（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關(guān)鍵字：t[5]=39，t[6]=57和t[7]=7，則下一個關(guān)鍵字23插入的位置是（）
a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個子表，整個矩陣看成是一個廣義表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為dout，則所有頂點的入度之和為（）
-1 +1 d.n 11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）a線性結(jié)構(gòu) b.樹形結(jié)構(gòu) c.線性結(jié)構(gòu)和樹型結(jié)構(gòu) d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)
12．棧的插入和刪除操作在()進(jìn)行。
a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）a.24 b.71 c.48 d.53 14．一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關(guān)于棧和隊列的說法中正確的是（）
a．棧和隊列都是線性結(jié)構(gòu) b.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu) c.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu) d.棧和隊列都不是線性結(jié)構(gòu) 16．關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（）a．順序存儲比鏈?zhǔn)酱鎯ι僬伎臻g b.順序存儲比鏈?zhǔn)酱鎯Χ嗾伎臻g
c.順序存儲和鏈?zhǔn)酱鎯Χ家笳加谜麎K存儲空間 d.鏈?zhǔn)酱鎯Ρ软樞虼鎯﹄y于擴充空間
17．已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；
18．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時，s語句被執(zhí)行的次數(shù)為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結(jié)點的時間復(fù)雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）
a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．關(guān)于串的敘述中，正確的是（）a．空串是只含有零個字符的串 b.空串是只含有空格字符的串
c.空串是含有零個字符或含有空格字符的串
d.串是含有一個或多個字符的有窮序列
23．在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）
a．front==rear
b.(front+1)%m==rear
+1==front
d.(rear+1)%m==front 24．設(shè)有二維數(shù)組
?1????a［n］［n］表示如下：?23456??????????，則a［i］［i］（0≤i≤n-1）的d.i2/2 值為（）
a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）
ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）
-1 c.n(m-1)d.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）a.矩陣中非全零元素的行數(shù)等于圖中的頂點數(shù)
b.第i行上與第i列上非零元素總和等于頂點vi的度數(shù) c.矩陣中的非零元素個數(shù)等于圖的邊數(shù)
d.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等
29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）a.1 b.2 c.3 d.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）
a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81
二、填空題
1.數(shù)據(jù)是計算機加工處理的對象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面()。
3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進(jìn)先出的線性表（）。
5.從循環(huán)鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的前驅(qū)結(jié)點（）。6.單鏈表設(shè)置頭結(jié)點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）。
9.從非循環(huán)鏈表的某一結(jié)點出發(fā)，既能找到它的后繼結(jié)點，又能找到它的前驅(qū)結(jié)點（）。
10.單鏈表結(jié)點的指針域是用來存放其直接后繼結(jié)點的首地址的（）
11.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象（）。
12.用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。
13.在非線性結(jié)構(gòu)中，至少存在一個元素不止一個直接前驅(qū)或不止一個直接后驅(qū)（）。14.樹的最大特點是一對多的層次結(jié)構(gòu)（）。15.隊列的特點是先進(jìn)先出（）。
16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨立于計算機（）。18.線性表簡稱為”順序表”。（）
19.對數(shù)據(jù)的任何運算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點出發(fā)，可以找到表中的所有結(jié)點（）。21.棧是一種先進(jìn)先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。
27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型（）。
28.線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進(jìn)后出的線性表（）。
30.將插入和刪除限定在表的同一端進(jìn)行的線性表是隊列（）。
三、畫圖題
1.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={a,b,c,d,e,f,g,h,i,j} r={,,
,
,
,
,
,
,
} 3．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={1,2,3,4,5} r={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) k={0,1,2,3,4,5,6,7} r={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}
四、運算題
1．已知一個圖的頂點集v和邊集h分別為：
v＝{0，1，2，3，4，5，6，7}
e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。
2.一個線性表為b=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為ht[0..12]，散列函數(shù)為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。
平均查找長度：（寫出計算過程）
3．已知一個圖的頂點集v和邊集h分別為：
v＝{0，1，2，3，4，5，6，7}
e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發(fā)）
____
__，___
_，___
___，__
____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：
前序： 中序： 后序：
5.設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。
五、編程題
1.請編寫一個算法，實現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：
int search_bin(keytype k,sstable st){ 3.請編寫一個算法，實現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點）。linklist *invertlink(linklist *h){
數(shù)據(jù)結(jié)構(gòu)資源篇四
實驗：線性表的基本操作
【實驗?zāi)康摹?BR> 學(xué)習(xí)掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的設(shè)計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法。
【實驗內(nèi)容】
1.順序表的實踐
1)建立4個元素的順序表s=sqlist[]={1，2，3，4，5}，實現(xiàn)順序表建立的基本操作。
2)在sqlist []={1，2，3，4，5}的元素4和5之間插入一個元素9，實現(xiàn)順序表插入的基本操作。
3)在sqlist []={1，2，3，4，9，5}中刪除指定位置（i=5）上的元素9，實現(xiàn)順序表的刪除的基本操作。2.單鏈表的實踐
3.1)建立一個包括頭結(jié)點和4個結(jié)點的（5，4，2，1）的單鏈表，實現(xiàn)單鏈表建立的基本操作。
2)將該單鏈表的所有元素顯示出來。
3)在已建好的單鏈表中的指定位置（i=3）插入一個結(jié)點3，實現(xiàn)單鏈表插入的基本操作。
4)在一個包括頭結(jié)點和5個結(jié)點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結(jié)點，實現(xiàn)單鏈表刪除的基本操作。5)實現(xiàn)單鏈表的求表長操作。
【實驗步驟】
1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中，碰到的第一個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。通過學(xué)習(xí)我知道了對線性表進(jìn)行建立、插入、刪除，同時單鏈表也是進(jìn)行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復(fù)雜度均為0（n）.通過這次的學(xué)習(xí)，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念。總之，這次實驗我找到了自己的不足之處，以后會努力的。
實驗二：棧的表示與實現(xiàn)及棧的應(yīng)用
【實驗?zāi)康摹?BR> （1）掌握棧的順序存儲結(jié)構(gòu)及其基本操作的實現(xiàn)。（2）掌握棧后進(jìn)先出的特點，并利用其特性在解決實際問題中的應(yīng)用。（3）掌握用遞歸算法來解決一些問題?！緦嶒瀮?nèi)容】
1.編寫程序，對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，輸出與其等值的八進(jìn)制數(shù)。
2.編寫遞歸程序，實現(xiàn)n！的求解。3.編寫遞歸程序，實現(xiàn)以下函數(shù)的求解。
n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1
4.編寫程序，實現(xiàn)hanoi塔問題?！緦嶒灢襟E】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
通過這次的學(xué)習(xí)我掌握了棧這種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭端稱為棧底（botton）；棧又稱為后進(jìn)先出（last in first out）的線性表,簡稱lifo結(jié)構(gòu)，因為它的修改是按后進(jìn)先出的原則進(jìn)行的。
加上這個實驗，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學(xué)習(xí)有很大的作用，可以說這是學(xué)習(xí)以后知識的總要基礎(chǔ)。
實驗三：二叉樹的建立及遍歷
【實驗?zāi)康摹?BR> （1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法?！緦嶒瀮?nèi)容】
1.編寫程序，實現(xiàn)二叉樹的建立，并實現(xiàn)先序、中序和后序遍歷。如：輸入先序序列abc###de###，則建立如下圖所示的二叉樹。
并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實驗步驟】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實驗心得】
這次試驗是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實驗中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數(shù)的計算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗不太好做，期間出現(xiàn)了很多邏輯錯誤，變量初始化的問題等，不過經(jīng)過仔細(xì)排查最后都一一解決了。
實驗四：查找與排序
【實驗?zāi)康摹?BR> （1）掌握折半查找算法的實現(xiàn)。（2）掌握冒泡排序算法的實現(xiàn)?！緦嶒瀮?nèi)容】
1.編寫折半查找程序，對以下數(shù)據(jù)查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.編寫冒泡排序程序，對以下數(shù)據(jù)進(jìn)行排序。49，38，65，97，76，13，27，49 【實驗步驟】 1.打開vc++。
2.建立工程：點file->new，選project標(biāo)簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點file->new，選file標(biāo)簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
（1）查找算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st){ int i,n;
=
(elemtype*)
malloc(elemtype));
if(!)return(overflow);
printf(“輸入元素個數(shù)和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
(maxnum*sizeof
scanf(“%d”,&[i]);}
= n;
return ok;} int seq_search(sstable st,elemtype key){
int i;
[0]=key;
for(i=;[i]!=key;--i);
return i;} int binarysearch(sstable st,elemtype key){
int mid,low,high,i=1;
low=1;
high=;
while(low<=high)
{
mid=(low+high)/2;
if([mid]==key)
return mid;
else if(key
high=mid-1;
else
}
return 0;} void main(){ sstable st;initlist(st);
elemtype key;int n;printf(“ key= ”);
scanf(“%d”,&key);
printf(“nn”);
/*printf(“after seqsearch:: ”);
n=seq_search(st,key);
printf(“position is in %d nn”,n);*/
printf(“after binary search::”);
n=binarysearch(st,key);
low=mid+1;if(n)printf(“position is in %d nn”,n);else
} 實驗結(jié)果如下所示：
（2）排序算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;
(elemtype));
if(!)return(overflow);
printf(“輸入元素個數(shù)和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
scanf(“%d”,&[i]);}
= n;
return ok;} void sort(sstable st){
int i,j,t;
for(i=1;i
for(j=i+1;j<=;j++)
if([i]>[j]){ t=[i];=
(elemtype*)
malloc
(maxnum*sizeof
}
} [i]=[j];[j]=t;void display(sstable st){ int i;
for(i=1;i<=;i++){
printf(“%d
”,[i]);}
} void main(){
sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 實驗結(jié)果如下所示：
【實驗心得】
通過這次實驗,我明白了程序里的折半查找和冒泡查找.其實排序可以有很多種，但是其目的應(yīng)該都是為了能夠在海量的數(shù)據(jù)里迅速查找到你要的數(shù)據(jù)信息，折半查找是種比較快的方式，但前提是要是有 序的排序才可以。對于有序表，查找時先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較，若相等，則查找成功；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進(jìn)行折半查找；否則在前半部分進(jìn)行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實際上死先確定待查找元素所在的區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。算法中需要用到三個變量，low表示區(qū)域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.