东师数据结构17春在线作业答案
东师数据结构17春在线作业2一、单选题：
1.一个有n个结点的图，连通分量的个数最少为( )。 (满分:3)
A. 0
B. 1
C. n-1
D. n
2.在下述几种排序方法中，不稳定的排序方法是( )。 (满分:3)
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 归并排序
3.在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是( ) 。 (满分:3)
A. G中有弧＜Vi , Vj >
B. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
4.下列哪一种图的邻接矩阵是对称矩阵？( ) (满分:3)
A. 有向图
B. 无向图
C. AOV 网
D. AOE 网
5.设二维数组A按列优先顺序存储且每个元素占c个单元，则元素A的地址为( )。 (满分:3)
A. LOC(A) +(j*m+i)*c
B. LOC(A) +(i*n+j)*c
C. LOC(A) + [(j-1)*m+i-1]*c
D. LOC(A) + [(i-1)*n+j-1]*c
6.平衡的二叉排序树(AVL树)属于( )的数据结构。 (满分:3)
A. 动态
B. 静态
C. 线性
D. 无结构
7.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是( )。 (满分:3)
A. U
B. V
C. X
D. Y
8.倒排文件中倒排表是指( )。 (满分:3)
A. 主关键字索引
B. 次关键字索引
C. 物理顺序与逻辑顺序不一致
D. 多关键字索引
9.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( ) (满分:3)
A. 线性表
B. 广义表
C. 树形结构
D. 图结构
10.完全二叉树是下列情况的哪一种( )。 (满分:3)
A. 一定是满二叉树
B. 可能是满二叉树
C. 一定不是满二叉树
D. 不是二叉树
11.排序趟数与序列的原始状态有关的排序方法是( ) 排序法。 (满分:3)
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
12.最佳二叉排序树属于( )的数据结构。 (满分:3)
A. 动态
B. 静态
C. 线性
D. 无结构
13.一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。 (满分:3)
A. 不确定
B. 0
C. 1
D. 2
14.算法分析的两个主要方面是( )。 (满分:3)
A. 正确性与健壮性
B. 可读性与可用性
C. 时间复杂度与空间复杂度
D. 数据复杂性与程序复杂性
15.由3个结点可以构造出多少种不同的有向有序树？( ) (满分:3)
A. 9
B. 10
C. 11
D. 12
16.数组A 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A 的地址是( )。 (满分:3)
A. 1165
B. 1170
C. 1175
D. 1180
17.在数据结构中，从逻辑上可以把数据结构分成( )。 (满分:3)
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
18.在线索二叉树中，p所指结点没有左子树的充要条件是( )。 (满分:3)
A. p->lchild = = NULL
B. p->ltag = = 1
C. p->ltag = = 1且p->lchild = = NULL
D. p->ltag = = 0
19.若要求尽可能快地对序列进行稳定的排序，则应选( ) 。 (满分:3)
A. 快速排序
B. 归并排序
C. 起泡排序
D. 希尔排序
20.B+ 树应用在( ) 文件系统中。 (满分:3)
A. ISAM
B. VSAM
C. 顺序
D. 散列
三、判断题：
1.将森树转成二叉树，根结点没有右子树。 (满分:2)
A. 错误
B. 正确
2.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。 (满分:2)
A. 错误
B. 正确
3.快速排序总比简单的排序方法快。 (满分:2)
A. 错误
B. 正确
4.有向图的邻接矩阵是对称的。 (满分:2)
A. 错误
B. 正确
5.用链表( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n-1个空指针。 (满分:2)
A. 错误
B. 正确
6.树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点前序遍历和后序遍历是一致的。 (满分:2)
A. 错误
B. 正确
7.树形结构中元素之间存在一对多的关系。 (满分:2)
A. 错误
B. 正确
8.对有序的单链表可以进行折半查找。 (满分:2)
A. 错误
B. 正确
9.有向图中顶点Vi的度等于其邻接矩阵里第i行中的 l 的个数。 (满分:2)
A. 错误
B. 正确
10.折半查找法的查找速度一定比顺序查找法快。 (满分:2)
A. 错误
B. 正确
11.广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。 (满分:2)
A. 错误
B. 正确
12.串只能按顺序存储方式进行存储。 (满分:2)
A. 错误
B. 正确
13.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。 (满分:2)
A. 错误
B. 正确
14.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。 (满分:2)
A. 错误
B. 正确
15.( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。 (满分:2)
A. 错误
B. 正确
16.无向图的邻接矩阵是对称的。 (满分:2)
A. 错误
B. 正确
17.串是一种数据对象和操作都特殊的线性表。 (满分:2)
A. 错误
B. 正确
18.任何无向图都存在生成树。 (满分:2)
A. 错误
B. 正确
19.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。 (满分:2)
A. 错误
B. 正确
20.二叉树的后序遍历序列中，任意一个结点均处在其子女结点( 若存在)的后面。 (满分:2)
A. 错误
B. 正确
数据结构17春在线作业1
一、单选题：
1.设二维数组A按列优先顺序存储且每个元素占c个单元，则元素A的地址为( )。 (满分:3)
A. LOC(A) +(j*m+i)*c
B. LOC(A) +(i*n+j)*c
C. LOC(A) + [(j-1)*m+i-1]*c
D. LOC(A) + [(i-1)*n+j-1]*c
2.在下述几种排序方法中，辅助空间需要最多的是( )。 (满分:3)
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
3.用ISAM组织文件适合于( )。 (满分:3)
A. 磁带
B. 磁盘
C. 光盘
D. 外存储器
4.在k叉树中，度为0的结点称为( )。 (满分:3)
A. 根
B. 叶
C. 祖先
D. 子孙
5.若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为( )。 (满分:3)
A. 79,46,56,38,40,84
B. 84,79,56,38,40,46
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
6.AVL树中任一结点的平衡因子的绝对值都应小于等于( )。 (满分:3)
A. 0
B. 1
C. 2
D. 3
7.求顶点间的最短路径问题，考虑的是下面的哪一种图( )。 (满分:3)
A. 无向图
B. 有向图
C. 带权的无向图
D. 带权的有向图
8.n个结点的线索二叉树上含有的线索数为( )。 (满分:3)
A. n-1
B. n
C. n +1
D. 2n
9.一个存储结点存放一个( )。 (满分:3)
A. 数据项
B. 数据元素
C. 数据结构
D. 数据类型
10.堆的形状是一棵( )。 (满分:3)
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. AVL树
11.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为( )。 (满分:3)
A. LOC(a0)+(i-1)*c
B. LOC(a0)+i*c
C. LOC(a0)-i*c
D. LOC(a0)+(i+1)*c
12.稀疏矩阵常用的压缩存储方法有两种，它们是( )。 (满分:3)
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
13.head指向的非空的单循环链表的尾结点(由p所指向)满足( )。 (满分:3)
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
14.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用( ) 的方法可降低所需的代价。 (满分:3)
A. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
D. 连续排序
15.二叉树在线索化后，仍不能有效求解的问题是( )。 (满分:3)
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序前驱
C. 中序线索二叉树中求中序后继
D. 后序线索二叉树中求后序后继
16.算法分析的两个主要方面是( )。 (满分:3)
A. 正确性与健壮性
B. 可读性与可用性
C. 时间复杂度与空间复杂度
D. 数据复杂性与程序复杂性
17.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。 (满分:3)
A. O(log2n )
B. O( 1 )
C. O(n )
D. O(nlog2n )
18.递归过程的实现需用到( )。 (满分:3)
A. 线性表
B. 链表
C. 栈
D. 队列
19.若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X的中序前驱为( )。 (满分:3)
A. X的双亲
B. X的右子树中最左下的结点
C. X的左子树中最右下的结点
D. X的左子树中最右下的叶结点
20.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为( )。 (满分:3)
A. 10
B. 16
C. 31
D. 32
三、判断题：
1.取顺序表的第i个元素的时间与i的大小无关。 (满分:2)
A. 错误
B. 正确
2.对于查找运算来说，链接存储结构一定优于顺序存储结构。 (满分:2)
A. 错误
B. 正确
3.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。 (满分:2)
A. 错误
B. 正确
4.最佳二叉排序树是AVL树( 平衡二叉排序树 ) 。 (满分:2)
A. 错误
B. 正确
5.快速排序总比简单的排序方法快。 (满分:2)
A. 错误
B. 正确
6.最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。 (满分:2)
A. 错误
B. 正确
7.算法可以用不同的语言描述，如果用C语言或 JAVA 语言等高级语言来描述，则算法实际上就是程序了。 (满分:2)
A. 错误
B. 正确
8.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。 (满分:2)
A. 错误
B. 正确
9.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。 (满分:2)
A. 错误
B. 正确
10.二叉树的中序遍历序列中，任意一个结点均处在其左子女结点( 若存在 )的前面。 (满分:2)
A. 错误
B. 正确
11.数组不适合作为任何二叉树的存储结构。 (满分:2)
A. 错误
B. 正确
12.二叉树只能用二叉链表表示。 (满分:2)
A. 错误
B. 正确
13.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。 (满分:2)
A. 错误
B. 正确
14.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 (满分:2)
A. 错误
B. 正确
15.需要借助于一个队列来实现DFS算法。 (满分:2)
A. 错误
B. 正确
16.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。 (满分:2)
A. 错误
B. 正确
17.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。 (满分:2)
A. 错误
B. 正确
18.完全二叉树肯定是平衡二叉排序树。 (满分:2)
A. 错误
B. 正确
19.直接访问文件也能顺序访问，只是一般效率不高。 (满分:2)
A. 错误
B. 正确
20.栈是实现过程和函数等子程序所必需的结构。 (满分:2)
A. 错误
B. 正确
页:
[1]