数据结构（本）课程作业

作业2

（本部分作业覆盖教材第3-5章的内容）

 

一、单项选择题

1．若让元素1，2，3依次进栈，则出栈顺序不可能为（     ）。

A．3，2，1           B．2，1，3         

C．3，1，2           D．1，3，2

 

2．一个队列的入队序列是1，2，3，4。则队列的输出序列是（    ）。

A．4，3，2，1       B．1，2，3，4          

C．1，4，3，2       D．3，2，4，1

 

3．向顺序栈中压入新元素时，应当（    ）。

A．先移动栈顶指针，再存入元素        B．先存入元素，再移动栈顶指针   

C．先后次序无关紧要                  D．同时进行

 

4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（   ）。

A．top->next=p;                B．p->next=top->next; top->next=p;

C．p->next=top; top=p;         D．p->next=top->next; top=top->next;

 

5．在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（   ）。

A．x=top;top=top->next;       

B．x=top->data;

C．top=top->next; x=top->data;  

D．x=top->data; top=top->next;

 

6．一般情况下，将递归算法转换成等价的非递归算法应该设置（    ）。

A．栈                      B．队列

C．堆栈或队列              D．数组

 

7．表达式a*(b+c)-d的后缀表达式是（    ）。

 A．abcd*+-      B．abc+*d-     C．abc*++d-    D．-+*abcd

 

8．判断一个顺序队列sq（最多元素为m₀）为空的条件是（     ）。

  A．sq->rear-sq->front== m₀           B．sq->rear-sq->front-1= = m₀      

C．sq->front==sq->rear                 D．sq->front==sq->rear+1

9．判断一个循环队列Q（最多元素为m₀）为空的条件是（   ）。

A．Q->front==Q->rear                 B．Q->front!=Q->rear

C．Q->front==(Q->rear+1)% m₀         D．Q->front!= (Q->rear+1)%m₀

 

10．判断一个循环队列Q（最多元素为m₀）为空的条件是（   ）。

A．Q->front==Q->rear                 B．Q->front!=Q->rear

C．Q->front==(Q->rear+1)% m₀         D．Q->front!= (Q->rear+1)% m₀ 

 

11．判断栈S满（元素个数最多n个）的条件是（    ）。

A．s->top==0                B．s->top!=0

C．s->top==n-1               D．s->top!=n-1 

 

12．一个队列的入队顺序是a,b,c,d，则离队的顺序是（    ）。

A．a,d,cb       B．a,b,c,d      C．d,c,b,a    D．c,b,d,a

 

13．如果以链表作为栈的存储结构，则退栈操作时（    ）。

A．必须判断栈是否满           B．判断栈元素类型  

C．必须判断栈是否空           D．对栈不作任何判断

 

14．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（   ）结构。

A．堆栈      B．队列      C．数组      D．先性表

 

15．一个递归算法必须包括（  ）。

A．递归部分          B．终止条件和递归部分           

C．迭代部分       D．终止条件和迭代部分

 

16．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（    ）。

A．x=top->data; top=top->next;    B．x=top->data; 

C．top=top->next; x=top->data;    D．top=top->next; x=data;

 

17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（    ）。

A．r=f->next;    B．r=r->next;   C．f=f->next;   D．f=r->next;

 

18．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（  ）。

A．f->next=s; f=s;       B．r->next=s;r=s; 

C．s->next=r;r=s;        D．s->next=f;f=s;

 

19.以下陈述中正确的是（     ）。

A．串是一种特殊的线性表        B．串的长度必须大于零

C．串中元素只能是字母          D．空串就是空白串

 

20．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（  ）。

A．求子串                     B．连接    

 C．匹配                      D．求串长

 

21．串是（     ）。

  A．不少于一个字母的序列      B．任意个字母的序列

  C．不少于一个字符的序列      D．有限个字符的序列      

 

22．串的长度是指（     ）。

A．串中所含不同字母的个数    B．串中所含字符的个数

C．串中所含不同字符的个数    D．串中所含非空格字符的个数

 

23. 若串S==“English”，其子串的个数是（      ）。

  A．9       B．16         C． 36         D．28

 

24．下面关于串的叙述中，不正确的是（     ）。

A．串是字符的有限序列       

B．空串是由空格构成的串       

C．模式匹配是串的一种重要运算

D．串即可以采用顺序存储，也可以采用链式存储   

 

25．串与普通的线性表相比较，它的特殊性体现在（    ）。

A．顺序的存储结构             B．链接的存储结构  

C．数据元素是一个字符         D．数据元素可以任意

 

26．空串与空格串（       ）。

A．相同         B．不相同      C．可能相同   D．无法确定

 

27．两个字符串相等的条件是（    ）。

   A．两串的长度相等     

B．两串包含的字符相同

   C．两串的长度相等，并且两串包含的字符相同

   D．两串的长度相等，并且对应位置上的字符相同

 

28．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（    ）存储比较合适（     ）。

A．链式        B．顺序        C．堆结构     D．无法确定        

 

29.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（     ）。

A．64      B．28       C．70             D．90

 

30．稀疏矩阵采用压缩存储的目的主要是（  ）。

A．表达变得简单                B．对矩阵元素的存取变得简单   

C．去掉矩阵中的多余元素        D．减少不必要的存储空间的开销

 

31．一个非空广义表的表头（     ）。

  A．不可能是原子                 B．只能是子表

  C．只能是原子                   D．可以是子表或原子      

 

32．常对数组进行的两种基本操作是（     ）。

A．建立与删除                   B．索引与、和修改

C．查找和修改                   D．查找与索引

 

33. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（      ）。

  A．1140        B．1145       C． 1120         D．1125

 

34．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a_9,2在一维数组B中的下标是（    ）。

A．41             B．32            C．18           D．38

 

35．一个非空广义表的表头（   ）。

A．不可能是子表            B．只能是子表          

C．只能是原子              D．可以是子表或原子

 

二、填空题

1．栈是限定在表的一端进行插入和删除操作的线性表，又称为                。

2．队列的特性是               。

3．往栈中插入元素的操作方式是：先                  ，后                  。

4．删除栈中元素的操作方式是：先                  ，后                  。

5．循环队列队头指针在队尾指针         位置，队列是“满”状态

6．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针           ，当删除一个元素队列时，头指针            。

7．循环队列的引入，目的是为了克服                  。

8．向顺序栈插入新元素分为三步：第一步进行           判断，判断条件是                 ；第二步是修改               ；第三步是把新元素赋给          。同样从顺序栈删除元素分为三步：第一步进行            判断，判断条件是           。第二步是把            ；第三步                 。

9．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为              。

10．一个递归算法必须包括          和            。

11．判断一个循环队列LU（最多元素为m₀）为空的条件是                。

12．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的             ，而对于后者，进入栈的元素为   

          ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是                      。

16．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行________和h=s;操作。(结点的指针域为next)

17．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和________。(结点的指针域为next)

18．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为________和r=s; (结点的指针域为next)

19．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为________。 (结点的指针域为next)

20．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是          。

21．串的两种最基本的存储方式是                和                  。

22．空串的长度是          ；空格串的长度是               。

23．需要压缩存储的矩阵可分为              矩阵和              矩阵两种。

24．设广义表L=（（），（）），则表头是          ，表尾是              ，L的长度是           。

25．广义表A（（a,b,c）,(d,e,f)）的表尾为             。

26．两个串相等的充分必要条件是_______             ___。

27．设有n阶对称矩阵A，用数组s进行压缩存储，当i³j时，A的数组元素a_ij相应于数组s的数组元素的下标为__  _____。（数组元素的下标从1开始）

28．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。

 

三、问答题

1．简述栈和一般线性表的区别。

 

2．简述队列和一般线性表的区别。

 

3．链栈中为何不设头结点？

 

4．利用一个栈，则：

（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。

（2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。

 

5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？

 

6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有几种？

 

7．写出以下运算式的后缀算术运算式

⑴ 3x2+x-1/x+5

⑵ (A+B)*C-D/(E+F)+G

 

8．在什么情况下可以用递归解决问题？在写递归程序时应注意什么？

 

9． 简述广义表和线性表的区别和联系。

 

四、程序填空题

1．在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。

define TRUE 1;

define FALSE 0;

define MAXSIZE 100;

typedef charelemtype;

typedef struct

{

           Elemtype queue [MAXSIZE];

           int front,rear;

        }sequeuetype;

Sequeuetype Q;

int encqueue(sequeuetype*Q,elemtype x)

{

if (    ( 1 )   )

{

Printf(〝The cicular queue is full!\n〞);

return(FALSE);

}

else

{

           (2)    

           (3)     

       return(TRUE);

               }

} 

elemtype  del_cqueue(sequeuetype *Q)

{

     if    (    (4)     )

     {

           Printf(〝The queue is empty !\n〞)

           return(NULL);

     }

     else

     {

               (5)    

           Return(Q->queue[Q-＞front]);

        }

}  

   

2.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。 

int write(LinkQueue *q)

        {QueueNode *p;

          if (q->front==q->rear)　          

             {printf(“underflow”);

               exit(0);}

           while (q->front->next != NULL)

                {p=q->front->next;

                   (1)                      

                  printf(“%4d”,p->data);

                   (2)            

                }

           （3）                     ;　   

            }

 

五、综合题

 1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？

  

 2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；

（1）初始化队列initqueue(Q):建立一个新的空队列Q。

（2）入队列enqueue(Q,x):将元素x插入到队列Q中。

（3）出队列delqueue(Q):从队列Q中退出一个元素。

（4）取队首元素gethead(Q):返回当前队首元素。

（5）判断队列是否为空：emptyqueue(Q)。

（6）显示队列中元素：dispqueue(Q)。

 

 六、完成：实验2――栈、队列、递归程序设计

根据实验要求（见教材P₂₀₃）认真完成本实验，并提交实验报告。