《2018年北京市培养单位空间应用工程与技术中心408计算机学科专业基础综合之数据结构考研核心题库.doc》由会员分享，可在线阅读，更多相关《2018年北京市培养单位空间应用工程与技术中心408计算机学科专业基础综合之数据结构考研核心题库.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2018年北京市培养单位空间应用工程与技术中心408计算机学科专业基础综合之数据结构考研核心题库一、算法设计题1 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。【答案】算法如下: 将满二叉树的后序序列转为前序序列，标。 根结点 左子树或右子树的结点数 将左子树前序序列转为后序序列 将右子树前序序列转为后序序列 2 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，N的二叉树的存储结构。和分别指示结点i 的左儿子和右儿子，使) 表示i 的左(右) 儿子为空。试写一个存放结点i 的父亲；然后再写一个判别结点u 是否算法，由L 和R 建立一个一维数组
2、为结点V 的后代的算法。【答案】算法如下: 和 是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组 T 数组初始化 若结点i 的左子女是则结点L 的双亲是结点i若结点i 的右子女是R , 则R 的双亲是i判断U 是否是V 的后代 第 2 页，共 36 页 是序列初始和最后结点的下 本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 3 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。【答案】算法如下: 在用邻接表方式存储的无向图g 中，删除边(i,j)删顶点i 的边结点(i, j) , pre 是前驱指针 释放空间 沿链表继续査找删顶点j 的边
3、结点(j,i) 释放空间 沿链表继续査找 4 已知关键字序列(试写出一算法将(利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下: 假设 是大堆，本算法把 (2) 5 己知L 为链表的头结点地址，表中共有m(m3) 个结点，从表中第i 个结点(li m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。 【答案】算法如下: /L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表/本算法将这部分循环链表倒置第 3 页，共 36 页 ) 是大根堆。) 调整为大根堆；调成大堆 /p是工作指针，初始指向第二结点(已假定i
4、 l) /pre是前驱结点指针，最终指向第i i 个结点 /计数器 /查找第i 个结点 /査找结束，P 指向第i 个结点 /暂存第i 个结点的指针 /p指向第i l 个结点，准备逆置 /上面while 循环结束时，j i 1现从第i 1结点开始逆置 /暂存P 的后继结点+/逆置P 结点 /P恢复为当前待逆置结点/计数器增1 /将原第i 个结点的后继指针指向原第m 个结点 二、应用题6 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？【答案】(1)最高位优先(MSD)法先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的 K 0值，然后，分别就每个子序列对
5、关键字K 1进行排序，按K 1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。(2)最低位优先(LSD)法 先对最低位关键字 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高位关键字K 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。7 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？【答案】(1)动态存储分配伙伴系统的基本思想在伙伴系统中，无论占用块或空闲块，其大小均为(k为大于等于0的正整数) 。若内存容量为，则空闲块大小只能是。由同一大块分裂而得的两个小块互称“伙伴空间”，109如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。第 4 页，共 36 页 一、算法设计题考研试题
