哈工大计算机科学与技术专业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.线性链表
司法考试报名时间2021年
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.若待排序关键字序列在排序前已按其关键字递增次序排列, 则采取（）方法比较次数最2021国考考录专题网站
少。
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树）中, 查AVL树中一个关键字最多需要
（18）次比较。
19.对初态有序表, 最少时间排序算法是（19）。
三、简答题
20.在n个数据中出前K个最大元素, 能够采取堆排序或败者树来实现。分别说明上述两
种实现方法基础步骤, 并分析每种方法时间复杂度和空间复杂度。
21.假设举行一个1000人参与学术会议, 作为会议报道组责任人, 你会收到会务组为每名参
会者开具包含其英文名字注册费发票, 同时还会收到为每位参会者提供印有其英文名字参会胸牌和其她会议资料。请回复以下问题:
（1）怎样有效地把每个参会者注册费发票和参会胸牌等其她会议资料放在一起形成
一份参会资料？
考研计算机真题（2）怎样在会议报道日更有效地把每份资料发放给参会者？
要求: 说明你所使用关键技术和相关步骤。
四、算法设计题
按以下要求设计算法:
（1）描述算法设计基础思想;
（2）依据设计思想, 采取C或C++或Java语言描述算法;
（3）分析算法时间复杂度和空间复杂度。
22.给定一个n个整数无序数组A, 设计一个时间和空间尽可能高效算法, 出其中第k个
小整数: int findTheKmin (int A[], int n, int k)。
23.给定一棵n个结点二叉排序树（即BST）, 每个结点均存放一个整数, 其结点格式为
普通话准考证号查询入口[lechild][data][rechild]。令half=(BST中最大值+BST中最小值)/2。设计一个算法intfindNearMid(BinTree * root), 完成:
（1）出BST中最大和最小以及计算half值;
（2）返回大于half且与half相差最小结点值。
II．计算机组成原理部分
五、填空
1.在整数定点机中, 采取1位符号位, 若寄存器内容为10000000, 当它分别表示为原码、
补码, 及无符号数时, 其对应真值分别为1-1 、1-2 、1-3 和1-4 。（均用十进制表示）
2.变址寻址和基址寻址区分是: 在基址寻址中, 基址寄存器提供2-1 , 指令提供2-2
; 而变址寻址中, 变址寄存器提供2-3 , 指令提供2-4。
3.利用3-1指令进行输入输出操作I/O编址方法为统一编址。
4.设n=16（不包含符号位）, 机器完成一次加和移位各需100ns, 则原码一位乘最多需
4-1 ns, 补码Booth算法最多需4-2 ns。2019河南特岗教师招聘公告
5.CPU从主存取出一条指令并实施该指令时间叫5-1 , 它通常包含若干个5-2 。以后者
又包含若干个5-3 、5-4 组成多级时序系统。
六、选择题
1.冯·若依曼计算机中指令和数据均以二进制形式存放在存放器, CPU区分它们依据是（）。
A.指令操作码译码结果
B.指令和数据寻址方法
C.指令周期不一样阶段
D.指令和数据所在存放单元
2.DMA方法传送数据时是在（）控制。
A.CPU
B.程序
C.CPU+程序
D.硬件电路
3.总线通信中同时控制是（）。
A.只适合于CPU控制方法
B.由统一时序控制方法
C.只适合于外围设备控制方法
D.只适合于主存
4.下列叙述中（）是错误。
A.采取微程序控制器处理器称为微处理器
B.在微程序编码中, 编码效率最低是直接编码方法
C.在多种微地址形成方法中, 增量计数法需要次序控制字段较短
D.CMAR是控制器中存放地址寄存器
5.设相对寻址转移指令占两个字节, 第一字节是操作码, 第二字节是相对位移量（用补码
表示）, 若CPU每当从存放器取出一个字节时, 即自动完成(PC)+1 PC。设目前PC内容为H, 要求转移到H地址, 则该转移指令第二字节内容应为（）
A.F5H
B.F7H
C.09H