2018年青海大学土木工程学院408计算机学科专业基础综合[专业硕士]之数据结构考研核心题库
● 摘要
一、算法设计题
1． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。
【答案】算法如下:
相邻两趟向相反方向起泡的起泡排序算法，
起泡的上下界
设不发生交换
以上向下起泡
有交换，修改标志
change
修改界
气泡下沉，小元素上浮(向左
)
修改下界
2． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
) ；
("字母字符％c 的个数＝
//算法结束。
) ；
3． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间
//置链表尾标记
//注:本算法中也可对B 表不作释放空间的处理
4． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
5． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
元素\n"，x) ；
二、应用题
6． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD(Rl)，R0”的功能为(R0) ＋((R1))—(R1)，即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
下表给出了上述指令取指和译码阶段每个节拍(时钟周期) 的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
【答案】执行阶段每个节拍(时钟周期) 的功能和有效控制信号见下表。