《江西理工大学《数据结构》复习题(附答案).docx》由会员分享,可在线阅读,更多相关《江西理工大学《数据结构》复习题(附答案).docx(14页珍藏版)》请在优知文库上搜索。
1、2022级数据结构习题第1章绪论,一、单项选择题:(从给定的选项中选择出一个最恰当的答案)1 .算法分析的目的是_。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 .线性表的顺序存储结构是一种A的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取3 .顺序存储设计时,存储单元的地址A_oA.一定连续B.一定不连续C.不一定连续D.部份连续,部份不连续4 .下列数据中C一是非线性数据结构。A栈B.队列C.彻鸟二叉树D.串5 .一个算法应该是B。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.6 .以下属于逻
2、辑结构的是一CoA.顺序表B.哈希表C.线性表D.单链表7 .计算机执行下面的语句时,语句S的执行频度为_DoFOR(i=l;i=i;j-)A.0(n)B.O(nlogn)C.0(n3)D.0(n2)8 .算法分析的两个主要方面是_A_oA.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D-数据复杂性和程序复杂性9 .下面说法错误的是_A.A.算法原地工作的含义是指不需要增加额外的辅助空间B.在相同的规模n下,复杂度0(n)的算法在时间上总是优丁复杂度0(2n)的算法C.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界D.同一合算法L实现语言的级别越高,执行效率就越低10
3、.一个顺序表的第一个元素的存储地址是100,每一个元素的长度为2,则第5个元素的地-OA.110B.108C.100D.12011 .从存储结构上可以把数据结构分为两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构12 .下列叙述中正确的是。A.一种逻辑数据结构只能有一种存储结构。B.数据的逻辑结构属壬线性结构,存储结构属于非线性结构。C. 一种逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率。D. 一种逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率。13 .算法的计算量的大小称为计算的OA.效率B.复杂性C
4、.现实性D.难度14 .下述昂顺下存储结构的优点?A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示15 .以下叙述中错误的是二A.算法IE确的程序最终一定会结束B.算法正确的程序可以有零个输出C算法正确的程序可以有零个输入D.算法正确的程序对于相同的输入一定有相同的结果16 .数据结构的定义为(D,S),其中D是的*九A.算法B.数据元素C.数据操作D.逻辑结构17 .执行完下列语句段后,i值为。intf(intx)return(x0)?x*f(x-l);inti;i=f(f(D);A.2B.4C.8D.无限递归18 .三个递归算法必须包括oA.递归部份B.
5、终止条件和递归部份C.迭代部份D.终止条件和迭代部份二、判断对错题:(正确的选A,错误的选B)1 .数据的逻辑结构是指数据的各数据项之间的逻辑关系。()2 .顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。()3 .记录是数据处理的最小单位。()4 .程序二定是算法。()5 .在顺序存储结构中,有时也存储数据结构中元素之间的关系。()6 .数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。()7 .递归的算法简单、易懂、容易编写,而且执行效率也高。()8 .每种数据结构都应具备三种基本运算:插入、删除和搜索。()三、应用题1 .给出圆环类的声明(内径为R,外径为R
6、J(包括求圆环面积、圆环内周长和外周长)。2 .给出等腰三角形类的声明(腰长为a,底长为b)(包括求面积与周长)。第2章线性表一、单项选择题:(从给定的选项中选择出一个最恰当的答案)1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表I2 .以下数据结构中,是线性结构。A.哈希表B.二叉树C.有向图D.串3 .设单链表中结点的结构为StrUCtnOdeElcmTypedat;astructnode*Li;nk;己知指针P所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列操作。A
7、.s-link=;pp-link=;SB.s-link=p-l;inkp-Iink=;SC.link=p-l;inkp=s;D.p-link=;ss-link=;P4 .在作进栈运算时,应先判别栈是否。A.空B.满C.上溢D.下溢5 .若栈顶指针指向栈顶元素,当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为OA.n-1B.nC.n+1D.n/26若栈采用顺序存储方式存储,现两栈共享空间VLm,topi代表第i个栈(i=l,栈2)顶,栈1的底在vl,栈2的底在Vm,若栈顶指针指向栈顶元素,则栈满的条件是oA.top2-toplI=B.topl+1=topl2JC.topltop2=
8、mD.topl=top27 .递归过程或者函数调用时,处理参数及返回地址,要用一种称为的数据结构。A.队列B.多维数组C.栈D.线性表8 .若用一个大小为6的数组来实现循环队列,且当前mar和fiwl的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,mar和fint的值分别为.IA.1和5B.2和4C.4和2D.5和19 .若进队列的序列为1,2,3,4则是一个出队列序列。A.3,2,1,4B.3,2,4,1C.4,3,2,1D.1,2,3,410 .在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算时oA.r=f-next;B.r=r-next;C.f=f-next
9、;D.f=r-next;11 .线性表(al,a2,an)以链接方式存储时,访问第i位置元素的时间复杂性为。A.0(i)B.0(1)C.O(n)D.O(i-1)12 .删除一单向链表中P指针所指向结点的后继结点,正确的操作是。A.p-ncxt=p-next-next;B.p=p-next;C.p-next=p;D.p-next-next=p-next:13 .为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的设在内存空间的两端。A.长度B.深度C.栈顶D.栈底14 .栈在中应用。A.递归调用B.子程序调用C.表达式求值D.A,B,C31.栈和队列都是OA.
10、顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构15 .在作退栈运算时应先判别栈是否。A.空B.满C.上溢D.下溢16 .若一个栈的输入序列为1,2,3,,n输出序列的第一个元素是i,则第j个输出元素是A.i-j-1B.i-jC.j-i+1D.不确定的17 .在一个链队中,假设f和份别为队首和队尾指针,则插入S所指结点的运算时一oA.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;18 .判定一个循环队列0列最多元素为m)为空的条件是。A.QU.front=(QU.rear+l)%mB
11、.QU.front!=(QU.rear+1)%mC.QU.front=QU.rearD.QU.front!=QU.rear19 .在单项循环链表head的末尾(rear指针指向)插入S指针指向的结点,正确操作是A.rear-next=s;s-next=head;B.s-next=rear;rear-next=head;C.rear=s;s-next=head;D.rear-next=s;s=head;20 .已知函数SUb(S,i,的j)功能是返回串S中从第i个字符起长度为j的子串,函数Spy(s,t)的功能为复制串t到s。若字符串S=SClENCESTUDY,则调用函数SeOPy(P,Sub
12、(S,1,7)后得到丁A.P=SCIENCEB.P=STUDYC.S=SCIENCED.S=STUDY21 .设计一个判别表达式中左,右括号是否配对浮现的算法,采用数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈22 .用链接方式存储的队列,在进行删除运算时oA.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针都不修改23 .以下算法的功能是(栈和队列的元素类型均为int。)voidalgo(StackS,inte)StackT;intd;InitS(ack(T);while(!StackEmpty(三)pop(S,d);if(d!=e)push(T
13、,d);)while(!StackEmpty(T)pop(T,d);push(S,d);IJA.删除栈S中的数据eB.判断栈S中是否存在数据eC.将栈S中的数据逆置D.将栈S中的数据放入栈T中24 .以下算法的功能(栈中的数据元素类型为int)是。voidstatusalgo(StackS)inti,n,a255;n=0;while(!StackEmpty(三)n+;Pop(S,an);)fr(i=l;inext=r;q-next=r-next;r-next=q;B.p-next=r;r-next=q;q-next=r-next;C.r-next=q;q-next=r-next;p-next=
14、r;D.r-next=q;p-next=r;q-next=r-next;28 .串的操作函数Str定义为:inlstr(char*s)dwr;*p=hsile(*!k计;+returnp-;s)W1Jstr(abcde)的返回值是iA.3B.4C.5D.629 .飞线性表相比,串的插入和删除操作的特点是oA.通常以用整体作为操作对象B.需要更多的辅助空间_斗法的时间复杂度较高涉及挪移的元素更多口30 .对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有个。A.1B,2C3D.431 .设主串长为n,模式串长为m(mwn),则在匹配失败情况下,朴素匹配算法进行的无效位移次数为。A.mB.n-mC.n-m+1D.n32 .已