班…… …… …… …… …… ……业……专…… …… …… …… …… …… …… …… …… …… ……级…… 线答 …… …… …… …… 院……学…… …… …… …… …… …… 订题 …… …… …… …… …… …… …… …… …… …… …… 装线 …… …… … … …… … … …… ……号……学…… …… …… …… …… … … …… … … ……名……姓…… 西华师范大学学生试卷 2011年 月 日 2011-2012 学年第 1 学期 考室 题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 得分 计算机学院软件工程专业2010级《 数据结构 》试题 A卷 闭卷考试 时间120分钟 注意事项：1.满分：100 分。保持卷面整洁，否则扣卷面 2 分。 2.交卷时请将试题卷与答题卷一起交，否则扣分。 3.学生必须将姓名、班级、学号完整填写在规定的密封栏目内，否则视为废卷。 4.学生必须签到，否则出现遗漏由学生本人负责。 得分 阅卷人 一、选择题（每空3分，共 30 分） 1、数据结构是一门研究非数值计算的程序设计问题中,数据元素的（ ① ） 、数据信息在计算机中的（ ② ）以及一组相关的运算等的课程。 ① A．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2、线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。 A 所有的操作算法实现简单 B 便于随机存取 C 便于插入和删除 D 便于利用零散的存储器空间 3、对于前序遍历与中序遍历结果相同的二叉树为（ ），对于前序遍历与后序遍历结果相同的二叉树为（ ）。 A一般二叉树 B 只有根结点的二叉树 C 根结点无左孩子的二叉树 D 根结点无右孩子的二叉树 E 所有结点只有左子树的二叉树 F 所有结点只有右子树的二叉树 4、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2 5、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。 A． 8 B. 9 C. 10 D. 1 6、已知一个图，如下图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（ ① ）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ② ）。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b
② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b a b e c d f 7、关键路径是事件结点网络中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 得分 阅卷人 二、填空题（每空 3 分，共 30分） 1、构造哈希函数的方法有___________，___________，___________，___________等； 2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3时，从队列中删除一个元素，再加入两个元素后，rear值为___________，front的值为___________； 3、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，根据数据元素之间关系的不同特性，通常有___________、___________、___________和___________4类基本结构。 得分 阅卷人 三、应用解答题（请写出具体操作步骤）（每小题 10 分，共 30 分） 1、已知两个包含n及m个记录的排好序的文件能在O（n+m）时间内合并为一个包含n+m个记录的排好序的文件。当有多于两个的排好序的文件要被合并在一起时只需成对的合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现在有文件f1,f2,f3,f4,f5,各有记录数为20、30、10、5和30试找出记录移动次数最少的合并步骤。（10分）
2、简述拓扑排序的基本思想，并写出下图中的全部拓扑排序。（10分）
3、若有一颗二叉树，左右子树均有三个结点，其左子树的先序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。（10分） 得分 阅卷人
四、算法设计题（每小题 10 分，共 10 分） 1、请写出从二叉排序树中删除结点P的算法。（10分）