2020 哈尔滨工业大学 854 真题回忆版
第 I 部分 计算机系统与基础
一、选择题（10 道题，每道 1 分）
1.objdump 反编译的程序中，有个常数1024（RIP），请问是什么。 A
局部变量 B 局部静态变变量 C 全局变量 D 都不是
2 linux 内核的编码方式采用编码
A unicode
B ASCII
C utf-8
D utf-32 3
int 和f loat 哪个能表示的个数多（）
A int
B float
C 一样多
D 无法确定
4 执行hello world 程序时最有可能首先() A.
出现缺页. B.执行c all main 指令
5 ()提供了应用程序和硬件的之间的桥梁
A.操作系统
B.进程
C.指令集架构
D.虚拟内存 6
当数据位于（）时操作速度最快。
A.L1 cache
B.TLB
C.ddr 内存
D.ssd
7 哪个不是进程的状态（）
A 睡眠
B 运行
C 停止
D 终止 8
链接标准库的时间不包括（）
A 操作系统加载时
B 编译时
C 程序加载时
D 程序运行时 9
一个整数除0报什么异常（）
A 浮点异常
B segment fault
C 数据溢出
D 空行
10 …
二、填空题（5 道题，每道 2 分）
1.对于整形数-2,&x 的第四个字节是
2.补齐指令字节，指令地址40800 ea
3.TLB 是的缓存。
4 linux 下，ctrl+c 发送的是信号
5 代码中的常数是由转换成补码的。
三、问答题（4 道题，每道 5 分）
1.请写出0.1 的二进制表示，规格化表示，解码和尾码等。
2.Intel I7 CPU 的虚拟地址 48 位，物理地址 52 位。其内部结-构如下图所示，依据此结构，每一页面4KB，分析如下项目：
（1）虚拟地址中的V PN 占位；其一级页表为项。
（2）L1 数据T LB 的组索引位数T LBI 为位。
（3）L1 数据C ache 共组。
（4）用物理地址访问L1 数据C ache 时，C ache 标记C T 占位
3.给了汇编让写程序，程序名和程序参数可自定义。
mov (%rsi), %rax
neg %rax
mov (%rdi), %rdx
neg %rdx
mov %rdx, (%rsi)
mov %rax, (%rdi) ret
4.根据汇编，分析漏洞产生的原因（缓冲区溢出攻击相关）。里面
一句指令是：call strcpy
四、设计题（3 道题，每道 10 分）
1.流水线阶段分为取值、译码、执行、访存、写回、PC 更新阶段。请写出r et 指令各阶段的操作。若r et 发生控制冒险，应如何处理？
2.向量内积计算的相关程序如下。
/*向量的数据结构定义*/
typedef struct{
int len; //向量长度，即元素的个数
float *data; //向量元素的存储地址
} vec;
/*获取向量长度*/
int vec_length(vec *v){return v->len;}
/* 获取向量中指定下标的元素值，保存在指针参数v al 中*/ int
get_vec_element(*vec v, size_t idx){
if (idx >= v->len)
return 0;
*val = v->data[idx];
return *val;
}
/*计算向量内积*/
void inner0(vec *v，vec *u，float *sum){ long
int i;
*sum = 0;//初始化为0
for (i = 0; i < vec_length(v); i++) { float
val;
*sum = *sum + get_vec_element(v,i )*get_vec_element(u, i);
}
}
请对上述程序进行基本的优化，优化后的程序名使用i nner1，并说明优化依据。 3.请对上述程序进行基于C PU 的优化，给了基本的硬件单元（2 个浮点乘、1 浮点加、2 个加载器），对其进行2*2 循环展开，请编写优化程序i nner2。Inner2 的优化程序时最优的吗？如果不是，还可以怎样对其进行优化？
第 II 部分 数据结构
一、选择题（5 道题，每道1 分）
1. 复杂度
2. 10 阶对称矩阵，最少需要多少个元素
3.给了字符及其出现频率，问哈夫曼编码算法的时间复杂度是()
A.o(n2)
B.o(nlogn)
C.o(n)
D.o(n2logn)
4.散列表的表长为m，散列函数为H(key)=key%p ，则p应为（）
A.不大于m的最大素数
B.不大于m的最大偶数
C.大于等于m的最大素数
D.大于等于m的最大偶数 5
5….
二、填空（5 道题，每道2分）
1. 完全二叉树有2019 个节点，问有多少个叶子节点
2. 定点n边数e，无向图的邻接矩阵有零元素
3. a+(b*(c-d)-e)/f，求后缀表达式
4. 4 阶B树非失败节点关键字的个数范围
5…
三、问答题（10 分）
给你一个后序遍历（比如 6,7，5,10,11,9,8）可以唯一确定一颗二叉查找树吗？若可以，说明理由。若不可以，则举反例说明。
四、程序设计题（15 分）
要求：
1. 给出算法的基本设计思想
2. 根据设计思想，给出基本的数据结构
3. 编写算法，栈和队列的基本操作可直接使用。
题目：有两个有序数组A和B，试写出一种尽可能高效的算法找出序列中第k小的元素。并说明你所设计的算法的时间复杂度和空间复杂度。
第Ⅲ部分 计算机网络
一、选择题（10 道题，每道2分）
1 1000 个文件分发，采用C S 或P2P 模式，分别要用多少时间()
2.在无噪声的情况下，某通信链路的带宽为2kHz，采用2PSK 调制，则其传输速率为（）
A.1kbps
B.2kbps
C.4kbps
D.8kbps
3.单程传播时间7ms，传输速率100Mbps，发送的数据帧的大小为x B，确认帧的大小为
46B，帧号的比特数为4，则最大数据传输率是()
A.60%
B.80%
C.83%
D.100%
4.有三个设备，第一台设备连接着H1 和H2，第二台设备连接着H3 和H4，第三台设备
连接着H5 和H6。H1 和H2 同属于一个广播域，但属于不同的冲突域。H3 和H4 属于不同的冲突域，H5 和H6 属于同一个冲突域，则设备1,2，3 分别是（）
A.路由器，交换机，集线器
B.路由器，集线器，交换机
C.集线器，交换机，路由器
D.交换机，路由器，集线器
5 tcp 的非流水h ttp1.1 和并行t cp 连接的h ttp1.0 分别请求一个带有4个图像的请求的
时间计算。
6 报文交换和分组交换的时间计算。比如发送1M 的文件，分别报文发送和分组交换发送（分组的长度是1000B）
7 无线网络数据帧的三个地址具体是什么
8 tcp 中，tcp 段都是1000B，A发送了一个1001 的序号段给B ，之后发起断开连接，B返回给A的报文中的确认号是多少？
二分析题（20 分）（见下面的图,ip 地址都是模拟的，不一定和原题一样）
1 变长地址分配。假设将202.11.4.0/24 网址分配给网络1，网络2，网络3，网络
4.要求：网络1不少于120 的可分配地址，网络4不少于60 个可分配地址，网络2和网络3不少于20 个分配地址。请给出分配方案
2 给出R2 的路由表（要求：路由近可能少）路由表的格式：目的网络，掩码，下一条，接口
3 路由器R2 配置了D HCP 协议，主机2想要获得i p 地址，发送D HCP 报文是什么报文。源地址和目的地址是什么？给R2 的E0 端口分配一个I P 地址。
4 在R2 发送完D HCP 报文，获得i p 地址后，给出交换机的交换表。（路由表格式： mac地址，端口）
哈工大_2020考研计算机基础（854）
报考单位：哈尔滨工业大学
考试科目：计算机基础（854）
注：回忆的不全，只记得大概意思
数据结构：
算法题
1、在数组A[n]中，找到第k小的树：int findKMin(int a[],int n,int k);
2、在二叉排序树中：1、找到最大值Max和最小值min，代码中要求实现，通过half = (max+min)/2计算half的值 2、在BST中找到离half差值最小的节点，返回节点值
简答题：
1、在数组中，输出前k个最大值。分别用堆排序和败者树的方法，写出实现的步骤，并分析各自的时间和空间复杂度
2、1000人的会议中，有会议的资料，会议的参加人员。都是用英文名标识。
问题：1 如何将参加大会的人员资料和对应的会议资料更好地发给参与的人员
2 将会议资料和与会人员整合到一起（要求：详细写出你所用的技术和方法）
选择题：（记不清几个题,顺序不定）
1、2层7阶B树，最少的关键字是多少（）
2、 int x = n*n;
while(x>2){
x=x/2; }
时间复杂度是（）
3、下面关于B树和B+树中说法错误的（）
A 都满足顺序操作（好像是存取操作） B 都满足随机存取 CD记不清
填空题
1、n个人进行单循环赛需要比赛次数（）
2、完全二叉树有4033个叶子节点，此二叉树有（）个叶子节点。【题目应该出问题了】
3、10阶B树，内节点至少有（）个关键字，至多有（）个关键字
机组部分
大题
1、cpu有16根地址线，8根数据线，MREQ,W/R这些信号都和之前的题上要求一样。要求：最小4k是系统程序区，相邻4K是系统程序工作区，最小16k是用户程序区。
ROM 1k*8位、2k*8位 、2k*4位、剩下记不清 RAM 1K*8位，2k*8位、8k*8位剩下记不清 ，控制的38译码器没变。
要求，1、最小4k是系统程序区，相邻4K是系统程序工作区，最小16k是用户程序区
2、说明存储器的选择及具体的数量
3、详细画出片选逻辑
2、微程序的题，cpu采用总线结构。参考书上的图，差不多。（学习指导上的）。
1、要求，pc加1由ALU完成，写出取值周期的微操作和节拍安排
2、ADD #a #是立即寻址，写出执行周期的微操作及节拍安排
3 中断需要哪些硬件配置，各有什么作用？指令系统又需要什么硬件配置？
简答题：
1、主存于I/O的数据传输有哪些方式？说明各个方式的特点？指出那种方式传输最快
2、总线的传输速率。32位微处理器16位总线宽，机器主频是50Mhz，传输周期是4个时钟周期，总线的传输速率是多少？要想将传输速率提高一倍，可以采取什么措施？
3 计算 2^5*(9/16)+ 2^4*(-11/16),补码计算结果
4、主存1M,cache 16k，每块有32个字，每字32位。 分别画出直接映射和四路组相联的图，说明各段的内容
还有一题记不清了
选择题：（记不清）
填空题：
1、10000000,原码表示（），反码表示（），补码表示（），移码表示（）
2、指令执行的时间是（），包括多个（），后者又包括多个（）；（）组成了指令时序系统。
