资源描述：
《数据结构试卷A.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、hhh河北大学课程考核试卷2006—2007学年第1学期04级测控专业（类）考核科目数据结构课程类别选修课考核类型考试考核方式闭卷卷别A（注：考生务必将答案写在答题纸上，写在本试卷上的无效）一、选择题：（共20分，每小题2分）1、数据结构是一门研究非数据计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。A.结构B.关系C.运算D.算法2、线性表采用链式存储时，其地址（D）0A,必须是连续的B.一定是不连续的C.部分地址必须连续D.连续与否均可3、若某链表中最常用的操作为在最后一个结点之
2、后插入一个结点和删除最后一个结点，则采用（D）存储方式最节省时间。A.双链表B.单链表C.单循环链表D.带头结点的双循环链表4、一个栈的序列是：a,b,c,d,e,则栈不可能的输出序列是（C）。A.a,b,c,d,eB.d,e,c,b,aC.d,c,e,a,bD.e,d,c,b,a5、栈和队列的共同点是AA.只允许在端点处插入和删除B.FIFOC.LIFOD.无6、在下列排序算法中，不稳定的为—B。A.直接插入排序B.希尔排序C.直接选择排序D.冒泡排序7、已知一个满二叉树，有n个叶结点，则二叉树中
3、一共有（C）个结点。A.2n-1B.2nC.2n-1D.2n+18、已知某二叉数的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序dgbaechf,则其后序遍历的结点访问顺序是（D）。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca9、设一棵二叉树度为2的结点数是7,度为1的结点数是6,则叶子结点数是（C）＜A.6B.7C.8D.910、无向图的邻接矩阵是一个（A）。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵二、名词解释题：（共20分，每小题5分）
4、1、队列队列可以看成是一种运算受限的线性表，在这种线性表上，插入限定在标的某一端进行，删除限定在标的另一端进行。允许插入的一端称为队尾，允许删除的一端称为对头。2、二叉树二叉树（BinaryTree）是n（n结点的有限集，它或者是空集（n=0）,或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成3、生成树4、连通图三、解答题：（共50分）1、设有三个元素A,B,C进栈，给出它们所有可能的出栈次序。（5分）先进先出：结果是a,b,c。先进后出：结果是c,b,a。2、写出对关键
5、字序列（23,76,47,53,41,12,6,85,30,90）进行快速排序的每一趟结果（由小到大）。（10分）（23,76,47,53,41,12,#6,85,30,90）（6,#23,76,47,53,41,12,85,30,90）（6,76,47,53,41,12,23,85,30,90）3、在关键字序列（07,12,15,18,27,32,41,92）中用二分查找法查找和给定值92相等的关键字，请画出二分判定树及查找的全部过程。（10分）4、下图表示一个地区的通讯网，边表示城市间的通讯线路
6、，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出其中一种的构造全过程。（应用Prim算法）（10分）5、已知电文中有A、B、C、D和E五个字符，它们出现的概率分别为0.20、0.15、0.25、0.08和0.32,请构造哈夫曼树并画出全过程，给出其哈夫曼编码序列。（8分）A-3-26、设二叉树t的中序序列为BADCE后序序列为BDECA请给出二叉树并写出该二叉树的前序序列的次序。（7分）四、编程题：（共10分）已知带头结点的单链表L中的结点是按整数值递减排列的
7、，写一算法，将值为x的结点插入到表L中，使得表L仍然有序。A-3-3
