专升本数据结构试题解析(15)
时间:2025-07-11
时间:2025-07-11
第2部分 习题解析 亱店↘打烊oO
rear+1=front(准确记是(rear+1)%m=front,m是队列容量)时为队满。另一种解法是“设标记”方法,如设标记tag,tag等于0情况下,若删除时导致front=rear为队空;tag=1情况下,若因插入导致front=rear则为队满。
5. 若以1、2、3、4作为双端队列的输入序列,试分别求出以下条件的输出序列:
(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;
(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;
(3)既不能由输入受限双端队列得到,也不能由输出受限双端队列得到的输出序列。
【答案】(1)4132 (2)4213 (3)4231
3.5 程序设计题
1.设表达式以字符形式已存入数组E[n]中, # 为表达式的结束符,试写出判断表达式中括号( ( 和 ) )是否配对的C语言描述算法:EXYX(E); (注:算法中可调用栈操作的基本算法。)
【算法分析】判断表达式中括号是否匹配,可通过栈,简单说是左括号时进栈,右括号时退栈。退栈时,若栈顶元素是左括号,则新读入的右括号与栈顶左括号就可消去。如此下去,输入表达式结束时,栈为空则正确,否则括号不匹配。
【算法源代码】
int EXYX (char E[]){
/*E[]存放字符串表达式,以‘#’结束*/
char s[30]; /*s是一维数组,容量足够大,用作存放括号的栈*/
int top=0,i; /*top用作栈顶指针*/
s[top]='#'; /*‘#’先入栈,用于和表达式结束符号‘#’匹配*/
i=0; /*字符数组E的工作指针*/
while(E[i]!='#') /*逐字符处理字符表达式的数组*/
switch (E[i])
{case '(': s[++top]= '('; i++ ; break ;
case ')': if(s[top]=='('){top--; i++; break;}
else{printf("括号不配对");exit(0);}
case '#': if(s[top]=='#'){printf("括号配对\n");return (1);}
else {printf(" 括号不配对\n");return (0);} /*括号不配对*/
default : i++; /*读入其它字符,不作处理*/
}
}/*算法结束*/
2.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。
【算法分析】
根据队列的先进先出的性质,队列的入队操作在队尾进行,出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。
【算法源代码1】
void EnQueue (LinkList rear, ElemType x)
/* rear是带头结点的循环链队列的尾指针,本算法将元素x插入到队尾*/
{ s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/
s->data=x; s->next=rear->next; /*将s结点链入队尾*/
rear->next=s; rear=s; /*rear指向新队尾*/
}
【算法源代码2】
void DeQueue (LinkList rear)
/* rear是带头结点的循环链队列的尾指针,本算法执行出队操作,操作成功输出队头元
素;否则给出出错信息*/
{ if(rear->next==rear) {printf("队空\n"); exit(0);}
s=rear->next->next; /*s指向队头元素*/
rear->next->next=s->next; /*队头元素出队*/
printf ("出队元素是:%d",s->data);
if(s==rear) rear=rear->next; /*空队列*/