吉林大学数据结构_关键路径共34页

计算机考研专业课大纲——专业学位第一部分概述一、考查目标计算机学科专业综合考试包括《数据结构》和《高级语言程序设计》学科专业基础课程。

要求考生比较系统地掌握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知识判断和解决相关的理论问题和实际问题。

二、考试形式和试卷结构试卷满分及考试时间本试卷满分为150分，考试时间为180分钟答题方式：闭卷、笔试三、试卷内容结构数据结构75分高级语言程序设计75分四、试卷题型结构第二部分《数据结构》第三部分《高级语言程序设计》第二部分《数据结构》考查目标1. 熟悉数据结构的相关概念及其分类，数据结构与算法的关系。

掌握线性表、堆栈和队列，数组和字符串等数据结构的存储、操作和应用，树与二叉树的性质与应用算法，图的存储结构和相关算法，排序与查找的典型算法。

2. 掌握算法时空复杂性分析和正确性验证的基本方法。

3．能够综合运用数据结构、算法、数学等多种知识，对问题进行分析、建模，选择或构建合适的数据结构，设计较优算法。

题型结构：包括问答题与算法设计题具体内容：一、绪论（1）数据、数据元素、数据逻辑结构和存储结构的定义及其关系；（2）数据逻辑结构及其分类；（3）算法的定义和特征；（4）算法的正确性证明方法；（5）算法的时间和空间复杂性分析方法及复杂性函数的渐进表示。

二、线性表、堆栈和队列（1）线性结构的概念和特点；（2）顺序存储和链式存储线性表的基本操作；（3）堆栈的定义和两种存储结构下堆栈的基本操作；（4）堆栈在括号匹配和递归中的应用；（5）队列的定义和两种存储结构下队列的基本操作；（6）队列的应用。

三、数组和字符串（1）二维及多维数组的存储原理及寻址方式；（2）矩阵的存储及基本操作；（3）三元组表和十字链表存储的稀疏矩阵的基本操作；（4）字符串的存储及基本操作；（5）模式匹配算法。

四、树与二叉树（1）树的概念、相关术语和表示方法；（2）二叉树的定义和性质；（3）二叉树的顺序存储结构和链接存储结构；（4）二叉树遍历的递归与非递归算法；（5）线索二叉树的定义和操作；（6）树与二叉树的转换；（7）树的链接存储结构，树和森林的遍历算法；（8）树的顺序存储结构；（9）树在并查集实现中的应用。

关键路径若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续时间），则此带权的有向图称为边表示活动的网(Activity on Edge Network) ，简称AOE 网。

【例】图7.21 是一个网。

其中有9 个事件v 1 , v 2 , … , v 9 ；11 项活动 a 1 , a 2 , … , a 11 。

每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。

如v 1 表示整个工程开始，v 9 表示整个工程结束。

V 5 表示活动a 4 和a 5 已经完成，活动a 7 和a 8 可以开始。

与每个活动相联系的权表示完成该活动所需的时间。

如活动 a 1 需要 6 天时间可以完成。

(1)AOV 网具有的性质⒈只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

⒉只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。

⒊表示实际工程计划的AOE 网应该是无环的，并且存在唯一的入度过为0 的开始顶点和唯一的出度为0 的完成顶点。

(2)由事件v j 的最早发生时间和最晚发生时间的定义, 可以采取如下步骤求得关键活动:1. 从开始顶点v 1 出发, 令ve(1)=0, 按拓扑有序序列求其余各顶点的可能最早发生时间。

Ve(k)=max{ve(j)+dut(<j,k>)} （7.1 ）j ∈T其中T 是以顶点v k 为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n ，则说明网中有环，不能求出关键路径，算法结束。

2. 从完成顶点v n 出发，令vl(n)=ve(n) ，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-dut(<j,k>)}k ∈S其中S 是以顶点v j 是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。

数据结构单选题：1．线性链表中各结点之间的地址（）。

4.连续与否无所谓2 线性表是具有n个( )的有限序列。

3.数据元素3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。

（1?i ?n+1）3.O(n)4.不带头结点的单链表head为空的判断条件是( )。

1.head==NULL5.线性表的长度是指（）3.表中的元素个数6.某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（）。

3.2167.链栈和顺序栈相比，有一个较明显的优点是( )。

1.通常不会出现栈满的情况8 带头结点的单链表head为空的判断条件是( )。

2.head->next==NULL9 在单链表中增加头结点的目的是为了( )。

1.方便运算的实现11 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省空间。

3.带头结点的双循环链表12.单链表的存储密度（）。

3.小于113 非空的循环单链表head的尾结点（由p指针所指）满足( )。

3.p->next==head14 在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s) 结点,则执行( )。

3.q->next=s ; s->next=p ;15 在一个单链表中，若删除(*p)结点的后继结点，则执行( )。

1.p->next=p->next->next ;16 设输入序列为的1,2,3,4,借助一个栈可以得到的输出序列是( )。

1.1,3,4,217．以下叙述正确的是( )。

3.顺序存储的线性表可以随机存取18.设输入序列为的A,B,C,D,借助一个栈不可以得到的输出序列是( )。

4.D,A,B,C19 栈和队列都是（）3.限制存取点的线性结构20．设输入序列为1,2,3,4,5，借助一个栈可以得到的输出序列是( )。

数据结构课程设计报告---关键路径数 据 结 构课 程 设 计报 告院系： 信息管理学院 专业： 软件工程班级： 软件Q1141学号： 11150038姓名： 李艳平 教师： 邓沌华时间： 2013.4.2理论成绩 实践成绩 总成绩目录一、问题的描述二、系统需求及分析1、简要介绍2、需求分析3、概要设计4、详细设计(1)数据结构(2)创建有向图的邻接表(3)计算各事件及活动的相关信息(4)输出有向图的相关信息(5)判断图中是否有回路(6)计算并输出关键活动(7)计算并输出关键路径(8)操作入口三、系统实现四、设计总结五、附件（完整源代码）一、问题的描述：关键路径问题（起评分：85）1、功能：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

2、数据：自行设计每个活动的前导活动和后续活动以及活动的进行时间，然后依据这些活动的前后次序，画出其网络图，选择存储结构。

3、操作：（1）求工程最短工期；（2）输出关键路径；（3）输出关键活动。

4、要求：界面友好，提示信息完整。

二、系统需求及分析：1、简要介绍：我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。

工程通常分为若干个称为“活动”的子工程。

完成了这些“活动”，这个工程就可以完成了。

我们通常用AOE-网来表示工程。

AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。

AOE-网可以用来估算工程的完成时间。

他可以使人们了解：(1). 研究某个工程至少需要多少时间?(2). 哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。

完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。

《数据结构》课程设计报告课程题目：关键路径学院：班级：学号：姓名：指导教师：完成日期：目录一、需求分析 (2)二、概要设计 (4)三、详细设计 (5)四、调试分析 (12)五、用户使用说明 (12)六、测试结果 (13)七、附录 (13)一、需求分析1、问题描述AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。

它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。

2、设计步骤（1）、以某一工程为蓝本，采用图的结构表示实际的工程计划时间。

（2）、调查并分析和预测这个工程计划每个阶段的时间。

（3）、用调查的结果建立AOE网，并用图的形式表示。

（4 ）、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。

（5）、用SearchMaxPath()函数求出最大路径，并打印出关键路径。

（6）、编写代码并调试、测试通过。

3、测试数据○v2○v5○v1○v4○○v36v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a4 3 v3 v4 a5 4v3 v6 a6 3v4 v6 a7 2v5 v6 a8 1二、概要设计为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={ VR }；VR={＜v，w＞|v，w∈V，且P(v，w)，＜v，w＞表示从v到w的弧，谓词P(v，w)定义了弧＜v，w＞的意义和信息 }基本操作：InitGraph(G);初始条件：图G存在。

吉林大学智慧树知到“计算机科学与技术”《数据结构》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.递归过程中要保存的信息包括()。

A.返回地址B.本次调用中与形参结合的实参值C.本次递归调用中的局部变量值D.执行结果2.对线性表，可进行如下基本操作：()A.随机存取B.插入C.删除D.查找3.不是所有的AOV网都有一个拓朴序列。

()A.正确B.错误4.对有序表的查找方式有以下几种：()A.折半查找B.斐波那契查找C.插值查找D.二叉树查找5.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少()个。

A.k+1B.2kC.2k-1D.2k+16.对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树。

() A.正确B.错误7.具有n(n0)个顶点的无向图最多含有n(n-1)/2条边。

()A.正确B.错误8.算法在发生非法操作时可以作出处理的特性称为健壮性。

()A.正确B.错误9.非空的循环单链表head的尾结点(由指针p所指)满足()。

A.p->next=NULLB.p=NULLC.p->next=headD.p=head10.类string中包含的串运算有()。

A.Find()B.Substr()C.Insert()D.Length()第1卷参考答案一.综合考核1.参考答案：ABC2.参考答案：ABCD3.参考答案：A4.参考答案：ABC5.参考答案：C6.参考答案：A7.参考答案：A8.参考答案：A9.参考答案：C10.参考答案：ABCD。

数据结构课程设计关键路径数据结构课程设计-关键路径#define max 20#include#include#includeusing namespace std;typedef struct ArcNode//定义表结点{int adjvex;//该弧所指向顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针int info;//该弧的权值}ArcNode;typedef struct VNode//定义头结点{int data;//顶点信息ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[max];typedef struct//定义ALGraph{AdjList vertices;int vexnum,arcnum;//图的当前顶点数和弧数int kind;//图的种类标志}ALGraph;typedef struct//定义栈{int *base;//栈底int *top;//栈顶}stack;void initstack(stack &s)//建立空栈{s.base=(int*)malloc(max*sizeof(int)); s.top=s.base;}int stackempty(stack s)//判断是否为空栈{if(s.base==s.top)return 1;else return 0;}int stackfull(stack s)//判断是否为满栈{if(s.top-s.base>=max) return 1;else return 0;}int pop(stack &s)//进行出栈{int e;//出栈先进行赋值，后移动指针if(!stackempty(s)){e=*(s.top-1);s.top--;return e;}else return NULL;}void push(stack &s,int e)//进行入栈{if(!stackfull(s)){s.top++;//进栈先移动指针，后进行赋值*(s.top-1)=e;}}void CreateDG(ALGraph &G)//创建邻接表的图{int k,i,j;char tag;cout<<"请输入图的顶点数目:"<>G.vexnum;cout<<"请输入图的弧的数目:"<>G.arcnum;cout<<"请确认是否输入弧的权值(y/n):"<<endl;< p="">cin>>tag;for(i=1;i<=G.vexnum;++i){G.vertices[i].data=i;//初始化顶点值G.vertices[i].firstarc=NULL;//初始化指针}cout<<"请输入弧的相关信息arc(V1-->V2)"<{cout<<endl<<"请输入弧头"<<"[1,"<<g.vexnum<<"]:";< p="">cin>>i;cout<<"请输入弧尾"<<"[1,"<<g.vexnum<<"]:";< p="">cin>>j;while(i<1||i>G.vexnum||j<1||j>G.vexnum)//如果弧头或弧尾不合法,重新输入{cout<<endl<<"请再次输入弧头"<<"[1,"<<g.vexnum<<"]:";< p="">cin>>i;cout<<"请再次输入弧尾"<<"[1,"<<g.vexnum<<"]:";< p=""> cin>>j;}ArcNode *p;p=(ArcNode*)malloc(sizeof(ArcNode));//分配内存if(!p){cout<<"Overflow!";//如果没有足够的空间,则退出}p->adjvex=j;//对弧结点的弧顶点数据域赋值p->nextarc=G.vertices[i].firstarc;//对弧结点下一条弧指针域赋值p->info=0; // 对弧结点相关信息指针域赋值G.vertices[i].firstarc=p; // 将弧结点插入到对应的单链表if(tag=='y'){cout<<"请输入弧的权值:";cin>>p->info;}}}void ShowMGraph(ALGraph G)//输出图G{int j;ArcNode *p;for(j=1;j<=G.vexnum;++j){if(G.vertices[j].firstarc)cout<<g.vertices[j].data<<"->";</g.vertices[j].data<<"->else cout<<g.vertices[j].data<<">";</g.vertices[j].data<<"> for(p=G.vertices[j].firstarc;p;p=p->nextarc)cout<adjvex<<" "<info<<" "<adjvex<<"->"; cout<<endl;< p="">}}int degree(ALGraph G,int i)//求各顶点的入度{int *indegree,j,k;indegree=(int*)malloc((G.vexnum+1)*sizeof(int)); ArcNode *p;for(j=1;j<=G.vexnum;j++)indegree[j]=0;for(j=1;j<=G.vexnum;j++){for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex;++indegree[k];}}return indegree[i];}void critical(ALGraph G)//输出关键活动{ArcNode *p;int i,k,r,j,*ve,*vl,ee,el,count=0;int *indegree,length;indegree=(int*)malloc(G.vexnum*sizeof(int));ve=(int*)malloc((G.vexnum+1)*sizeof(int));vl=(int*)malloc((G.vexnum+1)*sizeof(int)); stack S,T;initstack(T);initstack(S);//一，求各顶点的入度for(j=1;j<=G.vexnum;j++)indegree[j]=degree(G,j);//二，求各顶点最早发生的时间vefor(j=1;j<=G.vexnum;j++)//入度为零则进栈if(indegree[j]==0)push(S,j);for(j=1;j<=G.vexnum;j++)//对该数组初始化ve[j]=0;while(!stackempty(S)){i=pop(S);push(T,i);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc) {k=p->adjvex; //顶点位置if(--indegree[k]==0) push(S,k);r=p->info;if(ve[i]+r>ve[k])ve[k]=ve[i]+r;}//for结束}//while结束if(count<<"aoe网有回路!"<<endl;<="">return;}//三，求各顶点的最迟时间for(j=1;j<=G.vexnum;j++)//对vl数组进行初始化vl[j]=ve[G.vexnum];while(!stackempty(T)){j=pop(T);for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;r=p->info;if(vl[k]-r<vl[j])< p="">vl[j]=vl[k]-r;}}//四，对活动的最早时间和最迟时间比较cout<<"================================= ============= ================"<<endl;< p=""> printf(" 起点终点最早开始时间最迟完成时间差值备注\n"); for(j=1;j<=G.vexnum;j++)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;r=p->info;ee=ve[j]; el=vl[k]-r;printf("%4d %4d %4d %4d %4d ",j,k,ve[j],vl[k]-r,vl[k]-r-ve[j]);if(ee==el)cout<<" 是关键活动"<<endl;< p="">elsecout<<" 不是关键活动"<<endl;< p="">}//for结束cout<<"================================= ============= ================"<<endl;< p=""> length=ve[G.vexnum];cout<<endl<<"2.关键路径长度为："<<endl;< p="">cout<<" "<<length<<="">}int main()//主函数{ALGraph G;cout<<"=============================="<< endl;< p="">cout<<"======1.创建邻接表图=========="<<endl;< p="">cout<<"======2.输出邻接表图=========="<<endl;< p="">cout<<"======3.寻找关键活动=========="<<endl;< p="">cout<<"======4.退出=================="<<endl;< p="">cout<<"=============================="<< endl;< p="">cout<<"请选择操作:"<<endl;< p="">int a;l1:{cin>>a;}system("cls");while(a<=4){switch(a){case 1:cout<<"请正确创建邻接表图:"<<="" p="">cout<<"Create ALGraph success !"<<<"请选择操作:"<<endl;<="" p="">goto l1;break;case 2:cout<<"输出该邻接表图如下:"<<<"="<<endl; ShowMGraph(G);</p><p>cout<<" p="" 该图输出完毕!"<<endl;<="">cout<<"=================="<<<"请选择操作:"<<endl;<="" p="">goto l1;break;case 3:cout<<"1.输出关键活动如下:"<<="" p="">cout<<"请选择操作:"<<endl;< p="">goto l1;break;case 4:return 0;}}return 0;}</endl;<></endl;<></endl;<></endl;<></endl;<></endl;<></endl;<></endl;<></length<</endl<<"2.关键路径长度为："<<endl;<></endl;<></endl;<></endl;<></endl;<></vl[j])<></endl;<></g.vexnum<<"]:";<></endl<<"请再次输入弧头"<<"[1,"<<g.vexnum<<"]:";<> </g.vexnum<<"]:";<></endl<<"请输入弧头"<<"[1,"<<g.vexnum<<"]:";<></endl;<>。

吉林大学智慧树知到“计算机科学与技术”吉大-数据结构20春离线作业二答案网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.递归过程中要保存的信息包括()。

A、返回地址B、本次调用中与形参结合的实参值C、本次递归调用中的局部变量值D、执行结果2.任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置()。

A、肯定发生变化B、有时发生变化C、肯定不发生变化D、无法确定3.属于插入排序的排序方法有()。

A、直接插入排序B、对半插入排序C、渐减增量排序D、冒泡排序4.非空的循环单链表head的尾结点(由指针p所指)满足()。

A、p->next=NULLB、p=NULLC、p->next=headD、p=head5.二叉树的遍历方式有()。

A、先根遍历B、中根遍历C、后根遍历D、深度遍历6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()。

A、数据元素具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7.设有两个串p和q，求q在p中首次出现的位置的运算称作模式匹配。

()A、错误B、正确8.在具有n个单元的循环队列中，队满共有_______个元素。

A、nB、n-1C、n+1D、n+29.邻接多重表示法对于有向图和无向图的存储都适用。

()A、错误B、正确10.由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44。

()A、错误B、正确第1卷参考答案一.综合考核1.参考答案：A,B,C2.参考答案：C3.参考答案：A,B,C4.参考答案：C5.参考答案：A,B,C6.参考答案：B7.参考答案：B8.参考答案：B9.参考答案：B10.参考答案：B。