《数据结构》-数据结构试卷第二章

数据结构期末复习题及参考答案第2章线性表一、选择题1、下面关于线性表的叙述中，错误的是哪一个（）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。2、线性表是具有N个（）的有限序列（N0）。A表元素B字符C数据元素D数据项E信息项3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用最节省时间。A单链表B单循环链表C带尾指针的单循环链表D带头结点的双循环链表5、静态链表中指针表示的是（）A内存地址B数组下标C下一元素地址D左、右孩子地址6、链表不具有的特点是（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比7、长度为N的线性表，如果是顺序存储，则访问、删除某个结点的时间复杂度分别是（）和（）；如果是链式存储，则访问、删除某个结点的时间复杂度分别是（）和（）。AON,O1,O1,ONBON,O1,ON,O1CO1,O1,ON,O1DO1,ON,ON,O18、若长度为N的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为（）1LLINKQQRLINKPPLLINKRLINKQQLLINKQ；BPLLINKQPLLINKRLINKQQRLINKPQLLINKPLLINKCQRLINKPQLLINKPLLINKPLLINKRLINKQPLLINKQDQLLINKPLLINKQRLINKQPLLINKQPLLINKQ12、在单链表指针为P的结点之后插入指针为S的结点，正确的操作是（）。APNEXTSSNEXTPNEXTBSNEXTPNEXTPNEXTSCPNEXTSPNEXTSNEXTDPNEXTSNEXTPNEXTS13、对于一个头指针为HEAD的带头结点的单链表，判定该表为空表的条件是（）AHEADNULLBHEADNEXTNULLCHEADNEXTHEADDHEADNULL14、设指针变量P指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。AQPNEXT；PDATAQDATA；PNEXTQNEXT；FREEQ；BQPNEXT；QDATAPDATA；PNEXTQNEXT；FREEQ；CQPNEXT；PNEXTQNEXT；FREEQ；DQPNEXT；PDATAQDATA；FREEQ；二、填空题1、对于一个长度为N的顺序存储的线性表，在表头插入元素的时间复杂度为ON，在表尾插入元素的时间复杂度为O1。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。1、长度为N的线性表中插入一个结点，对于顺序存储和链式存储的线性表，其插入操作的时间复杂度分别是ON和O1。3、线性表L（A1,A2,AN）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_（N1）/2_。3、顺序存储的线性表中已有N个结点，插入一个新结点平均需要移动数据N/2次。4、设单链表的结点结构为DATA,NEXT，NEXT为指针域，已知指针PX指向单链表中DATA为X的结点，指针PY指向DATA为Y的新结点,若将结点Y插入结点X之后，则需要执行以下语句PYNEXTPXNEXTPXNEXTPY；5、在一个长度为N的顺序表中第I个元素（1NEXTNULL13、线性表的存储结构分为_顺序存储结构_和_链式存储结构_。14、采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。15、设单链表结点指针域为NEXT，则删除链表中指针P所指结点的直接后继的的操作是QPNEXTPNEXTQNEXTFREEQ16、设单链表的头结点的头指针为HEAD,且PREHEAD，单链表中某指针P所指结点（即P结点）的数据域为DATA，链指针域为NEXT，则在P结点之前插入S结点的操作是WHILEPRENEXTPPREPRENEXTSNEXTPPRENEXTS17、在单链表P结点之后插入S结点的操作是SNEXTPNEXTPNEXTS三、简答题1、已知顺序表LA和LB中数据元素按值非递减有序排列，归并LA和LB得到新的顺序表LC，使LC中的数据元素也按值非递减有序排列这种操作称为顺序表的归并操作。请阅读下列顺序表的归并操作算法代码，分析该算法的时间复杂度，并作简要解释。VOIDMERGELISTSQLISTLA,SQLISTLB,SQLISTPBLBELEMLCLISTSIZELCLENGTHLALENGTHLBLENGTHPCLCELEMELEMTYPEMALLOCLCLISTSIZESIZEOFELEMTYPEIFLCELEMEXITOVERFLOW/存储分配失败PA_LASTLAELEMLALENGTH1PB_LASTLBELEMLBLENGTH1WHILEPADATAPNEXTNULLIFI1HEADQPELSEQNEXTP_QP_2、下面的结构体定义了双向链表的节点结构。请分析如下程序代码，填写其中缺少的语句代码TYPEDEFSTRUCTNODEINTDATA；STRUCTNODELASTSTRUCTNODENEXTNODEVOIDDELETEONENODEHEAD,INTTARGETNODEPHEADNEXTWHILEPNULLIFPDATATARGET_PPNEXT_ELSEIFPNEXTNULLPNEXTLAST_PLAST_PLASTNEXT_PNEXTFREEP3、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首结点的关系。参考答案在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了使插入和删除等操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。首结点也就是第一元素结点，它是头结点后边的第一个结点。五、算法描述题设有一带头结点的单链表,编程将链表颠倒过来。要求不用另外的数组或结点完成。参考答案要实现带头结点的单链表的逆置，通常作法是将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。TYPEDEFSTRUCTNODEINTDATA；假定结点数据域为整型。STRUCTNODENEXT；NODE,LINKEDLIST；LINKEDLISTCREAT（）LINKEDLISTHEAD，PINTX；HEAD（LINKEDLIST）MALLOC（SIZEOF（NODE）；HEADNEXTNULL；/设置头结点/SCANF（“D”，/P