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

第2部分 习题解析 亱店↘打烊oO

【答案】先进先出

5．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_____________。

【答案】

s=(LinkList)malloc(sizeof(LNode));

s->data=x;

s->next=r->next;

r->next=s;

r=s;

【解析】根据队列的性质，新插入的元素永远插在队尾。

6．区分循环队列的满与空，只有两种方法，它们是_____________和_____________。

【答案】（1）牺牲一个存储单元 （2）设标记

7．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_____________。

【答案】23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）

【解析】表达式的后缀表达式是将表达式中的运算符写在两个操作数之后。转换原则如下：

（1）从左到右扫描表达式，若读到的是操作数，则直接把它输出

（2）若读到的是运算符：

①该运算符为左括号“（”，则直接入栈

②该运算符为右括号“）”，则输出栈中运算符，直到遇到左括号为止

③该运算符为非括号运算符，则与栈顶元素做优先级比较：若比栈顶元素的优先级高或相等，则直接入栈；若比栈顶元素的优先级低，则输出栈顶元素。

（3）当表达式扫描完后栈中还有运算符，则依次输出运算符，直到栈空。

8．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_____________。

【答案】(M+1)% N；

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。

9．当两个栈共享一存储区时，栈利用一维数组stack[1..n]表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_____________，栈2空时，top[2]为_____________，栈满时为_____________。

【答案】（1）0 （2）n+1 （3）top[1]+1=top[2]

【解析】为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的栈顶分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生上溢，即top[1[+1=top[2]。

10．在作进栈运算时应先判别栈是否_____________；在作退栈运算时应先判别栈是否 n个，作进栈运算时发生上溢，则说明该栈的最大容量为_____________。

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

【答案】（1）满 （2）空 （3）n （4）栈底 （5）两栈顶指针相邻

11．在Q的链队列中，判断只有一个结点的条件是_____________。

【答案】Q->front!=NULL&&Q->front==Q->rear

【解析】只有一个结点时，队列不为空并且队头指针和队尾指针指向同一结点。

12．若用不带头结点的单链表来表示链栈S，则创建一个空栈所需要执行的操作是_____________。

【答案】S=NULL

13．无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为_____________。

【答案】O(1)

【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。

14．在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。

【答案】假溢出

【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。