东师数据结构18秋在线作业2答案答案
数据结构18秋在线作业2-0002
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A.直接插入
B.直接选择
C.冒泡
D.归并
2.递归过程的实现需用到 ( )。
A.线性表
B.链表
C.栈
D.队列
3.折半查找要求结点 ()。
A.无序、顺序存储
B.无序、链接存储
C.有序、顺序存储
D.有序、链接存储
4.一个有向无环图的拓扑排序序列 () 是唯一的。
A.一定
B.不一定
C.可能
D.三者均不对
5.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A.求子串
B.求串长
C.联接
D.模式匹配
6.下面关于串的叙述中，哪一个是不正确的? ( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
7.设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A.Ο( 1 )
B.Ο(log2n)
C.Ο(n)
D.Ο(nlog2n)
8.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A.希尔排序
B.插入排序
C.归并排序
D.选择排序
9.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
A.U
B.V
C.X
D.Y
10.一个有n个结点的图，连通分量的个数最多为 ()。
A.0
B.1
C.n-1
D.n
11.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。
A.h+1
B.2h-1
C.2h
D.2h+1
12.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
13.在数据结构中，从逻辑上可以把数据结构分成 ( )。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
14.若对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
15.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
A.同等概率
B.最大概率
C.最小概率
D.平均概率
16.在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 ()。
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.希尔排序
17.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
D.LOC(a0)+(i+1)*c
18.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
D.任一结点无右子女
19.head指向的不带表头结点的单链表为空的判定条件是 ( )。
A.head = = NULL
B.head->next = = head
C.head ! = NULL
D.head->next = = NULL
20.静态链表中的指针表示的是()。
A.内存地址
B.数组下标
C.下一元素地址
D.左、右子女地址
东师数据结构18秋在线作业2答案多选题
二、 判断题 (共 20 道试题,共 40 分)
1.对于查找运算来说，链接存储结构一定优于顺序存储结构。
A.错误
B.正确
2.二叉树中序线索化后，不存在空指针域。
A.错误
B.正确
3.连通图的各边权值均不相同，则该图的最小生成树是唯一的。
A.错误
B.正确
4.任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A.错误
B.正确
5.二叉树只能用二叉链表表示。
A.错误
B.正确
6.任何无向图都存在生成树。
A.错误
B.正确
7.在指定结点之前插入新结点时，双链表比单链表更方便。
A.错误
B.正确
8.对有序的单链表可以进行折半查找。
A.错误
B.正确
9.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
A.错误
B.正确
10.必须把一般的树转换成二叉树后才能进行存储。
A.错误
B.正确
11.树形结构中元素之间存在一对多的关系。
A.错误
B.正确
12.数组是同类型值的集合。
A.错误
B.正确
13.串是一种数据对象和操作都特殊的线性表。
A.错误
B.正确
14.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
A.错误
B.正确
15.二叉排序树删除一个结点后，仍是二叉排序树。
A.错误
B.正确
16.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。
A.错误
B.正确
17.归并排序的辅助存储空间代价为O(1 )。
A.错误
B.正确
18.数组不适合作为任何二叉树的存储结构。
A.错误
B.正确
19.任何二叉树的后序线索树进行后序遍历时都必须用栈。
A.错误
B.正确
东师数据结构18秋在线作业2答案历年真题如下：
