2008_数据结构-b

《2008_数据结构-b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试题：2008年春数据结构-B卷班号：姓名：一、填空题（每题2分，共28分）1.设有一个10阶对称矩阵A采用压缩存储方式（已行序为主序存储：），则的地址为。2.已知广义表，则Head(Tail(Tail(Head(A))))=。3.对于一个具有n个结点的单向链表，在已知P所指结点后插入一个新结点的时间复杂度为；在值域为给定值的结点后插入一个新结点的时间复杂度为。4.表达式的后缀表达式是。5.设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b，d，

2、c，f，e，a，则栈的容量至少应该是。6.已知二叉树有50个叶子结点，则总结点数至少是，最多是。7.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是。8.有数据WG=（7，19，2，6，32，3，21，10），则所建Huffman树的树高为，带权路径长度WPL为。9.G是一个非连通无向图，共有28条边，则该图至少有个顶点。含n个顶点的图形成一个环，则它有棵生成树。10.已知有序记录（2，3，5，7，11，13，17，19，23，29，31，37，41，43，47），用折半查找算法查找关键字为7、41的记录时，比较次

3、数分别为次和次。设有100个结点，用折半查找算法时，最大比较次数为次。11.对一组记录（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取，，其中，，n为待排序记录的个数，则第二趟排序结束后前4条记录依次为。12.若图是可拓扑排序的，则该图中一定存在入读和出度分别为的不同顶点。若某图不能一次完成拓扑排序，则该有向图必定或。13.假定K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行次探测。第4页（共4页）试题：2008年春数据结构-B卷班号：姓名：1.在一棵树中，度为

4、1的结点的个数为，度为2的结点的个数为，……，度为m的结点的个数为，则该树有个叶子结点。二、简答题（共32分）1.请分别简述在中序线索二叉树中求某结点P在中序遍历顺序下的直接前驱（）和直接后继（）的基本思想。（6分）2.请简述利用Kruskal算法、Prim算法和破圈法求图的最小生成树的基本思想。（6分）3.冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。希尔排序和快速排序过程中分别有这种现象吗？如有，请举例说明。（8分）4.一棵二叉树的前序、中序、后序序列如下，其中有部分未标出，试填

5、充完整：（6分）【精析P103】前序序列为：第4页（共4页）试题：2008年春数据结构-B卷班号：姓名：中序序列为：后序序列为：1.已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用链地址法解决冲突，假设装填因子为，Hash函数的形式为，试回答下列问题：（6分）【i】构造Hash函数；【ii】计算等概率情况下查找成功的平均查找长度；【iii】计算等概率情况下查找失败的平均查找长度。五、算法设计（共20分）1.（10分）请设计一种队列，要求：【i】队列的大小不受限制，可根据实际需要进行分

6、配；【ii】队列的入队操作的时间效率是，出队操作的时间效率是；【iii】无需额外的辅助空间来完成队列的入队和出队操作；基于上述要求，根据你设计的队列，实现下列操作：【a】队列的初始化操作；【b】队列的队空和队满判定操作；【c】队列的入队和出队操作；2.（10分）请写出二叉树后序遍历的非递归遍历算法，其中：【i】二叉树采用左右孩子表示法，线索二叉树是对基本结构的相应扩展；【ii】给出存储结构描述，并以伪代码或C++代码方式给出算法的基本描述；第4页（共4页）试题：2008年春数据结构-B卷班号：姓名：第4页（共4页）