东北师范大学东师数据结构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.  算法的优劣与算法描述语言无关，但与所用计算机有关。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。