《数据结构试卷A卷及答案》由会员分享，可在线阅读，更多相关《数据结构试卷A卷及答案（5页珍藏版）》请在金锄头文库上搜索。
1、1 计算机科学与技术学院2009 年春季学期2007 级计算机科学与技术、网络工程本科数据结构期末考试试卷（A 卷、闭卷）一、选择题（单选题，每小题3 分，共 33 分）1已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。ABCDEAF BABDCEF CDBACEF DDABECF 2在 11 个元素的有序表A1 11 中进行折半查找（2/ )(highlow） ，查找元素A11 时，被比较的元素的下标依次是。A 6，8，10，11 B6， 9，10，11 C6，7，9，11 D 6，8，9，11 3由元素序列（27，16，75，38，51）构造平衡二叉树
2、，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2 的结点）为。A 27 B38 C51 D75 4利用逐点插入法建立序列（50，72，43 ，85，75，20， 35， 45，65，30 ）对应的二叉排序树以后，查找元素30 要进行次元素间的比较。A 4 B 5 C6 D7 5循环链表的主要优点是。A不再需要头指针了B 已知某个结点的位置后，很容易找到它的直接前驱结点C在进行删除后，能保证链表不断开D 从表中任一结点出发都能遍历整个链表6已知一个线性表（38，25，74，63，52，48） ，假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A0
3、6 中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。A 15 B17 C20 D23 7由权值为9，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。A 23 B37 C44 D46 8在最好和最坏情况下的时间复杂度均为O（nlogn ）且稳定的排序方法是。A基数排序B快速排序C堆排序D归并排序9无向图 G=(V ，E)，其中 V=a ，b，c，d，e，f ，E=(a ，b)， （a，e） ，(a，c)， （ b，e） ， （c，f） ，(f，d)， （e，d）。对该图进行深度优先遍历，下面不能得到的序列是。A aebdcf Babedf
4、c Caedfcb Dacfdeb 10置换 -选择排序的功能是。A产生初始归并段B选出最大的元素C产生有序文件D置换某个记录11ISAM 和 VSAM 文件属于。A索引顺序文件B索引非顺序文件C顺序文件D散列文件二、填空题 ( 18 每空 2 分， 912 每空 1 分，共 20 分）1下面程序段的时间复杂度为【1】。Sum=1; For (i=0; sumrchild=p) /右子树不存在或已被访问, 访问之 ; /访问根结点Pop(S,p); /退栈p=t; /p指向已被访问的结点else t=t-rchild; /t指向右子树tag=0; /设置未被访问的标记 while( ); re
5、turn OK; 四、解答题（共20 分）1 （6 分）已知模式串p= cbcaacbcbc ，求出 p 的 next 数组值和nextval 数组值。j 1 2 3 4 5 6 7 8 9 10 模式串 pc b c a a c b c b c NextjNextvalj2 （6 分）已知一组关键字为21，33，12，40，68， 59，25，51 ，(1) 试依次插入关键字生成一棵3 阶的 B-树；(2) 在生成的3 阶 B-树中依次删除40 和 12，画出每一步执行后B-树的状态。3 （8 分）试对右图所示的AOE 网络，解答下列问题。(1) 求每个事件的最早开始时间Vei 和最迟开始时
6、间Vli 。1 2 3 4 5 6 Ve Vl (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。e l l- e (3) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。(4) 这个工程最早可能在什么时间结束。五、算法设计题（9 分）完成以下算法，对单链表实现就地逆置。void LinkList_reverse(Linklist 为简化算法 ,假设表长大于2 Linklist p,q,s; p=L-next; q=p-next; s=q-next; p-next=NULL; 4 2009 年春季学期 2007 级计算机科学与技术专业本科
7、数据结构期末考试试卷（A 卷、闭卷）试题答案及评分标准一、选择题（单选题，每小题3 分，共 33 分）1 2 3 4 5 6 7 8 9 10 11 B B D B D C C D A A A 二、填空题 ( 18 每空 2 分， 912 每空 1 分，共 20 分）【1】【2】【3】【4】【5】【6】O(n) O(tu+nu) O(nu) (b，c，d) 22) !()!2(1111nnnCnn n或14 【 7】【8】【9】【10】【11】【12】692 69 快速排序二路归并排序堆排序链式基数排序三、算法填空题(每空 3 分，共 18 分）1M.datat.j numcol-1 +cpo
8、tcol 2t=t-lchild Visit(t-data) !StackEmpty(S) 四、解答题（共 20 分）1 (6 分) 2 (共 6 分) (1) (2 分 ) 3 阶 B-树为：(2) （4 分）删除 40 后 B-树的状态删除 12 后 B-树的状态3(8 分) 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl 。然后再计算各个活动的最早可能开始时间e 和最迟允许开始时间l，根据 l - e = 0? 来确定关键活动，从而确定关键路径。(1) 每个事件的最早开始时间Vei和最迟开始时间Vli j 1 2 3 4 5 6 7 8 9 10 模式串 pc
9、b c a a c b c b c Nextj0 1 1 2 1 1 2 3 4 3 Nextvalj0 1 0 2 1 0 1 0 4 0 5 2 3 4 5 6 Ve 0 15 19 29 38 43 Vl 0 15 19 37 38 43 (2) 每个活动的最早开始时间e( )和最迟开始时间l( )e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l- e 17 0 0 8 0 12 8 0 (3) 关键活动为：， ，；加速这些活动可使整个工程提前完成；由所有关键活动构成的图：（关键路径为： ）(4) 此工程最早完成时间为43。五、算法设计
10、题（9 分）试写一算法，对单链表实现就地逆置。void LinkList_reverse(Linklist 为简化算法 ,假设表长大于2 Linklist p,q,s; p=L-next; q=p-next; s=q-next; p-next=NULL; 解：while (s-next) q-next=p; p=q; q=s; s=s-next; /把 L 的元素逐个插入新表表头 q-next=p; s-next=q; L-next=s; /LinkList_reverse 分析：本算法的思想是,逐个地把L 的当前元素q插入新的链表头部，p 为新表表头。1 3 2 6 5 15 4 19 5
