《数据结构》第1教学单元测试练习题

一、选择（60分）

1、以下说法正确的是 ( )

A、数据元素是数据的最小单位 B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合 D、数据结构是带有结构的数据元素的集合 2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作 A、条件判断 B、结点移动 C、算术表达式 D、赋值语句 3、对于顺序表的优缺点，以下说法错误的是 （ ）

A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便 D、容易造成一部分空间长期闲置而得不到充分利用

4、链表不具有的特点是：

A、可随机访问任一个元素 B、插入删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表长度成正比 5、循环链表主要优点是（ ）

A、不再需要头指针了 B、已知某个结点的位置后，能够容易找到它的直接前趋 C、从表中任一结点出发都能扫描到整个链表 D、在进行插入、删除运算时，能更好地保证链表不断开 6、以下说法正确的是

A、线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

B、线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 C、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关

D、顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动 7、以下说法错误的是 （ ）

A、求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B、顺序存储的线性表可以随机存取

C、由于顺序存储要求连续约存储区域 所以在存储管理上不够灵活 D、线性表的链式存储结构优于顺序存储结构 8、以下说法错误的是 （ ）

A、线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 B、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 C、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 D、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 9、以下说法正确的是（ ）

A、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素

B、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 C、顺序存储方式只能用于存储线性结构

D、顺序存储方式的优点是存储密度大、且插入、删除运算效率高 10、线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( ) A、每个元素都有一个直接前驱和直接后继 B、线性表中至少要有一个元素

C、表中诸元素的排列顺序必须是由小到大或由大到小的

D、除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前驱和直接后继 11、线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )

A、必需是联系的 B、部分地址必须是连续的 C、一定是不连续的 D、连续不连续都可以 12、单链表中，增加头结点的目的是为了 ( )

A、使单链表至少有一个结点 B、标示表结点中首结点的位置

第 1 页 共 3 页

C、方便运算的实现 D、说明单链表是线性表的链式存储实现 13、带头结点的单链表Head为空的判定条件是

A、Head==Null B、Head->next==NULL C、Head->next==Head 14、空的单循环链表L的尾结点*P,满足

A、P->next==NULL B、P==NULL C、P->next==L D、P==L 15、算法的时间复杂度是指（ ） A、执行算法程序所需要的时间 B、算法执行过程中所需要的基本运算次数 C、算法程序的长度 D、算法程序中的指令条数 16、算法的空间复杂度是指（ ）

A、执行算法程序所占的存储空间 B、算法程序中的指令条数 C、算法程序的长度 D、算法执行过程中所需要的存储空间 17、下列叙述中正确的是（ ）

A、线性表是线性结构 B、栈和队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构 18、数据的存储结构是指（ ）

A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据 19、下列属于线性数据结构的是( )

A、队列 B、树 C、图 D、不确定

20、单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针P指向的单链表结点之后，下面的操作序列中哪一个是正确的？( ) A、P->link = q-> link; q = p-> link; B、P-> link = q; q-> link = p-> link; C、q-> link = p-> link; p-> link =q; D、q = p-> link; p-> link = q-> link; 21、在一个单链表中，若删除p所指结点的后续结点，则执行 ( )

A、p->link=p-> link -> link; B、p=p-> link; p-> link =p-> link -> link;

C、p-> link =p-> link; D、p=p-> link -> link; 22、循环链表指( )

A、最后一个节点的指针域总是指向链表头 B、可以自由膨胀的链表 C、链表含有指向上一级节点的指针域 D、都不是

23、如果以链表作为栈的存储结构,则退栈操作时 ( )

A、必须判别栈是否满 B、判别栈元素的类型 C、必须判别栈是否空 D、队栈不做任何判别 24、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ ） A、2 B、3 C、5 D、6

25、设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列

中不可能出现的出栈序列是（ ）

A、a3,a1,a4,a2 B、a3,a2,a4,a1 C、a3,a4,a2,a1 D、a4,a3,a2,a1 26、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ） A、e d c b a B、d e c b a C、d c e a b D、a b c d e

27、一个队列的入队列顺序是1，2，3，4，则队列的输出系列是 （ ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1

28、若一个栈的输入序列是1、2……N，输出序列的第一个元素是N，则第I个输出元素为（ ） A、N-I B、 I C、N-I+1 D、N-I-1 29、队列操作的原则是（ ）

A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除

第 2 页 共 3 页

30、数据结构中，与所使用的计算机无关的是数据的( C ) A) 存储结构 B) 物理结构 C) 逻辑结构 D) 物理和存储结构

二、填空题（13分）

1、循环链表与单链表的区别仅仅在于其尾结点的链域值不是__空（NULL）__，而是一个指向_头指针__的指针。

2、在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为___双向链表___。

3、带头结点的单链表H为空的条件是_H->next=NULL_。不带头结点的单链表H为空的条件是 H=NULL 4、非空单循环链表L中*p是尾结点的条件是__p->next=L____。 5、在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->link=_p->link__;和p->link=__s_的操作。 6、在一个单链表中p所指结点之前插入一个由指针s所指结点，可依次执行以下操作： s-> link =__ p->link _; p-> link =s; t=p->data; p->data=__s->data__; s->data=_t_;

7、在长度为n的顺序表中插入一个元素，最坏情况需要移动表中的__n_个元素。

8、线性表的存储结构主要有顺序存储和链式存储，队列是一种特殊的线性表，循环队列是队列的__顺序_存储结构

9、栈的操作特点是 ；队列的操作特点是

三、判断题（7分）

1、在顺序表中取出第i个元素所花费的时间与i成正比 （ X ） 2、线性表的长度是线性表所占用的存储空间的大小 （ X ）

3、在对不带头结点的链队列作出队列操作时，不会改变front指针的值 （ X ）

4、已知指针P指向链表L中某结点，执行语句P=P->link不会删除该链表中结点 （ √ ） 5、在链队列中，即便不设置尾指针也能进行入队列操作 （ √ ） 6、栈和队列都是运算受限的线性表 （ √ ）

7、在带头结点的单循环链表中，任一结点的后继指针均不空 （ √ ） 四、阅读算法，写出结果（20分）

第 3 页 共 3 页