2018年郑州大学联合培养单位安阳师范学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为 2． 对给定关键字序号j(1 。 中找到关键字从小到大排在第j 位上的记 长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。 【答案】算法如下: 在用邻接表方式存储的无向图g 中，删除边(i, j) 删顶点i 的边结点(i, j) , pre 是前驱指针 释放空间 沿链表继续査找 删顶点j 的边结点(j, i) 释放空间 沿链表继续査找 4． 设排序二叉树中结点的结构为下述三个域构成: Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。 【答案】算法如下: 非递归删除以r 为根的二叉排序树 栈，容量足够大，栈中元素是二叉排序树结点的指针 沿左分枝向下 出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间 在二叉排序树T 中删除所有小于等于x 的结点 根结点的值小于等于 x 删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止 沿根结点左分支向下，査小干等于x 的结点 q 记P 的双亲 结点的值小于等于 x 再査原P 的右子树中小于等于x 的结点 5． 设有一个数组中存放了一个无序的关键序列 【答案】算法如下: 。现要求将K n 放在将元素排序后 的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。 二、应用题 6． 分析ISAM 文件( VSAM 文件( ) 和 ) 的应用场合、优缺点等。 【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。 VSAM 文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。 优缺点:与ISAM 文件相比，VSAM 文件有如下优点:动态分配和释放存储空间，不需对文件
相关内容
相关标签