解答：d,e,b,g,h入队 d e b g h F r d,e出队
b g h F r i,j,k,l,m入队 b g h i j k l m F r
n,o,p入队 b g h i j k l m n o p
F r
所有元素均正好能入队，共有11个存储空间，恰好11个元素。
9、假设CQ[0..10]是一个环形队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队
解答： 图略 。
p不能入队，共有11个地址，p为第12个元素，故不能入队。
10、有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个? 答：三个：CDEBA，CDBEA，CDBAE
11、设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名?
答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。 12、简要叙述栈和队列的特点.
答：栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。
- 26 -
4 串
数据结构复习题：串单选题
沈阳理工大学应用技术学院信息与控制学院 计算机科学与技术教研室
2011-5-8
- 27 -
1、设字符串s1='abcdefg',s2='pqrst'，则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为_____。 2、空串与空白串是相同的,这种说法________。
3、串是一种特殊的线性表,其特殊性体现在________。 4、_______是C语言中\的子串。
5、有串s1='ABCDEFG',s2='PQRST',假设函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是___CDEFGFG ____。
6、经过以下队列运算后,队头的元素是______。
InitQueue(qu);enQueue(qu,'a');enQueue(qu,'b');enQueue(qu,'c');deQueue(qu);
7、经过以下队列运算后,QueueEmpty(q)的值是______。
InitQueue(qu);enQueue(qu,a);enQueue(qu,b),deQueue(qu,x);deQueue(qu,y);
8、元素A、B、C、D顺序连续进入队列qu后,队头元素是______,队尾元素是______。 9、一个队列的入列序列为1234,则队列可能的输出序列是______。 10、环形队列qu的队满条件是______。 11、环形队列qu的队空条件是______。
12、设环形队列中数组的下标是0～N-1,其头、尾指针分别为f和r,则其元素个数为___(r-f+N)%N___。 13、判定一个环形队列qu(存放元素位置0～QueueSize-1)队满的条件是______。
14、假设用qu[0..M]实现环形队列,qu[f]、qu[r]分别为队首元素的前一个位置和队尾位置。若用\作为队满的标志,则______。
15、最适合用作链队的链表是__带队首指针和队尾指针的非循环单链表____。 16、用单链表表示的链队的队头在链表的______位置。 17、用单链表表示的链队的队尾在链表的______位置。 18、对于链队,在进行删除操作时,______。 19、栈和队列的共同点是______.
20、判定一个环形队列Q(存放元素位置为0～QueueSize-1)队满的条件是______. 21、栈的插入和删除操作在_________进行。
22、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_________语句修改top指针。
23、假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针,top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为_________.
24、利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为____return a[top--]_____。
25、一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为_________。 26、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为_________。 27、若让元1，2，3依次进栈，则出栈次序不可能出现_________种情况。 28、在一个顺序队列中，队首指针指向队首元素的____前一个_____位置。
29、当利用大小为N的数组顺序存储一个队列时，若没有队列长度的变量，则该队列的最大长度为_________。
30、当利用大小为N的数组顺序存储一个队列时，若不设有队列长度的变量，则该队列的最大长度为____N-1_____。
31、从一个顺序队列删除元素时，首先需要____队首指针循环加１_____。
32、一个不设队列长度变量的顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为_________。 33、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为___front==NULL______。 34、假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元
- 28 -
素x进队时所执行的操作为_________。
37、在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为_________。
数据结构复习题：串 判断题
1、栈和队列都是限制存取端的线性表。
2、队列是一种对进队列、出队列操作的次序作了限制的线性表。F 3、n个元素进队列的顺序和出队列的顺序总是一至的。T
4、顺序队中有多少元素,可以根据队首指针的值和队尾指针的值来计算。 5、队列的输入序列为124?n,输出序列为a1a2?an,则ai
数据结构复习题答案：串 判断题 1、True 2、False 3、True 4、True 5、True
数据结构复习题：串 填空题
1、串的两种最基本的方式是____顺序存储方式和链式存储方式_____。
2、两个串相等的充分必要条件是____两个串的长度相等且对应位置的字符相同____。 3、空串是____零个字符的串____,其长度等于_________。
4、空白串是____由一个或多个空格字符组成的串____,其长度等于____其包含的空格个数_____。 5、设s='I_AM_A_TEACHER',(其中,_表示一个空格字符),其长度是_______。 6、设s1='GOOD',s2=' ',s3='BYE!',则s1,s2和s3连接后的结果是________。 7、队列是一种具有______特性的线性表。 8、顺序队和链队的区别仅在于______的不同。
9、如果队列的最大长度以难以估计,则最好使用______。 10、在队列中,新插入的元素只能插入到______。 11、环形队列的优点是__解决了假溢出问题____。 12、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,则元素x执行入队的操作是______。
13、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,假设队列车不空,则元素出队并保存到x中的操作是______。
14、若用带头结点的单链表来表示链队,则队列空的标志是______。
15、若用不带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是___将单链表的首结点指针赋空值___。
16、若用带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。 17、己知链队的头、尾指针分别是f和r,则将值x入队的操作序列是
__p=(QNode*)malloc(sizeof(QNode));p->data=x;p->next=r->next;r->next=p;r=p___。
- 29 -
18、在顺序队列实现的时候,通常将数组看成是一个首尾相连的环,这样做的目的是为避免产生___假溢出___现象.
19、环形队列用数组A[0..m-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列中的元素个数是______.
20、队列的插入操作在____________进行，删除操作在____________进行。 21、栈又称为____________表，队列又称为____________表。
22、向一个顺序栈插入一个元素时，首先使____________后移一个位置，然后把待插入元素____________到这个位置上。
23、从一个顺序栈删除元素时，首先取出____________的值，然后再使栈顶指针____________。 24、在一个不设队列长度变量的顺序队列Ｑ中，判断队空的条件为____________，判断队满的条件为____________。
25、在一个链队中，若队首指针与队尾指针的值相同，则表示该队为____________或该队______只含有一个结点______。
26、向一个链栈插入一个新结点时，首先把栈顶指针的值赋给____________，然后把新结点的存储位置赋给____________。 27、从一个链栈中删除一个结点时，需要把栈顶结点_____指针域_______的值赋给______栈顶指针______。 28、当用长度为Ｎ的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为____________。 29、向一个栈顶指针为ＨＳ的链栈中插入一个新结点*p时，应执行____________和____________操作。 30、中缀表达式3*(x+2)-5所对应的后缀表达式为____________。
33、设元素a,b,c,d依次进Ｓ栈，若要在输出端得到序列cbda，则应进行的操作序列为push(S,a),push(S,b),push(S,c),____________,____________,____________,pop(S),pop(S)。
数据结构复习题：串 问答题
1、设栈s和队列q的初始状态都为空,元素a,b,c,d,e和f依次通过栈s,一个元素出栈后即进入队列q,若6个元素出队的序列是bdcfea,则栈s的容量至少应该存多少个元素?
数据结构复习题答案：串 问答题
1、答：栈s的容量至少应该存3个元素。
6 树和二叉树
- 30 -
