《数据结构》课后参考答案

1、专业资料单元练习1一.判断题（下列各题，正确的请在前面的括号内打，；错误的打X ）（，）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（，）（2） 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（义）（3）数据元素是数据的最小单位。（义）（4）数据的逻辑结构和数据的存储结构是相同的。（义）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（，）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（，）（7）数据的存储结构是数据的逻辑结构的存储映像。（，）（8）数据的物理结构是指数据在计算机内实际的存储形式。（义）（9）数据的逻辑结构是依赖

2、于计算机的。（，）（10）算法是对解题方法和步骤的描述。.填空题（1） 数据有逻辑结构和存储结构两种结构。（2） 数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构（3） 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构（4） 树形结构和图形结构合称为非线性结构。（5） 在树形结构中，除了树根结点以外，其余每个结点只有二个前趋结点。（6） 在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个（7） 数据的存储结构又叫物理结构 。（8） 数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储（9） 线性结构中的元素之间存在一对一的关系。（10）树形结构结构中的

3、元素之间存在一对多 的关系,（11）图形结构的元素之间存在多对多 的关系。（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（13）数据结构被定义为（D, R）,其中D是数据的有限集合，R是D上的 关系 的有 限集合。（14）算法是一个有穷指令的集合。（15）算法效率的度量可以分为事先估算法和事后统计法。（16） 一个算法的时间复杂性是算法输入规模的函数。（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（18）若一个算法中的语句频度之和为T （n） =6n+3nlog 2n,则算法的时间复杂度为O（nlog 2n）。（19）若一

4、个算法中的语句频度之和为T （n） =3n+nlog 2n+n2,则算法的时间复杂度为_0_(n2)。(20)数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。三.选择题(1)数据结构通常是研究数据的(A )及它们之间的相互联系。A.存储结构和逻辑结构B.(2)在逻辑上可以把数据结构分成：A. 动态结构和静态结构C.线性结构和非线性结构存储和抽象C.(C )。B.D.联系和抽象D. 联系与逻辑紧凑结构和非紧凑结构内部结构和外部结构(3)数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(C )。A. 存储结构 B.逻辑结构 C.顺

5、序存储结构D.链式存储结构(4)非线性结构中的每个结点( D )。A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D.可能有多个直接前趋结点和多个直接后继结点(5)链式存储的存储结构所占存储空间( A )。A .分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B .只有一部分，存放结点的值C .只有一部分，存储表示结点间关系的指针D .分两部分，一部分存放结点的值，另一部分存放结点所占单元素(6)算法的计算量大小称为算法的( C )。A. 现实性 B. 难度 C.时间复杂性D. 效率(7)数据的基本单位是( B )。A.数据结构B.数据元素C. 数据

6、项 D. 文件(8)每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种 存储结构称为(A )结构。A.顺序存储B. 链式存储 C. 索引存储 D. 散列存储(9)每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是(B )存储方式。A.顺序B.链式C.索引D.散列(10)以下任何两个结点之间都没有逻辑关系的是(D )。A.图形结构B.线性结构C.树形结构D.集合(11)在数据结构中，与所使用的计算机无关的是(C )。A.物理结构B.存储结构C.逻辑结构D.逻辑和存储结构(12)下列四种基本逻辑结构中，数据元素之间关系最弱的是( A )。A. 集合 B.线性结

7、构C.树形结构D. 图形结构(13)与数据元素本身的形式、内容、相对位置、个数无关的是数据的(A )。A. 逻辑结构 B.存储结构C.逻辑实现D. 存储实现(14)每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是( C )存储方式。A. 顺序 B.链式 C.索引 D.散列(15)算法能正确的实现预定功能的特性称为算法的( A )。A.正确性B.易读性C.健壮性D.高效性(16)算法在发生非法操作时可以作出处理的特性称为算法的( C )。A.正确性B.易读性C.健壮性D.高效性(17)下列时间复杂度中最坏的是( D )。一，、一 一，、

8、一 一，、 一，2、A. O (1) B. O ( n) C. O (log2n)D. O (n)(18)下列算法的时间复杂度是( D )。for (i=0;i<n;i+)for (j=0;i<n;j+)cij=i+j；A. O (1) B. O ( n)(19)算法分析的两个主要方面是( AA.空间复杂性和时间复杂性C.可读性和文档性(20)计算机算法必须具备输入、输出和(A.计算方法B.C.解决问题的有限运算步骤四.分析下面各程序段的时间复杂度(1) for (i=0;i<n;i+)for (j=0;j<m;j+)Aij解：O(n*m) s=0;for (i=0;i

9、<n;i+)for (j=0;j<n;j+)s+=Bij;sum=s;解：O(n2)(3) T=A;A=B;B=T;解：O(1)(4) s1(int n) int p=1,s=0;for (i=1;i<=n;i+) p*=i;s+=p; return(s);O(n)(5) s2(int n)一 一，、 一，2、C. O(log2n)D. O(n )°8. 正确性和简明性D.数据复杂性和程序复杂性C )。排序方法D. 程序设计方法x=0;y=0;for (k=1;k<=n;k+) x+;for (i=1;i<=n;i+)for (j=1;j<=n；j

10、+) y+;-2解：O(n )五.根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据结构(1) A= (D, R),其中：D=a, b, c, d, e,R= 解： a b 00c d e0°°属于集合(2) B= (D,R),其中：D=a,b,c,d,e,f, R=rR=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>(尖括号表示结点之间关系是有向的)解：:；b-.c 一一 e 一 f属于线性结构。(3) F= (D,R),其中:D=50,25,64,57,82,36,75,55, R=rR=

11、<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>解:属于树结构(4) C= (D,R),其中：D=1,2,3,4,5,6, R=rR=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)(园括号表示结点之间关系是有向的）属于图结构(5) E= (D,R),其中：D=a,b,c,d,e,f,g,h, R=rR=<d,b>,<d,g>,<d,a>,<b,c>,<

12、;g,e>,<g,h>,<e,f>解：f属于树结构。word完美格式单元练习2一.判断题(下列各题，正确的请在前面的括号内打，；错误的打X )(X) (1)线性表的链式存储结构优于顺序存储。(X) (2)链表的每个结点都恰好包含一个指针域。(V) (3)在线性表的链式存储结构中， 逻辑上相邻的两个元素在物理位置上并不一定紧邻。(X) (4)顺序存储方式的优点是存储密度大，插入、删除效率高。(X) (5)线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续 的各个单元向前移动。(x) (6)顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是

13、一个复杂类型。(，)(7)线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。(，)(8)线性表采用顺序存储，必须占用一片连续的存储单元。(X) (9)顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。(义)(10)插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也 经常使用。二.填空题(1) 顺序表中逻辑上相邻的元素在物理位置上必须 相连。(2) 线性表中结点的集合是有限的，结点间的关系是一对一 关系。(3) 顺序表相对于链表的优点是：节省存储和随机存取。(4) 链表相对于顺序表的优点是：插入、删除 方便。(5) 采用 顺序存储结构的线性表叫顺序表。(6

14、) 顺序表中访问任意一个结点的时间复杂度均为0(1)。(7) 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小 。(8) 在双链表中要删除已知结点 *P,其时间复杂度为0(1) q(9) 在单链表中要在已知结点 *P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为0(n)。(10) 单链表中需知道 头指针 才能遍历整个链表。(11) 性表中第一个结点没有直接前趋，称为开始 结点。(12) 在一个长度为n的顺序表中删除第i个元素，要移动 n-i个元素。(13) 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素， 要后移n- i +1 个元素。(14) 在

15、无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。(15) 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。(16) 在线性表的链式存储中，元素之间的逻辑关系是通过指针 决定的。(17) 在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点,另一个指向其后继结点。(18) 对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。(19) 双链表中，设p是指向其中待删除的结点，则需要执行的操作为： p->prior->next=p->next。(20)

16、 在如图所 示的链 表中，若在指针P所在 的结点 之后插入 数据域 值为a和b的两 个结点 ，则可 用下歹U 两个语句 ： S->next->next=P->next; 和P->next=S; 来实现该操作。三.选择题(1)在具有n个结点的单链表中， 实现(AA.遍历链表或求链表的第 i个结点C.删除开始结点)的操作，其算法的时间复杂度都是O(n)。B .在地址为P的结点之后插入一个结点D .删除地址为P的结点的后继结点(2)设a、b、c为三个结点，p、10、20分别代表它们的地址， 则如下的存储结构称为(B )。a10b20cAA.循环链表B .单链表(3)单链表的存

17、储密度( C )。A . 大于1B . 等于1(4)已知一个顺序存储的线性表，设每个结点占 则第i个结点的地址为( A )。C .双向循环链表D .双向链表C .小于1D .不能确定m个存储单元，若第一个结点的地址为B,A. P= L(7)两个指针P和Q,分别指向单链表的两个元素, 是(B )。A. P->next=Q->next B . P->next= Q C(8)用链表存储的线性表，其优点是( C )。A.便于随机存取BA. B+(i-1)*mB , B+i*mC , B-i*mD , B+(i+1)*m(5)在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为(

18、B )。A. O (1)B . O (n)C . O (n2)D . O (log2n)(6)设Llink、Rlink分别为循环双链表结点的左指针和右指针，则指针P所指的元素是双 循环链表L的尾元素的条件是( D )。B . P->Llink= L C , P= NULL D . P->Rlink=LP所指元素是Q所指元素前驱的条件.Q->next= P D . P= QC.便于插入和删除D.数据元素的物理顺序与逻辑顺序相.花费的存储空间比顺序表少(9)在单链表中，增加头结点的目的是(CA.使单链表至少有一个结点BC.方便运算的实现D结构(10)下面关于线性表的叙述中，错误的

19、是(A.顺序表必须占一片地址连续的存储单元C.链表不必占用一片地址连续的存储单元)。.标志表中首结点的位置.说明该单链表是线性表的链式存储D )关系。B .顺序表可以随机存取任-,元素D .链表可以随机存取任-,元素(11) L是线性表，已知 LengthList(L)的值是 5,经 DelList (L, 2)运算后，LengthList(L)的值是(C )。A. 2B.3C.4D.5(12)单链表的示意图如下:L指向链表Q结点的前趋的指针是(B )。A. LB.PC . QD.R(13)设p为指向单循环链表上某结点的指针，则 *p的直接前驱(C )。A.找不到B.查找时间复杂度为 O (1

20、)C.查找时间复杂度为O (n)D .查找结点的次数约为n(14)等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为(C )。A. nB . (n-1)/2 C . n/2 D . (n+1)/2(15)在下列链表中不能从当前结点出发访问到其余各结点的是( C )。A.双向链表B .单循环链表C .单链表 D .双向循环链表(16)在顺序表中，只要知道( D ),就可以求出任一结点的存储地址。A.基地址B .结点大小C .向量大小 D .基地址和结点大小(17)在双链表中做插入运算的时间复杂度为( A )。O (log 2n)A. O (1) B . O (n) C .

21、 O (n2)D(18)链表不具备的特点是( A )。A.随机访问B.不必事先估计存储空间C.插入删除时不需移动元素D .所需空间与线性表成正比(19)以下关于线性表的论述，不正确的为( C )。A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前趋和一个直接后继D.存在这样的线性表，即表中没有任何结点(20)在(B )的运算中，使用顺序表比链表好。A.插入 B.根据序号查找C .删除 D.根据元素查找四.分析下述算法的功能11) ListNode *Demo1(LinkList L,ListNode *p)/ L

22、是有头结点的单链表ListNode *q=L->next;While (q && q->next!=p)q=q->next;if (q)return q;elseError( " *p not in L " );(2) void Demo2(ListNode *p,ListNode *q)/ p,*q是链表中的两个结点DataType temp;temp=p->data;p->data=q->data;q->data=temp;解：(1)返回结点*p的直接前趋结点地址。(2)交换结点*p和结点*q (p和q的值不变)

23、。五.程序填空(1)已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除 表中所有大于 min ,小于max的元素，试完成下列程序填空。Void delete (lklist head; datatype min, max) q=head->next;while (p!=NULL) if (p->data<=min ) | | (p->data>=max )q=p; p= p->next ; else q->next= p->next ;delete (p);p= q->next ; (2)在带头结点head的单链表的

24、结点a之后插入新元素x,试完成下列程序填空。 struct node elemtype data;node * next;；void Ikinsert (node *head, elemtype x) node *s, * p;s= new node;s->data= x;p=head->next;while (p!=NULL) && ( p->data!=a ) _p=p->next;if (p=NULL) cout<< "不存在结点a!"else s->next=p->next; p->next=s;

25、六.算法设计题(1)写一个对单循环链表进行遍历(打印每个结点的值)的算法，已知链表中任意结点的 地址为P。解：void Show(ListNode *P) ListNode *t=P;do printf("%c",t->data);t=t->rear;while (t!=P);(2) 对给定的带头结点的单链表L,编写一个删除L中值为x的结点的直接前趋结点的算法。解：void delete(ListNode *L) ListNode *p=L,*q;if(L->next->data=X)printf( “值为x的结点是第一个结点，没有直接前趋结点可以删

26、除”)return;For(p->next->data!=X;q=p;p=p->next);/删除指针 p 所指向的结点q->next=p->next;delete p;(3)解：void Del(node *head,int i,int k) node *p,*q;int j;if(i=1)for(j=1;j<=k;j+)/ p=head;/ phead=head->next;delete p; else p=head;for(j=1;j<=i-2;j+) p=p->next; / p for(j=1;j<=k;j+) q=p-&g

27、t;next; / q p->next=q->next;delete q;已知一个单向链表，编写一个函数从单链表中删除自第i个结点起的k个结点。删除前k个元素指向要删除的结点指向要删除的结点的前一个结点指向要删除的结点(4) 有一个单向链表(不同结点的数据域值可能相同)，其头指针为head,编写一个函数计算彳1域为x的结点个数。解：本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1,结点个数存储在变量n中。实现本题功能的函数如下：int counter(head)node *head ; node *p;int n=0;p=head ;while(p!=NULL) if(p-

28、>data=x)n+； p=p->next; return(n);(5)有两个循环单向链表，链头指针分别为headl和head2,编写一个函数将链表headl链接到链表head2,链接后的链表仍是循环链表。解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：node *link (node *head1, *head2) node *p,*q;p=head1;while(p->next!=head1)p=p->next;q=head2;while(q->next!=head2)q=q->ne

29、xt;p->next=head2;q->next=head1;return (headl);单元练习3一.判断题(下列各题，正确的请在前面的括号内打，；错误的打 X )(，)(1)栈是运算受 限制的线 性表。(，)(2)在栈空的情 况下，不能作出栈操作，否则产 生下溢出。(义)(3)栈一定是顺序存储的线性结构。(，)(4)栈的特点是“后进先 出”。(义)(5)空栈就是所有元素都为 0的栈。(义)(6)在C或C+镭言中设顺序栈的长度为 MAXLEN则top=MAXLEN时表示队满。(，)(7)链栈与顺序 栈相比， 其特点 之一是 通常不会 出现栈 满的情 况。(义)(8)一个栈的输入

30、序列为：A,B,C,D,可以得到输出序列：C,A,B,d(义)(9)递归定义就 是循环定 义。(，)(10)将十进制 数转换为二 进制数 是栈的 典型应用 之一。二.填空题(1)在 栈结构 中，允 许插入、删除的一端称 为 栈顶 。(2)在 顺序栈 中，当 栈顶指针top=-1时，表 示 栈空 。(3)在 有n个元素的栈 中，进栈 操作的 时间复 杂度为 O (1)。(4)在 栈中，出栈操 作的时间 复杂度 为： O(1)。(5)已知表达式，求它的后缀表达式是栈的典型应用。(6)在一个链栈中，若栈顶指针等于NULL,则表示 栈空 。(7)向一个栈顶指针为top的链栈插入一个新结点*p时，应执行

31、 p->next=top ;和top=p ;操作。(8)顺序栈S存储在数组S->data0.MAXLEN-1中，进栈操作时要执行的语句有：S->top +。(或=S->top+1 )(9)链栈LS,指向栈顶元素的指针是LS->next。(10)从一个栈删除元素时，首先取出栈顶元素 ，然后再移动栈顶指针。(11)由于链栈的操作只在链表的头部进行，所以没有必要设置头 结点。(12)已知顺序栈S,在对S进行进栈操作之前首先要判断栈是否满。(13)已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。(14)若内存空间充足， 链栈可以不定义栈满运算。(15)链栈 LS是

32、空的条件是LS->next=NULL 。(16)链栈LS的栈顶元素是链表的首 元素。(17)同一栈的各元素的类型相同 。(18)若进栈的次序是 A、日G D、E,执行三次出栈操作以后，栈顶元素为B。(19) A+B/C-D*E 的后缀表达式是：ABC/+DE*- 。(20)四个元素按A、B、C、D顺序进S栈，执行两次Pop (S,x)运算后，x的值是C 。三.选择题(1)插 入和删 除只能 在一端进 行的线 性表，称为(C )。D.循环栈(2)设有编号为 能的出站顺序为(3)(4)(5)(6)(7).1234如果以链表作为.必须判别栈是.必须判别栈元1243栈的存储否满素类型元素A,B,

33、C,D依次进栈以后顺 序栈存 储空间 的实现使.链表(8) 组在C或C+语言中带头结点的链栈个顺不固定LS的示意LSC . 1324D . 1423结构，则出栈操作时( B )B.必须判别栈是否空D .队栈可不做任何判别,栈顶元素是 (D用(B )存储栈元C.循环链表序栈一旦被声明，其占C .可以改变图如下，栈顶元素是(素。D.变量用空间的大小 (A )。D.动态变化HABCDA(8)链栈与顺序栈相比，有个比较明显的优点是( B )。1, 2, 3, 4的四辆列车，顺序进入一个栈结构的站台，下列不可A.插入操作更加方便C.不会出现栈空的情况B.通常不会出现栈满的情况。D .删除操作根加方便x保

34、存被删除的结点，应(9)从一个栈 顶指针 为top的链 栈中删 除一个 结点时，用执行下列(D ) 命令。A . x=top;top=top->next;B . top=top->next;x=top->data;C . x=top->data;D. x=top->data;top=top->next;(10)在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下歹U-(B ) 命令。A . HS->next=S;B. S->next=HS->next;HS->next=S;C . S->next=HS->ne

35、xt;HS=S;D . S->next=HS;HS=HS->next;(11)四个元素按A、B、C、D顺序进S栈，执行两次Pop ( S, x)运算后，栈顶元 素的值是 (B )。A . AB.BC. CD . D(12)元素A,B,C,D依次进栈以后，栈底元素是(A )。A . AB.BC. CD . D(13)经过下列栈的运算后，再 执行ReadTop(s)的值是 (AInitStack(s)(初 始化栈)；Push(s,a);Push(s,b); Pop(s)A. a（14）经过下列InitStack(s)栈的运算后，（初始化栈）x的值是 （B ）。;Push(s,a);Pu

36、sh(s,b); ReadTop(s);Pop(s,x);A. a（15）经过下列InitStack(s)栈的运算后，（初始化栈）x的值是 （B ）。;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);A. a（16）经过下列InitStack(s)栈的运算后，SEmpty(s)的值是(C )。(初始化栈)；Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);A. a（17）向顺序栈A.先存入元中压入元素时， （素，后移动栈顶指针C.谁先谁后无关紧要B ）。B .先移动栈顶指针，后存入元素D.同时进行(18)初始化一个空间大小为5的顺序栈

37、S后，S->topC .不再改变的值是（ B ）。D.动态变化(19)个栈的入栈次序ABCDE,则栈的不可能的输出序列是（C）(20)EDCBA设有一个是 B, D, C, F,B . DECBAC . DCEABABCDE顺序栈巳A,S,元素A,B,C,D,E,F,依次进栈,则栈的容 量至少应是（A ）如果六个元素出栈的顺序四.应用题（1）设有一个栈，元素进栈的次序为: 出栈操作，写出下列出栈的操作序列。 C, B, A, D, E解： IIIOOOIOIOA, B, C, D,E,用I表不进栈操作，O表不 A, C, B, E, D IOIIOOIIOO(2) 求后缀表达式 AABA

38、C/D解：A B a C a d / -A+B*C+D/E解：0 A - B C * + D E / + A*(B+C)*D-E解：A B C + * D * E -(A+B)*C-E/(F+G/H)-D解：A B + C * E F G H / + / - D - 8/(5+2)-6解：852 + / 6 -六.算法设计题(1)设用一维数组stackn表示一个堆栈，若堆栈中每个元素需占用Mt数组单元(M>1试写出其入栈操作的算法。试写出其出栈操作的算法。解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从 S 1开始存 放元素。/入栈算法：void push (cha

39、r x) if (top+M)>MAXLEN-1)printf (“堆栈溢出！”)； else if (top= =0) top+;S top=x; else top=top+M; S top=x; /出栈算法：void pop (char x) if (top= =0) printf ("堆栈为空栈！” );elseif (top= =1)x= S top;top； else x= S top;top=top- M;(2)设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。 解：设表达式在字符数组 a中，使用一堆栈 S来帮助判断。int correct (char a

40、)stack s ;InitStack (s);for (i=0; i <strlen(a);i+)if (ai='(')Push (s,'(')；elseif (ai=')')if StackEmpty (s)return 0;elsePop(s);if (StackEmpty (s)printf ("配对正确！”);elseprintf ("配对错误！” );/调用初始化栈函数/调用判栈空函数/若栈为空返回0;否则出栈/调用判栈空函数/若栈空，说明配对正确，并返回/配对错误返回0(3) 设计一个将十进正整数转换为十进

41、制数的算法，并要求上机调试通过。#include<stdlib.h>typedef struct stacknodeint data;struct stacknode *next;stacknode;typedef structstacknode *top;linkstack;void Conversion(int n)换 linkstack s;int x;s.top=NULL;/定义栈的存储结构定义栈顶的指针/栈的应用：/ 置栈空卜六进制转解：#include<stdio.h>do x=n%16;/ 取余数n= n/16 ;/取新的商stacknode *p=new

42、 stacknode; /申请新结点p->next=s.top ;修改栈顶指针s.top=p;s.top->data=x;/余数入栈while(n);printf("ntt转换后的十六进制数值为："while (s.top)/出栈处理 if(s.top->data<10);printf("%d",s.top->data);elseswitch(s.top->data)case 10: printf("%c",'A');break;case 11: printf("%c&qu

43、ot;,'B');break;case 12: printf("%c",'C');break;case 13: printf("%c",'D');break;case 14: printf("%c",'E');break;case 15: printf("%c",'F');break;stacknode *p=s.top;s.top=s.top->next;free(p) ;/出栈一个余数，收回一个结printf("nn

44、");void main()int n;printf("ntt请输入一个十进制正整数：");scanf("%d",&n);Conversion(n);单元练习4一.判断题(下列各题，正确的请在前面的括号内打，；错误的打X )(，)(1)队列是限制 在两端进行操作的线性表。(，)(2)判断顺序队 列为空的标准是头指针和尾指针都指向同一个结点。(X) (3)在链队列上做出队操作时，会改变 front指针的值。(，)(4)在循环队列中，若尾指针 rear大于头指针front ,其元素个数为rear- front(x) (5)在单向循环链表中，

45、若头指针为h,那么p所指结点为尾结点的条件是p=h。(，)(6)链队列在一定范围内不会出现队满的情况。(X) (7)在循环链队列中无溢出现象。(X) (8)栈和队列都是顺序存储的线性结构。(X) (9)在队列中允 许删除的 一端称 为队尾。(X) (10)顺序队和 循环队关于 队满和 队空的 判断条件 是一样 的。二.填空题(1) 在队列中存取数据应遵循的原则是先进先出。(2) 队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。(3) 在队列中，允许插入的一端称为队尾 。(4) 在队列中，允许删除的一端称为队首(或队头) 。(5) 队列在进行出队操作时，首先要判断队列

46、是否为空 。(6) 顺序队列在进行入队操作时，首先要判断队列是否为满 。(7) 顺序队列初始化后，front=rear= -1。(8) 解决顺序队列“假溢出”的方法是采用循环队列。(9) 循环队列的队首指针为front ,队尾指针为rear ,则队空的条件为front =rear 。(10)链队歹U LM空日LQ->front->next= NULL。(10) 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间 复杂度为 O ( n)。(12)设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间 复杂度为 0(1)。(13)在一个链队列中，若队首指针与

47、队尾指针的值相同，则表示该队列为 2。(14)设循环队列的头指针front指向队首元素，尾指针 rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN,则队满标志为： front=(rear+1)%MAXLEN。(15)在一个链队列中，若队首指针为 front ,队尾指针为 rear ,则判断该队列只 有一 个结点的条件为：front=rear && front !NULL。(或 front=rear && front <>NULL )(16)向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。(17)读队

48、首元素的操作不改变(或不影响)队列元素的个数。(18)设循环队列的容量为40 (序号从0到39),现经过一系列的入队和出队运算后，有front=11 , rear=19 ,则循环队列中还有8 个元素。(L= (N + rear front)% N= (40+1911) % 40=8)(19)队列 Q,经过下列运算：InitQueue(Q)( 初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0。(20 )队歹U Q 经过 InitQueue(Q)( 初始化队列);InQueue(Q,a);

49、InQueue(Q,b); ReadFront(Q,x)后，x 的值是 a 。三.选择题(1)队列是限定在(D )进行操作的线性表。A .中间B 队首C .队尾(2)队列中的元素个数是(B )。A .不变的B .可变的C .任意的(3)同一队列内各元素的类型(A )。A .必须一致 B .不能一致C.可以不一(4)队列是一个(C )线性表结构A .不加限制的B .推广了的C .力口 了限制的 D .非(5)当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为B . n-1C . n(6) 一个循环 队列一 旦说明， 其占用 空间的 大小(AB.可以变动 C .不能固定(7)循环

50、队列占用的空间(A )A .必须连续B .不必连续 C .不能连续D ,可以不连续(8)存放循 环队列元素的数组data有10个元素，则data数组的下标范围是(9)0.10若进队的序列为:B, C, D, AB.A,0.9B,(10)A, B, C, D四个元素按：A,B,C,(11)四个元素按:A,B,C,C . 1.9C, D,则出队的序列是(D顺序连续进队D顺序连续进队B.Q,A, C,C, B,B, DD, AD. 1.10则队尾元素是( D )。D.D执行一次 OutQueue(Q)操作后，队头兀素是( B )。A . AB.B(12)四个元素按： A, B C, D顺序连续进队执

51、行QEmpty(Q);后的值是(B )。A . 0B. 1C .Q,执行四次 OutQueue(Q)操作后，再2D . 3(13)队列Q,经过下列运算后，x的值是(BInitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);ReadFront (Q,x);A. aB . bC. 0(14)循环队列 SCR满 的条件是(B )。A . SQ->rear=SQ->frontB . (SQ->rear+1)% MAXLEN =SQ->frontC. SQ->rear=0D . SQ->front=0(

52、15)设链栈中结点的结构:data为数据域，next为指针域，且 top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列(A )操作。A . s->next=top->next ; top->next=s C . s->next=top ; top=top->next ;(16)带头结点 的链队 列LQ示意图如下; B . top->next=s ;D . s->next=top ; top=s ;,链队列的队头元素是 (A )LQ->frontLQ->rearA. A(17)带头结点的链队列LQ示意图如下,指向链队列的

53、队头指针是(LQ->frontLQ->rearA. LQ->frontB . LQ->rearC. LQ->front->nextD. LQ->rear->next(18 )带头结点的链队列LQ示 意图如下，在进行进队运算时指针LQ->front(A )LQ->frontLQ->rearA.始终不改变 B .有时改变(19)队列Q,经过下列运算后，再执行InitQueue(Q)( 初InQueue(Q,b);OutQueue(Q,x);ReadQueue(Q,x);A. aB . bC .进队时改变QEmpty(Q)的值是(C始

54、 化 队 列D.出队时改变);InQueue(Q,a);(20)若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0 ,当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B )A . 5和 1B. 4和 2C. 2和 4D. 1和 5四.写出程序运行的结果写出下列程序段的输出结果(队列中的元素类型为char)。void main()Queue Q; InitQueue (Q); 初始化队列char x="E" y="C"InQueue (Q, "H");InQueue (Q, "R");InQueue (Q, y);OutQueue (Q,x); In