2010数据结构
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（）
A．问题规模
B．语句条数
C．循环层数
D．函数数量
2．具有线性结构的数据结构是（）
A．树
B．图
C．栈和队列
D．广义表
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（）
A．O(1)
B．O(m)
C．O(n)
D．O(m+n)
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（）
A．2个
B．3个．
C．4个
D．6个
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（）
A．3
B．37
C．50
D．97
6．若栈采用链式存储结构，则下列说法中正确的是（）
A．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空
7．若串str=”Soft ware”，其子串的数目是（）
A．8
B．9
C．36
D．37
8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，a ll为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（）A．1012
C．1032
D．1039
9．允许结点共享的广义表称为（）
A．纯表
B．线性表
C．递归表
D．再入表
10．下列数据结构中，不属于二叉树的是（）
A．B树
B．AVL树
C．二叉排序树
D．哈夫曼树
11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（）
A．1，5，2，6，3，4
B．1，5，6，2，3，4
C．5，1，6，3，4，2
D．5，1，2，6，4，3
12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（）
A．v1，v2，v3，v4，v5，v6，v7
B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5，v6
D．v1，v2，v5，v6，v7，v3，v4
13．下列排序算法中不稳定的是（）
A．快速排序
B．归并排序
D．直接插入排序
14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（）A．2
B．3
C．4
D．8
15．采用ISAM组织文件的方式属于（）
A．链组织
B．顺序组织
C．散列组织
D．索引组织
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16．数据元素及其关系在计算机存储器内的表示称为_________。
17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。
18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。
typedef struct{
DataType data[100]；
int top；
}SeqStack；
DataType f18(SeqSta ck*S)
{ if(St ackEmpty(S))
Error(”St ack is empty”)；
return S->data[S->top]；
}
19．在串匹配中，一般将主串称为目标串，将子串称为_________。
20．已知广义表C=(a(b，c)，d)，则：tail(he ad(tail(C)))= _________。
21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_________。
22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。
23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。
24．高度为3的3阶B-树最少的关键字总数是_________。
25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。
三、解答题(本大题共4小题，每小题5分，共20分)
26．假设二叉树的RNL遍历算法定义如下：
若二叉树非空，则依次执行如下操作：
(1)遍历右子树；
(2)访问根节点；
(3)遍历左子树。
已知一棵二叉树如图所示，请给出其RN L遍历的结果序列。
27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。
请回答下列问题：
(1)请画出对应的图G。
(2)画出图G的邻接表存储结构。
28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。29．已知一棵二叉排序树如图所示。
请回答下列问题：
(1)画出插入元素23后的树结构；
(2)请画出在原图中删除元素57后的树结构。
四、算法阅读题(本大题共4小题，每小题5分，共20分)
30．已知下列程序，Ls指向带头结点的单链表。
Typedefstruct node {
DataType data;
struct node * next;
} * LinkList;
void f30( LinkList Ls )
{ LinkList p, q;
q = Ls->next;
Ls->next = q->next;
p=q
while ( p->next )
p = p->next;
p->next = q;
q->next = NULL;
}
}
请回答下列问题：
(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。
(2)请简述算法的功能。
31．已知字符串处理函数f31程序如下。
int f31(char*strl，char*str2)
{ while(*strl==*str2&&(*strl!=’＼0’)){
strl++；
str2++；
}
return(*strl-*str2 ? l∶0)；
}
请回答下列问题：
(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么?
(2)简述该函数的功能。
32．数组A[]中存储有n个整数，请阅读下列程序。
void f32(intA[]，int n)
{ inti，j，k，x；
k=n-l；
while(k>0){
i=k；k=0；
for(j=O；j if(A[j]>A[j+1]){ x=A[j]； A[j]=A[j+l]； A[j+1]=x； k=j； }／／end of if }／／end of while return； } 请回答下列问题： (1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? (2)说明该算法的功能。 33．下面程序实现二分查找算法。 KeyType key； InfoType otherinfo； }SeqList[N+1]； int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) ){ mid=(1ow+high)／2； if( (2) ) return mid； if(R[mid]．key>K) high=mid-1； else (3) ； } return O； } ／／BinSea rch 请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3) 五、算法设计题(本题10分) 34．已知二叉树采用二叉链表存储，其结点结构定义如下：typedef struct Node{ ElmType data； struct Node *lchild，*rchild； }*BiTre e； 请编写递归函数Su mNodes(BiTree T)，返回二叉树T的结点总数。 《数据结构与算法设计》实验大纲及实验内 容详细要求 一、课程编号： 二、课程类型：必修 适用专业：通信工程 实验学时：32学时 三、本课程的地位、作用与任务 数据结构课程的目标是使学生掌握数据的基本的逻辑结构和存储结构、一些典型的数据结构算法及程序设计方法，要求学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，要求具备算法分析的基本技术和能力，并培养良好的程序设计风格，掌握开发复杂、高效程序的技能。 在实验前要预习或者自行补充部分学时，同时进行部分代码准备，实验后要认真完成实验报告。 四、课程基本要求 1.学生应根据每个实验的任务和教师所提的要求，带C语言教材和课程教材。 2.完成指定的实验任务，保存源代码并输出、记录实验结果。 3.实验结束后按时提交实验报告，对于未完成部分，应该利用课余时间补充完成。 五、实验安排 本实验课程共32学时，五个实验(单元)，分16次实验，每次2学时。 实验一：C程序编程、调试实验 1、实验学时：4学时（学生堂下自行加4学时） 2、实验目的： 1)巩固复习前期所学C语言的基本数据类型和自定义数据类型等知识点，强化 学习数据结构语言和编程基础。 2)巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学 习数据结构语言基础。 3)能够较熟练调试程序 3、实验内容： 1)学生信息的显示。具体要求如下： ●定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)； ●设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构 体类型； ●设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数 进行显示（学生人数不少于5人）。 2)输入若干个整数存储到数组元素值，然后按输入顺序进行逆置存储，最后打 印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：1023045，逆置后显示为：5430210。 3)编写扑克牌发牌程序。在VC++的调试环境下观察数据存储位置、存储数据的 变化、数据之间的逻辑次序、物理存储位置次序。 4)对上述C程序进行调试，运行，从中理解数据和算法的概念，总结调试方法。 实验二：线性表的存储及基本操作、综合应用 1、实验学时：6学时 2、实验目的： 1)掌握线性表的逻辑特征 2)熟练掌握线性表的链式存储结构定义及基本操作 3)理解循环链表和双链表的特点和基本运算 4)加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实 际问题的编程能力。 5)掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理 结构 6)和实验一一起撰写一份实验报告，总结学习效果 3、实验内容： 使用顺序表和链表两种存储结构（linked list），存储输入的一组数据整数，能够进 数据结构实验报告 实验：图的遍历 一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列 三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。 四、程序实现及结果： 1、邻接矩阵： #include . 数据结构实验报告 图 一、实验目的 1、熟悉图的结构和相关算法。 二、实验内容及要求 1、编写创建图的算法。 2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。 三、算法描述 1、图的邻接表存储表示： 对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。 存储表示如下： typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 // InfoType *info; // 该弧相关信息的指针 } ArcNode; typedef struct VNode { char data; // 顶点信息 int data2; int sngle; ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph; 2、深度优先搜索： 假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。 2、广度优先搜索： 假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。若图中仍有未被访问的顶点，选择另一个未被访问的顶点开始，重复上述操作，直到图中所有顶点都被访问。为了使“先 禁止抄袭，否则一律不及格。机会仅有一次！！！！！ 《数据结构课程设计》 一、基本要求 （1）选择一个与线性表、堆栈和队列、数组、树、图、排序、查找等相关的专题，利用C语言或java来实现，解决具有一定规模的、具有实际意义的应用题目。 （2）论文内容主要包括封面、正文、参考文献等，其中正文内容主要引言、系统分析设计、系统实现和小结几部分组成。 （3）论文格式参考下面文档《模板》撰写课程报告。 （4）特别要求自己独立完成。 （5）第15周周一提交课程设计论文、电子版、源代码。 二、创新要求 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。 可选题目列表： 1.运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构实验课程大纲 本大纲是针对计算机科学与技术专业本科对数据结构的基本要求而编写的。 一、目的与任务 数据结构是一门实践性很强的课程，每个学生必须完成一定数量的上机作业。通过上机作业，要求在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。 二、课程内容 1.顺序表的表示和运算（0-2学时） 2.链表的表示和运算（2学时） 3.栈的应用（2-3学时） 4.队列的应用（2-3学时） 5.二叉树的基本操作和应用（2-6学时） 6.图及其应用（2-6学时） 7.排序（4-6学时） 8.查找（2-4学时） 三、基本要求 1.逐步理解和掌握程序设计和上机操作的基本方法和技能。 2.理解并实现各种基本数据结构的存贮表示、运算方法及其典型应用；学会根据实际问题的要求设计算法的 数据结构，并具有一定的比较和选用数据结构及算法的能力。 3.理解并实现常用的查找和排序的基本方法。 四、学时分配 五、实验内容 注：带*的内容以及练习与思考题，可根据实际学时、专业方向特点等具体要求，做相应调整或从略。 实验一、顺序表 实验目的： 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求： 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设数据元素为整数，实现这样的线性表的顺序存储表示。 (2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。 (3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。 (4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。要求尽可能少地修改前面的程序来得到新程序。（这里用于比较的字段为分数） 练习及思考题： （1）不同类型的数据元素所对应的顺序表在类型定义和操作实现上有什么异同？ （2）顺序表的操作上有什么特点？ （3）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。 实验二、链表 实验目的： 熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求： 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。 (2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。 (3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。（用于比较的关键字字段为分数）。 (4) 输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 (5) * 释放该链表（删除所有结点）。 (6) * 若要求建立的学生成绩单链表为有序表，重新编写算法和程序实现前面的要求（3）。（用于比较的字段为分数）。 练习及思考题： （1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？ （2）有头结点的链式表，有什么特点？ 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四） 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构实验报告 顺序表实验 1.实验目标 a.熟练掌握线性表的顺序存储结构。 b.熟练掌握顺序表的有关算法设计。 c.根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。 2.实验内容和要求 a.顺序表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现； b.实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； c.程序有适当的注释。 3.数据结构设计 顺序表 4.算法设计 1.i表示要在顺序表中查找的位置，x表示查找到后返回的值。 int search(seqlist A,int i,elementType &x) { if(i<1||i>A.Len)//查找的范围不在顺序表中 return 0; else { x=A.data[i-1];//复制要查找的值 return 1; } } 2.i表示要在顺序表中插入的位置，x表示要插入的元素。 void insert(seqlist &A,int i,elementType x) { if(i<1||i>A.Len)//超出顺序表范围 cout<<"error"< } 3.先利用循环找到顺序表中第i个结点，然后进行删除操作。 void del(seqlist *L,int i) { int j; if(i<1||i>L->Len+1)//超顺序表范围 cout<<"超出表范围"< 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下： （1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 （1）进一步掌握指针变量的用途和程序设计方法。 （2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。 （3）掌握构造二叉树的基本方法。 （4）掌握二叉树遍历算法的设计方法。 3．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）掌握一个实际二叉树的创建方法。 （3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4．实验内容 （1）定义二叉链存储结构。《数据结构与算法设计》实验大纲及实验内容详细要求
数据结构实验报告-图的遍历
数据结构实验报告--图
《数据结构设计》内容要求要点
数据结构图的遍历实验报告
第三章栈和队列习题_数据结构电子教案
数据结构课程设计题目及要求
数据结构实验 - 图的储存与遍历
数据结构实验报告图实验
(完整版)数据结构详细教案——图
数据结构实验报告图实验
《数据结构》实验指导书
《数据结构实验》实验题目及实验报告模板
《数据结构与算法》上机实验要求
数据结构实验报告图实验
数据结构实验报告模板
数据结构实验报告全集