2018年北京市培养单位中丹学院864程序设计之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
2． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【答案】算法如下:
//L是带头结点的按访问频度递减的双向链表
//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中
//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置
//查找值为x 的结点
("不存在所査结点\n”) ；exit(0)；
//令元素值为x 的结点的freq 域加
1
//将P 结点从链表上摘下
//以下査找P 结点的插人位置
//将P 结点插人
//返回值为x 的结点的指针
//算法结束
3． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
4． 设要求按
是一个记录构成的数组，是一个整数数组，其值介于1〜100之间，现
的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]
中去。规定可使用的附加空间为O(1)。
【答案】算法如下:
//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序
//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整
//B[j]和B[k]交换
//r0是数组A 的元素类型，A[j]和A[k]
交换
//完成了一个小循环，第i 个已经安排好
//算法结束
5． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
二、应用题
6． 设包含4个数据元素的集合
各元素的查找概率依次为:请回答：
(1)若采用顺序存储结构保存S , 且要求平均查找长度更短, 则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
, 。
。
将S 保存在一个长度为4的顺序表中, 采用折半查找法, 查找成功时的平均查找长度为
相关内容
相关标签