数据结构复习题：串 单选题
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))的结果串是_______。
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,则其元素个数为______。 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表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为_________。
25、一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为_________。 26、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为_________。 27、若让元1，2，3依次进栈，则出栈次序不可能出现_________种情况。 28、在一个顺序队列中，队首指针指向队首元素的_________位置。
29、当利用大小为N的数组顺序存储一个队列时，若没有队列长度的变量，则该队列的最大长度为_________。
30、当利用大小为N的数组顺序存储一个队列时，若不设有队列长度的变量，则该队列的最大长度为_________。
- 46 -
31、从一个顺序队列删除元素时，首先需要_________。
32、一个不设队列长度变量的顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为_________。 33、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为_________。
34、假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元素x进队时所执行的操作为_________。
37、在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为_________。 数据结构复习题答案：串 单选题
1、'bcdef' |'bcdefg' |'bcpqrst' |'bcdefef' D 2、正确|不正确|| B 3、可以顺序存储|数据无素是一个字符|可以链式存储|数据元素可以是多个字符 B 4、abcd|321AB|\ D 5、BCDEF|BCDEFG|BCPQRST|CDEFGFG D 6、a|b|1|0 B 7、a|b|1|0 C 8、A|B|C|D AD 9、4321|1234|1432|3241 B 10、
(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize|(qu.rear+1)%MaxSize==qu.front+1|(qu.rear+1)%MaxSize==qu.front|qu.rear==qu.front C 11、
(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize|(qu.rear+1)%MaxSize==qu.front+1|(qu.rear+1)%MaxSize==qu.front|qu.rear==qu.front D
12、r-f|r-f-1|(r-f)%N+1|(r-f+N)%N D 13、
qu.front==qu.rear|qu.front+1==qu.rear|qu.front==(qu.rear+1)%QueueSize|qu.rear==(qu.front+1)%QueueSize C 14、可用\作为队空的标志|可用\作为队空的标志|可用\作为队空的标志|队列中最多可以有M+1个元素 A
15、带队首指针和队尾指针的循环单链表|带队首指针和队尾指针的非循环单链表|只带队首指针的非循环单链表|只带队首指针的循环单链表 B
16、链头|链尾|链中|以上都可以 A 17、链头|链尾|链中|以上都可以 B 18、仅修改头指针|仅修改尾|头、尾指针都要修改|头、尾指针可能都要修改 D 19、都是先进后出|都是先进先出|只允许在端点处插入和删除元素|没有共同点 C
20、Q.front==Q.rear|Q.front+1==Q.rear|Q.front==(Q.rear+1)%QueueSize|Q.rear=(Q.front+1)%QueueSize C
21、栈顶|栈底|任意位置|指定位置 A 22、top++|top--|top=0|top B 23、a[--top]=x|a[top--]=x|a[++top]=x|a[top++}=x D 24、return a[--top]|return a[top--]|return a[++torp]|return a[top++] B
25、p->next=top;top=top->next;|top=p;p->next=top;|p->next=top->next;top->next=p;|p->next=top;top=p; D
- 47 -
26、top->next=top;|top=top->data;|top=top->next;|top->next=top->next->next C 27、3，2，1|2，1，3|3，1，2|1，2，3 C 28、前一个|后一个|当前|后面 A 29、N-2|N-1|N|N+1 C 30、N-2|N-1|N|N+1 B
31、队首指针循环加１|队首指针循环减１|取出队首指针所指位置上的元素|取出队尾指针所指位置上的元素 A
32、f+1==r|r+1==f|f==0|f==r D 33、front==rear|front!=NULL|rear!=NULL|front==NULL D 34、a[++r%N]=x|a[r++%N]=x|a[--r%N]=x|a[r--%N]=x B 37、(rear-front)%N|(rear-front+N)%N|(rear+N)%N|(front+N)%N B
数据结构复习题：串 判断题
1、栈和队列都是限制存取端的线性表。
2、队列是一种对进队列、出队列操作的次序作了限制的线性表。 3、n个元素进队列的顺序和出队列的顺序总是一至的。
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执行入队的操作
- 48 -
是______。
13、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,假设队列车不空,则元素出队并保存到x中的操作是______。
14、若用带头结点的单链表来表示链队,则队列空的标志是______。
15、若用不带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。 16、若用带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。 17、己知链队的头、尾指针分别是f和r,则将值x入队的操作序列是_____。
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、顺序存储方式和链式存储方式
2、两个串的长度相等且对应位置的字符相同 3、零个字符的串|零
4、由一个或多个空格字符组成的串|其包含的空格个数 5、14
6、'GOOD BYE!' 7、先进先出 8、存储结构 9、链队 10、队尾
11、解决了假溢出问题
12、rear=(rear+1)%(m++1);A[rear]=x; 13、front=(front+1)%(m+1);x=A[front]; 14、头结点的指针域为空
15、将单链表的首结点指针赋空值
- 49 -
16、将单链表头结点的指针域赋空值
17、p=(QNode *)malloc(sizeof(QNode));p->data=x;p->next=r->next;r->next=p;r=p; 18、假溢出
19、(rear-front+m)%m 20、队尾| 队首
21、后进行出|先进先出 22、栈顶指针|写入 23、栈顶元素|减1
24、Q.front=Q.rear|(Q.rear+1)%MaxSize==Q.front 25、空|只含有一个结点
26、新结点的指针域|栈顶指针 27、指针域 | 栈顶指针 28、top==0
29、P->next=HS|HS=p 30、3x2+*5-
33、pop(S)|pop(S)| push(S,d)
数据结构复习题：串 问答题
1、设栈s和队列q的初始状态都为空,元素a,b,c,d,e和f依次通过栈s,一个元素出栈后即进入队列q,若6个元素出队的序列是bdcfea,则栈s的容量至少应该存多少个元素?
数据结构复习题答案：串 问答题
1、答：栈s的容量至少应该存3个元素。
- 50 -