电子科技大学研究生算法设计与分析拟考题及答案评分细则 (3)
第 1 页 共 6 页
一、Please answer T or F for each of the following statements to indicate whether
the statement is true or false
1. The knapsack problem can be solved in polynomial time by using dynamic programming.
( F )
2. Some problems in NP can be solved in polynomial time.
( T )
3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem.
( F )
4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T )
5. log 2)n n O =. ( F )
二、Arrange the following functions in ascending asymptotic order of growth rate:
log 1001()5log n f n n n n =+，log loglog 2()2n n f n +=，3()f n =24()2n f n n =+，5()(2log )n f n n =+.
参考答案：f2，f3，f1，f4，f5
三、Please answer the following questions:
(a) What are the main steps of designing a dynamic programming algorithm? 参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem? 参考答案：1.证明该问题属于NP ；2.选一个已知的NPC 问题B ；3.将问题B 归约到该问题上。
四、The Traveling salesman problem (TSP) is defined as follows: Given a graph,
the task is to find a shortest possible route that visits each vertex exactly once and returns to the origin vertex.
Fig. 1
For the graph shown in Fig. 1,
(a) find a solution to TSP ((the route is starting from A and back to A);
(b) find a longest directed cycle that contains vertex A.
参考答案：|
（a）A->D->C->B->A 35+12+30+20=97
（b）A->C->B->D->A 42+30+34+35=141
五、Design an algorithm for the following Interval Scheduling problem: There are
n jobs each of which has a starting time s and a finishing time f. Two jobs are compatible if they don’t overlap. The goal of the problem is to find a maximum set of mutually compatible jobs.
参考答案及评分标准：
将所有工作（Interval）按其完成时间的先后进行排序；
在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。
六、Find a minimum s-t cut in the following graph (the number beside the edge is
the capacity of the edge). Y ou are required to give the computation steps and show the size of the cut.
第 2 页共 6 页
参考答案：35. 有两个解：{S，4，3，8}和{S，1，2，3，4，5，6，7，8，9}
评分标准：说明计算该图从s到t的最大流
给出第一个增广连
后面任意两个增广连（
最后答案35和这个cut
七、Prove that if we can check if a graph has a path of length k in polynomial time
then we can also find a path of length k in polynomial time.
参考答案及评分标准：依次从图中删除一条边，然后检查是否还存在长度为k的路径，如果存在则直接删除，如果不存在则保留该边。如此下去，最后图只剩下k条边。
以上思想正确给全分。
八、A Hamiltonian cycle in a graph is a cycle that contains each vertex. The
Hamiltonian Cycle problem is to find a Hamiltonian cycle in a graph. The Constrained Hamiltonian Cycle problem is to find a Hamiltonian cycle passing through some given edges in the graph.
Give a polynomial reduction from the Constrained Hamiltonian Cycle problem to the Hamiltonian Cycle problem.
参考答案及评分标准：在每个给出的要求通过的边上添加一个顶点（度数
第 3 页共 6 页
第 4 页 共 6 页
为2），这样Hamilton cycle 就必须通过这些边了。
以上思想正确给全分。
九、Answer the following questions.
Given a graph G with nonnegative vertex weight, the Weighted V ertex Cover problem is to find a minimum vertex set (the weight of vertices in the set is minimized) such that each edge in the graph has at least one endpoint in the set. (a) Please give an integer programming formulation of the Weighted V ertex Cover problem.
(b) Give a 2-approximation algorithm based on linear programming.
(c) Prove that your algorithm guarantees the approximation ratio 2.
参考答案及评分标准：
（a ） m i n ..1
f o r e a c h e d
g e 0o r 1f o r e a c
h v e r t e x
i
i j i j i i x s t x x x x x x +≥=∑ （b ） 将以上整数规划改为线性规划：将约束条件0o r 1f o r e a c h i i x x =改为01for each vertex i i x x ≤≤，并且将解中x_i 值大于等于0.5的选入点覆盖中。
（c ）证明在教材在有。大体思路对可以给全分。
十、There are m machines and n=2m+1 jobs, where two of jobs has length of
(m+1,m+2, m+3, …, 2m) respectively , and one job has length of m. Each job must be processed contiguously on a machine and each machine can process at most one job at a time. Y ou are asked to assign jobs to machines to minimize the makespan (the longest processing time on any machine).
(a) Give an approximation solution by using the longest processing time first
第 5 页 共 6 页
(LPT) algorithm. (give the main idea of LPT and the final solution)
(b) Try to find an optimal solution for this problem.
参考答案及评分标准：
（a ）LPT 算法基本思想是将任务按照处理时间长度降序排列，总是将处理时间最长的任务分配到目前负载最低的机器上。
（b ）The optimal solution of the minimizing the makespan is 3m+2. 因为所有任务长度之和是3m^2+2m, 共有m 个机器，每个机器都分配相同长度的任务（3m^2+2m ）/m=3m+2.
十一、 Given a graph, the V ertex Cover problem is to find a minimum subset of
vertices such that each edge has at least one endpoint in it; the Independent Set problem is to find a maximum subset of vertices such that there is no edge between any two vertices in it, and the Clique problem is to find a maximum subset of vertices such that there is an edge between any two vertices in it. Please give a polynomial reduction from the V ertex Cover problem to the Independent Set problem and a polynomial reduction from the Independent Set problem to the Clique problem.
参考答案及评分标准：
VC 到IS 的归约：图中除去vertex cover 中的点剩下的点就是一个independent set 。
IS 到 Clique 的归约：让G ’为G 的补图，则G 中的independent set 就是G ’中的clique 。
十二、 U se dynamic programming to solve the following knapsack problem: There
are n different types of items and each type has two pieces (totally we have 2n items). Item i has weight of 0i w > kilograms and value of 0i v > dollars. Y ou have a knapsack that can contain at most W kilograms. How to fill your knapsack with the items to maximum the value?
(a) Please define your subproblem;
第 6 页 共 6 页 (b) Give the recurrence relation based on your subproblems;
(c) Solve the following instance showed in Table 1 by using the bottom-up method. Y ou are required to give the computation steps (the table used to store the solutions to the subporblems).
Table 1: There are 5 items, each of which has two pieces. The capacity of the
knapsack is 10 kilograms.
参考答案及评分标准：
（a ）定义OPT （i ，w ）为只能选择前i 种物品且背包容量为w 的最优解；
（b ） 建立递归关系式：
{}i 0if i 0(,)(1,)if w w
max (1,),(1,),2(1,2)otherwise i i i i OPT i w OPT i w OPT i w v OPT i w w v OPT i w w =??=->??-+--+--?
其中第一条边界条件1分，第二条1分，第三条递归关系式3分。 （c ）画出存储的表格，用自底而上的方法求解
算出最后正确答案
电子科技大学硕士研究生培养方案
电子科技大学硕士研究生培养方案.doc 目录课程编号、课程分级及研究生获取课程学分计算说明.............................................................1 电子科技大学学科点一览表（2006.06）....................................................................................4 电子科学与技术一级学科硕士研究生培养方案.....................................................................6 计算机科学与技术一级学科硕士研究生培养方案...................................................................9 材料科学与工程一级学科硕士研究生培养方案. (12) 数学一级学科硕士研究生培养方案.......................................................................................15 区域经济学学科硕士研究生培养方案...................................................................................18 金融学学科硕士研究生培养方案...........................................................................................21 金融工程学科硕士研究生培养方案.......................................................................................21 数量经济学学科硕士研究生培养方案...................................................................................24 宪法学与行政法学学科硕士研究生培养方案.......................................................................27 国际政治学科硕士研究生培养方
电子科技大学研究生试题《图论及其应用》(参考答案)
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
《计算机算法设计与分析》习题及答案
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
电子科技大学研究生算法设计与分析拟考题及答案评分细则 (2)
一、Please answer T or F for each of the following statements to indicate whether the statement is true or false 1. An algorithm is an instance, or concrete representation, for a computer program in some programming language. ( F ) 2. The following problem is a Decision Problem: What is the value of a best possible solution? ( F ) 3. The dynamic programming method can not solve a problem in polynomial time. ( F) 4. Assume that there is a polynomial reduction from problem A to problem B. If we can prove that A is NP-hard, then we know that B is NP-hard. ( F ) 5. If one can give a polynomial-time algorithm for a problem in NP, then all the problems NP can be solved in polynomial time. ( F ) 6. In an undirected graph, the minimum cut between any two vertices a and b is unique. ( F) 7. Linear programming can be solved in polynomial time, but integer linear programming can not be solved in polynomial time. ( T ) 8. We can solve the maximum independent set problem in a graph with at most 100 vertices in polynomial time. ( T ) 结论 9. If an algorithm solves a problem of size n by dividing it into two subproblems of size n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(n log n) time. ( T ) 10. Neural Computation, Fuzzy Computation and Evolution Computing are the three research fields of Computational Intelligence. ( T ) 二、Given the following seven functions f1(n) = n5+ 10n4, f2(n) = n2+ 3n , f3(n) = f4(n) = log n + (2log n)3, f5(n) = 2n+n!+ 5e n, f6(n) = 3log(2n) + 5log n, f7(n) = 2n log n+log n n. Please answer the questions: 第 1 页共5 页
答案(电子科大版)图论及其应用第一章
习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)
m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；
算法设计与分析课后部分习题答案
算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中
for(i=0;i
电子科技大学研究生学位授予实施细则
电子科技大学研究生学位授予实施细则 第一章 总 则 第一条根据《中华人民共和国学位条例》、《中华人民共和国学位条例暂行实施办法》，结合我校的实际情况，制定本实施细则。 第二条按国务院学位委员会批准我校有权授予学位的学科领域和学位类型授予研究生硕士、博士学位。 第三条拥护中国共产党的领导，拥护社会主义制度，遵守宪法、法律、法规，具有良好的道德品德，并具有一定学术水平者，可按本细则的有关规定，申请相应的学位。 第二章 硕士学位 第四条学术水平 硕士研究生或具有硕士生毕业同等学力的人员，按《电子科技大学硕士研究生培养方案》的要求完成规定的培养环节和学分，通过学位论文答辩，达到下述学术水平者，授予硕士学位： 1.在本学科或领域掌握坚实的基础理论和系统的专门知识； 2.具有从事科学研究工作或独立担负专门技术工作的能力。 第五条硕士学位论文工作 硕士学位论文的选题应对科技和社会发展有一定的价值。硕士生在导师指导下确定选题和开展学位论文工作。论文的工作时间一般不少于1年，论文工作期间应每周1次向导师汇报研究进展。硕士生到校外单位及委培硕士生回原单位做学位论文，须经导师、学院批准。 1.开题报告 （1）开题报告的时间。硕士生在确定选题，大量阅读文献的基础上，原则上应在入学的第三学期期末之前完成开题报告。 （2）开题报告的方式。开题报告应以报告会的形式，在教（科）研室或以上范围公开举行。开题报告会考评组须由本学科及相近学科至少3位副高级及以上的专家组成。 （3）开题报告的内容。依据《硕士研究生学位论文开题报告表》的要求，做开题报告。考评组对开题报告进行认真审查，并作出考评意见。开题报告会后，硕士生及时完成《硕士研究生学位论文开题报告表》，交学院保存。 （4）开题报告未通过者，须在导师的指导下3个月后才能申请重新开题。2次开题报告不过者，应终止硕士生的学业（作退学处理）。 （5）因正当原因改变选题，须按上述要求重做开题报告。 （6）开题报告通过6个月后方能申请学位论文中期考评。 2.中期考评 （1）学位论文开题6个月后，硕士生可申请进行中期考评，在教（科）研室或以上范围公开举行，向考评组作论文工作进展情况报告。考评组须由本学科及相近学科至少3位副高级及
图论及其应用答案电子科大
图论及其应用答案电子科 大 Newly compiled on November 23, 2020
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。
电子科技大学2014年《809管理学原理》考研专业课真题试卷
电子科技大学 2014年攻读硕士学位研究生入学考试试题 考试科目：809管理学原理 注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 一、名词解释（每小题3分，共15分） 1．概念技能 2．管理绿色化 3．学习型组织 4．平衡记分卡 5．信度与效度 二、判断题（每小题1分，共20分。在正确说法后面写T，在不正确说法后面写F） 1.管理学反映了管理过程的客观规律性，具有显著的科学性。但是，管理过程中的诸多不确定因素使管理本身无法完全量化，因而它是一种不精确的科学。 2.效率与效果之间的差别可表述为：效果是使组织资源的利用成本达到最小化，而效率则是使组织活动实现预定的目标。 3.主张通过与管理者职能相联系的办法把有关管理知识汇集起来，力图把用于管理实践的概念、原则、理论和方法揉合在一起以形成管理学科的学派是管理过程学派。 4.按决策的作用（所处地位）可以把决策分为战略决策、管理决策和专业决策。 5.行为决策学派认为决策是一个选优过程，所以决策结果是基于已有资源背景下寻求利润或收益的尽可能大。 6.群体决策理论的三个前提是自主性、共存性、差异性。 7.组织变革的阻力是直接的、公开的、消极的，应予以杜绝。 8.“理解，执行；不理解，执行中理解”，这是在管理活动中具有分权化倾向的管理者的表述。 9.管理者能力越强，管理者的管理幅度越大；被管理者能力越强，管理者的管理幅度越小。 10.分工是社会化大生产的要求，所以分工越细，效率就越高。 11.参谋职权是指参谋人员或职能部门主管所拥有的原属于直线主管的那部分权力。 12.领导工作是组织结构中一种特殊的人与人的关系，其实质是影响。 《管理学原理》试题共4页，第1页
算法设计与分析第2版 王红梅 胡明 习题答案
精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include
电子科技大学经济与管理学院
电子科技大学经济与管理学院标准实验报告 （实验）课程名称企业经营决策模拟 电子科技大学教务处制表
电子科技大学 实验报告 学生姓名：学号：指导教师：曹欢 实验地点：经管大楼实验时间： 一、实验室名称：经管大楼 二、实验项目名称：运用《人机对抗——网络版》系统，进行决策仿真实践 三、实验学时：8 四、实验原理： 根据上机实验操作，运用所学的相关知识，对所遇到问题进行分析，提出解决方案。利用决策仿真，巩固已学的相关知识，增加实践经验。 五、实验目的： （1）掌握决策时所需要考虑的因素 （2）在环境发生变化时采取相应的措施 （3）进一步从整体上考虑企业的优化决策，进而激发创新意识，提高创新能力 六、实验内容： 对相关的理论知识进行强化、熟悉人机对抗版的操作步骤，上机实际操作，针对实验结果进行讨论 七、实验器材（设备、元器件）： 东华大学现代企业经营决策仿真系统软件、电脑、投影仪
八、实验步骤： （1）有重点地学习部分理论知识，分别侧重于竞争条件下的产品市场需求预测、产品市场销售决策、生产方案决策、物 料采购决策、决策方案全面预算和方案成果盈亏计算等现 代企业决策的各个主要方面及其相互联系和影响。 （2）正式运用《人机对抗——网络版》系统，进行决策仿真实践。 九、实验数据及结果分析： （需要粘贴软件中第六步骤的四张表格）！！ 十、实验结论： 结果如何，为什么会造成这样的结果的分析。例如，战胜电脑，个人的策略是什么控制了哪些关键点输给电脑，或成绩不理想，是由于哪些环节出了问题 十一、总结及心得体会： 请根据个人的思考和分析来填写。例如，在这次实验中的体会。以及
电子科技大学导师给研究生的36条建议
电子科技大学导师给研究生的36条建议 1. 研究生真经：尽量完美的做好一件事，在完成目标的过程中有种自我感觉，其他人同时来做这件事时，起码得有三个人的绩效才能达到我现在的水平。 2. 关于毕业答辩前需达到的水平，是以下三个指标的和： (1) 不少于一篇学术论文。该论文应尽量是正规的期刊，或国内不收费的学术会议上的论文，不是为发论文而组织的会议或期刊上的论文(原则由指导教师定义)。 (2) 至少完成一项高质量的科研任务。 (3) 至少完成一项高质量的专利申请。 3. 关于学分：一定量的学分是硕士研究生毕业的必备条件，也就是说没有修满足够的学分不能硕士毕业答辩。但是，学分的相对重要性是次要的：修某些课程的目的，是为了更好地做研究，出研究成果，也就是说，修学分是一个相对基础的学习过程，修学分是为了更好地完成科研任务。 4. 关于科研任务：当有了某个研究目标、或研究兴趣时，科研任务是读硕士研究生期间最重要的，因为研究生毕业后给人的感觉是靠科研过程来驱动升华的。科研任务的重要性起码高于修学分。在当今信息爆炸的时代，对于指导教师所研究的专业，硕士研究生的学习，是通过科研的驱动来进行的，是为用而学的。 5. 关于指导教师对你本科、中学学习成绩的看法：除非你一直是你所在班上的第一名，否者，只要你通过了考研要求的分数，以后指导教师不会再考虑你本科或中学的学习成绩多么好或多么差。如你一直是你所在班上的第一名的话，这方面指导教师对你可能还有一点或不超过一点的印象：你掌握了一种会考试的技能(这也是一种成功模式)。 6. 关于马太效应与成功模式：所谓马太效应，意思是指在过去及现在的社会中，对某一个人来说，如果他是通过自己奋斗致富的，则这位富人会越来越富有；与之对应的是穷人越来越穷。指导教师认为，之所以富人会越来越富，是因为某位富人掌握了一种致富或做事的成功模式，该富人只需拷贝其成功模式，就会越来越富有；而所有的穷人之所以穷，因为他一直没有找到一种致富或做事成功的经验。作为硕士研究生，他在读研期间，应该至少体会到一种做事成功的经验；高一点的要求是，在读研期间，掌握一种成功模式，以便毕业之后在社会上复制其成功模式。 7. 关于爱心：起码有一次爱心经历，发自内心的经历，自己一人把所在的宿舍卫生彻底的扫一遍。起码有一次爱心经历，发自内心的经历，把所在的办公室卫生彻底的扫一遍，
图论及其应用答案电子科大
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
算法设计与分析考试题及答案
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
电子科技大学2010年管理学考研真题
电子科技大学2010年管理学考研真题 一、判断题（1*20） 1、一些文献对管理定义阐述不同，有活动论、过程论、职能论、工作论和环境论。其中1978年诺贝尔经济学奖获得者西蒙认为：“管理就是决策”，以及哈佛大学教授德鲁克认为“管理是一种以绩效责任为基础的专业职能”。这两种解释都属于活动论。 2、各项管理职能都有自己独特的管理形式。例如计划职能通过目标的制定和行动的确定表现出来。组织职能通过组织设计和人员配备表现出来。但创新职能本身并没有某种独特的表现形式。 3、人群关系理论是“行为科学”管理学派的早期思想，它只强调重视人的行为，而行为科学还要求进一步研究人的行为规律，找出产生不同行为的影响因素，探讨如何控制人的行为以达到预定目标。 4、马斯洛的需要层次理论，虽然在发表为不少人接受，但在实际工作中得到应用，但对它层次排列是否符合客观实际也有不少争议，有人认为它对人的动机没有完整的看法，没有提出激励方法等。这一理论注意到了工作于工作环境的关系。 5、从伦理的角度看，具有内在控制中心的人不大可能对其行为后果负责，更可能依赖外部力量。相反，具有外在控制力量的人则更可能对后果负责并依赖自己内在的是非标准来指导其行为。 6、“IBM就是服务”是美国国际商业机器公司的价值观。“顾客第一”是日本三菱公司的组织精神。 7、强烈管理欲望是有效进行管理工作的基本前提。正直和诚实是每个组织成员都应该具备的基本品质。 8、计划是决策的前提，决策是计划的逻辑延续，计划为决策提供依据，决策为计划的目标实现提供保证。 9、据有关权威部门调查统计分析，家电行业某类家用加湿取暖器在近六年的市场年销售量依次是1000万、2000万、3500万、5500万、5800万、5850万台。由此可以推断该类家用加湿取暖器正处于其产品生命周期的成长期。 10、如果高层次对低层次的决策没有任何控制，则分权程度高：如果低层次在决策后要向高一级管理部门报告备案，则分权程度次之：如果低层次在决策前要征询上级部门的意见，则分权程度更低。 11、管理劳动横向分工的结果是部门的设置；纵向分工是根据管理幅度的限制，确定管理系统的层次，并根据管理层次在管理系统中的位置，规定各层次管理人员的职责和权限。 12、管理者能力越强，管理者的管理幅度越大；被管理者能力越强，管理者的管理幅度越小。 13、某公司安排某员工完成一项任务，其上司告诉他可以在一个月内完成，而事隔两天，总裁亲自过问此项目，要求他在半个月内完成。这说明该公司组织设计违背了命令统一原则。 14、泰罗的科学管理理论是假设把工人看成经济人，工人追求最高的工资收入而业主难以做到，就必须用科学管理的方法来提高效率。在这里业主不是经济人 15、信息技术对集权化和分权化可能带来双重影响。希望集权化的管理者能运用先进技术区获取更多信息和做出更多决策，同时管理者也能够向下属分散信息并且增强参与性与自主性。 16、目标管理是美国管理学家维克多·弗鲁姆在1954年提出来的，是一种管理管理者的方法。 17、绿色和平组织为了保护人类赖以生存的环境其活动踪迹遍布全球每一角落。他对于一家石油化工企业来说，绿色和平组织属于组织因素中的一般环境因素的社会环境。
算法设计与分析试卷及答案
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人
电子科技大学研究生专业介绍
目录 电子科技大学概况 0 电子科技大学博士、硕士学位授权点一览表 (3) 信息与通信工程一级学科博士研究生专业 (5) 材料科学与工程一级学科博士研究生专业 (8) 计算机科学与技术一级学科博士研究生专业 (10) 马克思主义基本原理学科博士研究生专业 (12) 思想政治教育学科博士研究生专业 (14) 应用数学学科博士研究生专业 (16) 等离子体物理学科博士研究生专业 (18) 凝聚态物理学科博士研究生专业 (20) 光学学科博士研究生专业 (22) 无线电物理学科博士研究生专业 (24) 机械电子工程学科博士研究生专业 (26) 光学工程学科博士研究生专业 (28) 测试计量技术及仪器学科博士研究生专业 (30) 物理电子学学科博士研究生专业 (32) 电路与系统学科博士研究生专业 (34) 微电子学与固体电子学学科博士研究生专业 (36) 电磁场与微波技术学科博士研究生专业 (38) 电子信息材料与元器件学科博士研究生专业 (40) 通信与信息系统学科博士研究生专业 (42)
信号与信息处理学科博士研究生专业 (44) 信息获取与探测技术学科博士研究生专业 (46) 信息安全学科博士研究生专业 (48) 检测技术及自动化装置学科博士研究生专业 (50) 生物医学工程学科博士研究生专业 (52) 管理科学与工程学科博士研究生专业 (54) 新兴技术管理学科博士研究生专业 (56) 信息管理与电子商务学科博士研究生专业 (58) 金融工程学科博士研究生专业 (60) 企业管理学科博士研究生专业 (62) 信息与通信工程一级学科硕士研究生专业 (64) 电子科学与技术一级学科硕士研究生专业 (67) 材料科学与工程一级学科硕士研究生专业 (69) 数学一级学科硕士研究生专业 (71) 计算机科学与技术一级学科硕士研究生专业 (73) 区域经济学学科硕士研究生专业 (76) 金融学学科硕士研究生专业 (78) 数量经济学学科硕士研究生专业 (80) 宪法学与行政法学学科硕士研究生专业 (82) 国际政治学科硕士研究生专业 (84) 马克思主义基本原理学科硕士研究生专业 (86) 思想政治教育学科硕士研究生专业 (88)
算法设计与分析习题解答
第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn)
证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 图论第三次作业 一、第六章 2.证明： 根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者 子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明： 假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明： 设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.电子科大图论答案
- 电子科技大学研究生学位论文(含研究报告)撰写范例(中文)
- 电子科技大学考研复试经验
- 电子科技大学研究生学位授予实施细则
- 电子科技大学研究生联合培养专业实践计划表
- 电子科技大学研究生奖励管理办法
- 电子科技大学研究生试卷
- 电子科技大学在读研究生更换导师的规定
- 2020年电子科技大学考研招生简章
- 电子科技大学2015年推荐免试攻读硕士学位研究生推荐名单
- 电子科技大学2017-2018-1学期全日制研究生课表
- 电子科技大学研究生算法设计与分析拟考题及答案评分细则 (2)
- 电子科技大学研究生图论总结
- 电子科技大学硕士研究生培养方案
- 毕业感悟-(成都电子科技大学在读研究生)
- 电子科技大学研究生考试参考书目
- 电子科技大学导师给研究生的36条建议
- 电子科技大学研究生招生考生现实表现情况表
- 电子科技大学研究生算法设计与分析拟考题及答案评分细则 (1)
- 成电考研心得
- 电子科技大学硕士研究生培养方案