数据结构期末考试题.doc

班级:专业:姓名:考号:密封装订线信息技术学院2006-2007学年第二学期期末考试数据结构试卷30(适用班级:)(答题时间:120分钟,满分:100分)题号第一部分第二部分第三部分第四部分总分核分人得分得分评卷人一、判断题(10分,每题1分),从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。(),在等概率查找情况下,其平均查找长度不公与表的个数有关,而且与每一块中的元素个数有关。(),冒泡排序所执行的比较次数最多。()。(),一定能构造出该树。(),不一定能得到一个有序序列。(),则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。(),且是从源点到汇点的路径中最长的一条。(),再重新插入上去,一定能得到原来的二叉排序树。()。()得分评卷人二、填空题(20分,每空2分)=((X,Y,Z),(A,B,C,D))中的原子B的函数是________。[1..20]中,中,采用二分查找算法查找元素值等于A[12]的元素,所比较过元素的下标依次为________。,则采用________存储方式最节省空间。,每个顶点的度最大可达________。,共有一个孩子的结点数为30,则总结点数为________。,空链域的数目是________。。。,占用辅助空间最多的是________。(堆排序,希尔排序,快速排序,归并排序),其邻接矩阵一定是一个______________得分评卷人三、选择题(20分,每题2分),其结点总数为()。 +1 -,()是执行第一趟快速排序得到的序列(排序的关键字类型是字符串)。A.[da,ax,eb,de,bb]ff[ha,gc] B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha] D.[ax,bb,cd,da]ff[eb,gc,ha],则采用()存储方式节省时间。 ,时间复杂度不受数据初始状态影响,恒为O(nlog2n)的是()。 ,则该二叉树一定是()的二叉树。 ,某一趟结束后未必能选出一个元素放在其最终