2017年内蒙古工业大学算法与程序设计之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：
2． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）
元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小
且分布没有规律。用十字链表作存储结构自然失去了随机
最差情况下是
因此也失去
存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为
了随机存取的功能。
3． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部
域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：
（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；
（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。
【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：
图1
（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：
图2
4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：
图2
5． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。
【答案】该二叉树如图所示：