数据结构18春在线作业2-0003 试卷总分:100 得分:0 一、 单选题 (共 20 道试题,共 60 分) 1.如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。 A.顺序
数据结构18春在线作业2-0003
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
A.顺序查找
B.折半查找
C.分块查找
D.基于属性的查找
2.下面的排序方法中，辅助空间为O( n ) 的是 ()。
A.希尔排序
B.堆排序
C.选择排序
D.归并排序
3.插入、删除只能在同一端进行的线性表，称为 ( )。
A.队列
B.循环队列
C.栈
D.循环栈
4.数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是 ()。
A.1165
B.1170
C.1175
D.1180
5.若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
A.X的双亲
B.X的右子树中最左下的结点
C.X的左子树中最右下的结点
D.X的右子树中最左下的叶结点
6.下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A.广(宽)度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
7.求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A.无向图
B.有向图
C.带权的无向图
D.带权的有向图
8.ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。
A.磁带
B.磁盘
C.光盘
D.外存储器
9.一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
A.acbd
B.abcd
C.dbca
D.adcb
10.若由树转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A.根结点无右子树的二叉树
B.根结点无左子树的二叉树
C.根结点可能有左子树和右子树
D.各结点只有一个子女的二叉树
11.采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
12.算法的计算量的大小称为计算的（）。
A.效率
B.复杂性
C.现实性
D.难度
13.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
14.顺序存储结构的优点是( )。
A.存储密度大
B.插入运算方便
C.删除运算方便
D.结构可动态变化
15.判断线索二叉树中某结点p有右子女的条件是 ( )。
A.p->rtag = = 0
B.p->rtag = = 1
C.p ! = NULL
D.p->lchild ! = NULL
16.倒排文件中倒排表是指 ()。
A.主关键字索引
B.次关键字索引
C.物理顺序与逻辑顺序不一致
D.多关键字索引
17.有n个顶点的无向图的边数最少为 ()。
A.0
B.1
C.n-1
D.n
18.( ) 的遍历仍需要栈的支持。
A.前序线索二叉树
B.中序线索二叉树
C.后序线索二叉树
D.前三种均需要
19.若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A.快速排序
B.归并排序
C.起泡排序
D.希尔排序
20.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A.求子串
B.求串长
C.联接
D.模式匹配
二、 判断题 (共 20 道试题,共 40 分)
1.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插人、删除等操作。
A.错误
B.正确
2.算法的优劣与算法描述语言无关，但与所用计算机有关。
A.错误
B.正确
3.二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A.错误
B.正确
4.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A.错误
B.正确
5.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
A.错误
B.正确
6.在指定结点之前插入新结点时，双链表比单链表更方便。
A.错误
B.正确
7.树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点前序遍历和后序遍历是一致的。
A.错误
B.正确
8.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
A.错误
B.正确
9.直接选择排序算法对n个记录排序，在最好情况下的时间复杂度为O(n)。
A.错误
B.正确
10.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
A.错误
B.正确
11.循环队列通常用指针来实现队列的头尾相接。
A.错误
B.正确
12.广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。
A.错误
B.正确
13.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。
A.错误
B.正确
14.链表中的表头结点仅起到标识的作用。
A.错误
B.正确
15.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
A.错误
B.正确
16.对有序的单链表不能进行折半查找。
A.错误
B.正确
17.最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A.错误
B.正确
18.连通分量是无向图中的极大连通子图。
A.错误
B.正确
19.二维以上的数组其实是一种特殊的广义表。
A.错误
B.正确
20.任何无向图都存在生成树。
A.错误
B.正确
