2011年江西农业大学908《数据结构》考研真题

《2011年江西农业大学908《数据结构》考研真题》由会员分享，可在线阅读，更多相关《2011年江西农业大学908《数据结构》考研真题（5页珍藏版）》请在金锄头文库上搜索。

1、考试复习重点资料（最新版）考试复习重点资料（最新版） 封封 面面 第1页 资料见第二页资料见第二页 江 西 农 业 大 学 江 西 农 业 大 学 2011 年招收攻读硕士学位研究生入学考试试题2011 年招收攻读硕士学位研究生入学考试试题(机密) (机密) 适用学科、专业 考试科目代码、名称 908 数据结构 注意事项：答案一律在答题纸上填写，答在草稿纸或注意事项：答案一律在答题纸上填写，答在草稿纸或 试卷上一律无效。试卷上一律无效。 数据结构试题 A 卷 一、选择题（每小题 3 分，共 45 分） 1 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则 采用（ ）存

2、储方式最节省时间。 A、单链表 B、双链表 C、单向循环 D、顺序表 2 串是任意有限个（ ） A、符号构成的序列 B、符号构成的集合 C、字符构成的序列 D、字符构成的集合 3 设矩阵 A（aij ，li,j 10）的元素满足： aij0(ij, li, j 10) aij=0 (ij, li, j 10) 现将 A 的所有非 0 元素以行序为主序存放在首地址为 2000 的存储区域中，每个 元素占有 4 个单元，则元素 A95的首址为 A、2340 B、2336 C、2164 D、2160 4 如果以链表作为栈的存储结构，则退栈操作时（ ） A、 必须判别栈是否满 B、 对栈不作任何判别

3、C、 必须判别栈是否空 D、 判别栈元素的类型 5 设数组 Data0.m作为循环队列 SQ 的存储空间，front 为队头指针，rear 为 队尾指针，则执行出队操作的语句为（ ） A、front=front+1 B、front=(front+1)% m C、rear=(rear+1)%m D、front=(front+1)%(m+1) 6 深度为 6（根的层次为 1）的二叉树至多有（ ）结点。 A、 64 B、32 C、31 D、63 7 将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点 编号，根结点的编号为 1。编号为 49 的结点 X 的双亲编号为（ ） A、2

4、4 B、25 C、23 D、无法确定 8 设有一个无向图 G=（V，E）和 G=（V，E）如果 G为 G 的生成树，则 下面不正确的说法是（ ） A、G为 G 的子图 B、G为 G 的边通分量 C、G为 G 的极小连通子图且 V=V D、G为 G 的一个无环子图 9 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值 （ ） A、 一定都是同义词 B、一定都不是同义词 C、都相同 D、不一定都是同义词 10 二分查找要求被查找的表是（ ） A、 键值有序的链接表 B、链接表但键值不一定有序 C、 键值有序的顺序表 D、顺序表但键值不一定有序 11 当初始序列已经按键值有序，用直

5、接插入算法对其进行排序，需要循环的 次数为（ ） A、n2 B、nlog2n C、log2n D、n-1 12 堆是一个键值序列k1,k2, kn,对 i=1,2,|_n/2_|,满足( ) A、kik2ik2i+1 B、kik2i+1k2i C、kik2i 且 kik2i+1(2i+1n) D、kik2i 或 kik2i+1(2i+1n) 13一个具有 n 个顶点的无向完全图的边数为（ ） A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1) 14在索引顺序表中查找一个元素，可用的且最快的方法是（ ） A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B

6、、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找 15 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后 一个元素，则采用（ ）存储方式最节省运算时间。 A、 单链表 B、双链表 C、带头结点的双循环链表 D、容量足够大的顺序表 二、判断题（每小题 1 分，共 10 分） 1双链表中至多只有一个结点的后继指针为空。 （ ） 2在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队 尾元素，队列为满的条件是 front=

7、rear。 （ ） 3对链表进行插入和删除操作时，不必移动结点。 （ ） 4栈可以作为实现程序设计语言过程调用时的一种数据结构。 （ ） 5 在一个有向图的拓朴序列中， 若顶点 a 在顶点 b 之前， 则图中必有一条弧。 ( )i 6对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访 问每个顶点，则该图一定是完全图。( ) 7“顺序查找法”是指在顺序表上进行查找的方法。 （ ） 8向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结 点。 （） 9键值序列A，C，D，E，F，E，F是一个堆。 10二路归并时，被归并的两个子序列中的关键字个数一定要相等。 （） 三

8、、填空题（每小题 3 分，共 30 分） 1在带有头结点的单链表 L 中，若要删除第一个结点，则需执行下列三条语句： ；L-next=U-next；free(U)； 2有一个长度为 20 的有序表采用二分查找方法进行查找，共有个 元素的查找长度为 3。 3采用冒泡排序对有 n 个记录的表 A 按键值递增排序，若 L 的初始状态是按键 值递增，则排序过程中记录的比较次数为。若 A 的初始状态为递减 排列，则记录的交换次数为。 4在无头结点的双链表中，指针 P 所指结点是第一个结点的条件是 。 5G 为无向图，如果从 G 的某个顶点出发，进行一次广度优先搜索，即可访问 图的每个顶点，则该图一定是图

9、。 6如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑 序列。 7深度为 8（根的层次号为 1）的满二叉树有个叶子结点。 8将一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点 X，其双亲 PARENT（X）的编号为。 9设某闭散列表 HT 未满，散列函数 H（KEY）为键值第一字母在字母表中的 序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现 按键值第一字母的顺序输出闭散列表中所有键值的算法。 void printword(keytype HTm) for(i=1;idata=x; p-next=NULL； ； ； 四、简答题： （每小题 5 分，

10、共 25 分） 1. 对于一个有 10000 个结点的二叉树，树叶最多有多少个？最少有多少个？ 2. 已 知 一 棵 二 叉 树 的 中 序 序 列 和 后 序 序 列 分 别 为 ： DBGEACHF 和 DGEBHFCA，则该二叉树的前序序列是什么？ 3. 设有 1000 个无序的元素，需排出前 10 个最大（小）的元素，你认为采用哪 种排序方法最快？为什么？ 4. 在 KMP 算法中，已知模式串为 ADABCADADA ，请写出模式串的 nextj函 数值。 5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题 10 分，共 40 分） 1. 试编写一个算法，判断一给

11、定的整型数组 an是不是一个堆。 2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一 高效算法，求二叉树的繁茂度。 3设有一单链表L，结点结构为data|next，结点个数至少 3 个，试画出链表L 的结构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素 值次为a1,a2,a3,an，判断ai+1-ai=ai-ai-1是否成立，其中i满足 2=i=n-1.(8 分) 4设有一棵二叉树以二叉链表作为存储结构，结点结构为 lchild|data|rchild,其中 data 域中存放一个字符， 设计一个算法按前根遍历顺序仅打印出 data 域为数字的 字符（即0=data=9）