青 岛 科 技 大 学
二○一六年硕士研究生入学考试试题
考试科目：数据结构
注意事项：1．本试卷共三道大题（共计 23个小题），满分 150 分；
2．本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；
3．必须用蓝、黑钢笔或签字笔答题，其它均无效。
﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡
一、选择题(每个2分，共30分)
1、在长度为n的顺序表的第i(1≤i≤n+1)个位置上删除一个元素，移动元素的个数为( ) 。
A. i-1 B .n-i+1 C. i D. n-i
2、以下哪一个术语与数据的逻辑结构无关？（ ）
A．哈希表 B. 栈 C. 二叉树 D. 线性表
3、下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
A. O(m2) B. O(m*n) C. O(n2) D. O(m+n)
4、三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为( )。
A. 356 B. 362 C. 360 D. 358
5、下列陈述中不正确的是( ) 。
A. 二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时也有左右之分
C.二叉树中可以没有度为2的结点
D. 二叉树中最多只有两棵子树，并且有左右之分
6、n个顶点的连通图，若从一个顶点出发进行遍历，则（ ）。
A. 可以访问图中一个顶点 B. 可以访问图中所有的顶点
C. 可以问n/2 个顶点 D. 可以访问n(n-1) 个顶点
7、在一棵具有k层（k>=1）的满三叉树中，结点总数为（ ）。
A. 3k B. 3k-1 C . （3k-1）/3 D. （3k-1）/2
8、AVL树是一种平衡的二叉排序树，树中任一结点的( ) 。
A. 左、右子树高度差的绝对值不超过1 B. 左、右子树的高度均相同
C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度
9、若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A. i-j-1 B. 不确定的 C. j-i+1 D. i-j
10、适用于折半查找的表的存储方式及元素排列要求为( ) 。
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
11、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )。
A．9 B．3 C．5 D． 8
12、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）。
A．p=p->next B．p->next=p->next->next
C．p=p->next->next D．p->next=p
13、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择 B. 快速 C. 冒泡 D. 希尔
14、关键路径是事件结点网络中的（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长的回路 D．最短的回路
15、在含有n个结点的二叉树中有（ ）个分支。
A. n B. n-1 C. n+1 D.（n+1）/2
二、应用题（60分）
1．（12分）回答下列问题：
① 什么是数据结构？
② 对于数据结构一般包含哪三个方面的讨论？
③ 在编制管理通讯录的程序时，通讯录数据采用什么样的数据结构合适？
④ 对于第③问，存储结构采用什么样的结构合适？为什么？
2．（12分）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：
① 存放该数组所需多少单元？
② 存放数组第4列所有元素至少需多少单元？
③ 数组按行存放时，元素A[7,4]的起始地址是多少？
④ 数组按列存放时，元素A[4,7]的起始地址是多少？
3．（12分）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
4．（12分）请阅读下列算法，回答问题。
for ( i=2; i<=L.length; ++i )
if (L.r[i].key < L.r[i-1].key) {
L.r[0] = L.r[i]; // 复制为监视哨
for ( j=i-1; L.r[0].key < L.r[j].key; -- j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0];
}
① 这是什么类型的排序算法？；
② 该排序算法稳定吗？
③ 该排序算法的时间复杂度与关键字的初始排列顺序有没有关系？
④ 假定设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，请写出使用该排序方法，每趟排序结束后关键字序列的状态。
5.（12分）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树；
② 若查找元素54，需依次与哪些元素比较？
③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
三、算法设计题（60分）
1.（20分）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
（1）描述算法的基本设计思想；
（2）用类C的语言描述该算法，关键之处给出简要注释。
2.（20分）以二叉链表作为二叉树的存储结构，编写以下算法：
（1）判别两棵树是否相等；
（2）交换二叉树每个结点的左孩子和右孩子。
3.（20分）
（1）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
（2）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。
