第五套数据结构自测题

第五套数据结构自测题内容摘要：

过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做 __________排序。 11. 快速排序在平均情况下的空间复杂度为 ____________。 12. 若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为 ________。 三、判断题，在每小题前面打对号表示正确或打叉号表示失败（每小题 1分 ， 共 10分） 1. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。 3. 在一个顺序存储的循环队列中 , 队头指针指向队头元素的后一个位置。 4. 用非递归方法实现递归算法时一定要使用递归工作栈。 5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。 6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。 7. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。 8. 对于 AOE网络，加速任一关键活动都能使整个工程提前完成。 9. 直接选择排序是一种稳定的排序方法。 10. 闭散列法通常比开散列法时间效率更高。 四、运算题（前 2小题，每小题 6分，后 3小题，每小题 8分，共 36分） 1. 设有一个二维数组 A[10][20]，按行存放于一个连续的存储空间中， A[0][0]的存储地址是 200，每个数组元素占 1个存储字，则 A[6][2]的存储字地址是多少。 2. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为 1）和度为 度为 1及度为 0的结点个数。 中序序列： c,b,d,e,a,g,i,h,j,f 后序序列： c,e,d,b,i,j,h,g,f,a 3. 假定一组记录为 (36,75,83,54,12,67,60,40)，将按次序把每个结点 插入到初始为空的一棵 AVL 树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少。 4. 已知一个带权图的顶点集 V和边集 G分别为： V={0,1,2,3,4,5,6}。