数据结构与算法-试题及答案

绪论

一、填空题

1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合—、线性结构_、

树型结构_、图状结构

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储

_、链式存储_、索引存储_、散列存储

二、选择题

1、一个算法必须在执行有穷步之后结束，这是算法的（B）0

A、正确性B、有穷性

C、确定性D、可行性

2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚

地给出规定，这是算法的（A）o

A、正确性B、有穷性

C、确定性D、可行性

3、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”,

其中的每一步都是我们力所能及的一个动作，这是算法的（D）

A、正确性B、有穷性C、确定性D、可行性

三、简单题

1、什么是数据结构？什么是算法？两者有什么关系？

什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元

素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中,并

在其上定义了一个运算的集合。

什么是算法？广义地说，为解决一个问题而采取的方法和步骤,就称为“算法”

两者有什么关系？算法与数据结构关系密切。选择的数据结构是否恰当直接影响算法的效

率；而数据结构的优劣由算法的执行来体现。

2、什么是复杂度和空间复杂度？

时间复杂度是指执行算法所需要的计算工作量；而

空间复杂度是指执行这个算法所需要的内存空间。

3、数据的逻辑结构分几种？存储结构又有哪几种？

数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性

结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；

数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素

的表示和关系德表示。有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。

线性表

1、一个线性表第一个元素的存储地址是100,每个元素的长度

为2,则第5个元素的地址是（B）。

（A）110（B）108（C）100（D）120

2、向一个有127个元素的顺序表中插入一个新元素并保持原来

顺序不变，平均要移动（O个元素。

（A）64（B）63（C）63.5（D）7

2、线性表采用链式存储结构时，其地址（D）。

（A）必须是连续的（B）部分地址必须是连续的

(C)一定是不连续的(D)连续与否均可以

3、在一个单链表中，若p所指结点不是最后结点，在p之后插

入s所指结点，则执行(B)。

(A)s->next=p;p->next=s;(B)s->next=p->next;p->next=s;

(C)s->next=p->next;p=s;(D)p->next=s;s->next=p;

4、在一个单链表中，若删除p所指结点的后续结点，则执行(A)

(A)p->next=p->next->next;

(B)p=p->next;p->next=p->next->next;

(C)p->next=p->next;(D)p=p->next->next;

5.在长度为n的顺序表的第i(lWiWn+l)个位置上插入一个

元素，元素的移动次数为A,删除第i个位置元素，元素

的移动次数为B«

A.n-i+1B.n-iC.iD.i-1

6.算法分析的两个主要方面是_A__。

A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

7.写出顺序表插入、删除及就地逆置算法(见实验)

〃顺序表的逆置

voidreverse(SqListL)

inti,j,k;

for(i=0,j=L.length-1;i<j;i++,j-)

k=L.elem[i];

L.elem[i]=L.elem[j];

L.elem[j]=k;

8、写出单链表插入、删除、求表长及逆置算法(见教材p32页算法2.19)

排序

1.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是_A_。

A.堆排序B.冒泡排序

C.直接选择排序D.快速排序

解析：本题考察的是排序的性能。

2.若表R在排序前已按键值递增顺序排列，则_A_算法的比较次数最少。

A.直接插入排序B.快速排序

C.堆排序D.选择排序

3.已知一组关键字{29,18,23,1,68,41,8,65},请分别写出按插入排序、冒泡排序、直接选择

排序和快速排序方法排序过程，每一趟排序结束时的关键字的状态。(见书本P47-P52)

4.写出简单排序算法和一场快速排序算法等等

栈的基础知识

1、若入栈序列是a,b,c,d,e,则不可能的出栈序列是(C)o

(A)edcba(B)decba(C)dceab(D)abode

2、判定一个栈ST(最多元素为m°)为空的条件是(B)o

(A)ST.top!=-1(B)ST.top=-l

(C)ST.top!=m0-1(D)ST.top=m0-l

3、判定一个栈ST(最多元素为m0)为满的条件是(D)o

(A)ST.top!=0(B)ST.top=0

(C)ST.top1=m0-1(D)ST.top=m0-l

4.在n(n>0)个元素的顺序栈中插入1个元素的时间复杂度为(C)。

A.O(nlog2n)B.0()C.0(1)D.0(n)

5.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为(D)。

A.0(n)B.0()C.O(nlog2n)D.0(1)

填空题部分

1、栈的特点是(后进先出(或LIF。))，队列的特点是(先进先出(或FIFO))o

2、线性表、栈和队列都是(线性)结构，可以在线性表的(任何)位置插入和删除元

素，栈只能在(表尾)插入和删除元素，队列只能在(表尾)插入元素和(表首)删

除元素。

3、若队列的入队序列是1,2,3,4,则出队序列是(B)o

(A)4,3,2,1(B)1,2,3,4(C)1,4,3,2(D)3,2,4,1

队列基础知识

1、循环队列用数组A[0,m-l]存放其元素值，已知其头尾指

针分别是front和rear则当前队列中的元素个数是(A)。

(A)(rear-front+m)%m(B)rear-front+1

(C)rear-front-1(D)rear-front

2、以数组Q[0...m-l]存放循环队列中的元素，变量rear

和qulen分别指示循环队列中队尾元素的实际位置和当前

队列中元素的个数，队列第一个元素的实际位置是(D)。

(A)rear—qulen(B)rear—qulen+m

(C)m—qulen(D)l+(rear+m—qulen)%m

3.设循环队列中数组的下标范围是1〜n,其头尾指针分别为f和r,

则判断循环队列满的条件为(B)

A.r=fB.f=(r+l)%n

C.r=(f+l)%(n+1)D.r=f+l

一、填空题

1、线性表、栈和队列都是一线性一结构，线性表可以在—任意位置插入和删除元素；对于

栈只能在栈顶—插入和删除元素；对于队列只能在—队尾插入和一队首删除元素。

2、栈是一种特殊的线性表，允许插入和删除运算的一端称为—栈顶，不允许插入和删除运

算的一端称为—栈底。

3、队列—是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4、向栈中压入元素的操作是先—移动栈顶指针，后一存入元素。

5、在操作序列push(l),push⑵,pop。,push⑸,push⑺,pop。,push⑹之后，栈顶元素是—6,栈

底元素是_1。(push(k)表示整数k入栈，pop表示栈顶元素出栈。)

6、用单链表表示的链式队列的队头是在链表的—链尾一位置。

二叉树和树

1.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，

这种说法(A)(A)正确(B)错误

2.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，

这种说法(B)(A)正确(B)错误

3.已知某二叉树的后序遍历序列是dabeco中序遍历序列是debac,它

的前序遍历序列是(D)o

(A)acbed(B)decab(C)deabc(D)cedba

4.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访

问顺序是dgbaechf,则其后序遍历的结点访问顺序是(D)。

(A)bdgcefha(B)gdbeefha(C)bdgaechf(D)gdbehfea

5.在一非空二叉树的中序遍历序列中，根结点的右边(A)

(A)只有右子树上的所有结点(B)只有右子树上的部分结点

(O只有左子树上的部分结点(D)只有左子树上的所有结点

6.任一二叉树的叶子结点在先、中和后序遍历序列中的相对次序(A)。

(A)不发生改变(B)发生改变(C)不能确定(D)以上都不对

7.对二叉树从1开始进行连续编号，要求每个结点的编号大于其

左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号

小于其右孩子的编号，则可采用」_遍历实现编号。

A.无序B.中序C.后序D.从根开始的层次遍历

8.深度为k的二叉树的结点总数，最多为上个。

klkk

A)2B)log2kC)2-1D)2

9.深度为9的二叉树中至少有3个结点。

A)29B)28C)9D)29-l

10.二叉树有n个叶子，没有度为1的结点，共有2n-l个结点

分析：度为2的结点有n-1个，所以共2n-l个结点。

11.设一棵完全二叉树具有1000个结点，则它有500个叶子结

点，有处个度为2的结点，有」_个结点只有非空左子树，有_

。一个结点只有非空右子树。

12.一棵深度为6的满二叉树有32个叶子和31个分支结点。

13、n个叶子结点的二叉树最少有2n-l结点。

作业：

1、一棵哈夫曼树有19个结点，则其叶子结点的个数是(10)。

2、有七个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造

一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点

的权的次序构造)，并计算出带权路径长度WPL及该树的结点总数。

例：50

2129

11101514

5678

23

上图为树，

所以带权路径长度为2x4+3x4+6x3+10x2+7x3+8x3+14x2=131

3、有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。

(1)、试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树

根结点的权)。

(2)、求出每个字符的哈夫曼编码。(3)、求出传送电文的总长度。

(4)、并译出编码系列11000111000101011的相应电文。(P143)

(1)

27

II

189

II

117

II

65

II

24

WPL=9*l+7*2+5*3+(2+4)*4=62

(2)5种字符a、b、c、d、e的哈夫曼编码依次为011、10、00、010、11

4、对于给定的一组权值W={1,3,7,8,14,20,28}建立哈夫曼树，并计算带

权路径长度。

5、假定有7个字符a,b,c,d,e,f,g出现的概率分别为0.07,0.09,0.14,0.23,

0.44,0.58,0.77,求这7个字符的哈夫曼编码。

6、某通信过程中使用的编码有8个字符A,B,C,D,E,F,G,H,其出现的次数分别为20,6,34,11,9,

7,8,5。若每个字符采用3位二进制数编码，整个通信需要多少字节？请给出哈夫曼编码，

以及整个通信使用的字节数？

7、对右图所示的普通树，完成以下操作：

⑴分别画出这棵树的双亲表示法、孩子表示法的存储结构图；

⑵将这棵树转换成二叉树；

⑶写出对上小题得到的二叉树分别进行前序、中序、

后序遍历所得到的遍历序列。

8、设一棵二叉树的先序、中序遍历序列分别为ABDFCEGH和BFDAGEHC,请写出

分析过程并画出这棵二叉树，然后写出该二叉树的后序遍历序列。

第7章图

选择题

1.在一个图中，所有顶点的度数之和等于所有边数的(C)倍。

(A)1/2(B)1(C)2(D)4

2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B)倍。

(A)1/2(B)1(C)2(D)4

3.一个有"个顶点的无向图最多有(C)条边。

(A)n(B)n(n-l)(C)n(n-l)/2(D)2n

4.具有4个顶点的无向完全图有(A)条边。

(A)6(B)12(C)16(D)20

5.具有6个顶点的无向图至少应有(A)条边才能确保是一个连通图。

(A)5(B)6(C)7(D)8

6.在一个具有"个顶点的无向图中，要连通全部顶点至少需要(C)条边。

(A)n(B)n+1(C)n-1(D)nfl

7.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小

为(D)o

(A)n(B)(n-l)2(C)n-1(D)n2

8.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头数

组的大小为(A),所有邻接表中的结点总数是(C)。

①(A)n(B)n+1(C)n-1(D)n+e

②(A)efl(B)e(C)2e(D)n+e

9.在含有n个项点有e条边的无向图的邻接矩阵中,零元素的个数为(D)o

A.eB.2eC.n2-eD.n2-2e

10.图的深度优先遍历算法类似于树的(A)o

(A)先根遍历(B)后根遍历(C)按层遍历

11.图的广度优先遍历算法类似于树的(C)。

(A)先根遍历(B)后根遍历(C)按层遍历

填空题部分

1.n个顶点的连通图至少(N-1)条边。

2.在一个无向图的邻接表中，若表结点的个数是m,则图中

边的条数是(M/2)条。

3.分别用普里姆和克鲁斯卡尔算法构造下图所示网络的最小

生成树。

4.分别求出图4从V2出发按深度优先搜索和广度优先搜

索算法遍历得到的顶点序列（假设图的存储结构采用邻

接矩阵表示）。

图45.已知一个有向图的邻接表如图5所示，求出根据深度优

先搜索算法从顶点vl出发遍历得到的顶点序列。

6、对右边所示的有向图邻接矩阵：

①求出每个顶点的入度和出度。

②画出图的邻接表；

③分别写出自顶点1出发进行遍历所得的深

度优先遍历序列和广度优先遍历序列。

2345678910

10000001010

20010001000

30001000100

40000100010

50