2018年厦门大学智能科学与技术系408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针
邻接表
修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。
用邻接表作为存储结构的深度优先遍历算法
第一邻接点
结束dfs （ ）
求顶点的度
若顶点度为0, 或顶点的度不是偶
数，无解
无解
2． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
3． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
4． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
【答案】算法如下:
//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回
//在类C 中，一维数组下标从零开始
相关内容
相关标签