数据结构18秋在线作业1-0005
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.n个结点的线索二叉树上含有的线索数为 ( )。
A.n-1
B.n
C.n +1
D.2n
2.折半查找要求结点 ()。
A.无序、顺序存储
B.无序、链接存储
C.有序、顺序存储
D.有序、链接存储
3.算法分析的两个主要方面是 ( )。
A.正确性与健壮性
B.可读性与可用性
C.时间复杂度与空间复杂度
D.数据复杂性与程序复杂性
4.非线性结构的逻辑特征是一个结构可能有 ( )。
A.一个前驱和一个后继
B.多个前驱和一个后继
C.一个前驱和多个后继
D.多个前驱和多个后继
5.一个存储结点存放一个（）。
A.数据项
B.数据元素
C.数据结构
D.数据类型
6.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A.60
B.66
C.18000
D.33
7.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
8.在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
A.p->lchild = = NULL
B.p->ltag = = 1
C.p->ltag = = 1且p->lchild = = NULL
D.p->ltag = = 0
9.B+ 树应用在 () 文件系统中。
A.ISAM
B.VSAM
C.顺序
D.散列
10.若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X的中序前驱为 ( )。
A.X的双亲
B.X的右子树中最左下的结点
C.X的左子树中最右下的结点
D.X的左子树中最右下的叶结点
11.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
B.按关键字大小排序
C.按记录输入先后排序
D.连续排序
12.设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 ( )。
A.n-1
B.élog2(n+1)ù -1
C.?log2n?
D.不确定
13.在n个结点的线索二叉树中线索的数目为 ( )。
A.n-1
B.n
C.n+1
D.2n
14.用ISAM组织文件适合于 ()。
A.磁带
B.磁盘
C.光盘
D.外存储器
15.若由树转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A.根结点无右子树的二叉树
B.根结点无左子树的二叉树
C.根结点可能有左子树和右子树
D.各结点只有一个子女的二叉树
16.散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的 () 方法是散列文件的关键。
A.哈希函数
B.除余法中的质数
C.冲突处理
D.哈希函数和冲突处理
17.一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
A.acbd
B.abcd
C.dbca
D.adcb
18.内排序方法的稳定性是指 ()。
A.该排序算法不允许有相同的关键字记录
B.该排序算法允许有相同的关键字记录
C.平均时间为O(nlog2n ) 的排序方法
D.以上都不对
19.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
20.稀疏矩阵常用的压缩存储方法有两种，它们是 ()。
A.二维数组和三维数组
B.三元组和散列
C.三元组和十字链表
D.散列和十字链表
二、 判断题 (共 20 道试题,共 40 分)
1.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
A.错误
B.正确
2.N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A.错误
B.正确
3.任何一个递归过程都可以转换成非递归过程。
A.错误
B.正确
4.倒排文件的优点是维护简单。
A.错误
B.正确
5.完全二叉树一定存在度为1的结点。
A.错误
B.正确
6.对一棵二叉树进行层次次序遍历时，应借助于一个栈。
A.错误
B.正确
7.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A.错误
B.正确
8.空串与空格串是相同的。
A.错误
B.正确
9.稀疏矩阵压缩存储后，必会失去随机存取功能。
A.错误
B.正确
10.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
A.错误
B.正确
11.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
A.错误
B.正确
12.用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。
A.错误
B.正确
13.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列3, 2, 5, 6, 4, 1。
A.错误
B.正确
14.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。
A.错误
B.正确
15.有向图的邻接矩阵是对称的。
A.错误
B.正确
16.二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A.错误
B.正确
17.将森树转成二叉树，根结点没有左子树。
A.错误
B.正确
18.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A.错误
B.正确
19.栈是实现过程和函数等子程序所必需的结构。
A.错误
B.正确
20.哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
A.错误
B.正确
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。