数据结构18秋在线作业2-0005 试卷总分:100 得分:0 一、 单选题 (共 20 道试题,共 60 分) 1.在下列情况中，可称为二叉树的是 ( )。 A.每个结点至多有两棵子树的树 B.哈夫曼树 C.每个结点至多有
数据结构18秋在线作业2-0005
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.在下列情况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
2.若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
A.X的双亲
B.X的右子树中最左下的结点
C.X的左子树中最右下的结点
D.X的右子树中最左下的叶结点
3.有n个顶点的有向图的边数最多为 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
4.对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A.1000
B.1010
C.1008
D.1020
5.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
6.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A.堆排序＜快速排序＜归并排序
B.堆排序＜归并排序＜快速排序
C.堆排序＞归并排序＞快速排序
D.堆排序＞快速排序＞归并排序
7.一个存储结点存放一个（）。
A.数据项
B.数据元素
C.数据结构
D.数据类型
8.在数据结构中，从逻辑上可以把数据结构分成 ( )。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
9.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
A.x = top; top = top->next;
B.top = top->next; x = top->data;
C.x = top->data;
D.x = top->data; top = top->next;
10.B+ 树应用在 () 文件系统中。
A.ISAM
B.VSAM
C.顺序
D.散列
11.由3个结点可以构造出多少种不同形态的有向树？( )
A.2
B.3
C.4
D.5
12.设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A.1和1
B.1和3
C.1和2
D.2和3
13.设有n个结点的AVL树，其平均查找长度为 ()。
A.Ο( 1 )
B.Ο(log2n)
C.Ο(n)
D.Ο(nlog2n)
14.n个结点的线索二叉树上含有的线索数为 ( )。
A.n-1
B.n
C.n +1
D.2n
15.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
A.n
B.(n-1)/2
C.n/2
D.(n+1)/2
16.经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A.a
B.b
C.1
D.2
17.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A.求子串
B.求串长
C.联接
D.模式匹配
18.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
19.下述文件中适合于磁带存储的是 ()。
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件
20.插入、删除只能在同一端进行的线性表，称为 ( )。
A.队列
B.循环队列
C.栈
D.循环栈
二、 判断题 (共 20 道试题,共 40 分)
1.数据对象是具有相同性质的数据元素的集合。
A.错误
B.正确
2.连通图的各边权值均不相同，则该图的最小生成树是唯一的。
A.错误
B.正确
3.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
A.错误
B.正确
4.在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
A.错误
B.正确
5.带权的连通无向图的最小(代价)生成树必是唯一的。
A.错误
B.正确
6.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A.错误
B.正确
7.哈希表(散列表)的平均查找长度与处理冲突的方法无关。
A.错误
B.正确
8.取顺序表的第i个元素的时间与i的大小无关。
A.错误
B.正确
9.循环链表不是线性表。
A.错误
B.正确
10.采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。
A.错误
B.正确
11.连通分量是无向图中的极大连通子图。
A.错误
B.正确
12.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A.错误
B.正确
13.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
A.错误
B.正确
14.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。
A.错误
B.正确
15.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
A.错误
B.正确
16.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A.错误
B.正确
17.循环队列通常用指针来实现队列的头尾相接。
A.错误
B.正确
18.完全二叉树的存储结构通常采用顺序存储结构。
A.错误
B.正确
19.循环队列也存在空间溢出问题。
A.错误
B.正确
20.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。
A.错误
B.正确
