数据结构与算法

1) 以下数据结构中不属于线性数据结构的是___

a. 队列。

b. 线性表。

c. 二叉树。

d. 栈。答案]c

一棵二叉树的一个结点下面可以有2个子结点，故不是线性结构a是先进先出的线性表；b是宏观概念，包括顺序表、链表、堆栈、队列…；d是先进后出的线性表

2) 在一棵二叉树上第5层的结点数最多是___

a. 8b. 16

c. 32d. 15

答案]b评析]依次从上到下，可得出：

第1层结点数为1；

第2层结点数为2*1=2；

第3层结点数为2*2=4；

第n层结点数为2的n-1次幂，如图所示。

3) 算法的时间复杂度是指___

a. 执行算法程序所需要的时间。

b. 算法程序的长度。

c. 算法执行过程中所需要的基本运算次数。

d. 算法程序中的指令条数。

答案]c(4) 下列叙述中正确的是___

a. 线性表是线性结构。

b. 栈与队列是非线性结构。

c. 线性链表是非线性结构。

d. 二叉树是线性结构

答案]a一棵二叉树的一个结点下面可以有2个子结点，故不是线性结构。

(5) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为___

a. 349

b. 350

c. 255

d. 351

答案]b完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。

完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为b！

如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。

6) 下列关于栈的叙述中正确的是___

a. 在栈中只能插入数据。

b. 在栈中只能删除数据。

c. 栈是先进先出的线性表。

d. 栈是先进后出的线性表。

答案]d注意：队列是先进先出的线性表。

7) 在深度为5的满二叉树中，叶子结点的个数为___

a. 32b. 31

c. 16d. 15

答案]c首先搞清楚满二叉树与完全二叉树之间的区别，前面已解释过。

依次从上到下，可得出：

第1层结点数为1；

第2层结点数为2*1=2；

第3层结点数为2*2=4；

第n层结点数为2的n-1次幂

8) 算法一般都可以用哪几种控制结构组合而成___

a. 循环、分支、递归。

b. 顺序、循环、嵌套。

c. 循环、递归、选择。

d. 顺序、选择、循环。

答案]d结构化程序设计中，基本的控制结构为顺序、选择、循环。

(9) 数据的存储结构是指___

a. 数据所占的存储空间量。

b. 数据的逻辑结构在计算机中的表示。

c. 数据在计算机中的顺序存储方式。

d. 存储在外存中的数据。

答案]b10) 设有下列二叉树：

对此二叉树中序遍历的结果为___

a. abcdef

b. dbeafc

c. abdecf

d. debfca

答案]b11) 希尔排序法属于哪一种类型的排序法___

a. 交换类排序法。

b. 插入类排序法。

c. 选择类排序法。

d. 建堆排序法。

答案]b12) 下列关于队列的叙述中正确的是___

a. 在队列中只能插入数据。

b. 在队列中只能删除数据。

c. 队列是先进先出的线性表。

d. 队列是先进后出的线性表。

答案]c13) 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为___

a. n+1

b. nc. (n+1)/2

d. n/2

答案]b二分法最坏情况为》log2 n的最小整数值。

比如n为4，最坏的情况要比较3次；

14) 在计算机中，算法是指___

a. 查询方法。

b. 加工方法。

c. 解题方****而完整的描述。

d. 排序方法。

答案]c15) 栈和队列的共同点是___

a. 都是先进后出。

b. 都是先进先出。

c. 只允许在端点处插入和删除元素。

d. 没有共同点。

答案]c16) 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是___

a. cedba

b. acbed

c. decab

d. deabc

答案]a(17) 在下列几种排序方法中，要求内存量最大的是___

a. 插入排序。

b. 选择排序。

c. 快速排序。

d. 归并排序。

[答案]d我们对比一个排序方法的优越性有"平均时间"、"最坏情况时间"和"辅助空间"。其中辅助空间一般是排序中需要额外的内存开销，这些内存开销一般据一些如中间变量（暂存变量）、比较与交换等等来决定。

插入排序和选择排序的辅助空间都是o(1),快速排序是o(nlog2n),归并排序是o(n)。

可知归并排序要求内存量最大，我们也可以从其变量及循环个数也以看出归并排序要求内存量最大。

18) 数据结构中，与所使用的计算机无关的是数据的___

a. 存储结构。

b. 物理结构。

c. 逻辑结构。

d. 物理和存储结构。

答案]c19) 栈底至栈顶依次存放元素a、b、c、d，在第五个元素e入栈前，栈中元素可以出栈，则出栈序列可能是___

a. abced

b. dbcea

c. cdabe

d. dcbea

答案]d栈是先进后出的，因为在e放入前，a、b、c、d已经依次放进栈里了，故这四个元素出栈的顺序只能是d、c、b、a，e可是其中排序的任何位置，答案只有d符合了。

20) 线性表的顺序存储结构和线性表的链式存储结构分别是___

a. 顺序存取的存储结构、顺序存取的存储结构。

b. 随机存取的存储结构、顺序存取的存储结构。

c. 随机存取的存储结构、随机存取的存储结构。

d. 任意存取的存储结构、任意存取的存储结构。

答案]b顺序存储结构如数组，它在内存中的一片连续的储存空间，从第一个元素到最后一个元素，只要根据下标就可以访问。

链式存储结构以链表为例，各个链结点无须存放在一片连续的内存空间，而只需要指针变量指过来指过去，实现随机存取。

21) 在单链表中，增加头结点的目的是__。

a. 方便运算的实现。

b. 使单链表至少有一个结点。

c. 标识表结点中首结点的位置。

d. 说明单链表是线性表的链式存储实现。

答案]a22) 数据处理的最小单位是___

a. 数据。

b. 数据元素。

c. 数据项。

d. 数据结构。

答案]c。23) 算法分析的目的是___

a. 找出数据结构的合理性。

b. 找出算法中输入和输出之间的关系。

c. 分析算法的易懂性和可靠性。

d. 分析算法的效率以求改进。

答案]d24) n个顶点的强连通图的边数至少有___

a. n-1

b. n(n-1)

c. nd. n+1

答案]c25) 已知数据表a中每个元素距其最终位置不远，为节省时间，应采用的算法是___

a. 堆排序。

b. 直接插入排序。

c. 快速排序。

d. 直接选择排序。

答案]b堆排序是边建堆边排序的过程，而建堆排序时的效率元素距其最终位置的远近关系不大。

插入排序是把每个元素挨个比较之前的元素，插入到合适的位置，这种排序的比较次数很不固定，它决定于每个元素距其最终位置。

快速排序的每一趟可确定一个元素的最终位置，但以某个元素为标准的比较次数还是得比较剩下所有的，它的最大的特点是序列初始无序的情况下排序最快。（初始有序并不是每个元素距其最终位置不远，而是有一些最终相邻的元素初始已经相邻了或大致左右的顺序已经好了）。

直接选择排序，就是每一趟选择序列剩下的元素的一个最大值（或最小值）挨个排在首端（或尾端），是人脑最常使用的方法，所以被人脑最易理解。在电脑上，这种排序效率不受其初始位置的影响。

26) 用链表表示线性表的优点是___

a. 便于插入和删除操作。

b. 数据元素的物理顺序与逻辑顺序相同。

c. 花费的存储空间较顺序存储少。

d. 便于随机存取。

答案]a27)根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成(c)

a.动态结构和静态结构 b.紧凑结构和非紧凑结构。

c.线性结构和非线性结构d.内部结构和外部结构

28)下列叙述中，错误的是(b)

a.数据的存储结构与数据处理的效率密切相关

b.数据的存储结构与数据处理的效率无关

c.数据的存储结构在计算机中所占的空间不一定是连续的

d.一种数据的逻辑结构可以有多种存储结构。

29)线性表l=(a1,a2,a3,…ai，…an)，下列说法正确的是(d)

a.每个元素都有一个直接前件和直接后件

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

c.表中诸元素的排列顺序必须是由小到大或由大到。

d.除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件。

30)线性表若采用链式存储结构时，要求内存中可用存储单元的地址(d)

a.必须是连续的 b.部分地址必须是连续的。

c.一定是不连续的 d.连续不连续都可以。

31)栈通常采用的两种存储结构是(a)

a.顺序存储结构和链式存储结构 b.散列方式和索引方式。

c.链表存储结构和数组 d.线性存储结构和非线性存储结构。

32)下列数据结构中，按先进后出原则组织数据的是(b)

a.线性链表 b.栈 c.循环链表 d.顺序表。

33)树是结点的集合，它的根结点数目是(c)

a.有且只有1 b.1或多于1 c.0或1 d.至少2

34)具有3个结点的二叉树有(d)

a.2种形态 b.4种形态 c.7种形态 d. 5种形态

35)设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为(b)

a. 12 b. 13 c.14 d. 15

填空题。1) 算法的复杂度主要包括___复杂度和空间复杂度。

答：时间。2) 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、__遍历和后序遍历。

答：中序。3) 设一棵完全二叉树共有500个结点，则在该二叉树中有___个叶子结点。

答：2504) 在最坏情况下，冒泡排序的时间复杂度___

答：n(n-1)/2或n*(n-1)/2或o(n(n-1)/2)或o(n*(n-1)/2)

5) 数据结构包括数据的___结构和数据的存储结构。

答：逻辑。

数据结构与算法

数据结构与算法

算法与数据结构

算法与数据结构

其他用户还读了