2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研强化五套模拟题
● 摘要
一、综合题
1． 设mxn 阶稀疏矩阵A 有t 个非零元素，其三元组表示为
素的个数t 达到什么程度时用LTMA 表示A 才有意义？
【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数nu 和非零元素个数tu(也算一个三元组) ，共占用三元组表LTMA 的3(t＋1) 个存储单元，用二维数组存储时占用m*n个单元，只有当3(t＋1) ＜m*n时，用LTMA 表示A 才有意义。解不等式得t ＜m*n/3﹣l 。
2． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如0-2-7-9-11) 表示进行作业的路径。
完成此工程的关键路径是(A)完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。
试问:非零元
图
【答案】A.0-2-6-9-11；B.20；C. 事件顶点1、5和7各充裕两天；D.4天；E.0
3． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
(2)因为归并的趟数
排序的效率。
第 2 页，共 32 页 ，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部
4． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下:
(1)对该算术表达式(二叉树) 进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值。
(2)递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+、－、*、/等) 进行求值。
5． 在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPACE[N﹣1]分别是两个栈的栈底。
(1)对栈1、栈2，试分别写出(元素X) 入栈的主要语句和出栈的主要语句。
(2)对栈1、栈2，试分别写出栈满、栈空的条件。
【答案】(1)入栈主要语句
//设X 为入栈元素
.
出栈主要语句
//返回出栈元素
//返回出栈元素
(2)
栈满条件:top2﹣topl ＝l
栈空条件:topl ＝﹣l 并且top2＝N //topl＝﹣l 为左栈空，top2＝N 为右栈空
6． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同(即两串串值相等) 。
7．
设与记录
对应的关键字分别是成立，试证明经过一趟起泡后，一定有记录与进行交换。
【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在，又因
之前且，则，故，即说明和是反序；设对于和之前全部记录:(其中包括) 中关键字最大为，故经过起泡排序前i-2次比较后，
必定交换。 的关键字一定为。如果存在
和使得j 且和Rf 为反序，由此可知第 3 页，共 32 页 8． 某计算机采用16位定长指令字格式, 其CPU 中有一个标志寄存器, 其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令, 其格式如下: 其中, 00000为操作码OP ; C 、Z 和N 分别为CF 、ZF 和NF 的对应检测位, 某测位为1时表示需检测对应标志, 需检测的标志位中只要有一个为1就转移, 否则就不转移, 例如, 若C=1, Z=0, N=1, 则需检测CF 和NF 的值, 当CF=1或NF=1时发生转移; OFFSET 是相对偏移量, 用补码表示。 转移执行时, 转移目标地址为 顺序执行时, 下条指令地址为 请回答下列问题。 (1)该计算机存储器按字节编址, 还是按字编址？该条件转移指令向后(反向) 最多可跳转最多少条指令？ (2)某条件转移指令的地址为200CH , 指令内容如下图所示, 若该执行时CF=0, ZF=0, NF=1, 则该指令执行后PC 的值是多少？若该指令执行时CF=1, ZF=0Z, NF=0, 则该指令执行后PC 的值又是多少？请给出计算过程。 (3)实现“无符号数比较小于等时转移”功能的指令中, C 、Z 和N 应各是什么？ (4)以下是该指令对应的数据通路示意图, 要求给出中部件①〜③的名称或功能说明。 。 ; 图 【答案】(1)因为指令长度为16位且下条指令地址为 题中给出偏移量OFFSET 为8位补码, 其范围为 后最多可跳转127条指令。 第 4 页，共 32 页 , 故编址单位是字节。 , 故相对当前指令进行条件跳转, 向