线性结构总复习

《线性结构总复习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章一、填空题1是数据的基本单位，.........是具有独立含义的最小标识单位。3数据之间的关系(逻辑结构)有四种——、——、——、——。4数据的存储结构包括二、问答题什么是数据结构?什么是数据类型？叙述算法的定义与特性。3.叙述算法的时间复杂度。三、判断题(在各题后填写“J”或“X”)1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。()2.下列几种数量级从小到人的排列顺序为：0(1)、O(logn)>0(n)、O(nlogn)、0(n2)、0(n3)、0(2n)。()四、设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的

2、时间复杂度可表示为(1)(....)(2)(....)1)floatsuml(intn){/*计算1!+2!+...+n!*/p=l;sum1=0;for(i=l;i<=n;++i){p=p*i;sum1=sum1+p})/*suml*/(2)floatsum2(intn){/*计算1!+2!+...+n!♦/sum2=0;for(i=l;i<=n;++i){P=Ufor(j=l;j<=i;++j)p=p*j;sum2=sum2+p;)}/*sum2*/第二章一、判断1.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。()2•顺序表结构适宜于进行顺序存取

3、，而链农适宜于进行随机存取。()二、填空1.在单链表中，指针p所指结点为最后一个结点的条件是。2.在单链的循环链表中，指针p所指结点为最后一个结点的条件是。三、选择A・0(n)B・0(1)2•线性链表不具有的特点是()。A.随机访问C.插入与删除时不必移动元索3•线性表采用链式存储时，英地址(C・0(n2)D・O(Iog2n)B.不必事先估计所需存储空间大小D.所需空间与线性表长度成正比A必须是连续的B一定是不连续的C部分地址必须是连续的D连续与否均可以.4、下列哪一个程序片段是在链表中间插入一个结点。(假设新结点为NEW,欲插入在Pointer结点之后)ANEW->nex

4、t=PointerPointer=NEWCPointcr->ncxt=NEW->ncxtBNEW->next=Pointer->nextPointer->next=NEWD以上皆非()A.使单链表至NEW->ncxt=Pointcr5.在单链表中,增加头结点的H的是少有一结点B.标志表中首结点位置C.方便运算的实现D.说明单链表是线性表的链式存储实现6.线性表L在情况下适用于使用链式结构实现。()(A)需经常修改L中的结点值(B)需不断对L进行删除插入(C)L中含有大量的结点(D)L中结点结构复杂7、向一个冇127个元素原顺序表屮插入一个新元素并保存原來顺序不变，平均要移动

5、()个元素。A.8B、63.5C.63D、7三、算法设计1设顺序表L中的数据元索递増有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的冇序性。2分别写出算法将单链衣和顺序表就地逆用(用尽可能少的附加空间在原存储出空间内将将线性表al,a2,a3….an逆置为an...a3,a2,al)。*3删除元索递增排列的链农L中所有值相同的元索。第三章习题1.铁道进行车厢调度，回答：(1)如进站的车厢序列为123,则可能得到的出站车厢序列是什么？(2)如进站的车厢序列为123456,能否得到435612和135426的出站序列，并说明原因。(即写出以“S”表示进栈、以“X”表

6、示出栈的栈操作序列)。2.设队列中有A、B、C、D、E这5个元索，其屮队首元索•为A。如果对这个队列重复执行下列4步操作：(1)输出队首元素；(2)把队首元素值插入到队尾;(3)删除队首元索；(4)再次删除队首元索。直到队列成为空队列为止，得到输出序列：(1)A、C、E、C、C(2)A、C、E(3)A、C、E、C、C、C(4)A、C、E、C3・给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满?3.按照四则运算加、减、乘、除和幕运算(t)优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A—B*C/D+EfF4.要求循坏队列不损失一

7、个空间全部都能得到利用，设置一个标志域tag,以lag为0或1來区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。5.简述以下算法的功能(其屮栈和队列的元素类型均为int)：(1)voidproc_1(StackS){inti,n,A[255];n=0;while(!EmptyStack(S)){n++;Pop(&S,&A[nJ);}for(i=l;i<=n;i++)Push(&S,A[i]);)(2)voidproc_2(StackS,inte){StackT;inid;InitStack