北理工考研辅导班：2020北京理工大学计算机考研813真题

一、数据结构

1.    填空题

1） 一颗二叉树使用二叉链表存储，使用____遍历可以求出树的深度。

2）m阶B-树的非根非叶节点的孩子节点至少有___个

3） 一个循环队列（size为100），rear和front分别是6和13，这个队列的长度是___.

4） 一个关于链表操作的时间复杂度的问题，比较简单，我忘了…

剩下的题就记不清了。

2.判断题

1)静态链表的插入和删除操作比动态链表的要快。

2）从平均时间复杂度来看，折半查找要比二叉排序树查找快。

其他简单的我都忘了。

3.选择题

好像有两道题是考适合的数据结构的。（比如用下面哪一种数据结构表示队列最合适）

其他的记不清了。

下面都是大题。

4.给了两个堆的操作函数：（20分）

PercolateUp(T,N,I):对长度为N的堆的I位置进行向上筛选使得以I为根的堆成为一个小顶堆。

PercolateDown(T,N,I):对长度为N的堆的I位置进行向下筛选使得以I为根的堆成为一个小顶堆。

1）使用上面的函数说明如何根据一个序列建立一个小顶堆。然后给了一个序列，让写出最终建立的小顶堆。

2）使用上面的函数说明如何在一个小顶堆中插入一个元素。然后给了一个序列，让写出插入一个元素后建立的小顶堆。

3）使用上面的函数说明如何在一个小顶堆中删除一个非堆顶元素。然后给了一个序列，让写出删除一个非堆顶元素后建立的小顶堆。

4） 使用上面的函数说明如何在一个小顶堆中修改一个元素。然后给了一个序列，让写出修改一个元素后建立的小顶堆。

5.这道题28分还是38分。。。错不起。

给了一个平衡二叉树的结点定义，然后又给了平衡二叉树的几个操作函数(LR,LL,RR,RL旋转操作函数)。

1)   请写出LLRotation(L)的代码。

2)   程序填空题：

平衡二叉树的Insert操作。

3）给了一个序列，写出最后建立的平衡二叉树。

6.

1）给了这些符号：+ - * / ( ) 在栈外的运算符优先级，让写出这些符号在栈内的运算符优先级。

2）给了一个中缀表达式，让把其转换为后缀表达式的过程写出来（每一步中栈中运算符和当前输入符号还有后缀表达式都要写）。

3）还是写运算符优先级。

7.给了一个链表算法，让写出其时间复杂度并改进。这道题很简单。

二、计算机组成

1. 填空题

1）两个八位补码数加法，若溢出使用上限或者下限表示运算结果表示，写出运算结果。

2）用4K*8的DRAM芯片组成8K*16的存储器，问DRAM芯片的数据线和地址线一共有几根；若DRAM的地址增加一根，存储器容量增大几倍？

2.  选择题

1）***系统使用16位指令，32位数据，目的是：

A．增加系统安全性

B．降低系统复杂度

C.增加指令存储密度

D…

2）忘了。

3）忘了。

4）指令系统扩展的题。指令长32位，一个地址长12位，已知二地址指令有250条，则一地址指令最多有多少条。

5） 给了磁盘的转速和一个磁道上的扇区数目以及每个扇区的字节数，让算数据传输率。

下面是两道大题。

3.    给了各类指令的执行路径以及每个阶段所需时间。让求：

1）单周期指令系统中如何规定CPU时钟周期？

2）若访存和取指都缩短到100ps，问系统加速比是多少。

3）计算系统吞吐率。

4.    cache组相连映射。

1)   写出标记、组索引和块内地址所占位数。

2)   给了一个int数组，问访问这个数组8次，cache命中率是多少。

新祥旭一对一考研辅导最基本的特征是一个老师专门辅导一个考研的学生，区别于学校中的很多学生听一个老师讲课的大班上课形式。从教育的本质看，只有互动才能够达到有效的教育效果，而一对一是教育能够互动的基本要求，传统的大班上课形式，互动很难有效展开。正因为如此，在传统学校教育课堂之外，新祥旭大力推广一对一辅导的教育培训模式。人们常说的一对一辅导全称一对一个性化辅导，是由专门的个性化教育辅导机构针对每个学生不同的学习情况和心理情况，有针对性地制定出一套独特的、行之有效的教学辅导方案和心理辅导策略，并由每个学生所配备的教学团队加以实施执行(包括一位专业教师+专业的心理咨询师+潜能开发专家+励志拓展专家+专职班主任)，通过全方位、策略性地辅导，不仅使学生掌握一种切合自身的学习方法，改善不良学习习惯，稳固提升学科知识，而且在树立自信，完善人格、为人处事等方面均得以提升。