1、综合模拟试卷 16 及答案与解析一、单项选择题1 下面有关浮点运算器的描述中，正确的是( )。（A）浮点运算器可用两个松散的定点运算器(阶码部件和尾码部件)来实现（B）阶码部件不可以实现加、减、乘、除这 4 种运算（C）阶码部件进行加、减、乘、除和比较操作（D）尾数部件只进行乘、除操作2 某机浮点数格式为：数符 1 位、阶符 1 位、阶码 5 位、尾数 9 位(共 16 位)。若机内采用阶移尾补规格化浮点数表示，那么它能表示的最小负数为( )。（A）一 231（B）一 232(0111111111)（C）一 231(0111111111)（D）一 2323 设浮点数的阶为 8 位(其中 1 位
2、阶符)，用移码表示，尾数为 24 位(其中 1 位数符)；用原码表示，则它所能表示的最大规格化正数是( )。（A）(2 7 一 1)(12-23)（B） 227-1(12-23)（C） 227(12-23)（D）2 27-1(12-22)4 假设有浮点数 x=2-500110011，y=2 3(-01110010)，阶码用 4 位补码表示，尾数(含符号位) 用 8 位补码表示，则xy 浮 为( )。（A）2 -2(一 01010001)（B） 2-3(-0001 1 101)（C） 2-3(一 0101 1011)（D）2 -2(一 0101 1011)5 非线性流水线是指( ) 。（A）一次
3、运算中使用流水线中的多个功能段（B）一次运算中要多次使用流水线中的某些功能段（C）流水线中的某些功能段在各次运算中的作用不同（D）流水线中各个功能段存各种运算中有不同的组合6 利用时间重叠概念实现并行处理的是( )。（A）流水处理机（B）多处理机（C）并行 (阵列)处理机（D）相联处理机二、填空题7 紧耦合并行计算机的处理结点之间的通信靠_完成，松耦合并行计算机的处理结点之间的通信靠_完成。8 异步流水线会出现顺序流水线不可能发生的_相关和写一写相关。9 流水线流出任务的顺序可以与流入的顺序不同的流水线称为_流水线。10 超标量流水线采用的是_并行性，超流水线采用的是_并行性。11 解决多处理
4、机系统中各 Cache 数据一致性问题的主要方法有软件方法、采用总线检测机制和采用_法。12 TTL 三态门的 3 种可能输出状态是 _ 、_和_。13 组合逻辑电路的输出只与_状态有关，而与电路的_输入状态无关。综合模拟试卷 16 答案与解析一、单项选择题1 【正确答案】 C2 【正确答案】 C【试题解析】 栈中元素必须按与输入顺序相反的顺序出栈。3 【正确答案】 A【试题解析】 顺着链表的指针往下走即可。4 【正确答案】 C【试题解析】 对称矩阵只用存上或下三角矩阵中的元素。5 【正确答案】 C【试题解析】 对于基本有序的表使用直接插入排序是较好的。6 【正确答案】 D【试题解析】 广义表
5、是一种特殊的线性表，不要求每个元素都为原子，可以是子表。7 【正确答案】 B【试题解析】 AOV 网不带权值，邮电网、公路网都会有运费等权值。8 【正确答案】 D【试题解析】 左、右标记为 1 说明是线索。9 【正确答案】 C【试题解析】 建立哈夫曼树的方法是： (1)对给定的 n 个权值W1，W 2，W 3，W i 一，W n构成 n 棵二叉树的初始集合F=T1，T 2，T 3，T i， ，T n，其中每棵二叉树中只有一个权值为 Wi 的根结点，它的左、右子树均为空(为方便在计算机上实现算法，一般还要求以 Ti 的权值Wi 的升序排列)。 (2)在 F 中选取两棵根结点权值最小的树作为新构造
6、的二叉树的左、右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 (3)从F 中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合 F 中。 (4)重复(2)和(3)两步，直到集合 F 中只有一棵二叉树为止。依照上述方法，即可得选项C。10 【正确答案】 A【试题解析】 B 一树定义为：一棵小(m3)阶的 B 一树是满足如下性质的 m 叉树：(1)每个结点至少包含下列数据域：(j ，p 0，K 1，P 1，K 2，K i，P i)其中：j 为关键字总数。K i(1i，)是关键字，关键字序列递增有序：K 12i。P i(0ij)是孩子指针。对于叶结点，每个 Pi 为空指针。 (
7、2)所有叶子结点是在同一层上，叶子结点的层数为树的高度 h。 (3)每个非根结点中所包含的关键字个数 j 满足：m2一1jm1 即每个非根结点至少应有m2 一 1 个关键字，至多有 m1 个关键字。因为每个内部结点的度数正好是关键字总数加 1，故每个非根的内部结点至少有m2棵子树，至多有 m，棵子树。 (4)若树非空，则根至少有 1 个关键字，故若根不是叶子，则它至少有 2 棵子树。根至多有 m1 个关键字，故至多有 m 棵子树。对照以上定义，即可得选项 A。二、简答题11 【正确答案】 图 G 中的边数为矩阵 A 的上三角矩阵中非零元素的个数。12 【正确答案】 第 i 行第 j 列的元素是
8、否非零。13 【正确答案】 顶点所在的行或列的非零元素的个数。14 【正确答案】 n 一 1。中序遍历时，要先找到最左叶子结点，途中经历的那些结点依次进栈。因为整棵树共有 n 个结点，途中最多经历 n1 个结点，故栈的最大深度为 n1。15 【正确答案】 因为二叉树的结点数问存在关系：n 0=n2+1。且哈夫曼树中只有度为 0 和度为 2 的结点，故哈夫曼树共有结点数为：2n 0-1。16 【正确答案】 设此循环队列采用的存储方案为队尾指针与队头指针间空一个元素，则队头和队尾指针相等，为空队列；(q 一rear+1)N=q 一front ，为满队列。元素 x 入队的算法是：voidEnelem
9、(cyQueue*q)intm：m=(q 一rear+1)N；计算元素在队列中的存放序号if(m=q 一front)printf(”队满n”)；队满的判断方法elseq 一datam：x；入队17 【正确答案】 因为是线性探测，所以比较次数为 1+2+n=n(n+1)2。第一个记录散列到相应位置要查看此位置上是否有元素，比较一次；第二个记录散列到此位置上时比较一次，此位置不空，然后向后移动一个位置(线性探测)，再比较一次，共比较了两次；以此类推，可得结果。18 【正确答案】 关键字有序。其有序性在存储结构上使用链指针来表示。三、计算题19 【正确答案】 voidselection(intAn，
10、intx，inty)inti=0，j：n-1；while(Ai=y&j=0)j 一一；找到比 y 大的第一个元素或 y 元素for(k=j；klchild=21 【正确答案】 #defineINFINITY65536voidshortpath(MGraphGintv，intlen，shortpathTable&D)用 Dijkstra 算法求有向网 G 的 v 结点的最短路径 PV及其带权长度 DV，各边的权值均为 1finalu为 true 当且仅当 u 已经求得从 v 到 u 的最短路径for(u=0；uGvexnum ；+u)finalU=false；Du=GarcsvU ；Dv：0；finalv=true ；初始化，V 顶
