2014-2015学年二学期数据结构期末考试试卷(A卷).doc

石家庄学院 班级:___________学号:___________姓名:___________得分:___________ 题号 一 二 三 四 五 六 七 八 九 十 成绩 复核 得分 ? ? ? ? ? ? ? ? ? ? ? ? 阅卷 ? ? ? ? ? ? ? ? ? ? ? 题目部分，(卷面共有23题,100分,各大题标有题量和总分) 一、应用题(4小题,共29分) 1．若一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 2．设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？ 3．请回答下列关于堆的一些问题 ? ①堆的存储表示是顺序的，还是链接的? ? ②设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方? ? ③对一个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)? 4．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？ 二、判断正误(4小题,共4分) 1．有n个数顺序(依次)进栈，出栈序列有种。? 2．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(??? ) 3．线性表的逻辑顺序与物理顺序总是一致的（??? ）。 4．?数据元素是数据的最小单位(??? )。 三、单项选择题(6小题,共12分) 1．循环链表H的尾结点P的特点是 A、P^.NEXT:=H???????? B、P^.NEXT:= H^.NEXT??????? C、P:=H????? ??????????D、P:=H^.NEXT 2．一般情况下，将递归算法转换成等价的非递增归算法应该设置 ??? A、堆栈??? B、队列??? C、堆栈或队列? ??D、数组 3．在一棵高度为k的满二叉树中，结点总数为 A、2k-1??????????? B、2k???????????? C、2k-1??????? D、?log2k?+1 4．对有18个元素的有序表作二分(折半)查找，则查找A[3]的比较序列的下标为 ?? A、1、2、3??? B、 9、5、2、3??? C、 9、5、3??? D、 9、4、2、3 5．下面说法错误的是 ???? (1)算法原地工作的含义是指不需要任何额外的辅助空间 ??? （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 ??? （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 ??? （4）同一个算法，实现语言的级别越高，执行效率就越低 A、 (1)?????????????? ?B、 (1),(2)?? C、 (1),(4)?????????? ??D、 (3) 6．设有广义表D(a,b,D),其长度为（? ），深度为 A、∞ ?? ?????? ???????B、3 ?????? ?????? ???C、2??????? ??????? D、5 四、算法设计题(3小题,共35分) 1．编写算法判别给定二叉树是否为完全二叉树。 2．设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。（13分） 3．关于堆排序方法，完成如下工作： ?(1) 简述该方法的基本思想。 (2) 写出堆排序算法。 (3) 分析该算法的时间复杂度。? 五、填空题(5小题,共12分) 1．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 2．设为哈夫曼树的叶子结点数目．则哈夫曼树共有_______个结点。 3．树在计算机内的表示方式有? ??????，??????? ，??????? 。 4．通常元素进栈的操作是_________。 5．?一棵高度为5的满二叉树中的结点数为????????? 个，一棵高度为3满四叉树中的结点数为????????? 个。 六、简答题(1小题,共8分) 1．试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 石家庄学院 2014-2015学年二学期数据结构期末考试试卷(A卷) 答案部分，(卷面共有23题,100.0分,各大题标有题量和总分) 一、应用题(4小题,共8分) 1．据题意，左子树的前序序列与中序序列相同，有 即以左子树为根的树无左孩子。此外，右子树的中序序列与后序序列相同，即有 即以右子树为根的树无右孩子。由此构造该树如下图所示： 2．方法有二