2017年北京师范大学生命科学学院978数据结构考研仿真模拟题
● 摘要
一、填空题
1． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
3． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
4． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
5． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
已包括进生成树，就把矩阵元素A （i ，j ）置成。
（3）算法结束时，相邻矩阵中的元素指出最小生成树的
【答案】（1）边上的权值；都大的数；（2）1; 负值；（3）为负；边
6． 实现字符串拷贝的函数strcpy 为：
【答案】
7．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
8． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
编号，以rear 指示实际的队尾元素，现
要在此队列中插入一个新元素，新元素的位置是（ ）。
9． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
10．模式串的next 函数值序列为_____。
【答案】01122312
11．二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
和块的伙伴地址分别为：_____
和
其伙伴块的起始地址计算公
当大小为16时，起始地址为
：
12．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
13．二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
14．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
【答案】（1）（2）（3）（4）（5）