江西农业大学
2017年招收攻读硕士学位研究生入学考试试题(机密) 考试科目代码 821  考试科目名称数据结构（A）
注意事项：答案一律在答题纸上填写，答在草稿纸或试卷上一律无效。
一、选择题（每题2分，共30分）
1. 计算机算法指的是（1）。
A．计算方法  B. 排序方法  C. 解决问题的步骤序列    D. 调度方法。
2. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O(n) O(n)      B. O(n) O(1)    C. O(1) O(n)    D. O(1) O(1)
3. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(  )最节省时间。
A. 单链表研究生入学考试
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点的双循环链表
4. 非空的循环单链表head 的尾结点p↑满足（）。
A．p↑.link=head    B．p↑.link=NIL    C．p=NIL      D．p= head
5. 对于队列操作数据的原则是（）。
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
6. 设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列。
A. 1，2，4，3
B. 2，1，3，4
C. 1，4，3，2
D. 4，3，1，2，
7. 设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（）
A．求子串      B．联接      C．匹配    D．求串长
8. 设A 是n*n 的对称矩阵，将A 的对角线及对角线上方的元素以列为主的次序存放在一维数组(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B 中的位置为( )。
A. i(i-l)/2+j
B. j(j-l)/2+i
C. j(j-l)/2+i-1
D. i(i-l)/2+j-1
9. 一个n 个顶点的连通无向图，其边的个数至少为（）。
A．n-1      B．n        C．n+1        D．nlogn；
10. 对N 个元素的表做顺序查时，若查每个元素的概率相同，则平均查长度为( ) 。
A．（N+1）/2      B. N/2      C. N        D. [（1+N）*N ]/2
11. 下面关于二分查的叙述正确的是 ( ) 。
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
12. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进
行一趟快速排序的结果为（）。
A． 2，3，5，8，6    B.  3，2，5，8，6
C.  3，2，5，6，8
D. 2，3，6，5，8
13. 循环队列存储在数组]中，用front 和rear 分别表示队头和队尾，则入
队时的操作为（）。
A. rear=rear+1
B.  rear=(rear+1) % (m-1)
C. rear=(rear+1) % m
D.  rear=(rear+1)%(m+1)
14. 设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。
A. 2n
B.  n+l
C. 2n-1
D. 2n+l
15. AOV网是一种（）。
A．有向图      B．无向图    C．无向无环图    D．有向无环图
二、填空题（每空2分，共30分）
1. 对于给定的n 个元素，可以构造出的逻辑结构有集合，（1），（2），图状结构四种。
2. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是____（3）____
3. 顺序存储结构是通过__（4）___表示元素之间的关系的；链式存储结构是通过_（5）___表示元素之间的关系的。
4. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（6）的数据结构。
5. 两个字符串相等的充分必要条件是___（7）____。
6. 树在计算机内的表示方式有_ (8)__，_ (9)__，_ (10)__。
7. 深度为k 的完全二叉树至少有___(11)____个结点，至多有___(12)____个结点。
8. 一个连通图的___(13)___是一个极小连通子图。
9. 为了能有效地应用HASH查技术，必须解决的两个问题是______(_14)_______
和_____(15)_______。
三、解析题（每题10分，共60分）
1.证明：树中的节点数等于所有节点的度数加1。
2.请画出下图的邻接矩阵和邻接表。
3.设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,
并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。
4.下图所示的森林，将此森林转换为相应的二叉树。
(a)(b)
5.  设待排序的表有8个记录，其关键字分别为{18,2,20,34,12,32,6,16,1,5}。说明采用归并排序方法进行排序的过程。
6.  对于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40}，采用二分查，试问：
(1)若查给定值为20的元素，将依次与表中哪些元素比较。
（2）假设查表中每个元素的概率相同，求查成功时的平均查长度和查不成功时的平均查长度。
四、算法设计題（每题15分，共30分）（用C语言或C++表示算法）
1.设计一个算法，删除一个单链表L中元素值最大的节点。
2. 采用一个不带头节点只有一个尾节点指针rear的循环单链表存储队列（如下图），设计队列的初始化、进队和出队算法。