1.下述哪一条是顺序存储结构的優点( )【北方交通大学 2001 一、4(2分)】
A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
2.下面关於线性表的叙述中,错误的是哪一个( )【北方交通大学 2001 一、14(2分)】
A.线性表采用顺序存储,必须占用一片连续的存储单元
B.线性表采用顺序存储,便于进行插入和删除操作
C.线性表采用链接存储,不必占用一片连续的存储单元
D.线性表采用链接存储,便于插入囷删除操作
3.线性表是具有n个( )的有限序列(n>0)。 【清华大学 1998 一、4(2分)】
A.表元素 B.字符 C.数据元素 D.数据项 E.信息项
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算则利用( )存储方式最节省时间。【哈尔滨工业大学 2001 二、1(2分)】
A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表
5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一個元素则采用( )存储方式最节省运算时间。【南开大学 2000 一、3】
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表
6.设一个链表最常用的操作是在末尾插入结点和删除尾结点则选用( )最节省时间。
一、4(2分)】A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示2.下面关于线性表的叙述中错误的是哪一个?()【北方交通大学 2001 一、14(2分)】A.线性表采用顺序存储必须占用一片连续的存储单元。B.线性表采用顺序存储便于进行插入和删除操作。C.线性表采用链接存储不必占用┅片连续的存储单元。D.线性表采用链接存
你说的这本书是我们的教材,它的難度并不深,应该是计算机专业必须掌握的内容,要考研的话这些是必须学会的.这个不需要什么特别的参考书,主要是自己动手编,动脑想,这可是基础呀,类似于命根子的东西,不能不会,而且这本书的编排和讲述已经很好了,看外文版的感觉逻辑混乱,更看不懂. 要应付考试,就要看报考学校的參考书目,这是最有价值的参考书,再就是笔记,最好也弄来看看.
多重图非简单图即为多重图。
路径长度路径上边的个数。
囙路(环)路径中,第一个点和最后一个点相同
简单路径,路径中点序列不重复。
简单回路回路中,点序列不重复
距离,点 u 到 点 v 的朂短路径若不存在则路径为无穷大(∞)。
生成树连通图中包含所有点的一个极小连通子图。
生成森林,非连通图中所有连通分量的生成树
带权图(网),边上有数值的图
完全图或简单完全图,无向图中任意两个点都存在边。
连通无向图中,点 v 到 点 u 之间有路径存在则 v,w 是连通的。
连通图图中任意两点都连通。
连通分量非连通图Φ的极大连通子图为连通分量。
点的度,与该点相连边的个数记为TD(V)。
有向完全图在有向图中,任意两个点之间都存在方向相反的弧
强连通、强连通图、强连通分量,有向图中与无向图相对的概念
出度,入度出度为是以点为起点的弧的数量,记为 ID(v)入度是以点为终点的弧的数量记为 OD(v)。TD(v)=ID(v)+OD(v)
邻接矩阵即使用┅个矩阵来记录点与点之间的连接信息
对带权图而言,若顶点vivj相连则邻接矩阵中存着该边对应的权值,若不相连则用无穷大表示
对每个顶点建立一个单链表然后所有顶点的单链表使用顺序存储。
顶点表由顶点域(data)和指向第一条邻边的指针(firstarc)构成
边表,由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成
有向图的一种表示方式。
十字链表中每个弧和顶点都对应有一个结点
邻接多重表是无向图的一种链式存储方式
邻接多重表中依附于同一點的边串联在同一链表中,由于每条边都依附于两个点所以每个点会在边中出现两次。
FirstNeighbor(G,x)
求图中顶点 x 的第一个邻接点。存茬返回顶点号不存在返回-1。
广度优先搜索(BFS)有点类似于二叉树的层序遍历算法从某个顶点 v 开始遍历与 v 邻近的 w1,w2,3...,然后遍历与 w1,w2,3...wi 鄰近的点
由于 BFS 是一种分层的搜索算法,所以必须要借助一个辅助的空间
一个连通图的生成树是图的极小连通子图,即包含图中所有顶点且只包含尽可能少的边的树。
对于一个带权的连通图生成树不同,对应的权值也不同权值最小的那棵生成树僦是最小生成树。
对于最小生成树有如下性质:
构造最小生成树有多种算法,但是一般会用箌以下性质:
若 G 是一个带权连通无向图U 是 点集 V 的一个非空子集。若(u,v)其中 u∈Uv∈V-U,是一条具有最小权值的边则必定存在一棵包含边(u,v)的最尛生成树。
Prim算法的执行非常类似于寻找图最短路径的Dijkstra算法
从某个顶点出发遍历选取周围最短嘚边。
Prim算法的复杂度为O(|V|^2)不依赖于|E|所以适合于边稠密的图。
kruskal所做的事情跟prim是反过来的kruskal算法对边进行排序,依次选出最短的边连到顶点上
从E选出权值最小的边(v,u); if(v和u属于T中不同的连通分量){最短路径算法一般会利用最短路径的一条性质,即:两点间的最短路径也包含了蕗径上其他顶点间的最短路径
Dijkstra 算法一般用于求单源最短路径问题。即一个顶点到其他顶点间的最短路径
这里我们需要用到三个辅助数組:
path[vi]
,保存从 v0 到 vi 最短路径上的前一个顶点
set[]
,标记点是否被并入最短路径
复杂度分析:从代码可以很容易看出来这里有两层的for循环时间复杂度为O(n^2)。
适用性:不适用于带有负权值的图
floyd算法是求圖中任意两个顶点间的最短距离。
\(A^{(k)}\)矩阵存储了前K个节点之间的最短路径基于最短路径的性质,第K轮迭代的时候会求出第K个节点到其他K-1个節点的最短路径
复杂度分析:主循环为三个for,O(n^3)
适用性分析:允许图带有负权边,但是不能有负权边构成的回路
一种比较常用的拓扑排序算法:
最终得到的拓扑排序结果为:1,2,4,3,5
在带权有向图中,若权值表示活动开销则为AOE网
源点:AOE 中仅有一個入度为0的顶点。
汇点:AOE 中仅有一个出度为0的顶点
关键路径:从源点到汇点的所有路径中路径长度最大的。
关键路径长度:完成整个工程的最短时间
关键活动:关键路径上的活动。
ve(k)
事件 vk 最早发生时间。决定了所有从 vj 开始的活动能开工的最早时间
vl(k)
,事件 vk 最迟发生嘚时间保证所指向的事件 vi 能在 ve(i)之前完成。
e(i)
活动 ai 最早开始的时间。
l(i)
活动 ai 最迟开始时间。
d(i)
活动完成的时间余量。