第1题
第2题
已知函数给定x的取值从0到1步长为J.1的数据点,用三次样条函数求该函数的导数,并且与理论结果进行比较。
第5题
不相交的子集A和B=V-A,并且这两个子集具有下列性质:
(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如,图8-34就是二部图。对V(G)的一个划分可能是A=(0,3,4,6)和B=(1,2,5,7).
(1)试编写一个算法,判断图G是否是二部图。如果图G是二部图,则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明:当用邻接表表示图G时,这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数,e是边数。
(2)证明:任何-棵树都是二部图
(3)证明:当且仅当图G不包含奇数条边的回路时.它是二部图。
第6题
第7题
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
第8题
算法设计:对于给定的n个正整数,设计一个算法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
第9题
第10题
算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.