数据结构复习材料

一、单选题(共20题，40分)

1、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素

个数为()。(2.0)

A、8

B、63.5

C、63

D、7

正确答案：B

2、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间

复杂度是()。

(2.0)

A、0(1)

B、0(n)

C>0(n2)

D、0(log2n)

正确答案：B

3、根据一组关键字(56,42,50,64,48)依次插入结点生成一棵AVL树，当插入到值为0

的结点时需要进行旋转调整。(2.0)

A、42

B、50

C、64

D、48

正确答案：B

4、若查找每个元素的概率相等,则在长度为n的顺序表上查找任一元素的平均查找长度为()。

(2.0)

A、n

B、n+1

C、(n-l)/2

D、(n+1)/2

正确答案：D

5、在一个长度为n的顺序表中删除第i个元素((K=i<=n)时，需向前移动个

元素。

(2.0)

A、n-i

B、n-i+1

C、n-i-1

D、i

正确答案：A

6、稀疏矩阵一般的压缩存储方法有两种，即（）。（2.0）

A、二维数组和三维数组

B、三元组和散列

C、三元组和十字链表

D、散列和十字链表

正确答案：C

7、以下关于线性表的说法不正确的是o（2.0）

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

正确答案：C

8、在n个结点的顺序表中，算法的时间复杂度是0（1）的操作是（）。（2.0）

A、访问第i个结点（IWiWn）和求第i个结点的直接前驱（2WiWn）

B、在第i个结点后插入一个新结点（IWiWn）

C、删除第i个结点（IWiWn）

D、将n个结点从小到大排序

正确答案：A

9、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相同，则该二叉树一

定满足（）。

（2.0）

A、所有的结点均无左孩子

B、所有的结点均无右孩子

C、只有一个叶子结点

D、是任意一棵二叉树

正确答案：C

10、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。（2.0）

A、中序

B、前序

C、后序

D、层次序

正确答案：B

11、Photoshop的当前状态为全屏显示，而且未显示工具箱及任何调板，在此情况下，按什么

键，能够使其恢复为显示工具箱、调板及标题条的正常工作显示状态。（）（2.0）

A、先按F键，再按Tab键

B、先按Tab键，再按F键，但顺序绝对不可以颠倒

C、先按两次F键，再按两次Tab键

D、先按Ctrl+Shift+F键，再按Tab键

正确答案：A

12、在等概率情况下，顺序表的插入操作要移动______结点。

（2.0）

A、全部

B、一半

C、三分之一

D、四分之一

正确答案：B

13、在一个长度为n的顺序表中，在第1个元素（l&iSn+l）之前插入一个新

元素时须向后移动（）个元素。

（2.0）

A、n-i

B、n-i+1

C、n-i-1

D、I

正确答案：B

14、有一个有序表为表3,9,12,32,41,45,62,75,77,82,95,100｝当二分查找值为82

的结点时,一次比较后查找成功。（2.0）

A、1

B、2

C、4

D、8

正确答案：C

15、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正

确位置上的方法，这种排序方法称为（）。（2.0）

A、归并排序

B、冒泡排序

C、插入排序

D、选择排序

正确答案：C

16、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行

深度优先搜索，得到的顶点序列可能为()。(2.0)

A、A,B,C,F,D,E

B、A,C,F,D,E,B

C、A,B,I),C,F,E

D、A,B,D,F,E,C

正确答案：B

17、用邻接表表示图进行广度优先遍历时，通常借助()来实现算法。(2.0)

A、栈

独

B、

树

C、

图

D、

正确答案：B

18、下列关键字序列中，()是堆。(2.0)

A、16,72,31,23,94,53

B、94,23,31,72,16,53

C、16,53,23,94,31,72

D、16,23,53,31,94,72

正确答案：D

19、由3个结点可以构造出多少种不同的二叉树？()(2.0)

A、2

B、3

C、4

D、5

正确答案：D

20、算法分析的目的是()。(2.0)

A、找出数据结构的合理性

B、研究算法中输入和输出的关系

C、分析算法的效率以求改进

D、分析算法的易懂性

正确答案：C

二、多选题(共5题，10分)

1、在对n个元素进行快速排序的过程中,平均情况下的时间复杂度错误的是()。(2.0)

A、0(1)

B、0(log2n)

C、0(n2)

D、0(nlog2n)

正确答案：ABC

2、在对n个元素进行直接插入排序的过程中，算法的空间复杂度错误的是0。(2.0)

A、0(1)

0(log2n)

C、0(n2)

D、0(nlog2n)

正确答案：BCD

3、数据元素又称为。。(2.0)

素

A元

、

点

B结

、

录

c记

、

文

D英

、

案

答

jI5确

jABC

4、数组元素的下标一般具有固定的(),因此它比其他复杂的非线性结构简单。(2.0)

A、上界

B、下界

C、中界

D、尾界

正确答案：AB

5、在对n个元素进行快速排序的过程中,最坏情况下的时间复杂度错误的是()。(2.0)

A、0(1)

B、0(log2n)

C、0(n2)

D、0(nlog2n)

正确答案：ABI)

三、判断题(共10题，20分)

1、解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别

对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。(2.0)

正确答案：正确

2、队头、队尾指针加1时从maxsSize-1直接进到0,可用语言的取模（余数）运算实现。（2.0）

正确答案：正确

3、创建一个空集合必须用set（）（2.0）

正确答案：错误

4、2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）（2.0）

正确答案：正确

5、5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（）（2.0）

正确答案：错误

6、只可以使用set（）函数创建集合（2.0）

正确答案：错误

7、在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（）

（2.0）

正确答案：错误

8、N个元素进队列的顺序和出队列的操作顺序总是一致的（2.0）

正确答案：正确

9、在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（2.0）

正确答案：错误

10、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（2.0）

正确答案：错误

一、单选题（共20题，40分）

1、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。（2.0）

A、250

B、500

C、254

D、501

正确答案：D

2、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为()。(2.0)

A、n+1

B>n

C、n-l

D、n(n-l)/2

正确答案：D

3、图的BFS生成树的树高比DFS生成树的树高()o(2.0)

A、小

B、相等

C、小或相等

D、大或相等

正确答案：C

4、设哈希表K为14,哈希函数是H(key)=key%ll,表中已有数据的关键宇为15,38,G1,84

共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是()o

(2.0)

A、8

B、3

C、5

D、9

正确答案：D

5、在下列存储形式中，()不是树的存储形式？

(2.0)

A、双亲表示法

B、孩子链表表示法

C、孩子兄弟表示法

D、顺序存储表示法

正确答案：D

6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针,

则判断队空的条件为o(2.0)

A、rear%n==front

B、front+l=rear

C、rear==front

D、(rear+1)%n=front

正确答案：C

7、线性表采用链式存储时，其地址(2.0)

A、必须是连续的

B、一定是不连续的

C、部分地址必须是连续的

D、连续与否均可以

正确答案：D

8、已知一个有向图的边集为

{<a,b>,<a,c>,<a,d>,<b,d>,<b,c>,<d,e>}

则由该图产生的一种可能的拓扑序列为()o(2.0)

A、a,b,c,d,e

B、a,b,d,e,b

C、a,c,b,e,d

D、a,c,d,b,e

正确答案：A

9、

已知图的邻接矩阵如图6.30所示，则从顶点小出发按深度优先遍历的结果

是（）。

图6.30邻接矩阵

(2.0)

A、0243156

B、0136542

C、0134256

D、0361542

正确答案：C

10、若对n个元素进行归并排序，则进行归并的趟数为（）。（2.0）

A、n

B、n-1

C、n/2

D、log2n

正确答案：D

11、数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1

到10,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]

的起始地址为()。

(2.0)

A、SA+141

B、SA+144

C、SA+222

D、SA+225

正确答案：C

12、在Photoshop中历史记录(History)调板默认的记录步骤是()(2.0)

A1o步

、

B2o步

、

c3o步

、

D4O步

、

正确答案：B

13、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均

比较个元素结点。(2.0)

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

正确答案：C

14、若对n个元素进行直接插入排序，在进行第i趟排序时,假定元素r[i+l]的插入位置为r[j],

则需要移动元素的次数为()。(2.0)

A、j-i

B、i-j-1

C、i-j

D、i-j+1

正确答案：D

15、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图

一定是()图。(2.0)

A、非连通

B、连通

C、强连通

D、有向

正确答案：B

16、在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。（2.0）

A、s->next=p+l;p->next=s;

B、（*p）.next=s;（*s）.next=（*p）.next;

C、s->next=p->next:p->next=s->next;

D、s->next=p->next:p->next=s;

正确答案：D

17、顺序表中第一个元素的存储地址是100,每人元素的长度为2,则第5个元

素的地址是（）。

（2.0）

A、110

B、108

C、100

D、120

正确答案：B

18、下列关键字序列中，（）是堆。（2.0）

A、16,72,31,23,94,53

B、94,23,31,72,16,53

C、16,53,23,94,31,72

D、16,23,53,31,94,72

正确答案：D

19、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）o

（2.0）

A、存储结构

B、存储实现

C、逻辑结构

D、运算实现

正确答案：C

20、由3个结点可以构造出多少种不同的二叉树？（）（2.0）

A、2

B、3

C、4

D、5

正确答案：D

二、多选题（共5题，10分）

1、Photoshop中下面有关CloneStampTool（仿制图章工具）的使用描述正确的是（）（2.0）

A、仿制图章工具只能在本图像上取样并用于本图像中

B、仿制图章工具可以在任何一-张打开的图像—上取样，并用于任何一张图像中

C、仿制图章工具一次只能确定--个取样点

D、在使用仿制图章工具的时候，可以改变画笔的大小

正确答案：BCD

2、串中任意个连续字符组成的子序列不能称为该串的（）（2.0）

A子H

、f

主a

Bp

、

c末af

、p

D串

、

答

H一D

二BC

3、在Photoshop中下面对动作（Action）调板与历史记录（History）调板的描述哪些是不正确

的？（）（2.0）

A、历史调板记录的动作要比动作调板多

B、虽然记录的方式不同，但都可以记录对图像所做的操作

C、都可以对文件夹中的所有图像进行批处理

D、在关闭图像后所有记录仍然会保留下来

正确答案：ACD

4、若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+l]的插入位置为r[j],

则需要移动元素的次数错误的算法是0。（2.0）

A、j-i

B、i-j-1

C、i-j

D、i-j+1

正确答案：ABC

5、（）不属于信息的载体（2.0）

字

A母

、

数

B据

、

字

c数

、

文

D英

、

照

答

3E确A

CD

三、判断题（共10题，20分）

1,数据项是具有独立含义的数据的最小单位。

（2.0）

正确答案：正确

2、解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别

对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。（2.0）

正确答案：正确

3、集合中的成员一般是无序的，但在表示它时，常写在一个序列里。（2.0）

正确答案：正确

4、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负我因子的增大而增:大。

（2.0）

正确答案：正确

5、2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）（2.0）

正确答案：正确

6、对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（2.0）

正确答案：正确

7、集合（set）是一个无序不重复元素的序列。（2.0）

正确答案：正确

8、广义表实际上是基本线性表的推广。（）（2.0）

正确答案：正确

9、每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。（2.0）

正确答案：正确

10、二叉树中每个结点的度不能超过2,所以二叉树是一种特殊的树。（）

（2.0）

正确答案：错误

一、单选题（共20题，40分）

1、对于一个无向图，下面（）种说法是正确的。（2.0）

A、每个顶点的入度等于出度

B、每个顶点的度等于其入度与出度之和

C、每个顶点的入度为0

D、每个顶点的出度为0

正确答案：A

2、在一棵二叉树上第4层的结点数最多为()°(2.0)

A、2

B、4

C、6

D、8

正确答案：D

3、在AVL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平

衡因子为0,右孩子的平衡因子为1,则应作()型调整以使其平衡。(2.0)

A、LL

B、LR

C、RL

D、RR

正确答案：C

4、G是一个非连通无向图，共有28条边，则该图至少有()个顶点。(2.0)

A、7

B、8

C、9

D、10

正确答案：C

5、欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用()存

储结构。(2.0)

A、三叉链表

B、广义表

C、二叉链表

D、顺序

正确答案：A

6、在对n个元素进行快速排序的过程中，平均情况下的空间复杂度为()。(2.0)

A、0(1)

B、0(log2n)

C、0(n2)

D、0(nlog2n)

正确答案：D

7、假定对元素序列(7,3,5,9,1,12)进行堆排序，并且采用小根堆，则由初始数据构成

的初始堆为()。(2.0)

A、1,3,5,7,9,12

B、1,3,5,9,7,12

C、1,5,3,7,9,12

D、1,5,3,9,12,7

正确答案：B

8、对于长度为9的顺序存储的有序表,若采用折半查找,在等概率情况下的平均查找长度为()

的9分之一。(2.0)

A、20

B、18

C、25

D、22

正确答案：A

9、若要把n个顶点连接为一个连通图，则至少需要()条边。(2.0)

A、n

B、n+1

C、n-1

D、2n

正确答案：C

10、从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时I可复杂度大致为()

(2.0)

A、0(n)

B、0(1)

C、0(logn)

D、0(n)

正确答案：C

11、设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all为第一元素，其

存储地址为1,每个元素占一个地址空间，则a85的地址为()°(2.0)

A、13

B、32

C、33

D、40

正确答案：C

12、从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为()o

(2.0)

A、0(n)

B、0(1)

C、0(log2n)

D、0(n2)

正确答窠：C

13、在一个长度为n的顺序表中向第i个元素(0〈i(n+l)之前插入一个新元素

时，需向后移动个元素。

(2.0)

A、n-i

B、n-i+1

C、n-i-1

D、i

正确答案：B

14、若要对1000个元素排序，要求既快又稳定，则最好采用()方法。(2.0)

A、直接插入排序

B、归并排序

C、堆排序

D、快速排序

正确答案：B

15、顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素

的地址是()。

(2.0)

A、110

B、108

C、100

D、120

正确答案：B

16、在Photosh叩中将前景色和背景色恢复为默认颜色的快捷键是：()(2.0)

A、D

B、X

C、Tab

D、Alt

正确答案：A

17、在。中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链

表类。这种方式灵活。(2.0)

A、复合万式

B、嵌套方式

C、继承方式

D、以上都不是

正确答案：A

18、从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为()。(2.0)

A、0(n)

B、0(1)

C、O(logn)

D、0(n)

正确答案：A

19、广义表A=(a),则表尾为()。(2.0)

A、a

B、(())

C\空表

D、(a)

正确答案：C

20、一个存储结点存储一个()。(2.0)

A、数据项

B、数据元素

C、数据结构

D、数据类型

正确答案：B

二、多选题(共5题，10分)

1、只允许在一端插入和删除的线性表允许插入和删除的一端不能称为()(2.0)

A栈顶

B栈底

c栈中

D栈末

答案

2确

：BCD

2、在Photoshop中下面有关模糊工具(BlurTool)和锐化工具(SharpenTool)的使用描述正确的

是()。(2.0)

A、它们都是用于对图像细节的修饰

B、按住Shift键就可以在这两个工具之间切换

C、模糊工具可降低相邻像素的对比度

D、锐化工具可增强相邻像素的对比度

正确答案：ACD

3、当我们在Photoshop中建立新图像时，可以为图像设定，（）（2.0）

A、图像的名称

B、图像的大小

C、图像的色彩模式

D、图像的存储格式

正确答案：ABC

4、有3个数据{1,2,3},可得5种不同的二，叉树。它们的前序排列均为123,中序序列可能

是（）（2.0）

A、321

B、231

C、213

D、132

正确答案：ABCD

5、数据结构不是。的组织形式（2.0）

字

A母

B据

数

c-字

文

D英

案

专

n确

ACD

三、判断题（共10题，20分）

1、广义表的组成元素可以是不同形式的元素。（）（2.0）

正确答案：正确

2、数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。

（）（2.0）

正确答案：错误

3、7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）（2.0）

正确答案：正确

4、通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中

的位置。（2.0）

正确答案：正确

5、广义表的表尾一定是一个广义表。（）（2.0）

正确答案：正确

6、字典当中的元素是通过键来存取的，也可以通过偏移存取（2.0）

正确答案：错误

7、栈和队列都是限制存取端的线性表。（2.0）

正确答案：正确

8、对称性:若x=y，则y=x。（2.0）

正确答案：正确

9、Hash表的平均查找长度与处理冲突的方法无关（2.0）

正确答案：错误

10、数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标.（index）

和值（value）组成。（2.0）

正确答案：正确

一、单选题（共20题，40分）

1、在对n个元素进行冒泡排序的过程中，至少需要（）超完成。（2.0）

A、1

B、n

C^n-1

D、n/2.

正确答案：A

2、设广义表L=（（a,b,c））,则L的长度和深度分别为（）。（2.0）

A、1和1

B、1和3

C、1和2

D、2和3

正确答案：C

3、下面()算法适合构造一个稠密图G的最小生成树。(2.0)

A、Prim算法

B、Kruskal算法

C、Floyd算法

D、Dijkstra算法

正确答案：A

4、假定对元素序列(7,3,5,9,1,12,8,15)进行快速排序，则进行第一次划分后，得到

的左区间中元素的个数为()。(2.0)

A、2

B、3

C、4

D、5

正确答案：B

5、若一个元素序列基本有序，则选用()方法较快。(2.0)

A、直接插入排序

B、简单选择排序

C、堆排序

D、快速排序

正确答案：A

6、在下列存储形式中，()不是树的存储形式？

(2.0)

A、双亲表示法

B、孩子链表表示法

C、孩子兄弟表示法

D、顺序存储表示法

正确答案：D

7、下列哪个是Photoshop图象最基本的组成单元：()(2.0)

A、节点

B、色彩空间

C、像素

D、路径

正确答案：C

8、广义表A=((x,(a,B)),(x,(a,B),y)),则运算head(head(tail(A)))的结果为()。(2.0)

A、x

B、(a,B)

C、（x,（a,B））

D、A

正确答案：A

9、在______运算中，使用顺序表比链表好。（2.0）

A、插入

B、删除

C、根据序号查找

D、根据元素值查找

正确答案：C

10、最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（）。（2.0）

A、（rear+1）%n—front

B、rear==front

C、rear+l==front

D、（rear-1）%n==front

正确答案：B

11、下面的说法中，只有（）是正确的。（2.0）

A、字符串的长度是指串中包含的字母的个数

B、字符串的长度是指串中包含的不同字符的个数

C、若T包含在S中，则T一定是S的一个子串

D、一个字符串不能说是其自身的一个子串

正确答案：C

12、若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,…，pn,若pl=n,

则pi为（）。（2.0）

A、i

B、n-i

C、n-i+l

D、不确定

正确答案：C

13、若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的

时间复杂度为（）。（2.0）

A、0（1）

B、0（n）

C、0（n2）

D、0（log2n）

正确答案：B

14、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。（2.0）

A、1/2

B、1

C、2

D、4

正确答案：B

15、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线

上所有元素)依次存放于一维数组B[(n(n+l))/2]中，则在B中确定aij(i<j)

的位置k的关系为()C

(2.0)

A、i*(i-l)/2+j

B、j*(j-l)/2+i

C、i*(i+l)/2+j

D、j*(j+l)/2+i

正确答案：D

16、.一棵深度为k的AVL树其每个分支结点的平衡因子均为0,则该平衡二叉树共有()个结点。

(2.0)

A、43862

B、2+1

C、2-1

D、2

正确答案：C

17、一个存储结点存储一个()。(2.0)

A、数据项

B、数据元素

C、数据结构

D、数据类型

正确答案：B

18、若下三角矩阵AnXn,按列顺序压缩存储在数组Sa[(n+l)n/2]中，则非零元

素aij的地址为((设每个元素占d个字节)

(2.0)

A、[j*(n-l)-j*(j-l}/2+i-j>d

B、[(j-1)*n-j*(j-l)/2+i]*d

C、[j*n-j*(j-l)/2+i-l]*d

D、[j*n-j*(j-l)/2+i-j]*d

正确答案：D

19、在Photoshop中将前景色和背景色恢复为默认颜色的快捷键是：()(2.0)

A、D

B、X

C、Tab

D、Alt

正确答案：A

20、广义表A=（a）,则表尾为（）。（2.0）

A、a

B、（（））

C、空表

D、（a）

正确答案：C

二、多选题（共5题，10分）

1、在对n个元素进行直接插入排序的过程中，算法的空间复杂度错误的是（）。（2.0）

A、0（1）

B、0（log2n）

C、0（n2）

D、0（nlog2n）

正确答案：BCD

2、深度优先遍历有（）（2.0）

A、先根次序遍历

氏后根次序遍历

C、广度优先遍历

D、以上都是

正确答案：AB

3、递归过程。（2.0）

A、简洁

B、易编

C、易懂

D、过程效率低

正确答案：ABCD

4、（）不属于信息的载体（2.0）

字

A母

、

数

B据

、

数

C字

、

D、英文

正确答案：ACD

5、在对n个元素进行快速排序的过程中,最坏情况下的时间复杂度错误的是（）。（2.0）

A、0（1）

B、0（log2n）

C、0（n2）

D、0（nlog2n）

正确答案：ABD

三、判断题（共10题，20分）

1、空栈没有栈顶指针。（2.0）

正确答案：错误

2、有n个数存放在一维数组A[..n]中，在进行顺序查找时，这n个数的排列有序或无序其平

均查找长度不同。（2.0）

正确答案：错误

3、集合（set）是一个无序不重复元素的序列。（2.0）

正确答案：正确

4、每种数据结构的逻辑结构与物理结构总是一致的。（2.0）

正确答案：错误

5、顺序栈中元素值的大小是有序的。（2.0）

正确答案：错误

6、多维数组可以看作数据元素也是基本线性表的基本线性表。（）（2.0）

正确答案：正确

7、数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程

序识别和处理的符号的集合。（2.0）

正确答案：正确

8、每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。（2.0）

正确答案：正确

9、整数、字符和串都有一个自然线性顺序。（2.0）

正确答案：正确

10、数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标.（index）

和值（value）组成。（2.0）

正确答案：正确

一、单选题（共20题，40分）

1、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。（2.0）

A、24

B、48

C、72

D、53

正确答案：D

2、在对n个元素进行快速排序的过程中，最好情况下需要进行（）躺。（2.0）

A、n

B、n/2

C、log2n

D、2n

正确答案：C

3、根据一组关键字（56,42,50,64,48）依次插入结点生成一棵AVL树，当插入到值为0

的结点时需要进行旋转调整。（2.0）

A、42

B、50

C、64

D、48

正确答案：B

4、在对n个元素进行直接插入排序的过程中，共需要进行（）趟。（2.0）

A、n

B、n+1

C、n-1

D、2n

正确答案：C

5、对于一个有向图，若一个顶点的度为kL出度为k2,则对应邻接表中该顶点单链表中的边

结点数为（）。（2.0）

A、kl

B、k2

C、kl-k2

D、kl+k2

正确答案：B

6、对于顺序存储的有序表（5,12,20,26,37,42,46,5。,64）,若采用折半查找，则查找元素26的

比较次数为（）<>（2.0）

A、2

B、3

C、4

D、5

正确答案：C

7、在平均情况下速度最快的排序方法为（）.（2.0）

A、简单选择排序

B、归并排序

C、堆排序

D、快速排序

正确答案：D

8、下面（）方法可以判断出一个有向图是否有环。（2.0）

A、深度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

正确答案：B

9、若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pLp2,p3,…，pn,若pl=n,

则pi为（）。（2.0）

A、i

B、n-i

C、n-i+l

D、不确定

正确答案：C

10、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（2.0）

A、n

R、n/2

C、(n+l)/2

D、(n-l)/2

正确答案：C

11、在Photoshop中使用变换(Transform)命令中的缩放(Scale)命令时，按住哪个键可以保

证等比例缩放()(2.0)

A、A1

B、Ctrl

C、Shift

D、Ctrl+Shift

正确答案：C

12、若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+l]的插入位置为r[j],

则需要移动元素的次数为()o(2.0)

A、j-i

B、i-j-1

C、i-j

D、i-j+1

正确答案：D

13、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为()o(2.0)

A、n

B、e

C、n+e

D、2e

正确答案：D

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

(2.0)

A、

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

B、

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

C、

删除第i个结点(l(i(n)

D、

将n个结点从小到大排序

正确答案：A

15、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。