中国石油大学（华东）《数据结构》2021年秋季学期在线作业（二）

第1,树根的层次为1，则有64个结点的完全二叉树的深度为（   ）。

A、8

B、7

C、6

D、5

正确答案:

第2题,设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（   ）个结点。

A、13

B、12

C、26

D、25

正确答案:

第3题,设A是一个m*n阶矩阵，A按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若A[1,1]的存储地址为base，则A[i,j]的存储地址为（   ）。

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

正确答案:

第4题,对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（   ）。

A、(c,d )

B、(d )

C、b

D、(b)

正确答案:

,下列说法正确的是 （   ）。

A、树的先根遍历序列与其对应的二叉树的先根遍历序列相同

B、树的先根遍历序列与其对应的二叉树的后根遍历序列相同

C、树的后根遍历序列与其对应的二叉树的先根遍历序列相同

D、树的后根遍历序列与其对应的二叉树的后根遍历序列相同

正确答案:

第6题,题目和答案如下图所示：

A、A

B、B

C、C

D、D

正确答案:

第7题,假设主串的长度为m，模式串的长度为n，BF算法在一般和最坏情况下的时间复杂性分别为 （   ），所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。

A、n+m n*m

B、n m

C、n*m n+m

D、m n

正确答案:

第8题,在有序表中使用折半查找法的平均时间是（   ）。

A、O(1)

B、O(n)

C、O(log2n)

D、O(n2)

正确答案:

第9题,下列判断正确的是（   ）。

A、二叉树是树的特例。

B、具有n个结点的完全二叉树的深度为n/2。

C、Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。

D、栈和队列都是限制存取点的线性结构。

正确答案:

,以下说法错误的是（   ）。

A、对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。

B、对单链表来说，只有从头结点开始才能扫描表中全部结点。

C、双链表的特点是找结点的前趋和后继都很容易。

D、对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

正确答案:

第11题,已知广义表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))))

正确答案:

,设深度为K的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为（   ）。

A、K+1

B、2K

C、2K-1

D、2K+1

正确答案:

第13题,希尔排序和快速排序分别属于（   ）。

A、交换排序 选择排序

B、插入排序 选择排序

C、选择排序 归并排序

D、交换排序 选择排序

正确答案:

第14题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（   ）。

A、O(n)

B、O(e)

C、O(n+e)

D、O(n2)

正确答案:

,题目和答案如下图所示：

A、A

B、B

C、C

D、D

正确答案:

第16题,（  ）是指数据中的一个个的个体，是数据的基本单位。

A、数据相

B、数据元素

C、数据结构

D、数据类型

正确答案:

第17题,以下判断不正确的是（   ）。

A、顺序存储的线性表可随机存取。

B、同一线性表中的数据元素应具有相同的特性。

C、顺序存储方式的优点是存储密度大，插入、删除操效率高。

D、在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。

正确答案:

第18题,在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（   ）。

A、都不相同

B、完全相同

C、前序遍历和中序遍历相同，而与后序遍历不同

D、前序遍历和后序遍历相同，而与中序遍历不同

正确答案:

第19题,关于链表的特点描述不正确的是（   ）。

A、存储空间不一定连续；

B、元素之间的后继关系是由指针来体现的；

C、逻辑上相邻，物理上不一定相邻；

D、随机存取（顺序存取），即访问任何一个元素的时间相同。

正确答案:

,题目和答案如下图所示：

A、A

B、B

C、C

D、D

正确答案: