数据结构习题及答案

1、第1章 算法一、选择题1. 算法的时间复杂度是指（ ）。A）执行算法程序所需要的时间 B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2. 算法的空间复杂度是指（ ）。A）算法程序的长度 B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数3.下面（ ）的时间复杂度最好（即执行时间最短）。A）O(n ) B）O() C）O(n ) D）O(n2)4.下面累加求和程序段的时间复杂度为（ ）。int sum(int a,int n) int i, s=0;for (i=0;i<n;i+) s+=ai;return s; A）O

2、(1 ) B）O( ) C）O(n ) D）O(n2)5.下面是将两个n阶矩阵a与b相加的结果存放到n阶矩阵c中的算法，该算法的时间复杂度为（ ）。void matrixadd(int a,int b,c,int n) int i,j; for (i=0;i<n;i+)for(j=0;j<n;j+) cij=aij+bij;A）O(1 ) B）O() C）O( n ) D）O(n2)6.下面程序段的时间复杂度为（ ）。int i=0,s1=0,s2=0;while(i<n) if(i%2) s1+=i; else s2+=i; i+; A）O(1 ) B）O( ) C）O(n

3、 ) D）O(n2)7.下面程序段的时间复杂度为（ ）。int prime(int n) int i=1;int x=(int)sqrt(n);while(i<=x) i+;if(n%i=0)break;if(i>x) return 1;else return 0;A）O(1 ) B）O() C）O(n ) D）O() 8.下面程序段的时间复杂度为（ ）int fun(int n) int i=1,s=1; while(s<n) i+;s+=i; return i;A）O(n/2) B）O() C）O(n ) D）O()9.下面程序段的时间复杂度为（ ）int i,j,m,n

4、,a;for(i=0;i<m;i+) for(j=0;j<n;j+) aij=i*j;A）O(m2) B）O(n2 ) C）O(m*n ) D）O(m+n)10. 下面程序段的时间复杂度为（ ）int sum1(int n) int i,p=1,s=0; for(i=1;i<=n;i+) p*=i; s=s+p; return s;A）O(1 ) B）O() C）O(n ) D）O(n2)二、填空题1.算法复杂度主要包括时间复杂度和 复杂度。2.一个算法的时间复杂度的计算式为 ( 3n2+2n+5 ) / n ，其数量级表示为 。3.从一维数组an中顺序查找出一个最大值元素的

5、平均时间复杂度为 ，读取一个二维数组bmn中任一元素的时间复杂度为 。4.在下面程序段中，s = s+p语句的执行次数为 ，p*=j 语句的执行次数为 ，该程序段的时间复杂度为 。int i=0, s=o; while(+i <=n) int p=1; for(int j=1; j<=i ; j+ ) p*=j ; s=s+p ; 5. 通常用平均性态分析和 两种方式来确定一个算法的工作量。三、 简答题3. 什么是算法？4. 算法的基本特征是什么？5. 算法的两种基本要素是什么？6. 递归是算法的基本方法之一，其基本思想是什么？7. 算法的描述方法有多种，试说出任意三种方法。四、编

6、写出求下列问题的算法1.比较两个整型数据a1与a2的大小，对于a1 > a2、a1 = a2、a1< a2这三种不同情况应分别返回“>”、“=”、“<”字符。2.求一维double型数组an中的所有元素之乘积。3.假定一维整型数组an中的每个元素值x均在0，200区间内，分别统计出落在0x < 20、20x<50、50x<80、80x<130、13 x200各区间内的元素个数。参考答案一、单选题1.C 2.C 3.B 4.C 5.D 6.C 7.D 8.D 9.C 10.C二、填空题1. 空间 2. O(n) 3.O(n)，O(1) 4. n，n

7、(n+1)/2，O(n2) 5. 最坏情况复杂性三、简答题1. 答案：所谓算法是指解题方案的准确而完整的描述。2. 答案：算法的基本特征为：1)可行性；2)确定性；3)有穷性；4)拥有足够的情报。3. 答案：算法通常由两种基本要素组成；一是对数据对象的运算和操作；二是算法的控制结构。4. 答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。5.答案：一个算法可以用多种方式来描述，如自然语言、

8、程序语言、流程图等。四、算法设计1.比较两个整型数据a1与a2的大小。char compare(int a1,int a2)if(a1>a2)return ">"elase if(a1=a2)return "=" elase return "<"2.求一维double型数组an中的所有元素之乘积。double product(dluble a,int n)double p=1;for(int i=0;i< n;i+)p=p*ai;return p;3.统计数组an中的每个元素值x分别落在0x<20、20x

9、<50、50x< 80、80x<130、130x200各区间内的元素个数。int count(int a,int n,int c5) /用c5保存统计结果 int d5=20,50,80,130,201; /用d5保存各统计区间上限 int i,j; for(i=0;i<n;i+)ci=0; for(i=0;i<n;i+) if(ai<0; | ai>200) return 0; /数组中数据有错，统计失败 for(j=0;j< 5;j+) if(ai<dj) break; /查找ai所在区间 cj+; /使统计相应区间的元素数增1 ret

10、urn 1; /表示统计成功第2章 数据结构的基本概念一、 单选题1.一个数据结构可形象地表示成B=(D,R)，其中D是（）的有限集合，R是D上的（）有限集合。 A）算法 B）数据元素 C）数据操作 D）逻辑结构 A）操作 B）映像 C）存储 D）关系2. 数据结构在计算机存储空间中的存放形式称为（ ）。A）数据元素之间的关系 B）数据结构C）数据的存储结构 D）数据的逻辑结构3. 下列叙述中正确的是（ ）。A）一个逻辑结构只能有一种存储结构B）数据逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑结构可以有多种存储结

11、构，且各种存储结构影响数据处理的效率4. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A）逻辑 B）存储 C）逻辑和存储 D）物理5. 在存储数据时，通常不仅需要存储各数据元素的值，而且还要存储（ ）。A）数据的处理方法 B）数据元素的类型 C）数据元素之间的关系 D）数据的存储方法6. 如果一个非空的数据结构满足两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（ ）。A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构7. 数据的（ ）包括插入、删除、查找、更新、排序等操作类型。A）存储结构 B）逻辑结构C）基本运算 D）算法描述8.

12、 数据的存储结构是指（ ）。A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示C）存储在外存中的数据 D）数据在计算机中的顺序存储方式9. 在决定选取何种存储结构时，一般不考虑（ ）。A）结点个数的多少 B）各结点的值如何C）对数据有哪些运算 D）所用编程语言实现这种结构是否方便10.以下说法正确的是（ ）。A）数据元素是数据的最小单位 B）数据项是数据的基本单位C）数据结构是带结构的各数据项的集合D）一些表面上很不相同的数据，可以有相同的逻辑结构11.在数据结构中，从逻辑上可以把数据结构分成（ ）。A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构

13、和外部结构12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。A）数据元素具有同一特点 B）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C）每个数据元素都一样D）数据元素所包含的数据项的个数要相等二、填空题1.数据的基本单位是 ，数据的最小单位是 。2. 一种数据的逻辑结构，根据需要可以表示成顺序、 、 和散列四种基本存储结构。3. 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据分为 两大类型。4. 在一个线性结构中插入或删除任何一个结点后还应是 。5.一种数据结构的元素集合为D，它在D上的二元关系R为：D=a,b,c,d,e,f,g,

14、hR=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>则该数据结构具有 结构。6.一种数据结构的元素集合为D，它在D上的二元关系R为：D=a,b,c,d,e,f,g,hR=<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>则该数据结构具有 结构。7.数据的逻辑结构分为线性结构和非线性结构，其中的非线性结构有 两种基本类型。三、 简答题1. 数据结构主要研究的三个问

15、题是什么？2. 一个数据结构应包含两方面的信息是什么？3. 简述数据存储结构中的顺序存储方式。4. 简述数据存储结构中的链式存储方式参考答案一、单选题1.B，D 2. C 3.D 4.A 5.C 6.A 7.C 8.B 9.B 10.D 11.C 12.B二、填空题1. 数据元素，数据项 2. 链式、索引 3. 线性结构与非线性结构 4. 线性结构5. 线性 6.非线性（或树形）7. 树和图三、简答题1. 答案：数据结构主要研究的三个问题是：数据的逻辑结构，数据的存储结构，对各种数据结构进行的运算。2. 答案：一个数据结构应包含两方面的信息：表示数据元素的信息；表示各数据元素之间的前后件关系。

16、3. 答案：在数据的存储结构中，顺序存储方式的含义如下：顺序存储方式：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。4. 答案：在数据的存储结构中，链式存储方式的含义如下：链式存储方式：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，不要求逻辑上相邻的数据元素在物理位置上也相邻。第3章 线性表及其存储结构一、 单选题1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1 i n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i2. 在一个长度为n的顺序存

17、储的线性表中，删除第i个元素（1 i n+1）时，需要从前向后依次前移（ ）个元素。A）n-i B）ni+1 C）ni-1 D）i3. 在一个长度为n的顺序表中，存在值为x的元素。在此表中用顺序搜索法，查找值为x的元素，在等概率情况下，查找成功时的平均查找长度为（ ）。A）n B）n/2 C）(n+1)/2 D）(n - 1)/24. 在一个长度为n的顺序表中，删除值为x的元素时，需要比较元素的次数和移动元素次数的和为（ ）。A）n/2 B）(n+1)/2 C）n D）n+15. 在一个顺序表的表尾，插入一个元素时的时间复杂度为（ ）。A）O(1) B）O() C）O(n) D）O(n2)6.

18、 在一个顺序表的任意位置，插入一个元素的时间复杂度为（ ）。A）O(1) B）O() C）O(n) D）O(n/2)7. 线性表的顺序存储比链式存储最有利于进行（ ）操作。A）查找 B）表尾插入或删除C）按值插入或删除 D）表头插入或删除8. 线性表的链式存储比顺序存储最有利于进行（ ）操作。A）查找 B）表尾插入或删除C）按值插入或删除 D）表头插入或删除9. 在一个单链表中，若要在pre所指向的结点之后插入一个新结点，则相继修改（ ）个指针域的值。A）2 B）1 C）3 D）410. 在带表头结点的单链表中，插入一个新结点所用算法的时间复杂度为（ ）。A）O(1) B）O() C）O(n)

19、 D）O(n/2)11.以下关于线性表的链式存储结构的叙述中，正确的是（ ）。A）存储密度大B）逻辑上相邻的结点物理上不必相邻C）可以通过计算直接确定第i个结点的存储地址D）插入、删除运算操作不方便12.带头结点的单链表H为空的判定条件是（ ）。A）H=NULL B）H->next=NULLC）H->next=H D）H!=NULL13.不带头结点的单链表H为空的判定条件是（ ）。A）H=NULL B）H->next=NULLC）H->next=H D）H!=NULL14.在一个带头结点的单链表H中，若要向表头插入一个由指针p指向的新结点，则应执行的操作是（ ）A）H=

20、p;p->next=H; B）p->next=H;H=p;C）p->next=H;p=H; D）p->next=H->next; H->next=p;15.非空的循环单链表H的尾结点（由p所指向）满足（ ）。A）p=NULL B）p->next=NULLC）p->next=H D）p=H16.链表不具备的特点是（ ）。A）插入删除不需要移动元素 B）可随机地访问任一结点C）不必事先估计存储空间 D）所需空间与其长度成正比17.设线性表有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现的效率更高。A）输出第i（0in-1）个元素B）交换第0

21、个元素与第1个元素的值C）顺序输出这n个元素的值D）输出与给定值x相等的元素在线性表中的序号18.设线性表中有2n个元素，以下算法中，（ ）在单链表上实现要比在顺序表上实现效率更高。A）删除所有值为X 的元素B）在最后一个元素的后面插入一个新元素C）顺序输出前k个元素D）交换第i个元素和第2ni-1个元素的值（i = 0，1，n-1）二、填空题1. 在线性表中，第一个结点 前件，其余每个结点有且只有 个前件；最后一个结点 后件，其余每个结点有且只有 个后件。2. 数据元素在线性表中的位置只取决于它们自己的 。 3. 线性表中结点的个数 n 称为线性表的 。当 n=0时，称为 。4. 用一维数组

22、存放线性表时，数组的基本类型要与线性表中数据元素的类型 。5. 线性表的顺序存储结构存在插入、删除操作时需 数据元素的缺点。6. 线性表的两种存储结构分别是 和 。7. 线性表的顺序存储结构称为 ；线性表的链式存储结构称为 。8. 对线性单链表进行插入操作时，没有发生数据元素的 ，只是改变了有关结点的 。 9. 在线性单链表中删除一个元素后，不需要 表中的数据元素，只需改变被删除元素所在结点的 的指针域即可。10. 在带表头结点的单链表中，查找第i个结点。只能从单链表的 ，沿着结点的 ，直到搜索到第i个结点为止。11. 在单链表中，若一个元素所在结点的地址为p，则其后继（件）结点的地址为 。1

23、2. 在单链表中，删除指针p所指向结点的后继结点时，需要把 的值赋给p->next指针域。 13. 在单链表中指针p所指结点的后面，插入一个指针q所指的结点时，首先把 的值赋给q->next，然后把 的值赋给p->next。14. 在一个带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。15. 在一个不带表头结点的单链表的表头插入或删除，与在其他位置插入或删除的操作过程是否相同？ 。 16. 在双向链表中的每一个结点，包含有两个指针域，一个指向 结点，另一个指向其 结点。17. 在一个双向链表中，通过一个结点的prior 和 next指针域，能

24、够分别访问到该结点的 和 结点。 18.由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的 。三、简答题1. 非空线性表的结构特征是什么？2线性表的顺序存储结构具有哪两个基本特点？3. 用一维数组存放线性表时，应注意什么？4. 简述线性表顺序存储的优点和缺点。5. 什么是线性表的链式存储结构？6. 在带头结点的单链表中与在顺序表中，查找与给定元素值item相等的结点的操作有何不同？7. 带表头结点的循环链表与前面所讨论的单链表相比具有哪两个特点？四、算法设计1. 分别编写在顺序表和链表中统计出值为x的元素个数的函数，统计结果由函数值返回。

25、2. 分别编写在顺序表和带表头结点的单链表中删除其值等于x的所有元素的函数。3. 编写在单链表中删除具有重复值的多余结点，使每个结点的值均不同的函数。参考答案一、单选题1.B 2.A 3.C 4.C 5.A 6.C 7.B 8.D 9.A 10.C11.B 12.B 13.A 14.D 15.C 16.B 17.A 18.A 二、填空题1. 没有，1，没有，1 2. 序号3. 长度，空表 4. 相同5. 移动大量 6. 顺序存储结构，链式存储结构7. 顺序表，线性链表 8. 移动，指针域9. 移动，前一个结点 10. 头指针出发，链域逐个向下11. p->next 12. p->n

26、ext->next13. p->next，q 14. 相同15. 不相同 16. 前件，后件17. 前件，后件 18. 运算统一三、简答题 1. 答案：非空线性表的结构特征为： 有且只有一个根结点 a1 ,它无前件； 有且只有一个终端结点 an ,它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。2. 答案：线性表的顺序存储结构具有如下两个基本特点： 线性表中所有元素所占的存储空间是连续的； 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。3. 答案：用一维数组存放线性表时，应注意数组的基本类型，要与线性表中数据元素的类型相同，而且该一维数组

27、的长度，通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算。4. 答案：线性表顺序存储结构的优点是：简单、存储密度大、空间利用率高，对表中任意元素可直接确定其存储地址，随机访问存取效率高。缺点是，在顺序表中进行插入与删除操作时，需大量移动数据元素，时间开销大；再者，在顺序存储结构下，线性表的长度估计困难，并且当有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。5. 答案：假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于

28、指向该结点的前一个或后一个结点（即前件或后件）。通过每个结点的指针域，将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。6答案：在带表头结点的单链表中进行查找操作，不能像在顺序表中那样根据序号直接访问表中的元素，而只能依据给定数据元素值item，在带表头结点的单链表中从头指针出发，沿着结点的链域逐个向下进行查找。若查找成功，则返回首次找到的结点的地址。若查找失败，则返回NULL。 7答案：带表头结点的循环链表与前面所讨论的单链表相比具有以下两个特点： 循环链表的头结点的数据域为任意或者根据需要来设置，头结点的指针域指向线性表的第一个元素的结点（首结点）。头指针指向表头结点

29、。 循环链表中最后一个结点的指针域不是NULL，而是指向表头结点。即在循环链表中，没有空指针，所有结点的指针构成了一个环状链。四、算法设计1. 算法由函数Count1( ) 和Count2( )所示：/ Count1( )从顺序表上统计出值为x的元素个数的算法 int Count1(SeqList &L,ElemType x ) /使用&的参数L为引用参数 int i=0,j; for(j=0;j<L.length;j+) if(L.listj=x)i+; return i; / Count2从单链表上统计出值为x的元素个数的算法 int Count2(LinkList

30、&H,ElemTtype x) node *p=H.head->next; /将指向第1个结点的指针赋给p int i=0; /将i作为统计变量 while(p!=NULL) if(p->data=x)i+; p=p->next; return i;2. 算法由函数Delete1( )和Delete2( ) 所示：/Delete1( )从顺序表中删除具有给定值x的所有元素 void Delete1(SeqList &L,ElemType x) int j,i=0; while(i<L.length) if(L.listi=x) for(j=i+1;j&l

31、t;L.length;j+) L.listj-1=L.listj; L.length-; else i+; / Delete2( )从单链表中删除具有给定值x的所有元素 void Delete2(LinkList &H,ElemType x) node *q,*p=H.head; /将指向附加头结点的指针赋给p while(p->next!=NULL) q=p->next; if(q->data=x) p->next=q->next; /删除p 的后继结点，即q 结点 delete q; else p=p->next; 3. 算法由Delete3(

32、)所示：/ Delete3( )从单链表中删除具有重复值的多余结点，可使所有结点的值均不同 void Delete3(LinkList &H) node *p=H.head; /p链表的第1个结点 while(p!=NULL) node *t1=p,*t2=p->next; /t2指向待处理的结点 while(t2!=NULL) if(t2->data=p->data) /删除t2结点 t1->next=t2->next; delete t2; t2=t1->next; /t2指向新的结点 else t1=t2; t2=t2->next; p=

33、p->next; /p指向下一个结点 第4章 栈和队列一、单选题1.下列叙述中正确的是（ ）。A）线性表是线性结构 B）栈与队列是非线性结构C）线性链表是非线性结构 D）树是线性结构2.下列关于栈的叙述中正确的是（ ）。A）在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是先进后出的线性表3.栈的插入和删除操作在（ ）进行。A）栈顶 B）栈底 C）任意位置 D）指定位置4.当利用大小为N的一维数组，顺序存储一个栈时，用top表示栈顶指针（指示器），用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。A）top+; B）top-;

34、C）top=0; D）top=N-1;5. 利用数组aN顺序存储一个栈时，用top表示栈顶元素的下标位置，用top=-1表示栈空，用top=N-1表示栈满，则该数组所能存储栈的最大长度为（ ）。A）N-1 B）N C）N+1 D）N+2 6. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=N+1表示栈空，则该数组所能存储栈的最大长度为为N，则表示栈满的条件为（ ）。A）top=1; B）top=-1;C）top=0; D）top>1;7. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作是（ ）。A）a-

35、top=x; B）atop-=x; C）a+top=x; D）atop+=x;8. 利用数组aN顺序存储一个栈时，用top表示栈顶指针，用top=-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作是（ ）。A）return a-top; B）return atop-; C）return a+top; D）return atop+;9. 假定一个链栈的栈顶指针用top表示，则该链栈为空的条件是（ ）。A）top!=NULL; B）top=top->next;C）top=NULL; D）top!=top->next;10.假定一个链栈的栈顶指针用top表示，每个结点的结构由

36、一个数据域data和一个指针域组成，当p指向的结点进栈时，执行的操作为（ ）。A）p->next=top;top=top->next; B）top=p;p->next=top;C）p->next=top->next;top->next=p; D）p->next=top;top=p;11.假定一个链栈的栈顶指针用top表示，每个结点的结构由一个数据域data和一个指针域组成，退栈时所执行的指针操作为（ ）。A）p->next=top; B）top=top->data;C）top=top->next; D）top->next=top

37、->next->next;12.若让元素1，2，3依次进栈，则出栈次数不可能出现（ ）的情况。A）3，2，1 B）2，1，3 C）3，1，2 D）1，3，213.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（ ）的情况。A）3，2，1，4 B）2，1，4，3 C）4，3，2，1 D）1，4，2，314.下列关于队列的叙述中正确的是（ ）。A）在队列中只能插入数据 B）在队列中只能删除数据C）对列是先进先出的线性表 D）队列是先进后出的线性表15.在一个顺序循环队列中，队头指针指向队头元素的（ ）位置。A）前一个 B）后一个 C）当前 D）最后16. 在一个顺序循环队列中，队

38、尾指针指向队尾元素的（ ）位置。A）前一个 B）后一个 C）当前 D）最后17.从一个顺序循环队列中删除元素时，首先需要( )。A）前移队头指针 B）取出队尾指针所指位置上的元素C）后移队头指针 D）取出队头指针所指位置上的元素18.假设一个顺序循环队列的队头指针和队尾指针分别用front和rear表示，则判别队空的条件为（ ）。A）front+1=rear B）rear+1=frontC）front=0 D）front=rear19.假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，则判断队列满的条件为（ ）。A）(rear-1)%N=front B）

39、(rear+1)%N=frontC）(front-1)%N=rear D）(front+1)%N=rear20. 假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当元素x入队时所执行的操作为（ ）。A）a+rear%N=x; B）ar+%N=x;C）a-rear%N=x; D）arear-%N=x;21. 假设一个顺序循环队列存储于数组aN中，其队头指针和队尾指针分别用front和rear表示，已知队列未满，当出队并返回队头元素时所执行的操作为（ ）。A）return a+rear%N; B）return a-rear%N;C）retur

40、n a+front%N; D）return afront+%N;22.假设一个链接队列的队头指针和队尾指针分别为front和rear，则判别队列空的条件为（ ）。A）front=rear B）front!=NULLC）rear!=NULL D）front=NULL23. 假设一个链接队列的队头指针和队尾指针分别为front和rear，每个结点由一个数值域data和一个指针域next构成，当出队时，所进行的指针操作为（ ）。A）front=front->next; B）front->next=rear;rear=rear->next;C）rear=rear->next;

41、D）front=front->next;front->next=rear;24.以下哪一个不是队列的基本运算（ ）。A）从队尾插入一个新元素 B）从队列中删除第i个元素C）判断一个队列是否为空 D）读取队头元素的值25.栈和队列的共同特点是（ ）。A）都是先进先出 B）都是先进后出C）都只允许在端点处插入和删除元素 D）没有共同点26.一个队列的入队序列是1，2，3，4，在队列的出队序列是（ ）。A）4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，127.下列叙述中，（ ）与在循环顺序队列中插入下一个元素有关。A）与队头指针和队尾指针的值有关B）只与队尾指针

42、的值有关，与队头指针的值无关C）只与队头指针的值有关，与队尾指针的值无关D）与曾经进行过多少次插入操作有关二、填空题1. 在栈中，允许插入与删除的一端称为 ，而不允许插入与删除的另一端称为 。2. 往栈中插入一个元素称为 运算。从栈中删除一个元素（即删除栈顶元素）称为 运算。 3.栈又称为 表，队列又称为 表。 4.在一个用一维数组aMax表示的顺序栈中，该栈所含元素的个数最少为 个，最多为 个。5.向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把新元素 到这个位置上。6.从一个顺序栈删除元素时，首先取出 ，然后再使 减1。7.队列的插入操作在 进行，删除操作在 进行。8.一个顺序循环

43、队列存于一维数组aMax中，假设队头指针和队尾指针分别为front和rear，则判断队空的条件为 ，判断队满的条件为 。9. 一个顺序循环队列存于一维数组aMax中，假设队头指针和队尾指针分别为front和rear，则求出队头指针和队尾指针的下一个位置的计算公式分别为 和 。10. 一个顺序栈存储于一维数组a 0.N-1 中，栈顶指针用top表示，当栈顶指针等于 时，则为空栈，栈顶指针等于 时，则为满栈。11.在一个链栈中，若栈顶指针等于NULL，则为 ；在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为 或该队 。12.假设一个链栈的栈顶指针为top，每个结点包含值域data和指针

44、域next，当p所指向的结点入栈时，则首先执行 操作，然后执行 操作。13. 假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（栈非空），则要把栈顶指针top修改为 的值。14.向一个顺序循环队列中插入元素时，需要首先移动 ，然后再向它所指的位置 新元素。15.在一个空链队列中，假定队头指针和队尾指针分别为front和rear，当向其插入一个新结点*p时，则首先执行 操作，然后执行 操作。16.假设front和rear分别为一个链队列的队头指针和队尾指针，则该链队列中只有一个结点的条件为 。 17.在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有 个元素。三、简答题1. 什么是栈？栈组织数据的