数据结构习题11级用(3)

18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）

A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1 19．完成在双循环链表结点p之后插入s的操作是（ ）；

A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next; B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next; C． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ; D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s; 20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。

注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案：

A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q；q↑.llink：=q； B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink；

C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q;

D． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q； 21．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为: rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ）

A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p D．rlink(rlink(p)) ← p

22． 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;

B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;

C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 23．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

8

24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;

25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;

二、填空题

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。

2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;

4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。

5．在单链表中设置头结点的作用是________。

6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。 7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。

8．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、

_______、_______、________。

9．在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：

s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s； 10.链接存储的特点是利用________来表示数据元素之间的逻辑关系。

11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过

9

________表示元素之间的关系的。

12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链

表为_______个。

13. 循环单链表的最大优点是：________。

14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________ 15. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 16. 在单链表L中，指针p所指结点有后继结点的条件是：__ 17.带头结点的双循环链表L为空表的条件是：________。 18. 在单链表p结点之后插入s结点的操作是：_______。

三、解答题

1．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性

表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取

线性表中的元素，那么应采用哪种存储结构？为什么？

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大

量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？

为什么？

4．线性结构包括______、______、_______和_______。线性表的存储结构分成______

和______。请用类PASCＡL语言描述这两种结构。

5．线性表（a1，a2，?，an）用顺序映射表示时，ai和ai+1（1<=i

6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首

元结点的关系。

7. 试述头结点,首元结点,头指针这三个概念的区别.

8．有线性表(a1,a2,?,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。

（1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。

10

9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?

10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链

表？

11. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C

语言语句。

12. 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，

请写出在p结点之前插入s结点的操作（PASCAL语句）。

四、算法设计题

1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法

将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

2. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点

个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 3．在带头结点的单链表上，给出求表长Length(L)的算法，并加入简要的注释或说

明。

4．设单链表具有头结点，且表中元素各不相同，试给出在单链表中查找值为\的结

点的算法，并加入简要的注释或说明。

5．设单链表具有头结点，且表中元素各不相同，试给出在单链表中删除值为\的结点的算法。

11

第三章 栈和队列

一、 选择题

1. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

③ , ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.

3. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

4. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。

A. i-j-1 B. i-j C. j-i+1 D. 不确定的

5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定

6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，

12

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题11级用(3)在线全文阅读。