2018年北京市培养单位软件研究所408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
2． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。
【答案】算法如下:
//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点，
应刪除 //删除结点
3． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
4． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如:
第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:
第一个数组
第二个数组
//
【答案】算法如下:
//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列
.
" 交换A[m﹣1]和
B[0]
//寻找A[m﹣1]的插入位置
//寻找B[0]的插入位置
算法结束
5． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；
。其中，data 存放结点的值；lc 、rc 为指向左、
右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。
【答案】算法如下:
先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
设P 指向二叉树的根结点
结束
在中序线索二叉树T 中,, 求给定值为x 的结点的
后继结点
首先在T 树上査找给定值为x 的结点，由p 指向
' 若P 的右标志为1, 则P 的rc 指针指向其后继
结点P 的右子树中最左边的结点是结点P 的中序后继
结库
.
二、应用题