数据结构习题-分章

素是（ C ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

13．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 二 填空题

1. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。

2. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_________。

3. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。

4不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。 5设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

6设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。

7 设输入序列为1、2、3，则经过栈的作用后可以得到____5_______种不同的输出序列。

8不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___O(1)____。 9设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储_ m-1，(R-F+M)%M_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

三 简答题

1. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。 2. 什么是队列的上溢现象？一般有几种解决方法，试简述之。

四 算法设计题

1. 假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：

（1）向循环链队列插入一个元素值为x的结点； （2）从循环链队列中删除一个结点。

五 程序阅读

1. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) {

if (stack.top==m-1) printf(“overflow”);

else {____________________;_________________;} }

习题3参考答案 栈和队列

一 单项选择题

1A 2C 3A 4C 5C 6B 7D 8C 二 填空题

1．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 2．2、3 O(1) 4 O(1)

5 top1+1=top2 6 F==R

三 简答题

1．共有14种可能的出栈序列，即为： ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA 2．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法：

（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （2）要避免出现“假溢出”现象可用以下方法解决：

第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。

第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。

四 算法设计题

1．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：

（1）插入（即入队）算法：

insert(LinkList *rear, elemtype x)

{ //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p;

p=(LinkList *)malloc(sizeof(LinkList));

if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p;

rear->next=p; //链接成循环链表 }

else //否则在队尾插入p结点 { p->next=rear->next;

rear->next=p; rear=p; }

9A 10C 11C 12D

}

（2）删除（即出队）算法：

delete(LinkList *rear)

{ //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf(\

if(rear->next= =rear) //队中只有一个结点 rear=NULL; else

rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点 }

五 程序阅读

1. stack.top++，stack.s[stack.top]=x

习题4 串

一、单项选择题

1. 空串与空格字符组成的串的区别在于（ ）。

A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置

D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ ）是正确的。

A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ ）。

A.两串的长度相等 B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。

A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”

6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。

A.2 B.3 C.4 D.5 7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。

A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”

8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。

A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1

9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。

A.链表的长度为1

B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符

10．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE” (A) 20 (B) 30 (C) 40 (D) 45 11 两个字符串相等的充要条件是（C）。

(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等 (C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对