东师《数据结构16秋在线作业2.doc

东师《数据结构16秋在线作业2

东北师范大学东师数据结构16秋在线作业2

一、单选题（共 20 道试题，共 60 分。）

1. 在下述几种排序方法中，辅助空间需要最多的是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
正确答案：
2. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
A. ( c , d )
B. c , d
C. ( ( c , d ) )
D. d
正确答案：
3. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。
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 ]
正确答案：
4. 递归过程的实现需用到 ( )。
A. 线性表
B. 链表
C. 栈
D. 队列
正确答案：
5. 数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中则元素A[5,5] 的地址是 ()。
A. 1165
B. 1170
C. 1175
D. 1180
正确答案：
6. AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。
A. 0
B. 1
C. 2
D. 3
正确答案：
7. 下述文件中适合于磁带存储的是 ()。
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
正确答案：
8. 在n个结点的线索二叉树中线索的数目为 ( )。
A. n-1
B. n
C. n+1
D. 2n
正确答案：
9. 一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )
A. 不确定
B. 0
C. 1
D. 2
正确答案：
10. 有n个顶点的无向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
正确答案：
11. 由3个结点可以构造出多少种不同的有向无序树？( )
A. 9
B. 10
C. 11
D. 12
正确答案：
12. 引入线索二叉树的目的是 ( )。
A. 加快查找结点的前驱或后继的速度
B. 为了能方便地找到双亲
C. 为了能在二叉树中方便地进行插入与删除
D. 使二叉树的遍历结果唯一
正确答案：
13. 设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
正确答案：
14. 插入、删除只能在同一端进行的线性表，称为 ( )。
A. 队列
B. 循环队列
C. 栈
D. 循环栈
正确答案：
15. 完全二叉树是下列情况的哪一种 ( )。
A. 一定是满二叉树
B. 可能是满二叉树
C. 一定不是满二叉树
D. 不是二叉树
正确答案：
16. 若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。
A. i*(i-1)/2+j
B. j*(j-1)/2+i
C. i*(i+1)/2+j
D. j*(j+1)/2+i
正确答案：
17. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A. 112
B. 132
C. 118
D. 140
正确答案：
18. 存放在外存中的数据的组织结构是 ()。
A. 数组
B. 表
C. 文件
D. 链表
正确答案：
19. 下列描述中正确的是 ( )。
A. 线性表的逻辑顺序与存储顺序总是一致的
B. 每种数据结构都具备查找、插入和删除三种基本运算
C. 数据结构实质上包括逻辑结构和存储结构两方面的内容
D. 选择合适的数据结构是解决应用问题的关键步骤
正确答案：
20. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
D. 连续排序
正确答案：

数据结构16秋在线作业2

二、判断题（共 20 道试题，共 40 分。）

1. 所谓取广义表的表尾就是返回广义表中最后一个元素。
A. 错误
B. 正确
正确答案：
2. 强连通分量是无向图的极大强连通子图。
A. 错误
B. 正确
正确答案：
3. 当广义表中的每个元素都是原子时，广义表便成了线性表。
A. 错误
B. 正确
正确答案：
4. 需要借助于一个栈来实现DFS算法。
A. 错误
B. 正确
正确答案：
5. 通常使用队列来处理函数或过程的调用。
A. 错误
B. 正确
正确答案：
6. 稀疏矩阵压缩存储后，必会失去随机存取功能。
A. 错误
B. 正确
正确答案：
7. 完全二叉树的存储结构通常采用顺序存储结构。
A. 错误
B. 正确
正确答案：
8. 归并排序的辅助存储空间代价为O(1 )。
A. 错误
B. 正确
正确答案：
9. 拓扑排序算法仅适用于有向无环图。
A. 错误
B. 正确
正确答案：
10. 任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A. 错误
B. 正确
正确答案：
11. 将一棵树转成二叉树，根结点没有左子树。
A. 错误
B. 正确
正确答案：
12. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
A. 错误
B. 正确
正确答案：
13. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。
A. 错误
B. 正确
正确答案：
14. 用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
B. 正确
正确答案：
15. 算法的优劣与算法描述语言无关，但与所用计算机有关。
A. 错误
B. 正确
正确答案：
16. 对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A. 错误
B. 正确
正确答案：
17. 数组是同类型值的集合。
A. 错误
B. 正确
正确答案：
18. 哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
A. 错误
B. 正确
正确答案：
19. 折半插入排序所需比较次数与待排序记录的初始排列状态无关。
A. 错误
B. 正确
正确答案：
20. 链接存储结构属动态存储方式。
A. 错误
B. 正确
正确答案：

数据结构16秋在线作业2

一、单选题（共 20 道试题，共 60 分。）

1. 下列哪一种图的邻接矩阵是对称矩阵？ ()
A. 有向图
B. 无向图
C. AOV 网
D. AOE 网
正确答案：
2. “堆积”问题是由于()引起的。
A. 同义词之间发生冲突
B. 散列函数
C. 不同的同义词子表结合在一起
D. 散列表“溢出”
正确答案：
3. 采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
正确答案：
4. 下列排序方法中，哪一个是稳定的排序方法？()
A. 直接选择排序
B. 直接插入排序
C. 希尔排序
D. 快速排序
正确答案：
5. 顺序存储结构的优点是( )。
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 结构可动态变化
正确答案：
6. 堆的形状是一棵 ( )。
A. 二叉排序树
B. 满二叉树
C 完全二叉树
D. AVL树
正确答案：
7. 一个有n个结点的图，连通分量的个数最少为 ()。
A. 0
B. 1
C. n-1
D. n
正确答案：
8. 在栈中存取数据的原则是 ( )。
A. 先进先出
B. 后进先出
C. 后进后出
D. 随意进出
正确答案：
9. 判断线索二叉树中某结点p有右子女的条件是 ( )。
A. p->rtag = = 0
B. p->rtag = = 1
C. p ! = NULL
D. p->lchild ! = NULL
正确答案：
10. 由3个结点可以构造出多少种不同的二叉树？( )
A. 15
B. 21
C. 30
D. 33
正确答案：
11. 在下述几种排序方法中，不稳定的排序方法是 ()。
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 归并排序
正确答案：
12. 在n个结点的线索二叉树中线索的数目为 ( )。
A. n-1
B. n
C. n+1
D. 2n
正确答案：
13. head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
正确答案：
14. 设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。
A. LOC(A[0][0]) + (j*m+i)*c
B. LOC(A[0][0]) + (i*n+j)*c
C. LOC(A[0][0]) + [(j-1)*m+i-1]*c
D. LOC(A[0][0]) + [(i-1)*n+j-1]*c
正确答案：
15. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
A. r = f->next;
B. r = r->next;
C. f = f->next;
D. f = r->next;
正确答案：
16. 顺序表中逻辑上相邻的结点其物理位置也 ( )。
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
正确答案：
17. 下面的排序方法中，辅助空间为O( n ) 的是 ()。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
正确答案：
18. 若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。
A. i*(i-1)/2+j
B. j*(j-1)/2+i

C. i*(i+1)/2+j
D. j*(j+1)/2+i
正确答案：
19. 下列描述中正确的是 ( )。
A. 线性表的逻辑顺序与存储顺序总是一致的
B. 每种数据结构都具备查找、插入和删除三种基本运算
C. 数据结构实质上包括逻辑结构和存储结构两方面的内容
D. 选择合适的数据结构是解决应用问题的关键步骤
正确答案：
20. 若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。
A. 10
B. 16
C. 31
D. 32
正确答案：

数据结构16秋在线作业2

二、判断题（共 20 道试题，共 40 分。）

1. 在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
A. 错误
B. 正确
正确答案：
2. 程序一定是算法。
A. 错误
B. 正确
正确答案：
3. 用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。
A. 错误
B. 正确
正确答案：
4. 在指定结点之前插入新结点时，双链表比单链表更方便。
A. 错误
B. 正确
正确答案：
5. 二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A. 错误
B. 正确
正确答案：
6. 若哈希表(散列表)的负载因子α < l，则可避免冲突的产生。
A. 错误
B. 正确
正确答案：
7. 对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
A. 错误
B. 正确
正确答案：
8. 在有向图中，度为0的顶点称为终端顶点(或叶子)。
A. 错误
B. 正确
正确答案：
9. 空串是由空格构成的串。
A. 错误
B. 正确
正确答案：
10. 算法的优劣与算法描述语言无关，但与所用计算机有关。
A. 错误
B. 正确
正确答案：
11. 树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点前序遍历和后序遍历是一致的。
A. 错误
B. 正确
正确答案：
12. 栈和队列都是限制存取点的线性结构。
A. 错误
B. 正确
正确答案：
13. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
A. 错误
B. 正确
正确答案：
14. 数组是同类型值的集合。
A. 错误
B. 正确
正确答案：
15. 若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
A. 错误
B. 正确
正确答案：
16. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
A. 错误
B. 正确
正确答案：
17. 一棵哈夫曼树的带权 ( 外部 ) 路径长度等于其中所有分支结点的权值之和。
A. 错误
B. 正确
正确答案：
18. 若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。
A. 错误
B. 正确
正确答案：
19. 堆是满二叉树。
A. 错误
B. 正确
正确答案：
20. 在待排序记录已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
A. 错误
B. 正确
正确答案：

数据结构16秋在线作业2

一、单选题（共 20 道试题，共 60 分。）

1. 由3个结点可以构造出多少种不同的有向有序树？( )
A. 9
B. 10
C. 11
D. 12
正确答案：
2. “堆积”问题是由于()引起的。
A. 同义词之间发生冲突
B. 散列函数
C. 不同的同义词子表结合在一起
D. 散列表“溢出”
正确答案：
3. 下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
A. 有序表的查找
B. 二叉排序树的查找
C. AVL树
D. 散列查找
正确答案：
4. 一个算法应该是（）。
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C
正确答案：
5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续或不连续都可以
正确答案：
6. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A. 二叉排序树
B. 哈夫曼树
C. AVL树
D. 堆
正确答案：
7. 设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
正确答案：
8. 假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）

A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
正确答案：
9. 最佳二叉排序树属于()的数据结构。
A. 动态
B. 静态
C. 线性
D. 无结构
正确答案：
10. 一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
A. acb
B. abc
C. bca
D. cab
正确答案：
11. 判断线索二叉树中某结点p有左子女的条件是 ( )。
A. p ! = NULL
B. p->lchild ! = NULL
C. p->ltag = = 0
D. p->ltag = = 1
正确答案：
12. 相对于顺序存储而言，链接存储的优点是 ( )。
A. 随机存取
B. 节省空间
C. 插入、删除操作方便
D. 结点间关系简单
正确答案：
13. 树最适合用来表示 ( )。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
正确答案：
14. 在一个单链表中，已知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;
正确答案：
15. 递归过程的实现需用到 ( )。
A. 线性表
B. 链表
C. 栈
D. 队列
正确答案：
16. 堆的形状是一棵 ( )。
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. AVL树
正确答案：
17. 数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是 ()。
A. 1165
B. 1170
C. 1175
D. 1180
正确答案：
18. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。
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 ]
正确答案：
19. 每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。
A. 顺序存储
B. 链接存储
C. 索引存储
D. 散列存储
正确答案：
20. 对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。
A. ( 2 , 5 , 12 , 16 ) 28 ( 60 , 32 , 72 )
B. ( 5 , 16 , 2 , 12 ) 28 ( 60 , 32 , 72 )
C. ( 2 , 16 , 12 , 5 ) 28 ( 60 , 32 , 72 )
D. ( 5 , 16 , 2 , 12 ) 28 ( 32 , 60 , 72 )
正确答案：

数据结构16秋在线作业2

二、判断题（共 20 道试题，共 40 分。）

1. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。
A. 错误
B. 正确
正确答案：
2. 折半查找法的查找速度一定比顺序查找法快。
A. 错误
B. 正确
正确答案：
3. 直接访问文件也能顺序访问，只是一般效率不高。
A. 错误
B. 正确
正确答案：
4. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。
A. 错误
B. 正确
正确答案：
5. 二叉树中序线索化后，不存在空指针域。
A. 错误
B. 正确
正确答案：
6. 链表中的表头结点使得插入、删除操作简单。
A. 错误
B. 正确