2018年北京大学前沿交叉学科研究院907计算机专业基础之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
本句的有无不影响査找结果
2． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
3． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。
【答案】算法如下:
第 2 页，共 36 页
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A
链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点，
应刪除 //删除结点
4． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
5． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
) ；
) ；
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
第 3 页，共 36 页
向左
向右
访问根结点
找被访问结点的双亲
结束
二、应用题
6． 阅读下面的算法，说明算法实现的功能。
【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。headl 最后一个结点的链域指向head2，head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。
7． 某文件系统空间的最大容量为, 以磁盘块为基本分配单位, 磁盘块大小为1KB 。文件控制块(FCB)包含一个512B 的索引表区。请回答下列问题。
(1)假设索引表区仅采用直接索引结构, 索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
(2)假设索引表区采用如下结构:第0〜7字节采用<起始块号, 块数>格式表示文件创建时预分配的连续存储空间, 其中起始块号占6B , 块数占2B ; 剩余504字节采用直接索引结构, 一个索引项占6B , 则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大, 请指出起始块号和块数分别所占字节数的合理值并说明理由。
【答案】(1)文件系统存储空间共有块数为表示
个块号, 索引表项占
每个索引项对应一个磁盘块, 故最大文件长度:
(2)块号占6字节, 块数占2字节的情形下, 最大文件长度:
。
合理的起始块号和块数所占字节数分别为
(
或
或
或
或
) 。理由:
。
, 512B 可存放个索引项,
。
第 4 页，共 36 页
相关内容
相关标签