《数据结构试卷-A+答案.docx》由会员分享，可在线阅读，更多相关《数据结构试卷-A+答案.docx（8页珍藏版）》请在三一文库上搜索。
1、北京师范大学 2011 2012 学年第 1学期期末考试试卷（ A卷） 课程名称 ：数据结构任课教师姓名：刘玉铭 卷面总分： 100分考试时长： 100分钟考试类别：闭卷院（系）：数学科学学院专 业：年级： 2010姓 名：学 号 ：题号第一题第二题第三题第四题总分得分阅卷教师（签字） ：一、 单项选择题（每题 2 分，共 10 题 20 分）装题号12345678910订答案ABBBBDDCCA1以下那一个术语与数据的存储结构无关？。线A 栈 B哈希表C线索树D双向链表2. 链表不具有的特点是。A. 插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性表长度成
2、正比3. 算术表达式 a+b*（ c+d/e）转为后缀表达式后为。A. ab+cde/* Babcde/+*+Cabcde/*+ Dabcde*/+4. 二维数组 A1020 采用列优先的存储方法 ,若每个元素占 2 个存储单元，设A00的地址为 100，则元素 A76 的存储地址为。A232B234C390D3925若一棵二叉树具有个数是10个度为 2 的结点， 5。个度为 1的结点，则度为 0 的结点A9B 11C15D不确定6. 一棵二叉树中序序列为 FEABDC ，后序序列为 FBADCE ，则层序序列为。A. ABCDEFB.EFCDBAC.FECDABD.EFCDAB7. 在有向图
3、 G 的拓扑序列中，若顶点 Vi 在顶点 Vj之前，则下列情形不可能出现的是。AG 中有弧BG 中有一条从 Vi 到 Vj的路径CG 中没有弧 DG 中有一条从 Vj到 Vi 的路径8. 对于二叉排序树，下面的说法是正确的。A. 二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B. 对二叉排序树进行层序遍历可得到有序序列 C用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/29. 一组记录的关键字为 47 、75、55、30、42、90 ，则用快速排序方法并以第一个记录为支点得到的第一次
4、划分结果是。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、成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。-()5. 若一个广义表的表头为空表，则此广义表亦为空表。-()6. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。-()7. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。-()8 AOE网一定是有向无环图。 -()9. 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。-()10. 倒排文件与多重表文件的次关键字索引结构是不同的。-()三、 填空题（每题 2 分，共 10 题 20 分）1. 带头结点的双循环链表 L 中只有一个元素结点的条件是：L-next-next=L。2. 已知链队列的头尾指针分
6、别是 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的平衡二叉树的结点数至少有3
7、3个。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 表示原子结点）1110a1110e0b0c0d2画出下列由三棵树组成的森林转换为二叉树。adgabcehijbdfklcegfhkilj3 给定一组叶子的权值分别为：8、 6、3、2、7、24，
8、填写下表构造一棵赫夫曼树，并画出该赫夫曼树 ( 同一层的左子树根权值小于右子树根权值)50242611155678234 已知某图的邻接表（ 1）画出此邻接表对应的图；（ 2）写出由 v1 开始的深度优先遍历的序列；（ 3）画出由v1 开始的深度优先的生成树；v1 开始深度优先遍历的序列: v1-v2-v5-v3-v4-v6V1V2V4V2V4V1V5V5V6V6V3V3图生成树HT：weightparentlchildrchild18900268003370042700579006241100758438111078915105110261189115006105. 画出带权无向图的一棵最小
9、生成树。16116221115112194831612553331466181616121612531154312115436666518666. 按 Dijkstra算法计算从顶点A 到其它各个顶点的最短路径和最短路径长度。（写出每一步计算得到的最短路径 和相应的路径长度）源点A终点BCDEV(i)路径i=1i=2i=2i=4路径AB路径长度3路 径 路径长度路径路径长度路径路径长度AC 20 ABC 18ABCD 38AE 45 ABE 43 ABE 43 ABE 43B ABC ABCD ABCDE ABE7. 由字符序列 (t, d, e, s, u, g,)建立一棵平衡的二叉排序树
10、(画出主要过程 )。关键字251638477982513989151231哈希值35532576180哈希地址01234567891011关键字231897925471638825139151比较次数11112123243ttteedddtdtesseeedttdtsusudgug8 已知散列表的地址空间为A0.11，散列函数 H（ k）=k mod 11 ，采用线性探测法处理冲突。请将下列数据 25,16,38,47,79,82,51,39,89,151,231概率情况下查找成功时的平均查找长度。依次插入到散列表中，并计算出在等等概率情况下查找成功时的平均查找长度：（1+1+1+1+2+1+
11、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，6，9，17， 18，19， 20，30，31， 51，55，50，61，71， 100，10110进行置换 - 选择排序时得到归并段长度分别为9，4，7，3，8，6，15，试画出 3 路平衡最佳归并树并求出总的读/ 写次数。最佳归并树 :34678913152452总的读 / 写次数： = （ 3+4+6+7+8+9） *2 + 15） *2 = 178