数据结构习题答案二
2008-11-05 13:09阅读：
3、简述以下算法的功能：
status A (linkedist
L)
{//L是无表头结点的单链表
if (L && L—>next)
{Q=L;L=L－>next;P=L;
while (P－>next)
P=P－>next;
P－>next=Q;Q－>next=NULL;
}
return ok;
}//A
本程序实现的功能就是：如果L的长度不小于2，则将首元结点删去并插入到末尾。
4、写出下列程序段的输出结果。（假设此栈中元素的类型是char）
void main (
)
pop (s,x)
{stack s;
push(s,'H');
char x,y;
while(!stackEmpty(a))
InitStack(a)
{pop(s,y);
x='L', y='O '
printf(y);
push (s,x);
}
push (s,x);
printf(x)
push(s,y);
}
push(s,x);
push(s,'E');
push(s,x);
此题的输出结果是HELOLLL。
5、以下为单链表删除运算，分析算法，请在
处填上正确的语句。
void delete_lkist(lklist head,int i)
{p=find_lkist(head,i-1);
if( p!=NULL)&&(p—>next!=NULL)
{q= p—>next ;
p—>next=q—>next;
free(q);
}
else error('不存在第i个结点')
}
6、以下为顺序表的定位运算，分析算法，请在
处用正确的语句予以填充。
int locate_sqlist(sqlist L,datatype
X)
{ i=1 ;
while(i£L>last)&&(L.data[i-1]!=X)i++;
if ( i≤L.last
)return(i);
else return(0);
}
7、以下为单链表的建表算法，分析算法，请在
处填上正确的语句
lklist create_lklist2()
{head=malloc (size);
p=head;
scanf ('%f',%x);
while(x!='$')
{q=malloc(size);
q—>data=x;
p—>next=q;
p=q ;
scanf ( '%f',%x);
}
p—>next=NULL
;
return(head);
}
此算法的量级为 O(n)
。
习题三
一、选择题
1、若用单链表来表示队列， 则应该选用 B
。
A、带尾指针的非循环链表
B、带尾指针的循环链表
C、带头指针的非循环链表
D、带头指针的循环链表
2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear
和front的值分别是 B
。
A、1和5
B、2和4
C、4和2
D、5和1
3、设栈的输入序列为1、2、3、4，则 C
不可能是其出栈序列。
A、1243 B、2134
C、1432
D、4312
E、3214
4、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为
C 。
A、-A+B*C/DE
B、-A+B*CD/E
C、-+*ABC/DE
D、-+A*BC/DE
5、设栈的输入序列是1、2、…、n，若输出序列的第一个元素是n，则第i个输出元素是
B 。
A、不确定
B、n-i+1
C、i
D、n-i
6、假定一个顺序循环队列的队首和队尾指针分别用front 和rear表示，则判队空的条件是
D 。
A、front+1==rear
B、front==rear+1
C、front==0
D、front==rear
7、假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front 和rear表示，则判断队满的条件是
B 。
A、(rear-1)%n==front
B、(rear+1)%n==front
C、rear==(front-1)%n
D、rear==(front+1)%n
8、一个栈的的输入序列为12345，则下列序列中不可能是栈的输出序列的是 B
。
A、23415
B、54132
C、23145
D、15432
9、若一个栈的输入序列是1、2、3、…、n，输出序列的第一个元素是i，则第i个输出元素是
D 。
A、i-j-1
B、i-j
C、j-i+1
D、不确定
10、用单链表表示的链式队列的队头在链表的 A
位置。
A、链头
B、链尾
C、链中
11、设计一个判别表达式中左、右括号是否配对出现的算法，采用
D 数据结构最佳。
A、线性表的顺序存储结构
B、队列
C、线性表的链式存储结构
D、栈
12、在下列算法描述中，涉及到队运算的算法是 D
。
A、表达式求值算法
B、深度优先搜索
C、二叉树遍历
D、广度优先搜索
13、栈的插入和删除操作在 A
进行。
A、栈顶
B、栈底
C、任意位置 D、指定位置
14、在一个顺序循环队列中，队首指针指向队首元素的 A
位置。
A、前一个 B、后一个
C、当前
D、最后
15、当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为 B
。
A、N-2
B、N-1
C、N
D、N+1
16、如果以链表作为栈的存储结构，则退栈操作时 C
。
A、必须判别栈是否满
B、判别栈元素的类型
C、必须判别栈是否空
D、对栈不作任何判别
17、链栈与顺序栈相比有一个明显的优点，即 B
。
A、插入操作更加方便
B、通常不会出现栈满的情况
C、不会出现栈空的情况
D、删除操作更加方便
二、填空题
1、中缀式a+b*3+4*(c-d)对应的前缀式为
++a×b3×4-cd
，若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为 18
。
2、用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是m=
（m+1）% n 。
3、表达式求值是 栈
应用的一个典型例子。
4、队列是特殊的线性表，其特殊性在于
只允许在表的一端进行元素的插入而在另一端进行元素的删除 。
5、一个循环队列存于A[M]中，假定队首和队尾指针分别为front和rear，则判断队空的条件为
front==rear
，判断队满的条件为 (rear+1) % M==front
。
6、向一个循环队列存入新元素时，需要首先移动 队尾指针
，然后再向它所指位置 存入
新元素。
7、 队列
又称为先进先出表。
8、栈是特殊的线性表，其特殊性在于 只允许在栈顶加入或删除元素
。
9、栈又称为 后进先出 表，队列又成为
先进先出 表。
10、在一个用一维数组A[N]表示的顺序栈中，该栈所含元素的个数最少为 0
个，最多为 N
个。
11、在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为 0
个，最多为 N-1
个。
习题四
一、选择题
1、设有两个串p和q，求q和p中首次出现的位置的运算称作 C
。
A、连接 B、求子串
C、模式匹配
D、求串长
2、若串S=’good student’，其子串的数目是 C
。
A、12
B、79
C、78
D、13
3、串是一种特殊的线性表，其特殊性体现在 B
。
A、可以顺序存储
