16春奥鹏东师数据结构在线作业2标准答案
数据结构16春在线作业2一、单选题：
1.对于二维数组A，数组的起始位置LOC(A)=1000，元素长度为2，则LOC(A)为( )。 (满分:3)
A. 1000
B. 1010
C. 1008
D. 1020
2.若要求尽可能快地对序列进行稳定的排序，则应选( ) 。 (满分:3)
A. 快速排序
B. 归并排序
C. 起泡排序
D. 希尔排序
3.下列排序方法中，哪一个是稳定的排序方法？( ) (满分:3)
A. 直接选择排序
B. 直接插入排序
C. 希尔排序
D. 快速排序
4.AVL树中任一结点的平衡因子的绝对值都应小于等于( )。 (满分:3)
A. 0
B. 1
C. 2
D. 3
5.由3个结点可以构造出多少种不同形态的有向树？( ) (满分:3)
A. 2
B. 3
C. 4
D. 5
6.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关( )。 (满分:3)
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 直接选择排序
7.最佳二叉排序树属于( )的数据结构。 (满分:3)
A. 动态
B. 静态
C. 线性
D. 无结构
8.设广义表L =(( a , b , c ) )，则L的长度和深度分别为( )。 (满分:3)
A. 1和1
B. 1和3
C. 1和2
D. 2和3
9.有n个顶点的无向图的边数最少为( )。 (满分:3)
A. 0
B. 1
C. n-1
D. n
10.数据序列( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的( ) 的两趟排序后的结果。 (满分:3)
A. 直接选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
11.对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序( 从小到大序 ) , 一次划分的结果为( )。 (满分:3)
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 )
12.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为( )。 (满分:3)
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
13.非线性结构的逻辑特征是一个结构可能有( )。 (满分:3)
A. 一个前驱和一个后继
B. 多个前驱和一个后继
C. 一个前驱和多个后继
D. 多个前驱和多个后继
14.散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的( ) 方法是散列文件的关键。 (满分:3)
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
15.在一个图中，所有顶点的度数之和等于图的边数的几倍( )。 (满分:3)
A. 1/2
B. 1
C. 2
D. 4
16.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。 (满分:3)
A. O(log2n )
B. O( 1 )
C. O(n )
D. O(nlog2n )
17.在线索二叉树中，p所指结点没有右子树的充要条件是( )。 (满分:3)
A. p->rchild = = NULL
B. p->rtag = = 1
C. p->rtag = = 1且p->rchild = = NULL
D. p->rtag = = 0
18.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。 (满分:3)
A. n
B.(n-1)/2
C. n/2
D.(n+1)/2
19.广义表(( a , b , c , d ) ) 的表尾是( )。 (满分:3)
A. a
B.( )
C.( a
b
c
d )
D.( b
c
d )
20.一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是( )。 (满分:3)
A. acbd
B. abcd
C. dbca
D. adcb
三、判断题：
1.对有序的单链表可以进行折半查找。 (满分:2)
A. 错误
B. 正确
2.广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。 (满分:2)
A. 错误
B. 正确
3.对磁带机而言，ISAM是一种方便的文件组织方法。 (满分:2)
A. 错误
B. 正确
4.对一棵二叉树进行层次次序遍历时，应借助于一个栈。 (满分:2)
A. 错误
B. 正确
5.倒排文件是对次关键字建立索引。 (满分:2)
A. 错误
B. 正确
6.中序线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 (满分:2)
A. 错误
B. 正确
7.文件系统采用索引结构是为了节省存储空间。 (满分: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.虽然关键字序列的顺序不一样，但依此生成的二叉排序树却是一样的。 (满分:2)
A. 错误
B. 正确
16.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。 (满分:2)
A. 错误
B. 正确
17.二叉排序树删除一个结点后，仍是二叉排序树。 (满分:2)
A. 错误
B. 正确
18.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。 (满分:2)
A. 错误
B. 正确
19.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。 (满分:2)
A. 错误
B. 正确
20.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。 (满分:2)
A. 错误
B. 正确
页:
[1]