湖南科技大学研究生考试试题参***。
1、给出下列函数的上界（或双界）估计并证明结果的正确性。（10分）
解：1）由于，所以由master定理（ⅱ）有。
2）由于，所以由master定理（ⅰ）有。
3）由于，而且，所以由master定理（ⅲ）有。
4）因为且，所以。
5）因为，所以。
2、使用一种程序设计语言描述有序数组的折半搜索算法。（10分）
解：template //
int binarysearch(t a,const t &x, int n)
int left = 0, right = n - 1;
while (left <=right)
return - 1; /未找到x
3、使用一种程序设计语言或伪**描述生成最小生成树的kruskal算法。（10分）
解：template //
bool kruskal(edgenode ed,int n, int e, edgenode t)
int i, k;
sort(ed, ed + e); 对边集合排序。
unionfind u(n); 合并/查找结构，初始时表示n个不同集合。
for (i = 0, k = 0; i
return (k ==n - 1); 是否有最小生成树。
4、使用一种程序设计语言或伪**描述求每对结点之间的最短路径floyd算法。（10分）
解：template //这个算法事先把图中结点编了号的。
void alldist(mat_t &a, mat_t &dist, mat_int &next)
int i, j, k, n;
t x;n = min(
// 建立初始dist=a[0]和next
dist = a;
for (i = 1; i <=n; i++)for (j = 1; j <=n; j++)next(i, j) =j;
for (k = 1; k <=n; k++)
5、使用一种程序设计语言编写一个子程序用于生成的所有排列。（10分）
解：void perm(int t)
for (int i = t; i < n; i++)
6、给出采用优先队列式分支限界法求解下列旅行商问题（从1出发）的示意图和活结点队列。（10分）
解：7、使用拉斯维加斯方法设计一个概率算法，该算法用于判断图（用邻接矩阵表示，含有个顶点）是否含有hamilton回路。（10分）
解：bool hamilton(int **g, int n, int *x)
int i, j, k;
for (i = 0; i < n; i++)x[i] =i; /自然排列。
// 随机选择一个排列。
for (i = 0; i < n; i++)j = rand(0, i), swap(x[i], x[j]);
for (k = 0; k < n; k++)
return true; /满足要求。
int hamilton_lv(int **g, int n, int *x)
for (int k = 0; !hamilton(g, n, x); k++)
return k;
8、考虑下列4个np问题：（10分）
1）hamilton回路问题：给定无向图g=(v, e)，判定其是否含有一哈密顿回路。
2）顶点覆盖问题：给定n个顶点的无向图g=(v, e)是和正整数k，判定g是否有k的顶点覆盖（大小为k的顶点覆盖）。
3）集合覆盖问题：给定一个有限集及的一个集合覆盖和一个正整数，判定是否存在使得覆盖了且。
4）旅行商问题：给定一个无向图g=(v, e)和一个非负整数t，其每一边(u, v)∈e有一非负整数费用c(u, v)。判定g是否存在费用不超过t的旅行商回路。
已知hamilton回路问题和顶点覆盖问题都是np完全的，证明集合覆盖问题和旅行商问题也都是np完全的。
解：1）证明顶点覆盖问题可在多项式时间内转换为集合覆盖问题。
设g=(v, e)是一个无向图，对1≤i≤|v|，令si是与顶点vi关联的所有边的集合。显然覆盖e当且仅当是g的一个顶点覆盖。的构造显然能在多项式时间内完成。
2）证明哈密尔顿回路问题可在多项式时间内转化为旅行商问题。
设图g=(v, e)，构造完全图，其中，费用函数定义为。
显然，该构造过程可在多项式时间内完成。容易证明，g有哈密尔顿回路当且仅当g’有费用为0的旅行商回路。
9、使用一种程序设计语言或伪**描述集合覆盖问题的一种近似算法。（10分）
解：function greedysetcover (x, f) as set
u = xc =
while u <>
选择f中使|s∩u|最大的子集s
u = u - s
c = c∪
wendreturn c
end function
10、使用宽度优先搜索方法遍历下列无向图，请写出搜索过程中待访问队列中的元素。（5分）
解：11、解释下列概念。（5分）
p类问题，np类问题，np难类问题，npc类问题，co-np类问题。
解：p类问题：用确定性算法能在多项式时间内成功求解的问题。
np类问题：用非确定性算法能在多项式时间内成功求解的问题。
问题x是np完全的当且仅当。
1）x∈np；
2）对任何x’∈np都有x’∝px。
如果有一个问题x满足上述性质（2），但不一定满足性质（1），则称该问题是np难的。所有np完全问题构成的问题类称为np完全问题类，记为npc。
co-np类是所有补问题属于np类的问题组成的集合。
09测绘2019考试题
1 平面控制网坐标平差计算步骤 平面控制网坐标平差一般分以下几个步骤 答 1.计算近似坐标x x1 y1 x2 y2 t.2.方向和距离的归心和改化。3.各种闭合 附合条件的检验。4.列出误差方程及条件式。5 组成法方程。6.解算法方程，求得dx dx1 dx2 dy1 dy2 t.7.求得平差后的...
09年安全考试题
四川电力建设二公司。汶川220kv开关站项目部2011年 安规 考试卷。部门 姓名 得分 填空题 每空2分，共计 分 1 安全生产必须贯彻方针。2 进入施工现场的施工人员必须穿戴合格的劳动保护服装并正确佩戴安全帽。严禁穿 或的鞋，以及 进入施工现场。严禁进入施工现场。3 施工现场及其周围的悬崖 陡坎...
09年微机原理考试题
一 简答题 45 8086的内部寄存器？给出 让填写寄存器名称。2 什么是寻址方式？一共有几种寻址方式？3 物理地址为3b2afh，段地址为3a00h，求偏移地址。4 统一编址 独立编址是什么？画图说明。5 微机的输入输出方式有哪些？分别对应于哪些外设？6 中断向量码为21h，算出中断向量地址单元。...