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、可以顺序存储                  B、数据元素是一个字符

C、可以链接存储                  D、数据元素可以是多个字符

4、串是任意有限个    D    。

   A、符号构成的集合                B、符号构成的序列

C、字符构成的集合                D、字符构成的序列

5、已知模式串T=’abcdabcd’,则其next数组值为   B     。

   A、00123412                      B、01111234

C、01232412                      D、11213412

6、二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、…、8，列下标n个] X         110=[9i-108n=9j-10]8k1、2、…、10。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素的    B    的起始地址相同。设每个字符占一个字节。

   A、A[8，5]      B、A[3，10]      C、A[5，8]       D、A[0，9]

7、数组SZ[-3..50，0..10]含有元素数目为   B     。

   A、88           B、99           C、80            D、90

8、稀疏矩阵一般的压缩存储方法有   C     两种。

   A、二维数组和三维数组            B、三元组和散列表

C、三元组和十字链表              D、散列表和十字链表

9、一个nⅹn的对称矩阵，如果以行或列为主序放入内存，则其容量为   C     。

   A、nⅹn                          B、nⅹn/2

C、（n+1）ⅹn/2                   D、（n+1）ⅹ(n+1)/2

10、对数组经常进行的两种基本操作是   C     。

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

C、查找与修改                    D、查找与索引

11、二维数组A[10..20，5..10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是    A    。

   A、1208           B、1212        C、1368         D、1364

 

二、填空题

 1、两个字符串相等的充分必要条件是   长度相等且对应位置上字符相同  。

 2、字符在串中的位置，即是字符在该序列中的  序号。

 3、串是指   含n个字符的有限序列且n>=0 。

 4、设有串S1=’I  an  a  student’,S2=’st’,其index(S1,S2)=   8     。

 5、含零个字符的串称为  空   串，用  Φ   表示；其他串称为  非空  串。任何串中所含的  字符  的个数称为该串的长度。

 6、一个串中任意个连续字符组成的子序列称为该串的  子  串，该串称为它的所有子串的  主  串。

 7、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若一行序为主序顺序存储，则元素a[45，68]的存储地址为 9174   ；若以列序为主序存储，则元素a[45，68]的存储地址为   8788   。

 8、数组结构是由固定数量的且由一个值和一组下标组成的数据元素构成，其元素间的下标关系具有  上下界约束及下标有序   。

 9、一维数组的逻辑结构是 线性结构   ，存储结构是  顺序结构  ；对二维或多维数组，分为按  以行为主序  和  以列为主序  两种不同的存储方式。

10、需要压缩存储的矩阵可分为  特殊  矩阵和  稀疏  矩阵两种。

11、数组元素间的关系由  下标 来限定。

12、有一个8ⅹ8的下三角矩阵A，若采用行序为主序顺序存储于一维数组a[1..n]，则n的值为  36 。

 

三、判断题

 1、稀疏矩阵压缩存储后，必会失去随机存取的功能。              （对）

 2、数组是同类型值的集合。                （错）

 3、 数组是一种复杂的数据结构；数组元素之间的关系既不是线性的，也不是树形的。（ 对 ）