2018年中山大学数据科学与计算机学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
2． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
3． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
若t 是的右孩子，返回1, 否则返回
后序遍历中序线索二叉树
bt
转向当前结点右分支
结束
4． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
5． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。
【答案】算法如下:
//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间
//pa、pb 是两链表的工作指针
//监视哨
//pa指针后移
//pb指针后移
//处理交集元素
//删除重复元素
//交集元素并入结果表
//置结果链表尾
元素\n"，x) ；
相关内容
相关标签