石油华东《数据结构》2016年秋学期在线作业一二三资料

admin

《数据结构》2016年秋学期在线作业（一）




一、单选题（共 20 道试题，共 100 分。）

1.  用堆栈求算术表达式+*(-)-e/f的后缀表达式为（ ）。
. -*+ef/-
. +*(-)-e/f
. ef-*+/-
. -*ef/+-
正确资料：
2.  一个堆栈的入栈序列为e，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（ ）。
. e
. e
. e
. e
正确资料：
3.  关于逻辑结构和存储结构，正确的描述是（ ）。
. 线性数据结构必须采用链式存储结构
. 一种逻辑结构，可以用不同的存储结构来存储，反之亦然
. 一种逻辑结构，可以用不同的存储结构来存储，反之不然
. 一种存储结构只能表示一种逻辑结构
正确资料：
4.  在线性表的顺序存储结构中，逻辑上相邻的数据元素的物理位置（ ），在链式存储结构中，逻辑上相邻的数据元素的物理位置（ ）。
. 必相邻 必相邻
. 必相邻 不一定相邻
. 不一定相邻 必相邻
. 不一定相邻 不一定相邻
正确资料：
5.  关于链表的特点描述不正确的是（ ）。
. 存储空间不一定连续；
. 元素之间的后继关系是由指针来体现的；
. 逻辑上相邻，物理上不一定相邻；
. 随机存取（顺序存取），即访问任何一个元素的时间相同。
正确资料：
6.  在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（ ）。
. q.front % m = 0 ;
. q.rer % m = 0 ;
. q.front = q.rer ;
. (q.front+1) % m = q.rer;
正确资料：
7.  以下说法错误的是（ ）。
. 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。
. 对单链表来说，只有从头结点开始才能扫描表中全部结点。
. 双链表的特点是找结点的前趋和后继都很容易。
. 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
正确资料：
8.  若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
. 顺序表
. 单链表
. 双链表
. 单循环链表
正确资料：
9.  题目和资料如下图所示：

.
.
.
.
正确资料：
10.  下面关于线性表的叙述中，错误的是哪一个？（ ）。
. 线性表采用顺序存储，必须占用一片连续的存储单元。
. 线性表采用顺序存储，便于进行插入和删除操作。
. 线性表采用链接存储，不必占用一片连续的存储单元。
. 线性表采用链接存储，便于插入和删除操作。
正确资料：
11.  以下判断不正确的是（ ）。
. 顺序存储的线性表可随机存取。
. 同一线性表中的数据元素应具有相同的特性。
. 顺序存储方式的优点是存储密度大，插入、删除操效率高。
. 在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
正确资料：
12.  在数据结构中，从逻辑上可以把数据结构分成（ ）。
. 动态结构和静态结构
. 紧凑结构和非紧凑结构
. 线性结构和非线性结构
. 内部结构和外部结构
正确资料：
13.  最大容量为n的循环队列，队尾指针是rer，队头是front，则队空的条件是（ ）。
. (rer+1) % n = front
. rer = front
. rer+1 = front
. (rer-l) % n = front
正确资料：
14.  链表不具有的特点是（ ）。
. 插入、删除不需要移动元素
. 可随机访问任一元素
. 不必事先估计存储空间
. 所需空间与线性长度成正比
正确资料：
15.  线性结构中的一个结点代表一个（ ）。
. 数据元素
. 数据项
. 数据
. 数据结构
正确资料：
16.  关于算法，下面描述正确的是（ ）。
. 时间复杂度就是算法的执行时间
. 算法必须有输入量和输出量
. 算法就是程序
. 时间复杂度仅反映时间关于问题规模的增长率
正确资料：
17.  单链表中，增加头结点的目的是为了（ ）。
. 使单链表至少有一个结点
. 标示表结点中首结点的位置
. 方便运算的实现
. 说明单链表是线性表的链式存储实现
正确资料：
18.  （ ）是指数据中的一个个的个体，是数据的基本单位。
. 数据相
. 数据元素
. 数据结构
. 数据类型
正确资料：
19.  带头结点的双向链表中，Prior 指针指向当前结点的前驱，Next指向当前结点的后继。在指针p指向的结点前插入指针s指向的结点，以下操作不正确的是（ ）。
. s->Prior=p->Prior ; p->Prior->Next=s ; s->Next=p ; p->Prior=s ;
. s->Next=p ; s->Prior=p->Prior ; p->Prior->Next=s ; p->Prior=s ;
. s->Prior=p->Prior ; s->Next=p ; p->Prior->Next=s ; p->Prior=s ;
. s->Prior=p->Prior ; p->Prior=s ; p->Prior->Next=s ; s->Next=
正确资料：
20.  有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）。
. 5 4 3 6 1 2
. 4 5 3 1 2 6
. 3 4 6 5 2 1
. 2 3 4 1 5 6
正确资料：

《数据结构》2016年秋学期在线作业（二）




一、单选题（共 20 道试题，共 100 分。）

1.  下列判断正确的是（ ）。
. 二叉树是树的特例。
. 具有n个结点的完全二叉树的深度为n/2。
. Huffmn树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
. 栈和队列都是限制存取点的线性结构。
正确资料：
2.  采用F算法在主串            中查找子串       的查找次数为（ ）。
. 13
. 14
. 15
. 16
正确资料：
3.  已知广义表: =(,), =(,), =(,(,),), 求下列运算的结果:til(he(til())) = （ ）。
. （）
.
. ()
. ()
正确资料：
4.  假设主串的长度为m，模式串的长度为n，F算法在一般和最坏情况下的时间复杂性分别为 （ ），所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。
. n+m n*m
. n m
. n*m n+m
. m n
正确资料：
5.  下列说法正确的是 （ ）。
. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
正确资料：
6.  某非空二叉树的先序和后序序列正好相反，则二叉树一定是（ ）的二叉树。
. 空或只有一个结点
. 高度等于其结点数
. 任一结点无左孩子
. 任一结点无右孩子
正确资料：
7.  假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为（ ）。
. n+m
. n*m
. n
. m
正确资料：
8.  设是一个m*n阶矩阵，按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若[1,1]的存储地址为se，则[i,j]的存储地址为（ ）。
. se+[(i-1)*m+(j-1)]*w
. se+[(j-1)*m+(i-1)]*w
. se+（j*m+i）*w
. se+（j*m+i）*w
正确资料：
9.  关于完全二叉树，不正确的描述是（ ）。
. 每个结点必须首先有左儿子，然后才能有右儿子。
. 在具有相同结点的所有二叉树中，它的高度最小。
. 每个结点的左右子树的高度最多相差为1。
. 没有度为1的结点。
正确资料：
10.  下面关于数据结构的叙述中，正确的叙述是（ ）。
. 顺序存储方式的优点是存储密度大，且插、删除运算效率高
. 链表中每个结点都恰好包含一个指针
. 包含n个结点的二叉排序树的最大检索长度为log2n
. 将一棵树转为二叉树后，根结点无右子树
正确资料：
11.  树根的层次为1，则有64个结点的完全二叉树的深度为（ ）。
. 8
. 7
. 6
. 5
正确资料：
12.  下面关于完全二叉树的特点叙述不正确的是（ ）。
. 只有最后一层是不满的，不满层的结点首先出现在左边
. 至多只有最下面的两层结点的度小于2
. 左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
. 叶子只能出现在最后两层上；
正确资料：
13.  在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（ ）。
. n-1
. 2n-1
. n+1
. 2n+1
正确资料：
14.  在线索二叉树中，t 所指结点没有左子树的充要条件是（ ）。
. t->lhil!=NULL
. t->ltg==1
. t->ltg==1且 t->left!=NULL
. 以上都不对
正确资料：
15.  在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（ ）。
. 都不相同
. 完全相同
. 前序遍历和中序遍历相同，而与后序遍历不同
. 前序遍历和后序遍历相同，而与中序遍历不同
正确资料：
16.  一维数组和线性表的区别为 （ ） 。
. 前者长度固定,后者长度可变
. 两者长度均固定
. 前者长度可变,后者长度固定
. 两者长度均可变
正确资料：
17.  对广义表L=((,),,)进行操作til(he(L))的结果是（ ）。
. (, )
. ( )
.
. ()
正确资料：
18.  设是n*n的对称矩阵，将的对角线及对角线上方的元素以列为主的次序存放在一维数组[1..n(n+1)/2]中，对上述任一元素ij(1≤i，j≤n，且i≤j)在中的位置为（ ）。
. i(i-l)/2+j
. j(j-l)/2+i
. j(j-l)/2+i-1
. i(i-l)/2+j-1
正确资料：
19.  
题目和资料如下图所示：

.
.
.
.
正确资料：
20.  树最适合用来表示（ ）。
. 有序数据元素
. 无序数据元素
. 元素之间具有分支层次关系的数据
. 元素之间无联系的数据
正确资料：



《数据结构》2016年秋学期在线作业（三）




一、单选题（共 20 道试题，共 100 分。）

1.  图结构的广度优先搜索遍历算法中使用了（ ）。
. 堆栈
. 队列
. 堆栈和队列
. 以上都不正确。
正确资料：
2.  VL树是一种平衡的二叉排序树，树中任一结点的（ ）。
. 左、右子树的高度均相同
. 左、右子树高度差的绝对值不超过1
. 左子树的高度均大于右子树的高度
. 左子树的高度均小于右子树的高度
正确资料：
3.  哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（ ）次探测。
. k
. k-1
. k(k-1)/2
. 1+k(k-1)/2
正确资料：
4.  二叉查找树的查找效率与二叉树的树型有关, 在（ ）时其查找效率最低。
. 结点太多
. 完全二叉树
. 呈单枝树
. 结点太复杂。
正确资料：
5.  下面关于哈希（Hsh，杂凑）查找的说法正确的是（ ）。
. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
. 除留余数法是所有哈希函数中最好的
. 不存在特别好与坏的哈希函数，要视情况而定
. 在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
正确资料：
6.  在有序表中使用折半查找法的平均时间是（ ）。
. O(1)
. O(n)
. O(log2n)
. O(n2)
正确资料：
7.  设有一个无向图G=（V，E）和G'=（V'，E'）如果G'为G的生成树，则下面不正确的说法是（ ）。
. G'为G 的子图
. G'为G 的连通分量
. G'为G的极小连通子图且V'=V
. G'为G的一个无环子图
正确资料：
8.  进行二分查找要求查找表必须（ ）。
. 以顺序方式存储。
. 以链式方式存储。
. 以顺序方式存储且数据元素按关键字有序排列。
. 以链式方式存储且数据元素按关键字有序排列。
正确资料：
9.  设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？（ ）。
. f->lhil=null
. f->lhil=p->lhil
. f->lhil=p->rhil
. 都不是
正确资料：
10.  下列说法不正确的是（ ）。
. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
. 图的深度遍历不适用于有向图
. 遍历的基本算法有两种：深度遍历和广度遍历
. 图的深度遍历是一个递归过程
正确资料：
11.  对于一组结点，从空树开始，把他们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于（ ）。
. 结点的输入顺序
. 结点的存储结构
. 结点的取值范围
. 计算机的硬件
正确资料：
12.  下面关于图的存储的叙述中正确的是（ ）。
. 用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
. 用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
. 用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
正确资料：
13.  
题目和资料如下图所示：

.
.
.
.
正确资料：
14.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）。
. O(n)
. O(e)
. O(n+e)
. O(n2)
正确资料：
15.  已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）。
. 1.0
. 2.9
. 3.4
. 5.5
正确资料：
16.  以下说法错误的是（ ）。
. 散列法存储的基本思想是由关键码的值决定数据的存储地址。
. 散列表的结点中只包含数据元素自身的信息，不包含任何指针。
. 装填因子是散列法的一个重要参数，它反映散列表的装填程度。
. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
正确资料：
17.  关键路径是事件结点网络中（ ）。
. 从源点到汇点的最长路径
. 从源点到汇点的最短路径
. 最长回路
. 最短回路
正确资料：
18.  
题目和资料如下图所示：

.
.
.
.
正确资料：
19.  希尔排序和快速排序分别属于（ ）。
. 交换排序 选择排序
. 插入排序 选择排序
. 选择排序 归并排序
. 交换排序 选择排序
正确资料：
20.  n个顶点的有向完全图中含有有向边的数目最多为（ ）。
. n-1
. n
. n(n-1)/2
. n(n-1)
正确资料：