数据结构习题汇编Word格式.docx
《数据结构习题汇编Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构习题汇编Word格式.docx(20页珍藏版)》请在冰点文库上搜索。
4.算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出_。
5.下列程序段的时间复杂度是____物理___。
for(i=1;
i<
=n;
i++)A[i,i]=0;
6.存储结构是逻辑结构的____物理___实现。
7.从数据结构的观点看,通常所说的“数据”应分成三个不同的层次,即_数据__、__数据元素_和__数据项___。
8.一个算法的时空性能是指该算法的_时间复杂度__和_空间复杂度_,前者是算法包含的_计算量___,后者是算法需要的___存储量__。
四、应用题
1.分析下列程序段的时间复杂度。
……
i=1;
WHILE(i<
=n)i=i*2;
……
答:
O(log2n)
2.简述下列术语:
数据,数据元素,数据结构,数据对象。
数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。
数据结构是指相互之间存在着一种或多种关系的数据元素的集合。
数据对象是性质相同的数据元素的集合。
3.逻辑结构与存储结构是什么关系?
在数据结构中,数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的,与计算机无关;
存储结构是数据元素之间的关系在计算机中的表示。
逻辑结构与存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系。
第二章线性表
1.线性结构中的一个结点代表一个()。
A.数据元素B.数据项C.数据D.数据结构
2.线性表L=(a1,a2,…,ai,…,an),下列说法正确的是()。
A.每个元素都有一个直接前驱和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
3.顺序表是线性表的()。
A.链式存储结构B.顺序存储结构C.索引存储结构D.散列存储结构
4.对于顺序表,以下说法错误的是()。
A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是:
逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是:
逻辑上相邻的元素,存储在物理位置也相邻的单元中
5.对顺序表上的插入、删除算法的时间复杂度分析来说,通常以()为标准操作。
A.条件判断B.结点移动C.算术表达式D.赋值语句
6.对于顺序表的优缺点,以下说法错误的是()。
A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点C.插入和删除操作较方便D.由于顺序表要求占用连续的空间,存储分配只能预先进行(静态分配)
7.在含有n个结点的顺序存储的线性表中,在任一结点前插入一个结点所需移动结点的平均次数为()。
A.nB.n/2C.(n-1)/2D.(n+1)/2
8.在含有n个结点的顺序存储的线性表中,删除一个结点所需移动结点的平均次数为()。
A.nB.n/2C.(n-1)/2D.(n+1)/2
9.不带头结点的单链表head为空的条件是()。
A.head=NULLB.head->
next=NULLC.head->
next=headD.head!
=NULL
补充:
带头结点的单链表head为空的条件是()。
10.在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入结点*s,则执行()。
A.s->
next=p->
next;
p->
next=s;
B.p->
next=s->
s->
next=p;
C.q->
next=s;
s->
D.p->
next=q;
11.在一个单链表中,若*p结点不是最后结点。
在*p之后插入结点*s,则执行()。
A.s->
B.s->
C.s->
p=s;
D.p->
next=p;
12.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素,则采用()存储方式最节省时间。
A.顺序表B.单链表C.双链表D.单循环链表
13.在一个单链表中,若删除*p结点的后继结点,则执行()。
A.q=p->
next=q->
free(q);
B.p=p->
next->
free(p);
C.p->
free(p->
next);
D.p=p->
14.循环链表的主要优点是()。
A.不再需要头指针了B.已知某个结点的位置后,容易找到它的直接前驱C.在进行插入、删除操作时,能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表
15.在线性表的下列存储结构中,读取元素花费时间最少的是()。
A.单链表B.双链表C.循环链表D.顺序表
()1.顺序存储的线性表可以随机存取。
()2.顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。
()3.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。
()4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。
()5.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。
()6.在单链表中,可以从头结点开始查找任何一个元素。
()7.线性表的链式存储结构优于顺序存储结构。
()8.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。
()9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。
()10.顺序存储方式只能用于存储线性结构。
1.为了便于讨论,有时将含n(n>
0)个结点的线性结构表示成(a1,a2,…,an),其中每个ai代表一个__结点___。
a1称为___头___结点,an称为__尾_______结点,i称为ai在线性表中的____位置_____。
对任意一对相邻结点ai、ai+1(1≤i<
n),ai称为ai+1的直接___前驱_____,ai+1称为ai的直接____后继______。
2.线性结构的基本特征是:
若至少含有一个结点,则除起始结点没有直接__前驱_______外,其他结点有且仅有一个直接___前驱_____;
除终端结点没有直接__后继_______外,其他结点有且仅有一个直接______后继___。
3.所有结点按一对一的邻接关系构成的整体就是____线形______结构。
4.线性表的逻辑结构是__线性_结构,其所含结点的个数称为线性表的___长度、_______。
5.在单链表中,删除p所指结点的直接后继的操作是___q=p->
__·
6.对于一个具有n个结点的单链表,在p所指结点后插入一个结点的时间复杂度为___O
(1)_______,在给定值为x的结点后插入新结点的时间复杂度为__O(n)_______。
7.单链表表示法的基本思想是用___指针_________表示结点间的逻辑关系。
8.在顺序表中插入或删除一个元素,平均需要移动_____一半___元素,具体移动的元素个数与____元素位置_____有关。
9.在单链表中,若p和s是两个指针,且满足p->
next与s相同,则语句p->
next的作用是__删除__s指向的结点。
10.在单链表中,指针p所指结点为最后一个结点的条件是__p->
next=NULL_________。
11.在单链表中,若要在p所指结点之前插入s所指的结点,可进行下列操作:
next=__p->
next_________;
p->
temp=p->
data;
data=_s->
data_________;
data=_temp________;
1.描述以下三个概念的区别:
头指针,头结点,首元结点(第一个元素结点)。
首元结点是指链表中存储的线性表中的第一个数据元素的结点。
为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点。
头指针是指向链表中的第一个结点的指针。
2.在顺序表中插入和删除一个结点需平均移动多少个结点?
具体的移动次数取决于哪两个因素?
平均移动表中大约一半的结点,插入操作平均移动n/2个结点,删除操作平均移动(n-1)/2个结点。
具体移动的次数取决于表长和插入、删除的结点的位置。
3.如果有n个线性表同时共存,并且在处理过程中各表的长度会发生动态变化,线性表的总长度也会自动地改变。
在此情况下,应选择哪一种存储结构?
为什么?
应选用链式存储结构。
因为顺序表是静态存储结构,只能预先分配,不能随着线性表长度的改变而变化。
而链表则可根据需要动态地申请空间,因此适用于动态变化表长的线性表。
4.若线性表的总数基本稳定,且很少进行插入、删除操作,但要求以最快的方式存取线性表的元素,应该用哪种存储结构?
应选用顺序存储结构。
因为顺序存储结构存取元素操作的时间复杂度为O
(1)。
何时选用顺序表,何时选用链表作为线性表的存储结构为宜?
从空间上来看,当线性表的长度变化较大、难以估计其规模时,选用动态的链表作为存储结构比较合适,但链表除了需要设置数据域外,还要额外设置指针域,因此当线性表长度变化不大、易于事先确定规模时,为了节约存储空间,宜采用顺序存储结构。
从时间上来看,若线性表的操作主要是查找,很少进行插入和删除操作时,应选用顺序表。
对于频繁进行插入和删除操作的线性表,宜采用链表作为存储结构。
第三章栈和队列
1.设有一顺序栈s,元素s1,s2,s3,s4,s5,s6依次入栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是()。
A.2B.3C.5D.6
2.设有一顺序栈已经含有3个元素,如下图所示,元素a4正等待入栈。
以下序列中不可能出现的出栈序列是()。
A.a3,a1,a4,a2B.a3,a2,a4,a1C.a3,a4,a2,a1D.a4,a3,a2,a1
a1
a2
a3
top
3.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。
A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e
4.一个队列的入队序列是1,2,3,4,则队列的可能的输出序列是()。
A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1
对1.在顺序栈栈满情况下,不能再入栈,否则会产生“上溢”。
错2.与顺序栈相比,链栈的一个优点是插入和删除操作更加方便。
错3.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到4,3,1,2.
对4.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到1,2,3,4。
1.在具有n个单元的循环队列中,队满时共有__n-1____个元素。
2.假设以S和X分别表示入栈和出栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为___bceda__________。
3.栈的逻辑特点是_先进后出__,队列的逻辑特点是_先进先出______,二者的共同特点是___操作受限________。
4.____栈______可以作为实现递归函数调用的一种数据结构。
5.在队列中,新插入的结点只能添加到__队尾__________。
6.设有一个空栈,假设以push和pop分别表示入栈和出栈操作,现在输入序列为1,2,3,4,5,经过push,push,pop,push,pop,push后,栈顶指针所指元素是___4____。
四、综合题
1.已知当前循环队的状态如图所示,请写出依次执行如下操作时队的状态。
d
e
f
frontrear
(1)g,h,i,j入队;
g
h
i
j
(2)d,e出队;
(3)k,l,m,n,o,p入队
l
m
n
k
rearfront
第四章树
一、选择题
1.以下说法错误的是()。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上,二叉树的求双亲操作很容易实现
C.在二叉链表上,求根以及求左、右孩子等操作很容易实现
D.在二叉链表上,求双亲操作的时间性能很好
2.以下说法错误的是()。
A.一般在哈夫曼树中,权值越大的叶子离根结点越近
B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有n棵二叉树,最终求得的哈夫曼树共有2n-1个结点
D.若初始森林中共有n棵二叉树,进行2n-1次合并后才能剩下一棵最终的哈夫曼树
3.深度为6的二叉树最多有()个结点。
A.64B.63C.32D.31
4.将含有41个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为21的双亲结点编号为()。
A.10B.11C.41D.20
5.一棵二叉树满足下列条件:
对任意结点,若存在左、右子树,则其值都小于它的左子树上所有结点的值,而大于右子树上所有结点的值。
现采用()遍历方式就可以得到这棵二叉树所有结点的递减序列。
A.前序B.中序C.后序D.层次
6.如图6-1所示的二叉树的中序遍历序列是()。
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
7.已知某二叉树的后序遍历序列是deacb,中序遍历序列是deabc,它的前序遍历序列是()。
A.acbedB.baedcC.dceabD.cedba
8.在图6-2中的二叉树中,()不是完全二叉树。
9.哈夫曼树的带权路径长度是()。
A.所有结点权值之和B.所有叶结点带权路径长度之和
C.带权结点的值D.除根以外所有结点权值之和
10.设有一棵22个结点的完全二叉树,那么整棵二叉树有()个度为0的结点。
A.6B.7C.8D.11
11.已知完全二叉树有26个结点,则整棵二叉树有()个度为1的结点。
A.0B.1C.2D.13
12.已知如图6-3所示的哈夫曼树,那么电文CDAA的编码是()。
A.110100B.11011100C.010110111D.11111100
13.在n个结点的完全二叉树中,对任一结点i(1≤i≤n),i的左孩子可能是()。
A.i/2B.2i+1C.2iD.都不是
14.已给出图6-3所示的二叉树,A,B,C,D的权值分别为7,5,2,4,则该树的带权路径长度为()。
A.46B.36C.35D.都不是
二、填空题
1.树(及一切树形结构)是一种_________结构。
在树中,_________结点没有直接前驱。
对树上任一结点x来说,x是它的任一子树的根结点惟一的________。
2.二叉树第i(i>
0)层上至多有__________个结点。
3.深度为k(k>
0)的二叉树至多有__________个结点。
4.对任何二叉树,若度为2的节点数为n2,则叶子数n0=__________。
5.满二叉树上各层的节点数已达到了二叉树可以容纳的_________。
满二叉树也是__________二叉树,但反之不然。
6.具有n个结点的完全二叉树的深度为__________。
7.二叉树通常有_____________存储结构和__________存储结构两类存储结构。
8.每个二叉链表必须有一个指向_______结点的指针,该指针具有标识二叉链表的作用。
9.对二叉链表的访问只能从__________指针开始。
10.具有100个结点的完全二叉树的深度是__________。
11.在__________遍历二叉树的序列中,任何结点的子树上的所有结点都是直接跟在该结点之后。
12.若一棵二叉树的叶子数为n,则该二叉树中左、右子树皆非空的结点个数为__________。
13.一棵树的形状如图6-5所示,它的根结点是________,叶结点是____________________________,结点H的度是______,这棵树的度是_______,这棵树的深度是________,结点F的儿子结点是_______,结点G的父结点是_________。
14.含有2n个结点的二叉树高度至少是________,至多是________(仅含根结点的二叉树高度为1)。
三、应用题
1.分别写出图6-7所示二叉树的前序、中序和后序序列。
2.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试画出这棵二叉树,并写出其前序遍历序列。
3.设某密码电文由8个字母组成,a,b,c,d,e,f,g,h,每个字母在电文中的出现频率分别是7,19,2,6,32,3,21,10,试为这8个字母设计相应的哈夫曼树及编码。
4.对于一个关键字序列15,28,3,38,12,2,56,17,20,请生成一个二叉排序树,并给出依次删除38,28后的结果。
第五章图
1.在一个图中,所有顶点的度数之和等于所有边数的()倍。
A.1/2B.1C.2D.4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。
3.一个有N个顶点的无向图最多有()条边。
A.NB.N*(N-1)C.N*(N-1)/2D.2N
4.具有4个顶点的无向完全图有()条边,
A.6B.12C.16D.20
5.具有6个顶点的无向图至少应有()条边才能确保是一个连通图。
A.5B.6C.7D.8
6.一个具有N个顶点的无向图中,要连通全部顶点至少需要()条边。
A.NB.N+1C.N-1D.N/2
7.对于一个具有N个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是()。
A.NB.(N-1)*(N-1)C.N-1D.N*N
8.对于一个具有N个顶点和E条边的无向图,若采用邻接表表示,则表头向量的大小为(
(1));
所有邻接表中的结点总数是(
(2))。
(1)A.NB.N+1C.N-1D.N+E
(2)A.E/2B.EC.2ED.N+E
1.对无向图,其邻接矩阵是一个关于主对角线对称的矩阵。
2.在有向图的邻接矩阵上,由第i行可一得到第个结点的出度,而由第j列可得到第个结点的入度。
3.对无向图,设有n个结点e条边,则其邻接表表示中需要个表结点。
对有向图,设有n个顶点e条弧,则其邻接表表示需要个表结点。
4.在无权图G的邻接矩阵A中,若(Vi,Vj)或<
Vi,Vj>
属于图G的边集,则对应元素A[i,j]等于,否则等于。
5.遍历图的基本方法有优先搜索和优先搜索两种。
1.给出如图5-1所示的无向图G1的邻接矩阵和邻接表。
2.分别给出图5-1所示的G2的邻接矩阵、邻接表和逆邻接表。
图5-1
第六章查找
1.顺序查找法适合于()存储结构的查找表。
A.压缩B.散列C.索引D.顺序或链式
2.对采用折半查找法进行查找操作的查找表,要求按()方式进行存储。
A.顺序存储B.链式存储
C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序
3.设有序表的关键字序列为(1,4,6,10,18,35,42,53,67,71,78,84,92,99),当用折半查找法查找键值为35的结点时,经()次比较后查找成功。
A.