数据结构试题及答案解析卷B

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构试题及答案解析卷B数据结构试题及答案解析卷B

时光：120分钟满分：100分

一、挑选题(每小题1分，共20分)

1．以下数据结构中，是线性结构。

A）栈B）树C）二叉树D）图

2．在全部排序办法中，关键字比较的次数与记录的初始罗列次序无关的是。

A、挑选排序

B、冒泡排序

C、插入排序

D、希尔排序

3．下面是挨次存储结构的优点。

A）存储密度大B）插入运算便利C）查找便利D）适合各种规律结构的存储表示4．用链式方式存储的队列，在举行插入运算时，。

A）仅修改头指针B）仅修改尾指针

C）头、尾指针都要修改D）头、尾指针可能都要修改

5．从未排序序列中依次取出一个元素与已排序序列中的元素依次举行比较，然后将其放在已排序序列的合适位置，该排序办法称为排序法。

A）插入B）挑选C）冒泡D）都不是

6．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是。

先序序列：EFHIGJK中序序列：HFIEJKG

A）EB）FC）GD）H

7．下面办法可以推断出一个有向图中是否有环。

A）深度优先遍历B）拓朴排序C）求最短路径D）求关键路径

8．下面关于串的讲述中，是不正确的。

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

C）模式匹配是串的一种重要运算D）串既可以采纳挨次存储，也可以采纳链式存储9．的邻接矩阵是对称矩阵。

A）有向图B）无向图C）AOV网D）AOE网

10．若在线性表中采纳折半查找法查找元素，该线性表应当。

A）元素按值有序B）采纳挨次存储结构

C）元素按值有序，且采纳挨次存储结构D）元素按值有序，且采纳链式存储结构11．在一个长度为n的挨次存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移个元素。

A、n-i

B、n-i-1

C、n-i+1

D、i

12．一个栈的入栈序列是12345，则栈的不行能的输出序列是。

A、23415

B、54132

C、23145

D、15432

13．从邻接矩阵????

???=010101010A可以看出，该图共有顶点。

A、9

B、3

C、6

D、1

14．上题中，若是无向图，则有条边。

A、5

B、4

C、3

D、2

15．n个节点的彻低二叉树，编号为i的节点是叶子结点的条件是。

A、in

D、2*i>n

16．向一个有128个元素的挨次表中插入一个新元素并保持本来挨次不变，平均要移动个元素。

A、64.5

B、64

C、63

D、65

17．5个顶点的有向图最多有条弧。

A、5

B、20

C、30

D、25

18．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。

A、q->next=p->next;p->next=q;

B、p->next=q->next;q=p;

C、p->next=p->next;q->next=q;

D、p->next=q->next;q->nxet=p;

19．对一个满二叉树，m个树叶，n个结点，深度为h，则有。

A、n=h+m

B、h+m=2n

C、m=h-1

D、n=2h-1

20．假定一个链队的队首和队尾指针分离为front和rear，则推断队空的条件为。

A、front==rear

B、front!=NULL

C、rear!=NULL

D、front==NULL

二、推断题：（推断下列各题正误，正确的在题目后面的括号内写“对”，错误的在题目后面的括号内写“错”。每小题2分，共10分）

（）1.含尾指针的单链循环表可以被用于队列操作。

（）2.栈和队列都不是线性数据结构。

（对）3.数据项是数据的最小单位。（而数据元素是基本单位）

（）4.数据结构包含数据的规律结构、数据的存储结构以及数据集合上定义的运算。（）5.彻低二叉树不行以用挨次存储结构举行存储。

三、填空题（每空2分，共10分）

1、对于一个长度为n的挨次存储的线性表，在表头插入元素的时光复杂度为O（N），在表尾插入元素的时光复杂度为O（1）。

2、队列的插入操作在队尾举行，栈的删除操作在栈顶举行。

3、设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为BCDEFEF。

四、回答下列问题（每小题8分，共40分）

1．分离给出对下图举行深度优先和广度优先遍历的结果。

2．已知序列（12，4，17，10，7，30），用冒泡排序法对其举行递增排序，写出每一趟的排序结果。

3．一批数据有如下的规律结构B=(K,R),其中

K={kkkk1239,,,,},R={r},

r={kkkkkkkkkkkkkkkk1213141718454689,,,,,,,,,,,,,,,},试用图示法表示其规律结构。

4．已知字符：C1，C2，C3，C4，C5，C6的权分离为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。

5.已知如下图所示二叉树，分离写出其前序、中序和后序序列。

五、编写算法（每小题10分，共20分）

要求:1、说明算法中使用的主要数据结构、变量；2、用C

1．设有一个无头结点的单链表，编写子程序(或函数)统计其结点个数。

2．设有一向量A=（a1，a