《2018年浙江理工大学经济管理学院938数据结构与数据库技术之数据结构考研基础五套测试题.doc》由会员分享，可在线阅读，更多相关《2018年浙江理工大学经济管理学院938数据结构与数据库技术之数据结构考研基础五套测试题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、2018年浙江理工大学经济管理学院938数据结构与数据库技术之数据结构考研基础五套测试题-一、应用题1 简述广义表属于线性结构的理由。【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。 2 某计算机存储器按字节编址, 虚拟(逻辑) 地址空间大小为16MB , 主存(物理) 地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接
2、映射方式, 共8行; 主存与Cache 之间交换的块大小为32B 。系统运行到某一时刻时, 页表的部分内容和Cache 的部分内容分别如图a 、图b 所示, 图中页框号及标记字段的内容为十六进制形式。 图a 页表的部分内容 图b Cache的部分内容请回答下列问题。(1)虚拟地址共有几位, 哪几位表示虚页号? 物理地址共有几位, 哪几位表示页框号(物理页号) ？(2)使用物理地址访问Cache 时, 物理地址应划分哪几个字段? 要求说明每个字段的位数及在物理地址中的位置。(3)虚拟地址001C60H 所在的页面是否在主存中? 若在主存中, 则该虚拟地址对应的物理地址是什么? 访问该地址时是否C
3、ache 命中? 要求说明理由。(4)假定为该机配置一个4路组相联的TLB , 该TLB 共可存放8个页表项, 若其当前内容(十六进制) 如图c 所示, 则此时虚拟地址024BACH 所在的页面是否在主存中? 要求说明理由。 图c TLB的部分内容【答案】(1)由于页面大小为4KB , 页内地址需要12位, 所以虚拟地址24位, 其中虚页号占12位; 物理地址20位, 其中页框号(实页号) 占8位。(2)主存物理地址20位, 从左至右应划分3个字段:标记字段、块号字段、块内地址字段。其中标记12位, 块号3位, 块内地址5位。(3)虚拟地址是04C60H=。(物理地址高12位) , 故访问该地
4、址时Cache 不, 虚页号为024H , TLB 中存放8个页表项, , 该虚拟地址的虚页号为001H , 查页表可以发现, 虚页号1对应的有效位为“1”, 表明此页在主存中, 页框号为04H , 对应的20位物理地址访问该地址时, Cache 不命中, 因为Cache 采用直接映射方式, 对应的物理地址应该映射到Cache 的第3行中, 其有效位为1, 标记值命中。 (4)虚拟地址采用4路组相联, 即TLB 分为2组, 每组4个页表项。12位虚页号字段中最低位作为组索引, 其余11位为标记位。现在最低位为0, 表明选择第0组, 11位的标记为012H , 根据标记可以知道TLB 命中, 所
5、在的页面在主存中。因为如果在TLB 中查到了页表项, 即TLB 命中, 说明所在页一定命中3 在改进了的(无回溯) 字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。 在模式P 中求nextval 数组的值 算法中第4行有PJPK，第六行中也有PJPK。两处比较语句相同。请分析说明此两处比较语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？【答案】第4行的PJPK语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则指针J 和K 均增加1，继续比较。第6行的pJpK语句的意义是，当第J 个字符在模式匹配中失配时，若第K 个字符和第J 个字符不等，则
6、下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K 个字符失配时的下一个(即NEXTV ALK)。该算法在最坏情况下的时间复杂度0(m2)。 4 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。(1)(A(B(D，E) ，C(F)(2)(A(B(D，E) ，C)(3)(A)(4)(A(B(C，D(E)(5)（ ）【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。 5设与记录对应的关键字分别是成立，试证明经过一趟起泡后，一定有记录与进行交换。【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在，又因之前且，则，故，即说明和是反序；设对于和之前全部记录:(其中包括) 中关键字最大为，故经过起泡排序前i-2次比较后，必定交换。 的关键字一定为。如果存在和使得j-一、应用题-考研试题-
