数据结构自测题

1数据结构网上自测习题

1.1（一）章

数据结构中，与所使用的计算机无关的是数据的解析：逻辑结构指数据元素之间的关系，与计算机无关。

存储结构

物理结构

逻辑结构

物理和存储结构

我的答案：

下列说法不正确的是：

数据元素是数据的基本单位

数据项是数据中不可分割的最小标识单位

数据可由若干个数据元素构成

数据项可由若干个数据元素构成

我的答案：

答案解析：数据元素可由若干个数据项构成。

判断题（共题，每题分）

数据结构按逻辑结构可分为两大类，它们分别是：顺序结构和链式结构。

对错

我的答案：

算法的便于阅读和理解的特性称为

茁壮性高效率

易读性正确性

1

我的答案：

2算法的计算量大小称为计算的

现实性难度

复杂性效率

我的答案：

1.2(二)章

1已知线性表1,经运算2之后，等于

121,2

21

2线性表1,a2下列i说法正确的是n

每一个元素都有一个直接前驱和直接后继

线性表中至少要有一个元素

表中各元素的罗列顺序必须由小到大或者由大到小

除第一个元素和最后一个元素外，其余元素都有且仅有一个直接前驱和直接后继

在n个结点的顺序表中，算法的时间复杂度是(1)的操作是

访问第i个结点(1WiWn)和求第i个结点的直接前驱(2WiWn)

在第i个结点后插入一个新结点(1WiWn)

删除第i个结点(1Wi近n)

将n个结点从小到大排序

对于顺序表的优缺点，以下说法错误的是

无需为表示结点间的逻辑关系而增加额外的存储空间

2

B.可以方便地随机存取表中的任一结点

插•入和删除运算较方便.

D.由于顺序表要求占用连续的空间，存储分配只能预先进行静态分配

指.针P和分别指向单链表的两个元素，P所指元素是所指元素的前驱的判断条件是:

.pnext==

B.next==p

.P二二

D.pnext==next

.线性表采用链式存储时，其地址：D

必.须是连续的

B.部份地址必须是连续的

一•定是不连续的

D.连续与否均可以

在.单向循环链表中，若头指针为head,那末p所指结点为尾结点的条件是：D

.p==NULL

B.p->next二二NULL

.p二二head

D.pTnext二二head

设.指针P指向双链表的某一结点，则双链表结构的对称性可表示为

•PPnext-pnextnext

B.pPnext=pnextnext

•PPnext==pnextP

D.pnextnext==ppP

3

1.3（三）章

栈操作数据的原则是：

先进先出后进先出

后进后出不分顺序

设数组元素...............挨次通过栈结构，则不可能排成的序列为：

若用链接方式实现栈，则出栈时：

必须判别栈是否满必须判别栈是否空必须判别栈是否空对栈不作任何判别

设计一个判别表达式中左、右括号是否正确配对浮现的算法，采用哪种数据结构最佳？

线性表栈队列二叉树

任何递归算法都能通过使用那种数据结构转化为非递归算法？

线性表栈队列二叉树

若一个初始为空的队列的进队序列是，，，，则出队序列是（）：

循环队列存储在数组中，则入队时队尾指示变量的变化方法为（）：

1.4（四）章

4

下述陈述错误的是。（）

空白串是任意串的子串空白串是任意串的子串

串常量不同于串变量串常量不同于串变量

串的长度是指。（）

串中所含不同字母的个数串中所含字符的个数

串中所含不同字符的个数串中所含非空格字符的个数

判断题（共题，每题分）

两个长度不相同的串有可能相等。（）

对错

两个长度不相同的串有可能相等。（）

有效位移是惟独是有效位移

惟独，是有效位移惟独，，是有效位移

下面关于串的叙述中，哪一个是不正确的。（）

串是字符的有限序列空串是由空格构成的串

模式匹配是串的一种重要运算串既可以采用顺序存储，也可以采用链式存储

1.5（五）章

有一个行列的二维数组，用顺序查找法在该数组中查找值为的元素的时间复杂度是（）

1.6（六）章

5

一棵个叶子结点的彻底二叉树最多有个结点。（）

下述陈述正确的是。（）

下述陈述正确的是。（）彻底二叉树一定是满二叉树严格的二叉树一定是彻底二叉树

多选题（共题，每题分）

具有个结点的树共有（）种不同的形态，具有个结点的二叉树共有（）种不同的形态

设根的层数为，若深度为的彻底二叉树具有至少的结点，则编号最小和编号最大的叶子结点编号分别是

。个结点的彻底二叉树高度为取下整。

对错

我的答案：

已知某二叉树的前序序列为，中序序列为，则其后序序列为（）

个结点的线索二叉树中线索数目为（）

一棵左子树为空的二叉树在前序线索化后，其中空的链域个数为（）

不确定

在以下四种树的存储结构中，容易实现查找指定结点的祖先和后代的是（）

双亲链表表示法孩子链表表示法

双亲孩子链表表示法双亲孩子链表表示法

6

下述编码中哪一个不是前缀码。（）

1.7（七）章

在下面有关有向图的顶点的度的叙述中，正确的是（）

个顶点的强连通图中所有顶点的度之和的最小值为

顶点的出度等于其它顶点指向该顶点的有向边的数目

顶点的出度等于其它顶点指向该顶点的有向边的数目

每一个顶点的入度等于出度

有个顶点的图，若用邻接矩阵表示，则该矩阵中元素的个数为（）

图的深度优先搜索是树的（）遍历的推广

先序中序后序层序

我的答案：

用邻接表表示图进行广度优先搜索时，通常采用（）来实现算法

线性表栈队列树

我的答案：

有个顶点的连通图的生成树有（）条无向边

我的答案：

有向无环图简称（）

7

我的答案:

求一个顶点到其他各顶点的最短路径可以使用（）算法

弗洛伊德克鲁斯卡尔迪杰斯特拉普里姆

我的答案：

弗洛伊德算法的时间复杂度是（）

我的答案：

1.8（八）章

折半插入排序的时间复杂度为（）

我的答案：

在对一组记录｛.............................,｝进行直接插入排序时，当把第个记录插入到

有序表时，为寻觅插入位置需比较（）次。

我的答案：

当初始序列有序时，冒泡排序的时间复杂度为（）。

我的答案：

每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，

右区间中元素的关键字均大于基准元素的关键字，则此排序方法叫做（）。

直接插入排序希尔排序

8

冒泡排序快速排序

我的答案：

快速排序在（）情况下最不利于发挥其长处。

被排序的数据量很大

被排序的数据已基本有序

被排序的数据彻底无序

被排序的数据中最大值与最小值相差不大

我的答案：

在堆排序过程中，由个待排序的记录建成初始堆需要（）次筛选。

我的答案：

一组记录的关键字为（，，，，，，，，，），其中含有个长度为的有序表，用

归并排序方法对该序列进行一趟归并后的结果为（）。

我的答案：

在归并排序中，若待排序记录的个数为，则共需要进行（）趟归并。

我的答案：

在所有的内部排序方法中，关键字的比较次数与记录的初始罗列无关的是（）

希尔排序希尔排序

直接插入排序简单选择排序

我的答案：

9

在内部排序中，要求附加的内存容量最大的是（）

快速排序选择排序

归并排序