还剩51页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第1章绪论
1.填空
(1)()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理【解答】数据元素
(2)()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位【解答】数据项,数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系
(3)从逻辑关系上讲,数据结构主要分为()、()、()和()【解答】__,线性结构,树结构,图结构
(4)数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容()和()【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系
(5)算法具有五个特性,分别是()、()、()、()、()【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性
(6)在一般情况下,一个算法的时间复杂度是()的函数【解答】问题规模
(7)设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()【解答】Ο1,Οnlog2n【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉
2.选择题⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的A线性结构B非线性结构C存储位置D指针【解答】C,D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示⑵假设有如下遗产继承规则丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不能相互继承则表示该遗产继承关系的最合适的数据结构应该是()A树B图C线性表D__【解答】B【分析】将丈夫、妻子和子女分别作为数据元素,根据题意画出逻辑结构图⑶算法指的是()A对特定问题求解步骤的一种描述,是指令的有限序列B计算机程序C解决问题的计算方法D数据处理【解答】A【分析】计算机程序是对算法的具体实现;简单地说,算法是解决问题的方法;数据处理是通过算法完成的所以,只有A是算法的准确定义⑷下面()不是算法所必须具备的特性A有穷性B确切性C高效性D可行性【解答】C【分析】高效性是好算法应具备的特性⑸算法分析的目的是(),算法分析的两个主要方面是()A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性【解答】C,E
3.判断题
(1)算法的时间复杂度都要通过算法中的基本语句的执行次数来确定【解答】错时间复杂度要通过算法中基本语句执行次数的数量级来确定
(2)每种数据结构都具备三个基本操作插入、删除和查找【解答】错如数组就没有插入和删除操作此题注意是每种数据结构
(3)逻辑结构与数据元素本身的内容和形式无关【解答】对因此逻辑结构是数据__的主要方面
(4)基于某种逻辑结构之上的基本操作,其实现是唯一的【解答】错基本操作的实现是基于某种存储结构设计的,因而不是唯一的
4.分析以下各程序段,并用大O记号表示其执行时间 【解答】⑴基本语句是k=k+10*i,共执行了n-2次,所以Tn=On⑵基本语句是k=k+10*i,共执行了n次,所以Tn=On⑶分析条件语句,每循环一次,i+j整体加1,共循环n次,所以Tn=On⑷每循环一次,循环变量y加1,最后一次y=Tn,即Tn+12≤n,Tn=n1/2-1,y=0……Tn循环体都执行,共Tn+1次,即n1/2次,所以Tn=On1/2⑸x++是基本语句,所以5.设有数据结构(D,R),其中D={123456},R={1223243435364546}试画出其逻辑结构图并指出属于何种结构【解答】其逻辑结构图如图1-3所示,它是一种图结构
6.求多项式Ax的算法可根据下列两个公式之一来设计⑴Ax=anxn+an-1xn-1+…+a1x+a0⑵Ax=…0*x+anx+an-1x+…+a1x+a0根据算法的时间复杂度分析比较这两种算法的优劣【解答】第二种算法的时间性能要好些第一种算法需执行大量的乘法运算,而第二种算法进行了优化,减少了不必要的乘法运算
8.算法设计(要求算法用伪代码和C++描述,并分析最坏情况下的时间复杂度)⑴对一个整型数组A[n]设计一个排序算法⑵找出整型数组A[n]中元素的最大值和次最大值学习自测及答案1.顺序存储结构的特点是(),链接存储结构的特点是()【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系,用指示元素存储地址的指针表示数据元素之间的逻辑关系
2.算法在发生非法操作时可以作出处理的特性称为()【解答】健壮性
3.常见的算法时间复杂度用大O记号表示为常数阶、对数阶、线性阶、平方阶和指数阶【解答】O1,Olog2n,On,On2,O2n4.将下列函数按它们在n时的无穷大阶数,从小到大排列nn-n3+7n5nlogn2n/2n3log2nn1/2+log2n3/2nn!n2+log2n【解答】log2nn1/2+log2nnnlog2nn2+log2nn3n-n3+7n52n/23/2nn!5.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别【解答】数据结构是指相互之间存在一定关系的数据元素的__而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作程序设计语言中的数据类型是一个值的__和定义在这个值集上一组操作的总称
6.对下列用二元组表示的数据结构试分别画出对应的逻辑结构图,并指出属于何种结构⑴A=D,R,其中D={a1a2a3a4},R={}⑵B=D,R,其中D={abcdef},R={abbccddeef}⑶C=D,R,其中D={a,b,c,d,e,f},R={dbegabbceggh}⑷D=D,R,其中D={123456},R={12,14,23,24,34,35,36,46}【解答】⑴属于__,其逻辑结构图如图1-4a所示;⑵属于线性结构,其逻辑结构图如图1-4b所示;⑶属于树结构,其逻辑结构图如图1-4c所示;⑷属于图结构,其逻辑结构图如图1-4d所示
7.求下列算法的时间复杂度count=0;x=1;whilex=n{x*=2;count++;}returncount;【解答】Olog2n第2章线性表
1.填空⑴在顺序表中,等概率情况下,插入和删除一个元素平均需__()个元素,具体__元素的个数与()和()有关【解答】表长的一半,表长,该元素在表中的位置⑵顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是()【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址+5-1×2=108⑶设单链表中指针p指向结点A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为()【解答】p-next=p-next-next⑷单链表中设置头结点的作用是()【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理⑸非空的单循环链表由头指针head指示,则其尾结点(由指针p所指)满足()【解答】p-next=head【分析】如图2-8所示⑹在由尾指针rear指示的单循环链表中,在表尾插入一个结点s的操作序列是();删除开始结点的操作序列为()【解答】s-next=rear-next;rear-next=s;rear=s;q=rear-next-next;rear-next-next=q-next;deleteq;【分析】操作示意图如图2-9所示⑺一个具有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为();在给定值为x的结点后插入一个新结点的时间复杂度为()【解答】Ο1,Οn【分析】在p所指结点后插入一个新结点只需修改指针,所以时间复杂度为Ο1;而在给定值为x的结点后插入一个新结点需要先查找值为x的结点,所以时间复杂度为Οn⑻可由一个尾指针唯一确定的链表有()、()、()【解答】循环链表,循环双向链表,双向链表
2.选择题⑴线性表的顺序存储结构是一种()的存储结构,线性表的链接存储结构是一种()的存储结构A随机存取B顺序存取C索引存取D散列存取【解答】A,B【分析】参见
2.
2.1⑵线性表采用链接存储时,其地址()A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,甚至可以零散分布在内存中任意位置⑶单循环链表的主要优点是()A不再需要头指针了B从表中任一结点出发都能扫描到整个链表;C已知某个结点的位置后,能够容易找到它的直接前趋;D在进行插入、删除操作时,能更好地保证链表不断开【解答】B⑷链表不具有的特点是()A可随机访问任一元素B插入、删除不需要__元素C不必事先估计存储空间D所需空间与线性表长度成正比【解答】A⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋,则采用()存储方法最节省时间A顺序表B单链表C双向链表D单循环链表【解答】A【分析】线性表中最常用的操作是取第i个元素,所以,应选择随机存取结构即顺序表,同时在顺序表中查找第i个元素的前趋也很方便单链表和单循环链表既不能实现随机存取,查找第i个元素的前趋也不方便,双向链表虽然能快速查找第i个元素的前趋,但不能实现随机存取⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用()存储方法最节省时间A单链表B带头指针的单循环链表C双向链表D带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、带头指针的单循环链表、双向链表都不合适,考虑在带尾指针的单循环链表中删除第一个结点,其时间性能是O1,所以,答案是D⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用()存储方法最节省运算时间A单链表B循环双向链表C单循环链表 D带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、单循环链表都不合适,删除最后一个结点需要知道终端结点的前驱结点的地址,所以,带尾指针的单循环链表不合适,而循环双向链表满足条件⑻在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()AO1BOnCOn2DOnlog2n【解答】B【分析】首先应顺序查找新结点在单链表中的位置⑼对于n个元素组成的线性表,建立一个有序单链表的时间复杂度是()AO1BOnCOn2DOnlog2n【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中,而插入每个元素需On⑽使用双向链表存储线性表,其优点是可以()A提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找,所以,双向链表并不能提高查找速度,因为双向链表中有两个指针域,显然不能节约存储空间,对于动态存储分配,回收存储空间的速度是一样的由于双向链表具有对称性,所以,其插入和删除操作更加方便⑾在一个单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行()操作As-next=p-next;p-next=s;Bq-next=s;s-next=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;【解答】B【分析】注意此题是在q和p之间插入新结点,所以,不用考虑修改指针的顺序⑿在循环双向链表的p所指结点后插入s所指结点的操作是()Ap-next=s;s-prior=p;p-next-prior=s;s-next=p-next;Bp-next=s;p-next-prior=s;s-prior=p;s-next=p-next;Cs-prior=p;s-next=p-next;p-next=s;p-next-prior=s;Ds-prior=p;s-next=p-next;p-next-prior=s;p-next=s【解答】D【分析】在链表中,对指针的修改必须保持线性表的逻辑关系,否则,将违背线性表的逻辑特征,图2-10给出备选答案C和D的图解
3.判断题⑴线性表的逻辑顺序和存储顺序总是一致的【解答】错顺序表的逻辑顺序和存储顺序一致,链表的逻辑顺序和存储顺序不一定一致⑵线性表的顺序存储结构优于链接存储结构【解答】错两种存储结构各有优缺点⑶设p,q是指针,若p=q,则*p=*q【解答】错p=q只能表示p和q指向同一起始地址,而所指类型则不一定相同⑷线性结构的基本特征是每个元素有且仅有一个直接前驱和一个直接后继【解答】错每个元素最多只有一个直接前驱和一个直接后继,第一个元素没有前驱,最后一个元素没有后继⑸在单链表中,要取得某个元素,只要知道该元素所在结点的地址即可,因此单链表是随机存取结构【解答】错要找到该结点的地址,必须从头指针开始查找,所以单链表是顺序存取结构4.请说明顺序表和单链表各有何优缺点,并分析下列情况下,采用何种存储结构更好些⑴若线性表的总长度基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素⑵如果n个线性表同时并存,并且在处理过程中各表的长度会动态发生变化⑶描述一个城市的设计和规划【解答】顺序表的优点
①无需为表示表中元素之间的逻辑关系而增加额外的存储空间;
②可以快速地存取表中任一位置的元素(即随机存取)顺序表的缺点
①插入和删除操作需__大量元素;
②表的容量难以确定;
③造成存储空间的“碎片”单链表的优点
①不必事先知道线性表的长度;
②插入和删除元素时只需修改指针,不用__元素单链表的缺点
①指针的结构性开销;
②存取表中任意元素不方便,只能进行顺序存取⑴应选用顺序存储结构因为顺序表是随机存取结构,单链表是顺序存取结构本题很少进行插入和删除操作,所以空间变化不大,且需要快速存取,所以应选用顺序存储结构⑵应选用链接存储结构链表容易实现表容量的扩充,适合表的长度动态发生变化⑶应选用链接存储结构因为一个城市的设计和规划涉及活动很多,需要经常修改、扩充和删除各种信息,才能适应不断发展的需要而顺序表的插入、删除的效率低,故不合适5.算法设计欣赏⑴设计一个时间复杂度为On的算法,实现将数组A[n]中所有元素循环左移k个位置【解答】算法思想请参见主教材第一章思想火花下面给出具体算法分析算法,第一次调用Reverse函数的时间复杂度为Ok,第二次调用Reverse函数的时间复杂度为On-k,第三次调用Reverse函数的时间复杂度为On,所以,总的时间复杂度为On⑵已知数组A[n]中的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为On【解答】从数组的两端向中间比较,设置两个变量i和j,初始时i=0,j=n-1,若A[i]为偶数并且A[j]为奇数,则将A[i]与A[j]交换具体算法如下分析算法,两层循环将数组扫描一遍,所以,时间复杂度为On⑶试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较【解答】参见
2.
2.3⑷试分别以顺序表和单链表作存储结构,各写一实现线性表就地逆置的算法【解答】顺序表的逆置,即是将对称元素交换,设顺序表的长度为length,则将表中第i个元素与第length-i-1个元素相交换具体算法如下单链表的逆置请参见
2.
2.4算法2-4和算法2-6⑸假设在长度大于1的循环链表中,即无头结点也无头指针,s为指向链表中某个结点的指针,试编写算法删除结点s的前趋结点【解答】利用单循环链表的特点,通过指针s可找到其前驱结点r以及r的前驱结点p,然后将结点r删除,如图2-11所示,具体算法如下⑹已知一单链表中的数据元素含有三类字符字母、数字和其他字符试编写算法,构造三个循环链表,使每个循环链表中只含同一类字符【解答】在单链表A中依次取元素,若取出的元素是字母,把它插入到字母链表B中,若取出的元素是数字,则把它插入到数字链表D中,直到链表的尾部,这样表B,D,A中分别存放字母、数字和其他字符具体算法如下⑺设单链表以非递减有序排列,设计算法实现在单链表中删去值相同的多余结点【解答】从头到尾扫描单链表,若当前结点的元素值与后继结点的元素值不相等,则指针后移;否则删除该后继结点具体算法如下⑻判断带头结点的双循环链表是否对称【解答】设工作指针p和q分别指向循环双向链表的开始结点和终端结点,若结点p和结点q的数据域相等,则工作指针p后移,工作指针q前移,直到指针p和指针q指向同一结点(循环双向链表中结点个数为奇数),或结点q成为结点p的前驱(循环双向链表中结点个数为偶数)如图2-12所示学习自测及答案
1.已知一维数组A采用顺序存储结构,每个元素占用4个存储单元,第9个元素的地址为144,则第一个元素的地址是()A108B180C176D112【解答】D2.在长度为n的线性表中查找值为x的数据元素的时间复杂度为()AO0BO1COnDOn2【解答】C3.在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素,需向后__()个元素,删除第i(1≤i≤n)个元素时,需向前__()个元素【解答】n-i+1,n-i4.在单链表中,除了头结点以外,任一结点的存储位置由()指示【解答】其前趋结点的指针域5.当线性表采用顺序存储结构时,其主要特点是()【解答】逻辑结构中相邻的结点在存储结构中仍相邻6.在双向链表中,每个结点设置了两个指针域,其中一个指向()结点,另一个指向()结点【解答】前驱,后继7.设A是一个线性表(a1a2…an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要__的元素个数为多少?若元素插在ai与ai+1之间(1≤i≤n)的概率为,则平均每插入一个元素所要__的元素个数又是多少?【解答】,算法设计欣赏8.线性表存放在整型数组A[arrsize]的前elenum个单元中,且递增有序编写算法,将元素x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度【解答】本题是在一个递增有序表中插入元素x,基本思路是从有序表的尾部开始依次取元素与x比较,若大于x,此元素后移一位,再取它前面一个元素重复上述步骤;否则,找到插入位置,将x插入具体算法如下
9.已知单链表中各结点的元素值为整型且递增有序,设计算法删除链表中所有大于mink且小于__xk的所有元素,并释放被删结点的存储空间【解答】因为是在有序单链表上的操作,所以,要充分利用其有序性在单链表中查找第一个大于mink的结点和第一个小于__xk的结点,再将二者间的所有结点删除10.设单循环链表L1,对其遍历的结果是x1x2x3…xn-1xn请将该循环链表拆成两个单循环链表L1和L2,使得L1中含有原L1表中序号为奇数的结点且遍历结果为x1x3…;L2中含有原L1表中序号为偶数的结点且遍历结果为…x4x2【解答】算法如下第3章栈、队列
1.填空
(1)设有一个空栈,栈顶指针为1000H,现有输入序列为
1、
2、
3、
4、5,经过push,push,pop,push,pop,push,push后,输出序列是(),栈顶指针为()【解答】23,1006H
(2)栈通常采用的两种存储结构是();其判定栈空的条件分别是(),判定栈满的条件分别是()【解答】顺序存储结构和链接存储结构(或顺序栈和链栈),栈顶指针top=-1和top=NULL,栈顶指针top等于数组的长度和内存无可用空间
(3)()可作为实现递归函数调用的一种数据结构【解答】栈【分析】递归函数的调用和返回正好符合后进先出性
(4)栈和队列是两种特殊的线性表,栈的操作特性是(),队列的操作特性是(),栈和队列的主要区别在于()【解答】后进先出,先进先出,对插入和删除操作限定的位置不同
(5)循环队列的引入是为了克服()【解答】假溢出
(6)数组Q[n]用来表示一个循环队列,front为队头元素的前一个位置,rear为队尾元素的位置,计算队列中元素个数的公式为()【解答】(rear-front+n)%n【分析】也可以是(rear-front)%n,但rear-front的结果可能是负整数,而对一个负整数求模,其结果在不同的编译器环境下可能会有所不同
2.选择题
(1)若一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是()A不确定Bn-iCn-i-1Dn-i+1【解答】D【分析】此时,输出序列一定是输入序列的逆序
(2)设栈S和队列Q的初始状态为空,元素e
1、e
2、e
3、e
4、e
5、e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e
2、e
4、e
3、e
6、e
5、e1,则栈S的容量至少应该是( )A6 B4 C3 D2【解答】C【分析】由于队列具有先进先出性,所以,此题中队列形同虚设,即出栈的顺序也是e
2、e
4、e
3、e
6、e
5、e1
(3)一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是()A54321B45321C43512D12345【解答】C【分析】此题有一个技巧在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元素的序号)的两个元素
(4)设计一个判别表达式中左右括号是否配对的算法,采用()数据结构最佳A顺序表B栈C队列D链表【解答】B【分析】每个右括号与它前面的最后一个没有匹配的左括号配对,因此具有后进先出性
(5)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区,该缓冲区应该是一个()结构A栈B队列C数组D线性表【解答】B【分析】先进入打印缓冲区的文件先被打印,因此具有先进先出性
(6)一个队列的入队顺序是1,2,3,4,则队列的输出顺序是()A4321B1234C1432D3241【解答】B【分析】队列的入队顺序和出队顺序总是一致的
(7)栈和队列的主要区别在于()A它们的逻辑结构不一样B它们的存储结构不一样C所包含的运算不一样D插入、删除运算的限定不一样【解答】D【分析】栈和队列的逻辑结构都是线性的,都有顺序存储和链接存储,有可能包含的运算不一样,但不是主要区别,任何数据结构在针对具体问题时包含的运算都可能不同
3.判断题
(1)栈可以作为实现过程调用的一种数据结构【解答】对只要操作满足后进先出性,都可以采用栈作为辅助数据结构
(2)在栈满的情况下不能做进栈操作,否则将产生“上溢”【解答】对
(3)在循环队列中,front指向队头元素的前一个位置,rear指向队尾元素的位置,则队满的条件是front=rear【解答】错这是队空的判定条件,在循环队列中要将队空和队满的判定条件区别开
4.设有一个栈,元素进栈的次序为A,B,C,D,E,能否得到如下出栈序列,若能,请写出操作序列,若不能,请说明原因⑴C,E,A,B,D⑵C,B,A,D,E【解答】⑴不能,因为在C、E出栈的情况下,A一定在栈中,而且在B的下面,不可能先于B出栈⑵可以,设I为进栈操作,O为入栈操作,则其操作序列为IIIOOOIOIO
5.举例说明顺序队列的“假溢出”现象【解答】假设有一个顺序队列,如图3-6所示,队尾指针rear=4,队头指针front=1,如果再有元素入队,就会产生“上溢”,此时的“上溢”又称为“假溢出”,因为队列并不是真的溢出了,存储队列的数组中还有2个存储单元空闲,其下标分别为0和
16.在操作序列push
1、push
2、pop、push
5、push
7、pop、push6之后,栈顶元素和栈底元素分别是什么?(pushk表示整数k入栈,pop表示栈顶元素出栈)【解答】栈顶元素为6,栈底元素为1其执行过程如图3-7所示7.在操作序列EnQueue
1、EnQueue
3、DeQueue、EnQueue
5、EnQueue
7、DeQueue、EnQueue9之后,队头元素和队尾元素分别是什么?(EnQueuek表示整数k入队,DeQueue表示队头元素出队)【解答】队头元素为5,队尾元素为9其执行过程如图3-8所示
8.算法设计
(1)假设以不带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针试设计相应的入队和出队的算法【解答】出队操作是在循环链表的头部进行,相当于删除开始结点,而入队操作是在循环链表的尾部进行,相当于在终端结点之后插入一个结点由于循环链表不带头结点,需要处理空表的特殊情况入队算法如下出队算法如下学习自测及答案1.在一个具有n个单元的顺序栈中,假定以地址低端(即下标为0的单元)作为栈底,以top作为栈顶指针,当出栈时,top的变化为()A不变Btop=0;Ctop=top-1;Dtop=top+1;【解答】C2.一个栈的入栈序列是abcde,则栈的不可能的出栈序列是()AedcbaBcdebaCdebcaDabcde【解答】C3.从栈顶指针为top的链栈中删除一个结点,用x保存被删除结点的值,则执行()Ax=top;top=top-next;Bx=top-data;Ctop=top-next;x=top-data;Dx=top-data;top=top-next;【解答】D4.对于栈和队列,无论它们采用顺序存储结构还是链接存储结构,进行插入和删除操作的时间复杂度都是()【解答】O15.如果进栈序列为A、B、C、D,则可能的出栈序列是什么?答共14种,分别是ABCD,ABDC,A___,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,___A,CDBA,DCBA6.简述队列和栈这两种数据结构的相同点和不同点【解答】相同点它们都是插入和删除操作的位置受限制的线性表不同点栈是限定仅在表尾进行插入和删除的线性表,是后进先出的线性表,而队列是限定在表的一端进行插入,在另一端进行删除的线性表,是先进先出的线性表
7.设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出【解答】算法基于原理N=Ndivd×d+Nmodd(div为整除运算,mod为求余运算)8.假设一个算术表达式中可以包含三种括号圆括号“(”和“)”,方括号“[”和“]”以及花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用编写算法判断给定表达式中所含括号是否配对出现【解答】假设表达式已存入字符数组A[n]中,具体算法如下第4章串
1.填空1串是一种特殊的线性表,其特殊性体现在(数据元素的类型是一个字符)2两个串相等的充分必要条件是(长度相同且对应位置的字符相等)3空格串是指__1__,其长度等于___2__4一个字符串中________称为该串的子串5INDEX(‘DATASTRUCTURE’,‘STR’)=___5___6设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为__On+m__7设T和P是两个给定的串,在T中寻找等于P的子串的过程称为____,又称P为____8已知U=‘xyxyxyxxyxy’;t=‘xxy’;ASSIGN(S,U);ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1));ASSIGN(m,‘ww’)求REPLA__(S,V,m)=__‘xyxyxywwy’______9实现字符串拷贝的函数strcpy为voidstrcpychar*schar*t/*copyttos*/{while__*s++=*t++__;}10下列程序判断字符串s是否对称,对称则返回1,否则返回0;如fabba返回1,fabab返回0;intf1_chars[]_{inti=0j=0;whiles[j]2_j++_______;forj--;ijs[i]==s[j];i++j--;return3___i=j____}11设S=I_am_a_teacther,其长度为
(15)
2.选择题1设有两个串p和q,求q在p中首次出现的位置的运算称作(B)A连接B模式匹配C求子串D求串长2下面关于串的的叙述中,哪一个是不正确的?(B)A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存储3若串S1=‘ABCDEFG’S2=‘9__8’S3=‘###’S4=‘012345’执行concatrepla__S1substrS1lengthS2lengthS3S3substrS4indexS2‘8’lengthS2其结果为(E)A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###2345E.ABC###G1234F.ABCD###1234G.ABC###012344设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为(C)A.求子串B.联接C.匹配D.求串长5若串S=’software’其子串的数目是(B)A.8B.37C.36D.96设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为(D)A.2n-1B.n2C.n2/2+n/2D.n2/2+n/2-1E.n2/2-n/2-1F.其他情况7串的长度是指(B)A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数
3.判断题1空串与空格串是相同的【解答】错空串的长度为零,而空格串的长度不为0,其长度是串中空格的个数4.空串和空格串有何区别?串中的空格符有何意义?空串在串处理中有何作用?【解答】不含任何字符的串称为空串,其长度为零仅含空格的串称为空格串,它的长度为串中空格符的个数串中的空格符可用来分隔一般的字符,便于人们识别和阅读,但计算串长时应包括这些空格符空串在串处理中可作为任意串的子串
5.算法设计
(1)用顺序存储结构存储串S,编写算法删除S中第i个字符开始的连续j个字符【解答】先判断串S中要删除的内容是否存在,若存在,则将第i+j-1之后的字符前移j个位置算法如下voiddelchars{}intiintj{ifi+js
[0]{fork=I;k+j=s
[0];k++s[k]=s[s+j];s
[0]=s
[0]-1}}
(2)对于采用顺序存储结构的串S,编写一个函数删除其值等于ch的所有字符【解答】从后向前删除值为ch的所有元素,这样所有__的元素中没有值为ch的元素,能减少__元素的次数,提高算法的效率算法如下voiddelchars[]charch{fori=1j=1;j=s
[0];j++if(s[j]!=ch){s[i]=s[j];i++;}s
[0]=i-1;}}第6章树和二叉树
1.填空题⑴树是n(n≥0)结点的有限__,在一棵非空树中,有()个根结点,其余的结点分成m(m>0)个()的__,每个__都是根结点的子树【解答】有且仅有一个,互不相交⑵树中某结点的子树的个数称为该结点的(),子树的根结点称为该结点的(),该结点称为其子树根结点的()【解答】度,孩子,双亲⑶一棵二叉树的第i(i≥1)层最多有()个结点;一棵有n(n0)个结点的满二叉树共有()个叶子结点和()个非终端结点【解答】2i-1,n+1/2,n-1/2【分析】设满二叉树中叶子结点的个数为n0,度为2的结点个数为n2,由于满二叉树中不存在度为1的结点,所以n=n0+n2;由二叉树的性质n0=n2+1,得n0=n+1/2,n2=n-1/2⑷设高度为h的二叉树上只有度为0和度为2的结点,该二叉树的结点数可能达到的最大值是(),最小值是()【解答】2h-1,2h-1【分析】最小结点个数的情况是第1层有1个结点,其他层上都只有2个结点5具有100个结点的完全二叉树的叶子结点数为()【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100,其双亲即最后一个分支结点的编号为50,也就是说,从编号51开始均为叶子⑹已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点则该树中有()个叶子结点【解答】12【分析】根据二叉树性质3的证明过程,有n0=n2+2n3+1(n
0、n
2、n3分别为叶子结点、度为2的结点和度为3的结点的个数)⑺某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是___AFGE,则其后序遍历序列是()【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来⑻在具有n个结点的二叉链表中,共有()个指针域,其中()个指针域用于指向其左右孩子,剩下的()个指针域则是空的【解答】2n,n-1,n+1⑼在有n个叶子的哈夫曼树中,叶子结点总数为(),分支结点总数为()【解答】n,n-1【分析】n-1个分支结点是经过n-1次合并后得到的
2.选择题⑴如果结点A有3个兄弟,B是A的双亲,则结点B的度是( )A1B2C3D4【解答】D⑵设二叉树有n个结点,则其深度为()An-1BnC+1D不能确定【解答】D【分析】此题并没有指明是完全二叉树,则其深度最多是n,最少是+1⑶二叉树的前序序列和后序序列正好相反,则该二叉树一定是()的二叉树A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子【解答】B【分析】此题注意是序列正好相反,则左斜树和右斜树均满足条件4深度为k的完全二叉树至少有()个结点,至多有()个结点,具有n个结点的完全二叉树按层序从1开始编号,则编号最小的叶子的序号是()A2k-2+1B2k-1C2k-1D2k–1-1E2k+1F2k+1-1G2k-1+1H2k【解答】B,C,A【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点,最多的情况是满二叉树,编号最小的叶子应该是在结点数最少的情况下,叶子结点的编号⑸一个高度为h的满二叉树共有n个结点,其中有m个叶子结点,则有( )成立An=h+mBh+m=2nCm=h-1Dn=2m-1【解答】D【分析】满二叉树中没有度为1的结点,所以有m个叶子结点,则度为2的结点个数为m-1⑹任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序()A肯定不发生改变B肯定发生改变C不能确定D有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树⑺设森林中有4棵树,树中结点的个数依次为n
1、n
2、n
3、n4,则把森林转换成二叉树后,其根结点的右子树上有()个结点,根结点的左子树上有()个结点An1-1Bn1Cn1+n2+n3Dn2+n3+n4【解答】D,A【分析】由森林转换的二叉树中,根结点即为第一棵树的根结点,根结点的左子树是由第一棵树中除了根结点以外其余结点组成的,根结点的右子树是由森林中除第一棵树外其他树转换来的8讨论树、森林和二叉树的关系,目的是为了()A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转换成二叉树D体现一种技巧,没有什么实际意义【解答】B
3.判断题1在二叉树的前序遍历序列中,任意一个结点均处在其子女的前面【解答】对由前序遍历的操作定义可知2二叉树是度为2的树【解答】错二叉树和树是两种不同的树结构,例如,左斜树是一棵二叉树,但它的度为13由树转换成二叉树,其根结点的右子树总是空的【解答】对因为根结点无兄弟结点4用一维数组存储二叉树时,总是以前序遍历存储结点【解答】错二叉树的顺序存储结构是按层序存储的,一般适合存储完全二叉树4.证明对任一满二叉树,其分枝数B=2n0-1(其中,n0为终端结点数)【解答】因为在满二叉树中没有度为1的结点,所以有n=n0+n2设B为树中分枝数,则n=B+1所以B=n0+n2-1再由二叉树性质n0=n2+1代入上式有B=n0+n0-1-1=2n0-15.已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,……,__个度为m的结点,问该树__有多少个叶子结点?【解答】设该树的总结点数为n,则n=n0+n1+n2+……+__又n=分枝数+1=0×n0+1×n1+2×n2+……+m×__+1由上述两式可得n0=n2+2n3+……+m-1__+16.已知二叉树的中序和后序序列分别为CBEDAFIGH和__DBIFHGA,试构造该二叉树【解答】二叉树的构造过程如图5-12所示7.对给定的一组权值W=(5,2,9,11,8,3,7),试构造相应的哈夫曼树,并计算它的带权路径长度【解答】构造的哈夫曼树如图5-13所示树的带权路径长度为WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1208.已知某字符串S__有8种字符,各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98,所以,该字符串的编码长度至少为98位 9.算法设计⑴设计算法求二叉树的结点个数【解答】本算法不是要打印每个结点的值,而是求出结点的个数所以可将遍历算法中的“访问”操作改为“计数操作”,将结点的数目累加到一个全局变量中,每个结点累加一次即完成了结点个数的求解具体算法如下StatusNumberOfNodeBiTreeTintn//求二叉树结点个数,进入函数之前n初始化为0{ifT{n++;NumberOfNodeT-lchildn;NumberOfNodeT-rchildn;returnOK;}returnOK;}⑵设计算法按前序次序打印二叉树中的叶子结点【解答】本算法的要求与前序遍历算法既有相同之处,又有不同之处相同之处是打印次序均为前序,不同之处是此处不是打印每个结点的值,而是打印出其中的叶子结点,即为有条件打印为此,将前序遍历算法中的访问操作改为条件打印即可算法如下StatusPrinterLeafBiTreeT//打印二叉树叶子结点{ifT{ifT-lchild==NULLT-rchild==NULLprintT-data;PrinterLeafT-lchild;PrinterLeafT-rchild;returnOK;}returnOK;} ⑶设计算法求二叉树的深度【解答】当二叉树为空时,深度为0;若二叉树不为空,深度应是其左右子树深度的最大值加1,而其左右子树深度的求解又可通过递归调用本算法来完成具体算法如下 intDepthOfTreeBiTreeT//求二叉树的深度{intldrd;ifT{ld=DepthOfTreeT-lchild;//求左子树的深度rd=DepthOfTreeT-rchild;//求右子树的深度returnldrdld+1:rd+1;}elsereturn0;}学习自测及答案1.前序遍历和中序遍历结果相同的二叉树是()A根结点无左孩子的二叉树B根结点无右孩子的二叉树C所有结点只有左子树的二叉树D所有结点只有右子树的二叉树【解答】D2.由权值为{38625}的叶子结点生成一棵哈夫曼树,其带权路径长度为()A24B48C53D72【解答】C3.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A
[1]~A[n]中,结点A[i]若有左子树,则左子树的根结点是() AA[2i-1]BA[2i+1]CA[i/2]DA[2i]【解答】D4.对任何一棵二叉树T,如果其终端结点的个数为n0,度为2的结点个数为n2,则()An0=n2-1Bn0=n2Cn0=n2+1D没有规律【解答】C5.对于完全二叉树中的任一结点,若其右分支下的子孙的最大层次为h,则其左分支下的子孙的最大层次为()AhBh+1Ch或h+1D任意【解答】C6.假定一棵度为3的树中结点数为50,则其最小高度应为A3B4C5D6【解答】C7.在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是()【解答】8.现有按前序遍历二叉树的结果ABC,问有哪几种不同的二叉树可以得到这一结果?【解答】共有5种二叉树可以得到这一结果,如图5-15所示 9.将下面图5-16所示的树转换为二叉树,图5-17所示的二叉树转换为树或森林【解答】图5-16所示树转换的二叉树如图5-18所示,图5-17所示二叉树转换的森林如图5-19所示 第7章图
1.填空题
(1)设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边【解答】0,nn-1/2,0,nn-1【分析】图的顶点__是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边
(2)任何连通图的连通分量只有一个,即是()【解答】其自身
(3)图的存储结构主要有两种,分别是()和()【解答】邻接矩阵,邻接表【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等
(4)已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是()【解答】求第j列的所有元素之和
(5)有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的()【解答】出度
(6)如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列【解答】回路
(7)在一个有向图中,若存在弧、、,则在其拓扑序列中,顶点vivjvk的相对次序为()【解答】vivjvk【分析】对由顶点vivjvk组成的图进行拓扑排序
2.选择题⑴在一个无向图中,所有顶点的度数之和等于所有边数的()倍A1/2B1C2D4【解答】C【分析】设无向图中含有n个顶点e条边,则⑵n个顶点的强连通图至少有( )条边,其形状是()AnBn+1Cn-1Dn×n-1E无回路 F有回路 G环状 H树状【解答】A,G⑶含n个顶点的连通图中的任意一条简单路径,其长度不可能超过()A1Bn/2Cn-1Dn【解答】C【分析】若超过n-1,则路径中必存在重复的顶点⑷对于一个具有n个顶点的无向图,若采用邻接矩阵存储,则该矩阵的大小是()AnBn-12Cn-1Dn2【解答】D⑸图的生成树( ),n个顶点的生成树有()条边A唯一 B不唯一 C唯一性不能确定DnEn+1Fn-1【解答】C,F⑹设无向图G=VE和G=VE,如果G是G的生成树,则下面的说法中错误的是()AG为G的子图BG为G的连通分量CG为G的极小连通子图且V=VDG是G的一个无环子图【解答】B【分析】连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上,所以,连通分量中可能存在回路⑺G是一个非连通无向图,共有28条边,则该图至少有()个顶点A6B7C8D9【解答】D【分析】n个顶点的无向图中,边数e≤nn-1/2,将e=28代入,有n≥8,现已知无向图非连通,则n=9⑻最小生成树指的是()A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图【解答】C9下面关于工程计划的AOE网的叙述中,不正确的是()A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成,那么整个工程将会提前完成C所有的关键活动都提前完成,那么整个工程将会提前完成D某些关键活动若提前完成,那么整个工程将会提前完【解答】B【分析】AOE网中的关键路径可能不止一条,如果某一个关键活动提前完成,还不能提前整个工程,而必须同时提高在几条关键路径上的关键活动
3.判断题
(1)一个有向图的邻接表和逆邻接表中的结点个数一定相等【解答】对邻接表和逆邻接表的区别仅在于出边和入边,边表中的结点个数都等于有向图中边的个数
(2)用邻接矩阵存储图,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关【解答】对邻接矩阵的空间复杂度为On2,与边的个数无关
(3)无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的【解答】错有向图的邻接矩阵不一定对称,例如有向完全图的邻接矩阵就是对称的
(4)对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点【解答】错只有连通图从某顶点出发进行一次遍历,可访问图的所有顶点
(5)在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧【解答】错只能说明从顶点a到顶点b有一条路径
(6)在AOE网中一定只有一条关键路径【解答】错AOE网中可能有不止一条关键路径,他们的路径长度相同4.n个顶点的无向图,采用邻接表存储,回答下列问题⑴图中有多少条边?⑵任意两个顶点i和j是否有边相连?⑶任意一个顶点的度是多少【解答】⑴边表中的结点个数之和除以2⑵第i个边表中是否含有结点j⑶该顶点所对应的边表中所含结点个数5.n个顶点的无向图,采用邻接矩阵存储,回答下列问题⑴图中有多少条边?⑵任意两个顶点i和j是否有边相连?⑶任意一个顶点的度是多少?【解答】⑴邻接矩阵中非零元素个数的总和除以2⑵当邻接矩阵A中A[i][j]=1(或A[j][i]=1)时,表示两顶点之间有边相连⑶计算邻接矩阵上该顶点对应的行上非零元素的个数6.已知一个连通图如图6-6所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列【解答】邻接矩阵表示如下深度优先遍历序列为v1v2v3v5v4v6广度优先遍历序列为v1v2v4v6v3v5邻接表表示如下7.图6-7所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树【解答】按Prim算法求最小生成树的过程如下按Kruskal算法求最小生成树的过程如下8.对于图6-8所示的带权有向图,求从源点v1到其他各顶点的最短路径【解答】从源点v1到其他各顶点的最短路径如下表所示源点终点最短路径最短路径长度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v3259.如图6-9所示的有向网图,利用Dijkstra算法求从顶点v1到其他各顶点的最短路径【解答】从源点v1到其他各顶点的最短路径如下表所示源点终点最短路径最短路径长度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v
44510.算法设计
(1)设计算法,将一个无向图的邻接矩阵转换为邻接表【解答】先设置一个空的邻接表,然后在邻接矩阵上查找值不为零的元素,找到后在邻接表的对应单链表中插入相应的边表结点邻接矩阵存储结构定义如下constint__xSize=10;templatestructAdj__trix{Tvertex[__xSize];//存放图中顶点的数组intarc[__xSize][__xSize];//存放图中边的数组intvertexNumarcNum;//图的顶点数和边数};邻接表存储结构定义如下constint__xSize=10;structArcNode//定义边表结点{intadjvex;//邻接点域ArcNode*next;};templatestructVertexNode//定义顶点表结点{Tvertex;ArcNode*firstedge;};structAdjList{VertexNodeadjlist[__xSize];intvertexNumarcNum;//图的顶点数和边数};具体算法如下
(2)设计算法,将一个无向图的邻接表转换成邻接矩阵【解答】在邻接表上顺序地取每个边表中的结点,将邻接矩阵中对应单元的值置为1邻接矩阵和邻接表的存储结构定义与上题相同具体算法如下
(3)设计算法,计算图中出度为零的顶点个数【解答】在有向图的邻接矩阵中,一行对应一个顶点,每行的非零元素的个数等于对应顶点的出度因此,当某行非零元素的个数为零时,则对应顶点的出度为零据此,从第一行开始,查找每行的非零元素个数是否为零,若是则计数器加1具体算法如下
(4)已知一个有向图的邻接表,编写算法建立其逆邻接表【解答】在有向图中,若邻接表中顶点vi有邻接点vj,在逆邻接表中vj一定有邻接点vi,由此得到本题算法思路首先将逆邻接表的表头结点firstedge域置空,然后逐行将表头结点的邻接点进行转化学习自测及答案1.某无向图的邻接矩阵A=,可以看出,该图共有()个顶点A3B6C9D以上答案均不正确【解答】A2.无向图的邻接矩阵是一个(),有向图的邻接矩阵是一个()A上三角矩阵B下三角矩阵C对称矩阵D无规律【解答】C,D3.下列命题正确的是()A一个图的邻接矩阵表示是唯一的,邻接表表示也唯一B一个图的邻接矩阵表示是唯一的,邻接表表示不唯一C一个图的邻接矩阵表示不唯一的,邻接表表示是唯一D一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一【解答】B
4.在一个具有n个顶点的有向完全图中包含有()条边Ann-1/2Bnn-1Cnn+1/2Dn2【解答】B5.n个顶点的连通图用邻接矩阵表示时,该矩阵至少有()个非零元素【解答】2n-16.表示一个有100个顶点,1000条边的有向图的邻接矩阵有()个非零矩阵元素【解答】
10007.关键路径是AOE网中()A从源点到终点的最长路径B从源点到终点的最长路径C最长的回路 D最短的回路【解答】A
8.已知无向图G的邻接表如图6-10所示,分别写出从顶点1出发的深度遍历和广度遍历序列,并画出相应的生成树【解答】深度优先遍历序列为1,2,3,4,5,6对应的生成树为广度优先遍历序列为1,2,4,3,5,6对应的生成树为
9.已知已个AOV网如图6-11所示,写出所有拓扑序列【解答】拓扑序列为v0v1v5v2v3v6v
4、v0v1v5v2v6v3v
4、v0v1v5v6v2v3v4第9章查找
1.填空题⑴顺序查找技术适合于存储结构为()的线性表,而折半查找技术适用于存储结构为()的线性表,并且表中的元素必须是()【解答】顺序存储和链接存储,顺序存储,按关键码有序⑵设有一个已按各元素值排好序的线性表,长度为125,用折半查找与给定值相等的元素,若查找成功,则至少需要比较()次,至多需比较()次【解答】1,7【分析】在折半查找判定树中,查找成功的情况下,和根结点的比较次数最少,为1次,最多不超过判定树的深度⑶对于数列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定每个结点的查找概率相同,若用顺序存储结构__该数列,则查找一个数的平均比较次数为()若按二叉排序树__该数列,则查找一个数的平均比较次数为()【解答】8,59/15【分析】根据数列将二叉排序树画出,将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数,即为二叉排序树的平均查找长度⑷长度为20的有序表采用折半查找,共有()个元素的查找长度为3【解答】4【分析】在折半查找判定树中,第3层共有4个结点⑸假定一个数列{25,43,62,31,48,56},采用的散列函数为Hk=kmod7,则元素48的同义词是()【解答】62【分析】H48=H62=6⑹在散列技术中,处理冲突的两种主要方法是( )和( )【解答】开放定址法,拉链法⑺在各种查找方法中,平均查找长度与结点个数无关的查找方法是()【解答】散列查找【分析】散列表的平均查找长度是装填因子的函数,而不是记录个数n的函数⑻与其他方法相比,散列查找法的特点是()【解答】通过关键码计算记录的存储地址,并进行一定的比较
2.选择题⑴静态查找与动态查找的根本区别在于()A它们的逻辑结构不一样 B施加在其上的操作不同C所包含的数据元素的类型不一样 D存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作,而动态查找涉及插入和删除操作⑵有一个按元素值排好序的顺序表(长度大于2),分别用顺序查找和折半查找与给定值相等的元素,比较次数分别是s和b,在查找成功的情况下,s和b的关系是();在查找不成功的情况下,s和b的关系是()As=bBsbCs【解答】D,D【分析】此题没有指明是平均性能例如,在有序表中查找最大元素,则顺序查找比折半查找快,而平均性能折半查找要优于顺序查找,查找不成功的情况也类似⑶长度为12的有序表采用顺序存储结构,采用折半查找技术,在等概率情况下,查找成功时的平均查找长度是(),查找失败时的平均查找长度是()A37/12B62/13C39/12D49/13【解答】A,B【分析】画出长度为12的折半查找判定树,判定树中有12个内结点和13个外结点⑷用n个键值构造一棵二叉排序树,其最低高度为()An/2BnClog2nDlog2n+1【解答】D【分析】二叉排序树的最低高度与完全二叉树的高度相同⑸二叉排序树中,最小值结点的()A左指针一定为空B右指针一定为空C左、右指针均为空D左、右指针均不为空【解答】A【分析】在二叉排序树中,值最小的结点一定是中序遍历序列中第一个被访问的结点,即二叉树的最左下结点⑹散列技术中的冲突指的是()A两个元素具有相同的序号B两个元素的键值不同,而其他属性相同C数据元素过多D不同键值的元素对应于相同的存储地址【解答】D⑺设散列表表长m=14,散列函数Hk=kmod11表中已有
15、
38、
61、84四个元素,如果用线性探侧法处理冲突,则元素49的存储地址是()A8B3C5D9【解答】A【分析】元素
15、
38、
61、84分别存储在
4、
5、
6、7单元,而元素49的散列地址为5,发生冲突,向后探测3个单元,其存储地址为8⑻在采用线性探测法处理冲突所构成的闭散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些位置的键值()A一定都是同义词B一定都不是同义词C不一定都是同义词D都相同【解答】C【分析】采用线性探测法处理冲突会产生堆积,即非同义词争夺同一个后继地址
3.判断题⑴二叉排序树的充要条件是任一结点的值均大于其左孩子的值,小于其右孩子的值【解答】错分析二叉排序树的定义,是左子树上的所有结点的值都小于根结点的值,右子树上的所有结点的值都大于根结点的值例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值,小于其右孩子的值,但不是二叉排序树⑵二叉排序树的查找和折半查找的时间性能相同【解答】错二叉排序树的查找性能在最好情况和折半查找相同⑶若二叉排序树中关键码互不相同,则其中最小元素和最大元素一定是叶子结点【解答】错在二叉排序树中,最小元素所在结点一定是中序遍历序列中第一个被访问的结点,即是二叉树的最左下结点,但可能有右子树最大元素所在结点一定是中序遍历序列中最后一个被访问的结点,即是二叉树的最右下结点,但可能有左子树如图7-8所示,5是最小元素,25是最大元素,但5和25都不是叶子结点⑷散列技术的查找效率主要取决于散列函数和处理冲突的方法【解答】错更重要的取决于装填因子,散列表的平均查找长度是装填因子的函数⑸当装填因子小于1时,向散列表中存储元素时不会引起冲突【解答】错装填因子越小,只能说明发生冲突的可能性越小4.分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码e和g的过程【解答】查找关键码e的过程如图7-9所示,查找关键码g的过程如图7-10所示5.画出长度为10的折半查找判定树,并求等概率时查找成功和不成功的平均查找长度【解答】参见
7.
2.16.将数列(24,15,38,27,121,76,130)的各元素依次插入一棵初始为空的二叉排序树中,请画出最后的结果并求等概率情况下查找成功的平均查找长度【解答】二叉排序树如图7-11所示,其平均查找长度=1+2×2+3×2+4×2=19/77.一棵二叉排序树的结构如图7-12所示,结点的值为1~8,请标出各结点的值【解答】二叉排序树中各结点的值如图7-13所示8.已知散列函数Hk=kmod12,键值序列为2537524384991201526117082,采用拉链法处理冲突,试构造开散列表,并计算查找成功的平均查找长度【解答】H25=1H37=1H52=4H43=7H84=0H99=3H120=0H15=3H26=2H11=11H70=10H82=10构造的开散列表如下平均查找长度ASL=8×1+4×2/12=16/
129.算法设计⑴设计顺序查找算法,将哨兵设在下标高端【解答】将哨兵设置在下标高端,表示从数组的低端开始查找,在查找不成功的情况下,算法自动在哨兵处终止具体算法如下⑵编写算法求给定结点在二叉排序树中所在的层数【解答】根据题目要求采用递归方法,从根结点开始查找结点p,若待查结点是根结点,则深度为1,否则到左子树(或右子树)上去找,查找深度加1具体算法如下⑶编写算法,在二叉排序树上找出任意两个不同结点的最近公共祖先【解答】设两个结点分别为A和B,根据题目要求分下面情况讨论⑴若A为根结点,则A为公共祖先;⑵若A-datadata且root-datadata,root为公共祖先;⑶若A-datadata且B-datadata,则到左子树查找;⑷若A-dataroot-data且B-dataroot-data,则到右子树查找具体算法如下⑷设计算法判定一棵二叉树是否为二叉排序树【解答】对二叉排序树来讲,其中序遍历序列为一个递增序列因此,对给定二叉树进行中序遍历,如果始终能够保证前一个值比后一个值小,则说明该二叉树是二叉排序树具体算法如下学习自测及答案1.已知一个有序表为(12,18,24,35,47,50,62,83,90,115,134),当折半查找值为90的元素时,经过()次比较后查找成功A2B3C4D5【解答】A2.已知10个元素(54,28,16,73,62,95,60,26,43),按照依次插入的方法生成一棵二叉排序树,查找值为62的结点所需比较次数为()A2B3C4D5【解答】B3.已知数据元素为(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树,则该树的深度为()A4B5C6D7【解答】B4.按()遍历二叉排序树得到的序列是一个有序序列A前序B中序C后序D层次【解答】B5.将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T中,则T与T是相同的,这种说法是否正确?【解答】正确
6.一棵高度为h的平衡二叉树,最少含有个结点A2hB2h-1C2h+1D2h-1【解答】D7.在散列函数Hk=kmodm中,一般来讲,m应取()A奇数B偶数C素数D充分大的数【解答】C8.已知关键码序列为(JanFeb__rApr__yJunJulAugSepOctNovDec),散列表的地址空间为0~16,设散列函数为Hx=,其中i为关键码中第一个字母在字母表中的序号,采用线性探测法和链地址法处理冲突,试分别构造散列表,并求等概率情况下查找成功的平均查找长度【解答】HJan=10/2=5HFeb=6/2=3H__r=13/2=6HApr=1/2=0H__y=13/2=6HJun=10/25HJul=10/25HAug=1/2=0HSep=19/2=8HOct=15/2=7HNov=14/2=7HDec=4/2=2采用线性探测法处理冲突,得到的闭散列表如下平均查找长度=1+1+1+1+2+4+5+2+3+5+6+1/12=32/12采用链地址法处理冲突,得到的开散列表如下平均查找长度=1×7+2×4+3×1/12=18/
129.试推导含有12个结点的平衡二叉树的最大深度,并画出以棵这样的树【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目,则F1=1,F2=2,…,Fn=Fn-2+Fn-1+1含有12个结点的平衡二叉树的最大深度为5,例如第9章排序
1.填空题⑴排序的主要目的是为了以后对已排序的数据元素进行()【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率⑵对n个元素进行起泡排序,在()情况下比较的次数最少,其比较次数为()在()情况下比较次数最多,其比较次数为()【解答】正序,n-1,反序,nn-1/2⑶对一组记录
(543896231572604583)进行直接插入排序,当把第7个记录60插入到有序表时,为寻找插入位置需比较()次【解答】3【分析】当把第7个记录60插入到有序表时,该有序表中有2个记录大于60⑹利用简单选择排序对n个记录进行排序,最坏情况下,记录交换的次数为()【解答】n-1⑺如果要将序列(50,16,23,68,94,70,73)建成堆,只需把16与()交换【解答】50⑻对于键值序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从键值为()的结点开始【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点
2.选择题⑴下述排序方法中,比较次数与待排序记录的初始状态无关的是()A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为On2,归并排序在最好、最坏、平均情况下的时间性能均为Onlog2n⑵下列序列中,()是执行第一趟快速排序的结果A[da,ax,eb,de,bb]ff[ha,__]B[cd,eb,ax,da]ff[ha,__,bb]C[__,ax,eb,cd,bb]ff[da,ha]D[ax,bb,cd,da]ff[eb,__,ha]【解答】A【分析】此题需要按字典序比较,前半区间中的所有元素都应小于ff,后半区间中的所有元素都应大于ff⑶对初始状态为递增有序的序列进行排序,最省时间的是(),最费时间的是()已知待排序序列中每个元素距其最终位置不远,则采用()方法最节省时间A堆排序B插入排序C快速排序D直接选择排序【解答】B,C,B【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序⑷堆的形状是一棵()A二叉排序树B满二叉树C完全二叉树D判定树【解答】C【分析】从逻辑结构的角度来看,堆实际上是一种完全二叉树的结构⑸当待排序序列基本有序或个数较小的情况下,最佳的内部排序方法是(),就平均时间而言,()最佳A直接插入排序B起泡排序C简单选择排序D快速排序【解答】A,D⑹设有5000个元素,希望用最快的速度挑选出前10个最大的,采用()方法最好A快速排序B堆排序C希尔排序D归并排序【解答】B【分析】堆排序不必将整个序列排序即可确定前若干个最大(或最小)元素⑺设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按升序排列,则()是起泡排序一趟扫描的结果,()是增量为4的希尔排序一趟扫描的结果,()二路归并排序一趟扫描的结果,()是以第一个元素为轴值的快速排序一趟扫描的结果,()是堆排序初始建堆的结果A(F,H,C,D,P,A,M,Q,R,S,Y,X)B(P,A,C,S,Q,D,F,X,R,H,M,Y)C(A,D,C,R,F,Q,M,S,Y,P,H,X)D(H,C,Q,P,A,M,S,R,D,F,X,Y)E(H,Q,C,Y,A,P,M,S,D,R,F,X)【解答】D,B,E,A,C【分析】此题需要按字典序比较,并且需要掌握各种排序方法的执行过程⑻排序的方法有很多种,()法从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上()法从未排序序列中挑选元素,并将其依次放入已排序序列的一端交换排序是对序列中元素进行一系列比较,当被比较的两元素为逆序时,进行交换;()和()是基于这类方法的两种排序方法,而()是比()效率更高的方法;()法是基于选择排序的一种方法,是完全二叉树结构的一个重要应用A选择排序B快速排序C插入排序D起泡排序E归并排序F堆排序【解答】C,A,D,B,B,D,F⑼快速排序在()情况下最不利于发挥其长处A待排序的数据量太大B待排序的数据中含有多个相同值C待排序的数据已基本有序D待排序的数据数量为奇数【解答】C【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况,各种排序方法对待排序的数据中是否含有多个相同值,待排序的数据数量为奇数或偶数都没有影响⑽()方法是从未排序序列中挑选元素,并将其放入已排序序列的一端A归并排序B插入排序C快速排序D选择排序【解答】D
3.判断题⑴如果某种排序算法是不稳定的,则该排序方法没有实际应用价值【解答】错一种排序算法适合于某种特定的数据环境,有时对排序的稳定性没有要求⑵当待排序的元素很大时,为了交换元素的位置,__元素要占用较多的时间,这是影响时间复杂性的主要因素【解答】对此时着重考虑元素的__次数⑶对n个记录的__进行快速排序,所需要的附加空间是Οn【解答】错最坏情况下是Οn⑷堆排序所需的时间与待排序的记录个数无关【解答】错堆排序最好、最坏及平均时间均为Οnlog2n,是待排序的记录个数n的函数一般来说,待排序的记录个数越多,排序所消耗的时间也就越多⑸设有键值序列(k1k2…kn),当in/2时,任何一个子序列(kiki+1…kn)一定是堆【解答】对当in/2时,kiki+1…kn均是叶子结点,所以一定是堆4.已知数据序列为12,5,9,20,6,31,24,对该数据序列进行排序,写出插入排序、起泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果【解答】用上述排序方法的每趟结果如下5.对n=7,给出快速排序一个最好情况和最坏情况的初始排列的实例【解答】最好情况4,7,5,6,3,1,2最坏情况7,6,5,4,3,2,16.判别下列序列是否为堆,如不是,按照堆排序思想把它调整为堆,用图表示建堆的过程⑴(1,5,7,25,21,8,8,42)⑵(3,9,5,8,4,17,21,6)【解答】序列⑴是堆,序列⑵不是堆,调整为堆(假设为大根堆)的过程如图8-5所示7.已知下列各种初始状态(长度为n)的元素,试问当利用直接插入排序进行排序时,至少需要进行多少次比较(要求排序后的记录由小到大顺序排列)?⑴关键码从小到大有序(key1key2…keyn)⑵关键码从大到小有序(key1key2…keyn)⑶奇数关键码顺序有序,偶数关键码顺序有序(key1key3…,key2key4…)br/⑷前半部分元素按关键码顺序有序,后半部分元素按关键码顺序有序,即(key1key2…keym,keym+1keym+2…【解答】依题意,最好情况下的比较次数即为最少比较次数⑴插入第i(2≤i≤n)个元素的比较次数为1,因此总的比较次数为1+1+……+1=n-1⑵插入第i(2≤i≤n)个元素的比较次数为i,因此总的比较次数为2+3+……+n=n-1n+2/2⑶比较次数最少的情况是所有记录关键码按升序排列,总的比较次数为n-1⑷在后半部分元素的关键码均大于前半部分元素的关键码时需要的比较次数最少,总的比较次数为n-18.算法设计⑴直接插入排序中寻找插入位置的操作可以通过折半查找来实现据此写一个改进的插入排序的算法【解答】插入排序的基本思想是每趟从无序区中取出一个元素,再按键值大小插入到有序区中对于有序区,当然可以采用折半查找来确定插入位置具体算法如下mosi__ge}⑵设待排序的记录序列用单链表作存储结构,试写出直接插入排序算法【解答】本算法采用的存储结构是带头结点的单链表首先找到元素的插入位置,然后把元素从链表中原位置删除,再插入到相应的位置处具体算法如下⑶设待排序的记录序列用单链表作存储结构,试写出简单选择排序算法【解答】参见
8.
2.2⑷对给定的序号j(1<j<n),要求在无序记录A
[1]~A[n]中找到按关键码从小到大排在第j位上的记录,试利用快速排序的划分思想设计算法实现上述查找【解答】本算法不要求将整个记录进行排序,而只进行查找第j个记录⑸写出快速排序的非递归调用算法【解答】先调用划分函数Quickpass(划分函数同教材),以确定中间位置,然后再借助栈分别对中间元素的左、右两边的区域进行快速排序⑹一个线性表中的元素为正整数或负整数设计算法将正整数和负整数分开,使线性表的前一半为负整数,后一半为正整数不要求对这些元素排序,但要求尽量减少比较次数【解答】本题的基本思想是先设置好上、下界和轴值,然后分别从线性表两端查找正数和负数,找到后进行交换,直到上下界相遇算法如下⑺已知(k1k2…kn)是堆,试写一算法将(k1k2…knkn+1)调整为堆【解答】增加一个元素应从叶子向根方向调整,假设调整为小根堆⑻给定n个记录的有序序列A[n]和m个记录的有序序列B[m],将它们归并为一个有序序列,存放在C[m+n]中,试写出这一算法【解答】采用二路归并排序中一次归并的思想,设三个参数i、j和k分别指向两个待归并的有序序列和最终有序序列的当前记录,初始时i、j分别指向两个有序序列的第一个记录,即i=1,j=1,k指向存放归并结果的位置,即k=1然后,比较i和j所指记录的关键码,取出较小者作为归并结果存入k所指位置,直至两个有序序列之一的所有记录都取完,再将另一个有序序列的剩余记录顺序送到归并后的有序序列中学习自测及答案1.评价基于比较的排序算法的时间性能,主要标准是()和()【解答】关键码的比较次数,记录的__次数
2.对n个记录组成的任意序列进行简单选择排序,所需进行的关键码间的比较次数总共为()【解答】比较次数=n-1+n-2+…+2+1=n×n-1/
23.对于一个堆,按二叉树的层序遍历可以得到一个有序序列,这种说法是否正确?【解答】错误堆的定义只规定了结点与其左右孩子结点之间的大小关系,而同一层上的结点之间并无明确的大小关系4.一组记录的关键码为{467956384084},则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为()A{403846567984}B{403846795684}C{403846845679}D{847956464038}【解答】A5.排序趟数与序列的原始状态有关的排序方法是()A直接插入排序B简单选择排序C快速排序D归并排序【解答】C
6.用直接插入排序对下面四个序列进行由小到大排序,元素比较次数最少的是()A9432409080462169B2132464080699094C3240214669949080D9069804621329440【解答】B
7.对数列
(258421471527683520)进行排序,元素序列的变化情况如下⑴258421471527683520⑵201521254727683584⑶152021253527476884⑷152021252735476884则采用的排序方法是()A希尔排序B简单选择排序C快速排序D归并排序【解答】C
8.如果只想得到一个序列中第k个最小元素之前的部分排序序列,最好采用什么排序方法?___?对于序列{57403811133448752561997},得到其第4个最小元素之前的部分序列{67911},使用所选择的排序算法时,要执行多少次比较?【解答】采用堆排序最合适,依题意可知只需取得第k个最小元素之前的排序序列时,堆排序的时间复杂度Οn+klog2n,若k≤nlog2n,则得到的时间复杂性是Οn对于上述序列得到其前4个最小元素,使用堆排序实现时,执行的比较次数如下初始建堆比较20次,得到6;第一次调整比较5次,得到7;第二次调整比较4次,得到9;第三次调整比较5次,得到119.荷兰__问题要求重新排列一个由字符RWB(R代表红色,W代表白色,B代表兰色,这都是荷兰__的颜色)构成的数组,使得所有的R都排在最前面,W排在其次,B排在最后为荷兰__问题设计一个算法,其时间性能是On【解答】设立三个参数i、j、k,其中i以前的元素全部为红色;j表示当前元素;k以后的元素全部为蓝色这样,就可以根据j的颜色,把其交换到序列的前部或后部具体算法如下
10.已知记录序列A
[1]~A[n]中的关键码各不相同,可按如__法实现计数排序另设一个数组C
[1]~C[n],对每个记录A[i],统计序列中关键码比它小的记录个数C[i],则C[i]=0的记录必为关键码最小的记录,C[i]=1的记录必为关键码次小的记录,依此类推,即按C[i]值的大小对A中记录进行重新排列试编写算法实现上述计数排序【解答】具体算法如下
11.对于记录序列A
[1]~A[n]可按如下如__法实现奇偶交换排序第一趟对所有的奇数i,将A[i]和A[i+1]进行比较,第二趟对所有的偶数i,将A[i]和A[i+1]进行比较,每次比较时若A[i]A[i+1],则将二者交换,然后重复上述排序过程,直至整个数组有序编写算法实现上述奇偶交换排序【解答】具体算法如下PAGE4。