哈工大深圳算法设计与分析08年试卷答案-何震宇
08算法答案 1、B
2、D
3、A
4、B
5、C
6、
Linear probing Quadratic probing
7、
8、Two stacks can be implemented in a single array without overflows occurring if
they grow from each end and towards the middle.
* + +
g
h
f
+ + *
a
b +
c d
e
9、The elements of dynamic programming: optimal substructure, overlapping sub-problems
The elements of greedy programming: optimal substructure, greedy choice property
They share the optimal substructure property, but we may not use dynamic programming when a greedy solution suffices, or reverse.
The greedy choice property is that a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. We must prove that a greedy choice at each step yields a globally optimal solution. First consider a globally optimal solution, and then modify the optimal solution, to make it to begin as a greedy choice.
10、Any minimum spanning tree algorithm is OK.
11、Searching(A)
for i 1 to length(A)
do
if A[i] = v
return i
return NIL
Loop invariant proof:
Initialization:
Loop invariant holds before the first loop iteration. Now i=1, if A[i] = v, then we return the index 1, if A[i]! = v, then until now we are sure that there is no v in the array!
Maintenance:
Each iteration maintains the loop invariant. The for loop compare v to the current array element A[i], to make sure there is no v in A[1…i-1], if A[i] = v, then we return the index i.
Termination:
If there is an element matched, the index is returned from early detect, or the program will return a NIL if we come to the end. So the loop invariant holds.
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
Because α is uncertain ,there is three situations:
a. 0 < α < 1/2
b. α = 1/2
c. 1 > α > 1/2
The value of α will influence the height of the recursion tree ,but the final answer is the same, so we just consider α = 1/2 here. From the recursion tree, we can calculate :
T(n) =(log 1
n α-+?
???)*cn
=Θ(log n n α-) =Θ（lg n n ）
13、 1）
4.If a node is red, then both its children are black.
5.For each node, all paths from the node to descendant leaves contain the same number of black nodes.
2）
Consider a red-black tree with black-height k. If every node is black the total number of internal nodes is 2k - 1. If only every other nodes is black we can construct a tree with 22k - 1 nodes.
3）
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 x ← right [x ]
8 p [z ] ← y
9 if y = nil [T ]
10 then root [T ] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
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 color[p[z]] ← BLACK? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z←p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z←p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? 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、
The final result is ((A1A2)((A3A4)(A5A6))) (Detailed process is omit here).
15、
1）k h-1
2）suppose the parent is i, if the student can give “(i-1)k+2<=n<=ik+1” , take it right
3)(n-1)*k+1+i
4) If it has a right brother, than it must not be the first child from right of its parent, which is (n-1)%k!=0, the number of its right brother is n+1
(完整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语言描述算法；
哈尔滨工业大学深圳研究生院
哈尔滨工业大学深圳研究生院 2015年硕士研究生入学考试复试及录取工作办法 哈工大深研院发[2015]2号根据《2015年全国硕士研究生招生工作管理规定》（教学[2014]13号）以及《哈尔滨工业大学2015年硕士研究生入学考试复试及录取工作办法》（研院发[2015]6号），结合深圳研究生院今年硕士研究生招生工作的实际情况，现确定深圳研究生院2015年硕士研究生入学考试复试及录取工作办法如下。 一、工作原则 坚持对考生进行德智体全面衡量，择优录取、保证质量、宁缺毋滥；在保证人才培养质量的前提下，既尊重考生的意愿，又兼顾国家、国防建设需求和学科建设工作的需要。 复试工作要做到全面考察，有所侧重，在德智体等各方面全面衡量的基础上，突出对专业知识、科研能力、创新精神和综合素质等方面的考核。复试过程要政策透明、程序规范、操作公开、监督机制健全，要提高服务意识、维护考生的合法权益。 二、工作组织 复试及录取工作的具体组织由研究生院负责，监督工作由校监察处负责。 根据教育部文件精神和校本部相关要求，深圳研究生院组成复试及录取工作领导小组，并设立复试及录取工作督察小组，公布督察电话，如下：复试及录取工作领导小组名单： 组长：张敏 副组长：俞晓国 组员：王轩、张钦宇、李兵、金文标、王耀武、李明雨、赵毅 复试及录取工作督察小组名单： 组长：姚英学 组员：张雁、李琳、于刚 三、录取规模 2015年深圳研究生院硕士统考生招生规模（不含推免生数）
四、复试工作 1．复试基本线
注：（1）工程硕士[0852]相应领域的学校复试基本线与相对应学科的工学复试基本线一致（2）“少数民族高层次骨干人才计划”类别考生的复试基本线由教育部统一划定 2．复试准备 （1）复试资格线的确定 深圳研究生院各学科复试资格线按校本部各院（系）该学科的复试资格线要求，具体见校本部各院（系）复试方案。 参加复试的考生名单由校本部各相关院（系）统一公布.cn，同时可查询深圳研究生院学生发展处（部）网站招生公告栏.cn/。 （2）复试资格审查 复试前必须对考生进行资格审查，资格审查不合格者不予复试。审查条件以我校2015年硕士研究生招生简章的规定为准，除审查准考证和有效身份证件外，非应届本科生需提交学历证书、学位证书、《教育部学历证书电子注册备案表》或《中国高等教育学历认证报告》；应届本科生需提交学生证、《教育部学籍在线验证报告》，其毕业证书及学士学位证书将在入学时提交审查。考生可登陆中国高等教育学生信息网（https://www.sodocs.net/doc/494918807.html,），按要求进行学历或学籍认证（认证办法见附件1）。复试阶段未提交学历或学籍认证的考生，应在录取结束后的规定时间内提交，否则将视为资格审核不合格。资格审查由深圳研究生院负责录取工作的教师会同校本部有关老师共同完成，具体时间、地点见校本部相关院（系）通知。复试资格审查表（见附件2）须由审查人和深圳研究生院各学科招生负责人共同签字，研究生院将对资格审查结果进行检查。如考生提供
哈尔滨工业大学深圳研究生院
哈尔滨工业大学深圳研究生院 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）培训内容：能确保用户能够对设备有足够的了解和熟悉，并能独立进行设备的日常运行、维护和管理。 以上为最低要求，否则招标人将拒绝其投标。投标人的响应将作为评标的依据。
哈工大深圳机器学习复习4_丁宇新
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年哈工大哈尔滨工业大学(深圳)考研复试时间复试内容复试流程复试资料及经验
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力学。
哈工大数字信号处理实验报告
实验一： 用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) 编制信号产生子程序， 产生以下典型信号供谱分析用：
算法设计与分析报告 正文
实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得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多次。研究成果获加拿大岩土工程协会颁发的大中华地区首个优秀论文奖等国内外科研奖励。中/美/加/英等国科学院
哈工大 国家级精品课《数据结构与算法》
第四章 树与二元树 填空题 1.假定一棵树的广义表表示为A(B(E)，C(F(H，I，J)，G)，D)，则该树的度为 ① ，树 高度为 ② ，终端结点的个数为 ③ ，单分支节点的个数为 ④ ，双分支结点的个数为 ⑤ ，三分支结点的个数为 ⑥ ，C结点的双亲结点为 ⑦ ，其孩子结点 ⑧ 和 ⑨ 结。该树先根、中根和后根遍历序列分别为 ⑽ 、⑾ 和⑿。该树对应的 二元树为 ⒀ ，此二元树的先根、中根和后根遍历顺序序列分别为⒁、⒂和⒃。 2.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 ① ， 该最优二元树共有 ② 个结点，度数为0、1、2的结点的个数分别为③ ，④ 和 ⑤ 个。 3.已知字符集{A、B、C、D、E} 的字符出现的概率分别为{ 3/25 ，9/25，6/25，2/25， 5/25}。画出该字符集的Huffman编码树② ， 字符A、B、C、D、E的编码分别为 ③， ④ ，⑤ ，⑥ ，⑦ ，该字符集的Huffman编码的平均编码长度为⑧ 。若采用二进制 等长编码方案，该字符集的编码长度为 ⑨ 。读该字符集而言，Huffman编码比等长编码平均压缩了 ⑽ %。 4.对于一棵具有n个结点的二元树，当进行链接存储时，其左右链存储结构中的指针域的 总数为 ①个，其中，② 个用于链接孩子结点， ③个空闲着。 5.在一棵二叉树中，度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个 数为n2，则有n0= ① 。 6.由a，b，c 三个结点构成的二叉树，共有 ① 种不同结构。 7.一棵高度为K的完全二叉树的结点总数最少为 ① 个，最多为 ② 个；第K层最多有 ③ 个结点，最少有 ④ 个结点。 选择题 8.假定在一棵二元树中，双分支结点数为15，单分支结点数为30，则叶子结点数为( ) 个。 A．15 B．16 C．17 D．47 9.在一棵二叉树上第5层的结点数最多为( ) 。 A．8 B．16 C．15 D．32 10.用顺序存储的方式将完全二叉树中的所有结点逐层存放在数组R[ 1…n]中，结点R[i] 若有子树，则左子树是结点( )。
2014年哈工大计算机科学与技术专业854考研真题
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 4. /*升序创建两个含有整形数据的链表，其中Create函数中调用Insert函数实现升序排列。再通过Combine函数将两个链表合并，用Print函数输出。代码如下。*/ #include "stdafx.h" #include
node *head,*n; int a ; head=NULL; cout<<"升序插入法产生链表，请输入数据（-1结束）：\n"; for(cin>>a;a!=-1;cin>>a) { n=new node; n->data=a; head=Insert(head,n);} return head; } void Print( node *head) { cout<<"链表的结点数据（升序）为：\n"; while(head) { cout<
哈工大优化算法复习重点
Taylor series of a function with multiple variables is: [] ))(()(2 1 )()()()(2k k T k k T k k X X X f X X X X X f X f X f -?-+ -?+≈ Extremum conditions: i)()0*=?X f and () *2X f ?positive definite →Minimum ii)()0*=?X f and () *2X f ?negative definite →Maximum iii)()0*=?X f and () *2X f ?indefinite →Not a Extremum The algorithm of the GSM: 1.initial point X0, initial step h and the convergence accuracy ?are given; 2. Determine Initial search interval [a,b]; 3.The interpolation points are generated by GSM, the function values are also computed: X1 = a + 0.382(b-a) f1 = f (X1) X2 = a + 0.618(b-a) f2 = f (X2) 4. Compare f1 and f2 to determine the new interval: a) if f1
算法设计大作业 哈工大 王宏志
算法设计大作业 软件学院软件2班 1093710219 周宇 一、 1.1 解 递推求解如下： A(n) = 3A(n/2) + n = 32 A(n/22)+3(n/2) + n = 33 A(n/23)+32(n/22)+3(n/2) + n …… =3k A(n/2k)+3i(n/2i) 设 n= 2k k=log2n 有 3i(n/2i) = n3i/2i =(3k-2k)/(3/2 - 1)=O(3k)=O(3log2n)= O(n log23) T(n) = n log23 +O(n log23)= 或根据master 定理直接带入公式…亦可得T(n ) = 1.2 解 递推求解如下： B(n) = 2B(n/2) + n/ lg n 首先根据master 定理 ==>=f(n) 其中接近为0. 又因为n/lgn < n 。 所以B(n) =2B(n/2) + n/ lg n<2B(n/2) + n 既得 B(n)< (nlgn) 1.3
猜测解为H(n)=O(nlgn)，下证H(n)<=dnlgn，当d是一个合适的正值常数，有H(n)<=d(n/2)lgn/2+d(n/4)lgn/4+d(n/6)lgn/6+d(n/12)lgn/12+n =dnlgn-d(n/2)lg2-d(n/4)lg4-d(n/6)lg6-d(n/12)lg12+n <=dnlgn 使上式成立的条件时d>1/(4lg2/3+lg3/4) 假设 1.4 解 递推求解如下： G(n) = G(n?1) + 1/n 同1.1 可得 …… = G(1) + 1/2+……+1/n = G(1) + Ln(n)+R-1 =Ln(n)+O(1) 二、 给定两个大小分别为m和n的已经排序的序列A和B, 给出一个算法求得序列A和B 的并集中第k小元素，要求时间复杂性为O(log m + log n)。 1. 取a=, b= 2. 若k<=a+b,比较A[a]和B[b]， 若A[a]>B[b],即知第k小的元素不在A的后半部，则将A去掉后半部分,令m=a,n=n。否则将B的后半部分去掉，令m=m,n=b。 3. 类比2，反面易得… 若k>a+b, 比较A[a]和B[b]。 若A[a]>B[b], 即知第k小的元素不在B的前半部分，则将去掉B的前半部分，改为寻找第k-b大的元素，否则将去掉A的后前部分，寻找第k-a大的元素。 4. 重复过程2、3直至为空。 三、 1. 证明= 2. 判断是否=, 请证明你的结论 3. 判断是否=,请证明你的结论…… 3.1 <=4n=O(n) >=(1/4)*n= 所以原式 3.2
相关文档
- 2019年哈尔滨工业大学深圳校区材料科学与工程学院硕士研究生招生考试拟录取名单
- 哈工大深圳硕博连读的有关规定
- 2019年哈尔滨工业大学建筑学院深圳083300城市规划学专业硕士研究生招生考试拟录取名单公示.xls
- 关于工程硕士以及哈工大深圳研究生院
- 2019年哈尔滨工业大学硕士研究生招生考试拟录取名单深圳机械工程学硕
- 2019年哈工大哈尔滨工业大学(深圳)考研复试时间复试内容复试流程复试资料及经验
- 哈尔滨工业大学深圳研究生院委托培养硕士研究生合同书
- 哈尔滨工业大学深圳优秀硕士毕业研究生登记表
- 2019年哈尔滨工业大学硕士研究生招生考试拟录取名单深圳机械工程专硕
- 哈尔滨工业大学深圳研究生院招收博士后审批表
- 【哈尔滨工业大学深圳研究生院排名】哈尔滨工业大学深圳研究生院特色专业-哈工大深圳研究生院录取分数线
- 哈工大深圳研究生院教案模板1
- 哈尔滨工业大学深圳研究生院
- 哈工大深圳研究生院用印审批单
- 哈工大深圳研究生院硕士研究生入学协议二等奖学金
- 哈尔滨工业大学深圳研究生院教职员请假审批表
- 哈尔滨工业大学深圳研究生院2016届毕业生生源信息表
- 中期报告模板-哈尔滨工业大学(深圳)
- 哈尔滨工业大学深圳研究生院委托培养硕士研究生合同书(精)
- 哈尔滨工业大学深圳研究生院招聘教师公告