数据结构讲义五篇(通用)

人的记忆力会随着岁月的流逝而衰退，写作可以弥补记忆的不足，将曾经的人生经历和感悟记录下来，也便于保存一份美好的回忆。相信许多人会觉得范文很难写？接下来小编就给大家介绍一下优秀的范文该怎么写，我们一起来看一看吧。

数据结构讲义篇一

第一章：数据结构概述

1、掌握数据结构的定义，即数据结构三要素：数据的逻辑结构、存储结构、操作；

2、数据结构包括：逻辑结构和存储结构；

3、数据之间的关系：表（一对一之间的关系）、树（一对多之间的关系）、图（多对多之间的关系）；

4、算法的定义：算法衡量的标准：时间复杂度和空间复杂度；

5、算法时间复杂度的求法：给定一段程序，求其时间复杂度；时间复杂度的比较；

6、为什么学习“数据结构”？“数据结构”课程主要学了哪些知识？

第二章：线性表

1、线性表按照存储结构不同分为顺序表、链式表；顺序表的特点：逻辑上相邻的两个元素在物理上也相邻；链式表的特点：逻辑上相邻的两个元素在物理上未必相邻；（“未必”的含义是可相邻也可以不相邻）

2、比较线性表顺序存储和链式存储的优缺点。

第三章：栈和队列

1、栈和队列的特点：栈：后进先出，队列：先进先出

2、熟悉栈和队列的基本操作：初始化栈、入栈操作、出栈操作、判断栈是否为空、取栈顶元素等。

3、根据实例，能够容易的判断出是栈的应用还是队列的应用？

4、重点掌握栈的应用：进制转换算法的思想或程序。

第四章：数组

1、牢记对称矩阵、三角矩阵、对角矩阵的特点，掌握矩阵中的元素aij与一维数组sa[k]的对应关系。

2、掌握稀疏矩阵的三元组表示法。

第五章：串

1、掌握上课介绍的9种函数名称及其实现结果；

第六章：树

1、二叉树的5个性质；

2、二叉树前序、中序和后序遍历，根据2种遍历结果求第3种遍历结果。

3、完全二叉树、满二叉树、哈弗曼树的定义；

4、给定一组叶子权值，求带权路径长度最小的多少？

第七章：图

1、掌握图的术语：无向完全图、有向完全图、顶点的度等；

2、图的深度优先遍历和广度优先遍历；

3、图的邻接矩阵存储，给定一个图，求出邻接矩阵；或者给定一个邻接矩阵，构造图；

4、图的最小生成树；

第八章：查找

1、查找的定义：静态查找和动态查找

2、折半查找算法的思想；

第九章：排序

1、掌握排序的分类：插入排序、交换排序、选择排序；

2、重点掌握希尔排序、快速排序、简单选择排序；

数据结构讲义篇二

数据结构】二叉排序树的建立，查找，插入和删除实践题 /*sy53.c*/

#include

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;

}/*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.两个字符串相等的条件是（）

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,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.而冒泡查找则是从小到大的排序.

数据结构讲义篇五

数据结构复习资料

模块一：计算题

一.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列： b f iceh g 中序序列：d kfia ejc 后序序列： k fbhj g a 解：在先序序列空格中依次填adkj，中序中依次填bhg，后序中依次填diec。

二叉树自画！

二．试列出如下图中全部可能的拓扑排序序列。

123456 解：全部可能的拓扑排序序列为：152364、152634、156234、561234、516234、512634、512364 三．已知哈希表地址空间为0..8，哈希函数为h(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度以及查找因子。

解：哈希表及查找各关键字要比较的次数如下所示：

asl=1(4×1+1×2+1×4+2×5)=2.5

8a=8/9

四．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。

解：

五．设有序列：w={23,24,27,80,28}，试给出哈夫曼树； 哈夫曼树如下图所示：

六：已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序列：abcdefghij 中序序列：cbedaghfji

解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。

七．（本题8分）

对于如下图所示的g，用kruskal算法构造最小生成树，要求图示出每一步的变化情况。

解：用kruskal算法构造最小生成树的过程如下图所示：

八．给出一组关键字29、18、25、47、58、12、51、10，写出归并排序方法进行排序时的变化过程。

解：

(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58)

九．

三、（本题8分）

请画出如下图所示的邻接表。

解：邻接表如下图所示：

***45454∧∧∧∧5∧ 十．判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 解：（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70}

（2）是小根堆。

十一． 设有如下图所示的aoe网（其中vi（i=l，2，…，6）表示事件，弧上表示活动的天数）。

v26v14v48217v311v693v5 找出所有的关键路径。

解：所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。十二.对给定的有7个顶点的有向图的邻接矩阵如下：（l）画出该有向图；

（2）若将图看成是aoe-网，画出关键路径。

25221835

5395

解：（1）由邻接矩阵所画的有向图如下图所示：

2212523***5）关键路径如下图所示：

22213715945 4（2