范文一:数据结构课程简介
《数据结构》课程简介
《数据结构》作为一门独立的课程,最早在美国的一些大学开设。1968年美国唐?欧?克努特教授所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据结构的著作。从60年代末到70年代初,随着大型程序的出现以及软件的相对独立,人们越来越重视数据结构,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。自70年代中期到80年代初,不同版本的数据结构著作相继出现,逐步发展为一门称为数据结构的计算机科学,并且广泛应用于计算机领域。
计算机信息管理专业开设的《数据结构》是一门专业基础课。本课程主要任务是讨论数据之间的各种关系、数据在计算机中如何存储以及相关运算的算法。内容包括:线性表、栈和队列、树与森林、图、查找、排序等。本课程采用类C语言和自然语言作为算法的描述工具,结合生活中的实例分析数据之间的关系,并且能够根据实际情况选用合适的存储结构,理解掌握各种基本算法思想,为后续的计算机课程的学习打下坚实的基础。
范文二:《数据结构》课程简介
个人总结
西南财经大学天府学院
课程简介
任课教师:
课程名称:数据结构
任课班级:2007级本科计算机专业班
授课时间:2008-2009 第一学期
西南财经大学天府学院教务处制
课程名称:数据结构
内容概要:Data structure is a fundamental course. The primary focus of this course is to introduce to students the ways elemental data could be organized into entities that facilitate more efficient programming. These organized items, called data structures, form the basis on which advanced programming techniques could be designed. In this course, we would learn various data structuring techniques (logic structures and storage structures of data) and also the ways efficient algorithms on such structures could be realized. The course material contains :Introduction ( Pseudocode , Abstract data type, Algorithm efficiency analysis), Searching (Sequential search, Binary search and Hashed list searches) ,Linked lists( The concepts of Linear lists and Linked list, Linked list algorithms and applications, Complex linked list structures ), Stacks ( Basic stack operations ,Stack linked list implementation and stack applications ), Queues ( Queue operations, Queue linked list design and Queue applications ), Recursion(How recursion works and designing recursive algorithms ), Introduction to trees ( Basic tree concepts, Binary trees, Binary tree traversals and expression trees ), Search trees(Binary search trees, *AVL trees and its implementation ), *Heaps (Definition, structure , Algorithms and applications ), *Multi-way trees (m-way search trees , B-trees, ), Advanced sorting concepts(Basic concepts, Insertion sorts, Selection sorts, Exchange sorts ), *Graphs (Terminology, Operations, Graph storage structures and algorithms ). The course would be language independent as much as possible. The students, however, are expected to write and test their data structures and programs on them using a language, such as C or C++.
适用对象:西南财经大学天府学院,二年级IT类专业
使用教材:《DATA STRUCTRUE A Pseudocode Approach with C++》 Richard.F.Giberg Behrouz.A.Forouzan
参考书目:
《数据结构》(C语言版) 严蔚敏,吴伟民 清华大学出版社.2002,9
《Data Structure, Algorithms, and Application in C++.》 Sartaj Sahni The McGraw-Hill Company Inc.1998(数据结构、算法与应用--C++语言描述.,机械工业出版社.1999)
《数据结构实用教程(C/C++描述)》 徐孝凯 :清华大学出版社.1999,12
《数据结构(
使用C++语言描述)》 陈慧南 东南大学出版社.2001,1
先行课:程序设计、计算机应用基础、离散数学等
所需课时:72(讲授、上机实习)
西南财经大学天府学院课程简介 TIANFU COLLEGE OF SWUFE
个人总结
范文三:数据结构课程简介
没有想像力的灵魂,就像没有望远镜的天文台
数据结构课程简介
数据结构是信息类专业学生的专业技术基础课程
它介绍了软件设计中最常用的基本技术
它对学生专业素质培养
至关重要
包括各种常用的数据结构及其存储结构和算法设计与实现
以及排序和查找这两种常用运算
本课程学习的效果不仅关系到后续课程的学习
而且直接关系到软件设计水平的提高和专业素质的培养
因而成为信息类专业的核心课程之一
现已成为大多数单位招收信息类专业研究生的必考课程
鉴于本课程的性质
现在也成为许多专业提高软件水平的关键性课程
例如
我校的计算机专业、信息与计算科学专业、电气工程专业、电子信息专业、机械电子专业等均开设了此课程
湖北民族学院信息工程学院从1995年开设数据结构课程以来
在数据结构课程的教学方法、理论教学体系建设、实践教学建设、实验工具环境建设等方面取得了一定的成果
本课程组师资较为雄厚
有博士2名
7名硕士
5名高级教师
本课程
注重"算法+数据结构=程序设计"的实践动手能力培养
通过 "习题练习、上机实习
课程设计"三位一体的训练
促使学生把理论学习和上机编程密切结合起来
可设计出正确、规范、严密、高效的算法并能编程实现
提高学生的逻辑思维能力、抽象能力和应用能力
范文四:数据结构课程
数据结构课程
考核说明与综合练习
《数据结构》课程是计算机科学与技术专业统设的一门重要的必修专业基础课,它
主要研究数据的各种逻辑结构和在计算机中的存储结构,还研究对数据进行的插入、查
找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算
法。由于本课程的主教材采用C++语言描述算法,期末卷面考试也采用C++语言描述,因而要求在做平时作业和上机实验操作时用C++开发工具(如:Visual C++或 C++ Builder或Borland C++)。
考试的题型有:单选题、填空题、运算题、阅读算法、填写算法和编写算法等。
下面按照主教材中各章次序给出每章的具体复习要求。
第一章 绪论
【重点掌握】
1.数据结构的二元组表示,对应的图形表示,序偶和边之间的对应关系。
2.集合结构、线性结构、树结构和图结构的特点。
3.抽象数据类型的定义和表示方法。
4.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换,元素地址和数
组地址的计算,元素占用存储空间大小和数组占用存储空间大小的计算。
5.普通函数重载和操作符函数重载的含义、定义格式和调用格式。
6.函数定义中值参数和引用参数的说明格式及作用,函数被调用执行时对传送来的实
际参数的影响。
7.算法的时间复杂度和空间复杂度的概念、计算方法、数量级表示。
8.一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。
对于本章的其余内容均作一般掌握。
第二章 线性表
【重点掌握】
1.线性表的定义和抽象数据类型的描述,线性表中每一种操作的功能,对应的函数名、
返回值类型和参数表中每个参数的作用。
2.线性表的顺序存储结构的类型定义,即List类型的定义和每个域的定义及作用。
3.线性表的每一种运算在顺序存储结构上实现的算法,及相应的时间复杂度。
4.链接存储的概念,线性表的单链接和双链接存储的结构,向单链表中一个结点之后
插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。
5.单链表中结点的结构,每个域的定义及作用,即LNode类型的定义及结构。
6.带表头附加结点的链表、循环链表、双向链表的结构特点。
7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
对于本章的其余内容均作一般掌握。
第三章 稀疏矩阵和广义表
1
【重点掌握】
1.稀疏矩阵的定义和三元组线性表表示。
2.稀疏矩阵的顺序存储、带行指针向量的链接存储,在每一种存储中非零元素结点的
结构。
3.稀疏矩阵的转置运算。
4.广义表的定义和表示,广义表长度和深度的计算。
5.广义表的链接存储结构中结点类型的定义,分别求广义表长度和深度的递归算法,
它们对应的时间复杂度。
【一般掌握】
稀疏矩阵转置的算法描述。
对于本章的其余内容均作一般了解。
第四章 栈和队列
【重点掌握】
1.栈的定义和抽象数据类型的描述,栈中每一种操作的功能,对应的函数名、返回值
类型和参数表中每个参数的作用。
2.栈的顺序存储结构的类型定义,即Stack类型的定义和每个域的定义及作用。
3.栈的每一种运算在顺序存储结构上实现的算法,及相应的时间复杂度。
4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。
5.算术表达式的中缀表示和后缀表示,以及相互转换的规则,后缀表达式求值的方法。
6.队列的定义和抽象数据类型的描述,队列中每一种操作的功能,对应的函数名、返
回值类型和参数表中每个参数的作用。
7.队列的顺序存储结构的类型定义,即Queue类型的定义和每个域的定义及作用。
8.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
9.利用栈和队列解决简单问题的算法分析和设计。
【一般掌握】
1.后缀表达式求值的算法,把中缀表达式转换为后缀表达式的算法。
2.队列的链接存储结构,以及实现每一种队列运算的算法和相应的时间复杂度。
对于本章的其余内容均作一般了解。
第五章 树和二叉树
【重点掌握】
1.树和二叉树的定义,对于一棵具体树和二叉树的二元组表示及广义表表示。
2.树和二叉树的概念,如结点的度、树的度、树的层数、树的深度等。
3.树和二叉树的性质,如已知树或二叉树的深度h可求出相应的最多结点数,已知结
点数n可求出对应树或二叉树的最大和最小高度。
4.二叉树中结点的编号规则和对应的顺序存储结构。
5.二叉树的链接存储结构及存储结点的类型定义,即BTreeNode类型的定义和每个域的定义及作用。
6.二叉树的先序、中序、后序遍历的递归过程和递归算法,中序遍历的非递归算法,
按层遍历的过程和算法,每种算法的时间复杂度。
【一般掌握】
1.普通树的链接存储结构,GTreeNode类型的定义和每个域的定义及作用。
2.普通树的先根、后根和按层遍历的过程及算法。
3.在链接存储的二叉树上实现指定功能的算法分析和设计。
对于本章的其余内容均作一般了解。
2
第六章 二叉树的应用
【重点掌握】
1.二叉搜索树的定义和性质。
2.二叉搜索树查找的递归算法和非递归算法,相应的时间复杂度,查找一个元素的查
找长度,即从树根结点到该结点的路径上的结点数。
3.二叉搜索树插入的递归算法和非递归算法,相应的时间复杂度,根据一组数据生成
一棵二叉搜索树的过程。
4.堆的定义和顺序存储结构,小根堆和大根堆的异同。
5.向堆中插入元素的过程、算法描述及时间复杂度。
6.从堆中删除元素的过程、算法描述及时间复杂度。
7.哈夫曼树的定义,树的带权路径长度的计算,根据若干个叶子结点的权构造哈夫曼
树的过程。
对本章的其余内容均作一般了解。
第七章 图
【重点掌握】
1.图的顶点集和边集的表示。
2.图的一些概念的含义,如顶点、边、度、完全图、子图、路径、路径长度、连通图、
权、网等。
3.图的邻接矩阵、邻接表和边集数组三种存储结构及相应的空间复杂度。
4.存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用
途。
5.图的深度优先和广度优先搜索遍历的过程。
6.对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以
及相应的时间复杂度。
7.对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以
及相应的时间复杂度。
8.图的生成树、生成树的权、最小生成树等的定义。
9.根据普里姆算法求图的最小生成树的过程。
10.根据克鲁斯卡尔算法求图的最小生成树的过程。
11.图的拓扑序列和拓扑排序的概念,求图的拓扑序列的方法,对用邻接表表示的图
进行拓扑排序的过程。
【一般掌握】
1.根据普里姆算法求图的最小生成树的算法描述。
2.根据克鲁斯卡尔算法求图的最小生成树的算法描述。
3.对用邻接表表示的图进行拓扑排序和算法描述。
对本章的其余内容均作一般了解。
第八章 查找
【重点掌握】
1.在一维数组上进行顺序查找的过程、算法、平均查找长度和时间复杂度。
2.在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂
度,二分查找一个给定值元素的查找长度(即查找路径上的元素数),二分查找对应的判
定树的性质。
3.索引存储的概念,索引表的存储结构和索引项的存储结构,索引查找一个元素的过
3
程、平均查找长度和时间复杂度。
4.散列存储的概念,散列函数、散列表、冲突、同义词、装填因子等术语的含义。
5.利用除留余数法建立散列函数求元素散列地址的方法。
6.利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程,利用链接法
处理冲突进行散列存储和查找的过程。
7.根据除留余数法构造散列函数,采用线性探查法或链接法处理冲突,把一组数据散
列存储到散列表中,计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。
8.B_树中每个结点的结构,树根结点或非树根结点中关键字的个数范围和子树的个
数范围,B_树的结构特性,从B_树上查找一个给定值元素的过程。
【一般掌握】
1.索引查找和分块查找算法。
2. B_树查找算法。
3.向B_树中插入元素的过程。
对本章的其余内容均作一般了解。
第九章 排序
【重点掌握】
1.直接插入、直接选择和冒泡排序的方法,排序过程及时间复杂度。
2.在堆排序中建立初始堆的过程和利用堆排序的过程,对一个分支结点进行筛运算的
过程、算法及时间复杂度,整个堆排序的算法描述及时间复杂度。
3.快速排序的方法,对一组数据的排序过程,对应的二叉搜索树,快速排序过程中划
分的层数和递归排序区间的个数。
4.递归排序的递归算法,它在平均情况下的时间和空间复杂度,在最坏情况下的时间
和空间复杂度。
5.二路归并排序的方法和对数据的排序过程,每趟排序前、后的有序表长度,二路归
并排序的趟数、时间复杂度和空间复杂度。
【一般掌握】
1.每一种排序方法的稳定性。
2.直接插入排序和直接选择排序的算法。
【一般了解】
1.二路归并排序过程中涉及的每个算法描述。
2.冒泡排序算法。
综合练习一
一、单选题(每题 2 分,共20分)
1.以下数据结构中哪一个是线性结构?( )
A.有向图 B.队列
C.线索二叉树 D. B树
2.在一个单链表HL中,若要在当前由指针p指向的结点后面插入一个由q指向的结
点,则执行( )语句序列。
A. p=q; p->next=q
B. p->next=q; q->next=p
4
C. p->next=q->next; p=q
D. q->next=p->next; p->next=q
3.以下哪一个不是队列的基本运算?( ) A.在队列第i个元素之后插入一个元素
B.从队头删除一个元素
C.判断一个队列是否为空
D.读取队头元素的值
4.字符A、B、C依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以
组成( )个不同的字符串。
A.14 B.5 C.6 D.8
5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为( )。
A.11 B.35 C. 19 D. 53
6.如图1,该二叉树结点的前序遍历的序列为( )。 A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
图1 7.如图1,该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D.B、D、C、A、F、G、E
8.如图1,该二叉树的按层遍历的序列为( )。 A. E、G、F、A、C、D、B
B. E、A、C、B、D、G、F
C. E、A、G、C、F、B、D
D. E、G、A、C、D、F、B
9.下面关于图的存储的叙述中正确的是( )。 A.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关
B.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关
C.用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关
D.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无
关
10.设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出
发建堆的结果?( )
A. a,g,h,m,n,p,q,x,z
B. a,g,m,h,q,n,p,x,z
C. g,m,q,a,n,p,x,h,z
D. h,g,m,p,a,n,q,x,z
二、填空题(每空1分,共26分)
1.数据的物理结构被分为_______、_______、_______和_______四种。
5
2.对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为_______,在表尾插入元素的时间复杂度为_______。
3.向一个由HS指向的链栈中插入一个结点p时,需要执行的操作是_______,删除一个结点时,需要执行的操作是_______(假设栈不空而且无需回收被删除结点)。
4.对于一棵具有n个结点的二叉树,一个结点的编号为i(1?i?n),若它有左孩子,则左孩子结点的编号为_______;若它有右孩子,则右孩子结点的编号为_______;若它有双亲,则双亲结点的编号为_______。
5.当向一个大根堆插入一个具有最大值的元素时,需要逐层_______调整,直到被调整到_______位置为止。
6.以二分查找方法从长度为10的有序表中查找一个元素时,平均查找长度为
_______。
7.表示图的三种常用的存储结构为_______、_______和_______。
8.对于线性表(70,34,55,23,65,41,20)进行散列存储时,若选用H(K)=K %7作为散列函数,则散列地址为0的元素有_______个,散列地址为6的有_______个。
9.在归并排序中,进行每趟归并的时间复杂度为_______,整个排序过程的时间复杂度为______,空间复杂度为______。
10.在一棵m阶B_树上,每个非树根结点的关键字数目最少为______个,最多为______个,其子树数目最少为_______,最多为_______。
三、运算题(每题 6 分,共24)
1. 写出下列中缀表达式的后缀形式:
13X/(Y-2)+1 ()
22+X*(Y+3) ()
2图
2.2 试对图中的二叉树画出:
1 ()顺序存储表示的示意图;
2 ()二叉链表存储表示的示意图。
3.? , 判断以下序列是否是小根堆如果不是将它调整为小根堆。
1{12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } ()
2{05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }()
4.VE 已知一个图的顶点集和边集分别为:
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)2
5};
按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的
各条边。
四、阅读算法(每题7分,共14分)
1.void AE(Stack& S){
InitStack(S);
Push(S,3);
Push(S,4);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[5]={1,5,8,12,15};
for(i=0;i<5;i++) push(s,2*a[i]);="">5;i++)>
6
while(!StackEmpty(S)) cout<><<' ';=""><'>
}
该算法被调用后得到的输出结果为:_____________。
2.void ABC (BTNode *BT,int &c1,int &c2) {
if (BT !=NULL ) {
ABC(BT->left,c1,c2);
c1++;
if (BT->left==NULL&&BT->right==NULL) c2++;
ABC(BT->right,c1,c2);
}//if
}
该函数执行的功能是什么? 五、算法填空(共8分) 向单链表的末尾添加一个元素的算法。
Void InsertRear(LNode*& HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
If (______________________)
{
cerr<<"memory allocation=""><"memory>
exit(1);
}
________________________=item;
newptr->next=NULL;
if (HL==NULL)
HL=__________________________;
else{
LNode* P=HL;
While (P->next!=NULL)
____________________;
p->next=newptr;
}
}
六、编写算法(共8分) 编写从类型为List的线性表L中将第i个元素删除的算法,(假定不需要对i的值进
行有效性检查,也不用判别L是否为空表。)
void Delete(List& L, int i)
【参考答案】
一、单选题
1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B
二、填空题
1.顺序 链表 索引 散列
2. O(n) O(1)
3.p->next=HS;HS=p HS=HS->next
4.2i 2i+1 ,i/2,(或i/2)
5.向上 根
7
6.2.9
7.邻接矩阵 邻接表 边集数组
8.1 4
9.O(n) O(nlogn) O(n) 2,,,, 10. m/2-1 m-1 m/2m
三、运算题
1.(1)3 X * Y 2 - / 1 +
(2)2 X Y 3 + * +
2.(1)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 (2)见图3所示。
图3
3.(1)不是小根堆。调整为:{12,24,33,65,33,56,48,92,86,70}
(2)是小根堆。
4.普里姆算法从顶点1出发得到最小生成树为:
(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
四、阅读算法
1. 30 24 16 10 2 10
2.该函数的功能是:统计出BT所指向的二叉树的结点总数和叶子总数。
五、算法填空
newptr==NULL newptr->=data newptr
p=p->next
六、编写算法
void Delete(List& L, int i)
{
for(int j=i-1;j
L.list[j]=L.list[j+1]; //第i个元素的下标为i-1
L.size--;
}
综合练习二 一、单选题(每题 2 分,共20分)
1.在一个带有附加表头结点的单链表HL中,若要向表头插入一个由指针p指向的结
点,则执行( )。
A. HL=p; p->next=HL;
B. p->next=HL->next; HL->next=p;
C. p->next=HL; p=HL;
D. p->next=HL; HL=p;
2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储( )个元素。
8
A. n B.n-1 C. n+1 D.不确定
3.下述哪一条是顺序存储方式的优点?( )
A.存储密度大
B.插入和删除运算方便
C.获取符合某种条件的元素方便
D.查找运算速度快
4.设有一个二维数组A[m][n],假设A[0][0]存放位置在600,A[3][3]存放位置在(10)678,每个元素占一个空间,问A[2][3]存放在什么位置?(脚注表示用10进制表(10)(10)(10)示,m>3)( )
A.658 B.648 C.633 D.653
5.下列关于二叉树遍历的叙述中,正确的是( )。
A.若一个树叶是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍
历最后一个结点
B.若一个点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的
最后一个结点
C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最
后一个结点
D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后
一个结点
6. k层二叉树的结点总数最多为( )。
A. 2kkkk-1-1 B.2+1 C.2-1 D. 2
7.对线性表进行二分法查找,其前提条件是( )。
A.线性表以链接方式存储,并且按关键码值排好序
B.线性表以顺序方式存储,并且按关键码值的检索频率排好序
C.线性表以顺序方式存储,并且按关键码值排好序
D.线性表以链接方式存储,并且按关键码值的检索频率排好序
8.对n个记录进行堆排序,所需要的辅助存储空间为( )。
A. O(1ogn) B. O(n) 22C. O(1) D. O(n)
9.对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)
=K %7作为散列函数,则散列地址为0的元素有( )个。 A.1 B.2 C.3 D.4
10.下列关于数据结构的叙述中,正确的是( )。 A.数组是不同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构
D.用一维数组存储一棵完全二叉树是有效的存储方法 二、填空题(每空1分,共26分)
1.数据的逻辑结构被分为_______、_______、_______和_______四种。 2.一个算法的时间复杂度为(3n32+2000nlogn+90)/n,其数量级表示为_______。 2
3.对于一个长度为n的单链存储的队列,在表头插入元素的时间复杂度为_______,
在表尾插入元素的时间复杂度为_______。
4.假定一棵树的广义表表示为A(D(E,G),H(I,J)),则树中所含的结点数为_______
个,树的深度为_______,树的度为_______。
5.后缀算式79 2 30 + - 4 2 / *的值为_______。中缀算式(3+X*Y)-2Y/3
对应的后缀算式为_______。
9
6.在一棵高度为5的理想平衡树中,最少含有_______个结点,最多含有_______个结点。
7.在树中,一个结点的直接后继结点称为该结点的_______。一个结点的直接前趋结点称为该结点的_______。
8.在一个具有10个顶点的无向完全图中,包含有_______条边,在一个具有n个顶点的有向完全图中,包含有_______条边。
9.假定一个线性表为(12,17,74,5,63,49,82,36),若按Key % 4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为_______、_______、_______和_______。
10.对一棵B_树进行删除元素的过程中,若最终引起树根结点的合并时,会使新树的
高度比原树的高度_______。
11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为______,整个堆排序过程的时间复杂度为______。
12.在线性表的散列存储中,装填因子,又称为装填系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则,等于_______。
三、运算题(每题 6 分,共24分)
1.在如下数组A中链接存储了一个线性表,表头指针存放在A [ 0].next,试写出该线性表。
A 0 1 2 3 4 5 6 7
data 60 50 78 90 34 40
next 4 0 5 2 7 1 3
2.已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。
3.已知一个图的顶点集V为: V={1,2,3,4,5,6,7};
其共有10条边。该图用如下边集数组存储:
起点 1 2 2 5 5 2 2 6 1 3
终点 6 4 5 4 7 6 7 7 7 5
权 1 1 2 2 2 3 3 4 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。
4.画出向小根堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时,每加入一个数据后堆的变化。
四、阅读算法(每题7分,共14分)
1.在下面的每个程序段中,假定线性表La的类型为List,元素类型ElemType为int,并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。
(1)InitList(La);
Int a[]={100,26,57,34,79};
For (i=0;i<5;i++)>5;i++)>
Insert(La,a[i]);
TraverseList(La);
(2)DeleteFront(La);
InsertRear(La, DeleteFront(La));
TraverseList(La);
(3)ClearList(La);
For (i=0;i<5;i++)>5;i++)>
InsertFront(La,a[i]);
TraverseList(La);
2.下面算法的功能是什么?
10
void ABC(BTNode * BT)
{
if BT {
cout ABC(BT->left); ABC(BT->right); } } 五、算法填空(共8分) 二分查找的递归算法。 Int Binsch(ElemType A[],int low,int high,KeyType K) { if ______________{ int mid=(low+high)/2; if (________________) return mid; //查找成功,返回元素的下标 else if (K return Binsch(A,low,mid-1,K); //在左子表上继续查找 else return___________; //在右子表上继续查找 } else ______________; //查找失败,返回-1 } 六、编写算法(共8分) HL为单链表的表头指针,试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item) 【参考答案】 一、单选题 1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D 10.D 二、填空题 1.集合结构 线性结构 树结构 图结构 2. O(n) 3. O(1) O(1) 4. 7 3 2 5. 94 3 X Y * + 2 Y * 3 / - 6. 16 31 7.孩子(或子)结点 双亲(或父)结点 8. 45 n(n-1) 9.(12,36) (17,5,49) (74,82) (63) 10.减少1(或减少) 11. O(logn) O(nlogn) 2212. n/m 三、运算题 1.线性表为:(90,40,78,50,34,60) 2.当前序序列为ABKCDFGHIJ,中序序列为KBCDAFHIGJ时,逐步形成二叉树的 过程如下图4所示: 11 图4 3.用克鲁斯卡尔算法得到的最小生成树为: (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4.见图5。 图5 四、阅读算法 1.(1)La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2.前序遍历链式存储的二叉树。 五、算法填空 (low<=high)>=high)> K==A[mid].key Binsch(A,mid+1,hight,K) return -1 六、编写算法 bool Find(LNode* HL, ElemType &item) { LNode* p=HL; while p if (p->data==item){ return true; } else p=p->next; return false; } 12 综合练习三 一、单选题(每题 2 分,共20分) 1.对一个算法的评价,不包括( )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行 ( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( )。 A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种( )。 A.有向图 B.无向图 C.无向无环图 D.有向无环图 6.采用开放定址法处理散列表的冲突时,其平均查找长度( )。 A.低于链接法处理冲突 B.高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.若需要利用形参直接访问实参时,应将形参变量说明为( )参数。 A.值 B.函数 C.指针 D.引用 8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的 ( )。 A.行号 B.列号 C.元素值 D.非零元素个数 9.快速排序在最坏情况下的时间复杂度为( )。 A. O(log n) B. O(nlogn) 222C. O(n) D. O(n) 10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) 2C. O(logn) D. O(n) 2 二、填空题(每题 6 分,共24分) 1.数据结构是指数据及其相互之间的_______。当结点之间存在M对N(M?N)的 联系时,称这种结构为_______。 2.队列的插入操作是在队列的_______进行,删除操作是在队列的_______进行。 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的 13 条件是_______。 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_______,在表尾插入元素的时间复杂度为_______。 5.设W为一个二维数组,其每个数据元素占用4个字节,行下标i从0到7 ,列下标j从0到3 ,则二维数组W的数据元素共占用_______个字节。W中第6 行的元素和第4 列的元素共占用_______个字节。若按行顺序存放二维数组W,其起始地址为100,则二维数组元素W[6,3]的起始地址为_______。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为_______,它的长度为_______。 7.二叉树是指度为2的_______树。一棵结点数为N的二叉树,其所有结点的度的总 和是_______。 8.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个_______。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_______。 9.对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为_______个,其中_______个用于指向孩子,_______个指针是空闲的。 10.若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维 数组A中,即编号为0的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为_______,右孩子元素为_______,双亲元素为_______。 11.在线性表的散列存储中,处理冲突的常用方法有_______和_______两种。 12.当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用_______排序;当待排序的记录数较大,存储空间允许且要求排序是稳定时,宜采用_______排序。 三、运算题(每题6分,共24分) 1.已知一个6,5稀疏矩阵如下所示,试: 00001,, ,,00000,, ,,0,1000,,0000,2,, ,,50000,,00700,,,, (1)写出它的三元组线性表; (2)给出三元组线性表的顺序存储表示。 2.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起,逐个输入各 个数据而生成的二叉搜索树。 3.对于图6所示的有向图若存储它采用邻接表,并且每个顶点邻接表中的边结点都是 按照终点序号从小到大的次序链接的,试写出: 1 ()从顶点?出发进行深度优先搜索所得到的深度优先生成树; 2 ()从顶点?出发进行广度优先搜索所得到的广度优先生成树。 图6 4.已知一个图的顶点集V和边集E分别为: V={1,2,3,4,5,6,7}; 14 E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}; 若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大 的次序链接的,按主教材中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序 列。 四、阅读算法(每题7分,共14分) 1. int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x)>=x)> if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能; (2)该算法的时间复杂度是多少? 2.写出下述算法的功能: void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<><<' ';=""><'> visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout<><<' ';=""><'> visited[j]=true; QInsert(Q,j); } p=p->next; } } } 五、算法填空(共8分) 如下为二分查找的非递归算法,试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high)>=high)> { int mid=_____________________________; if (K==A[mid].key) return mid; //查找成功,返回元素的下标 else if (K<[mid].key)>[mid].key)> 15 ____________________________________;//在左子表上继续查找 else _________________________________; //在右子表上继续查找 } return -1; //查找失败,返回-1 } 六、编写算法(共8分) HL是单链表的头指针,试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL) 【参考答案】 一、单选题 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、填空题 1.联系 图(或图结构) 2.尾 首 3. top==0 4. O(1) O(n) 5. 128 44 108 6. 3 3 7.有序 n-1 8.有序序列 后缀表达式(或逆波兰式) 9. 2n n-1 n+1 10. 2i+1 2i+2 (i-1)/2 11.开放定址法 链接法 12.快速 归并 三、运算题 1.(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (2)三元组线性表的顺序存储表示如图7所示。 6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 图7 6 3 7 2.如图8所示。 图8 3. DFS:????? BFS:????? 4.拓朴排序为: 4 3 6 5 7 2 1 16 四、阅读算法 1.(1)判断n是否是素数(或质数),若是返回1,否则返回0。 n(2)O() 2.功能为:从初始点v出发广度优先搜索由邻接表GL所表示的图。 i 五、算法填空 (low+high)/2 high=mid-1 low=mid+1 六、编写算法 ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<> exit(1); } LNode* p=HL; HL=HL->next; ElemType temp=p->data; delete p; return temp; } 综合练习四 一、单选题(每题 2 分,共20分) 1.以下数据结构中哪一个是线性结构?( ) A.有向图 B.栈 C.二叉树 D. B树 2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点, 则采用( )存储方式最节省时间。 A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表 3.以下哪一个不是队列的基本运算?( ) A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素 C.判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C、D依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多 可以组成( )个不同的字符串。 A.15 B.14 C.16 D.21 5.由权值分别为4,7,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为( )。 A. 11 B. 37 C. 19 D. 53 6-8题基于下面的叙述:若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、 G,后序遍历的序列为B、D、C、A、F、G、E。 6.该二叉树结点的前序遍历的序列为( )。 A. E、G、F、A、C、D、B 17 B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树有( )个叶子。 A.3 B.2 C. 5 D. 4 8.该二叉树的按层遍历的序列为( )。 A. E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面的二叉树中,( )不是完全二叉树。 10.设有关键码序列(q,g,m,z,a),下面哪一个序列是从上述序列出发建的小根堆 的结果?( ) A. a,g,m,q,z B. a,g,m,z,q C. g,m,q,a,z D. g, m,a,q,z 二、填空题(每空1分,共26分) 1.数据结构是指数据及其相互之间的_______。当结点之间存在1对N(1?N)的联系时,称这种结构为_______。 2.一个广义表中的元素分为_______元素和_______元素两类。 3.对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为_______,在表尾插入元素的时间复杂度为_______。 4.向一个由HS指向的链栈中插入一个结点p时,需要执行的操作是_______;删除一个结点时,需要执行的操作是_______(假设栈不空而且无需回收被删除结点)。 5.栈又称为_______表,队列又称为_______表。 6.在稀疏矩阵所对应的三元组线性表中,每个三元组元素按_______为主序、_______为辅序的次序排列。 7.若一棵二叉树中只有叶子结点和左、右子树皆非空的结点,设叶结点的个数为K,则左、右子树皆非空的结点个数是_______。 8.以折半(或二分)查找方法从长度为8的有序表中查找一个元素时,平均查找长度 为_______。 9.表示图的三种常用的存储结构为_______、_______和_______。 10.对于线性表(78,4,56,30,65)进行散列存储时,若选用H(K)=K %5作为散列函数,则散列地址为0的元素有_______个,散列地址为4的有_______个。 11.在归并排序中,进行每趟归并的时间复杂度为______,整个排序过程的时间复杂 度为______,空间复杂度为______。 12.在n个带权叶子结点构造出的所有二叉树中,带权路径长度最小的二叉树称为 18 _______。WPL称为_______。 13.在索引表中,若一个索引项对应主表的一个记录,则此索引为_______索引,若对 应主表的若干条记录,则称此索引为_______索引。 三、运算题(每题 6 分,共24分) 1. 写出下列中缀表达式的后缀形式: 13X/(Y-2H)+1 () 22+X*(Y+3) () 2.a(b(c),d(e,f))假定一棵二叉树广义表表示为,分别写出对它进行先序、中序、后序、 按层遍历的结果。 3.{a, b, c, d, e} 已知一个无向图的顶点集为,其邻接矩阵如下所示: 01001,, ,,10010,,a ,,00011b ,,01101,,c ,,10110,,d (1)画出该图的图形; e (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。 4.VE 已知一个图的顶点集和边集分别为: 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}; 按照普里姆算法从顶点0出发得到最小生成树,试写出在最小生成树中依次得到的各条边。 四、阅读算法(每题7分,共14分) 1.void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={2,5,8,22,15}; for(i=0;i<5;i++) push(s,a[i]);="">5;i++)> while(!StackEmpty(S)) cout<><<' ';=""><'> } 该算法被调用后得到的输出结果为:_____________。 2.int akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; else if ( n == 0 ) return akm ( m-1, 1 ); else return akm ( m-1, akm ( m, n-1 ) ); } 该函数执行的功能是什么? 五、算法填空(共8分) 二叉搜索树的查找——非递归算法 bool Find(BTreeNode* BST,ElemType& item) {while(BST(!=NULL){ 19 if (item==______________){ item=BST->data;//查找成功 return true;} else if(item BST=BST->_____________; else BST=BST->_____________; }//while return _____________; //查找失败 } 六、编写算法(共8分) 用递归的算法编写出对存入在a[n+1]数组中的n个有序元素进行二分(又称折半) 查找(假定a[0]单元不用)的程序。 int halfsearch(SSTable *a, KeyType k,int low,int high) 【参考答案】 一、单选题 1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B 二、填空题 1.联系 树(或树结构) 2.单 (子)表 3. O(n) O(1) 4. p->next=HS;HS=p HS=HS->next 5.先进后出 先进先出 6.行 列 7. k-1 8. 2.625 9.邻接矩阵 邻接表 边集数组 10. 2 1 11. O(n) O(nlogn) O(n) 2 12.哈夫曼树 带权路径长度 13.稠密 稀疏 三、运算题 1.(1)3 X * Y 2 H *- / 1 + (2)2 X Y 3 + * + 2. 先序: a,b,c,d,e,f 中序: c,b,a,e,d,f 后序: c,b,e,f,d,a 按层: a,b,d,c,e,f 3.(1)该图的图形如图9所示。 图9 20 (2)深度优先遍历序列为:abdce 广度优先遍历序列为:abedc 4.普里姆:(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20 四、阅读算法 1. 15 22 8 5 2 10 2.该函数的功能是: 求 n,1 当m,0 时,,akm(m,n),akm(m,1,1) 当m,0,n,0 时,,akm(m,1,akm(m,n,1)) 当m,0,n,0 时, 五、算法填空 BST->data left right false 六、编写算法 递归算法: int halfsearch(SSTable *a, KeyType k,int low,int high) { if (low>high) return 0; else { int mid=(low+high)/2 if EQ(k,a[mid].key) return mid; else if LT(k,a[mid].key) return halfsearch(a,k,low,mid-1); else return halfsearch(a,k,mid+1,high); } } 综合练习五 一、单选题(每题 2 分,共20分) 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列,在进行插入运算时( )。 A.仅修改头指针 B.头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构?( ) A.队列 B.栈 C.线性表 D.二叉树 4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在(10) 676,每个元素占一个空间,问A[3][3]存放在什么位置?脚注表示用10进制表示。(10)(10)(10) ( ) A. 688 B. 678 C. 692 D. 696 5.树最适合用来表示( )。 A.有序数据元素 21 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 5.二叉树的第k层的结点数最多为( )。 kkkk-1A. 2-1 B.2+1 C.2-1 D. 2 6.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( )。 A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 7.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为( )。 2A. O(1) B. O(n) C. O(1ogn) D. O(n) 2 8.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有( )个。 A. 1 B. 2 C. 3 D. 4 9.设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 二、填空题(每空1分,共26分) 1.通常从四个方面评价算法的质量:_______、_______、_______和_______。 2.一个算法的时间复杂度为(n322+nlogn+14n)/n,其数量级表示为_______。 2 3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为_______个,树的深度为_______,树的度为_______。 4.后缀算式9 2 3 +- 10 2 / -的值为_______。中缀算式(3+4X)-2Y/3对应的后缀算式为_______。 5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两 个指针。在这种存储结构中,n个结点的二叉树共有_______个指针域,其中有_______个指针域是存放了地址,有________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边 结点分别有______个和______个。 7.AOV网是一种_______的图。 8.在一个具有n个顶点的无向完全图中,包含有_______条边;在一个具有n个顶点的有向完全图中,包含有_______条边。 9.假定一个线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分,使得同一余数 的元素成为一个子表,则得到的四个子表分别为_______、_______、_______和_______。 10.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高 度_______。 11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为______,整个堆排序过程的时间复杂度为______。 12.在快速排序、堆排序、归并排序中,_______排序是稳定的。 三、运算题(每题 6 分,共24分) 1.在如下数组A中链接存储了一个线性表,表头指针为A [0].next,试写出该线性表。 A 0 1 2 3 4 5 6 7 Data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图10的邻接矩阵和邻接表。 22 图10 3.已知一个图的顶点集V和边集E分别为: V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时,每加入一个数据后堆的变化。 四、阅读算法(每题7分,共14分) 1. LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L->next;p=L; S1: while(p->next) p=p->next; S2: p->next=q;q->next=NULL; } return L; } 请回答下列问题: (1)说明语句S1的功能; (2)说明语句组S2的功能; (3)设链表表示的线性表为(a ,a, …,a),写出算法执行后的返回值所表示的线性12n表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout } } 该算法的功能是:__________________。 五、算法填空(共8分) 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); 23 }//if } 六、编写算法(共8分) 统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) 【参考答案】 一、单选题 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题 1.正确性 易读性 强壮性 高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7.有向无回路 8. n(n-1)/2 n(n-1) 9.(12,40) ( ) (74) (23,55,63) 10.增加1 11. O(logn) O(nlogn) 22 12.归并 三、运算题 1.线性表为:(78,50,40,60,34,90) 01110,,,,10101,,,,11011,,10101,,,,2.邻接矩阵:01110,, 邻接表如图11所示: 图11 3.用克鲁斯卡尔算法得到的最小生成树为: (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4.见图12。 24 图12 四、阅读算法 1.(1)查询链表的尾结点 (2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a,a,…,a,a) 23n12.递归地后序遍历链式存储的二叉树。 五、算法填空 true BST->left BST->right 六、编写算法 int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时i中的值即为x结点个数 return i; }//CountX 25 《数据结构》是计算机软件的重要核心基础课程之一.计算机科学各领域及有关的系统...4.掌握算法设计的步骤和基本的算法分析的方法.通过对不同的数据结构与算法的对比... 数据结构,算法 专题技术 牛档搜索(Niudown.COM) 本文系牛档搜索(Niudown.COM)根据用户的指令自动搜索的结果,文中内涉及到的资料均来自互联 网,用于学习交流经验,作品其著作权归原作者所有。不代表牛档搜索(Niudown.COM)赞成本文的内容或立场,牛档搜索(Niudown.COM)不对其付相应的法律责任! 实验教学大纲与指导 湖南商学院信息系计算机应用教研室 数据结构 Data Structure 030504 信息管理与信息系统、信息与计算科学、统计学。 第4学期 非独立开课 72学时/4学分(讲授54/实验18) 《数据结构(C语言版)》严蔚敏,清华大学出版社,2004年4月第3版。 计算机基础、C程序设计。 周 纳 《数据结构》是计算机软件的重要核心基础课程之一。计算机科学各领域及有关的系统 和应用软件都要用到各种数据结构。《数据结构》也是信息管理与信息系统、信息与计算科学、 统计学等专业重要的基础课程之一。《数据结构》课程由三部分内容组成:1. 以抽象数据类型为对象讨论线性表、栈、队列、串、数组、广义表、树和图等典型数据结构;2.排序和查找的原理与方法;3.外存的数据组织方法和内存动态存储管理。通过本课程的学习,使学生 熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法,以及有关基本操作的算法 实现;熟悉它们在计算机科学中的基本应用;培养和训练学生根据求解的问题合理选择数据 结构,应用高级语言编写和实现结构清晰和正确易读的算法,以及评价基本算法的能力。 通过本课程的学习,应能达到下列基本要求: 1.掌握数据结构的基本概念及其分类,数据结构与数据类型、抽象数据类型的关系,数 据结构与算法的关系。 2.掌握各种基本数据结构的特点、它们的内在逻辑关系及计算机中的表示方法和基本操 作的实现方法,熟悉它们在计算机科学中的基本应用。 3.进一步深入理解掌握递归的概念、递归算法的设计、递归算法的执行以及递归算法与 迭代算法之间的关系。 4.掌握算法设计的步骤和基本的算法分析的方法。通过对不同的数据结构与算法的对比, 学会根据问题的要求合理选择数据结构、设计算法并控制求解算法的空间和时间的复杂性的 能力。 5.掌握数据结构在排序和查找等常用算法中的应用。 6.了解文件的组织方法和索引技术。 1 7.能基于一种计算机程序设计语言(C语言)实现上述数据结构。 本课程是一门实践性较强的软件基础课程,上机实验是对学生的一种综合训练。考虑到 本大纲适应于非计算机专业学生,安排上机时数为18学时。利用C程序设计进行数据结构实验,培养学生的良好程序设计风格,提高分析问题和解决问题的能力。 通过上机作业,要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法 设计及其实现等方面加深对课程基本内容的理解,同时在程序设计的方法、风格以及上机操 作、程序调试等基本技能和科学作风方面受到比较系统和严格的训练。 教师根据学生作业中出现的主要问题,适当组织习题课或课堂讨论,以拓宽学生思路, 提高分析问题解决问题的能力。 2 (2学时) 掌握线性表的基本操作:插入、删除、查找以及线性表合并等运算在顺序存储结构和链 接存储结构上的运算。建立源程序,调试运行,分析结果。 1.构立学生成绩单链表,实现对它的记录的遍历、插入和删除。 ? 建立单链表 成绩单的每条记录便是一个数据元素,其对应的结构类型定义如下: struct student { int num; /*学号*/ float score; /*成绩*/ struct student *next; /*指针域*/ }; 构造单链表如下: struct student *creat() /*此函数返回一个指向链表的头结点*/ { struct student *head; /*指向student类型变量的指针head为头指针*/ struct student *p,*tail; /*tail指向链表末尾元素,p指向新分配的结点*/ float temp; /*临时数据变量*/ head=NULL; do { p=(struct student *)malloc(sizeof(struct student));/*分配新结点*/ printf(“Number Score:”); fflush(stdin); /*清除输入缓冲区*/ scanf("%d %f",&p->num,&temp); 3 if(p->num==0) { free(p); break; }; p->score=temp; /*取得结点数据*/ p->next=NULL; if(head==NULL) { head=p; tail=p; } else { tail->next=p; tail=p; /*指向尾结点*/ } }while(p->num!=0); return(head); } 以上算法的思路是:让p指向新开辟的结点,tail指向链表中最后一个结点,把p所指 向的结点链接在tail所指向的结点的后面,由语句“tail->next=p”来实现。 ? 遍历单链表 遍历单链表就是将链表中的各结点的数据依次输出。 显然,首先应知道链表的头指针head(即第一个结点元素的地址),然后设一个指针变 量p,先指向第一个结点,输出p所指的结点,然后使p后移一个结点,再输出,直到链表 的尾结点。 算法:遍历单链表。 void display(struct student *head) { struct student *p; p=head; while(p!=NULL) { printf("%4d %5.1f\n",p->num,p->score); p=p->next; } } 4 ? 在单链表中插入数据元素 在单链表中插入数据元素的首要问题描述为:已知p为指向单链表元素a的指针,要在 单链表中的两个元素a和b之间插入一个新的元素x。 为插入数据元素x,首先要生成一个数据域为x的结点,然后将其插入到单链表中。根 据插入的逻辑定义,需要修改结点a中的指针域,令其指向x,而结点x中的指针域应指向 结点b从而实现三个元素的逻辑关系变化。 设s为指向x的指针,则语句描述如下: s->next=p->next; p->next=s; 在实际应用中,当在一个单链表中插入一个新元素x时,首先需要查找元素x的插入位 置,然后插入。下面的算法设前面所建立的链表是按学号升序排列的,今要在其中插入一新 的结点,插入后链表仍然按学号升序排列。 算法如下: struct student *insert(struct student *head,struct student *new) { struct student *p,*q; if(head==NULL) head=new; else { if(head->num>=new->num) { new->next=head; head=new; }/*新结点插在链首*/ else { p=head; while(p->num { q=p; p=p->next; } if(p->num>new->num) { q->next=new; new->next=p; } 5 else { p->next=new; new->next=NULL; } } } return(head); } 以上算法的思路是:首先判断头结点是否为空,若为空,则把新结点作为头结点;否则 判断是否插在第一个结点的前面。如果插入位置在第一个结点之前,则将head赋给 new->next,将new赋给head;否则,在链表中查找插入位置p,然后把新结点new连到p 的后面。 ? 在单链表中删除数据元素 算法如下: struct student *delete(struct student *head,int num) /*在头结点为head的单链表中将指定的学号为num的结点删除*/ /*算法返回新的链表的表头结点*/ { struct sudent *p1,*p2; /*设置两个指针,用以指示删除位置*/ if(head==NULL) printf(“\nList null\n”); else { p1=head; while(num!=p1->num&&p1->next!=NULL) /*p1所指的结点不是要删除的结点,且其后还有结点*/ { p2=p1; p1=p1->next;/*后移一个结点*/ } if(num==p1->num)/*找到了要删除的结点*/ { if(p1==head) head=p1->next; /*若p1所指为第一个结点,则把第二个结点的地址赋给head*/ else p2->next=p1->next; /*否则将下一个结点的地址赋给前一个结点的指针域*/ 6 printf(“delete:%4d\n”,num); free(p1); } else printf(“%4d not been found!\n”,num); } return(head); } ? 主函数的实现 #define LEN sizeof(struct student) #include #include #include #include struct student { int num; float score; struct student *next; }; void main() { struct student *head,*stu; float temp; int number; clrscr(); printf(“Input records:\n”); head=create(); display(head); stu=(struct student *)malloc(LEN); printf(“Input the insert Number Score:”); scanf(“%d %f”,&stu->num,&temp); stu->score=temp; stu->next=NULL; head=insert(head,stu); display(head); printf(“\nInput the number to delete:”); scanf(“%4d”,&number); 7 head=delete(head,number); display(head); getch(); } (2学时) 掌握栈与队列的基本操作,并能对其进行简单应用。建立源程序,调试运行,分析结果。 1.顺序栈的表示和实现 和线性表类似,栈也有两种存储表示方法,即有两种存储结构:顺序存储结构和链表存 储结构。前者称为顺序栈,后者称为链栈。顺序栈是利用一组地址连续的存储单元依次存放 自栈底到栈顶的数据元素,同时高指针top指示栈顶元素的当前位置。空栈的栈顶指针值为 0。 可以用C语言中的一维数组S[M]作为栈的顺序存储结构,其中M是预先给定的常量。根 据C语言对一维数组S[M]的定义,S数组的元素为S[0],S[1],S[2],...,S[M-1]共M个元素。因此,M表示栈的最大容量。由于栈顶位置是经常变动的,故设置一个简单变量top来指示栈顶位置,top称为栈顶指针。我们约定top指向实际栈顶的下一个空位置,即新数 据元素将压入的位置。请看如下的示意图。 栈顶 4 4 4 4 3 3 3 3 2 2 2 ?top 2 1 1 ?top 1 1 ?top 48 0 ?top 0 0 0 30 30 30 栈底 (a)栈空 (b)30进栈 (c)48进栈 (c)48退栈 注意,当top=0时,说明栈为空,若再有进行退栈操作,则出现下溢;当进栈操作时, top的值加1;当退栈操作时,top的值减1;当top>=M时,若再有数据元素时栈,栈将上溢。 下面的进栈和出栈算法中,s数组用来存放栈元素,栈顶指针为top。 在进栈算法中,当栈满时,函数返回值为0,否则函数返回值为1。 8 #include #define M 10 typedef struct stack1 { int s[M]; int top; }stacktype; int push(stacktype *st,int x) { if(st->top==M) { printf(“Overflow”); return(0); } st->s[st->top]=x; st->top++; return(1); } 从顺序栈s中取出栈顶元素,若栈空,函数返回值为0,否则函数返回值为取出的元素。 算法如下: int pop(stacktype *st) { if(st->top==0) { printf(“Stack empty”); return(0); } st->top--; return(st->s[st->top]); } 下面给出调用进栈和出栈算法的主程序: main() { stacktype y; int i,z=0; y.top=0; for(i=0;i { scanf(&z); push(&y,z); 9 } for(i=0;i { z=pop(&y); printf(“%d”,z); } } 2.链队列的表示和实现 用链表表示的队列简称链队列,如图所示。 一个链队列显然需要两个分别指向队头和队尾的指针f和(分别称为头指针和尾指针)。r 为了操作方便,我们可以给链队列添加一个表头结点,并令头指针f指向该结点,而尾指针 则指向队尾元素。由此,空的链队列的判决条件为头指针和尾指针均指向表头结点(即r=f)。 链队列中结点类型定义如下: typedef struct node { data int data; link struct node *link; }JD; f? 表头 在链队列上的入队和出队操作是在单链表上插入和删除操 ? 作的特殊情况,只是需要修改队尾或队首指针。 队头 下面给出有关链队列入队和出队的算法。在把元素x加入 ? 链队列的算法中,函数返回值为r,算法如下: JD *enlqueue(JD *r,int x) ? { ... JD *p; p=(JD *)malloc(sizeof(JD)); ? 队尾 if(p==NULL) r? ? { printf(“%s”, “Memory allocation failure”); exit(0); } p->data=x; p->link=NULL; r->link=p; return(p); } 从带头结点的链队列中删除队首元素并存到(*p)指向的变量中,若链队列为空,则函 数返回值为空指针,否则函数返回值为r。 10 JD *delqueue(JD *f,JD *r,int *p) { JD *s; if(f==r) { printf(“Queue Null”); return(NULL); } s=f->link; f->link=s->link; if(s->link==NULL) r=f; *p=s->data; free(s); return(r); } 下面给出对链队列进行操作的主函数: #include #include main() { JD *r,*f; int q; clrscr(); f=r=(JD *)malloc(sizeof(JD)); if(f==NULL) { printf(“%s”,“Memory allocation failure”); exit(0); } r=enlqueue(r,20); r=enlqueue(r,30); r=delqueue(f,r,&q); printf(“%d\n”,q); r=delqueue(f,r,&q); printf(“%d\n”,q); } 11 (2学时) 熟悉串的各种基本操作,并掌握其应用。建立源程序,调试运行,分析结果。 1.串的定长顺序存储表示实现 ? 一般方法 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。在串 的定长顺序存储结构中,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储 区,则可用定长数组描述如下: #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; 串的实际长度可在预定义长度的范围内随意,超过预定义长度的串值则被舍去,称之为 “截断”。对串长有两种表示方法,一是以下标为0的数组分量存放串的实际长度,PASCAL中采用这种方法;二是串值后面加一个不计入串长的结束标记字符,如在C语言中以“\0” 表示串值的终结,此时串长为隐含值。 在这种存储结构中如何实现串的操作呢,下面以串联接 Concat(&T,S1,S2)为例讨论。 假设S1、S2、T都是SString型的串变量,且T是由S1和S2联结得到的,则有下列三种情况不可不考虑:一是S1[0]+S2[0]?MAXSTRLEN,则T值为S1和S2正常联结得到。二是S1[0] Status Concat(SString &T,SString S1,SString S2) { if(S1[0]+S2[0]<=maxstrlen)>=maxstrlen)> { T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]]; T[0]=S1[0]+S2[0]; uncut=TRUE; } else if(S1[0] { T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; 12 T[0]=MAXSTRLEN; uncut=FALSE; } else { T[0..MAXSTRLEN]=S1[0..MAXSTRLEN]; uncut=FALSE; } } ? C程序实现 #include #define MAX 100 typedef struct //定义串 { char *vec; int length; }String; void Display(String *s) //显示串 { int i; printf("\n"); for(i=0;i printf("%c",s->vec[i]); } String *Concat(String *r1,String *r2) //连接串 { int i,len; String *r; len= r1->length + r2->length; if(len>MAX) printf("\n Overflow \n"); else { for(i=0;i r->vec[i]=r1->vec[i]; for(i=r1->length;i r->vec[i]=r2->vec[i-r1->length]; 13 r->vec[len]='\0'; r->length=len; } return(r); } String *Substring(String *r1,int i,int j) //求子串 { int k; String *r; if(i+j-1>r1->length) printf("\n Outside error!\n"); else { for(k=0;k r->vec[k]=r1->vec[i+k-1]; r->length=j; r->vec[r->length]='\0'; } return(r); } int Index(String *r1,String *r2,int pos) //求子串位置 { int i,j,p; if ( (pos<1) ||="" (pos+r2-="">length) > (r1->length+1) || (r2->length==0) ) return(0); else { i=pos-1; j=0; while( i { if( r1->vec[i]==r2->vec[j] ) { i++; j++; } else { i=i-j+1; 14 j=0; } } if(j>=r2->length) { p=(i-(r2->length-1)+1); return(p); } else return(0); } } void main() { String *a,*b,*c,*d; int p; clrscr(); a->vec="abcdefghijk"; a->length=11; b->vec="fgh"; b->length=3; Display(a); Display(b); c=Concat(a,b); Display(c); d=Substring(a,3,4); Display(d); p=Index(a,b,1); printf("\nThe position is: %d \n",p); getch(); } 15 (4学时) 熟悉二叉树的特征,掌握二叉树的基本算法实现。建立源程序,调试运行,分析结果。 1.二叉树的建立 已知一棵二叉树,共有n个结点,如何建立该二叉树呢? 建立方法如下: a.按照完全二叉树的编号方法,对该二叉树进行编号。 b.每次输入一个结点的值x和该结点的编号k,动态申请一块空间来存放该结点,空间 的地址为p。 c.把p值赋给adr[k]中。 d.如果k=1,转到“f”;否则,把p的值填入其父结点的指针域中。p的父结点地址为 adr[k/2],若k为偶数,则做adr[k/2]->lc=p;若k为奇数,则做adr[k/2]->rc=p。 f.重复“b”到“d”,直到全部结点数据输入完为止。 下面给出C源程序清单: #define MAX 1000 struct node { int data; struct node *lc; /*left左指针*/ struct node *rc; /*right右指针*/ }; typedef struct node JD; JD *setuptree() { JD *adr[MAX]; JD *p; int i; /*i结点个数控制变量*/ int n; /*n为结点的个数*/ int x; /*x为结点的值*/ int k; /*k为结点的编号*/ int f; /*f左右结点控制变量*/ printf(“Enter the number of nodes”); 16 scanf(“%d”,&n); for(i=1;i<=n;i++)>=n;i++)> { p=(JD *)malloc(sizeof(struct node)); if(p==NULL) { printf(“Memory error”); exit(0); } else { p->lc=p->rc=NULL; printf(“Enter data”); scanf(“%d”,&p->data); printf(“Enter code of the node”); scanf(“%d”,&k); adr[k]=p; if(k>1) { f=k/2; if(k%2==0) adr[f]->lc=p; else adr[f]->rc=p; } } } return(adr[1]); } 2.前序遍历二叉树的非递归算法 使用栈来实现前序遍历二叉树的基本思想是: ? 从二叉树的根结点开始,沿左支一直走到没有左孩子的结点为止。 ? 在走的过程中访问所遇结点,并依次将所遇结点的非空右孩子进栈。 ? 当找到没有左孩子的结点时,如果该结点有右孩子,则从栈顶退出该结点的右孩子并 访问之,然后前序遍历该结点的右子树。 ? 如果该结点无右孩子,则从栈顶退出该结点的双亲或祖先的右孩子并访问之,然后前 序遍历该结点的双亲或祖先的右子树。 ? 按上述过程遍历所有子树,如此重复直到栈空。 17 例如右图的表达式二叉树的前序遍历非递归算法过程如下列所示。 访问+、*进栈、访问a、*出栈并访问之、+进栈、访问b、+出栈并访问之、*进栈、访问 /、d进栈、访问c、d出栈并访问之、*出栈并访问之、f进栈、访问e、f出栈并访问之。 具体C程序算法如下: #include #define M 100 typedef struct node { int data; struct node *lc; struct node *rc; }JD; void preordef(JD *tree) { int i=0; JD *p,*s[M]; p=tree; do { while(p!=NULL) { printf(“%d\t”,p->data); if(p->rc!=NULL) s[i++]=p->rc; p=p->lc; } if(i>0) p=s[--i]; }while(i>=0); } 注意,这里的数组s[M]是结构指针类型的数组,每个数组元素都可以存放一个结点的地 址(即指向该结点)。 (4学时) 掌握图的基本存储方法,掌握有关图的操作算法并用高级语言编程实现,建立源程序, 调试运行,分析结果。。 18 1.图的邻接矩阵实现 为了存储图的邻接矩阵,我们定义了一个整型的二维数组mat[M][M],并把它定义为全局变量。 函数adjmatrix(n,code)用于建立有向图(或无向图)的邻接矩阵。其中参数n和code都是整数,n是顶点数,code是图的类型代码,code为1时表示有向图,code为2时表示无向图。函数初始时我们将数组中所有元素都赋值为一个最大整数INFIN,表示不连通,然后,依次输入每条边的顶点u和 v及其权值w(对于不带权值的图,W的值为1),若图是无向图,则矩阵元素mat[u][v]=w的同时置mat[v][u]=w,输入过程直到出现u=0,u>n,v=0或v>n时结束。 函数prmatrix()用于打印矩阵,其格式与数学中常用格式相同,并且加上行号和列号。 #define M 40 #define INFIN 9999 int mat[M][M]; void adjmatrix(int n,int code) { int i,j,u,v,w; for(i=1;i<=n;i++)>=n;i++)> for(j=1;j<=n;j++)>=n;j++)> mat[i][j]=INFIN; do { printf(“u,v,w = ”); scanf(“%d,%d,%d ”,&u,&v,&w); if(code==1) mat[u][v]=w; else { mat[u][v]=w; mat[u][v]=w; } }while( u>0 && u } void prmatrix(int n) { int i,j; for(i=0;i<=n;i++)>=n;i++)> printf(“%d\t”,i); 19 printf(“\n”); for(i=1;i<=n;i++)>=n;i++)> { printf(“%d\t”,i); for(j=1;j<=n;j++)>=n;j++)> printf(“%d\t”,mat[i][j]); printf(“\n”); } } main() { int v,n,code; printf(“Enter the node_number of graph:\n”); scanf(“%d”,&n); printf(“\nEnter the code of the_graph:digraph:1 undigraph:2”); scanf(“%d”,&code); if(code<1||code>2) exit(1); else { adjmatrix(n,code); prmatrix(n); } } 2.图的邻接表实现 为了用邻接表存储图,邻接表中的头结点和表结点分别可以用如下结构来表示: struct lnode /*表结点定义*/ { int adjvex; /*邻接点编号域*/ int info; /*邻接点数据域*/ struct lnode *nextarc; /*指向顶点下一结点的指针*/ } struct hnode /*头结点定义*/ { int vexdata; /*顶点数据域*/ struct lnode *firstarc; /*顶点指向的第一个结点的指针*/ } 为今后使用方便,下面定义: 20 typedef struct hnode HNode; typedef struct lnode HNode; 下面的函数adjlist(n)用于建立一个图的邻接表,n是图中的顶点个数。在建立邻接表 时,用结构数组HNode mat[M]存放图中的M个顶点的相关信息,并把它定义成全局变量,函 数pradjlist用于打印邻接表的内容,打印结果给出了每一条链上的各边的顶点偶对。程序 如下: #define M 50 #include HNode mat[M]; void adjlist(int n) { LNode *p; int i,k,u,v,w; for(i=1;i<=n;i++)>=n;i++)> { mat[i].vexdata=i; mat[i].firstarc=NULL; } do { printf(“u,v,w= ”); scanf(“%d,%d,%d ”,&u,&v,&w); p=(LNode *)malloc(sizeof(LNode)); if(p==NULL) exit(1); else { p->adjvex=v; p->info=w; p->nextarc=mat[u].firstarc; mat[u].firstarc=p; } }while(u>0 && u<=n &&="" v="">0 && v<=n);>=n);> } void pradjlist(int n) { LNode *p; int i; printf(“Adjacency list of the graph:\n”); 21 printf(“Pair nodes\n”); for(i=1;i<=n;i++)>=n;i++)> { p=mat[i].firstarc; while(p!=NULL) { printf(“<%d,%d>”,i,p->adjvex); p=p->nextarc; } printf(“\n”); } } main() { int n; printf(“Enter the node_number of graph:\n”); scanf(“%d”,&n) adjlist(n); pradjlist(n); } 3.最小生成树PRIM算法的实现 构造生成树可以有多种算法,其中多数算法(包括Prim算法)利用了最小生成树的一种性质:假设N=(V,E)是一个连通图,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u?U,v?V-U,则必定存在一棵包含边(u,v)的最小生成树。 ? Prim算法 假定N=(V,E)是一个连通图,TE是N上最小生成树边的集合。算法从U={u }(u?V),TE=?00 开始,重复执行下列操作:在所有u?U,v?V-U的边(u,v)?E中找出一条权值最小的边(u,v)00 并入集合TE,同时v并入U,直到U=V为止。此时TE中必有n-1条边,则T=(V,TE)为N的0 最小生成树。 上述思想换种方式而言,即从图中任意一个顶点开始,首先把该顶点的包括在生成树中, 然后在那些其一个顶点已包括在生成树中,另一个顶点还未包括在生成树里的所有边中找权 值最小的边,并把这条边和其不在生成树中的那个顶点包括进生成树里。如此进行下去,直 到把所有顶点都包括进生成树里。 Prim算法的C程序实现,在实现算法中,使用了一个整型二维数组a[M][3]来表示在构造最小生成树时U、V-U、W的变化。其具体变化如下图所示: 22 ? C程序代码 #define M 50 #define INFIN 9999 int mat[M][M]; void prim(int n) { int a[M][3]; int i,j,k,min; for(i=1;i<=n;i++)>=n;i++)> { a[i][0]=1; if(i==1) a[i][1]=0; else a[i][1]=i; a[i][2]=mat[1][i]; } printf(“\nU\tV-U\tCost\n”); for(j=1;j<=n;j++)>=n;j++)> printf(“%d\t%d\t%d\n”,a[j][0],a[j][1],a[j][2]); getch(); for(i=1;i<=n-1;i++)>=n-1;i++)> { min=INFIN; k=0; for(j=1;j<=n;j++)>=n;j++)> { 23 if(a[j][2]) { min=a[j][2]; k=j; } } printf(“(%d,%d)\t”,a[k][0],a[k][1]); a[k][0]=k; a[k][1]=0; a[k][2]=INFIN; for(j=1;j<=n;j++)>=n;j++)> { if(mat[k][j] { a[j][0]=k; a[j][2]=mat[k][j]; } } printf(“\nU\tU-V\tCost\n”); for(j=1;j<=n;j++)>=n;j++)> printf(“%d\t%d\t%d\n”,a[j][0],a[j][1],a[j][2]); getch(); } } main() { int n,code=2; int i,j; printf(“Enter the node_number of graph:\n”); scanf(“%d”,&n); adjmatrix(n,code); printf(“Matrix of the undirected graph:\n”); prmatrix(n); printf(“Edges of minicost spanning tree:\n”); prim(n); getch(); } (2学时) 24 掌握数据结构中查找的基本算法思想,并能进行应用。建立源程序,调试运行,分析结 果。 1.折半查找的实现 折半查找(Binary Search)的查找过程是:先确定待查记录所在的范围(区间),然后 逐步缩小该范围直到找到或找不到该记录为止。 例如:已知如下有13个数据元素的有序表(关键字即为数据元素的值)。现要查找关键 字为12的数据元素:(1,3,11,12,25,33,35,40,57,77,89,90,91)。假设指针low和high分别指向待查元素所在范围的下界和上界,指针mid指示区间的中间位置,即mid=[(low+high)/2]。在此例中,初始的low=1,high=13,mid=7。 下面给出给定值key=12的查找过程: 1 3 11 12 25 33 35 40 57 77 89 90 91 ? ? ? low=1 mid=7 high=13 1 3 11 12 25 33 35 40 57 77 89 90 91 ? ? ? low=1 mid=3 high=6 1 3 11 12 25 33 35 40 57 77 89 90 91 ? ? ? low=4 mid=5 high=6 1 3 11 12 25 33 35 40 57 77 89 90 91 ? ? ? low=mid=high=4 当查找的是13时,下一步low=mid+1=5>high,也就是说,当low>=high时,不管ST.elem[mid].key与key是否相等,都应该退出了。 在上述查找的过程中, if(ST.elem[mid].key>key) { 25 high=mid-1; mid=(low+high)/2; } if(ST.elem[mid].key low=mid+1; mid=(low+high)/2 } 下面是折半查找法的一个完整程序。 #define M 50 #include #include main() { int i,length; int low,high,mid; int key,s; int st[M]; clrscr(); printf("Please input SSTable length:\n"); scanf("%d",&length); printf("Please input SSTable data:\n"); for(i=1;i<=length;i++)>=length;i++)> { printf("%d:\t",i); scanf("%d",&st[i]); } while(1) { s=0; printf("Please input Search Key:\n"); scanf("%d",&key); if(key==-1) exit(0); low=1; high=length; while(low<=high)>=high)> { mid=(low+high)/2; if(key 26 high=mid-1; if(key>st[mid]) low=mid+1; if(st[mid]==key) { s=mid; break; } } if(s==0) printf("%d is no\n",key); else printf("%d is st[%d]\n",key,s); } getch(); } (2学时) 掌握排序的各种算法思想,并能通过其解决应用问题。建立源程序,调试运行,分析结 果。 1.直接插入排序 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,它的基本操作是 将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。 请看序列:49,38,65,97,76,13,27,49其直接插入排序的变化状况如下: (49),38,65,97,76,13,27,49 (38,49),65,97,76,13,27,49 (38,49,65),97,76,13,27,49 (38,49,65,97),76,13,27,49 (38,49,65,76,97),13,27,49 (13,38,49,65,76,97),27,49 (13,27,38,49,65,76,97),49 27 (13,27,38,49,49,65,76,97) 这就是SIS的工作原理。在具体实现上,利用了一个称之为哨兵的技巧。其实现算法的 类C语言描述如下: void InsertSort(Sqlist &L) { for(i=2;i<=l.length;++i)>=l.length;++i)> if LT(L.r[i].key,L.r[i-1].key) { L.r[0]=L.r[i]; for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0] } } 标准C程序代码如下: #define MAX 100 int a[MAX]; void insert(int n) { int i,j; for(i=2;i<=n;i++)>=n;i++)> { a[0]=a[i]; j=i-1; while(a[0] { a[j+1]=a[j]; j--; } a[j+1]=a[0]; } } 直接插入排序的空间占用并不大,但时间复杂度为 2O(n)。 2.折半插入排序(二分法) 由于插入排序的基本操作是在一个序表中进行查找和插入,由前面的学习可知,这个“查 找”可以利用“折半查找”来实现,由此进行的插入排序称之为折半插入排序(Binary Insertion Sort)。 方法如下:在插入R时(这时R,R,...,R已排序),取R的关键字K与K进i12i-1[i/2][i/2]i 28 行比较,小于则在前半部继续上述方法,否则在后半部继续上述方法。直到插入所有结点为 止。 C程序如下: #define MAX 100 int a[MAX]; void half_insert(int n) { int i,j,temp; int d,r,m; for(i=2;i<=n;i++)>=n;i++)> { d=1; r=i-1; temp=a[i]; while(d<=r)>=r)> { m=(d+r)/2; if(temp r=m-1; else d=m+1; } for(j=i-1;j>=d;j--) a[j+1]=a[j]; a[d]=temp; } } 3.起泡排序 起泡排序(Bubble)是快速排序中较简单的一种。起泡排序的过程很简单,其思路是将 相邻两个数比较,将小的调到前面,大的调到后面(即交换)。 设有数据序列(9,8,5,6,2,0), 则起泡排序的过程如下所示: 0 0 0 0 0 9 9 9 9 9 9 9 9 9 9 9 2 2 2 2 9 0 0 0 0 8 8 8 8 8 8 8 6 6 6 9 2 2 2 2 8 0 0 0 6 6 6 6 5 5 9 6 6 6 6 8 2 2 2 6 0 0 5 5 8 9 5 5 5 5 8 6 6 6 6 2 2 5 0 2 9 8 8 8 8 8 5 5 5 5 5 5 5 2 2 0 29 C程序如下: #define M 50 int a[M]; void bubble(int n) { int i,j,t; for(j=1;j<=n-1;j++)>=n-1;j++)> for(i=1;i<=n-j;i++)>=n-j;i++)> if(a[i>a[i+1]) { t==a[i]; a[i]=a[i+1]; a[i+1]=t; } } 4.快速排序 快速排序(Quick Sort)是对起泡排序的一种改进。 ? 基本思想 在待排的n记录R ,R,...,R中,任取一个记录(一般可取第一个记录R),以该记12n1 录(亦称为支点记录)的关键字的值作为标准,通过一趟排序将待排记录分割成两组,其中 一部分的关键字均比另一部分记录的关键字小,则可分别对两部分记录继续进行排序,以达 到整个序列有序。 具体的操作见下面的过程(一趟快速排序的比较示例): 55 13 42 94 05 17 70 17 55 13 42 94 05 70 17 13 42 94 05 55 70 17 05 13 42 94 55 70 17 05 13 42 94 55 70 17 05 13 42 94 55 70 17 05 13 42 94 55 70 30 ? C语言实现 我们用函数quicksort(d,s)实现快速排序,其中参数d和s分别是待排序列的起始元素 的下标和结束元素的下标。待排序的数据放在数组a中,我们把a设成全局变量。在实现函 数时,设两个i和j,分别取d和s的值,并选基准元素pivot为a[i]。算法如下: a.如果i 如果a[i]<=a[j],则:若a[i]=pivot,则j--;若a[j]=pivot,则i++。>=a[j],则:若a[i]=pivot,则j--;若a[j]=pivot,则i++。> 否则,t=a[i],然后交换a[i]和a[j]的值。交换后:若t=pivot,则i++;否则j--。 b.如果d #define MAX 50 int a[MAX]; void quicksort(int d,int s) { int i,j,t,pivot; i=d; j=s; pivot=a[i]; while(i { if(a[i]<=a[j])>=a[j])> { if(a[i]==pivot) j--; else i++; } else { t=a[i]; a[i]=a[j]; a[j]=t; if(t==pivot) i++; else j--; } } if(d 31 quicksort(d,i-1); if(i+1 quicksort(i+1,s); } main() { int i,n; printf(“Enter the number of array:\n”); scanf(“%d”,&n); printf(“Enter %d data:”,n); for(i=1;i<=n;i++)>=n;i++)> { printf(“a[%d]=”i); scanf(“%d”,&a[i]); } quicksort(1,n); printf(“The sorted data:\n”); for(i=1;i<=n;i++)>=n;i++)> printf(“%d-5d”,a[i]); } 可以证明,快速排序的总的比较次数约为nlog n。 2 5.直接选择排序 设整型数组a[MAX]存放待排序的n个数据(a[0]不存放数据),并把数据a[MAX]定义为 全局变量,我们用函数getdata(n)来实现待排序数据的输入,函数putdata(n)用于输出数据, 函数swap来实现两个数据的交换,函数select(n)实现排序,参数n是待比较元素的个数。 #define MAX 100 int a[MAX]; void getdata(int n) { int i; for(i=1;i<=n;i++)>=n;i++)> { printf(“a[%d]=”,i); scanf(“%d”,&a[i]); } } 32 void putdata(int n) { int i; for(i=1;i<=n;i++)>=n;i++)> printf(“a[%d]=%d\t”,i,a[i]); } void swap(int *x,int *y) { int t; t=*x; *x=*y; *y=t; } void select(int n) { int i,k,j; for(i=1;i { k=i; for(j=i+1;j<=n;j++)>=n;j++)> if(a[k]>a[j]) k=j if(i!=k) swap(&a[i],&a[k]); } } main() { int n; printf(“Enter the number of array:\n”); scanf(“%d”,&n); getdata(n); printf(“\nBefore sorted array:\n”); putdata(n); select(n); printf(“Sorted array:”); putdata(n); } 33 (18学时) 学生必须仔细阅读《数据结构》课程设计方案,认真主动完成课设的要求。有问题及时 主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力,充分利用时间,安排好课 设的时间计划,并在课设过程中不断检测自己的计划完成情况,及时的向教师汇报。课程设 计按照教学要求需要在四周时间完成。 本次课程设计完成如下模块(共13个模块,学生可以在其中至少挑选6个功能块完成) 1、 运动会分数统计 任务:参加运动会有n个学校,学校编号为1??n。比赛分成m个男子项目,和w个女 子项目。项目编号为男子1??m,女子m+1??m+w。不同的项目取前五名或前三名积分;取 前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m<><=20)>=20)> 功能要求:1).可以输入各个项目的前三名或前五名的成绩; 2).能统计各学校总分, 3).可以按学校编号、学校总分、男女团体总分排序输出; 4).可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的 学校。 规定:输入数据形式和范围:20以内的整数(如果做得更好可以输入学校的名称,运动 项目的名称) 输出形式:有中文提示,各学校分数为整形 界面要求:有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要 求。 存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在 数据文件中。(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构; 测试数据:要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明; 2、 一元多项式计算 任务:能够按照指数降序排列建立并输出多项式; 能够完成两个多项式的相加、相减,并将结果输入; 在上交资料中请写明:存储结构、多项式相加的基本过程的算法(可以使用程序流程图) 、 34 源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 3、 订票系统 任务:通过此系统可以实现如下功能: 录入: 可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定) 查询: 可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价, 票价折扣,确定航班是否满仓); 可以输入起飞抵达城市,查询飞机航班情况; 订票:(订票情况可以存在一个数据文件中,结构自己设定) 可以订票,如果该航班已经无票,可以提供相关可选择航班; 退票: 可退票,退票后修改相关数据文件; 客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。 修改航班信息: 当航班信息改变可以修改航班数据文件 要求: 根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能; 4、 迷宫求解 任务:可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径, 并将路径输出; 要求: 在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、源程序、测试数 据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 5、 文章编辑 功能:输入一页文字,程序可以统计出文字、数字、空格的个数。 静态存储一页文章,每行最多不超过80个字符,共N行;要求(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该 次数;(3)删除某一子串,并将后面的字符前移。 存储结构使用线性表,分别用几个子函数实现相应的功能; 输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"(3)输出删除某一字符串后的文章; 6、 Joseph环 任务:编号是1,2,??,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正 整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的 35 下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出 列顺序。 要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。 测试数据: m的初值为20,n=7 ,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么? 要求: 输入数据:建立输入处理输入数据,输入m的初值,n ,输入每个人的密码,建立单循环链 表。 输出形式:建立一个输出函数,将正确的输出序列 7、 猴子选大王 任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只 剩下最后一只猴子,则该猴子为大王。 要求: 输入数据:输入m,n m,n 为整数,n 输出形式:中文提示按照m个猴子,数n 个数的方法,输出为大王的猴子是几号 ,建立一个函数来实现此功能 8、 建立二叉树,层序、先序遍历( 用递归或非递归的方法都可以) 任务:要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立 建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数; 9、 赫夫曼树的建立 任务 :建立建立最优二叉树函数 要求:可以建立函数输入二叉树,并输出其赫夫曼树 在上交资料中请写明:存储结构、 基本算法(可以使用程序流程图) 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 10、 纸牌游戏 任务:编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后?从第4张开始,以4为基数,是4的倍数的牌翻一次, 直到最后一张牌;...再依次5的倍数的牌翻一次,6的,7的 直到 以52为基数的 翻过,输出:这时正面向上的 牌有哪些? 11、图的建立及输出 任务:建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可 以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图 36 的邻接矩阵。 12、拓扑排序 任务:编写函数实现图的拓扑排序。 13、 各种排序 任务:用程序实现插入法排序、起泡法改进算法排序; 利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。 输入的数据形式为任何一个正整数,大小不限。 输出的形式:数字大小逐个递增的数列? 上交的成果的内容必须由以下四个部分组成,缺一不可 1. 上交源程序:学生按照课程设计的具体要求所开发的所有源程序(应该放到一个文 件夹中); 2. 上交程序的说明文件:(保存在.txt中)在说明文档中应该写明上交程序所在的目 录,上交程序的主程序文件名,如果需要安装,要有程序的安装使用说明; 3. 课程设计报告:(保存在word 文档中,文件名要求 按照"姓名-学号-课程设计报告"起名,如文件名为"张三-001-课程设计报告".doc )按照课程设计的具体要求建立的功能 模块,每个模块要求按照如下几个内容认真完成。其中包括: a. 需求分析:在该部分中叙述,每个模块的功能要求 b. 概要设计:在此说明每个部分的算法设计说明(可以是描述算法的流程图),每个程 序中使用的存储结构设计说明,如果指定存储结构请写出该存储结构的定义。 c.详细设计:各个算法实现的源程序,对每个题目要有相应的源程序(可以是一组源程 序,每个功能模块采用不同的函数实现)源程序要按照写程序的规则来编写。要结构清晰, 重点函数的重点变量,重点功能部分要加上清晰的程序注释。 d. 调试分析 测试数据,测试输出的结果,时间复杂度分析,和每个模块设计和调试时存在问题的思 考(问题是哪些?问题如何解决?),算法的改进设想。 4. 课设总结: (保存在word 文档中)总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、 在课程设计过程中对《数据结构》课程的认识等内容 37 1.实验报告 要求每个实验在实验过程和实验结束时填写实验报告。实验报告要求填写实 验名称、实验日期、实验组号、同组人、实验目的和要求、实验平台(软硬件)、 实验设计方案、实验步骤、实验和数据、实验结果及分析。 2.考核方式 本实验的考核方式由任课老师依据以下原则进行。 ? 可将实验报告列入本课程期末考核成绩比例,比例在20%以内酌情掌握。 ? 可在期末考核时单独进行实验考核,其成绩作为本课程期末考核成绩比 例,比例在50%以内酌情掌握。 38范文五:数据结构课程