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

地址，端口）