2019年北京理工大学硕士研究生入学考试初试题
北京理工大学
2019 年硕士研究生入学考试初试试题（真题回忆）
科目代码： 813 科目名称： 计算机专业基础 满分： 150 分 注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；
③本试题纸须随答题纸一起装入试题袋中交回！
第一部分：数据结构（120分） 一、填空题
1、L 是单向循环链表的指向头结点的指针，判断链表是否为空的条件是______ 。 2、一颗排序二叉树有 n 个结点，深度为 d，则插入一个结点的时间复杂度为____ 。 3、链队列的入队的时间复杂度是_____ 。 4、 二、判断题
1、哈夫曼树是一颗平衡二叉树 。
2、在拓扑排序中，如果在之前，说明存在一条从到的路径。 3、 三、选择题 1、给出了一种结构 typedef struct{ ……
}LNode, *List
问定义一个这种类型的指针的语句是？ A、LNode L B、List L C、List *L D、都不对 2、适合存储边稠密图的结构是
2019年北京理工大学硕士研究生入学考试初试题
A、邻接表 B、邻接矩阵 C、逆邻接表 D、都不对 四、简答题
1、给出了一个静态链表 SAPCE[MAXSIZE]，大概这样 （图片在附件里，是 SPACE.jpg）
（1）画出对应的链表。（应该是这么问的，我就把静态链表看成链式存储结构画了出来）
（2）画出从静态链表中删除 H 后的 SPACE[MAXSIZE]；
（3）定义了静态链表结点类型，请写出删除函数 void free( position k) typedef intposition; typedef struct{
elemtype data; position k;
}SPACE[MAXSIZE]；
（4）和顺序表相比，静态链表的主要优点是？ （5）和链式存储结构相比 ，静态链表的主要优点是？ 2、给了一种表达式树，A*(B+C*D)的表达式树如图 (图片是表达式树.jpg)
（1）写出前序、中序、后序遍历的序列 （2）写出 A*(B+C*D)的后缀表达式
（3）构造表达式树需要一个栈和后缀表达式，问栈的元素的类型是什么？简要说说构造表达式树的方法。
（4）按照上述方法，画出构造表达式树时栈内元素的变化情况。 3、
（1）说明希尔排序为什么比直接插入排序效率高
（2）给了一个包含 10 个数的序列，增量序列分别是 5、3、1，写出每一趟排序后的结
2019年北京理工大学硕士研究生入学考试初试题
果。
（3）给了希尔排序的算法的代码，要求补全。
（4）若要排序大块文件的话，希尔排序的效率特别低，请设计一种方法，使得每次只需要移动一趟。（这题我也记得很模糊，具体问法参考一下其他的回忆试题） 五、算法题
1、定义循环队列的结构 typedef struct{ int MAXSIZE；
int front; //指向队头元素 int num; //指出队内元素个数
elemtype * Elems;// 指向存储队列区域的指针。 }*Queue;
（1）写出建立一个队列的函数 QueueCreateQueue(int MAXSIZE) (2)写出删除队列的函数 void DeleteQueue(Queue Q);
(3)写出将一个元素入队的函数 void EnQueue(Queue Q, elemtypek) (4)写出返回队头元素并将其删除的函数 elemtype DeQueue(Queue Q)
3、有向无权图的顶点用数字表示。现要计算从源点 S 到其他顶点的最短路径。 LAST[MAXSIZE]是一个数组，LAST[w]=v 表明从 S 到点 w 的最短路径的最后一条弧是
（2）写出从源点到其他各点的最短路径
（3）补全利用 BFS 寻找源点到其他各点最短路径的代码。（不难）
2019年北京理工大学813考研真题回忆版
