清华大学-912-2017-真题版.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 清华大学 912 真题 2017 回忆版 一．数据结构 1.判断题 (1)若f(n)=时间复杂度O(g(n)),也不一定有f(n)=O(g(n-1)). (2)若散列表使用不超过其长度的素数，则存储关键不能保证其分布均匀。 (3)在字符集各字符出现概率相同时，kmp 算法时间渐进程度接近蛮力算法。 (4)哈夫曼树距离深度更小的节点的权值可能小于深度更大的节点的权值。 (5)？ (6)？ 微 (7)？ 2.选择题 信 （1）。五个互异节点构造的二叉树有多少种？ 公 （2 ）对序列（64，63，...，2，1）进行直接插入排序比较次数最接近于（） 众 A.2800 B.2600 C.2400 D.2200 E.2000 （3 ）将关键字1，2，3...，2016 插入初始为空的平衡二叉树中，假设只有一个根节点的二 号 叉树高度为0 ，那么最终二叉树的高度是多少？ 计 （4 ）有哪些信誉好的足球投注网站7 阶B 树的第2016 个关键字，假设B 树根节点在内存中，则共需启动几次I/O. （5 ）有如下逆波兰式结果为2016，问?中的运算符号是多少（） 算 2 0 ！ * 2 2 * 6 + ^ 18 8 ? 9 / * A.+ B.* C.^ D. ! E./ 机 3,算法题 与 请利用图的广度优先遍历找出图中的最小环，若不存在环则输出+oo,要求时间复杂度为 o 软 （n*e）空间复杂度为o （n），最小环即环中边数最少的环。件 （1）请描述你的算法思想。 （2 ）请用伪代码写出算法。 考 4（3 ）说明你的算法的时间复杂度和空间复杂度。 研 5.若二叉树的数据结构如下 Struct binarytree ｛ Struct binarytree*parent ； Struct binarytree*lc ； Struct binarytree*tc； Struct binarytree*first （）； ｝ Struct realbinarytree ｛ Struct binarytree p ； Struct binarytree*next （）； ｝ （1）若first() 函数是取二叉树后序遍历节点的第一个节点，请写出first （）函数代码。 （2 ）若next （）函数是取该节点的后序遍历的后继，请写出next （）函数代码。 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan （3 ）在调用first （）函数和next （）函数对二叉树进行后序遍历时，证明遍历时间复杂度 为o （n）。 二，计算机组成原理 1.填空题 （1）指令由操作码和（）-组成. （2 ）若海明码P1P2D1P4D2D3P4 为？？？？？？？？，则该海明码有（）位错误（0 位， 一位，二位），正确的D1D2D3 为（）。 （3 ）DMA 使用总线的方式为（）和（）。 2.选择题 （1）IEEE 规格化单精度浮点数能表示的最小正数是（） 微 （2 ）（2 ）计算机运行的最小单位（） 信 a ）？ b ）微指令 c ）指令 d ）？ ？ 公 ？ 众 ？ 号 3.30 位虚拟地址，28 位物理地址，一级页表，页表大小16KB，访问5ns，cache 采用直接相