2018年温州医科大学第一临床医学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
本句的有无不影响査找结果
2． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
第 2 页，共 33 页
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
3． 给定nxm 矩阵并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
4． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
5． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
第 3 页，共 33 页
元素\n"，x) ；
【答案】算法如下:
//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回
//在类C 中，一维数组下标从零开始
//两串相等
//算法结束
二、应用题
6． 文件F 由200条记录组成, 记录从1开始编号, 用户打开文件后, 欲将内存中的一条记录插入文件F 中, 作为其第30条记录, 请回答下列问题, 并说明理由。
(1)若文件系统为顺序分配方式, 每个存储块存放一条记录, 文件F 的存储区域前后均有足够空闲的存储空间, 则要完成上述操作最少要访问多少存储块？F 的文件控制区内容会有哪些改变？
(2)若文件系统为链接分配方式, 每个存储块存放的一条记录和一个链接指针, 则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB , 其中4个字节存放指针, 则该系统支撑文件的最大长度是多少？
【答案】(1)因为要最少访问, 所以选择将前29块前移一个存储块单元, 然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出, 再访问目标存储块将数据写入,
所以最少需要访问
块存储块
F 的文件区的文件长度加1, 起始块号减1
(2)采用链接方式则需要顺序访问前29块存储块, 然后将新纪录的存储块插入链中即可, 把新的块存入磁盘要1次访存, 然后修改第29块的链接地址存回磁盘又一次访存。一共就是29+1+1=31次。
4个字节的指针的地址范围为
。
7． 调用下列C 函数f(n)，回答下列问题:
(1)试指出f(n)值的大小，并写出，f(n)值的推导过程；
(2)假定n ＝5, 试指出，f(5)值的大小和执行，f(5)时的输出结果。 C 函数:
第 4 页，共 33 页
所以此系统支撑文件的最大长度为