第1章+公共基础知识.docx

第1章 公共基础知识

(1)算法的时间复杂度是指（ ）。

A．执行算法程序所需要的时间

B．算法程序的长度

C．算法执行过程中所需要的基本运算次数

D．算法程序中的指令条数

(2)下列叙述中正确的是（ ）。

A．线性链表是线性表的链式存储结构

B．栈与队列是非线性结构

C．双向链表是非线性结构

D．只有根结点的二叉树是线性结构

(3)有下列二叉树，对此二叉树进行前序遍历的结果为（ ）。

A．ACBEDGFH

B．ABDGCEHF

C．HGFEDCBA

D．ABCDEFGH

(4)某二叉树共有60个叶子结点与50个度为1的结点，则该二叉树中的总结点数为（ ）。

A．148

B．169

C．182

D．198

(5)下列叙述中正确的是（ ）。

A．一个逻辑数据结构只能有一种存储结构

B．逻辑结构属于线性结构，存储结构属于非线性结构

C．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

(6)有下列二叉树，对此二叉树进行中序遍历的结果为（ ）。

A．BDYEACFXZ

B．DYBEAFCZX

C．ABCDEFXYZ

D．ABDYECFXZ

(7)已知一个有序线性表为(13，18，24，35，47，50，62，83，90，115，134)，当用二分法查找其中值为90的元素时，查找成功的比较次数为（ ）。

A．1

B．2

C．3

D．9

(8)下列叙述中错误的是（ ）。

A．线性表是由11个元素组成的一个有限序列

B．线性表是一种线性结构

C．线性表的所有结点有且仅有一个前件和后件

D．线性表可以是空表

(9)栈S最多能容纳4个元素，现有6个元素按A、B、C、D、E、F的顺序进栈，则（ ）不是可能的出栈序列。

A．C、B、E、D、A、F

B．C、D、B、F、E、A

C．A、D、E、C、B、F

D．A、F、E、D、C、B

(10)两个或两个以上模块之间联系的紧密程度称为（ ）。

A．耦合性

B．内聚性

C．复杂性

D．数据传输特性

(11)在下列关于二叉树的叙述中，正确的一项是（ ）。

A．在二叉树中，任何一个结点的度都是2

B．二叉树的度为2

C．在二叉树中，至少有一个结点的度为2

D．一棵二叉树的度可以小于2

(12)待排序的关键码序列为(33，18，9，25，67，82，53，95，12，70)，如要按关键码值递增的顺序排序，并采取以第一个关键码为基准元素的快速排序法，则第一趟排序后关键码33被放到第（ ）个位置。

A．3

B．5

C．7

D．9

(13)设根结点的层次为0，高度为K的二叉树的最大结点数为（ ）个。

KA．2

K+lB．2-1

KC．2+1

K+lD．2+1

(14)算法的有穷性是指（ ）。

A．算法程序的长度是有限的

B．算法程序所处理的数据量是有限的

C．算法程序的运行时间是有限的

D．算法只能被有限的用户使用

(15)以下描述中，不是线性表顺序存储结构特征的是（ ）。

A．不便于插入和删除

B．需要连续的存储空间

C．可随机访问

D．需另外开辟空间来保存元素之间的关系

(16)按照“先进后出”原则组织数据的数据结构是（ ）。

A．队列

B．栈

C．双向链表

D．二叉树

(17)已知一棵二叉树的先根序列为ABCDEFK，中根序列为DGBAFCK，则结点的后根序列为（ ）。

A．ACFKDBG

B．GDBFKCA

C．KCFAGDB

D．ABCDFKG

(18)深度为6的满二叉树中，度为2的结点个数为（ ）。

A．31

B．32

C．63

D．64

(19)下列数据结构中，能用二分法进行查找的是（ ）。

A．顺序存储的有序线性表

B．线性链表

C．二叉链表

D．有序线性表

(20)以下关于顺序存储结构的叙述中，（ ）是正确的。

A．每个结点中至少包含一个指针域

B．逻辑上相邻的结点物理上不必邻接

C．可用于栈、队列、树等逻辑结构的存储表示

D．插入、删除运算操作不方便

(21)有3个结点的二叉树有（ ）。

A．2种形态

B．4种形态

C．7种形态

D．5种形态

(22)在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中，所有叶结点的先后顺序（ ）。

A．都不相同

B．完全相同

C．前序和中序相同，而与后序不同

D．中序和后序相同，而与前序不同

(23)下列叙述中正确的是（ ）。

A．线性链表的各元素在存储空间中的位置必须是连续的

B．线性链表的头元素一定存储在其他元素的前面

C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他

元素的前面

D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

(24)线性表常采用的两种存储结构是（ ）。

A．顺序存储结构和链式存储结构

B．散列方法和索引方式

C．链表存储结构和数组

D．线性存储结构和非线性存储结构

(25)设栈S和队列Q的初始状态为空，元素a、b、c、d、e和f依次通过栈S，一个元素出栈后即进入队列O，若6个元素出队的顺序是b、d、c、f、e、a，则栈s的容量至少应该是（ ）。

A．6

B．4

C．3

D．2

(26)对于长度为n的线性表，在最坏情况下，下列各种排序法所对应的比较次数中正确的是（ ）。

A．冒泡排序为n／2

B．冒泡排序为n

C．快速排序为n

D．快速排序为n(n一1)／2

(27)实现算法所需要的存储单元的多少称为（ ）。

A．可实现性

B．空间复杂度

C．时间复杂度

D．困难度

(28)以下关于栈的描述中，错误的是（ ）。

A．栈是先进后出的线性表

B．栈只能顺序存储

C．栈具有记忆作用

D．对栈的插入与删除操作中，不需要改变栈底指针

(29)下面数据结构中，属于非线性的是（ ）。

A．线性表

B．队列

C．树

D．栈

(30)下列数据结构中，能用二分法进行查找的是（ ）。

A．顺序存储的有序线性表

B．线性链表

C．二叉链表

D．有序线性链表

(31)树是结点的集合，它的根结点的数目是（ ）。

A．有且只有1个

B．1个或多于1个

C．0个或1个

D．至少有2个

(32)在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。

A．0(n)

B．O(n2)

C．O(1092n)

D．O(nl092n)

(33)若已知一个栈的入栈序列是l，2，3，?，n，其输出序列是pl，p2，p3，?，pn，则pi为（ ）。

A．i

B．n—i

C．n—i+l

D．不确定

(34)以下数据结构中，不属于线性数据结构的是（ ）。

A．队列

B．线性表

C．二叉树

D．栈

(35)在一棵二叉树上，第4层最多有（ ）个结点。

A．8

B．16

C．32

D．15

(36)下列关于栈的叙述中，正确的选项是（ ）。

A．在栈中只能删除数据

B．在栈中只能插人数据

C．栈是先进先出的线性表

D．栈是先进后出的线性表

(37)设有下列二叉树，对此二叉树进行前序遍历的结果为（ ）。

A．DEBFCA

B．DBEAFC

C．ABDECF

D．ABCDEF

(38)下列（ ）数据模型可以用树形结构来表示实体之间的联系。

A．网状模型

B．数据模型

C．关系模型

D．层次模型

(39)1、2、3、4四个元素按顺序进栈，不可能的出栈顺序为（ ）。

A．1 2 3 4

B．2 3 4 1

C．1 4 3 2

D．3 1 4 2

(40)下列对于线性链表的描述中，正确的是（ ）。