2011年江西农业大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2011 年江西农业大学数据结构考研真题一、选择题（每小题 3 分，共 45 分） 1.若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（）存储方式最节省时间。 A、单链表 B、双链表 C、单向循环 D、顺序表 2.串是任意有限个（） A、符号构成的序列 B、符号构成的集合 C、字符构成的序列 D、字符构成的集合 3.设矩阵 A（aij，1≤i，j≤10）的元素满足∶aij≠0(i≥j,1≤i,j≤ 10)aij=0(i

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.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（） A、n2 B、nlog2n C、log2n D、n-1 12.堆是一个键值序列（k1，k2，…，knl，对 i=1，2，…，n/21，满足（） A、ki≤k2i≤k2i+1 B、kisk2i+1k2i C、ki≤k2i 且 ki≤k2i+1（2i+1≤n） D、ki≤k2i 或 ki≤k2i+1（2i+1≤n） 13.一个具有 n 个顶点的无向完全图的边数为（） A、n(n+1)/2 B、n(n-1)/2 C、n(-1) D、n(+1) 14.在索引顺序表中查找一个元素，可用的且最快的方法是（） A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找 15.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。 A、单链表 B、双链表 C、带头结点的双循环链表 D、容量足够大的顺序表二、判断题（每小题 1 分，共 10 分）

1.双链表中至多只有一个结点的后继指针为空。（） 2.在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件是 front=rear。（） 3.对链表进行插入和删除操作时，不必移动结点。（） 4.栈可以作为实现程序设计语言过程调用时的一种数据结构。（） 5.在一个有向图的拓朴序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧。（） 6.对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（） 7."顺序查找法"是指在顺序表上进行查找的方法。（） 8.向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（） 9.键值序列{A，C，D，E，F，E，F}是一个堆。 10. 二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）三、填空题（每小题 3 分，共 30 分） 1.在带有头结点的单链表 L 中，若要删除第一个结点，则需执行下列三条语句∶____ __; L->next=L->next;free(0); 2.有一个长度为 20 的有序表采用二分查找方法进行查找，共有___个元素的查找长度为 3。 3.采用冒泡排序对有 n 个记录的表 A 按键值递增排序，若 L 的初始状态是按键值递增，则排序已录的比较次数为_____。若 A 的初始状态为递减排列，则记录的交换次数为__ 4.在无头结点的双链表中，指针 P 所指结点是第一个结点的条件是__ 5.G 为无向图，如果从 G 的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是___ 6.如果一个有向图中没有_____，则该图的全部顶点可能 7.深度为 8（根的层次号为 1）的满二叉树有____个叶子结点。 8.将一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点 X，其双亲 PARENT（X）的编号为_ 9.设某闭散列表 HT 未满，散列函数 H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。 10.设有一个链队，结点结构为 datanext，front 为队头指针，rear 为队尾指针，当执行入队操作时需执行下列语句∶ 四、简答题∶（每小题 5 分，共 25 分） 1.对于一个有 1000 个结点的二叉树，树叶最多有多少个?最少有多少个?

2.已知一棵二叉树的中序序列和后序序列分别为∶DBGEACHF 和 DGEBHFCA.则该二叉树的前序序列是什么? 3.设有 1000 个无序的元素，需排出前 10 个最大（小）的元素，你认为采用哪种排序方法最快? 4.在 KMP 算法中，已知模式串为 ADABCADADA，请写出模式串的 next【J】函数值。 5.中序遍历的递归算法平均空间复杂度为多少? 五、算法设计题（每小题 10 分，共 40 分） 1.试编写一个算法，判断一给定的整型数组 a【n】是不是一个堆。 2.一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。

分享到：

赞收藏

资料库

2011年江西农业大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料