数据结构模拟题(5)

1、数据结构模拟题（5）一、填空题:06分，每题02分 1、 一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点k的所有祖先的结点数为_个。 2、 在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过_。3、 在n(n0)个顶点的连通无向图中所有顶点的度数之和最少为_。二、单选题:10分，每题02分 4、 一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。 A:所有域长度之和 B:最大域所占字节长度 C:任意一个域长度 D:sizeof(r)的值 5、 将递归求解过程改变为非递归求解过程的目的是

2、（ ）。 A:提高速度 B:改善可读性 C:增强健壮性 D:提高可维护性 6、 对长度为n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为( )。 A:n/2 B:(n+1)/2 C:(n-1)/2 D:n/4 7、 图的深度优先搜索类似于树的（ ）次序遍历。 A:先根 B:中根 C:后根 D:层次 8、 在10阶B树中根结点所包含的关键码个数最少为（ ）。 A:0 B:1 C:3 D:4 三、判断题:10分，每题01分 9、 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构 10、如果采用如下方式定义一维字符数组： const int maxSiz

3、e = 30; char amaxSize; 则这种数组在程序执行过程中不能扩充。 11、 在对双向循环链表做删除一个结点的操作时，应先将被删除结点的前驱结点和后继结点链接好再执行释放结点操作。 12、 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。 13、 进行折半搜索的表必须是顺序存储的有序表。 14、 假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。 15、 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。 16、 对于AOE网络，任一关键活动延迟将导致整

4、个工程延迟完成。 17、 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 18、 图的广度优先搜索算法通常采用非递归算法求解。四、中型计算题:10分，每题10分 19、 假定一个大根堆为(64,38,55,20,15,44,18,12)，则从中删除一个元素后得到的堆为 五、小型计算题:40分，每题08分 20、 设有一个二维数组A1020，按行存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占1个存储字，则A62的地址是多少。21、假定一组记录为(40,28,16,56,50,32,30,63)，按次序插入每个结点生成一棵AVL树，根据插入过程填写下

5、表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。 22、 已知一个图的顶点集V和边集G分别为： V=1,2,3,4,5,6; E=,6,5; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即dest域的值）从大到小的次序链接的，试按照遍历算法写出： (1) 从顶点1出发进行深度优先搜索所得到的顶点序列； (2) 从顶点1出发进行广度优先搜索所得到的顶点序列。 23、已知一个AOE网络的顶点集V和边集G分别为： V=0,1,2,3,4,5; E=2,15,12,9,4,11,5,10; 若存储它

6、采用邻接表，则按主教材中介绍的求关键路径的方法，依次写出所有的关键活动（用边表示），并求出关键路径长度（提示：先画出对应的图形，然后再运算）。 所有关键活动： 关键路径长度 24、设散列表的长度m=11，散列函数为H(K)=K mod m，采用线性探查法解决冲突，被依次插入的关键码序列为1,13,12,34,38,33,27,22。根据构成的散列表回答： (1) 在等概率的情况下，搜索成功时的平均搜索长度； (2) 在等概率的情况下，搜索失败时的平均搜索长度。 六、综合题:20分，每题10分 25、 写出下列程序段的输出结果: void main(） stack S; char x,y; S.InitStack( ); X=c;y=k; S.Push(x); S.Push(a); S.Push(y); S.Pop(S,x); S.Push(t); S.Push(s); While(!S.IsEmpty() S.Pop(y); couty; Coutydata=x) _(2)_; else BinTreeNode* t; if(t=BTF(BT-left, x) _(3)_; _(4)_;