当前位置:问答库>考研试题

2017年闽南师范大学计算机学院916计算机专业基础之数据结构考研仿真模拟题

  摘要

一、填空题

1. 遍历图的过程实质上是_____,广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程;0(n+e); 0(n+e); 访问顶点的顺序不同;队列和栈 【解析】广度优先遍历图使用队列这种数据结构,深度优先遍历图使用栈这种数据结构。 2. 设有一个10阶对称矩阵A 采用压缩存储方式 ,(以行为主序存储:)则的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ,列标为j 。若

则的地址为

的地址为将代入得33。

3. 下列程序是快速排序的非递归算法,请填写适当的语句,完成该功能。

【答案】

【解析】快速排序(quicksort )的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

4. 在双向循环链表中,向P 所指的结点之后插入指针f 所指的结点,其操作是_____、_____、_____、_____。

【答案】

5. 设T 和P 是两个给定的串,在T 中寻找等于P 的子串的过程称为_____,又称P 为_____。

【答案】模式匹配;模式串

6. 当广义表中的每个元素都是原子时,广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子,则元素不可分。此时的元素是只有一对一的关系,所以广义表变成了线性表。

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

【答案】

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

8. 在循环队列中,队列长度为n ,存储位置从0到,

【答案】

编号,以rear 指示实际的队尾元素,现

要在此队列中插入一个新元素,新元素的位置是( )。

9. VSAM 系统是由_____、_____、_____构成的。

【答案】索引集;顺序集;数据集

10.完善算法:求KMP 算法.next 数组。

END ;

【答案】

二、选择题

11.下列有关浮点数加减运算的叙述中,正确的是( )。

对阶操作不会引起阶码上溢或下溢

右规和尾数舍入都可能引起价码上溢

左规时可能引起阶码下溢

尾数溢出时结果不一定溢出 A. 仅B. 仅

C. 仅

D. 【答案】D

【解析】浮点数的加减运算步骤包括:①对阶,使两个操作数的小数点位置对齐,阶码小的尾数右移,可能产生溢出,但是阶码不会溢出;②尾数求和,将对阶后的尾数按定点数加(减)运算规则运算;③规格化,包括左规和右规,左规时阶码减少,可能出现阶码下溢,而右规时,阶码増加可能出现阶码上溢;④舍入,该过程可能需要右规调整,因此可能出现阶码上溢;⑤溢出判断,浮点数的溢出与否是由阶码的符号决定的,而不是由尾数溢出判断的,因此尾数溢出时结果不一定溢出。因此均正确。

12.给定二叉树如下图所示。设N 代表二叉树的根,L 代表根结点的左子树,R 代表根结点的右子树,若遍历后的节点序列为3,1,7,5,6,2,4,则其遍历方式是( )

A.LRN B.NRL C.RLN

D.RNL

【答案】D

【解析】对“二叉树”而言,一般有三条搜索路径; ①先上后下的按层次遍历;

②先左(子树)后右(子树)的遍历; ③先右(子树)后左(子树)的遍历;