数据结构课后参考答案.pdf

《数据结构课后参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构课后参考答案.pdf（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单元练习1一.判 断 题 以下各题，正确的请在前面的括号打M;错误的打XM1数据的逻辑构造与数据元素本身的容和形式无关。，2 一个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体。X3数据元素是数据的最小单位。X4数据的逻辑构造和数据的存储构造是一样的。X5程序和算法原则上没有区别，所以在讨论数据构造时可以通用。，6从逻辑关系上讲，数据构造主要分为线性构造和非线性构造两类。，7数据的存储构造是数据的逻辑构造的存储映像。M8数据的物理构造是指数据在计算机实际的存储形式。乂9数据的逻辑构造是依赖于计算机的。，10算法是对解题方法和步骤的描述。二.填空题(1)数据有逻辑构造和存储构

2、造两种构造。(2)数据逻辑构造除了集合以外，还包括：线性构造、树形构造和图形构造。(3)数据构造按逻辑构造可分为两大类，它们是线性构造和非线性构造。(4)树形构造和图形构造合称为非线性构造。(5)在树形构造中，除了树根结点以外，其余每个结点只有个前趋结点。(6)在图形构造中，每个结点的前趋结点数和后续结点数可以任意多个。(7)数据的存储构造又叫物理构造。(8)数据的存储构造形式包括：顺序存储、链式存储、索引存储和散列存储。(9)线性构造中的元素之间存在一对一的关系。(1 0)树形构造构造中的元素之间存在一对多的关系,(1 1)图形构造的元素之间存在多对多的关系。(1 2)数据构造主要研究数据的

3、逻辑构造、存储构造和 算 法 或运算三个方面的容。(1 3)数据构造被定义为(D,R),其中D是数据的有限集合，R是D上的关系的有限集合。(1 4)算法是一个有穷指令的集合。(1 5)算法效率的度量可以分为事先估算法和事后统计法。(16)一个算法的时间复杂性是算法输入规模的函数。(1 7)算法的空间复杂度是指该算法所消耗的存储空间,它是该算法求解问题规模n的函数。(1 8)假设一个算法中的语句频度之和为Tn=6n+3nlog2n,则算法的时间复杂度为。nlogjiK(1 9)假设一个算法中的语句频度之和为Tn=3n+nlog2n+n2,则算法的时间复杂度为 Cn2。20数据构造是一门研究非数值

4、计算的程序设计问题中计算机的操作对象,以及它们之间的关系和运算的学科。三.选择题 1数据构造通常是研究数据的 A 及它们之间的相互联系。A.存储构造和逻辑构造 B.存储和抽象 C.联系和抽象 D.联系与逻辑 2在逻辑上可以把数据构造分成：C 。A.动态构造和静态构造 B.紧凑构造和非紧凑构造C,线性构造和非线性构造 D.部构造和外部构造 3 数据在计算机存储器表示时，物理地址和逻辑地址一样并且是连续的，称之为 C 。A.存储构造 B.逻辑构造 C.顺序存储构造 D.链式存储构造 4非线性构造中的每个结点 D LA.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D.可

5、能有多个直接前趋结点和多个直接后继结点5）链式存储的存储构造所占存储空间 A JoA.分两局部，一局部存放结点的值，另一局部存放表示结点间关系的指针B.只有一局部，存放结点的值C.只有一局部，存储表示结点间关系的指针D.分两局部，一局部存放结点的值，另一局部存放结点所占单元素 6算法的计算量大小称为算法的 C 。A.现实性 B.难度 C.时间复杂性 D,效率 7数据的根本单位是 B 。A.数据构造 B.数据元素 C.数据项 D.文件 8每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存 储 构 造 称 为 A 构造。A.顺序存储 B.链式存储 C.索引存储 D.散列存

6、储 9每一个存储结点不仅含有一个数据元素，还包含一组指针，该 存 储 方 式 是 B 存储方式。A.顺序 B.链 式 C.索引 D.散列 10以下任何两个结点之间都没有逻辑关系的是 D 。A.图形构造 B.线性构造 C.树形构造 11在数据构造中，与所使用的计算机无关的是 C 。A.物理构造 B.存储构造 C.逻辑构造储构造D.集合D.逻辑和存 12以下四种根本逻辑构造中，数据元素之间关系最弱的是 A 。A.集合B.线性构造C.树形构造D.图形构造 13与数据元素本身的形式、容、相对位置、个数无关的是数据的 A oA.逻辑构造 B.存储构造 C.逻辑实现 D.存储实现 14每一个存储结点只含有

7、一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该 存 储 方 式 是 C 存储方式。A.顺序 B.链式 C.索引 D.散列 15算法能正确的实现预定功能的特性称为算法的 AA.正确性 B.易读性 C.强健性 D.高效性 16算法在发生非法操作时可以作出处理的特性称为算法的 C 。A.正确性 B.易读性 17以下时间复杂度中最坏的是 D LA.O B.O n)C.18以下算法的时间复杂度是 D 。for(i=0n;i+)for(j=Oji n;j+)cij=i+j；A.O B.O n 19算法分析的两个主要方面是 A LA.空间复杂性和时间复杂性C.可读性和文档性

8、20计算机算法必须具备输入、输 出 和 A.计算方法C.解决问题的有限运算步骤四.分析下面各程序段的时间复杂度C.强健性 D.高效性O(log n D.O n2C.O log2nj D.O tnB.正确性和简明性D.数据复杂性和程序复杂性OB.排序方法D.程序设计方法(1)for(i=0;in;i+)for(j=O;jm;j+)Aij解：O(n*m)2 s=0;for(i=0;in;i+)for(j=O;jn;j+)s+=BiQ;sum=s;解：Q(m)T=A；A=B;B二 T;解：。4 sl(int n)int p=1,s=0;for(i=l;iv=n;i+)p*=i；s+=p；rcturn

9、(s);O(n)5 s2(int n)*=0;y=0;for(k=l;kv=n;k+)*+；for(i=l;i=n;i+)for(j=l;j=n;j+)y+;解：O(n?五.根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据构造。A=D,R，其中：D a,b,c,d,e,R=属于集合 B=,R，晶：。D=a,b,c,d,c,f)R=rR=,尖括号表示结点之间关系是有向的四生构造：3F=(D,R),其中：D=50,25,64,57,82,36,75,55,R=rR=,属于树构造 50；C=D=1,2,3，3，R=rR=(1,2),(21(2,4),(3,4而%),(4,5),(4,6)

10、园括号表示结点之间关系是有向的属于图构造 E=D,R，.D=a,b,c,d,eR=vd,b,企,属于树构一.判断题误的打XX 1X 2造。单元练习2 以下各题，正确的请在前面的括号打M;错线性表的链式存储构造优于顺序存储。链表的每个结点都恰好包 一个指针域。，3 在线性表的链式存储构造中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。X4顺序存储方式的优点是存储密度大，插入、删除效率高。X5线性链表的删除算法简单，因为当删除链中*个结点后，计算时机自动地将后续的各个单元向前移动。X 6 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。M7线性表链式存储的特点是可以用一组

11、任意的存储单元存储表中的数据元素。，8 线性表采用顺序存储，必须占用一片连续的存储单元。X 9 顺序表构造适宜于进展顺序存取，而链表适宜于进展随机存取。X 1 0 插入和删除操作是数据构造中最根本的两种操作，所以这两种操作在数组中也经常使用。填空题(1)顺序表中逻辑上相邻的元素在物理位置上必须相连。(2)线性表中结点的集合是有限的，结点间的关系是一对一关系。(3)顺序表相对于链表的优点是：节省存储和随机存取。(4)链表相对于顺序表的优点是：插入、删除方便。5 采用顺序存储构造的线性表叫顺序表。6 顺序表中访问任意一个结点的时间复杂度均为。7 链表相对于顺序表的优点是插入、删除方便；缺点是存储密

12、度处。8 在双链表中要删除结点*P,其时间复杂度为。(9)在单链表中要在结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为()(n)。(1 0)单链表中需知道头指针才能遍历整个链表。(1 1)性表中第一个结点没有直接前趋，称为开场结点。(1 2)在一个长度为n的顺序表中删除第i 个元素，要移动 n-i 个元素。(1 3)在一个长度为n的顺序表中，如果要在第i 个元素前插入一个元素，要 后 移 n-i+l个元素。(1 4)在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。(1 5)当线性表的元素总数根本稳定，且很少进

13、展插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储构造。(1 6)在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。(1 7)在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点,另一个指向其后继结点。(1 8)对一个需要经常进展插入和删除操作的线性表，采用链式存储构造为宜。(1 9)双 链 表 中，设p 是 指 向 其 中 待 删 除 的 结 点，则 需 要 执 行 的 操 作 为：p-p ri o r-n c*t=p-n c*t 0(2 0)在 如 下 列 图 的 链 表 中，假 设 在 指 针 P所 在 的 结 点 之 后 插 入 数 据 域 值 为

14、a 和 b的 两 个 结 点，则 可 用 以 下 两 个 语 句：S-n c*t-n c*t=P-n e*t;和P-n c*t=S;来实现该操作。PS三.选择题1在具有n个结点的单链表中，实 现 A 的操作，其算法的时间复杂度都是On。A.遍历链表或求链表的第i个结点 B.在地址为P的结点之后插入一个结点C.删除开场结点 D.删除地址为P的结点的后继结点2 设a、b、c为三个结点，p、10、20分别代表它们的地址，则如下的存储构造称为B 。PA.循环链表3单链表的存储密度CA.大于1B,等 于1C.小 于1D.不能确定4一个顺序存储的线性表，设每个结点占m个存储单元，假设第一个结点的地址为B,

15、则第i个结点的地址为A LA.B+(i-l)*mB.B+i*mC.B-i*mD.B+(i+l)*m5在 有n个结点的顺序表上做插入、删除结点运算的时间复杂度为B 。A.O 1B.OnC.O 滔D.O Uog2nJ 6)设Llink、Rlink分别为循环双链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是D 。BCA.P=LP-Llink=LP=NULLD.P-Rlink二 二L7两个指针P和Q,分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是 B 。A.P-ne*t=Q-ne*t B.P-ne*t=Q8用链表存储的线性表，其 优 点 是 C 。A.便于随机存

16、取C.便于插入和删除 19在单链表中，增加头结点的目的是C JoC.Q-ne*t=PB.D.D.P=Q花费的存储空间比顺序表少数据元素的物理顺序与逻辑顺序一样A.使单链表至少有一个结点C.方便运算的实现造10下面关于线性表的表达中，错误的选项是A.顺序表必须占一片地址连续的存储单元C.链表不必占用一片地址连续的存储单元B.D.标志表中首结点的位置说明该单链表是线性表的链式存储构B.D.关系。顺序表可以随机存取任一元素链表可以随机存取任一元素D11L 是线性表，LengthList L 的值是 5,经 DelList L,2 运算后，LengthListL)的 值 是 C 。A.2B.3C.4D

17、.512单链表的示意图如下:LQP指 向 链 表Q结点的前R趋 的 指 针 是 B 。A.L B.P C.Q D.R13设p为指向单循环链表上*结点的指针，则*p的 直 接 前 驱 C 。A.找不到 B.查找时间复杂度为O1C.查找时间复杂度为。n D.查找结点的次数约为n14等概率情况下，在 有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为C 。A.nB.(n-l)/2 C.n/2 D.(n+l)/215在以下链表中不能从当前结点出发访问到其余各结点的是CA.双向链表 B.单循环链表 C.单链表D.双向循环链表16在顺序表中，只要 知 道 D ，就可以求出任一结点的存储地址。A.基

18、地址 B.结点大小小17在双链表中做插入运算的时间复杂度为A.O B,On18链表不具备的特点是A 。A.随机访问C.插入删除时不需移动元素19以下关于线性表的论述，不 正 确 的 为 C.向量大小 D.基地址和结点大A oC.Om D.O lognJB.不必事先估计存储空间D.所需空间与线性表成正比C)0A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前趋和一个直接后继D.存在这样的线性表，即表中没有任何结点20在 B 的运算中，使用顺序表比链表好。A.插入 B.根据序号查找 C.删除D.根据元素查找四.分 析

19、 下 述 算 法 的 功 能ListNode*Demo 1 (LinkList L,ListNode*p)1 L是有头结点的单链表ListNode*q=L-ne*t;void QWI2能qdsn钳ili0Node*q)解：p,*q等镶表中的两个结点1返呼统区即前teA梭前趋结点地址。2交搀结1 5 施制妣显*0 P和q的值不变。五.程 序 埃 些ata=q-data;1线性裹布雌 艘 凫 阴 机 L#版带表头结点的单链表作存储。试写一算法，删除表中所有大E m i n,小于ma*的元素，试完成以下程序填空。Void delete Qklist head;datatype min,ma*)q=h

20、ead-ne*t;while(p!=NULL)if(p-datadata=ma*)q=p；P=p-ne*t;elseq-ne*t=p-ne*t;delete(p);p=q-ne*t;)2在带头结点head的单链表的结点a之后插入新元素*,试完成以下程序填空。struct node elemtype data;node*nc*t;void Ikinscrt(node*hcad,elemtype*)node*s,*p;s=new node;s-data=*;p=head-ne*t;while(p!二NULL)&(p-data!=a)p-p-ne*t;if(p二 二NULL)co u t 不存在结点

21、a!”；else s-ne*t=p-nc*t:pne*t-s:)六.算法设计题 1 写一个对单循环链表进展遍历 打印每个结点的值的算法，链表中任意结点的地址为P O解：void Show(I JstNode*P)ListNode*P;do printf(,%cn,t-data);t=t-rear;)while(t!=P);)(2)对给定的带头结点的单链表L,编写一个删除L中值为*的结点的直接前趋结点的算法。解:void delete(ListNode*L)ListNode*p=L,*q;if(L-ne*t-data=*)(printf(值为*的结点是第一个结点，没有直接前趋结点可以删除);re

22、turn;For(p-ne*t-data!=*;q=p;p=p-ne*t);/删除指针 p 所指向的结点q-ne*t=p-ne*t;delete p;(3)一个单向链表，编写一个函数从单链表中删除自第i个结点起的k个结点。解：void Dcl(nodc*hcad,int i,int k)node*p,*q;int j;if(i=l)for(j=l;j ne*t;delete p;else/删除前k个元素 p指向要删除的结点p=head;for(j=l;jnc*t;/p指向要删除的结点的前一个结点for(j=l;jne*t;/q指向要删除的结点p-ne*t=q-nc*t;delete q;(4)

23、有一个单向链表 不同结点的数据域值可能一样，其 头 指 针 为h ead,编写一个函数计算值域为*的结点个数。解：此题是遍历单链表的每个结点，每遇到一个结点，结点个数加1,结点个数存储在变量n中。实现此题功能的函数如下：int counter(head)node*head；n o d e *p;i n t n=0;p=h e a d；w h i l e(p!=N U L L)i f(p-d a t a=*)p=p-n e*t;r e t u r n (n);)5有两个循环单向链表，链头指针分别为h c a d l和h c a d 2,编写一个函数将链表h c a d l到链 表h e a d

24、2,后的链表仍是循环链表。解：此题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点起来，使之成为循环的。函数如下：n o d e *l i n k (n o d e *h e a d l,*h c a d 2)n o d e *p,*q;p=h c a d l;w h i l e (p-n e*t!=h e a d l)p=p-n e*t;q=h e a d 2;w h i l e(q-n e*t!=h e a d 2)q=q-n e*t;p-n e*t=h e a d 2;q-n e*t=h e a d l;r e t u r n (h e a d l);单元练习

25、3一.判 断 题 以下各题，正确的请在前面的括号打M;错误的打XM 0)栈是运算 受限制的线 性表。M2在栈空的情 况下，不 能 作 出 栈 操 作，否则产 生 下溢出。X3栈一定是顺序存储的线性构造。,4栈 的 特 点 是 后 进 先 出。义5空栈就是所有元素都为0的栈。X 6在C或C+语言中设顺序栈的长度为MA*LE N,则t o p=M A*L E N时表示队满。M7链 栈 与 顺 序 栈 相 比，其 特 点 之 一 是 通 常 不 会 出 现 栈 满 的 情 况。X8一个栈的输入序列为：A,B,C,D,可以得到输出序列：C,A,B,D。X9递 归 定 义 就 是 循 环 定 义。，10

26、将 十 进 制 数 转 换 为 二 进 制 数 是 栈 的 典 型 应 用 之 一。填空题1在 栈 构 造 中，允许插入、删除的一端称 为栈顶。2在 顺 序 栈 中，当 栈 顶指针t o p=-l时，表示栈空。3在 有n个 元 素 的 栈 中，进 栈 操 作 的 时 间 复 杂 度 为 C。4在 栈 中，出 栈 操 作 的 时 间 复 杂 度 为：0（1）o5表达式，求它的后缀表达式是 扰的典型应用。6在一个链栈中，假设栈顶指针等于 N U L L,则表示栈空。7向 一 个 栈 顶 指 针 为top的链栈插入-个新结点*p时，应执行 p-ne*t=top;和top=p；操作。8顺 序 栈S存

27、储 在 数 组S-data O.MA*LEN-l中，进栈操作时要执行的语句有：S-top+0 或=S-top+l9链 栈L S,指向栈顶元素的指针是 LS-ne*t。10从一个栈删除元素时，首先取出栈顶元素,然后再移动栈顶指针。11由于链栈的操作只在链表的头部进展，所以没有必要设置老结点。12顺序栈S,在 对S进展进栈操作之前首先要判断栈是否满。13顺序栈S,在 对$进展出栈操作之前首先要判断栈是否空。14假设存空间充足，筵栈可以不定义栈满运算。15链 栈LS是空的条件是 LS-ne*t=NULL。16链 栈LS的栈顶元素是链表的首匹素。17同一栈的各元素的类型一样。18假设进栈的次序是A、B

28、、C、D、E,执行三次出栈操作以后，栈顶元素为 B。19A+B/C-D*E 的后缀表达式是：A B C/+D E*-。20 四 个 元 素 按A、B、C、D顺 序 进S栈，执 行 两 次P o pS,*运 算 后，*的值是 C。三.选择题1插 入 和 删 除 只 能 在 一 端 进 展 的 线 性 表，称 为（C）oA.队列 B.循环队列 C.栈 D.循环栈2设 有 编 号 为1,2,3,4的四辆列车，顺序进入一个栈构造的站台，以下不可能的出站顺序为（D）A.1234 B.1243 C.1324 D.14233如 果 以 链 表 作 为 栈 的 存 储 构 造，则 出 栈 操 作 时 B A.

29、必 须 判 别 栈 是 否 满 B.必须判别栈是否空C.必须判 别 栈 元 素 类 型 D.队栈可不做任 何判别4元 素A,B,C,D依 次 进 栈 以 后，栈 顶 元 素 是 D A.A B.B C.C D.D5顺 序 栈 存 储 空 间 的 实 现 使 用 B）存 储 栈 元 素。A.链表 B.数组 C.循环链表 D.变量6在C或C+语 言 中，一 个 顺 序 栈 一 旦 被 声 明，其 占 用 空 间 的 大 小（：A）oA.已固定 B.不固定 C.可以改变 D.动态变化7带 头 结 点 的 链 栈LS的 示 意 图 如 下，栈 顶 元 素 是 A LSH I I 1 1 I 1 I 廿

30、 I I 扣7IA.A B.B C.C D.D8链 栈 与 顺 序 栈 相 比，有一个比较明显的 优 点 是 B 。A.插入操作 更加方便 B.通常不会出现栈满的 情况。C.不会出 现栈空的情况 D.删 除 操 作 根 加 方 便9从 一 个 栈 顶 指 针 为top的 链 栈 中 删 除 一 个 结 点 时，用*保 存 被 删 除 的 结 点，应执 行 以 下(D)命令。A.*=top;top=top-ne*t;B.top=top-ne*t;*=top-data;C.*=top-data;D.*=top-data;top=top-ne*t;10在 一 个 栈 顶 指 针 为HS的 链 栈 中

31、，将一个S指 针 所 指 的 结 点 入 栈，应执行以下(B)命令。A.HS-ne*t=S;B.S-ne*t=HS-ne*t;HS-ne*t=S;C.S-ne*t=HS-ne*t;HS=S;D.S-nc*t=HS;HS=HS-nc*t;11四 个 元 素 按A、B、C、D顺 序 进S栈，执 行 两 次P o pS,*运 算 后，栈顶元素 的 值 是 B。A.AB.BC.CD.D12元 素A,B,C,D依 次 进 栈 以 后，,栈 底 元 素 是 AA.AB.BC.CD.D13经过 以下栈 的运算后，再 执 行ReadTop(s)的 值 是 A。InitStack(s)初 始 化 栈;Push(

32、s,a);Push(s,b);Pop(s)A.a B.b C.1 D.014经 过 以 下 栈 的 运 算 后，*的 值 是 BInitStack(s)初 始 化 栈;Push(s,a);Push(s,b);ReadTop(s);Pop(s,*);A.a B.b C.1 D.015经 过 以 下 栈 的 运 算 后，*的 值 是 B。InitStack(s)初 始 化 栈;Push(s,a);Pop(s,*);Push(s,b);Pop(s,*);A.a B.b C.1 D.016经 过 以 下 栈 的 运 算 后，SEmpty(s)的 值 是 C。InitStack(s)初 始 化 栈；Pu

33、sh(s,a);Push(s,b);Pop(s,*);Pop(s,*);A.a B.b C.1 D.017向 顺 序 栈 中 压 入 元 素时，B。A.先 存 入 元 素，后 移 动 栈 顶 指 针 B.先 移 动 栈 顶 指 针，后存入元素C.谁先谁 后无关紧要 D.同时进展18初 始 化 一 个 空 间 大 小 为5的 顺 序 栈S后，S-top的 值 是 B。A.0 B.-1 C.不再改变 D.动态变化19一 个 栈 的 入 栈 次 序ABCDE,则 栈 的 不 可 能 的 输 出 序 列 是(C)A.EDCBA B.DECBA C.DCEAB D.ABCDE20 设 有 一 个 顺 序

34、 栈S,元素A,B,C,D,E,F,依 次 进 栈，如 果 六 个 元 素 出 栈 的 顺 序是B,D,C,F,E,A,则栈的容量至A.3 B.4四.应用题1设有一个栈，元素进栈的次序为：示出栈操作，写出以下出栈的操作序列。C,B,A,D,E解：IUOOOIOIO(2)1011001100(2)求后缀表达式 ABC/D解：A B -D/-A+B*C+D/E解：0A-BC*+D E/+A*(B+C)*D-E解：A B C+*D*E-(A+B)*C-E/(F+G/H)-D解：AB+C*E F G H/+/-D-8/(5+2)-6解：8 5 2+/6-六.算法设计题11：设 用 一 维 数 组sta

35、ck网表示一个堆栈,M1 o试写出其入栈操作的算法。试写出其出栈操作的算法。解：/用一整型变量top表示栈顶指针，tO|兀J素。/入栈算法：void push(char*)if(top+M)MA*LEN-l)printf(堆栈溢出！”)；elseif(top=0)(top+;s top=*;少 应 是（A）oC.5 D.6A,B,C,D,E,用I表示进栈操作，。表A,C,B,E,D假设堆栈中每个元素需占用 M个数组单元为0时表示栈为空。栈中元素从S开场存放elsetop=top+M;s top=*;出栈算法：void pop(char*)(if(top=0)printf(堆栈为空栈！);els

36、eif(top=1)*=S top;top-;else*=S top;top=top-M;)2设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。解：/设表达式在字符数组a中，使用一堆栈S 来帮助判断。int correct(char a)(stack s;InitStack(s);for(i=0;i strlen(a);i+)if(a i)=()P u s h ();elseif(a i=)(if StackEmpty(s)return 0;else调用初始化栈函教调用判栈空函数/假设栈为空返回0；否则出栈Pop(s);if(StackEmpty(s)printf(配对正确！”);e

37、lseprintf(配对错误！);调用判栈空函数/假设栈空，说明配对正确，并返回1配对错误返回0(3)设计一个将十进正整数转换为十进制数的算法，并要求上机调试通过。M：*include*includetypcdef struct stacknodeint data;struct stacknode*ne*t;Jstacknodc;typedef structstacknode*top;linkstack;void Conversion(int n)linkstack s;int*;s.top=NULL;do*=n%16;n=n/16;stacknode*p=new stacknode;p-ne

38、*t=s.top;/修改栈顶指针s.top=p;s.top-data=*;/定义栈的存储构造定义栈顶的指针栈的应用：十-十六进制转换置栈空取余数取新的商/申请新结点余数入栈while(n);printf(Hn tt转换后的十六进制数值为：”；while(s.top)/出栈处理 if(s.top-data data);elseswirch(s.top-data)case 10:printff,%cn,A,);brcak;case 11:printffc/Bbreak;case 12:printf(n%cH,C,);break;case 13:printffc/Dbreak;case 14:pri

39、ntf(%c,E);break;case 15:printffc/Fbreak;)stacknode*p=s.top;s.top=s.top-ne*t;free(p);/出栈一个余数，收回一个结)printf(nn);)void main。(int n;printffntt请输入一个十进制正整数：)；scanf(%d,&n);Conversion(n);单元练习4判 断 题 以下各题，正 确 的 请 在 前 面 的 括 号 打 错 误 的 打xM1队列是限 制在两端进展操作 的线性表。，2判 断 顺 序 队 列 为 空 的 标 准 是 头 指 针 和 尾 指 针 都 指 向 同 一 个 结 点

40、。X3在链队列上做出队操作时，会改变front指针的值。M4在循环队列中，假设尾指针rear大于头指针fro n t,其元素个数为rear-front。X5在单向循环链表中，假设头指针为h,则p所指结点为尾结点的条件是p=h。M6链队列在一定围不会出现队满的情况。X7在循环链队列中无溢出现象。X8栈和队列都是顺序存储的线性构造。X9在 队 列 中 允 许 删 除 的 一 端 称 为 队 尾。X10顺 序 队 和 循 环 队 关 于 队 满 和 队 空 的 判 断 条 件 是 一 样 的。二.填空题(1)在队列中存取数据应遵循的原则是 先进先出。(2)色弊被限定为只能在表的一端进展插入运算，在表

41、的另一端进展删除运算的线性表。(3)在队列中，允许插入的一端称为队尾。(4)在队列中，允许删除的一端称为队首 或队头。(5)队列在进展出队操作时，首先要判断队列是否为 至。(6)顺序队列在进展入队操作时，首先要判断队列是否为 遒。(7)顺序队列初始化后，front=rcar=-1。(8)解决顺序队列 小文溢出”的方法是采用循环队列。(9)循环队列的队首指针为fro n t,队尾指针为re a r,则队空的条件为 front=rear。(10)链队列 LQ为空时，LQ-front-ne*t=NULL。(1 1)设 长 度 为n的链队列用单循环链表表示，假设只设头指针，则入队操作的时间复杂度为。n

42、。(1 2)设 长 度 为n的链队列用单循环链表表示，假设只设尾指针，则出队操作的时间复杂度为 01)。(1 3)在一个链队列中，假设队首指针与队尾指针的值一样，则表示该队列为空。(1 4)设 循 环 队 列 的 头 指 针front指向队首元素，尾指针 rear指向队尾元素后的一个空 闲 元 素，队 列 的 最 大 空 间 为MA*LEN,则 队 满 标 志 为：front=(rear+l)%MA*LEN。(1 5)在一个链队列中，假设队首指针为 front,队 尾 指 针 为rear,则判断该队列只有一个结点的条件为:front=rear&front!NULL 0(或 front=rear

43、&front NULL)(1 6)向一个循环队列中插入元素时，首先要判断 队 尾 指 针,然后再向指针所指的位置写入新的数据。(1 7)读队首元素的操作不 改 变 或不影响队列元素的个数。18设循环队列的容量为4 0 序 号 从0到39，现经过一系列的入队和出队运算后，有front=ll,rcar=19,则循环队列中还有 8 个元素。L=(N+rear-front)%N=40+19-11 40=8(19 队列 Q,经 过 以 下 运 算：InitQucuc(Q)(初 始 化 队 列);InQucuc(Q,a);InQueue(Q,b);OutQueue(Q,*);ReadFront(Q,*);

44、QEmpty(Q);后的值是 0。20队列 Q 经过 InitQueue(Q)(初 始 化 队 列);InQueue(Q,a);InQueue(Q,b);ReadFront(Q,*)后，*的值是 a。三.选择题1队 列 是 限 定 在 D 进展操作的线性 表。A.中间 B.队首 C.队尾 D.端点2队 列 中 的 元 素 个 数 是(B)。A.不变的 B.可 变 的C.任 意 的D.03同 一 队 列 各 元 素 的 类 型(A)0A.必须一致 B.不能一致 C.可 以 不 一 致 D.不限制4队 列 是 一 个(C)线 性 表 构 造。A.不加限制的 B.推广了的 C.加 了 限 制 的D.

45、非5 当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为B。A.n-2B.n-1C.nD.n+16一 个 循 环 队 列 一 旦 说 明，其 占 用 空 间 的 大 小 AoA.已固定B.可 以 变 动C.不能固定D.动态变化7循 环 队 列 占 用 的 空 间(A)。A.必须连续B.不 必 连 续C.不能连续D.可以不连续8存放循环队列元素 的数组data有10个 元 素，则data数 组 的 下 标 围 是(B)0A.0.10B.0.9C.1.9 D.1.109假设进队的序列为：A,B,C,D,则出队的序列是 C)oA.B,C,D,A B.A,C,B,DC.A,B,C,D

46、 D.C,B,D,A10四个元素按：A,B,C,D顺 序 连 续 进 队Q,则队尾元素是 D。A.AB.BC.CD.D11四个元素按：A,B,C,D顺 序 连 续 进 队Q,执 行 一 次OutQueue(Q)操作后,队 头 元 素 是 B。A.A B.B C.C D.D12四个元素按：A,B,C,D顺 序 连 续 进 队Q,执 行 四 次OutQueue(Q)操作后,再 执 行QEmpty(Q);后 的 值 是 B。A.0 B.1 C.2 D.313队列Q,经过以下运算后，*的 值 是 B。TnitQueue(Q)(初始 4匕队歹);InQueue(Q,a);InQueue(Q,b);Out

47、Queue(Q,*);RcadFront(Q,*);A.a B.b14循 环 队 列SQ队满的条件是A.SQ-rear=SQ-frontC.SQ-rear=0C.0 D.1B)oB.(SQ-rear+l)%MA*LEN=SQ-frontD.SQ-front=015设链栈中结点的构造:data为数据域，ne*t为指针域，且top是栈顶指针。假设想在链栈的栈顶插入一个由指针 s所指的结点，则应执行以下 A 操作。A.s-ne*t=top-ne*t；top-ne*t=s；B.top-ne*t=s；C.s-ne*t=top；top=top-ne*t；D.s-ne*t=top；top=s；16带头 结点

48、的 链 队 列LQ示 意 图 如 下，链队列的队头 元 素 是 A LQ-frontiH I _i r n i rni i iA iLQ-rearA.A B.B C.C D.D17带头结点的 链 队 列LQ示 意 图 如 下，指向 链队列的 队头指 针 是 C LQ-frontiH nn_i i rniLQ-rearLQ-rcarHAA.LQ-front B.LQ-rearC.LQ-front-ne*t D.LQ-rear-ne*t：18)带 头 结 点 的 链 队 列LQ示 意 图 如 下，在 进 展 进 队 运 算 时 指 针LQAfront(A LQ-frontE EA.始终不改 变 B

49、.有时改 变 C.进队时改变 D.出 队时改变19队列Q,经过以下运算后，再执行QEmpty(Q)的 值 是 C。TnitQueue(Q)(初 始 化 队 列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,*);ReadQueue(Q,*);A.a B.b C.0 D.120假设用一个大小为6的数组来实现循环队列,且当前front和rear的值分别为3和0,当从队列中 删 除 一 个 元 素，再参加 两个元 素 后，front和rear的值分别为(B)。A.5和 1 B.4和 2 C.2 和4 D.1 和5四.写出程序运行的结果写 出 以下 程 序 段 的 输 出

50、 结 果 队列中的元素类型为charjovoid main()(Queue Q;InitQueue(Q);初始化队列char*=nE;y=nCn;InQueue(Q,”H”)；InQucuc(Q,nRn);TnQueue(Q,y);OutQucuc(Q,*);InQucuc(Q,*);OutQueue(Q,*);InQueue(Q,A);while(!QEmpty(Q)(OutQueue(Q,y);printf(y);)；printf(*);答：输出为”CHAR。五.程序填空假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针re a r,试填空完成向循环队列中插入一个元素为*的结点的