2022年上海海事大学文理学院828数据结构及程序设计之数据结构考

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 56 页

目录

2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五套题（一）

................................................................................................................................................ 2 2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五套题（二）

.............................................................................................................................................. 14 2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五套题（三）

.............................................................................................................................................. 25 2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五套题（四）

.............................................................................................................................................. 35 2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五套题（五）

(45)

专注考研专业课13年，提供海量考研优质文档！ 第 2 页，共 56 页 2018年上海海事大学文理学院828数据结构及程序设计之数据结构考研仿真模拟五

套题（一）

说明：仿真模拟试题是根据本校该考试科目历年考研真题题型及出题难度，结合常考侧重点，精心整理编写，均含有详细答案解析，是考研必备参考资料。

——————————————————————————————————————————

一、判断题

1． 如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。

2． 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）

【答案】√

【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。

3． 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）

【答案】 √

【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。

4． B-树中所有结点的平衡因子都为零。（ ）

【答案】√

【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。

5． 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）

【答案】×

【解析】外部排序方法:按可用内存大小，将外存上含n 个记录的文件分成若干长度为2的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件)逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段)所需的时间m*tIS+外存信息读写的时间

内部归并所

专注考研专业课13年，提供海量考研优质文档！ 第 3 页，共 56 页 需的时间。

6． 哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）

【答案】×

【解析】哈希文件是使用一个函数(算法)来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。

二、填空题

7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0,则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

8． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

9． 在单链表中设置头结点的作用是_____。

【答案】方便运算

10．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。

【答案】O(1)；O(n)；O(1)；O(1)

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

11．建立索引文件的目的是_____。

【答案】提高查找速度

12．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素在B 中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i ﹣l)(2n ﹣i ＋2)/2＋(j ﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 56 页

三、单项选择题

13．在系统总线的数据线上,不可能传输的是（ ）。

A.指令

B.操作数

C.握手(应答)信号

D.中断类型号型号

【答案】C

【解析】握手(应答)信号属于通信联络控制信号应该在通信总线上传输,不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。

14．下面关于求关键路径的说法不正确的是（ ）。

A.求关键路径是以拓扑排序为基础的

B.—个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D.关键活动一'定位于关键路径上

【答案】C

【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。

15．下列选项中，导致创建新进程的操作是（ ）.

(1)用户登录成功

(2)设备分配

(3)启动程序执行

A.仅(1)和(2)

B.仅(2)和(3)

C.仅(1)和(3)

D. (1)、(2)和(3)

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是(2).考察一个进程创建的过程是这样的:当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填写PCB 表创建进程.通常填写PCB 表的过程有一段时间(主要涉及资源分配需要协调），许多操作系统为此设立了一个中间状态称为“初始化”，也有的操作系统不设这个中间状态.此时操作系统填写进程ID 号、处理机参数、进程参数(状态、特权、优先级)、分配内存(若是虚拟存储就分配虚拟

本文来源：https://www.bwwdw.com/article/rqtl.html