当前位置：问答库＞考研试题

一、填空题

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

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

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

2． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

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

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

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

4． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

5． 设有N 个结点的完全二叉树顺序存放在向量

【答案】 中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

6． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。

本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

(3)重复(2)直到堆栈为空时为止。

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

7． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

8． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

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

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

10．求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

11．空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

12．堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；；O(1)；满足堆的性质

13．一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

14．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

15．已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

二、单项选择题

16．对矩阵压缩存储是为了（ ）。

A. 方便运算

B. 方便存储

C. 提高运算速度

D. 减少存储空间

【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。