数据结构18春在线作业1-0002
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
B.按关键字大小排序
C.按记录输入先后排序
D.连续排序
2.一个有向无环图的拓扑排序序列 () 是唯一的。
A.一定
B.不一定
C.可能
D.三者均不对
3.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
4.对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A.24
B.28
C.30
D.32
5.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
D.任一结点无右子女
6.树最适合用来表示 ( )。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
7.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
A.193
B.195
C.197
D.199
8.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
9.顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A.散列存储
B.顺序存储或链接存储
C.压缩存储
D.索引存储
10.B+ 树应用在 () 文件系统中。
A.ISAM
B.VSAM
C.顺序
D.散列
11.插入、删除只能在同一端进行的线性表，称为 ( )。
A.队列
B.循环队列
C.栈
D.循环栈
12.散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的 () 方法是散列文件的关键。
A.哈希函数
B.除余法中的质数
C.冲突处理
D.哈希函数和冲突处理
13.有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A.m
B.m+1
C.2m-1
D.2m
14.数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.堆排序
15.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
16.下列描述中正确的是 ( )。
A.线性表的逻辑顺序与存储顺序总是一致的
B.每种数据结构都具备查找、插入和删除三种基本运算
C.数据结构实质上包括逻辑结构和存储结构两方面的内容
D.选择合适的数据结构是解决应用问题的关键步骤
17.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A.求子串
B.求串长
C.联接
D.模式匹配
18.在一个单链表中，在p所指结点之后插入s所指结点，则执行 ( )。
A.s->next = p; p->next = s;
B.s->next = p->next; p->next = s;
C.s->next = p->next; p = s;
D.p->next = s; s->next = p->next;
19.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
20.线索二叉树是一种 ( ) 结构。
A.逻辑
B.物理
C.逻辑和存储
D.线性
二、 判断题 (共 20 道试题,共 40 分)
1.空串与空格串是相同的。
A.错误
B.正确
2.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
A.错误
B.正确
3.树形结构中元素之间存在一对多的关系。
A.错误
B.正确
4.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
A.错误
B.正确
5.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
A.错误
B.正确
6.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A.错误
B.正确
7.对有序的单链表可以进行折半查找。
A.错误
B.正确
8.堆排序是稳定的排序方法。
A.错误
B.正确
9.二叉树的中序遍历序列中，任意一个结点均处在其右子女结点( 若存在 )的前面。
A.错误
B.正确
10.哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
A.错误
B.正确
11.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
A.错误
B.正确
12.快速排序总比简单的排序方法快。
A.错误
B.正确
13.链接存储结构属动态存储方式。
A.错误
B.正确
14.必须把一般的树转换成二叉树后才能进行存储。
A.错误
B.正确
15.循环队列通常用指针来实现队列的头尾相接。
A.错误
B.正确
16.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
A.错误
B.正确
17.直接访问文件也能顺序访问，只是一般效率不高。
A.错误
B.正确
18.完全二叉树的存储结构通常采用顺序存储结构。
A.错误
B.正确
19.堆是完全二叉树。
A.错误
B.正确
20.需要借助于一个栈来实现DFS算法。
A.错误
B.正确
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。