2018年武汉大学卫星导航定位技术研究中心942数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 设数组址为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
2． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为。
3． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
4． 阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
第 2 页，共 54 页
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存
储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
5． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
7．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
8． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
9． 试利用下列栈和串的基本操作完成下述填空题。
initstack(S)置S 为空栈； push(S，X) 元素X 入栈； pop(S)出栈操作； gettop(S)返回栈顶元素； sempty(S)判栈空函数； setnull(St)置串St 为空串； length(st)返回串st 的长度；
第 3 页，共 54 页
equal(S1，S 2) 判串S 1并S 2是否相等的函数； concat(S1，S 2) 返回联接S 1和S 2之后的串； sub(S，i ，1) 返回S 中第i 个字符；
empty(st)判串空函数
FUNCinvert(pre:string ；V ARexp :string) :boolean ；
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。
)
_____；_____；
_____THEN_____
IF_____THEN_____
(_____，_____)；
(_____，_____)；
_____
_____THEN
注意:每个空格只填一个语句。
【答案】(1)initstack(S)//栈s 初始化为空栈 (2)setnull(exp)//串exp 初始化为空串 (3)chinopset//判取出字符是否是操作符
(4)push(s，ch)//如ch 是运算符，则入操作符栈s (5)sempty(s)//判栈s 是否为空
(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理 (7)exp
(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式 (9)exp
(10)gettop(s)//取栈顶操作符 (11)pop(s)//操作符取出后，出栈
(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后
第 4 页，共 54 页
相关内容
相关标签