中南大学-943-1997-2006-真题.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 追求卓越，挑战极限，从绝望中寻找希望，人生终将辉煌！ 中南大学1997 年数据结构 一. 是非题(共5分) 1、哈夫曼树是外部路径长度最小的扩展二叉树。 2、在表示某工程的AOE网中，加速其关键路经上的任意关键活动均可缩短整 个工程的完成时间。 3、二叉树是度为2的有序树。 4、在任意一棵二叉排序树中删除一个分支节点，接着又将该结点插入到二叉 排序树中，则所得到的二叉排序树和删除前的二叉排序树相同。 5、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 二． 填空题 （每空2分，共10分） 1、对于7个元素的集合（1，2，3，4，5，6，7）进行快速排序，具有最小比 微 较和交换次数的初始排列次序为 （ ） 信 2、设G为具有N个顶点的无向连通图，则G中至少有 （ ）条边。 3、设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分 公 支结点为 （ ）. 众 4、设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意 号 义下的出队列操作可表示为（ ），若用牺牲一个单元的办法来区分队 满和队空 （设队尾指针为sq.rear）,则队满的条件为 （ ）。 计 三、简答题 （每题3分，共15分） 算 1、设有三维数组A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为1210， 试求A （1，2，3）所在的地址。 机 与 2、在迷宫问题中求路径可用哪些结构实现，你认为求最短路经有哪种结构比 较合适，为什么？ 软 3、在查找和排序算法中，监视哨的作用是什么？件 4、直接在二叉排序数中查找关键字K与在中序遍历输出的有序序列中查找关 考 键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树， 然后对此树进行查找，其效率如何？为什么？ 研 5、设S1,S2为串，请给出使S1//S2=S2//S1成立的所有可能的条件（//为连 接符）。 四．单选题 （每题2分，共10分） 1．在文件“局部有序”和文件长度较小的情况下，最佳内部排序方法是（ ）： A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D.SHELL排序 2．以 T 为根的二叉树的值定义为：V(T)=V(TL)+1 当 V(TL)=V(TR)时， V(T)=MAX(V(TL),V(TR)) 当V(TL)V(TR)时，其中TL和TR分别是二叉树 T的左、右子树。空树的值为0，此时应用 （A）遍历法求二叉树T的值。 下面以a为根的二叉树的值V(a)=V(b)。 A:(1)前序（2）中序（3）后序 B:(1)0 (2)1 (3)2 (4)3 (5)4 - 3 - 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 追求卓越，挑战极限，从绝望中寻找希望，人生终将辉煌！ 3、顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（A）, 二