青岛大学数据结构期末复习题

数据结构

单选1.

中缀表达式的后缀“2”(3+4)7”表达式是()其中#表示一个数值的结束。

A.2#3#4#1#'+-

B.2#3#4#+-1#-

C.2#3#4#"+1#-

D.-+~2#3#4#l#

［答案］B

单选2.

一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是()。

A.对称矩阵

B.非对称矩阵

C.稀疏矩阵

D.稠密矩阵

［答案］A

判断3.

堆排序是一种稳定的排序算法。

A.正确

B.错误

［答案］B

单选4.

如果对含有n(N>l)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；

在第一个元素前面插入新元素；在最后一个元素后面插入新元素。则最好使用以下哪种存储

结构，并简要说明理由。

(1)只有尾节点指针没有头结点指针的循环单链表

(2)只有尾节点指针没有头结点指针的非循环双链表

(3)只有头结点指针没有尾结点指针的循环双链表

(4)既有头节点指针也有尾结点指针的循环单链表

［答案］(3)理由：实现上述4种运算的时间复杂度均为0(1)

多选5.

计算机算法必须具备()等特性。

A.可行性，确定性

B.可行性，可移植性

C.输入，输出

D.有穷性

E.易读性

F.稳定性

［答案］ACD

判断6

哈希查找法中解决冲突问题的常用方法是除留余数法。

A.正确

B.错误

［答案］B

单选7.

一棵含有n个结点的线索二叉树中，其线索个数为()。

A.n

B.n-1

C.n+1

D.n

［答案］C

单选8

设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是()。

A.25

B.50

C.10

D.7

［答案］D

判断9

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小值与图中的

顶点个数有关，而与图的边数无关。

A.正确

B.错误

［答案］A

单选10

一颗深度为h(h>=l)的完全二叉树至少有()个节点。

A.2"(h-1)

B.2-h

C.2*h+l

D.2"(h-1)+1

[答案]B

问答11

有一颗二叉树排序树按先序遍历得到的序列为(12,5,2,8,6,10,16,15,18,20)。

回答以下问题。

(1)画出该二叉树排列数。

(2)给出该二叉排序树的中序遍历序列。

(3)求在等概率下的查找成功和不成功情况下的平均查找长度。

[答案](1)

(2)(2,5,6,8,10,12,15,16,18,20)

(3)ASL成功=(13+2*2+4*3+3*4)/10=29/10

ASL不成功=(5*3+6*4/11)=39/11

单选12.

若一个栈采用数组s[0..n-l]存放其元素，初始时栈顶指针为n,则以下元素x进栈的正确

操作是()。

A.top++;s[top]=x;

B.s[top]=x;top++;

C.top—;S[top]=x;

D.s[top]=x;top一;

[答案]C

判断13.

使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

A.正确

B.错误

[答案]A

论述题14.

设A和B是两个结点个数分别为m和n的单链表(带头结点)，其中元素递增有序。设计-

个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。

给出你所设计的算法的时间复杂度和空间复杂度。

［答案］

多选15

以下说法正确的是()。

A.二叉树的特点是每个结点至多只有两棵子树。

B.二叉树的子树无左右之分。

C.二叉树只能进行链式存储。

D.树的结点包含一个数据元素及若干指向其子树的分支.

［答案］AD

判断16.

如果有向图中各个顶点的度都大于2,则该图中必有回路。

A.正确

B.错误

［答案］B

单选17

二叉树的第k层的结点数最多为()。

A.2"K-1

B.2K+1

C.2K-1

D.27K-1)

［答案］D

判断18.

如果采用如下方法定义一维字符数组：intmaxSize=30;char*a=newchar［maxSize］;则这种数

组在程序执行过程中不能扩充。

A.正确

B.错误

［答案］B

多选19.

下列属于算法的重要特征的是()。

A.有穷性

B.确定性

C.可行性

I).输入和输出

［答案］ABCD

论述20

单选2L

设无向连通图有n个顶点e条边，若满足()则图中一定有回路。

A.e>=n

B.e<n

C.e=n-l

D.2e>=n

［答案］A

多选22.

依据所有数据成员之间的逻辑关系的不同，数据结构分为()。

A.非线性结构

B.逻辑结构

C.物理结构

D.线性结构

［答案］AD

单选23.

数据结构是指()。

A.一种数据类型

B.数据的存储结构

C.一组性质相同的数据元素的集合

D.相互之间存在一种或多种特定关系的数据元素的集合

［答案］D

单选24.

以下序列是堆的是()。

A.{75,65,30,15,25,45,20,10}

B.(75,65,45,10,30,25,20,15}

C.{75,45,65,30,15,25,20,10}

D{75,45,65,10,25,30,20,15}

［答案］C

判断25.

任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。

A.正确

B.错误

[答案]A

单选26.

以下算法的时间复杂度为()。

voidfun(intn)

{inti=l;

while(i<=n)

i++；

)

A.0(n)

B.0(Vn)

C.0(nlog2n)

D.0(log2n)

[答案]A

判断27.

线性表的逻辑顺序总是与其物理顺序-致。

A.正确

B.错误

[答案]B

判断28.

在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0(1)。

A.正确

B.错误

[答案]A

判断29.

对稀疏矩阵进行压缩存储是为了节省存储空间。

A.正确

B.错误

[答案]A

单选30.

设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),

每个元素占一个空间，问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示()。

A.688

B.678

C.692

D.696

［答案］c

判断31.

对具有n个结点的堆进行插入一个元素运算的时间复杂度为0(n)。

A.正确

B.错误

［答案］B

单选32.

树最适合用来表示()。

A.有序数据元素

B.无序数据元素

C.元素之间具有分支层次关系的数据

D.元素之间无联系的数据

［答案］C

单选33.

在一棵m阶B树中删除一个关键字会引起合并，则该结点原有()个关键字。

A.1

B.［m/2］

C.「m/2」-1

D.［m/2］+1

［答案］C

判断34.

当向一个最小堆插入-一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到

堆顶位置为止。

A.正确

B.错误

［答案］A

判断35.

对平衡二叉树进行中根遍历，可得到结点的有序排列。

A.正确

B.错误

［答案］A

单选36.

以下数据结构中哪一个是非线性结构？()

A.队列

B.栈

C.线性表

D.二叉树

［答案］D

多选37

下列说法正确的有()。

A.算法和程序原则上没有区别，在讨论数据结构时二者通用

B.从逻辑关系上讲，数据结构分为两大类:线性结构和非线性结构

C.所谓数据的逻辑结构是指数据元素之间的逻辑关系

D.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的

个数相等

E.数据的逻辑结构与数据元素本身的内容和形式无关

F.数据结构是指相互之间存在一种或多种关系的数据元素的全体

［答案］BCF

单选38.

对于AOE网的关犍路径，以下叙述()是正确的。

A.任何一个关键活动提前完成，则整个工程一定会提前完成

B.完成整个工程的最短时间是从源点到汇点的最短路径长度

D.任何一个活动持续时间的改变可能会影响关键路径的改变

［答案］D

单选39

在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为()。

A.0(n)

B.0(Vn)

C.0(nlog2n)

D.0(n'2)

［答案］A

单选40.

设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为

()»

A.q=p->next;p->data=q->data;p->next=q->next;free(q);

B.q=p->next;q->data=p->data;p>next=q->next;free(q);

C.q=p->next;q->data=p->data;p->next=q->next;free(q);

D.q=p->next;p->data=q->data;free(q);

［答案］A

多选41.

线性表的特点正确的()

A.存在唯一的一个被称作”第一一个”的数据元素。

B.不存在唯一的一一个被称作”第一一个“的数据元素。

C.存在唯一的一个被称作”最后一个“的数据元素。

D.不存在唯一-的——个被称作”最后-个“的数据元素。

［答案］AC

单选42.

下列四种排序中()的空间复杂度最大。

A.快速排序

B.冒泡排序

C.希尔排序

D.堆

［答案］A

单选43.

用某种排序方法对数据序列

{24,88,21,48,15,27,69,35,20}进行递增排序,元素序列的变化情况如下:

{24,88,21,48,15,27,69,35,20}(2)

{20,15,21,24,48,27,69,35,88}(3)

{15,20,21,24,35,27,48,69,88}(4)

{15,20,21,24,27,35,48,69,88}则所采用的排序方法是0,

A.快速排序

B.简单选择排序

C.直接插入排序

D.归并排序

［答案］A

判断44.

在一个顺序存储的循环队列中，队头指针指向队头元素的后一一个位置。

A.正确

B.错误

［答案］B

单选45.

设环形队列中数组的下标为O~NT,其队头、队尾指针分别为front和rear(front指向队

列中队头元素的前一一个位置，rear指向队尾元素的位置)，则其元素个数为()。

A.rear-front

B.rear-front-1

C.(rear-front)%N+1

D.(rear-front+N)%N

［答案］D

多选46.

下面关于线性表的叙述正确的是()。

A.线性表采用顺序存储必须占用一片连续的存储空间

B.线性表采用链式存储不必占用一片连续的存储空间

C.线性表采用链式存储便于插入和删除操作的实现

D.线性表采用顺序存储便于插入和删除操作的实现

［答案］ABC

多选47.

算法设计的要求包括()

A.正确性

B.可读性

C.健壮性

D.确定性

［答案］ABC

问答题48.

有人提出这样的一种从图G中顶点u开始构造最小生成树的方法:假设G=(V,E)是一个具有

n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T

的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：

(1)初始化U={u}。以u到其他顶点的所有边为候选边。

(2)重复以下步骤n-1次，使得其他n-1个顶点被加入到U中。

从候选边中挑选权值最小的边加入到TE,设该边在V-U中的顶点是v,将v加入U中。考查

顶点V,将v与V-U顶点集中的所有边作为新的候选边。若此方法求得的T是最小生成树，

请予以证明。若不能求得最小边，请举出反例。

［答案］

答:此方法不能求得最小生成树。例如，对于如图9.37(a)所示的带权连通无向图，按照

上述方法从顶点0开始求得的结果为图9.37(b)所示的树，显然它不是最小生成树，正确

的最小生成树如图9.37(c)所示。

在有些情况下，上述方法无法求得结果，例如对于如图9.37(d)所示的带权连通无向图，

从顶点0出发，找到顶点1(边(0,1)),从顶点1出发，找到顶点3(边(1,3)),再从顶

点3出发，找到顶点0(边(3,0)),这样构成回路，就不能求得最小生成树了。

单选49.

用链接方式存储的队列，在进行插入运算时().

A.仅修改头指针

B.头、尾指针都要修改

C.仅修改尾指针

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

[答案]D

单选50.

在一棵m阶B-树中删除一个关键字会引起合并，则该结点原有()个关键字。

A.1

B.[m/2]

C.[m/2]-l

D.[m/2]+l

[答案]C

判断51.

当待排序序列初始有序时，简单选择排序的时间复杂性为0(n)。

A.正确

B.错误

[答案]B

判断52.

内部排序是指排序过程在内存中进行的排序。

A.正确

B.错误

［答案］A

问答题53.

已知一棵度为4的树中，其度为0、1、2、3的结点数分别为14、4、3、2,求该树的结点总

数n和度为4的结点个数，并给出推导过程。

［答案］

单选54.

设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对()个字符进行编码.

A.999

B.998

C.1000

D.1001

［答案］C

单选55.

哈希查找方法一般适用于()情况下的查找。

A.查找表为链表

B.查找表为有序表

C.关键字集合比地址集合大得多

D.关键字集合与地址集合之间存在着某种对应关系。

［答案］D

论述题56.

假设一个连通图采用邻接表G存储结构表示。设计一个算法，求起点u到终点v的经过顶点

k的所有路径。

［答案］

解法1,深度优先*i为的『递，1饵法思想是：采用个■序板SiU保〃被访问过

先将顶点V进板，修改其访问林忐，在栈小空时循环：出栈顶点j.访问之，将其所《

的辐接点进栈,并同时修改它们的访问标志.对应的W法如下.

voidDFS1(AGraph・G,intv)

(intvisitedlMAXV]rl.j;

intSt[MAXV)rtop-Ij

ArcNode*pj

for<i«0;i<G->n;i**)〃访“标志数细置初依

vi8ited[i]«0;

top**;

St(top]-v;//初始顶点过栈

visited(v]-l;〃修改访问标志

while(top>-l>〃极不空时循环

<j-St(topJ;top-一;//Hitt

prlntf<-%dj);〃访问力点j

p-G->adjllst(j].firstarc;〃找第个密接点

while(p!二NULL)

(if(vi«ited(p->adjvexJ~»0>〃构未访问过的郭隹点进枝

{top**;

St(top]-p->ad3vex;

visited(p->adovex)-1;//修改访问标上

p-p->nextarc;〃找下•个邻接点

DFSI作递以灯法思路滑处,但和DFS算法相比产生的访问序列是不同的.例女

如图9.9所示的邻接衣.从原点。开始遍历时.DFSW法是先输出0.切找到H邻接

2、3,即按fttt边单链我中忖点的顺序进行处理的•而DFS1环法中由于是采用栈保7

过的邻接度点.所以是按照边华能表中埼点的逆序进行处理因此，DFS(GO)的喻H

0、I.2、3、4•血DFSI(GO)的输出结果为0、3、4.2、1(实际上深度优先遍历月

«♦的)•

解法2：根仿DFS通仃算法中p指针的变化过程,得到如卜非递打环法：

voidDFS2(AGraph•GUntv)〃■渔仃潭皮优先遍历算法

<AxcNodeep;

ArcNode•St(MAXV);

intvisited[MAXVJ;

inttop«-lrw,i;

for(i»0;l<G->n;〃切问标志数用置初值

visited(i)«0;

printf(*%dLv”〃访向v『点

vlsited(v)«l;〃置已仿何标＜n

top**;〃将《USv的第个铺接点选栈

St(top]«G->«djlist(vj.flrstarcj

新编数据结构习题与解析

while(top>-l)〃栈不空循环

{p=St[top];

〃出栈一个顶点为当前顶点

top一;

while(p!=NULL)//循环遍历其邻接顶点

{w=p->adjvex;//该邻接顶点的编号为W

if(visited[w]«=0)〃若该顶点未访问过

{printf(n%d”，w)//访问w顶点