2018年同济大学测绘与地理信息学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
2． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
3． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表
查找成功时的平均查找长度
。
4． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
5． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数