标签：结点 数据结构 高校 路径 邻接矩阵 有向图 顶点 排序 考研

散列表

1. 若在散列表中删除一个记录,应如何操作？为什么？

答：在散列表中删除一个记录：

        在拉链法情况下,可以物理地删除。

        在开放定址法情况下,不能物理地删除,只能做删除标记。该地址可能是该记录的同义词查找路径上的地址,物理地删除就中断了查找路径,因为查找时碰到空地址就判定查找失败。

1. 假定把关键字key散列到有n个表项(从0到n-1编址)的散列表中。对于下面的每个函数H(key)函数,这些函数能够当作散列函数吗？若能,它是一个好的散列函数吗？说明理由。设函数random(n)返回一个0到n-1之间的随机整数(包括0与n-1在内)。

a)        H(key)=key/n

不能作为散列函数,因为key/n可能大于n,这样就无法找到合适的位置。

b)       H(key)=1

能够作为散列函数,但不是一个好的散列函数,因为所有关键字都映射到同一位置,造成了大量的冲突机会。

c)        H(key)=(key+random(n))%n

不能当作散列函数,因为该函数的返回值不确定,这样无法进行正常的查找。

d)       H(key)=key%p(n)；其中p(n)是不大于n的最大素数。

能够作为散列函数,是一个好的散列函数。

 

图

1. 图G是一个非连通无向图,共有28条边,该图至少有多少个顶点？

答：由于图G是一个非连通无向图,在边数固定时,顶点数最少的情况是该图由两个连通子图构成,且其中之一只含一个顶点,另一个为完全图。其中只含一个顶点的子图没有边,另一个完全图的边数为n(n-1)/2=28,得n=8。所以,该图至少有1+8=9个顶点。

1. 如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上?

答：按各顶点的出度进行排序。n个顶点的有向图,其顶点的最大出度是n-1,最小出度为0。这样排序后,出度最大的顶点编号为1,出度最小的顶点编号为n。之后,进行调整,即只要存在弧<i,j>,就不管顶点j的出度是否大于顶点i的出度,都把i编号在顶点j的编号之前,因为只有i<=j,弧<i,j>对应的1才能出现在邻接矩阵的上三角。

1. 对n个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问

a)       如何判别图中有多少条边？

对于邻接矩阵表示的无向图，边数等于矩阵中1的个数除以2；

对于邻接表表示的无向图，边数等于边结点的个数除以2.

对于邻接矩阵表示的有向图，边数等于矩阵中1的个数；

对于邻接表表示的有向图，边数等于边结点的个数。

b)       如何判别任意两个顶点i和j是否有边相连？

在邻接矩阵表示的无向图或有向图中，对于任意两个顶点i和j，邻接矩阵中A[i][j]或A[j][i]为1表示有边相连。

在邻接表表示的无向图或有向图中，对于任意两个顶点i和j，若从顶点表结点i出发找到编号为j的边表结点或顶点表结点j出发找到编号为i的边表结点，表示有边相连；否则为无边相连。

c)       任意一个顶点的度是多少？

邻接矩阵：

无向图，顶点i的度等于第i行中1的个数；入度等于第i列中1的个数；

有向图，顶点i的出度等于第i行中1的个数；入度等于第i列中1的个数；

邻接表：

        无向图：顶点i的度等于顶点表结点i的单链表中边表结点的个数；

        有向图：顶点i的入度等于邻接表中所有编号为i的边表结点数；度数等于入度与出度之和。

1. 深度判断Vi到Vj是否有路径…

int visited[MaxSize]={0};

void DFS ( ALGraph G , int i , int j, bool &can_reach){

//深度优先判断有向图G中顶点Vi到顶点Vj是否有路径，用can_reach来标识

if ( i ==j){

         can_reach=true;

         return;      // i 就是 j

}

visited[i]=1;

for ( int p = FirstNeighbor(G , i) ; p>=0 ; p=NextNeighbor (G , i ,p))

         if( ! visited[p] && ! can_reach)        //递归检测邻接点

                 DFS(G , p , can_reach);

}

1. 广度判断Vi到Vj是否有路径…

int visited[MaxSize]={0};

void BFS ( ALGraph G , int i , int j）{

//广度优先判断有向图G中顶点Vi到顶点Vj是否有路径，是则返回1，否则返回0

InitQueue(Q);   EnQueue(Q,i);  //顶点i入队

while( ! is Empty(Q)){

         DeQueue(Q,u);

         visited[u]=1;

         if(u==j)    return 1;

         for(int p=FirstNeighbor(G,i); p ; p=NextNeighbor(G , u, p)){

                 if(p==j)    return 1;

                 if(! visited[p]){

                         EnQueue(Q,p);

                         visited[p]=1;

                 }

         }

}

return 0;

}

图的应用

1. 下面是一种称为“破圆法”的求解最小生成树的方法：

所谓“破圆法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。

试判断这种方法是否正确。若正确，请说明理由。若不正确，举出反例。

       正确。由经过“破圆法”之后，最终没有回路，故一定可以构造出一颗生成树。下面证明这棵生成树是最小生成树。记“破圆法”生成的树为T，假设T不是最小生成树，则必然存在最小生成树T0，使得它与T的公共边尽可能地多，则将T0与T取并集，得到一个图，此图中必然存在回路，由于“破圆法”的定义就是从回路中去除权最大的边，此时生成的T的权必然是最小的，这与原假设T不是最小生成树矛盾，从而T是最小生成树。

 

1. 已知有向图如下图所示。

1)        写出该图的邻接矩阵表示并据此给出从顶点1出发的深度优先遍历序列。

	1	2	3	4	5	6	7
1	0	3	3	6	∞	∞	∞
2	∞	0	4	∞	5	∞	∞
3	∞	∞	0	∞	4	∞	∞
4	∞	∞	∞	0	∞	5	∞
5	∞	∞	∞	∞	0	∞	3
6	∞	∞	3	∞	∞	0	7
7	∞	∞	∞	∞	∞	∞	0

1，2，3，5，7，4，6

2)        求该有向图都的强连通分量的数目。

7  {1}, {2}, {3}, {4}, {5}, {6}, {7}

l  顶点1无入弧构成第一个强连通分量。删除顶点1以及所有以之为尾的弧。

l  顶点2无入弧构成一个强连通分量。删除顶点2以及所有以之为尾的弧。

l  ……

3)        给出该图的任意两个拓扑序列。

1，2，4，6，3，5，7

1，4，2，6，3，5，7

4)        若将该图视为无向图，分别用Prim算法和Kruskal算法求最小生成树。

 

Prim算法和Kruskal算法求最小生成树，在本题中相同。

 

1. 对下面所示的无向图，按照Dijkstra算法，写出从顶点1到其他各个顶点的最短路径和最短路径长度（顺序不能颠倒）。

 

1. 带权图(权值非负,表示边链接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径,假设从初始顶点到目标顶点之间存在路径,现在一种解决该问题的方法：

a)        设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点。

b)       选择离u最近且尚未在最短路径中的一个顶点v，加入最短路径，修改当前顶点u=v。

c)        重复步骤b),直到u是目标顶点时为止。

不一定能求得最短路径…

 

若按照上述方法，A到C的最短路径为：A-B-C。但实际上，A-D-C更短。

1. 使用prim算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题：

a)        对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

b)       图G的MST是唯一的吗？

c)        对任意的带权连通图，满足什么条件时，其MST是唯一的？

a)

b)是唯一的。第一小题的最小生成树包括图中权值最小的4条边，其他边除了(A,E)外都比这4条边大，但若用(A,E)替换同权值的(C,E)，A,D,E三个顶点构成了回路，因此不能替换，所以此图的MST唯一。

c)当带权连通图的任意一个环中所包含的边的权值均不相等时，其MST是唯一的。此题不要求回答充分必要条件，所以回答一个限制边权值的充分条件即可。

1. 已知有6个顶点(顶点编号为0~5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。

4

6

∞

∞

∞

5

∞

∞

∞

4

3

∞

∞

3

3

要求：

a)        写出图G的邻接矩阵A。

b)       画出有向带权图G。

c)        求图G的关键路径，并计算该关键路径的长度。

 

 

 

1）

2）至少需要16

3）

4）a2,a6,a9,a12可以缩短时间…

1）

2）

3）V1->V3->V4->V6，完成该工程至少需要8

1. 试说明利用DFS如何实现有向无环图拓扑排序。

对于有向无关图G中的任意结点u,v,它们之间的关系必然是下列三种之一：

a)         假设结点u是结点v的祖先，则在调用DFS访问u的过程中，必然会在这个过程结束之前递归地对v调用DFS访问，即v的DFS函数结束时间先于u的DFS结束时间。从而可以考虑在DFS调用过程中设定一个时间标记，在DFS调用结束时，对各结点计时。因此，祖先的结束时间必然大于子孙的结束时间。

b)         若u是结点v的子孙，则v为u的祖先，按上述思路，v的结束时间大于u的结束时间。

c)         若u和v没有关系，则u和v在拓扑序列的关系任意。

1. 一连通无向图，边非负权值，问用Dijkstra最短路径算法能否给出一颗生成树，该树是否一定是最小生成树。不一定

 

排序

1. 给出关键字序列{4,5,1,2,6,3},的直接插入排序过程。

 

1. 给出关键字序列{50,26,38,80,70,90,8,30,40,20}的希尔排序过程(取增量序列为d={5,3,1},排序结果为从小到大排序)。

 

1. 直接插入：
2. 希尔排序：
3. 冒泡排序：
4. 快速排序：

 

1. 简单选择：
2. 指出堆和二叉排序树的区别：以小根堆为例，堆的特点是双亲结点的关键字必须小于等于该孩子结点的关键字，而两个孩子结点的关键字没有次序规定。在二叉排序树中，每个双亲结点的关键字均大于左孩子结点的关键字，均小于右子树结点的关键字，也就是说，每个双亲结点的左、右孩子的关键字有次序关系。这样，当对两种执行中序遍历后，二叉排序树会得到一个有序的序列，而堆则不一定能得到一个有序的序列。
3. 若只想得到一个序列中第k(k<=5)个最小元素之前的部分排序序列，则最好采用什么排序方法？

a)        在基于比较的排序方法 中，插入排序、快速排序和归并排序只有在将元素全部排完序后，才能得到前k小的元素序列，算法的效率不高。

b)       冒泡排序、堆排序和简单选择排序可以，因为它们在每一趟中都可以确定一个最小的元素。采用堆排序最合适，对于n个元素的序列，建立初始堆的时间不超过4n，取得第k个最小元素之前的排序序列所花的时间为klog₂n,总时间为4n+klog₂n；冒泡和简单选择排序完成此功能所花时间为kn,当k>=5时，通过此比较可以得出堆排序最优。

1. 有n个元素已构成一个小根堆，现在要增加一个元素K_n+1，请用文字简要说明如何在log₂n的时间内将其重新调整为一个堆。

将K_n+1插入数组的第n+1个位置(即作为一个树叶插入)，然后将其与双亲比较，若大于其双亲则停止调整，否则将K_n+1与其双亲交换，重复地将K_n+1与其新的双亲比较，算法终止于K_n+1大于等于其双亲或K_n+1本身已上升为根。

标签：结点,数据结构,高校,路径,邻接矩阵,有向图,顶点,排序,考研
From： https://www.cnblogs.com/kaede/p/16824536.html