东师《数据结构（高起专）》14春在线作业答案

黄老师

东师《数据结构（高起专）》2014春第一次在线作业
试卷总分：100   测试时间：--
一、单选题（共20道试题，共60分。）
1.在下面的叙述中，正确的是 ( )。
A. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的前序遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的中序遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
满分：3分
2.非线性结构的逻辑特征是一个结构可能有 ( )。
A. 一个前驱和一个后继
B. 多个前驱和一个后继
C. 一个前驱和多个后继
D. 多个前驱和多个后继
满分：3分
3.线索二叉树是一种 ( ) 结构。
A. 逻辑
B. 物理
C. 逻辑和存储
D. 线性
满分：3分
4.一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
A. acbd
B. abcd
C. dbca
D. adcb
满分：3分
5.在数据结构中，从逻辑上可以把数据结构分成 ( )。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
满分：3分
6.在k叉树中，度为0的结点称为 ( )。
A. 根
B. 叶
C. 祖先
D. 子孙
满分：3分
7.单链表的存储密度 ( )。
A. 大于1
B. 等于1
C. 小于1
D. 不能确定
满分：3分
8.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左子树和必有右子树
D. 各结点只有一个子女的二叉树
满分：3分
9.若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
A. X的双亲
B. X的右子树中最左下的结点
C. X的左子树中最右下的结点
D. X的右子树中最左下的叶结点
满分：3分
10.由3个结点可以构造出多少种不同的有向有序树？( )
A. 9
B. 10
C. 11
D. 12
满分：3分
11.有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A. m
B. m+1
C. 2m-1
D. 2m
满分：3分
12.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左子女
D. 任一结点无右子女
满分：3分
13.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A. p->next = s; s->next = q;
B. s->next = p->next; p->next = s;
C. p->next = s->next; s->next = p;
D. q->next = s; s->next = p;
满分：3分
14.引入线索二叉树的目的是 ( )。
A. 加快查找结点的前驱或后继的速度
B. 为了能方便地找到双亲
C. 为了能在二叉树中方便地进行插入与删除
D. 使二叉树的遍历结果唯一
满分：3分
15.在队列中存取数据的原则是 ( )。
A. 先进先出
B. 后进先出
C. 先进后出
D. 随意进出
满分：3分
16.如果BT是由有序树T转换而来的二叉树，那么T中结点的后根序列就是BT中结点的 ( ) 序列。
A. 前序
B. 中序
C. 后序
D. 层次次序
满分：3分
17.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
A. U
B. V
C. X
D. Y
满分：3分
18.在下面的叙述中，正确的是 ( )。
A. 树的先根遍历序列与其对应的二叉树的前序遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
满分：3分
19.head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
满分：3分
20.设s1 = "abc" ，则strlen(s1) = ( )。
A. 0
B. 1
C. 2
D. 3
满分：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.顺序存储方式只能用于存储线性结构。
A. 错误
B. 正确
满分：2分
10.二叉树只能用二叉链表表示。
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.当一棵具有m个叶结点的二叉树的 WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
A. 错误
B. 正确
满分：2分
19.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
A. 错误
B. 正确
满分：2分
20.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
A. 错误
B. 正确
东师《数据结构（高起专）》2014春第二次在线作业
试卷总分：100   测试时间：--
一、单选题（共20道试题，共60分。）
1.“堆积”问题是由于()引起的。
A. 同义词之间发生冲突
B. 散列函数
C. 不同的同义词子表结合在一起
D. 散列表“溢出”
满分：3分
2.有n个顶点的无向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3分
3.在下述几种排序方法中，辅助空间需要最多的是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
满分：3分
4.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
A. 193
B. 195
C. 197
D. 199
满分：3分
5.在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
满分：3分
6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A. 112
B. 132
C. 118
D. 140
满分：3分
7.下面说法不正确的是 ()。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
满分：3分
8.有n个顶点的有向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3分
9.下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
A. 有序表的查找
B. 二叉排序树的查找
C. AVL树
D. 散列查找
满分：3分
10.存放在外存中的数据的组织结构是 ()。
A. 数组
B. 表
C. 文件
D. 链表
满分：3分
11.散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的 () 方法是散列文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
满分：3分
12.有n个顶点的无向连通图的边数最少为 ()。
A. n/2
B. n-1
C. n
D. n+1
满分：3分
13.顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
满分：3分
14.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
满分：3分
15.下列四个序列中，哪一个是堆 () 。
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分
16.AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。
A. 0
B. 1
C. 2
D. 3
满分：3分
17.设有n个结点的AVL树，其平均查找长度为 ()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
满分：3分
18.设散列地址空间为0～m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key) = key % p。为了减少发生冲突的频率，一般取p为 ()。
A. 小于等于m的最大奇数
B. 小于等于m的最大偶数
C. 小于等于m的最大素数
D. 小于等于m的最大合数
满分：3分
19.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A. 希尔排序
B. 插入排序
C. 归并排序
D. 选择排序
满分：3分
20.广义表 (( a , b , c , d ) ) 的表头是 ()。
A. a
B. ( )
C. ( a , b , c , d )
D. ( 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.拓扑排序算法仅适用于有向无环图。
A. 错误
B. 正确
满分：2分
10.完全二叉树肯定是平衡二叉排序树。
A. 错误
B. 正确
满分：2分
11.在待排数据基本有序的情况下，快速排序效果最好。
A. 错误
B. 正确
满分：2分
12.当广义表中的每个元素都是原子时，广义表便成了线性表。
A. 错误
B. 正确
满分：2分
13.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插人、删除等操作。
A. 错误
B. 正确
满分：2分
14.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
A. 错误
B. 正确
满分：2分
15.用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
A. 错误
B. 正确
满分：2分
16.直接选择排序算法对n个记录排序，在最好情况下的时间复杂度为O(n)。
A. 错误
B. 正确
满分：2分
17.若一个广义表的表头为空表，则此广义表亦为空表。
A. 错误
B. 正确
满分：2分
18.哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
A. 错误
B. 正确
满分：2分
19.( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
A. 错误
B. 正确
满分：2分
20.倒排文件是对次关键字建立索引。
A. 错误
B. 正确
满分：2分