数据结构第二章测试(长春理工大学精品课)

数据结构测试（长春理工大学精品课）第2章线性表一、选择题1下述( )是顺序存储结构的优点？查看答案A存储密度大 B插入运算方便C删除运算方便 D可方便地用于各种逻辑结构的存储表示正确答案为A解释：插入运算和删除运算对于顺序存储结构需要移动大量的数据元素，顺序存储结构对于非线性的逻辑结构表示比较复杂，顺序存储结构中只需要存储数据元素，不像链式结构除了存数据元素还要存储关系，因此顺序存储结构的存储密度比较大。收起2下面关于线性表的叙述中，错误的是哪一个？（)查看答案A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。正确答案是B解释：顺序存储不利于插入删除，需要移动近一半的数据元素。收起3线性表是具有n个（）的有限序列（n0）。查看答案A表元素 B字符C数据元素 D数据项正确答案是C解释：根据线性表的定义。收起4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。查看答案A顺序表 B双链表C带头结点的双循环链表 D单循环链表正确答案是A解释：顺序存储结构做相应的操作时间复杂度分别为O(1)，O(1)，O(1)因此是最节省时间的。收起5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。查看答案A单链表B仅有头指针的单循环链表C双链表 D仅有尾指针的单循环链表正确答案是D解释：在仅有尾指针的单循环链表做相应操作的时间复杂度为O(1)，O(1)收起6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=inext=head BP-next=NILCp=NIL Dp=head正确答案是A解释：循环单链表的尾结点的后继结点应当是头结点。收起8在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。查看答案Ap-next=s;s-next=p-next; Bs-next=p-next;p-next=s;Cp-next=s;p-next=s-next; Dp-next=s-next;p-next=s;正确答案是B解释：p结点插入前的后继应成为s的后继，s应成为p的新后继，而且两个操作不能换位，否则p结点的后继链将丢失。收起9.链表不具有的特点是（）。查看答案A插入、删除不需要移动元素 B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性长度成正比正确答案是B解释：链式存储方式不能随机访问，只能采用顺序访问的方式。收起10.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）。查看答案 A（1），（2） B（1）C（1），（2）,(3) D.（2）正确答案是B解释：静态链表采用数组做为存储结构，是方便没有指针的编程语言使用，元素的后继地址记录的是元素所在的下标，因此和单链表一样只能采用顺序访问方式，插入删除操作只需修改相应下标不需移动元素。收起二、填空题1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。查看答案正确答案是：顺序存储结构解释：元素总数稳定，说明很少做插入删除操作，因此采用顺序存储最合适。收起2线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。查看答案正确答案是：（n-1）/2解释：长度为n的线性表，删除任一元素的概率为1/n，删除一个元素平均移动的元素的个数为(n-1)+(n-2)+.+0/n=(n-1)/2收起3对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_,查看答案正确答案是：O(1)解释：在已知结点的后面插元素，只需修改后继元素的指针。收起4对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为_。查看答案正确答案是：O(n)解释：查找值为x的结点，只能顺序查找，时间复杂度为O(n)收起。5.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_。查看答案正确答案是：p-next=p-next-next解释：删除其后继只需让后继的后继成为其后继。收起6 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_、_、_、_。查看答案正确答案是：f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;收起7.带头结点的双循环链表L为空表的条件是：_。查看答案正确答案是：L-next=L & L-prior=L解释：双循环链表为空，前驱和后继都应指向头结点。收起8.对于双向链表,在两个结点之间插入一个新结点需修改的指针共_个。查看答案正确答案是：4个解释：修改的指针分别为前一个结点的后继，后一个结点的前驱，新结点的前驱和后继。收起9.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：S-next=p； s-prior= _； p-prior=s； _=s；查看答案正确答案是：p-prior s-prior-next解释：插入后p的前驱成为s，s的前驱应是原来p的前驱。收起10.在单链表L中，指针p所指结点有后继结点的条件是：查看答案正确答案是：p-next！=null收起三、应用题1.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。查看答案参考答案：链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。收起2.下面是一算法的核心部分，试说明该算法的功能.查看答案pre=L-next;L是一单链表，结点有数据域data和指针域nextIF (pre!=null) WHILE (pre-next!=nul