2018年浙江理工大学经济管理学院938数据结构与数据库技术之数据结构考研强化五套模拟题
● 摘要
一、应用题
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． 文件F 由200条记录组成, 记录从1开始编号, 用户打开文件后, 欲将内存中的一条记录插入文件F 中, 作为其第30条记录, 请回答下列问题, 并说明理由。
(1)若文件系统为顺序分配方式, 每个存储块存放一条记录, 文件F 的存储区域前后均有足够空闲的存储空间, 则要完成上述操作最少要访问多少存储块？F 的文件控制区内容会有哪些改变？
(2)若文件系统为链接分配方式, 每个存储块存放的一条记录和一个链接指针, 则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB , 其中4个字节存放指针, 则该系统支撑文件的最大长度是多少？
【答案】(1)因为要最少访问, 所以选择将前29块前移一个存储块单元, 然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出, 再访问目标存储块将数据写入,
所以最少需要访问块存储块
F 的文件区的文件长度加1, 起始块号减1
(2)采用链接方式则需要顺序访问前29块存储块, 然后将新纪录的存储块插入链中即可, 把新的块存入磁盘要1次访存, 然后修改第29块的链接地址存回磁盘又一次访存。一共就是29+1+1=31次。
4个字节的指针的地址范围为。
3． 带权图(权值非负，表示边连接的两顶点间的距离) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法:
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点
第 2 页，共 25 页 试问:非零元所以此系统支撑文件的最大长度为
;
③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，请证明之；否则请举例说明。
【答案】题目中方法不一定能(或不能) 求得最短路径。举例说明:
图
(a)
图(b)
图(a)中，假设初始顶点1到目标顶点4之间有一条边，权值x ＝2。显然图(a)中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4,
即初始顶点
显然，
短路径。
图(b)中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。
4． 画出同时满足下列两个条件的两棵不同的二叉树。
(1)按前序遍历二叉树的顺序为ABCDE 。
(2)高度为5其对应的树(森林) 的高度最大为4。
【答案】(1)满足条件的二叉树如图1所示:
一目标顶点4, 所经过的边的权值分别为。大于2。因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最
图1
(2)满足条件的二叉树如图2所示:
第 3 页，共 25 页
图2
5． 某程序中有如下循环代码段
P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示
。假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中, 数组A 的首地址在寄存器R3中, 程序段
表
执行上述代码的计算机M 采用32位定长指令字, 其中分支指令Bue 采用如下格式,
Op 为操作码:Rs 和Rd 为寄存器编号:OFFSET 为偏移量, 用补码表示。请回答下列问题, 并说明理由。
(1)M的存储器编址单位是什么？
(2)己知sll 指令实现左移功能, 数组A 中每个元素占多少位？
(3)上表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式, 当前PC 内容为bne 指令地址, 通过分析上表中指令地址和bne 指令内容, 推断出bne 指令的转移目标地址计算公式。
(4)若M 采用如下“按序发射、ID(译码及取数) 、EXE(执按序完成”的5级指令流水线:IF(取指) 、
行) 、MEM(访存) 、WB(写回寄存器) , 且硬件不采取任何转发措施, 分支指令的执行均引起3个时钟周期阻塞, 则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？
【答案】(1)由题可知, 指令为32为即4个字节, 而程序执行时是以4为间隔逐条取指令的, 故可知M 的存储器是采用字节编址。
(2)32位, 因为sll 中实现左移, 而即左移两位就是乘以4, 所以是
第 4 页，共 25 页
位