专升本数据结构试题解析(12)

数据结构上机实验与习题解析 亱店↘打烊oO

A）1和 5 B）2和4 C）4和2 D）5和1

【答案】B

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。

10．栈和队列的共同点是（ ）

A）都是先进先出 B）都是先进后出

C）只允许在端点处插入和删除元素 D）没有共同点

【答案】C

【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。

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

A）front->next=s;front=s; B）s->next=rear;rear=s;

C）rear->next=s;rear=s; D）s->next=front;front=s;

【答案】C

【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。

12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（ ）

A）S->top!=-1 S->top!=MAXSIZE-1

B）S->top=-1 S->top=MAXSIZE-1

C）S->top=-1 S->top!=MAXSIZE-1

D）S->top!=-1 S->top=MAXSIZE-1

【答案】B

13．循环顺序队列中是否可以插入下一个元素（ ）

A）与队头指针和队尾指针的值有关

B）只与队尾指针的值有关，与队头指针的值无关

C）只与数组大小有关，而与队头指针和队尾指针的值无关

D）与曾经进行过多少次插入操作有关

【答案】A

【解析】在循环队列中判断队满的条件为：(q.rear+1)%m==q.front是否为真，从中可以看出，与队头指针和队尾指针的值有关。

14．最不适合用作链队的链表是（ ）

A）只带队头指针的非循环双链表 B）只带队头指针的循环双链表

C）只带队尾指针的非循环双链表 D）只带队尾指针的循环单链表

【答案】A

【解析】链队是在链表的两端进行操作，而在A中查找链表最后一个结点的时间复杂度为O(n)。

15．下列哪中数据结构常用于系统程序的作业调度（ ）

A）栈 B）队列 C）链表 D）数组

【答案】B

【解析】作业调度采用先到先服务的方式，因此最适合的数据结构为队列。

3.2 填空题

1．栈是_____________的线性表，其运算遵循_____________的原则。

【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作） （2）后进先出

2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值是_____________H。设栈为顺序栈，每个元素占4个字节。

【答案】（1）23 （2）100CH

【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1，输出数据为2，然后经过PUSH,POP，3入栈，3出栈，然后经过PUSH,PUSH之后4，5入栈，此时出栈序列为2，3，栈中元素为1，4，5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH（十六进制数）

3．循环队列的引入，目的是为了克服_____________。

【答案】假溢出时大量移动数据元素。

4．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____________。