计算机专业基础综合数据结构线性表历年真题试卷汇编1

1计算机专业基础综合数据结构（线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ）历年真题试卷汇编)分钟70.00总分：，做题时间：90(18.00)，分数：(总题数：9一、单项选择题2004【北京工业大学()。对于双向循环链表，在P指针所指的结点之后插入s指针所指结点的操作应为1.】1(3分)一、）（分数：2.00；>right=p一>right一>left=s；s一A.P一>right=s；s一>left=p；p->right；一>fight>left=p；s一>right=psB.P一>right=s；p->right一>left=s；一；一>left=s>right=-s；P一>right>left=p；s一>right=p一>right；P一C.s一√；；P一>right=s>right=p一>fight；P一>right一>left=sD.s一>left=p；s一第BA和解析：解析：双链表在p指向的结点前或结点后插入结点都可以，但是必须避免“断链”。本例p的原后继断链，没必要再浪费时间看这两个选择答案后边的其他语句。一个语句就将所指结链表不带头结点。若在指针Ppre和next，2.设双向循环链表中结点的结构有数据域data，指针域一、】【北京交通大学20063(1分)点之后插入结点S，则应执行下列()操作。【南京理工大学2005一、)】1(2分2.00）（分数：>next；一>next=p一P一>next一>pre=s；sA.P一>next=s；s一≥pre=p；；>next=p一>next>next->pre=s；s一≥pre=p；s一PB.P一>next=s；一；P一>next->pre=s；P一>next=s；>pre=pC.s一；s一>nex=p一>next√；>pre=s；P一>next=sD.s一≥pre=p；s->next=p一>next；P一>next一解析：，则依次执行的所指的结点B之间插入指针A、Cpb3.在下列双向链表中，已知指针pa指向结点A，若在】；>prior=pa一(2)pb；二、4(2分)>next=pa->next一(1)pb【语句序列可以是()。华中科技大学2006；；(4)pa->next一>prior=pb(3)pa->next=pb）（分数：2.00√A.(1)(2)(4)(3)B.(4)(3)(2)(1)C.(3)(4)(1)(2)D.(1)(4)(3)(2)√解析：4(2二、。4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()【电子科技大学2013)】【烟台大学2007】分)一、2(2分】【青岛大学分)2000五、1(22.00）（分数：√A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)解析：3(2()5.线性表的动态链表存储结构与顺序存储结构相比，优点是。【暨南大学2011一、分)】2.00（分数：）所有的操作算法实现简单A.B.便于随机存取C.便于插入与删除√D.便于节省存储器空间解析：6.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为()。【暨南大学2010一、14(2分)】（分数：2.00）A.存储结构B.逻辑结构C.链式存储结构√D.顺序存储结构解析：7.若某线性表最常用的操作是存取第i个元素及其前驱的值，则采用()存储方式节省时．间。【暨南大学2010一、5(2分)】（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表√解析：8.根据教科书中线性表的实现方法，线性表中的元素必须是()。【北京理工大学2007一、1(1分)】（分数：2.00）A.整数类型B.字符类型C.相同类型√D.结构类型解析：9.若经常需要按序号查找线性表中的数据元素，采用()比较合适。【北京理工大学2007一、2(1分)】（分数：2.00）A.顺序存储结构√B.链式存储结构C.静态链表D.链式存储结构或静态链表解析：二、填空题(总题数：22，分数：46.00)10.在单链表中设置头结点的作用是__________。【哈尔滨工业大学2000二、1(1分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针不变。参见四、1的解释。)解析：11.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__________，在给定值为x的结点后插入一个新结点的时间复杂度为__________。【哈尔滨工业大学2001一、1(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：O(1)O(n))解析：12.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成__________和__________；而又根据指针的连接方式，链表又可分成__________和__________。【西安电子科技大学1998二、4(3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：单链表，双链表，(动态)链表，静态链表)解析：13.在双向循环链表中，向p所指的结点之后插入指针入所指的结点，其操作是__________、__________、__________、__________。【中国矿业大学2000一、1(3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：f->next=p一>next；f->prior=p；p一>next-一>prior=f；p一>next=-f;)解析：14.链接存储的特点是利用__________来表示数据元素之间的逻辑关系。【中山大学1998一、1(1分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：指针)解析：15.顺序存储结构是通过__________表示元素之间的关系的；链式存储结构是通过__________表示元素之间的关系的。【北京理工大学2001七、2(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：结点物理上相邻结点指针)解析：16.对于双向链表，在两个结点之间插入一个新结点需修改的指针共__________个，单链表为__________个。【南京理工大学2000二、2(3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：42)解析：17.循环单链表的最大优点是：__________。【福州大学1998二、3(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：从任一结点出发都可访问到链表中每一个元素)解析：18.带头结点的双循环链表L中只有一个元素结点的条件是：__________。【合肥工业大学1999三、32000三、2(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：L一>next一>nex-t==-L&&L一>prior一>priorL&&L一>next!=L)解析：19.在单链表L中，指针p所指结点有后继结点的条件是：__________。【合肥工业大学2001三、3(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：p一>next!--null)解析：20.带头结点的双循环链表L为空表的条件是：__________。【北京理工大学2000二、1(2分)】【青岛大学2002三、1(2分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：L一>nex=L&&L一>priOr=L)解析：21.下面算法的功能是__________。typedefstuctnode{dadetypedata；structnode*1ink；}*Linkl．ist；voidFUN(Linklistlista，Linklistlistb){Link2．istp；for(p=lista；p一>1ink;p=p一>link);p一>1ink=1istb;}【北京航空航天大学2006一、2(1分)】）2.00（分数：__________________________________________________________________________________________正确答案：(正确答案：将链表1istb接到链表lista之后，for语句的作用是查链表lista的尾。)解析：22.已知L是有表头结点的非空循环单链表，试从下列提供的答案中选择合适的填入空格中。(1)删除P结点之后的结点语句序列是__________；(2)在P结点前插入S结点的语句序列是__________。A．P一>next=S；B．Q=P一>next；C．P一>next=S一>next；D．S一>next=P一>next；E．P一>next=Q一>next；F．Q=P；GP=Q；H．while(p一>next!=Q)p=p一>next；I．free(Q)；【西南交通大学2004】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)BEI(2)F：HDA)解析：23.有一个无头结点的单链表，结点有数据域data，指针域next，表头指针为h，通过遍历链表，将链表中所有的链接方向逆转。要求逆转后的链表的表头指针h指向原链表的最后一个结点。算法如下所示，请在空格处填入正确的语句。voidInverse(＆h){if(1))return；p=h一>next；pr=NULL；while(2))(h一>next=pr；pr=h；h=p；(3)；}h一>next=pr；}／／inverse【南京理工大学2005二、1(3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)!h／／或h==null如果表空(2)p／／或p!=null未到表尾(3)p=p一>next／／指向下一待处理结点)解析：24.在头指针为head且表长大于1的循环链表中，指针P指向表中某个结点，若__________，则*p的直接后继是尾结点。【重庆大学2005】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：p->next->next=-head)解析：设有算法：voidabc(Linklist＆H){／／链表无头结点；r=H；p=r->next；while(p){if(p一>datadata)P一>datar一>data；／／交换数据；r=p；p=P一>next；}}／／abc链表结点结构为(data，next)。（分数：4.00）(1).该算法的功能是什么?（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)本算法的功能是相邻元素比较，逆序交换，算法结束时最大元素换到表尾。)解析：?【南京理工大学2006(三)(7分)】（分数：2.00）(2).执行该算法后下面的链表有什么变化__________________________________________________________________________________________正确答案：(正确答案：执行该算法后链表的结点数据从头到尾为：12，7，10，5，9，15。)解析：25.以下程序的功能是实现带附加头结点的单链表数据结点的逆序连接，请填空完善之。voidreverse(pointerh)/*h为附加头加结点指针*/{pointerP，q；p=h->next；h一>next=NULL；while((1)){q=p；p=p->next；q一>next=h->next；h一>next=(2)；}}【西南交通大学2000一、9】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)p!=null／／或p，链表未到尾就一直作(2)q／／将当前结点作为头结点后的第一元素结点插入)解析：26.下面是用C语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用三返回逆置后的链表的头；{(1)while(q!=null)；q=L；p=nullreverse(1inklist&L){void指针，试在空缺处填入适当的语句。．q一>next=p；p=q；(2)}(3)；}【北京理工大学2001九、1(6分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)L=L一>next；／／暂存后继(2)q=L；∥待逆置结点(3)L=p；／／头指针仍为L)解析：27.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next现对链表求一阶导数，链表的头指针为ha，头结点的exp域为一1。derivative(ha){q=ha；pa=ha一>next；while((1)){if((2)){(3));free(pa);pa=((4))；)else{pa一>coef((5))；pa->exp((6))；q=((7))；}pa=((8))；}}【南京理工大学2000三、3(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)pa!=ha／／或pa->exp!=-1，链表未到尾(2)pa->exp==0／／若指数为0，即本项为常数项(3)q->next=pa->next／／删常数项(4)q／／取下一元素(5)=pa->coef*pa->exp(6)一／／指数项减1(7)pa／／前驱后移(8)pa->next／／取下一元素)解析：28.对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstructnode{intdata；structnode*next；}linknode，*link；voidInsertsort(1inkL){linkP，q，r，u；p=L一>next;(1)；while((2)){r=L;q=n->next;while((3)＆&q一>data<=p一>data){r=q；q=q一>next；}u=p一>nextj(4)；(5)；p=u；}}【北京科技大学2001二(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)L一>next=null／／置空链表，然后将原链表结点逐个插入有序表中(2)p!--null／／或p，当链表尚未到尾(3)q!=p／／查p结点在链表中的插入位置，这时q是工作指针(4)p->next=r->next／／或p一>next=q苷p结点链入链表中(5)r->next=p／／r是q的前驱，u是下个待插入结点的指针)解析：29.一线性表存储在带头结点的双向循环链表中，L为头指针。对如下算法：(1)说明该算法的功能。(2)在空缺处填写相应的语句。voidunknown(BNODETP*L)(p=L一>next；q=p一>next；r=q->next；while(q!=L){while(p!=L)＆＆(p一>data>q一>data)p=p->prior；q一>prior一>next=r；(1)；q一>next=p一>next；q一>prior=p；(2)；(3)；q=r；p=q一>prior；(4);}}【北京理工大学1999第二部分数据结构[7](8分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减(可能包括数据域值相等的结点)有序双向循环链表。(2)(1)r->prior=q->prior；／／将q结点摘下，以便插入适当位置(2)p->next->prior=q；／／(2)(3)将q结点插入(3)p->next=q；(4)r=r->next；或r=q->next；／／后移指针，再将后面结点插入适当位置)解析：30.下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后A、B保持不变，C中元素按递增排列。下面的函数append(1ast，e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A，B)实现集合运算A一B，并返回表示结果集合C的链表的首结点的地址。在执行A一B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。typedefstructnode{intelement；structnode*link；}NODE;NODE*A，*B，*C；NODE*append(NODE*la8t，inte){last一>1ink=(NODE*)malloc(sizeof(NODE))；1a8t一>1ink一>element=e；C=la8t=(NODE*)malloc；*1ast，(NODE*cNODE*B)，NODE*difference(NODE*A}；>link)一return(last(sizeof(NODE))；while(1)if(A一>elementelement){1a8t=append(last，A一>element)；A=A一>link；)elseif(2){A=A一>1ink；B=B一>link;}ELSE(3)；while(4){1ast=append(1ast，A一>element)；A=A一>link;)(5)；last=c；c=c一>link；free(last)；return(C)；}／*callform：c=difference(A，B)；*／【上海大学2000一、4(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)(A!=null&&B!--null)／／两表均未空时循环(2)A->element--B->element／／两表中相等元素不作结果元素(3)B=B一>link／／向后移动B表指针(4)(A!=null)／／或(A)将A表剩余部分放入结果表中(5)last->link=null／／置链表尾)解析：三、判断题(总题数：3，分数：6.00)31.在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。()【中南大学2003一、2(1分)】（分数：2.00）A.正确B.错误√解析：解析：必须从头指针开始，查找到尾指针所指结点的前驱结点，故操作与链表长度有关。32.循环链表不是线性表。()【南京理工大学1998二、1(2分)】（分数：2.00）A.正确B.错误√解析：33.带头结点的单循环链表中，任一结点的后继结点的指针域均不空。()【中国海洋大学2005二、7(1分)】（分数：2.00）A.正确√B.错误解析：解析：当带头结点的单循环链表为空时，谈不上“后继结点”。如果说“带头结点的单循环链表中不存在空指针”，这种叙述是正确的。