数据结构16春在线作业1

李老师

数据结构16春在线作业1
试卷总分：100   测试时间：--
一、单选题（共20道试题，共60分。）
1.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 直接选择排序
满分：3分
2.在下述几种排序方法中，辅助空间需要最多的是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
满分：3分
3.设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
A. 6
B. 7
C. 25
D. 50
满分：3分
4.一个算法应该是（）。
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C
满分：3分
5.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A. 堆排序＜快速排序＜归并排序
B. 堆排序＜归并排序＜快速排序
C. 堆排序＞归并排序＞快速排序
D. 堆排序＞快速排序＞归并排序
满分：3分
6.在查找过程中，若同时还要做增、删工作，这种查找则称为 ()。
A. 静态查找
B. 动态查找
C. 内查找
D. 外查找
满分：3分
7.下面说法不正确的是 ()。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
满分：3分
8.递归过程的实现需用到 ( )。
A. 线性表
B. 链表
C. 栈
D. 队列
满分：3分
9.有n个顶点的有向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3分
10.设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
满分：3分
11.在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
A. p->lchild = = NULL
B. p->ltag = = 1
C. p->ltag = = 1且p->lchild = = NULL
D. p->ltag = = 0
满分：3分
12.顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
满分：3分
13.相对于顺序存储而言，链接存储的优点是 ( )。
A. 随机存取
B. 节省空间
C. 插入、删除操作方便
D. 结点间关系简单
满分：3分
14.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A. 112
B. 132
C. 118
D. 140
满分：3分
15.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。
A. h+1
B. 2h-1
C. 2h
D. 2h+1
满分：3分
16.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。
A. abcd
B. dcba
C. adcb
D. cbda
满分：3分
17.下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。
A. [ 68, 11 , 18 , 69 ] 70 [ 23 , 93 , 73]
B. [ 68 , 11 , 69 , 23 ] 70 [18, 93, 73 ]
C. [ 93, 73 ] 70 [ 68, 11, 69, 23, 18 ]
D. [ 68 , 11 , 69, 23, 18 ] 70 [ 93, 73 ]
满分：3分
18.下列四个序列中，哪一个是堆 () 。
A. 75 , 65 , 30 , 15 , 25 , 45 , 20 , 10
B. 75 , 65 , 45 , 10 , 30 , 25 , 20 , 15
C. 75 , 45 , 65 , 30 , 15 , 25 , 20 , 10
D. 75 , 45 , 65 , 10 , 25 , 30 , 20 , 15
满分：3分
19.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A. 1/2
B. 1
C. 2
D. 4
满分：3分
20.下面关于串的叙述中，哪一个是不正确的 ( )
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
满分：3分
二、判断题（共20道试题，共40分。）
1.二叉树的中序遍历序列中，任意一个结点均处在其左子女结点( 若存在 )的后面。
A. 错误
B. 正确
满分：2分
2.无向图的邻接矩阵是对称的。
A. 错误
B. 正确
满分：2分
3.哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。
A. 错误
B. 正确
满分：2分
4.若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。
A. 错误
B. 正确
满分：2分
5.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。
A. 错误
B. 正确
满分：2分
6.将森树转成二叉树，根结点没有右子树。
A. 错误
B. 正确
满分：2分
7.在中序线索二叉树中，每一非空的线索均指向其祖先结点。
A. 错误
B. 正确
满分：2分
8.有向图的邻接矩阵是对称的。
A. 错误
B. 正确
满分：2分
9.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。
A. 错误
B. 正确
满分：2分
10.需要借助于一个栈来实现DFS算法。
A. 错误
B. 正确
满分：2分
11.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
A. 错误
B. 正确
满分：2分
12.直接访问文件也能顺序访问，只是一般效率不高。
A. 错误
B. 正确
满分：2分
13.所谓取广义表的表尾就是返回广义表中最后一个元素。
A. 错误
B. 正确
满分：2分
14.数组不适合作为任何二叉树的存储结构。
A. 错误
B. 正确
满分：2分
15.两个栈共用静态存储空间，对接使用方式减少了空间溢出的可能性。
A. 错误
B. 正确
满分：2分
16.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插人、删除等操作。
A. 错误
B. 正确
满分：2分
17.树与二叉树是两种不同的树形结构。
A. 错误
B. 正确
满分：2分
18.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。
A. 错误
B. 正确
满分：2分
19.二叉树的前序遍历并不能唯一确定这棵树形，但是，如果还知道该树的根结点是哪一个，则可以确定这棵二叉树。
A. 错误
B. 正确
满分：2分
20.栈是实现过程和函数等子程序所必需的结构。
A. 错误
B. 正确
满分：2分
>>操作完成!