《数据结构》-第二章VIP

习题21选择题1、线性表的顺序存储结构是一种（A）的存储结构，线性表的链式存储结构是一种（B）的存储结构。A、随机存取B、顺序存取C、索引存取D、散列存取2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（B）。A、顺序存储方式B、链式存储方式C、散列存储方式D、索引存储方式3、已知，L是一个不带头结点的单链表，P指向其中的一个结点，选择合适的语句实现在P结点的后面插入S结点的操作（B）。A、PNEXTSSNEXTPNEXTB、SNEXTPNEXTPNEXTSC、PNEXTSSNEXTPD、SNEXTPPNEXTS4、单链表中各结点之间的地址（CD）。A、必须连续B、部分地址必须连续C、不一定连续D、连续与否都可以5、在一个长度为N的顺序表中向第I个元素（0NEXTL）。23读下面的程序段，画出执行过程的示意图及所完成的功能。1、DEFINEN6VOIDMAINLISTSQLINTANINTI,ELEMINITLISTL/初始化函数FORINTJ0JDATAXSMALLOCSIZEOFLNODESDATAYLNEXTSSNEXTNULLRETURNL功能创建一个两个结点的不带头结点的单链表，两个结点的值分别为X和Y，L为单链表的头指针。24算法题1、编写在两种存储方式下，删除线性表中多余的值相同元素的算法。解顺序存储方式下VOIDDELLISTSQWHILEINEXTWHILEPNEXTNULLLNODEQPNEXTLNODERPWHILEQNULLIFQDATAPDATARNEXTQNEXTFREEQQRNEXTELSERQQQNEXTPPNEXT2、已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的奇数元素，另一个存放所的偶数元素。解VOIDFENSQLISTSQL,LISTSQFORINTI0INEXTINTN0WHILEPLNPPNEXTRETURNN4、编写删除有序单链表中元素值大于MIN并且小于MAX的全部元素的算法。如果给定的表是无序的，如何改写上面的算法。解VOIDDEL4LNODEL,ELEMTYPEMIN,ELEMTYPEMAXLNODEQ,S,PPLNEXTQLWHILEPNULLIFPNULL/表示存在大于MIN的结点，最后一个小于等于MIN的结点为Q结点WHILEPNULLIFPNULL/表示存在大于等于MAX的结点，既P结点WHILEQNEXTP/删除Q的后继结点到P的前驱结点为止的所有结点SQNEXTQNEXTSNEXTFREESELSESQNEXTQNEXTNULL/Q以后的结点全部要删除WHILESNULLPSNEXTFREESSP5、用顺序表来求集合的并集、交集和差集，也可以用链表来实现以上操作。（作为上机实践题目）INCLUDETYPEDEFINTELEMTYPEDEFINEMAXLEN100DEFINEN30STRUCTLISTSQELEMTYPEEMAXLENINTLEN/顺序表的创建算法VOIDCREATE_SQLISTSQFORI0IL1LENL3EL3LENL2EIL3LENVOIDJIAOJILISTSQL1,LISTSQL2,LISTSQFORINTI0IL2LENL3EKL1EIFORINTM0ML1LENL3EKL2EML3LENK/主函数VOIDMAINLISTSQL1,L2,L3L3LEN0INTANINTM,N,CPRINTF“请输入线性表L1的元素个数N“SCANF“D“,PRINTF“请输入线性表L1的元素N“FORINTJ0JINCLUDETYPEDEFSTRUCTLNODEINTDATALNODENEXTLINKVOIDCREATELISTLINKLNODEP,SSLNODEMALLOCSIZEOFLNODESDATA1LPSFORI2IDATAIPNEXTSPSPNEXTLVOIDDELETELISTLINK/修改结点的指针域FREEP/释放P结点所占存储空间VOIDJOSEPHUSLINKPLFORINTI1INEXTQPNEXTWHILEQNEXTPQQNEXTWHILEPNEXTPFORINTJ1JNEXTPRINTF“D,“,PDATADELETELISTL,P,QPQNEXTPRINTF“D“,PDATAPRINTF“N“VOIDMAINLINKLNULLINTM,N,SPRINTF“请输入围圈人数、报数的开始位置和报数的上限N“SCANF“D,D,D“,IFM1000|N1000PRINTF“输入值M或N不合法N“ELSEIFSNPRINTF“输入值S和N不合法N“ELSECREATELISTL,NPRINTF“N“JOSEPHUSL,S,M7、某百货公司对仓库中的库存电视进行管理时，按其价格从低到高的次序构成一个循环单链表来保存信息，每个结点包含价格、数量和指针三个域。现新到M台价格为H的电视机，编写修改原信息链表的算法。（作为上机实践题目）INCLUDEINCLUDESTRUCTELEMTYPEFLOATJIAGEINTSHULIANGSTRUCTLNODEELEMTYPEDATASTRUCTLNODENEXT/单链表的后插入创建算法VOIDRCREATELNODEL,ELEMTYPEA,INTNINTILNODEP,SPLFORI0IDATAAISNEXTPNEXTPNEXTSPS/单链表的输出算法VOIDPRINTLISTLNODELLNODEPIFLNEXTLPRINTF“单链表为空N“ELSEPLNEXTPRINTF“当前仓库中库存的电视相关信息为N“PRINTF“价格TT数量N“WHILEPNEXTLPRINTF“FT“,PDATAJIAGEPRINTF“DN“,PDATASHULIANGPPNEXTPRINTF“FT“,PDATAJIAGEPRINTF“DN“,PDATASHULIANGVOIDINSERTLNODEL,ELEMTYPEELEMLNODESSLNODEMALLOCSIZEOFLNODESDATAELEMIFLNEXTLSNEXTLNEXTLNEXTSELSELNODEPL,QLNEXTWHILEQLQQNEXTSNEXTQPNEXTS/主函数VOIDMAINLNODELINTNELEMTYPEA50,ELEMPRINTF“请输入仓库中库存的电视的台数N“SCANF“D“,PRINTF“按价格从低到