哈工大算法设计与分析-ch1ch2答案
2017年哈工大计算机科学与技术专业854考研真题
2016年哈工大计算机科学与技术专业854考研真题 I．数据结构 一、选择题 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 Int x = n * n; While (x >= 1) { X = x / 2; } A.O(log2n) B.O(n) C.O(nlog2n) D.O(n1/2) 2.需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线 性表存储结构是（）。 A.单向链表 B.静态链表 C.线性链表 D.顺序表 3.已知字符串S为”ababcabcacbab”，模式串T为”abcac”。若采用KMP算法进行模式匹配， 则需要（）遍（趟匹配），就能确定T是S的子串。 A. 3 B. 4 C. 5 D. 6 4.已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。 A.1,2,3,4 B.2,3,4,1 C.1,4,3,2 D.3,1,4,2 5.将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。 A.没有左子树 B.没有右子树 C.没有左子树和右子树 D.以上都不对 6.一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。 A. e B.2e C.n2-2e D.n2-e 7.在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。 A. 5 B.7 C.8 D.14
8.设待排序的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。 A.log2n B.n C.nlog2n D.n2 9.下面关于B树和B+树的叙述中，不正确的是（）。 A.B树和B+树都能有效地支持随机检索 B.B树和B+树都能有效地支持顺序检索 C.B树和B+树都是平衡的多路树 D.B树和B+树都可以用于文件的索引结构 10.若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最 少。 A.插入排序 B.快速排序 C.堆排序 D.选择排序 二、填空题 11.在一棵n个结点的二叉树中，所有结点的空子树个数为11 。 12.若二叉树的一个叶结点是其某子树的中序遍历序列中的第一个结点，则它必是该子树的 后序遍历序列中的第12 个结点。 13.在有n个选手参加的单循环赛中，总共将进行13 场比赛。 14.在有4033个叶子结点的完全二叉树中，叶子结点的个数为14 个。 15.一个有向图G1的反向图是将G1的所有有向边取反而得到的有向图G2，若G1和G2 的邻接矩阵分别为A，B，则A与B的关系为15 。 16.N个顶点e条边的无环路有向图，若采用邻接表作为存储结构，则拓扑排序算法的时间 复杂度为16 。 17.在10阶B树中根结点所包含的关键字最多有17 个，最少有18 个。 18.在具有12个结点的平衡二叉树（A VL树）中，查找A VL树中的一个关键字最多需要 （18）次比较。 19.对初态有序的表，最少时间的排序算法是（19）。 三、简答题 20.在n个数据中找出前K个最大元素，可以采用堆排序或败者树来实现。分别说明上述两 种实现方法的基础步骤，并分析每种方法的时间复杂度和空间复杂度。 21.假设举办一个1000人参加的学术会议，作为会议报道组的负责人，你会收到会务组为 每名参会者开具的包含其英文名字的注册费发票，同时还会收到为每位参会者提供的印有其英文名字的参会胸牌和其他会议资料。请回答以下问题： （1）如何有效地把每个参会者注册费发票和参会胸牌等其他会议资料放在一起形成一份参会资料？ （2）如何在会议报道日更有效地把每份资料发放给参会者？ 要求：说明你所使用的主要技术和相关步骤。 四、算法设计题 按以下要求设计算法： （1）描述算法设计的基本思想； （2）根据设计思想，采用C或C++或Java语言描述算法；
算法设计与分析试卷A及答案
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =
哈工大概率论与数理统计课后习题答案 一
·1· 习 题 一 1．写出下列随机试验的样本空间及下列事件中的样本点： （1）掷一颗骰子，记录出现的点数. A =‘出现奇数点’； （2）将一颗骰子掷两次，记录出现点数. A =‘两次点数之和为10’，B =‘第一次的点数，比第二次的点数大2’； （3）一个口袋中有5只外形完全相同的球，编号分别为1,2,3,4,5；从中同时取出3只球，观察其结果，A =‘球的最小号码为1’； （4）将,a b 两个球，随机地放入到甲、乙、丙三个盒子中去，观察放球情况，A =‘甲盒中至少有一球’； （5）记录在一段时间内，通过某桥的汽车流量，A =‘通过汽车不足5台’，B =‘通过的汽车不少于3台’。 解 （1）123456{,,,,,}S e e e e e e =其中i e =‘出现i 点’1,2,,6i = ， 135{,,}A e e e =。 （2）{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)S = (2,1),(2,2),(2,3),(2,4),(2,5),(2,6) (3,1),(3,2),(3,3),(3,4),(3,5),(3,6) (4,1),(4,2),(4,3),(4,4),(4,5),(4,6) (5,1),(5,2),(5,3),(5,4),(5,5),(5,6) (6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}； {(4,6),(5,5),(6,4)}A =； {(3,1),(4,2),(5,3),(6,4)}B =。 （3）{(1,2,3),(2,3,4),(3,4,5),(1,3,4),(1,4,5),(1,2,4),(1,2,5)S = (2,3,5),(2,4,5),(1,3,5)} {(1,2,3),(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,5)}A = （4）{(,,),(,,),(,,),(,,),(,,),(,,),S ab ab ab a b a b b a =--------- (,,),(,,,),(,,)}b a a b b a ---，其中‘-’表示空盒； {(,,),(,,),(,,),(,,),(,,)}A ab a b a b b a b a =------。 （5）{0,1,2,},{0,1,2,3,4},{3,4,}S A B === 。 2．设,,A B C 是随机试验E 的三个事件，试用,,A B C 表示下列事件： （1）仅A 发生； （2）,,A B C 中至少有两个发生；
(完整word版)哈工大深圳算法设计与分析试卷-师兄只能帮你到这啦(额外再加8道保命题)-何震宇
1、Using figure to illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG , SEA, RUG , ROW, MOB, BOX, TAB. 2、Please write inorder, preorder and postorder tree walks of the following binary search tree. 3、Please write down the elements of dynamic programming. 4、Using a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n/3)+T(2n/3)+cn. 5、Please give an optimal Huffman code for the following set of frequencies. Minimize 2172x x + Subject to 71=x 24321≥+x x 02≥x 03≤x
7、Solve the following linear program using SIMPLEX: maximize 215.1218x x + Subject to 2021≤+x x 121≤x 162≤x 0,21≥x x 8、Suppose A1 a 105? matrix, A2 a 310? matrix, A3 a 123? matrix, A4 a 512? matrix, A5 a 505? matrix, A6 a 650? matrix. Please give an optimal parenthesization of a matrix-chain A1A2A3A4A5A6. 9、Using a recursion tree to give an asymptotically tight solution to the recurrence T (n ) = T(n/4)+T(n/2)+ n 2. 10、Using figure to illustrate the operation of COUNTING-SORT on the array A=<6,0,2,0,1,3,4,6,1,3,2> 11、Using figure to illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG , SEA, RUG , ROW, MOB, BOX, TAB. 12、Please write inorder, preorder and postorder tree walks of the following binary search tree. 13、X=
算法设计与分析课程设计(完整版)
HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日
一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。
算法分析与设计习题集整理
算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题 #include 习 题 一 1．写出下列随机试验的样本空间及下列事件中的样本点： （1）掷一颗骰子，记录出现的点数. A =‘出现奇数点’； （2）将一颗骰子掷两次，记录出现点数. A =‘两次点数之和为10’，B =‘第一次的点数，比第二次的点数大2’； （3）一个口袋中有5只外形完全相同的球，编号分别为1,2,3,4,5；从中同时取出3只球，观察其结果，A =‘球的最小号码为1’； （4）将,a b 两个球，随机地放入到甲、乙、丙三个盒子中去，观察放球情况， A =‘甲盒中至少有一球’ ； （5）记录在一段时间内，通过某桥的汽车流量，A =‘通过汽车不足5台’， B =‘通过的汽车不少于3台’ 。 解 （1）123456{,,,,,}S e e e e e e =其中i e =‘出现i 点’1,2,,6i =L ， 135{,,}A e e e =。 （2）{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)S = (2,1),(2,2),(2,3),(2,4),(2,5),(2,6) (3,1),(3,2),(3,3),(3,4),(3,5),(3,6) (4,1),(4,2),(4,3),(4,4),(4,5),(4,6) (5,1),(5,2),(5,3),(5,4),(5,5),(5,6) (6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}； {(4,6),(5,5),(6,4)}A =； {(3,1),(4,2),(5,3),(6,4)}B =。 （3）{(1,2,3),(2,3,4),(3,4,5),(1,3,4),(1,4,5),(1,2,4),(1,2,5)S = (2,3,5),(2,4,5),(1,3,5)} {(1,2,3),(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,5)}A = （4）{(,,),(,,),(,,),(,,),(,,),(,,),S ab ab ab a b a b b a =--------- (,,),(,,,),(,,)}b a a b b a ---，其中‘-’表示空盒； {(,,),(,,),(,,),(,,),(,,)}A ab a b a b b a b a =------。 （5）{0,1,2,},{0,1,2,3,4},{3,4,}S A B ===L L 。 2．设,,A B C 是随机试验E 的三个事件，试用,,A B C 表示下列事件： （1）仅A 发生； （2）,,A B C 中至少有两个发生； n = 3 Backtrack(1) t=1 for i = 1 to 3 i=1 Swap(x[1], x[1]) t=1时，x[1]取了x[1]=1 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=2 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> t = 4 > 3 输出(1,2,3) swap(x[3],x[3]) swap(x[2],x[2]) i=3 swap(x[2],x[3]) x[2]=3, x[3]=2 t=2时，x[2]取了3 Backtrack(3) -------> t=3 for i = 3 to 3 swap(x[3],x[3]) t=2时，x[3]取了x[3]=2 Backtrack(4) ---> t = 4 > 3 输出(1,3,2) swap(x[3],x[3]) swap(x[2],x[3]) x[2]=2, x[3]=3 Swap(x[1], x[1]) i=2 Swap(x[1], x[2]) x[1]=2, x[2]=1 t=1时，x[1]取了2 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=1 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> 《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 实验一： 用FFT 作谱分析 实验目的： (1) 进一步加深DFT 算法原理和基本性质的理解(因为FFT 只是DFT 的一种快速算法， 所以FFT 的运算结果必然满足DFT 的基本性质)。 (2) 熟悉FFT 算法原理和FFT 子程序的应用。 (3) 学习用FFT 对连续信号和时域离散信号进行谱分析的方法，了解可能出现的分析误差及其原因，以便在实际中正确应用FFT 。 实验原理： DFT 的运算量： 一次完整的DFT 运算总共需要2N 次复数乘法和(1)N N -复数加法运算，因而 直接计算DFT 时，乘法次数和加法次数都和2N 成正比，当N 很大时，运算量很客观的。例如，当N=8时，DFT 运算需64位复数乘法，当N=1024时，DFT 运算需1048576次复数乘法。而N 的取值可能会很大，因而寻找运算量的途径是很必要的。 FFT 算法原理： 大多数减少离散傅里叶变换运算次数的方法都是基于nk N W 的对称性和周期 性。 （1）对称性 ()*()k N n kn kn N N N W W W --== （2）周期性 ()(mod`)()()kn N kn n N k n k N N N N N W W W W ++=== 由此可得 ()()/2 (/2)1 n N k N n k nk N N N N N k N k N N W W W W W W ---+?==?=-??=-? 这样： 1.利用第三个方程的这些特性，DFT 运算中有些项可以合并； 2.利用nk N W 的对称性和周期性，可以将长序列的DFT 分解为短序列的DFT 。 前面已经说过，DFT 的运算量是与2N 成正比的，所以N 越小对计算越有利， 因而小点数序列的DFT 比大点数序列的DFT 运算量要小。 快速傅里叶变换算法正是基于这样的基本思路而发展起来的，她的算法基本 上可分成两大类，即按时间抽取法和按频率抽取法。 我们最常用的是2M N =的情况，该情况下的变换成为基2快速傅里叶变换。 完成一次完整的FFT 计算总共需要 2log 2 N N 次复数乘法运算和2log N N 次复数加法运算。很明显，N 越大，FFT 的优点就越突出。 实验步骤 (1) 复习DFT 的定义、 性质和用DFT 作谱分析的有关内容。 (2) 复习FFT 算法原理与编程思想， 并对照DIT-FFT 运算流图和程序框图， 读懂本实验提供的FFT 子程序。 (3) 编制信号产生子程序， 产生以下典型信号供谱分析用： 一、选择题（多选） 1.算法必须满足哪些条件？ 算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足条件： (1)输入：有零个或多个由外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 2.哪些问题比较适合用递归算法？ 阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的递归算法）：（1）二分搜索技术、（2）大整数的乘法、（3）Strassen 矩阵乘法、（4）棋盘覆盖、（5）合并排序、（6）快速排序、（7）线性时间选择、（8）最接近点对问题、（9）循环赛日程表 3. 哪些问题比较适合用贪心算法？ （1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）单源最短路径（5）最小生成树（6）多机调度问题 4. 哪些问题比较适合用回溯法？ （1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题 二、概念题 1.递归的概念是什么？ 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。2.什么是0-1背包问题？ 给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。该问题被称为0-1背包问题。 3.什么是哈夫曼编码，它有什么优缺点？ 由哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼编码是广泛地用于数据文件压缩。用于数据的无损耗压缩。其压缩率通常在20%～90%之间。 优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。 4.什么是图的m着色问题？ 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2的顶点着有不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 5.什么是单源最短路径问题？ 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得0分，不同的重复率扣不同的分数。分组的意义在于研究与实践不同策略的不同题目的差异、不同策略里不同题目异同、相同题目不解法之间的异同与算法效率等。 所有实验都需要包含八个组成部分： （1）实验题目 要求：一句简要的话概括或抽象出所做的实验内容 （2）个人所承担的工作 要求：独立完成报告所有内容者仅填写独立完成即可，此种情况若发现报告有雷同者得0分。协作完成的，重点写自己完成的部分，其他部分可略写，为了锻炼同学们的设计与分析能力，原则上不允许算法模型、算法描述与分析、算法实现上相同。 （3）选题背景与意义 要求：描述选题的背景、针对该问题求解的算法有多少种，发展历史及研究价值等。 （4）问题描述 要求：可以实际问题的描述，也可以某类问题的抽像描述。如果是某类问题的抽象描述，需要指出它的应用场景。 （5）算法策略选择 要求：简要说出选择该策略的理由 （6）计算模型 要求：最接近程序实现中问题求解的数学模型。指明定义域和值的范围或解空间。可以有数据结构及推导或计算公式。递归模型至少有递推公式、递归的出口。如果有的话，给出必要的证明。 （7）算法描述与分析 要求：以标准的描述方式，如流程图、伪码、语言文字。对算法进行时间和空间复杂度分析。时间复杂度要求有必要的推导步骤。 （8）算法实现 要求：给出编程语言、开发环境。给出可执行的算法代码，提供必要的注释。 （9）调试分析记录 要求：软件开发调试过程中遇到的问题及解决过程；核心算法的运行时间和所需内存空间的 2011年数值分析1、设32 ()(5) f x x =- （1）应用newton迭代法解方程()0 f x= 并讨论 迭代公式的收敛速度 （2）改进导出的迭代公式以提高迭代的收敛阶，并用改进后的迭代 x0=1，要求迭代三步，结果保留4位小数） 2（1）求a及不超过二次多项式() p x使 23,01 () (),12 a x x x S x p x x ?++≤≤ =? ≤≤ ? ，具有 连续的二阶导数且满足(2)0 p=； （2）当() f x用满足条件(1)(1),(2)(2),'(1)'(1) f p f P f p ===的插值多项式 近似时求 2 1 () f x dx -? 3已知线性方程组 1 2 3 211 222 121 x a a x a x ?? ???? ?? ???? = ?? ???? ?? ???????? ?? （1）写出Jacobi迭代格式 （2）证明当4 a>时，该迭代格式收敛 （3）当a=5时，取0111 ,, 10510T x=（），求出2x（计算结果保留4位小数） 4 设f(x)=e x，在[0,1]上给出函数() f x的n+1个等距节点 i x函数表，若想用二次插值来计算f(x)的近似值。要求截断误差不超过10?6，问使用多大的函数表步长h。 5、给定求积公式2 0010()()()f x dx A f x f x ≈+? （1）求出待定参数001,,A x x ，使公式的代数精度尽可能高，并指出此 求积公式的代数精度是多少？ （2）用此求积公式计算积分2 40x dx ?。（计算结果保留4位小数） 6试用共轭梯度法求解线性方程组，初始值取x 0=()0,0,0T 123210113110143x x x -????????????--=??????????? ?-??????已知计算过程为cg 法 7已知数据点1(0,1)(1,0)(2,)(3,10)3 ，试利用反差商构造有理插值函数()R x 通过已知数据点. 8、方程组123343246353317x x x -????????????-=?????????????????? (1)试用Doolittle 分解方法求解方程组 (2)计算出系数矩阵A 按模最大特征值及对应的特征向量，初始向量为（1,0,0）T ，迭代两步，计算结果保留4位小数。 9利用四阶经典的Runge-Ktta 方法求解此初值问题'100(0)0y y y +=??=? （1）讨论步长h 应取何值方能保证方法的稳定性？ （2）取步长h=0.2，求0.2,0.4x =时的数值解，要求写出由,,n n h x y 直接计算的迭代公式（计算中结果保留小数点后4位） 10线性多步法1111113'8''228 n n n n n n h y y y y y y +-+-??=++++??及初始值01,y y 和步长h （1）确定方法中的局部截断误差主项，并指出方法的阶数 2013年哈工大计算机科学与技术专业854考研真题 I．数据结构部分 一、单项选择题 1.有一个100*90整型数的稀疏矩阵非0元素有10个，设每个整型数点2字节，则用三元 组表示该矩阵时，所需的字节数为（1）。 A.60 B.66 C.180 D.33 2.下列内部排序算法中，其比较次数与序列初始状态无关的是（2）。 A.快速排序 B.直接插入排序 C.二路归并 D.选择排序 3.若度数为m的哈夫曼树中，其叶子结点的个数为n，则非叶子结点的个数为（3）。 A.n-1 B.n/(m-1) C.(n-1)/(m-1) D.(n+1)/(m+1)-1 4.长度为12有序表，按折半查找法对该表进行查找，以等概率查找表内各元素，则查找 成功时所需要的平均比较次数为（4）。 A.35/12 B.36/12 C.39/12 D.43/12 5.设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要 进行（5）次探测。 A.K-1 B.K C.K+1 D.K(K+1)/2 6.有n个初始归并段，采用K路归并时，所需要的归并遍数是（6）。 A.log n k B.log2k C.log2n D.log k n 7.有n个顶点，e条边的有向图采用邻接存储，若删除与顶点V i相关的所有边，其时间复 杂度为（7）。 A.O(n) B.O(e) C.O(max(n, e)) D.O(n*e) 8.在平衡二叉树中插入一个结点造成不平衡，设最低的不平衡结点为A，并已知插入后A 的左子树根的平衡度为0，右子树根的平衡度为1，则应作（8）型的调整达到平衡。。 A.LL B.LR C.RL D.RR 9.一棵具有n个非叶子结点完全二叉树的线索树，含有多少条线索（9）。 A.2n+1或2n B.2n+2或2n+1 C.2n+1或2n-1 D.2n+2或2n-2 10.在某森林的二叉树表示中，结点M和结点N是同一父节点的左儿子和右儿子，则在该 森林中（10）。 A.M、N具有同一双亲 B.M、N可能没有共同祖先 C.M是N的儿子 D.M是N的左兄弟 二、填空题 11.高度为h的完全二叉树至少有（11）个结点。 12.N个结点的k叉树（k≥2）的k叉链表中有（12）空指针。 13.对具有n个元素的顺序存储的有序表和顺序存储的无序表进行顺序查找，在等概率的情 况下，查找不成功时的平均查找长度分别为（13-1）、（13-2）。 14.M阶B-树中，当有关键字插入导致相关结点分裂时，原结点上有（14）个关键字。 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在 叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 图 七桥问题 南区 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。 #include算法设计与分析第2版王红梅胡明习题答案
哈工大概率论与数理统计课后习题答案 一
算法设计与分析排列树递归推算
算法设计与分析习题
哈工大数字信号处理实验报告
算法设计与分析复习题
算法设计与分析：递归与分治法-实验报告
算法设计与分析报告 正文
哈工大2011年数值分析
2014年哈工大计算机科学与技术专业854考研真题
算法设计与分析习题答案1-6章
- 哈工大模式识别实验报告
- 哈工大2015计算机复试试题
- 哈工大模式识别课程期末总结分解
- 哈工大深圳算法设计与分析08年试卷-何震宇
- 哈尔滨工业大学课程设计报告
- 哈工大计算机科学与技术专业本科生培养方案
- 哈工大 C语言实验报告(答案)
- 哈工大2015计算机复试试题
- 算法设计与分析报告 正文
- 2019年哈尔滨工业大学854数据结构真题
- 哈工大计算机科学与技术专业本科生培养方案
- (完整版)哈工大深圳算法设计与分析08年试卷-何震宇
- (完整word版)哈工大深圳算法设计与分析试卷-师兄只能帮你到这啦(额外再加8道保命题)-何震宇
- 哈工大-计算机图形学-作业-圆弧的算法描述
- 2016年哈工大计算机科学与技术专业854考研真题
- 哈尔滨工业大学数据结构与算法历年考题汇总
- 哈工大深圳算法设计与分析试卷-师兄只能帮你到这啦(额外再加8道保命题)-何震宇
- 计算机科学与技术专业本科生培养方案-哈工大计算机学院
- 哈工大数字信号处理实验报告
- 哈工大人工智能原理习题homework-1