2017年北京师范大学政府管理学院986软件基础考研仿真模拟题
● 摘要
一、应用题
1． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的
，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）
于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：
2． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的
，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中
只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
3． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。
【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。
4． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。 5． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。 【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。 6． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。 【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域， ，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点） 凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序 割成两部分：和和 且 将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下： 初始序列：[28]，07，39，10，65，14，61，17，50，21 21移动：21，07，39，10，65，14，61，17，50，[] 39移动：21，07，[]，10，65，14，61，17，50，39 17移动：21，07，17，10，65，14，61，[]，50，39 65移动：21，07，17，10，[]，14，61，65，50，39 14移动：21，07，17，10，14，[28]，61，65，50，39 7． 设阶稀疏矩阵A 有t 个非零元素，其三元组表示为 表示A 才有意义？ 的个存储单元，用二维数组存储时占用 主机甲和主机乙之个单元， 只有当试问：非零元素的个数t 达到什么程度时用，共占用三元组表 元组）时，用 8． 某局域网采用 程。 【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三表示A 才有意义。解不等式得协议实现介质访问控制， 数据传输率为间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过 （1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据） （2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以 太网帧的前导码） 【答案】（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短 ：= （lkm/200000km/s）×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时，另一台主机才发送数据，两台主机均检测到冲突的时间最长： =1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps= 间=2km/200000km/s =确认帧的发送时间=64× 8/10Mbps=; 确认帧的传播时间 =2km/200000km/s=; 发送1518B 所用的总时间为主机甲的有效数据传输率为12000bit ／1285.6μs=9.33Mbps。 9． 假定在一个8位字长的计算机中运行下列C 程序段： 若编译器编译时将8个8位寄存器R1〜R8分别分配给变量 回答下列问题。（提示：带符号整数用补码表示） （1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示） （3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。 （4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？ 【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。 （2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112； （3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而实现；对于带符号整数用补码表示，补码加减运算公式为： 数据帧的传播时（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据请