2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库
● 摘要
目录
2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库（一） ... 2 2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库（二） ... 8 2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库（三） . 14 2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库（四） . 19 2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研核心题库（五） . 27
一、算法设计题
1． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。
【答案】算法如下:
//la是结点的元素为整数的单链表。本算法判断从第二结点开始
//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回
false
//P是工作指针，初始指向链表的第二项
//pre是p 所指结点的前驱指针
//i是la 链表中结点的序号，初始值为
2
//结点值间的关
系符合题目要求
//当前结点的值不等于其序号的平方减去前驱的值
//未查到表尾就结束了
//成功返回
//算法结束
//假设无头结点，初始P 指向第一元素结点
//初始p ﹣＞next 指向第二项
//失败
//成功
2． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
4． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代
5． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
二、应用题
6． 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2，5，3，4，6。因为根据输入序列，2进桟之后，2出栈，3，4，5依次进栈。5出栈，此时栈中剩下3，4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
7． 请阅读下列算法，回答问题。