哈工大深圳算法设计与分析08年试卷-何震宇
哈尔滨工业大学深圳研究生院 2008年 秋 季学期期末考试试卷
HIT Shenzhen Graduate School Examination Paper
Course Name: Lecturer:
Question One Two Three Four Five Six Seven Eight Nine Ten Total Mark
General directions :
This exam is closed book . You may not use the text book, your notes, computer, or any other materials during the exam.
No credit will be given for questions left unanswered, so you should be sure to answer all questions, even if you are only taking your best guess.
Write your answer to each question or problem in the paper provided. If necessary, extra sheets will be provided. Make sure your name is written on all of these pages.
Please be sure to write neatly and answer all questions unambiguously. This exam has a total of _100_ points, and you have 120 minutes.
Time : 09:00-11:00, Monday, Dec. 8, 2008
错误！未找到引用源。 Single choice [10 points]
1、Which of the following sorting algorithms is not stable? ( B ) (A) Insertion sort (B) Quick sort (C) Merge sort (D) Bubble sort
2、We say that ()f n is asymptotically larger than ()g n if ( D ). (A) ()()()f n O g n = (B) ()()()f n g n =Ω (C) ()()()f n o g n = (D) ()()()f n g n ω=
3、An order-statistic tree is an augmented red-black tree. In addition to its usual fields, each node x has a field
size[x], which is the number of nodes in the subtree rooted at x , For an order-statistic tree with n nodes, the time for insertion, deletion and maintenance of the size field are ( A ) (A) (lg )O n (lg )O n (lg )O n
(B) (lg )O n (lg )O n (lg )O n n (C) (lg )O n (lg )O n
(1)O
(D) (lg )O n
(lg )O n n ()O n
4、There ’s a B-tree whose minimum degree is t, every node other than the root must have at least __ keys, at most __ keys, every internal node other than the root has at least __ children ( D ). (A) t-1 2t t (B) t-1 2t-1 t (C) t 2t t+1 (D) t-1 2t+1 t
5、Which of the following statements about P, NP,NPC is correct? ( C ) (A) P = NP , NPC ? NP (B) P ?NP , NPC ? P (C) P ?NP , NPC ?NP (D) P = NPC , P ? NP
错误！未找到引用源。 short answer [30 points]
6、Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing with the primary hash function h1(k) = k mod m. Illustrate the result of inserting these keys using linear probing, using quadratic probing with c1 = 1 and c2 = 3. The final results are required to be expressed as charts. [6 points] 0 1 2 3 4 5 6 7 8 9 10 22 88 4 15 28 17 59 31 10
7、Use the arithmetic expression ((a+b)+c*(d+e)+f)*(g+h) to construct a binary tree. [6 points]
8、Explain how to implement two stacks in one array A [1 .. n ] in such a way that neither stack overflows unless the total number of elements in both stacks together is n . The PUSH and POP operations should run in O (1) time. [6 points]
Student Name: Student ID: Major:
答题内容写在边线外视为无效
9、Tell the difference between dynamic programming and greedy programming. [6 points]
10、We are given a directed graph G=(V, E) on which each edge (u, v)∈E has an associated value r(u, v), which is a real number in the range 0 ≤r(u, v) ≤1 that represents the failure rate of a communication channel from vertex u to vertex v. We assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices. [6 points]
错误！未找到引用源。[60 points]
11、Consider the searching problem:
?Input: A sequence of n numbers A = 〈a1, a2, . . . , a n〉and a value v.
?Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
[10 points] 12、Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 - α)n) + cn, where α is a constant in the range 0 <α < 1 and c > 0 is also a constant. [12 points]
13、A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK, and the red-black is a nearly balanced tree. [13 points]
1) A binary search tree is a red-black tree if it satisfies the following red-black properties:
1.Every node is either red or black.
2.The root is black.
3.Every leaf (NIL) is black.
4.(1)
5.(2)
Please give the missing property 4 and property 5. [2 points]
2)What is the largest possible number of internal nodes in a red-black tree with black-height k? What is the smallest possible number? [3 points]
3) There is the RBT insertion pseudo-code ,which insert a given node z into a RBT T. Suppose you can use LEFT-ROTATE(T, z) and RIGHT-ROTATE(T, z) operation directly ,Please fill the blank! [8 points]
RB-INSERT(T, z)
1 y← nil[T]
2 x← root[T]
3 while x≠ nil[T]
4 do y← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else (1)
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then(2)
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 (3)
17 RB-INSERT-FIXUP(T, z)
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then(4) ? Case 1
6 (5) ? Case 1
7 (6) ? Case 1
8 z ← p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 (7) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 (8) ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
15 else (same as then clause with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
14、Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 10, 3, 12, 5, 50, 6 >. [10 points] 15、A full k-tree with the depth L has the following properties: All the nodes on the L th layer are leaves; Every node on other layers has k non-empty subtrees. If we number all the nodes from the first layer to the L th layer and from left to right with 1,2,3..., please answer the following questions: [15 points]
1) How many nodes does the i th layer have? [3 points]
2)What is the number of the parent of node n, if it exists. [4 points]
3)What is the number of the i th child from left of node n, if it exists. [4 points]
4) In what condition does node n have a right brother? If it has, what is the number of its right brother? [4 points]
(完整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=
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 =
哈尔滨工业大学深圳研究生院
哈尔滨工业大学深圳研究生院 2015年硕士研究生入学考试复试及录取工作办法 哈工大深研院发[2015]2号根据《2015年全国硕士研究生招生工作管理规定》（教学[2014]13号）以及《哈尔滨工业大学2015年硕士研究生入学考试复试及录取工作办法》（研院发[2015]6号），结合深圳研究生院今年硕士研究生招生工作的实际情况，现确定深圳研究生院2015年硕士研究生入学考试复试及录取工作办法如下。 一、工作原则 坚持对考生进行德智体全面衡量，择优录取、保证质量、宁缺毋滥；在保证人才培养质量的前提下，既尊重考生的意愿，又兼顾国家、国防建设需求和学科建设工作的需要。 复试工作要做到全面考察，有所侧重，在德智体等各方面全面衡量的基础上，突出对专业知识、科研能力、创新精神和综合素质等方面的考核。复试过程要政策透明、程序规范、操作公开、监督机制健全，要提高服务意识、维护考生的合法权益。 二、工作组织 复试及录取工作的具体组织由研究生院负责，监督工作由校监察处负责。 根据教育部文件精神和校本部相关要求，深圳研究生院组成复试及录取工作领导小组，并设立复试及录取工作督察小组，公布督察电话，如下：复试及录取工作领导小组名单： 组长：张敏 副组长：俞晓国 组员：王轩、张钦宇、李兵、金文标、王耀武、李明雨、赵毅 复试及录取工作督察小组名单： 组长：姚英学 组员：张雁、李琳、于刚 三、录取规模 2015年深圳研究生院硕士统考生招生规模（不含推免生数）
四、复试工作 1．复试基本线
注：（1）工程硕士[0852]相应领域的学校复试基本线与相对应学科的工学复试基本线一致（2）“少数民族高层次骨干人才计划”类别考生的复试基本线由教育部统一划定 2．复试准备 （1）复试资格线的确定 深圳研究生院各学科复试资格线按校本部各院（系）该学科的复试资格线要求，具体见校本部各院（系）复试方案。 参加复试的考生名单由校本部各相关院（系）统一公布.cn，同时可查询深圳研究生院学生发展处（部）网站招生公告栏.cn/。 （2）复试资格审查 复试前必须对考生进行资格审查，资格审查不合格者不予复试。审查条件以我校2015年硕士研究生招生简章的规定为准，除审查准考证和有效身份证件外，非应届本科生需提交学历证书、学位证书、《教育部学历证书电子注册备案表》或《中国高等教育学历认证报告》；应届本科生需提交学生证、《教育部学籍在线验证报告》，其毕业证书及学士学位证书将在入学时提交审查。考生可登陆中国高等教育学生信息网（https://www.docsj.com/doc/e912383046.html,），按要求进行学历或学籍认证（认证办法见附件1）。复试阶段未提交学历或学籍认证的考生，应在录取结束后的规定时间内提交，否则将视为资格审核不合格。资格审查由深圳研究生院负责录取工作的教师会同校本部有关老师共同完成，具体时间、地点见校本部相关院（系）通知。复试资格审查表（见附件2）须由审查人和深圳研究生院各学科招生负责人共同签字，研究生院将对资格审查结果进行检查。如考生提供
算法设计与分析课程设计(完整版)
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 情况。
哈尔滨工业大学深圳研究生院
哈尔滨工业大学深圳研究生院 F楼国际报告厅音响系统改造招标文件 目录 1.1投标人资格要求 (1) 1.2合同主要条款 (1) 1.3招标项目要求 (2) 1.3.1项目背景与功能要求。 (2) 1.3.2设备技术指标 (2) 12、本项目不设投标保证金。 (4) 1.4开标和评标 (4) 1.4.1 开标 (4) 1.4.2 对投标文件响应性的确定 (4) 1.4.3 询标及投标文件的澄清 (5) 1.5评标原则和方法 (5) 1.5.1 评标原则 (5) 1.5.2标程序及方法 (6) 1.6授予合同 (7) 1.6.1定标 (7) 1.6.2中标通知 (7) 1.6.3授予合同时变更数量的权力 (8) 1.6.4签订合同 (8)
1.1 投标人资格要求 投标人应属于在中华人民共和国境内注册的企业法人： 1．投标人的企业注册资金以及注册年限要求：注册资本200万元人民币以上，注册时间必须超过1年； 2．投标人必须是独立法人，具备独立承担民事责任的能力和良好诚信的专业公司； 3．投标人的注册地点要求：深圳市或在深圳市内设有办事处； 4．投标人的资质及许可证要求：具有合法经营地址、经营范围； 5．投标人应遵守中华人民共和国相关法律、规章条例、行业规范要求； 6.须是在深圳市政府网注册的供应商； 1.2 合同主要条款 1、供货时间：所有设备及配套工程必须在合同签订后15天内全部交付使用。 2、要求供应商能按招标文件要求送货到招标人指定地点并按要求安装、调试，使设备达到 最佳使用状态。 3、付款方式：分期付款。 1）合同签订后3工作日内支付合同总价70%的预付款 2）设备及工程安装、调试并验收合格后5工作日内支付30%的余款。 4、售后服务最低要求： 1）保修期：保修期二年（免人工配件等费用）,保修其满终身维修（提供原厂配件，价格不高于市场价）。 2）提供上门维修服务，10分钟响应，40分钟到达现场。 5、培训最低要求： 1）投标人必须提供优质的培训服务。 2）培训地点：本项目使用单位内。 3）培训内容：能确保用户能够对设备有足够的了解和熟悉，并能独立进行设备的日常运行、维护和管理。 以上为最低要求，否则招标人将拒绝其投标。投标人的响应将作为评标的依据。
算法设计与分析第2版王红梅胡明习题答案
算法设计与分析(第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 实验一： 用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.什么是单源最短路径问题？ Machine Learning Question one: （举一个例子，比如:导航仪、西洋跳棋） Question two: Initilize: G={?,?,?,?,?,?} S={,,,,,} Step 1: G={?,?,?,?,?,?} S={sunny,warm,normal,strong,warm,same} Step2: coming one positive instance 2 G={?,?,?,?,?,?} S={sunny,warm,?,strong,warm,same} Step3: coming one negative instance 3 G= 2019年哈工大哈尔滨工业大学（深圳）考研复试时间复试内容复试 流程复试资料及经验 随着考研大军不断壮大，每年毕业的研究生也越来越多，竞争也越来越大。对于准备复试的同学来说，其实还有很多小问题并不了解，例如复试考什么？复试怎么考？复试考察的是什么？复试什么时间？复试如何准备等等。今天启道小编给大家整理了复试相关内容，让大家了解复试，减少一点对于复试的未知感以及恐惧感。准备复试的小伙伴们一定要认真阅读，对你的复试很有帮助啊！ 学院简介 哈尔滨工业大学(深圳)由哈工大与深圳市政府合作共建，是哈工大的一个校区，是广东省、深圳市的一所大学。哈工大(深圳)以全日制本科生与研究生教育为主、非全日制教育为辅，是首所进驻深圳招收本科生的中国九校联盟(C9)成员、国家“985工程”建设高校和“双一流”建设A类高校。哈工大(深圳)的前身是始建于2002年的哈工大深圳研究生院。 哈尔滨工业大学始建于1920年，隶属于工业和信息化部，是一所以理工为主，理、工、管、文、经、法等多学科协调发展的国家重点大学，是中国九校联盟(C9)成员，2017年入选“双一流”建设A类高校名单。在长期的办学过程中，哈工大坚持立德树人根本使命，坚持师德师风第一标准，形成了“规格严格，功夫到家”的校训，培育了精神引领、典型引路、品牌带动的思想政治工作传统，涌现出一大批全国先进典型。 复试时间 复试内容（科目） 一、全日制招生学科目录 注：上表学科代码栏内标注“*”的学科为工程硕士。 二、非全日制招生学科目录 说明： 1.此招生计划仅供参考，具体以国家批准招生计划数为准。 2.各专业只招英语考生。各专业考试科目与哈工大校本部全日制招生目录中对应专业的考试科目相同。 3.交通运输工程、外国语言文学学科须在校本部报到入学并完成第一学年的课程学习，第二学年由校本部转往深圳校区报到并进行硕士课题研究工作。 4.0830环境科学与工程专业研究生期间，50%研究生从事水污染控制研究方向，50%研究生从事大气污染控制研究方向。0830环境科学与工程、0814 土木工程：32市政工程方向和085229环境工程专业，欢迎生物科学、生物技术、生态学、化学、应用化学、化学工程与工艺、材料化学、高分子材料与工程、材料科学与工程等专业考生跨专业报考。跨专业考生初试考试科目与所报考专业一致，复试按校本部的要求进行。 5.0801力学(31固体力学、工程力学;32流体力学)考试科目同001航天学院的0801力学。 实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得0分，不同的重复率扣不同的分数。分组的意义在于研究与实践不同策略的不同题目的差异、不同策略里不同题目异同、相同题目不解法之间的异同与算法效率等。 所有实验都需要包含八个组成部分： （1）实验题目 要求：一句简要的话概括或抽象出所做的实验内容 （2）个人所承担的工作 要求：独立完成报告所有内容者仅填写独立完成即可，此种情况若发现报告有雷同者得0分。协作完成的，重点写自己完成的部分，其他部分可略写，为了锻炼同学们的设计与分析能力，原则上不允许算法模型、算法描述与分析、算法实现上相同。 （3）选题背景与意义 要求：描述选题的背景、针对该问题求解的算法有多少种，发展历史及研究价值等。 （4）问题描述 要求：可以实际问题的描述，也可以某类问题的抽像描述。如果是某类问题的抽象描述，需要指出它的应用场景。 （5）算法策略选择 要求：简要说出选择该策略的理由 （6）计算模型 要求：最接近程序实现中问题求解的数学模型。指明定义域和值的范围或解空间。可以有数据结构及推导或计算公式。递归模型至少有递推公式、递归的出口。如果有的话，给出必要的证明。 （7）算法描述与分析 要求：以标准的描述方式，如流程图、伪码、语言文字。对算法进行时间和空间复杂度分析。时间复杂度要求有必要的推导步骤。 （8）算法实现 要求：给出编程语言、开发环境。给出可执行的算法代码，提供必要的注释。 （9）调试分析记录 要求：软件开发调试过程中遇到的问题及解决过程；核心算法的运行时间和所需内存空间的 2018年度广东省科学技术奖公示表 （自然科学奖） 项目名称非饱和土状态相关本构关系及应用 主要完成单位广州市香港科大霍英东研究院哈尔滨工业大学(深圳) 主要完成人（职称、完成单位、工作单位）吴宏伟(教授、广州市香港科大霍英东研究院、广州市香港科大霍英东研究院；他是总体学术思想和研究方案的提出者，也是支持本项目所有科研资金的主要负责人，领导研究人员开展实验和理论研究。他是本项目10篇代表性论文的作者，并是其中8篇的第一作者） 陈锐（副教授、哈尔滨工业大学(深圳)、哈尔滨工业大学(深圳)；陈锐博士和吴洪伟教授共同研发了一系列非饱和土吸力测量仪器，包括新型土体吸力传感器和现场土壤水势测量仪等，也提出了全天候毛细阻滞覆盖系统，获得美国发明专利，他是其中1篇的通讯作者） 周超（讲师、广州市香港科大霍英东研究院、广州市香港科大霍英东研究院；周超博士和吴宏伟教授建立了应力状态土水特征曲线理论模型。本项目的10篇代表性论文里，他是其中2篇的第一作者/通讯作者） 项目简介本项目属土木工程的环境岩土工程领域。 非饱和土是固、液、气三相介质组成的多孔碎散材料，广泛存在于地表土层中，是所有自然边坡和人工构筑物的承载体。加深对非饱和土认知，是人类生存发展的永恒课题。非饱和土状态及力学行为随自然大气环境和地下水位的变化而变化，特别是21世纪以来极端气候条件频发和人类活动导致地下水位变幅大，非饱和土相关的灾害时有发生。Fredlund教授于1993年基于土壤学和弹性力学相关理论建立了经典非饱和土力学理论体系，其中持水本构关系忽略了土体应力状态的影响，应力-应变本构关系难以描述土体水分和应变状态相关的弹塑性力学行为，难以满足21世纪对垃圾填埋场覆盖系统、自然边坡、高铁路基等重大基础设施服役性能精准控制的要求。建立状态相关的非饱和土弹塑性本构理论是本学科国际前沿的科学难题。本项目经十几年探索与研究，取得如下原创性科学成果： (1) 发现了应力增加的最重要影响是改变土体孔隙分布，对持水性质起主导作用，建立了应力状态相关的持水本构关系，通过自主研发的应力控制压力板仪在国际上率先验证了应力提高土体持水能力，突破了基于土壤学的持水曲线忽略应力状态效应的局限性。 (2) 建立了吸力路径相关的各向异性小应变模量计算公式，通过弯曲元系统在国际上首次验证了干湿循环作用下土体孔隙水重分布，导致小应变模量的各向异性和吸力路径相关性，为干湿循环条件下非饱和的变形计算提供精确的方法。 (3) 发现了吸力影响土体结构和大应变剪胀（缩）的规律，推导了吸力状态相关的大应变剪胀（缩）本构关系，利用自主研发的双室高精度体变测量系统在国际上率先验证了吸力增加土体剪胀势，突破了经典非饱和土应力-应变本构关系忽略吸力状态效应的局限性。 基于以上三点重要科学发现，建立了状态相关非饱和土弹塑性本构模型，并基于本项目发明的一系列非饱和土测试仪器提出了简单可靠的本构模型参数标定方法，形成了状态相关的非饱和土力学理论体系，出版了《Advanced Unsaturated Soil Mechanics and Engineering》英文专著。 本项目在国际权威期刊上共发表SCI论文100余篇，他引5000多次。10篇代表性论文均发表在本学科公认顶级国际期刊，SCI他引300多次。研究成果获加拿大岩土工程协会颁发的大中华地区首个优秀论文奖等国内外科研奖励。中/美/加/英等国科学院 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）个关键字。 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，x n-1） 设方程组为： 2019年哈尔滨工业大学(深圳)招生计划录取人数及招生专业目录(文科理科) 哈尔滨工业大学(深圳)招生计划录取人数及招生专业目录(文科理科) 2019年哈尔滨工业大学(深圳)招生计划录取人数及招生专业目录(文科理科) 选择可以说在很大程度上影响着考生后半生的生活方向和轨迹，很多考生因为高考填志愿时没有足够重视，要么浪费了不少分数；要么学了不喜欢的专业，在大学里感觉“痛不欲生”。 俗话说“七分考，三分报”，正是说明志愿填报的重要性。那么如何填报志愿，填报志愿时选大学应主要考虑哪些指标？其中一个重要指标就是大学招生计划人数和招生专业。今日将带你一起了解关于哈尔滨工业大学(深圳)招生计划和招生人数、哈尔滨工业大学(深圳)招生专业目录等相关知识。 注：2019年哈尔滨工业大学(深圳)招生专业和招生计划人数截至发稿前官方暂未公布，所以小编先整理了2018年哈尔滨工业大学(深圳)的招生计划专业的信息。考生务必以官方发布的信息为准，本文只作参考！ 2018年哈尔滨工业大学(深圳)招生计划人数和招生专业哈工大（深圳）宣（向碧霞、赵影/文黄衎/图）3月20日，在2018年 本科招生宣传人员第三次培训会上，校区正式公布了2018年本科招生人数、省份、专业。哈工大校长助理、校区常务副校长甄良，校区相关工作负责人姚英学、刘红军、韩喜双、周超英、张素梅、孙秀冬出席会议，学生发展处（部）处长俞晓国介绍招生政策，各省招生宣传工作负责人及工作人员共百余人参加了培训会。 2018年校区本科招生总数将增加至700人。本科招生省份在去年原有的16个（广东、湖南、江西、安徽、福建、浙江、广西、河北、辽宁、吉林、黑龙江、四川、重庆、湖北、贵州、云南）基础上，增加江苏省和海南省，达到18个。本科招生专业在去年原有的8个（机械类、计算机类、电子信息类、土木类、材料类、经济学类、环境科学与工程类、自动化类）基础上，增加电气类和建筑类，达到10个。 据悉，2016年，校区首次招收本科生，在12个省市招收6大类专业本科生共376名，在11个省份录取提档线超过一本线80分，8个省份的录取提档线超过一本线100分。2017年，校区在16个省份录取8大类专业优秀本科生558人，在13个省份的录取分数超过一本线100分，9个省份超过一本线120分，3个省份超过一本线150分，其中最高为黑龙江省，超过一本线158分。哈工大数字信号处理实验报告
算法设计与分析复习题
哈工大深圳机器学习复习4_丁宇新
2019年哈工大哈尔滨工业大学(深圳)考研复试时间复试内容复试流程复试资料及经验
算法设计与分析报告 正文
非饱和土状态相关本构关系及应用-哈尔滨工业大学深圳
2014年哈工大计算机科学与技术专业854考研真题
算法设计与分析(详细解析(含源代码))
哈尔滨工业大学(深圳)招生计划录取人数及招生专业目录(文科理科).doc
- 哈工大数字信号处理实验报告
- 哈工大人工智能原理习题homework-1
- 哈工大深圳算法设计与分析08年试卷-何震宇(可编辑修改word版)
- 哈工大2015计算机复试试题
- 2017年哈工大计算机科学与技术专业854考研真题
- 哈工大算法设计与分析ch4课件
- 论计算思维 哈工大计算机作业
- 2017年哈工大计算机科学与技术专业854考研真题
- 哈工大算法设计与分析ch课件
- 算法设计与分析大作业答案
- 哈工大数据结构课件第一章
- 哈工大模式识别课程总复习资料
- 哈工大算法设计与分析-ch1ch2答案
- 哈工大算法课件
- 《算法设计与分析》历年期末试题整理(含答案)
- 2017年哈工大计算机科学与技术专业854考研真题
- 2014年哈工大计算机科学与技术专业854考研真题
- 数据结构知识点总结(哈工大)
- 哈工大模式识别实验报告
- 哈工大2015计算机复试试题