数据结构试卷-A答案.doc

北京师范大学20112012学年第 1 学期期末考试试卷（A卷）课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 题号第一题第二题第三题第四题总分得分阅卷教师（签字）： 装 订 线一、 单项选择题（每题2分，共10题20分）题号12345678910答案ABBBBDDCCA1 以下那一个术语与数据的存储结构无关？ 。A栈 B哈希表 C线索树 D双向链表2 链表不具有的特点是 。A插入、删除不需要移动元素 B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性表长度成正比3 算术表达式a+b*（c+d/e）转为后缀表达式后为 。Aab+cde/*Babcde/+*+Cabcde/*+Dabcde*/+4 二维数组A1020采用列优先的存储方法,若每个元素占2个存储单元，设A00的地址为100，则元素A76的存储地址为 。 A232B234C390D392 5 若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是 。A9B11C15D不确定6 一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为 。A. ABCDEFB. EFCDBAC. FECDABD. EFCDAB7 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是 。AG 中有弧BG 中有一条从Vi 到Vj 的路径CG 中没有弧DG 中有一条从Vj 到Vi 的路径8 对于二叉排序树，下面的说法 是正确的。A二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B对二叉排序树进行层序遍历可得到有序序列C用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/29 一组记录的关键字为47、75、55、30、42、90，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是 。A. 30,42,47,55,75,90B. 42,30,47,75,55,90C. 42,30,47,55,75,90D. 42,30,47,90,55,7510 下述文件中适合于磁带存储的是 。A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件二、 判断（每题1分，共10题10分）题号12345678910答案1 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。-( )2 KMP 算法的特点是在模式匹配时指示主串的指针不会变小。-( )3 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. -( )4 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。-( )5 若一个广义表的表头为空表，则此广义表亦为空表。-( )6 完全二叉树中，若一个结点没有左孩子，则它必是树叶。-( )7 一个有向图的邻接表和逆邻接表中结点的个数可能不等。-( )8 AOE 网一定是有向无环图。-( )9 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。-( )10 倒排文件与多重表文件的次关键字索引结构是不同的。-( )三、 填空题（每题2分，共10题20分）1 带头结点的双循环链表L 中只有一个元素结点的条件是： L-next-next=L 。2 已知链队列的头尾指针分别是f 和r，则将s指向的结点入队的操作是 r-next=s；r=s 。3 广义表A( ),(a,(b),c)，head(tail(head(tail(head(A)等于 (b) 。4 高度为5 的完全二叉树至少有 8 个叶子结点5 一棵树T中，包括一个度为1的结点，两个度为2 的结点，三个度为3 的结点，四个度为4 的结点和若干叶子结点，则T 的叶结点数为 1+2*1+3*2+4*3 = 21 。6 求图的最小生成树有两种算法中， prim 算法适合于求稠密图的最小生成树。7 具有10 个关键字的有序表，折半查找的平均查找长度 2.9 。8 高度为7的平衡二叉树的结点数至少有 33 个。9 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是 m-1 。10 对n个记录进行简单选择排序，所需进行的关键字间的比较次数为 1+2+3+(n-1) = n(n-1)/2 。四、 简答题（每题5分，共10题50分）1 画出广义表（a，（b，c，d），e）的存储结构图（采用头尾指针的链表结构，标志1表示表结点，标志0表示原子结点）1111110a0b0c0d0eabcdefghijkl2 画出下列由三棵树组成的森林转换为二叉树。abcdefghijkl3 给定一组叶子的权值分别为：8、6、3、2、7、24，填写下表构造一棵赫夫曼树，并画出该赫夫曼树(同一层的左子树根权值小于右子树根权值)HT：weightparentlchild6243278511152650rchild18900268003370042700579006241100758438111078915105110261189115006104 已知某图的邻接表（1）画出此邻接表对应的图；（2）写出由v1 开始的深度优先遍历的序列；（3）画出由v1 开始的深度优先的生成树；v1 开始深度优先遍历的序列:v1-v2-v5-v3-v4-v6V1V2V3V4V5V6图V1V2V3V4V5V6生成树124536331814191621118565 画出带权无向图的一棵最小生成树。112161231651236165612436161156124536181611566 按Dijkstra算法计算从顶点A到其它各个顶点的最短路径和最短路径长度。（写出每一步计算得到的最短路径和相应的路径长度）源点AV(i)路径终点BCDEi=1路径路径长度AB3AC20 AE45BABi=2路径路径长度ABC18 ABE43CABCi=2路径路径长度ABCD38ABE43DABCDi=4路径路径长度ABE43EABE7 由字符序列(t, d, e, s, u, g,)建立一棵平衡的二叉排序树(画出主要过程)。ttdtdetdetdestdesutdesugtdesug8 已知散列表的地址空间为A0.11，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据25,16,38,47,79,82,51,39,89,151,231依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。关键字251638477982513989151231哈希值35532576180哈希地址01234567891011关键字231897925471638825139151比较次数11112123243等概率情况下查找成功时的平均查找长度：（1+1+1+1+2+1+2+3+2+4+3）/11=21/119 已知序列101，51，19，61，3，71，31，17，18，100，55，20，9，30，50，6，请采用希尔排序对该序列作升序排序，给出每一趟排序结果（设：d1=5，d2=3，d3=1）第1趟: 6，20， 9，18， 3，55，31，17，30，50，71，51，19，61，100，101第2趟: 6， 3， 9，18，17，30，19，20，51，31，61，55，50，71，100，101第3趟: 3，