数据结构强化习题课汇总复习过程.docx
- 文档编号:13648999
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:51
- 大小:13.87MB
数据结构强化习题课汇总复习过程.docx
《数据结构强化习题课汇总复习过程.docx》由会员分享,可在线阅读,更多相关《数据结构强化习题课汇总复习过程.docx(51页珍藏版)》请在冰点文库上搜索。
数据结构强化习题课汇总复习过程
数据结构强化习题课汇总
第一章绪论
考点1数据结构基础知识
1.数据的逻辑结构是指(),数据的存储结构是指()
分析:
数据结构包括三方面的内容:
数据的逻辑结构、存储结构和数据的运算。
其中,逻辑结构是指各数据元素之间的逻辑关系,存储结构是指逻辑结构用计算机语言的实现。
解答:
数据元素之间的逻辑关系;数据的逻辑结构用计算机语言的实现。
2.在数据结构中,从逻辑上可以把数据结构分为:
(A)
A线性和非线性结构B紧凑和非紧凑结构
C动态和静态结构D内部和外部结构
分析:
数据结构中,逻辑上可以把数据结构分成线性结构和非线性结构。
线性结构的顺序存储结构是一种随机存取的存储结构,线性表的链式存储结构是一种顺序存储结构。
线性表若采用链式存储表示时,所有结点之间的存储单元地址可连续可不连续。
逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数无关。
关键考点点评:
线性结构的特征,有且仅有一个开始结点和终端结点,所有结点最多只有一个直接前驱和后继。
栈和队列。
非线性结构的结点有多个前驱或后继,树和图。
3.数据结构在物理上可以分为()存储结构和链式存储结构。
分析:
物理存储
解答:
顺序
4.下列术语中,()与数据的存储结构无关
A循环队列B堆栈
C散列表D单链表
解答:
A
5.()不是算法所必须具备的特性
A有穷性B确定性
C高效性D可行性
分析:
算法的五个重要特征:
有穷性、确定性、可行性、输入和输出。
解答:
C
考点2时间复杂度计算
1.设n是描述问题规模的非负整数,下面程序段的时间复杂度是()
2.
第二章线性表
考点1线性表的基本概念
1.线性表是n个()的有限序列。
A字符B数据元素C由数据项D信息项
解析:
解答B
2.线性表是一个()。
A有限序列,可以为空B有限序列,不能为空
C无限序列,可以为空D无限序列,不能为空
解答A
关键考点点评:
对于非空线性表
1.有且仅有一个开始结点,没有直接前驱,有且仅有一个直接后继;
2.有且仅有一个终结结点,没有直接后继,有且仅有一个直接前驱;
3.其余的内部结点都有且仅有一个直接前驱和后继
3.单链表不能随机存取元素原因是:
要得到元素的存储地址,必须()
解答:
从起始结点开始扫描以得到其地址
注:
顺序表可以,但是链表不行
考点2线性表的顺序存储结构
1.下述()是顺序存储结构的优点
A插入运算方便B可方便地用于各种逻辑结构的存储表示
C存储密度大D删除运算方便
解答:
C
2.线性表的()存储结构是随机存储结构。
分析:
随机存储结构代表可以直接访问其中的任意一个元素。
解答:
顺序
关键考点点评:
顺序存储:
把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。
一般可以用数组实现。
3.设线性表有n个元素,以下操作中,()在顺序表上实现比在链表上实现效率更高
A输出第i个元素值B交换第一个第二个元素的值
C顺序输出所有元素D输出与给定值x相等的元素在线性表中的序号
解答:
A
4.若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算,则利用()存储方式最节省时间。
A顺序表B双链表C带头结点的双循环链表D单循环链表
解答:
A
5.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度是()
AO(0)BO
(1)CO(n)DO(n*n)
分析:
6.顺序表的插入算法中,当n个空间已满时,可申请再增加分配m个空间。
若申请失败,则说明系统没有()可分配的存储空间。
Am个Bm个连续的Cn+m个Dn+m个连续的
解答:
D
7.简述线性表的顺序存储和链式存储的特点的比较
8.对于顺序存储的线性表,设其长度为n,在任何位置上插入或删除都是等概率的。
插入一个元素时大约要移动表中()元素。
An/2B(n+1)/2C(n-1)/2Dn
解答A
9.设顺序表的长度为n,并设从表中删除元素的概率相等。
则在平均情况下,从表中删除一个元素需要移动的元素个数是()
A(n-1)/2Bn/2Cn(n-1)/2Dn(n+1)/2
解答A
10.在n个结点的线性表的数组实现中,算法的时间复杂性是O
(1)的操作是:
A访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)
B在第i个结点后插入一个新的结点(1<=i<=n)
C删除第i个结点(1<=i<=n)
D以上都不对
解答:
A
11.顺序存储的线性表A,其数据元素为整型,编写算法,将A拆成B和C两个表,使A中元素值大于等于0的存入B,小于0存入C。
要求:
(1)表B和C另外设置存储空间。
(2)B和C不另外设置,而利用A的空间。
考点3线性表的链式存储结构
1.以下关于链式存储结构的叙述,()是不正确的。
A结点除自身信息外还包括指针域,因此存储密度小于顺序结构
B逻辑上相邻的结点物理上不必相邻
C可以通过计算直接确定i个结点的存储位置
D插入删除操作方便,不必移动结点
解答:
C
2.链表不具备的特点是()
A可随机访问任一个元素B插入和删除时不需要移动元素
C不必事先估计存储空间D所需空间与线性表长度成正比
分析:
A是顺序表的特点,链表的元素不可以直接随机访问,一般是从链表的起始位置依次搜索得到
答案:
A
3.线性表可用顺序表或者链表存储,它们有什么优缺点?
如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表得到总数也可能自动改变,在这种情况下应该选用哪种存储表示
分析:
考点4单链表及其基本操作
1.对链表设置表头结点的作用是什么
解答:
一般来说,设置表头结点的目的是统一空表与非空表的操作,简化链表操作的实现,而且,头结点也可以用来存储一些链表的基本信息,如链表长度等。
2.对给定的n个元素,建立一个有序单链表的时间复杂度是:
分析:
在不申请额外存储空间的前提下,建立一个n元素的有序单链表是时间复杂度是O(n*n),因为对任意一个元素,插入单链表中合适位置的开销是O(n),对n个元素则是O(n*n)
3.将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度是:
分析:
由于将长度为n的单链表连接在长度为m的单链表之后的操作,需要把长度为m的单链表遍历一遍,找到最后一个结点,所以时间复杂度我O(m)
4.设计一个算法intincrease(LinkList*L),判定带头结点单链表L是否是递增的,若是返回1,否则返回0.
5.有一个无头结点的单链表,结点有数据域data,指针域next,表头指针为h,通过遍历链表,将链表中所有的链表方向逆转。
要求逆转后的链表的表头指针h指向原链表的最后一个结点。
算法如下请填空。
关键考点点评:
6.在一个单链表中,若删除p所指结点的后继结点,则执行:
答案:
A
7.在单向链表中p结点的后面插入新结点s,应执行语句:
答案:
s->next=p->next;p->next=s
8.
9.已知线性表中的元素以值递增有序排列,并以单链表作为存储结构。
编写算法,删除表中所有值相同的元素,同时释放被删除的结点空间。
10.设有序表以带头结点的单链表存储。
请设计一个函数,实现在该表内插入一个新元素的操作。
要求插入后,仍为有序表。
假定每个结点有两个域,element和link,元素为整型,link具有指向后继结点的指针类型,要求使用类型说明定义单链表结构,并实现函数。
11.编写逆向输出的不带头结点的单向链表中数据域的递归算法。
设表中有四个结点,从表头至表尾其数据域分别为10,30,20,40作图表示出该算法的执行过程。
设该链表的结点的数据类型名称为list,结点的数据域和指针域的名称分别是data和next,不必写出list的定义
考点5循环链表及其基本操作
1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间
A非循环的单链表B仅有头指针的单循环链表
C非循环的双链表D仅有尾指针的单循环链表
答案:
D
2.有一个含头结点的单循环链表,头指针为head,则判断其是否为空的条件是:
答案:
head->next==head
3.设线性表非空,采用下列()所描述的链表可以在O
(1)时间内在表尾插入一个新结点。
A带表头结点的单链表,一个链表指针指向表头结点
B带表头结点的单循环链表,一个链表指针指向表头结点
C不带表头结点的单链表,一个链表指针指向表的第一个结点
D不带表头结点的单循环链表,一个链表指针指向表的第一个结点
分析:
这里用O
(1)时间插入的方法是,在表头结点后面插入一个新表头,然后把原来表头改成新的结点。
解答:
B
考点6双链表及其基本操作
1.N表示线性表中当前元素的数目,p表示指针的存储单元大小,E表示数据元素的存储单元大小,D表示可以在数组中存储的线性表元素的最大数目,那么使用顺序表所需空间大小为(),使用双向链表(不考虑头结点)所需空间的大小为()
分析:
考察线性表存储空间的计算。
解答:
ED,(2P+E)n
2.
解答:
B
3.指针p指向双向链表的某个结点,在指针p所指结点之后插入s所指结点。
结点结构:
prior-data-next,操作序列是:
分析:
链表中插入结点的顺序是一般先处理被插入者
解答:
s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
考点7单链表的应用
1.
2.
3.
考点8单循环链表的应用
1.设计一个将单循环链表逆置的算法函数
考点9其他链表及特殊算法
1.判断带头结点的双向循环链表s是否对称相等的算法如下所示,请填空。
第三章栈和队列
考点1栈和队列的基本概念
1.判断:
线性表、栈和队列的逻辑结构完全相同
解答:
正确
2.判断:
栈和队列都是线性表,只是在插入和删除时受到一些限制。
分析:
栈和队列是两种特殊的线性表,他们的逻辑结构与线性表相同只是其运算规则较线性表有更多的限制,故又称他们为运算受限的线性表
解答:
正确
3.判断:
在链队列中,除了队头指针外,还必须设队尾指针,否则无法进行队列的插入操作。
解答:
正确
关键考点点评:
队列的链式存储结构简称链队列。
它是限制仅在表头删除和表尾插入的单链表。
注意:
增加指向链表上的最后一个结点的尾指针,便于在表尾作插入操作。
4.循环队列的优点是什么?
如何判断它的空和满。
5.以下的叙述中,正确的是:
A线性表的线性存储结构优于链式存储结构
B二维数组是其数据元素为线性表的线性表
C栈的操作方式是先进先出
D队列的操作方式是先进后出
解答:
B
6.执行()操作时,需要使用队列作为辅助存储空间
A查找哈希表B广度优先搜索图
C先序遍历二叉树D深度优先搜索图
分析:
考察上述几种操作在额外空间上的需求。
查找哈希表和先序遍历二叉树不需要比较额外的空间;而深度优先搜索图则可以利用递归的方法,使用堆栈,而不使用队列作为辅助存储空间;只有广度优先搜索图需要用到队列作为辅助存储空间。
解答:
B
考点2入栈出栈分析
1.元素abcde依次进入初始为空的栈中,若元素进栈后可停留,可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是:
A3B4C5D6
分析:
该题考查堆栈的进出问题,出栈顺序必为d-c-b-a-,e的顺序不定,在任意一个“-”上都有可能。
故可能以d开头的序列个数是4
解答:
B
2.当入队序列为1、2、3时,出队序列可以是什么?
当入栈序列为1、2、3时,出栈序列可以是什么?
解答:
出队序列为123,出栈序列可以是123,132,231,213,321
考点3栈的基本操作
1.利用栈求表达式的值时,设立操作数栈OPND,设OPND只有两个存储单元,在下列表达式中,不发生上溢的是:
A.a-b*(c-d)B.(a-b)*c-d
C.(a-b*c)-dD.(a-b)*(c-d)
分析:
只有B的运算顺序是依次向右,不需要暂存其他的操作数来配合运算优先顺序
解答:
B
2.向一个栈顶指针为top的链栈中插入一个s结点,则执行:
A.top->next=sBs->next=top->next;top->next=s
C.s->next=top;top=sD.s->next=top;top=top->next
解答:
C
关键考点点评:
3.用不带头结点的链表表示队列,在进行删除运算时
A仅修改头指针B仅修改尾指针
C头尾指针都要修改D头尾指针可能都要修改
解答:
A
4.当两个栈共享一个空间时,栈用一维数组stack(0,n-1)表示,梁栈顶指针分别为top[1]和top[2],则栈满时的条件为:
分析:
两个栈共享一个空间时,由于栈底是固定的且有两个,所以栈底一定是该空间的两个边,然后数据存放在中间,所以栈满的时候就是两个栈顶挨着的时候。
解答:
top[1]=top[2]+1
考点4栈在递归中的应用
1.一个递归的定义可以用递归过程求解,也可以用非递归过程求解,但是单从运行时间上来看,通常递归过程要比非递归过程:
A较快B较慢C相同D无法比较
分析:
递归过程中通常会引入一些元素的反复计算,而且有堆栈压缩开销,所以通常来说,递归过程要满
解答:
B
2.在递归程序调用过程中,递归工作栈包含了哪些数据?
考点5栈的应用
1.将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符,若栈初试为空,则转换过程中同时保存在栈中的操作符的最大个数是:
分析:
解答:
5
2.在将中缀表达式转换为后缀表达式和计算后缀表达式的算法中,都需要使用堆栈。
对于前者,进入堆栈的元素为表达式中的:
___,而对于后者,进入堆栈的元素为:
___。
中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式是:
___。
解答:
二元运算符,操作数,ab+c/fde/--
3.已知num为无符号十进制整数,请写一非递归算法,该算法依次输出num对应的r进制的各位数字。
要求算法中用到的堆栈采用线性链表存储结构(1 考点6队列的实现与应用 1.设栈s和队列q的初始状态均为空,元素abcdefg依次进入栈s。 若每个元素出栈后立即进入队列q,且7个元素的出队序列是bdcfeag,则栈s的容量至少为: A1B2C3D4 分析: 考查栈的最大递归深度。 栈是先进后出 解答: C 2.在一个链队列里,假设f和r分别为队首和队尾指针,则插入s所指结点的运算是: Af->next=s;f=s;Br->next=s;r=s; Cs->next=r;r=s;Ds->next=f;f=s; 分析: 考查队列的入队操作,即在队尾追加一个元素。 解答: B 关键考点点评: 3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3.当从队列中删除一个元素,再加上两个元素后,rear和front的值为: A1和5B2和4C4和2D5和1 分析: 出队一个元素时处理front执行的操作是front=(front+1)%queuesize,入队一个元素时处理rear执行的操作是rear=(rear+1)%queuesize 解答: B 4.单循环链表表示的队列长度为n,若只设头指针,则进队时间复杂度为: AO(n)BO (1)CO(n*n)DO(nlogn) 分析: 考查链表表示队列的基本知识。 队列的入队操作是把新增的结点插入当前队列的队尾处因为该队列只设置了队头指针,没有尾指针,因此必须要从头指针处一步一步遍历到队尾,让队列的尾指针指向新增结点,从而完成入队操作。 因此遍历的过程可以很容易的得到是n次。 解答: A 第四章树和二叉树 考点1树的概念 1.在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是: A41B82C113D122 分析: 考查树结点的特性。 设树中度为i的结点数分别为Ni,树中结点总数是N,则树中各结点的度之和等于N-1(设边数为B,N个结点的树,除了根结点,每一个结点都有一个边进入,则B=N-1;然而边又是由每个结点分出去的,则B=0*N0+1*N1+2*N2(这个算的其实就是度之和)……..)所以N=1+0*N0+1*N1+2*N2+3*N3+4*N4=N0+N1+N2+N3+N4.根据题中数据,就可以得到N0=82,就是叶子结点个数。 解答: B 2.一棵t叉树中要么是叶子结点,要么是有t个分支的非叶子结点。 设该t叉树叶子结点个数为s,非叶子结点个数为n,写出n和s的关系式。 分析: t叉树有n个非叶子结点,即分支数为n*t(一个分支出去就是一个结点),总的结点数为n*t+1,总的结点数就是叶子结点和非叶子结点之和,为s+n,故n*t+1=s+n,即s=(t-1)n+1 解答: s=(t-1)n+1 考点2二叉树 1.若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是: A257B258C384D385 分析: 该题考查二叉树的结点个数,叶节点数为n,则度为2的结点数为n-1,度为1的结点数为0或1,本题中为1(总结点数为偶数),即2n=768 解答: C 2.已知一棵完全二叉树的第六层(设根为第一层)有8个叶结点,则完全二叉树的结点个数最多是: A39B52C111D119 分析: 该题考查二叉树特点。 完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶节点,而最后一层之上是满二叉树,并且只有最后两层上有叶节点。 第六层有叶节点,则完全二叉树高度可能为6或7,显然树高为7时结点更多。 若第6层有8个叶节点,则前6层为满二叉树,而第7层缺失了8*2=16个叶节点,故完全二叉树的结点个数最多为2^7-1-16=111。 (满二叉树的结点个数是2^h-1) 解答: C 3.下列二叉排序树中,满足平衡二叉树定义的是: 分析: 平衡二叉树的左右子数高度之差不超过1 解答: B 4.若一棵二叉树有1001个结点,且无度为1的结点,则叶节点个数为: A498B499C500D501 分析: 设叶节点个数为x,则有(1001-x)*2+1=1001 解答: D 5.在完全二叉树中,含有n个叶子节点,当1度结点数为1时,该树的高度为: (),当1度结点数为0时该树高度为: () 6.设二叉树结点结构为left—data—bf—right,定义二叉树结点的平衡因子bf(T)=hl-hr,写一递归算法;确定二叉树tree中非叶子结点的个数。 7.当一棵有n(n<100)个结点的完全二叉树按顺序存储方式存储在bt[1….n],试写一算法,求出二叉树中结点值分别为x和y的两个结点的最近的公共祖先的结点的值。 二叉树的顺序存储表示为: TypedefcharSqBiTree[101]; SqBiTreebt; 考点3二叉树的遍历 1.某二叉树的先序序列和中序序列正好相反,则该二叉树一定具有()的特征。 A二叉树为空或只有一个结点 B若二叉树不为空,则任一结点不能同时拥有左儿子和右儿子 C若二叉树不为空,则任一结点没有左儿子 D若二叉树不为空,则任一结点没有右儿子 分析: 考查二叉树的遍历,先序遍历为: 根,左,右;中序遍历为: 左,根,右。 解答: D 2.任何一棵二叉树的叶子结点在先序中序和后序遍历中的相对次序: A不改变B改变C不能确定D以上都不对 分析: 无论是哪种遍历,都是按照先左后右的顺序进行访问,所以叶子结点遍历过程的相对顺序是固定的 解答: A 3.判断: 如果某二叉树的先序遍历和中序遍历序列相同,则该二叉树中除了叶子结点外的所有结点都没有左子树 解答: 正确 4.一棵非空的二叉树先序和后序序列正好相反,则该二叉树一定满足: A其中任意一个结点均无左孩子B其中任意一个结点均无右孩子 C其中只有一个叶子结点D其中度为2的结点最多只有一个 分析: 先序是按照根左右顺序,后序是按照左右根顺序。 所以如果某个结点同时有左右两个结点,关于这个节点的遍历就不能保证先序和后序正好相反,所以每个结点只有一个子树,所以就是只有一个叶子结点的情况。 解答: C 5.某二叉树的先序和后序序列正好相反,则该二叉树一定是()的二叉树。 A空或只有一个结点B任一结点只有左孩子 C高度等于其结点数D任一结点只有右孩子 分析: 后序和先序序列相反说明每个结点只有一个孩子 解答: C 6.有一链式二叉树btree,结点结构为(lchild,data,rchild)。 分别设计如下算法。 A用高级语言描述链式二叉树的存储结构; B计算二叉树中度为0的结点数目; C计算二叉树的深度; D后序遍历二叉树。 解答: 7.写出二叉树中序遍历的非递归算法。 考点4树与森林 1.已知一棵2011个结点的树其叶子结点个数为116,该树对应的二叉树中无右孩子的非叶子结点个数是: A115B116C1895D1896 分析: 本题可采用特殊情况解法。 设题意中的树如图所示,则对应的二叉树中仅有前115个叶子结点有右孩子,即有1896个结点无右孩子,即有1895个非叶子结点无右孩子。 解答: C 2.设F是由T1T2T3三棵树组成的森林,与F对应的二叉树B。 若T1T2T3的结点数分别是n1n2n3,则二叉树B的左子树中有()个结点,B的右子树有()个结点。 分析: 树和森林的自己的儿子结点就是二叉树中的左子树中的结点,兄弟结点或者兄弟树都是自己的右子树的结点。 解答: n1-1;n2+n3 3.一棵二叉树的中序遍历序列为BCDAFEHJIG,后序遍历序列为DCBFJIHGEA,要求: a画出此二叉树b将二叉树转换为树或森林 考点5哈夫曼树及其应用 1.哈夫曼树是叶子结点____最短的二叉树 解答: 带权路径长度 2.对下面给出的数据序列,构造一棵哈夫曼树,并求出其带权路径长度。 (18,15,7,6,12,23,10,5,4) 3.已知某系统在通信联络中只可能出现八种字符: ABCDEFGH,其出现频率分别为5,29,7,8,14,23,3和11. (1)试构造一棵哈夫曼树 (2)写出计算其WPL的算式和计算结果 (3)写出其中每一个字符的哈夫曼编码 第五章图 考点1图的基本概念和相关术语 1.若无向图G=(V,E)中含有7个顶点,则保证图G在任何情况下都是连同的,需要的边数最少是: A6B15
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 强化 习题 汇总 复习 过程