2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题
● 摘要
目录
2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题（一） ... 2
2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题（二） ... 9 2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题（三） . 17 2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题（四） . 24 2018年云南大学软件学院842数据结构与程序设计之数据结构考研仿真模拟五套题（五） . 30
一、填空题
1． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】O(1)；O(n)；O(1)；O(1)
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
2． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
3． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
4． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
5． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
6． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
；2；k
二、判断题
7． 对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
【解析】形状不同的两个二叉排序树(关键字集合相同) ，在中序遍历下是输出排好序的序列，所以顺序是一致的。
8． 设模式串的长度为m ，目标串的长度为n ，当n ≈m 且处理只匹配一次的模式时，朴素的匹配(即子串定位函数) 算法所花的时间代价可能会更为节省。（ ）
【答案】 √
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
9． 哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）
【答案】×
【解析】哈希文件是使用一个函数(算法) 来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。
10．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键话动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
11．数组是同类型值的集合。（ ）
【答案】 ×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
12．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）
【答案】 ×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
三、单项选择题
13．在采用中断
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B 【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需要的, 因此, 它不可能是CPU 和打印控制接口中的端口之间交换的信息。
14．某计算机的控制器采用微程序控制方式, 微指令中的操作控制字段采用字段直接编码法, 共有33个微命令, 构成5个互斥类, 分别包含7、3、12、5和6个微命令, 则操作控制字段至少有 （ ）。
A.5位
B.6位
C.15位
D.33位
【答案】C 。
33个微命令分成5个互斥类(即5个字段) , 根据每个类中微命令的多少可以分别确定【解析】
字段的长度为3、2、4、3、3位, 又因为采用直接编码方式, 所以它们之和也就是操作控制字段的位数。
15．将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1
【答案】A
【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序
方式控制打印输出的情况下, CPU 和打印控制接口中的端口之间交换的信息不可能是（ ）。
相关内容
相关标签