数据结构测试长春理工大学精品课

1、数据结构测试(长春理工大学精品课)第 2 章 线性表一、选择题1. 下述 ()是顺序存储结构的优点？查看答案A.存储密度大B .插入运算方便C.删除运算方便D .可方便地用于各种逻辑结构的存储表示正确答案为 A因此顺序) 查看答案 必须占用一片连续的存储单元。 便于进行插入和删除操作。 不必占用一片连续的存储单元。 便于插入和删除操作。解释： 插入运算和删除运算对于顺序存储结构需要移动大量的数据元素, 顺序存储结构对于非线性的逻辑结构 表示比较复杂, 顺序存储结构中只需要存储数据元素, 不像链式结构除了存数据元素还要存储关系, 存储结构的存储密度比较大。收起2. 下面关于线性表的叙述中,错误的

2、是哪一个？(A. 线性表采用顺序存储，B. 线性表采用顺序存储，C. 线性表采用链接存储，D. 线性表采用链接存储， 正确答案是 B解释： 顺序存储不利于插入删除，需要移动近一半的数据元素。收起3. 线性表是具有 n 个( )的有限序列( n>0 )。查看答案A .表兀素B .字符C.数据元素D .数据项 正确答案是 C解释： 根据线性表的定义。收起)存储方)存储方式4. 若某线性表最常用的操作是存取任一指定序号的兀素和在最后进行插入和删除运算，则利用( 式最节省时间。查看答案A.顺序表B .双链表C.带头结点的双循环链表D .单循环链表 正确答案是 A解释：顺序存储结构做相应的操作时间

3、复杂度分别为0(1), 0(1), 0(1)因此是最节省时间的。收起 5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( 最节省运算时间。查看答案A. 单链表B .仅有头指针的单循环链表C.双链表D 仅有尾指针的单循环链表 正确答案是 DO(1), O(1)收起解释： 在仅有尾指针的单循环链表做相应操作的时间复杂度为 6. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( (1<=i<=n+1) 。查看答案5 / 4A. O(0)C. O(n)B. O(1)D. O(n2)正确答案是 C解释： 在顺序表的

4、第 i 个位置插入一个元素平均需移动的元素的个数是 n+（n-1）+0/（n+1）=n/2，因此算法时间复杂度为 O（n）。收起7非空的循环单链表AP->next=headCp=NILhead 的尾结点 P 满足（ ）。查看答案B P->next=NILD P=head正确答案是 A解释： 循环单链表的尾结点的后继结点应当是头结点。收起&在单链表指针为P的结点之后插入指针为 s的结点，正确的操作是：（）。查看答案 Ap->next=s;s->next=p->next; CP->next=s;P->next=s->next;B s->

5、next=p->next;p->next=s;D p->next=s->next;p->next=s;正确答案是 B解释：p结点插入前的后继应成为继链将丢失。收起s的后继，s应成为P的新后继，而且两个操作不能换位，否则P结点的后9. 链表不具有的特点是（）。查看答案A.插入、删除不需要移动元素B.可随机访问任C.不必事先估计存储空间D .所需空间与线性长度成正比元素正确答案是 B解释： 链式存储方式不能随机访问，只能采用顺序访问的方式。收起10.（1） 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第（2）静态链表中能容纳的元素个数的最大数在表定

6、义时就确定了，以后不能增加。（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ A（1），（2）C（1），（ 2）,（3）i 个元素的时间与 i 无关。）。查看答案B （ 1）D. （ 2）正确答案是 B解释： 静态链表采用数组做为存储结构， 是方便没有指针的编程语言使用， 元素的后继地址记录的是元素所在 的下标，因此和单链表一样只能采用顺序访问方式，插入删除操作只需修改相应下标不需移动元素。收起二、填空题1当线性表的元素总数基本稳定， 且很少进行插入和删除操作， 但要求以最快的速度存取线性表中的元素时， 应采用 存_ 储结构。查看答案正确答案是：顺序存储结构

7、解释： 元素总数稳定，说明很少做插入删除操作，因此采用顺序存储最合适。收起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.

8、对于一个具有 n 个结点的单链表，在给定值为 x 的结点后插入一个新结点的时间复杂度为 案。_ 查看答正确答案是: O(n)解释：查找值为x的结点，只能顺序查找，时间复杂度为0(n)收起。5.已知指针P指向单链表L中的某结点，贝M除其后继结点的语句是:。_ 查看答案正确答案是:P->next=P->next->next解释: 删除其后继只需让后继的后继成为其后继。收起6.在双向循环链表中，向P所指的结点之后插入指针f所指的结点，其操作是 查看答案正确答案是:f->next=P->next; f->Prior=P; P->next->Prior=f

9、; P->next=f;收起7.带头结点的双循环链表 L为空表的条件是:。_ 查看答案正确答案是: L->next=L && L->Prior=L个。查看答案解释: 双循环链表为空，前驱和后继都应指向头结点。收起 8. 对于双向链表 ,在两个结点之间插入一个新结点需修改的指针共 正确答案是: 4 个解释: 修改的指针分别为前一个结点的后继，后一个结点的前驱，新结点的前驱和后继。收起 9. 在双向链表结构中，若要求在 P 指针所指的结点之前插入指针为 s 所指的结点，贝需执行下列语句:S->next=P ； s->Prior= ； P->Pri

10、or=s ； =；s 查看答案正确答案是:P->Prior s->Prior->next解释: 插入后 P 的前驱成为 s， s 的前驱应是原来 P 的前驱。收起 10. 在单链表 L 中，指针 P 所指结点有后继结点的条件是:查看答案正确答案是:P->next ！ =null 收起 三、应用题1.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估 计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式 存储结构是否一定都能够克服上述三个弱点，试讨论之。查看答案 参考答案： 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指 针，时间复杂度为 0(1);其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内 存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。收起2. 下面是一算法的核心部分，试说明该算法的功能.查看答案 pre=L->next;L 是一单链表，结点有数据域 data 和指针域 nextIF (pre!=null)WHILE (pre->nex