2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
目录
2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库（一） ... 2 2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库（二） ... 9 2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库（三） . 15 2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库（四） . 22 2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研核心题库（五） . 28
第 1 页，共 34 页
一、算法设计题
1． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。
【答案】算法如下:
//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性
//题目要求下标从1开始
//对分査找元素x 的插入位置
//元素后移
//将元素x 插人
算法结束
设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。
时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。
2． 设是一个记录构成的数组，要求按
中去。规定可使用的附加空间为O(1)。
【答案】算法如下:
//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序
第 2 页，共 34 页
是一个整数数组，其值介于1〜100之间，现
的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]
//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整
//B[j]和B[k]交换
//r0是数组A 的元素类型，A[j]和A[k]
交换
//完成了一个小循环，第i 个已经安排好
//算法结束
3． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
第 3 页，共 34 页
4． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点
f
从结点c 的双亲结点直到根结点，
路径上所有结点均为祖先结点
逆序输出，最老的祖先最后输出
结束
5． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
第 4 页，共 34 页
相关内容
相关标签