数据结构习题集包含答案(2)

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. 错误：也可以有顺序存储的形式。

×)(

第三章 栈和队列

一、选择题

l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（）。

A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a

2．若一个栈的输人序列是1，2，3，?，n，输出序列的第一个元素是n，则第k个输出元素是（ ）。

A．k B．n-k-1 C．n-k+1 D．不确定 3．判定一个栈S（最多有n个元素）为空的条件是（ ）。

A．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n 4．判定一个栈S（最多有n个元素）为满的条件是（ ）。

A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（ ）。 A．top->next=S； B．S->next=top；top=S；

C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；

6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 A．top->next=S； B．S->next=top；top=S；

C．S->next=top->next；top->next=S； D．S->next=top；top=S->next； 7．判定一个队列Q（最多有n个元素）为空的条件是（ ）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l

C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。

A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n

11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。

A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（ ）。

A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 14．若进栈序列为l，2，3，4，则（ ）不可能是一个出栈序列。

A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个

（ ）结构。

A．堆栈 B．队列 C．数组 D．线性表

1. C 2. C 3. B 4. D 5. B 6. C 7. C 8. A 9. A 10. C 11. C 12. A 13. C 14. C 15. B

二、填空回

1．栈（stack）是限定在________一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__________，而另一端称为_________。不含元素的栈称为_______。

2．在栈的运算中，栈的插人操作称为________或________，栈的删除操作称为_________或__________。

3．根据栈的定义，每一次进栈的元素都在原___________之上，并成为新的__________；每一次出栈的元素总是当前的_____________，因此最后进栈的元素总是__________，所以栈也称为___________线性表，简称为____________表。

4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有__________和_________________两种存储结构，分别称为______________和____________。

5．当栈满的时候，再进行人栈操作就会产生____________，这种情况的溢出称为___________；当栈空的时候，如果再进行出栈操作，也会_____________，这种情况下的溢出称为__________________。

6．栈的链式存储结构简称为____________，是一种__________________。 7．人们日常计算用到的表达式都被称为____________，这是由于这种算术表达式的运算符被置于两个操作数中间。

8．计算机中通常使用___________，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__________________。

9．队列（Queue）也是一种___________，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_________，允许删除的一端称为_______________。

10．队列的特点是_________，因此队列又被称为_______________．的线性表，或称为_________________表。

11．队列的_________又称为__________，是用一组地址连续的存储单元依次存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向__________和__________，这两个指针又称为__________和_____________。 13．循环顺序队列（Circular Sequence Queue）经常简称为___________，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_________________来实现的。

14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为____________。函数直接调用自己，则称为__________；当一个函数通过另一个函数来调用自己则称为_________________。

15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为___________， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为____________________。 16．用链表方式表示的队列称为____________________。

17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2= =n的输出序列共有__________________。

18．一个栈的输人序列是12345，则栈的输出序列为43512是________（填是否可能）。

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