97长沙铁道学院攻读硕士学位研究生入学考试

97长沙铁道学院攻读硕士学位研究生入学考试 97 直接在二叉排序数中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后 对此树进行查找，其效率如何 ... 关键字 专 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 技术 牛档搜索（Niudown.COM） 本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内 涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。 不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律 责任 安全质量包保责任状安全管理目标责任状8安全事故责任追究制幼儿园安全责任状占有损害赔偿请求权 ！ 97长沙铁道学院攻读硕士学位研究生入学考试 数据结构 一. 是非题(共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. 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（A）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（B）。在此假定N为线性表中结点数，且每次查找都是成功的。A,B: (1)N+1 (2)2logN (3)logN (4)N/2 (5)NlogN (6)N*N 五． 综合题 1． 设有三对角矩阵A[1:N][1:N], 将其三对角线上的元素逐行地存于 B[1:3N-2]中，使得B[K]=A[i][j], 求：（1）用i,j表示K的下标变 换公式，（2）用K表示i,j的下标变换公式。（10分） 2． 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 （10分） 3． 试利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径， 写出执行算法过程中各步的状态。（10分） 4． 试推导含12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 （10分） 5． 假设某线性表的关键字序列为（61，2378，789，345，8423，1125， 890，776，4683，553，213，8679，12287），按装填因子=13/17，将 关键字存入散列表中，散列函数为H(k)=k mod 17,H(k)=(k mod 15)+3, 试采用双散列函数探测法处理冲突，画出相应的散列表，并计算在等 概率下查找成功的平均查找长度。（10分） 6． 编写将一棵二叉树中序线索画的算法。（10分）要求：（1）结点结构; (2)变量说明； （3）具体算法。（用C或PASCAL均可） 长沙铁道学院九八年攻读硕士研究生入学考试 数据结构 要求：说明算法的基本思想，主要变量和数据结构类型。可用PASCAL或C语言。 一. 判断题（ 10分） 1. 设模式串的长度为m,目标串的长度为n，当n?m且处理只匹配一次时， 朴素的匹配（即子串定位函数）算法所花的时间可能更少。 2. 后序线索二叉树是不完善的，要对它进行遍历，还要使用栈。 3. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将 这个记录的所在位置置空，因为这会影响以后的查找。 4. 插入和删除操作是数据结构中最基本的两种操作，所以这 两种操作在数组中也经常使用。 5. 文件是记录的集合，每个记录由一个或多个数据项组成， 因而一个文件可看作由多个记录组成的数据结构。 6. 堆排序所须的时间与待排序的记录个数无关。 7. 磁盘的优点是容量比磁带大。 8. 用邻接矩阵A表示图，判定任意两顶点V1和V2之间是否 有长度为m的路径相连，只要检查Am的第I行，第j列 的元素是否为0即可。 9. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树 却是一样的。 10. 当待排序的元素很大时，为了交换元素的位置，移动元素 要占用较多的时间，这是影响时间复杂度的主要因素。 二. 填空题（20分） 1. 在磁带上的顺序文件中插入新的记录时，必须（ ）。 2. 对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为（ ），利用Kruskal算法生成最小代价生成树其时间复杂 度为（ ）。 3. 哈夫曼树是（ ）。 4. 所需读写的扇区旋转到磁头下方的所需时间称为（ ）。 5. 快速排序在（ ）的情况下最易发挥其长处。 6. 索引顺序文件是最常用的文件组职之一，通常用（ ）结构来组织索引。 7. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可 采用（ ）查找方法。 8. 当广义表中的每个元素都是原子时，广义表便成了（ ）。 9. 有向图G可拓扑排序的判别条件是（ ）。 三. 选择题 （18分） 1. 某而茶树T有n各界点，设按某种顺序对T中的每个结点进行编号，编 号为1，2，… ，n，且有如下性质：T重任一节点V，其编号等于左子树 上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上 结点的最大编号加1。这时是按（ ）编号的。 A． 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次顺序 2. 如果把某作业工程表示成网络的话, 则如图1所示,其中各箭头上的数字表示所需天数。 （1）事件5的最早完成时间是（ ）天。（2）事件4的最迟开始时间是（ ）天。（3）关键路径是（ ）。 A. 15 B. 19 C. 23 D. 27 E. 30 F. 32 G. 34 H. 1,2,5,6,10 I. 1,4,7,9,10 J. 1,4,7,8,9,10 3. 动态存储管理系统中，通常可有（ ）种不同的分配策略。 A． 1 B. 2 C. 3 D. 4 E. 5 4. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。 A． （a） b. A C. a D. (b) E. b F. (A) 四. 简答题 (每题6分, 共30分) 1. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都 有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 2. 试提出三种判断一个图是否有圈的方法. 3. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 4. 对一个有t个非零元素的Am*n 矩阵, 用B[0..t][1..3]的数组来表 示，其中第0行的三个元素分别为m,n,t, 从第一行开始到最后一行， 每行表示一个非零元素；第一列为矩阵元素的行号， 第二列为其列号， 第三列为其值。对这样的表示法，如果需要经常进行该操作—确定任 意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以 使时间得到改善？ 5. 在内排序的过程中，通常需要对待排序的关键字集合进行多遍扫描。 采用不同排序方法，会产生不同的中间结果。设要将序列 （Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键字按字母序的升序重新排列， 请分别给出对该序列进行冒泡排序，初始步长为4的希尔排序，二路 归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结 果，并给出对该序列作堆排序时初始建堆的结果。 五. 算法设计题 1. 试写一个判别给定二叉树是否为二叉排序树的算法。(12分) 2. 求图的中心电的算法。设V是有向图G的一个顶点，我们把V的偏心 度定义为：max(从w到v的最短距离/w是g中所有顶点)，如果v是 有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。（10 分）