中石油(华东)《数据结构》14春在线作业答案
中国石油大学(华东)《数据结构》2014年春学期在线作业（一）试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.（ ）是指数据中的一个个的个体，是数据的基本单位。
A. 数据相
B. 数据元素
C. 数据结构
D. 数据类型
满分：5分
2.以下说法错误的是（ ）。
A. 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。
B. 对单链表来说，只有从头结点开始才能扫描表中全部结点。
C. 双链表的特点是找结点的前趋和后继都很容易。
D. 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
满分：5分
3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）。
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
满分：5分
4.在线性表的顺序存储结构中，逻辑上相邻的数据元素的物理位置（ ），在链式存储结构中，逻辑上相邻的数据元素的物理位置（ ）。
A. 必相邻 必相邻
B. 必相邻 不一定相邻
C. 不一定相邻 必相邻
D. 不一定相邻 不一定相邻
满分：5分
5.以下判断不正确的是（ ）。
A. 顺序存储的线性表可随机存取。
B. 同一线性表中的数据元素应具有相同的特性。
C. 顺序存储方式的优点是存储密度大，插入、删除操效率高。
D. 在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
满分：5分
6.关于算法，下面描述正确的是（ ）。
A. 时间复杂度就是算法的执行时间
B. 算法必须有输入量和输出量
C. 算法就是程序
D. 时间复杂度仅反映时间关于问题规模的增长率
满分：5分
7.一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（ ）。
A. edcba
B. decba
C. decab
D. abcde
满分：5分
8.题目和答案如下图所示：
A.
B.
C.
D.
满分：5分
9.在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（ ）。
A. q.front % m = 0 ;
B. q.rear % m = 0 ;
C. q.front = q.rear ;
D. (q.front+1) % m = q.rear;
满分：5分
10.用堆栈求算术表达式a+b*(c-d)-e/f的后缀表达式为（ ）。
A. abcd-*+ef/-
B. a+b*(c-d)-e/f
C. abcdef-*+/-
D. abc-d*ef/+-
满分：5分
11.关于链表的特点描述不正确的是（ ）。
A. 存储空间不一定连续；
B. 元素之间的后继关系是由指针来体现的；
C. 逻辑上相邻，物理上不一定相邻；
D. 随机存取（顺序存取），即访问任何一个元素的时间相同。
满分：5分
12.带头结点的双向链表中，Prior 指针指向当前结点的前驱，Next指向当前结点的后继。在指针p指向的结点前插入指针s指向的结点，以下操作不正确的是（ ）。
A. s->Prior=p->Prior ; p->Prior->Next=s ; s->Next=p ; p->Prior=s ;
B. s->Next=p ; s->Prior=p->Prior ; p->Prior->Next=s ; p->Prior=s ;
C. s->Prior=p->Prior ; s->Next=p ; p->Prior->Next=s ; p->Prior=s ;
D. s->Prior=p->Prior ; p->Prior=s ; p->Prior->Next=s ; s->Next=
满分：5分
13.线性结构中的一个结点代表一个（ ）。
A. 数据元素
B. 数据项
C. 数据
D. 数据结构
满分：5分
14.下面关于线性表的叙述中，错误的是哪一个？（ ）。
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
C. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作。
满分：5分
15.在数据结构中，从逻辑上可以把数据结构分成（ ）。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
满分：5分
16.链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
满分：5分
17.关于逻辑结构和存储结构，正确的描述是（ ）。
A. 线性数据结构必须采用链式存储结构
B. 一种逻辑结构，可以用不同的存储结构来存储，反之亦然
C. 一种逻辑结构，可以用不同的存储结构来存储，反之不然
D. 一种存储结构只能表示一种逻辑结构
满分：5分
18.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
满分：5分
19.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A. (rear+1) % n = front
B. rear = front
C. rear+1 = front
D. (rear-l) % n = front
满分：5分
20.单链表中，增加头结点的目的是为了（ ）。
A. 使单链表至少有一个结点
B. 标示表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储实现
《数据结构》2014年春学期在线作业（二）
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.关于完全二叉树，不正确的描述是（ ）。
A. 每个结点必须首先有左儿子，然后才能有右儿子。
B. 在具有相同结点的所有二叉树中，它的高度最小。
C. 每个结点的左右子树的高度最多相差为1。
D. 没有度为1的结点。
满分：5分
2.设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A的存储地址为base，则A的存储地址为（ ）。
A. base+[(i-1)*m+(j-1)]*w
B. base+[(j-1)*m+(i-1)]*w
C. base+（j*m+i）*w
D. base+（j*m+i）*w
满分：5分
3.一维数组和线性表的区别为 （ ） 。
A. 前者长度固定,后者长度可变
B. 两者长度均固定
C. 前者长度可变,后者长度固定
D. 两者长度均可变
满分：5分
4.树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：5分
5.某非空二叉树的先序和后序序列正好相反，则二叉树一定是（ ）的二叉树。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
满分：5分
6.
题目和答案如下图所示：
A.
B.
C.
D.
满分：5分
7.假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为（ ）。
A. n+m
B. n*m
C. n
D. m
满分：5分
8.在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（ ）。
A. 都不相同
B. 完全相同
C. 前序遍历和中序遍历相同，而与后序遍历不同
D. 前序遍历和后序遍历相同，而与中序遍历不同
满分：5分
9.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为（ ）。
A. i(i-l)/2+j
B. j(j-l)/2+i
C. j(j-l)/2+i-1
D. i(i-l)/2+j-1
满分：5分
10.下面关于数据结构的叙述中，正确的叙述是（ ）。
A. 顺序存储方式的优点是存储密度大，且插、删除运算效率高
B. 链表中每个结点都恰好包含一个指针
C. 包含n个结点的二叉排序树的最大检索长度为log2n
D. 将一棵树转为二叉树后，根结点无右子树
满分：5分
11.在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为（ ）。
A. n-1
B. 2n-1
C. n+1
D. 2n+1
满分：5分
12.假设主串的长度为m，模式串的长度为n，BF算法在一般和最坏情况下的时间复杂性分别为 （ ），所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。
A. n+m n*m
B. n m
C. n*m n+m
D. m n
满分：5分
13.在线索二叉树中，t 所指结点没有左子树的充要条件是（ ）。
A. t->lchild!=NULL
B. t->ltag==1
C. t->ltag==1且 t->left!=NULL
D. 以上都不对
满分：5分
14.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（ ）。
A. (c,d )
B. (d )
C. b
D. (b)
满分：5分
15.下面关于完全二叉树的特点叙述不正确的是（ ）。
A. 只有最后一层是不满的，不满层的结点首先出现在左边
B. 至多只有最下面的两层结点的度小于2
C. 左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
D. 叶子只能出现在最后两层上；
满分：5分
16.下列说法正确的是 （ ）。
A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
满分：5分
17.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) = （ ）。
A. （a）
B. A
C. (b)
D. (A)
满分：5分
18.下列判断正确的是（ ）。
A. 二叉树是树的特例。
B. 具有n个结点的完全二叉树的深度为n/2。
C. Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
D. 栈和队列都是限制存取点的线性结构。
满分：5分
19.树根的层次为1，则有64个结点的完全二叉树的深度为（ ）。
A. 8
B. 7
C. 6
D. 5
满分：5分
20.采用BF算法在主串a a b a a a c a a c b b b中查找子串a a a c a a c b的查找次数为（ ）。
A. 13
B. 14
C. 15
D. 16
《数据结构》2014年春学期在线作业（三）
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
题目和答案如下图所示：
A.
B.
C.
D.
满分：5分
2.AVL树是一种平衡的二叉排序树，树中任一结点的（ ）。
A. 左、右子树的高度均相同
B. 左、右子树高度差的绝对值不超过1
C. 左子树的高度均大于右子树的高度
D. 左子树的高度均小于右子树的高度
满分：5分
3.n个顶点的有向完全图中含有有向边的数目最多为（ ）。
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
满分：5分
4.希尔排序和快速排序分别属于（ ）。
A. 交换排序 选择排序
B. 插入排序 选择排序
C. 选择排序 归并排序
D. 交换排序 选择排序
满分：5分
5.下面关于哈希（Hash，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
满分：5分
6.下列说法不正确的是（ ）。
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 图的深度遍历不适用于有向图
C. 遍历的基本算法有两种：深度遍历和广度遍历
D. 图的深度遍历是一个递归过程
满分：5分
7.在有序表中使用折半查找法的平均时间是（ ）。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n2)
满分：5分
8.二叉查找树的查找效率与二叉树的树型有关, 在（ ）时其查找效率最低。
A. 结点太多
B. 完全二叉树
C. 呈单枝树
D. 结点太复杂。
满分：5分
9.下面关于图的存储的叙述中正确的是（ ）。
A. 用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
B. 用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
C. 用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
D. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
满分：5分
10.
题目和答案如下图所示：
A.
B.
C.
D.
满分：5分
11.进行二分查找要求查找表必须（ ）。
A. 以顺序方式存储。
B. 以链式方式存储。
C. 以顺序方式存储且数据元素按关键字有序排列。
D. 以链式方式存储且数据元素按关键字有序排列。
满分：5分
12.关键路径是事件结点网络中（ ）。
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长回路
D. 最短回路
满分：5分
13.对于一组结点，从空树开始，把他们插入到二叉排序树中，就建立了一棵二叉排序树。这时，整个二叉排序树的形状取决于（ ）。
A. 结点的输入顺序
B. 结点的存储结构
C. 结点的取值范围
D. 计算机的硬件
满分：5分
14.设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？（ ）。
A. f->lchild=null
B. f->lchild=p->lchild
C. f->lchild=p->rchild
D. 都不是
满分：5分
15.图结构的广度优先搜索遍历算法中使用了（ ）。
A. 堆栈
B. 队列
C. 堆栈和队列
D. 以上都不正确。
满分：5分
16.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n2)
满分：5分
17.设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）。
A. G’为G 的子图
B. G’为G 的连通分量
C. G’为G的极小连通子图且V’=V
D. G’为G的一个无环子图
满分：5分
18.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（ ）次探测。
A. k
B. k-1
C. k(k-1)/2
D. 1+k(k-1)/2
满分：5分
19.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）。
A. 1.0
B. 2.9
C. 3.4
D. 5.5
满分：5分
20.以下说法错误的是（ ）。
A. 散列法存储的基本思想是由关键码的值决定数据的存储地址。
B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针。
C. 装填因子是散列法的一个重要参数，它反映散列表的装填程度。
D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
《数据结构》2014年春学期在线作业（四）
试卷总分：100 测试时间：--
一、单选题（共15道试题，共75分。）
1.已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中元素e的运算是（ ）。
A. head(tail(LS))
B. tail(head(LS))
C. head(tail(head(tail(LS))))
D. head(tail(tail(head(LS))))
满分：5分
2.判定一个栈ST（最多元素为m0）为空的条件是（ ）。
A. ST->top!=0
B. ST->top==0
C. ST->top!=m0
D. ST->top==m0
满分：5分
3.二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、…、8，列下标j=1、2、…、4、若A按行先存储，元素A的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
A. A
B. A
C. A
D. A
满分：5分
4.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点。
A. 13
B. 12
C. 26
D. 25
满分：5分
5.
题目和答案如下图所示：
A.
B.
C.
D.
满分：5分
6.算法分析的目的是（ ）。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易懂性和文档性
满分：5分
7.若串S=“software”,其子串数目是（ ）。
A. 8
B. 37
C. 36
D. 9
满分：5分
8.下列哪一个关键码序列不符合堆的定义？（ ）。
A. (102，87，100，79，82，62，84，42，22，12，68)
B. (102，100，87，84，82，79，68，62，42，22，12)
C. (12，22，42，62，68，79，82，84，87，100，102)
D. (102，87，42，79，82，62，68，100，84，12，22)
满分：5分
9.二分查找法要求查找表中各元素的键值必须是（ ）排列。
A. 递增或递减
B. 递增
C. 递减
D. 无序
满分：5分
10.若在线性表中采用折半查找法查找元素，该线性表应该（ ）。
A. 元素按值有序
B. 采用顺序存储结构
C. 元素按值有序，且采用顺序存储结构
D. 元素按值有序，且采用链式存储结构
满分：5分
11.设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）。
A. 联接
B. 求子串
C. 字符定位
D. 子串定位
满分：5分
12.判定“带头结点的链队列为空”的条件是（ ）。
A. Q.front==NULL
B. Q.rear==NULL
C. Q.front==Q.rear
D. Q.front!=Q.rear
满分：5分
13.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（ ）存储方式节省时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
满分：5分
14.设深度为K的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为（ ）。
A. K+1
B. 2K
C. 2K-1
D. 2K+1
满分：5分
15.数组A中，每个元素A的长度为3个字节，行下标i从1到8。列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A 的起始地址为（ ）。
A. SA+141
B. SA+180
C. SA+222
D. SA+225
满分：5分
二、判断题（共5道试题，共25分。）
1.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
A. 错误
B. 正确
满分：5分
2.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
A. 错误
B. 正确
满分：5分
3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
A. 错误
B. 正确
满分：5分
4.将一棵树转换成二叉树后，根结点没有左子树。
A. 错误
B. 正确
满分：5分
5.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
A. 错误
B. 正确
满分：5分
页:
[1]