江 西 农 业 大 学
2013年招收攻读硕士学位研究生入学考试试题
考试科目代码、名称 818 数据结构
注意事项：答案一律在答题纸上填写，答在草稿纸或试卷上一律无效。
一、选择题（每题2分，共30分） 1. 计算机算法指的是（ ）。
（A）．计算方法 （B）. 排序方法 （C）. 解决问题的步骤序列 （D）. 调度方法 2. 以下数据结构中，（ ）是线性结构？
（A）．广义表 （B）. 二叉树 （C）. 稀疏矩阵 （D）. 串 3. 链表不具有的特点是（ ）
（A）．插入、删除不需要移动元素 （B）．可随机访问任一元素 （C）．不必事先估计存储空间 （D）．所需空间与线性长度成正比 4．非空的循环单链表head 的尾结点p满足（ ）
（A）．p->link==head (B)．p->link==NIL (C)．p==NIL (D)．p== head 5. 对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（ ）
(A)．head==NULL (B)．head->next==NULL (C)．head->next==head (D)．head!=NULL 6. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
(A). 不确定 (B). n-i+1 (C). i (D). n-i 7. 对稀疏矩阵进行压缩存储目的是（ ）。
(A)．便于进行矩阵运算 (B)．便于输入和输出 (C)．节省存储空间 (D)．降低运算的时间复杂度 8. 设无向图的顶点个数为n，则该图最多有（ ）条边。
(A)．n-1 (B)．n(n-1)/2 (C)． n(n+1)/2 (D)． n
9. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
1
2
(A) .5 (B). 6 (C). 7 (D). 8
10.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21
11.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 (A) 25
(B) 10
(C) 7
(D) 1
12. （ ）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历
(B) 中序遍历
(C) 后序遍历
(D) 层次遍历
13. 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。 (A) O(n)
(B) O(nlog2n)
(C) O(n)
2
(D) O(n/2)
3
14. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 (A) top=top+1; (C) top->next=top;
(B) top=top-1; (D) top=top->next;
15.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。 (A) 1
(B) 2
(C) 3
(D) 4
二、填空题（每空2分，共30分）
1. 对于给定的n 个元素,可以构造出的逻辑结构有集合、 （1）、（2）和图结构四种。
2. 设单链表的结点结构为(data,next)，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点 , 若将结点y 插入结点x 之后，则需要执行以下语句: （3） ； （4） 。
3. ____（5）___是限定仅在表尾进行插入或删除操作的线性表。
4. 设数组a[1..50,1..80]的基地址为2000，每个元素占2 个存储单元，若以行序为
2
主序顺序存储，则元素a[45,68]的存储地址为_（6）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（7）_。
5. 二叉树由_(8)__，__(9)_，_(10)__三个基本单元组成。 6. 判断一个无向图是一棵树的条件是__(11)____。
7. 为了能有效地应用HASH查找技术，必须解决的两个问题是______(_12)_______和_____(13)_______。
8. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____(14)__，右孩子结点的编号为____(15)____。
三、解析题（每题10分，共60分）
?2050???0005???0300????1002?? 1. 设稀疏矩阵A=?画出其三元组表形式压缩存储表。 2. 请画出下图的邻接矩阵和邻接表。
3. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。
3
4. 设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。 5. 用C语言或C++实现在顺序有序表中实现二分查找的算法。 6. 用C语言或C++实现判断单链表中元素是否是递增。
四、算法设计題（每题15分，共30分）（用C语言或C++表示算法） 1. 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。 （1）请说明共享方法，栈满/栈空的判断条件；
（2）用C 设计公用的入栈操作push（i，x），其中i 为0 或1，用于表示栈号，x 为入栈值;
2. 写出二叉树的结构，并设计判断两个二叉树是否相同的算法。
4
江 西 农 业 大 学
2014年招收攻读硕士学位研究生入学考试试题
考试科目代码、名称 818 数据结构（Ａ卷）
注意事项：答案一律在答题纸上填写，答在草稿纸或试卷上一律无效。
一、选择题（每题2分，共30分）
1. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
（A）688 （B）678 （C）692 （D）696
2. 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。
(A) s->next=p->next；p->next=s； (B) q->next=s； s->next=p； (C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；
３.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i ４.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。
(A) 4 (B) 5 (C) 6 (D) 7
５.两个字符串相等的充要条件是（ ）。 (A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等 (C) 同时具备(A)和(B)两个条件 (D) 两个字符串的第一个字符相同
６. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next;
７. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。 (A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
８. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针
的操作序列为（ ）。
(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；
９. 一个n 个顶点的连通无向图，其边的条数至少为（ ）。 （A） n-1 （B）n （C）n+1 （D） n*(n-1)/2；
1
江西农业大学数据结构2013—2017(缺2016)年考研真题试题
