手机版

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

时间:2025-07-10   来源:未知    
字号:

第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.在顺序队列中,当尾指针等于数组的上界,即使队列不满,再作入队操作也会产生溢出,这种现象称为_____________。

【答案】假溢出

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

专升本数据结构试题解析(13).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
×
二维码
× 游客快捷下载通道(下载后可以自由复制和排版)
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能出现无法下载或内容有问题,请联系客服协助您处理。
× 常见问题(客服时间:周一到周五 9:30-18:00)