您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 数据结构复习习题和答案(DOC)
第一章绪论一、单项选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和操作等的学科。①A.操作对象B.计算方法C·逻辑存储D.数据映象②A.结构B.关系C.运算.D.算法2.数据结构被形式地定义为(D,R),其中D是①的有限集合,R是D上的②有限集合。①A.算法B.数据元素C.数据操作D.逻辑结构②A.操作B.映象C、存储D.关系3.在数据结构中,从逻辑上可以把数据结构分成()。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4·算法分析的目的是①,算法分析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①,它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性6.线性表的逻辑顺序与存储顺序总是一致的,这种说法()。A.正确B.不正确7.线性表若采用链式存储结构时,要求内存中可用存储单元的地址()。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以8.数据结构通常是研究数据的()及它们之间的相互联系。A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑9.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为()。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构11.非线性结构是数据元素之间存在一种()。A.一对多关系B.多对多关系C.多对一关系D.一对一关系12.非线性结构中,每个结点()。A.无直接前趋B.只有一个直接前驱和后继C.只有一个直接前趋和个数受限制的直接后继D.有个数不受限制的直接前趋和后继13.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为()。A.时间效率B.空间效率C.硬件效率D.软件效率14.链式存储的存储结构所占存储空间()。A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针B.只有一部分,存放结点值C.只有一部分,存储表示结点间关系的指针D.分两部分,一部分存放结点值,另一部分存放结点所占单元数15.设语句x+十的时间是单位时间,则语句:for(i=l;i<=n;i++)X++;的时间复杂度为()。A.O(l)B.O(n)C.O(n2)D.O(n3)二、填空题1.数据元素之间的关系称为(结构),通常分为4种(集合)(线性结构)(树形结构)(图状结构或网状结构)。2.在线性结构中,第一个结点(无)前驱结点,其余每个结点有且只有(1)个前驱结点;最后一个结点(无)后续结点,其余每个结点有且只有(1)个后续结点。3.在树形结构中,树根结点没有(前驱)结点,其余每个结点有且只有(1)个前驱结点;叶子结点没有(后继)结点,其余每个结点的后继结点可以(多个)。4.在图形结构中,每个结点的前驱结点数和后续结点数可以(多个)。5.线性结构中元素之间存在(一对一)关系,树形结构中元素之间存在(一对多)关系,图形结构中元素之间存在(多对多)关系。6.下面程序段的时间复杂度是(O(mn))。for(i=0;in;i++)for(j=0;j<m;j++)A[i][j]=0;7.数据结构包括数据的(逻辑结构)、数据的(存储结构)。8.数据结构按逻辑结构可分为两大类,它们分别是(线性结构)和(非线性结构)。9.数据的存储结构分为(顺序存储结构)和(链式存储结构)。10.一个算法的效率可分为(时间)效率和(空间)效率。11.数据元素是数据的(基本)单位,(数据项)是数据的最小单位。12.数据对象是(性质)相同数据元素的集合。三、阅读理解题设n为正整数,利用大“O”记号,将下列程序段的执行时间表示为n的函数。x=0;for(i=l;i<n;i++)for(j=i+1;j<=n;j++)x++;答案:n(n+1)/2,即O(n2)第2章线性表一、单项选择题:1.线性表的的顺序存储结构是一种()的存储结构,线性表的链式存储结构是一种()的存储结构。A·随机存取B.顺序存取C.索引存取D.散列存取2.在以下的叙述中,正确的是()。A.线性表的顺序存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出3.不带头结点的单链表head为空的判定条件是()。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4.带头结点的单键表head为空的判定条件是()。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL5.非空的循环单链表head的尾结点(由p所指向)满足()。A.p->next==NULLB.p==NULLC.p-next==headD.p==head6.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行()。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;7.在单链表中,若p所指结点不是最后结点,在p之后插入S所指结点,则执行()。A.S->next=P;P->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;8.在一个单链表中,若删除P所指结点的后继结点,则执行()。A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->next;D.p=p->next->next9.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较()个结点。A.nB.n/2C.(n-l)/2D.(n十1)/210.在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。A.O(l)B.O(n)C.O(n2)D.O(nlog2n)11.用单链表方式存储的线性表,每个结点需要两个域,一个是数据域,另一个是()。A当前结点所在地址域B.指针域C.空指针域D.空闲域12.在具有n个结点的单链表中,实现()的操作,其算法的时间复杂度都是O(n)。A.遍历链表和求链表的第i个结点B.在地址为P的结点之后插入一个结点C.删除开始结点D.删除地址为p的结点的后继结点13.单链表的存储密度()。A.大于1B.等于1C.小于1D.不能确定14.已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为dal,则第i个结点的地址为()。A.dal+(i-l)*mB.dal+i*mC.dal-i*mD.da1+(i+1)*m二、填空题:1.在线性结构中,第一个结点(无)前驱结点,其余每个结点有且只有(1)个前驱结点;最后一个结点(无)后续结点,其余每个结点有且只有(1)个后续结点。2.单链表是(线性表)的链式存储表示。3.若数组第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(108)。4.在一个长度为n的线性表的第i个元素(1<=i<=n+1)之前插入一个元素时,需向后移动(n+1-i)个元素。5.在长度为n的线性表中删除第i个元素(1≤i≤n)时,需向前移动(n-i)个元素。6.在双向链表中,每个结点有两个指针域,一个指向(直接前驱),另一个指向(直接后继)。7.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=(p->next)和p->next=(s)的操作。8.对于一个具有n个结点的单链表,在已知P所指结点后插入一个新结点的时间复杂度是(O(1));在给定值为X的结点后插入一个新结点的时间复杂度是(O(n))。9.顺序表相对于链表的优点有(可以随机存取,存储密度高)。10.链表相对于顺序表的优点有(不需要连续的存储空间,插入和删除时不需要移动元素)。11.在n个结点的顺序表中插入和删除一个结点需平均移动大约(n/2)个结点。12.线性表的链式存储有三种,分别是(单链表)(双向链表)(循环链表)。用数组描述的线性链表称为(静态链表).13.在顺序表中访问任意一结点的时间复杂度均为(O(1)),因此,顺序表也称为(随机存取)的数据结构。14.在n个结点的单链表中要删除已知结点*p,需找到(该结点的前驱),其时间复杂度为(O(n))。15.在循环链表中,可根据任一结点的地址遍历整个链表,而单链表中需知道(头指针)才能遍历整个链表。所以,整个单链表是由(头指针)来作为唯一标识的。三、阅读理解题NODE*demol(NODE*head,NODE*p){NODE*q=head-link;while(q&&q-next!=p)q=q-link;if(q)returnq;elseprintf(“*pnotinlinklist.\n”);}第3章栈和队列一、单项选择题:1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。A.edcbaB.decbaC.dceabD.abcde。2.栈结构通常采用的两种存储结构是()。A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构3.栈的特点是(B),队列的特点是(A)。A.先进先出B.先进后出4.一个队列的入列序列是1,2,3,4,则队列的输出序列是()。A.4,3,2,lB.1,2,3,4C.l,4,3,2D.3,2,4,l5.判定一个循环队列QU(最大空间是mo)为空的条件是()。A.QU.front==QU.rearB.QU.front!=QU.rearC.QU.front==(QU.rear+l)%moD.QU.front!=(QU.rear+1)%mo6.判定一个循环队列QU(最大空间是mo)为满队列的条件是()。A.QU.front==QU.rearB.QU.front!=QU.rearC.QU.front==(QU.rear+l)%moD.QU.front!=(QU.rear+l)%mo7.循环队列用数组A[0,m-l]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front8.栈和队列的共同点是()。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点9.向一个栈顶指针为top的链栈中插入一个S所指结点时,则执行()。A.top->next=s;B.s->next=top->next;top->next=s;C.s->next=top;top=s;D.s->next=top;top=top->next;10.从一个栈顶指针为top的链栈中删除一结点时,用X保存被删结点的值,则执行().A.x=top;top=top->next;B.x=top->data;C.top=top->next;x=top->data;D.x=top->data;top=top->next11.在链队列中,设front和rear分别为队首和队尾指针,插入s所指结点的运算为()。A.front->next=s;front=s;B.rear->next=s;rear=s;C.s->next=rear;rear=s;D.s->next=front;front=s;12.在链队中,设front和rear分别为队首和队
本文标题:数据结构复习习题和答案(DOC)
链接地址:https://www.777doc.com/doc-4692912 .html