数据结构期末考试题 数据结构在计算机内存中表示的是

每个人都曾试图在平淡的学习、工作和生活中写一篇文章。写作是培养人的观察、联想、想象、思维和记忆的重要手段。那么我们该如何写一篇较为完美的范文呢？以下是小编为大家收集的优秀范文，欢迎大家分享阅读。

数据结构期末考试题 数据结构在计算机内存中表示的是篇一

课程编号：030816 适用专业：教育技术学 总学时数：64

学 分：4 编制单位：茂名学院理学院教育与信息技术系 编制时间：2008年6月20日

一、课程地位、性质和任务

《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课程。通过本课程的教学，使学生知道求解非数值类问题的基本模型（表、树、图），模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。

本课程以提高学生的计算机应用能力和综合素质为目标，通过课程教学，为学生构建数据结构与算法方面的知识体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计能力，另一方面，在工程应用中，具有甄别好算法的能力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计能力。

二、与其他课程的关系

先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础

三、教学内容、课时安排和基本要求

（一）教学部分 第1章 绪论（2学时）1.1什么是数据结构 1.2 基本概念和术语

1.3 抽象数据类型的表示与实现

1.4 算法和算法分析（算法及其设计的要求，算法效率的度量，算法的存储空间需求）1.5 问题求解

基本要求：

了解：抽象数据类型，算法设计方法与算法分析。

掌握：数据与数据结构、算法的基本概念；问题求解的方法与步骤 重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤 难点：评价算法的标准和评价方法，最坏情况和平均情况的区分。

第2章 线性表（8学时）2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现（线性链表，循环链表，双向链表）2.4 一元多项式的表示及相加

基本要求：

了解：两种存储结构（顺序存储结构和链式存储结构）及一元多项式的表示及相加。

掌握：要求熟练掌握处理线性表的各种算法。为后继章节的学习打基础。重点：各种算法。难点：链表的理解。

第3章 栈与队列（4学时）

3.1 栈（定义，栈的表示和实现）

3.2 栈的应用举例（数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值）

3.3 栈与递归的实现

3.4 队列及其实现（定义，链队列，循环队列）3.5 *离散事件模拟

教学要求：熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要的数据结构，是数据结构课程的基础。

基本要求：

了解： 栈和队列的定义及其实现。

掌握： 熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。重点： 栈和队列的算法实现。难点： 栈和队列的算法实现。

第4章 串（2学时）4.1 串类型的定义

4.2 串的表示和实现（定长顺序存储，堆分配存储，串的块链存储）4.3 串的模式匹配算法（求子串位置的定位函数，模式匹配的一种改进算法）4.4 串操作应用举例（文本编辑，建立词索引表）

基本要求：

了解：串的基本概念及主要操作和运算。掌握：掌握串的基本概念和运算。重点：主要操作和运算。难点：模式匹配及串的应用。

第5章 数组（2学时）5.1 数组的定义

5.2 数组的顺序表示和实现

5.3 矩阵的压缩存储（特殊矩阵，稀疏矩阵）5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示

5.7 广义表的递归算法（求广义表的深度，复制广义表，建立广义表的存储结构）

基本要求：

了解：了解作为抽象数据类型的数组和c语言的数组。认识到数组可以作为顺序存储结构用于顺序表、字符串和稀疏矩阵的实现。也可以采用链式存储结构。

掌握：掌握基本概念和算法。重点：算法。

难点：广义表的递归算法。

第6章 树与二叉树（15学时）6.1 树的定义和基本术语

6.2 二叉树（二叉树的定义，二叉树的性质，二叉树的存储结构）6.3 遍历二叉树和线索二叉树（遍历二叉树，线索二叉树）

6.4 树和森林（树的存储结构，森林与二叉树的转换，树和森林的遍历）6.5 树与等价问题

6.6 赫夫曼树及其应用（最优二叉树（赫夫曼树），赫夫曼编码）6.7 回溯法与树的遍历 6.8 树的计数

基本要求：

了解：理解树与森林的定义与术语。

掌握：熟练掌握二叉树性质和遍历算法，掌握树与森林的孩子兄弟存储表示和遍历。掌握哈夫曼树构造的方法和算法。重点： 树的存储结构和遍历算法。难点：哈夫曼树构造的方法和算法

第7章 图（11学时）7.1 图的定义和术语

7.2 图的存储结构（数组表示法，邻接表，十字链表，邻接多重表）7.3 图的遍历（深度优先搜索，广度优先搜索）

7.4 图的连通性问题（无向图的连通分量和生成树，有向图的强连通分量，最小生成树，关节点和重连通分量）

7.5 有向无环图及其应用（拓扑排序，关键路径）

7.6 最短路径（从某个源点到其余各项点的最短路径，每一对顶点之间的最短路径）基本要求：

了解：图的基本概念和相关术语。

掌握：图的两种主要存储结构及遍历算法。掌握最小生成树、最短路径和活动网算法的思想。

重点：图的两种主要存储结构及遍历算法。难点：图的遍历算法，最短路径算法。

第8章 查找（8学时）

9.1 静态查找表（顺序表，有序表，静态树表，索引顺序表）9.2 动态查找表（二叉排序树和平衡二叉树，b_树和b+树，键树）9.3 哈希表（定义，构造方法，处理冲突的方法，查找及其分析）

基本要求：

了解： 各种查找法的基本概念及实现的基本思想。

掌握：熟练掌握搜索结构的折半查找、二叉搜索树、平衡二叉树主要搜索算法。掌握哈希表查找算法。重点：各种算法的基本思想及实现。难点：哈希表查找算法。

第9章 内部排序（8学时）10.1 概述

10.2 插入排序（直接插入，其他插入，希尔）10.3 交换排序（冒泡排序、快速排序）10.4 选择排序（简单，树形，堆）10.5 归并排序

10.6 基数排序（多关键字，链式）10.7 排序算法分析

基本要求：

了解：基数排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交换排序，选择排序，归并排序重点：内部排序算法

难点：基数排序（多关键字，链式）

第10章 *外部排序（2学时）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树

基本要求：

了解：外部排序的基本概念和相关术语。

掌握：基本掌握外排算法的基本思想，不同排序方法的比较。重点：外部排序算法 难点：多路平衡归并的实现 第11章 算法设计的一般方法（2学时）

1．重点

（1）有效算法的概念，问题固有难度的概念；

（2）递归法；分治法；平衡原则；贪心法；动态规划的基本原理；（3）搜索-回溯法的基本原理和本质.2．难点

（1）问题固有难度的概念；

（2）递归分治法的效率分析（写出时间耗费的递推式，并求解）；（3）动态规划法中的状态转移方程的确定。

（二）实验、实习部分

课程安排五个类别的实验，实验时数为12课时，其中： 实验

一、线性链表及运算 2课时 实验

二、栈和队列 2课时 实验

三、树和二叉树 4课时 实验

四、图及其应用 2课时 实验

五、查找与排序 2课时

四、课程考核方式

闭卷考试70%、平时作业与实验30%

五、建议教材和教学参考书 参考教材：

1、《数据结构》（c语言描述）高等教育出版社 耿国华主编

2、《数据结构》（c语言版）清华大学出版社 严蔚敏，吴伟民编者

3、《数据结构题集》（c语言版）清华大学出版社 严蔚敏，吴伟民编者

4、《数据结构》算法实现及解析（第二版）西安电子科技大学出版社 高一凡

六、说明

1、因课时安排少，教学内容多。建议采用多媒体教学。

2、由于本课程内容较多，在实际教学中可根据大纲内容，进行适当调整。

数据结构期末考试题 数据结构在计算机内存中表示的是篇二

数据结构】二叉排序树的建立，查找，插入和删除实践题 /*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请输入要查找的数据：”);

scanf(“n%d”,&key);

searchbst(t,key);

printf(“查找操作完毕。n”);break;

case '3': printf(“n请输入要插入的数据：”);

scanf(“n%d”,&key);

insertbst(&t,key);

printf(“插入操作完毕。n”);break;

case '4': printf(“n请输入要删除的数据：”);

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(“请输入一个关键字(输入0时结束输入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“请输入下一个关键字(输入0时结束输入)：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(“没有找到要删除的结点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);}

}

数据结构期末考试题 数据结构在计算机内存中表示的是篇三

数据结构参考题目

一、选择

1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）

a.栈 b.队列 c.树 d.图 2.下面程序段的时间复杂度为（）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.串的长度相等且对应的字符相同 5．若以s和x分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）

xx sx sx xx 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）a.0 b.1 c.48 d.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（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]，散列函数h（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：t[5]=39，t[6]=57和t[7]=7，则下一个关键字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．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）a线性结构 b.树形结构 c.线性结构和树型结构 d.线性结构和图状结构

12．栈的插入和删除操作在()进行。

a．栈顶 b.栈底 c.任意位置 d指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）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．关于栈和队列的说法中正确的是（）

a．栈和队列都是线性结构 b.栈是线性结构，队列不是线性结构 c.栈不是线性结构，队列是线性结构 d.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）a．顺序存储比链式存储少占空间 b.顺序存储比链式存储多占空间

c.顺序存储和链式存储都要求占用整块存储空间 d.链式存储比顺序存储难于扩充空间

17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）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．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 19．执行下面程序段时，s语句被执行的次数为：（）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所指结点的时间复杂度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）

a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．关于串的叙述中，正确的是（）a．空串是只含有零个字符的串 b.空串是只含有空格字符的串

c.空串是含有零个字符或含有空格字符的串

d.串是含有一个或多个字符的有穷序列

23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front 24．设有二维数组

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的完全二叉树中，结点数最多为（）

ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）

-1 c.n(m-1)d.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）a.n b.n-1 c.n+1 d.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）a.矩阵中非全零元素的行数等于图中的顶点数

b.第i行上与第i列上非零元素总和等于顶点vi的度数 c.矩阵中的非零元素个数等于图的边数

d.第i行上非零元素个数和第i列上非零元素个数一定相等

29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）

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.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。

3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。

5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。

9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。

10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）

11.数据的存储结构是数据的逻辑结构的存储映象（）。

12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。

13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。

16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）

19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。

27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。

28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。

30.将插入和删除限定在表的同一端进行的线性表是队列（）。

三、画图题

1.请根据下列二元组画出相应的数据结构

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构

k={a,b,c,d,e,f,g,h,i,j} r={,,

,

,

,

,

,

,

} 3．请根据下列二元组画出相应的数据结构 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.请根据下列二元组画出相应的数据结构

k={1,2,3,4,5} r={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．请根据下列二元组画出相应的数据结构 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．请根据下列二元组画出相应的数据结构

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），设散列表为ht[0..12]，散列函数为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出发）

____

__，___

_，___

___，__

____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果：

前序： 中序： 后序：

5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。

五、编程题

1.请编写一个算法，实现十进制整数与二进制数的转换。void shi_to_er(unsigned x){ 2.写出二分法查找的算法：

int search_bin(keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。linklist *invertlink(linklist *h){

数据结构期末考试题 数据结构在计算机内存中表示的是篇四

实验：线性表的基本操作

【实验目的】

学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】

1.顺序表的实践

1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。

2)在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3)在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践

3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。

2)将该单链表的所有元素显示出来。

3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。

4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。

【实验步骤】

1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。

实验二：栈的表示与实现及栈的应用

【实验目的】

（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】

1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。

2.编写递归程序，实现n！的求解。3.编写递归程序，实现以下函数的求解。

n,n0,1fib(n) fib(n1)fib(n2),n1

4.编写程序，实现hanoi塔问题。【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（last in first out）的线性表,简称lifo结构，因为它的修改是按后进先出的原则进行的。

加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。

实验三：二叉树的建立及遍历

【实验目的】

（1）掌握利用先序序列建立二叉树的二叉链表的过程。（2）掌握二叉树的先序、中序和后序遍历算法。【实验内容】

1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。

实验四：查找与排序

【实验目的】

（1）掌握折半查找算法的实现。（2）掌握冒泡排序算法的实现。【实验内容】

1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

（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(“输入元素个数和各元素的值:”);

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

} 实验结果如下所示：

（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(“输入元素个数和各元素的值:”);

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);} 实验结果如下所示：

【实验心得】

通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有 序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.