对于一个有向图(b),假定采用邻接表表示,并且假定每个顶点单链表中的边结点是按出边邻接点序号
从大到小的次序链接的,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
从大到小的次序链接的,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
第1题
(a)在图8.10中找出两个不同大小的最小支配集。
(b)设棋盘的64个方块用64个顶点表示,如果两顶点对应的两个方块是在同一行,同一列或同一对角线上,则这两顶点之间有一条边。已知5个皇后能被放在棋盘上,使它们支配所有64个方块,而且5是必须的最小皇后数,再用图论名词叙述这一结论.
第2题
问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
第3题
对于一个具有N个顶点的图,如果我们采用邻接矩阵法表示,则此矩阵的维数应该是()
A.(N-1)×(N-1)
B.N×N
C.(N+1)×(N+1)
D.不确定
第6题
问题描述:给定一棵树T,树中每个顶点u都有权值w(u),可以是负数.现在要找到树T的一个连通子图使该子图的权值和最大.
算法设计:对于给定的树T,计算树T的最大连通分支.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示树T有n个顶点.树T的顶点编号为1,2,...,n.第2行有n个整数,表示n个顶点的权值.接下来的n-1行中,每行有表示树T的一条边的2个整数u和v,表示顶点u与顶点v相连.
结果输出:将计算出的最大连通分支的权值输出到文件output.txt.
第7题
除留余数法构造哈希函数和线性探测法处理冲突,试求出每一元素在哈希表中的初始哈希地址和最终哈希地址,画出最后得到的哈希表,求出平均查找长度。
第8题
为了确定使用避孕套对于减少有性行为的高中生之间性疾病的传播是否有效,一个简单的模型为
其中,infrate表示有性行为的学生中感染性病的比例,conuse表示声称合理地、有规律地使用了避孕套的男孩子比例,avginc表示平均家庭收入,而city则是一个表示所在学校是否处在城里的虚拟变量;这个模型是在学校这个层次上做的。
(i)在因果性和其他条件不变的模式下解释上述方程,的符号应该是什么?
(ii)为什么infrate和conuse可能是联合决定的?
(iii)如果避孕套使用率随着性病感染率的提高而提高,所以在方程
courseγ0+γ1infrate+其他因素
中y1>0,那么用OLS估计β1时可能的偏误是什么?
(iv)令a表示一个二值变量,若学校有分发避孕套项目则取值1.解释这如何利用这一变量对通过β1(和其他系数)进行Ⅳ估计。我们必须在每个方程中对condis做怎样的假定?
第11题
现进程有如下的访问序列:其逻辑地址为八进制的105、217、567、1120、2500。
试问给定的这些地址能否进行转换?若能,请说明地址转换过程及相应的物理地址。若不能,则说明理由。