2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点

目录

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编（一） (2)

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编（二） (14)

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编（三） (25)

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编（四） (36)

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编（五） (46)

第1 页，共55 页

第 2 页，共 55 页

2017年长春理工大学计算机科学技术学院809数据结构考研导师圈点必考题汇编

（一）

说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。

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

一、填空题

1． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

2． 表达式的后缀表达式是_____。

【答案】

3． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为

当最后一层只有

一个元素时，此时堆的元素个数最少，元素个数为

4． 设广义表则是_____tail （L ）是_____；L 的长度是_____；深度是_____。

【答案】（ ）；（（ ））

；2；2 【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

5． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）链表未到尾就一直进行

（2）将当前结点作为头结点后的第一元素结点插入

6． 顺序栈用

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

【答案】

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

第 3 页，共 55 页 7． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为

8． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，

【答案】比较；移动

9． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

），则的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若则的地址为若

则的地址为将代入得33。

10．已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

11．VSAM 系统是由_____、_____、_____构成的。

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

12．高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

二、选择题

13．假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分

别用IEEE754单精度和双精度浮点数格式表示）

，已知若在32位机器中执行下列关系表达式，则结果为“真”的是（ ）。

第 4 页，共 55 页 A.仅I 和II

B.仅I 和III

C.仅II 和III

D.仅III 和IV

【答案】B

【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。

II 中，f 的数据类型从float 转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f 时需要对阶，对阶后f 的尾数有效位被舍去而变为0,故d+f 仍然为d ,再减去d 后结果为0,故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。

14．某计算机有五级中断中断屏蔽字为表示对级中断进行屏蔽。若中断响应优先级从高到低的顺序是且要求中断处理优先级从高到低的顺序为

则的中断处理程序中设置的中断屏蔽字是（ ）。 A.11110

B.01101

C.00011

D.01010

【答案】D

【解析】由于

的中断处理优先级下降，屏蔽字中需要3个0,所以可以将选项A 、B

排除掉。需要对

开放，所以相应位应该为即为01010。

15．下列调整中，不可能导致饥饿现象的是（ ） A.时间片转移

B.静态优先及调度

C.非抢占式作业优先

D.抢占式短作业优先

【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

16．下列选项中，不属于网络体系结构中所描述的内容是（ ）。

A.网络的层次

B.每一层使用的协议

C.协议的内部实现细节

D.每一层必须完成的功能

【答案】C

【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此