第二章 线性表
一、选择题
1．在一个长度为n的顺序表中删除第i个元素（0 2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( )个元素结点。 A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( )。 A．O(n) B．O(1) C．O(n2） D．O（long2n） 4．线性表采用链式存储时，其地址( )。 A． 必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( )。 A．O（long2n） B．O（l） C．O（n2） D．O（n） 6．线性表是( )。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 7．在一个长度为n的顺序表中，向第i个位置（0一1＜n＋1）插入一个新元素时，需要向后移动( )个元素。 A．n-i B．n-i＋1 C．n－i－1 D．i＋1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。 A．单链表 B．双向链表 C．单循环链表 D．顺序表 9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 10．在顺序存储的线性表（a1??an）中，删除任意一个结点所需移动结点的平均移动次数为( ) A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 11．在线性表的下列存储结构中，读取第i个元素花费的时间最少的是（）。 A．单链表 B．双链表 C．循环链表 D．顺序表 12．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。 A．双链表 B．单链表 C．单循环链表 D．带头结点的双循环链表 13．在单链表中删除指针p所指结点的后继结点，则执行（ ）操作。 A．p->next=p->next->next B．p->next=p->next C．p=p->next->next D．p=p->next; p->next=p->next->next 14．在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s所指的结点，则执行（ ）操作。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q; 15．在单链表中附加头结点的目的是为了（ ）。 A．保证单链表中至少有一个节点 B．标识单链表中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储 16．循环单链表的主要优点是（ ）。 A．不再需要头指针了 B．从表中任意一个结点出发都能扫描到整个链表 C．已知某个结点的位置后，能够容易找到它的前驱 D．在进行插入、删除操作时，能更好地保证链表不断开 17．非空的循环单链表L的尾结点p满足（ ）。 A．p->next=NULL B．p=NULL C．p->next=L D．p=L 18．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。 注:双向链表的结点结构为(prior,data,next)。 供选择的答案： A．p->prior=q； q->next=p； p->prior->next=q； q->prior=q； B．p->prior=q； p->prior->next=q; q->next=p； q->prior=p->prior； C．q->next=p； q->prior=p->prior；p->prior->next=q; p->prior=q; D．q->prior=p->prior； q->next=p； p->prior=q； p->prior=q； 19．在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A．p->prior->next=p->next; p->next->prior=p->prior; B．p->prior=p->prior->prior; p->prior->next=p;(删p的前趋) C．p->next->prior=p; p->next=p->next->next; D．p->next= p->prior->prior; p->prior= p->next->next; 二、填空题 1．线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着__________的相互关系。（一对一） 2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__________，除终端结点外，其他每个元素有且仅有一个______。 3．线性表是n（n>=0）个数据元素的________。其中n为数据元素的个数，定义为线性表的__________。当n为零时的表称为_________。 4．所谓顺序表（Sequential LISt）是线性表的__________，它是将线性表中的结点按其____________依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在____________的存储单元中。 5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_______的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_________的位置上，它们在物理上可以是一片连续的存储单元，也可以是__________的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。 6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_________；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为________或____________。 7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不 再一致，而是一种_________存储结构，又称为__________。 8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了______________。 9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了___________。 10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_______。 11．在单链表中，删除指针P所指结点的后继结点的语句是____________。 12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及__________。 13．单链表是___________的链接存储表示。 14．可以使用___________表示树形结构。 15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__________个元素。 16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动_______个元素。 17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__________。 18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_______。 19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是_________。 20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为_______________。 21．写出带头结点的双向循环链表L为空表的条件________________。 22．线性表、栈和队列都是_________________结构。 23．向栈中插人元素的操作是先移动栈_____________针，再存人元素。 1. 一对一 2. 直接前驱、直接后继 3. 有限序列、长度、空表 4. 顺序存储结构、逻辑顺序、地址相邻 5. 任意、任意、不连续、逻辑关系 6. 数据域、指针域、链域 7. 非顺序、非顺序映像 8. 循环链表 9. 双向链表 10. 所指向的结点本身 11. P->next=p->next->next 12. P->next->prior=P->prior 13. 线性表 14. 双链表 15. n-i+1 16. n-i 17. S->next=P->next; P->next=S 18. p->prior->next=S; s->prior=p->prior; s->next=p; p->prior=s; 19. head(tail(tail((head(tail(head(A)))))) 20. O(n) 21. (L==L->Next) && (L==L->Prior) 22. 线性 23. 顶 三、判断题 1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(×) 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(×) 3．顺序存储的线性表不可以随机存取。(×) 4．单链表不是一种随机存取结构。（） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。(×) 7．线性表的长度是线性表所占用的存储空间的大小。(×) 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。(×) 9．线性表的惟一存储形式是链表。(×) 1. 错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。 2. 错误：头指针指向头结点而不是数据结点。 3. 错误：顺序存储的线性表可以随机存取。 4. 正确。 5. 错误。 6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。 7. 错误：先行表的长度是线性表中结点的个数。 8. 错误：注意最后一个结点。 9. 错误：也可以有顺序存储的形式。 ×)(