华科2010级数据结构期末考试试题-A卷.docVIP

《数据结构》考试题（闭卷） A卷 （电信系本科2010级 2012年1月11日） 姓名 班级 学号 题 号 一 二 三 总分 题 分 40 30 30 100 得 分 一、回答下列问题 (每题5分，共40分) 1．采用哪种方法可构建表示表达式的二叉树，画出表示表达式A-B/(C+D)+E*F的二叉树，并给出后序遍历结果。 采用表达式求值方法 + * A / E F B + C D 后序遍历结果 ABCD+/-EF*+ 2.待排序列有256个关键字，采用锦标赛排序排出最小三个关键字的比较次数是多少？需多少个辅助空间。锦标赛排序空间复杂度是多少？ 比较次数 255+8+8 辅助空间 255+1 空间复杂度 o(n) 3．对n个记录的线性表进行快速排序，为减少算法的递归深度（空间），以下叙述正确的是（ ） A．每次分割后，先处理较短的部分 B．每次分割后，先处理较长的部分 C．与算法每次分割后的处理顺序无关 D．以上三者都不对 4．在KMP算法中，已知模式串为ACBACBBAD, 写出模式串的next[j]函数值，若主串为ADACBACACBACBBADABD, 给出匹配成功的比较次数。 next[j]函数值 0 1 1 1 2 3 4 1 2 比较次数 2+1+6+3+9 5．在二叉树的前、中、后序遍历序列中，所有叶子结点间的先后关系都是相同的。这个结论对吗？为什么？ 6．一输入序列（38，17，29，22，58，82，19，16），画出二叉排序树, 并计算平均查找长度ASL。输入序列在哪种情况下，二叉排序树查找与顺序查找比较次数相同？ 38 17 58 22 29 82 16 19 ASL=(1 + 2*2 + 3*3 + 4*2)/8 输入序列为有序序列时相同 7．设Hash表的冲突采用线性探测散列，给定一个待查找元素x，如果x不在Hash表中，如何给出判别准则，简单分析你的结论。 8．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为多少？ 二、综合题（共30分） 1. 下面是用c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。（6分） void reverse（linklist L）{ p=null；q=L； while（q！=null） { (1)__________________ ; q-next=p；p=q；(2)__________________ ; } (3)_____________________; } 2．设有5 个互不相同的元素a、b、c、d、e，能否通过7 次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。（9分） 3．在排序算法的某一存储结构中，有n个关键字存在一维向量K中，0号单元未用，试给出以下函数的功能及返回值0，-1，1，2的含义（8分） int SortL(sqlist k, int n) { if(n==0) return(0); if (a[1]a[2]) { for( i= n/2; i=1; i --) if (a[i]a[2*i]|| a[i]a[2*i+1]) return(-1); return(1); }; else{ for( i= n/2; i=1; i--) if (a[i]a[2*i]|| a[i]a[2*i+1]) return(-1); return(2); }; } 1. 该函数为判断是否是堆的函数 2. 函数返回值 0 表示空，-1 表示不是堆，1表示大根堆，2表示小根堆 4．已知一有向图的邻接链表存储结构如图所示。（7分） 试画出该图结构； 试给出以顶点0为出发点的深度优先有哪些信誉好的足球投注网站遍历序列 三、 算法设计题（每题10分，共30分） 1．设将n(n1)个整数存放到一维数组R中。设计一个时间和空间两方面尽可