数据构造（C说话版）（第2版）课后习题答案李冬梅目录第1章绪论1第2章线性表4第3章栈和队列12第4章串.数组和广义表25第5章树和二叉树32第6章图41第7章查找52第8章排序63第1章绪论1．简述下列概念：数据.数据元素.数据项.数据对象.数据构造.逻辑构造.存储构造.抽象数据类型.答案：数据：是客不雅事物的符号暗示,指所有能输入到盘算机中并被盘算机程序处理的符号的总称.如数学盘算顶用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形.图像.声音.动画等经由过程特别编码界说后的数据.数据元素：是数据的根本单位,在盘算机中平日作为一个整体进行斟酌和处理.在有些情形下,数据元素也称为元素.结点.记载等.数据元素用于完全地描写一个对象,如一个学生记载,树中棋盘的一个格局（状况）.图中的一个极点等.数据项：是构成数据元素的.有自力寄义的.不成朋分的最小单位.例如,学生根本信息表中的学号.姓名.性别等都是数据项.数据对象：是性质雷同的数据元素的集合,是数据的一个子集.例如：整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’, ‘a’,‘b’,…,‘z’},学生根本信息表也可是一个数据对象.数据构造：是互相之间消失一种或多种特定关系的数据元素的集合.换句话说,数据构造是带“构造”的数据元素的集合,“构造”就是指数据元素之间消失的关系.逻辑构造：从逻辑关系上描写数据,它与数据的存储无关,是自力于盘算机的.是以,数据的逻辑构造可以看作是从具体问题抽象出来的数学模子.存储构造：数据对象在盘算机中的存储暗示,也称为物理构造.抽象数据类型：由用户界说的,暗示运用问题的数学模子,以及界说在这个模子上的一组操纵的总称.具体包含三部分：数据对象.数据对象上关系的集合和对数据对象的根本操纵的集合.2．试举一个数据构造的例子,论述其逻辑构造和存储构造两方面的寄义和互相关系.答案：例若有一张学生根本信息表,包含学生的学号.姓名.性别.籍贯.专业等.每个学生根本信息记载对应一个数据元素,学生记载按次序号分列,形成了学生根本信息记载的线性序列.对于全部表来说,只有一个开端结点(它的前面无记载)和一个终端结点(它的后面无记载),其他的结点则各有一个也只有一个直接前趋和直接后继.学生记载之间的这种关系就肯定了学生表的逻辑构造,即线性构造.这些学生记载在盘算机中的存储暗示就是存储构造.假如用持续的存储单元(如用数组暗示)来存放这些记载,则称为次序存储构造;假如存储单元不持续,而是随机存放各个记载,然后用指针进行链接,则称为链式存储构造.即雷同的逻辑构造,可以对应不合的存储构造.3．简述逻辑构造的四种根本关系并画出它们的关系图.答案：（1）集合构造数据元素之间除了“属于统一集合”的关系外,别无其他关系.例如,肯定一逻辑学生是否为班级成员,只需将班级看做一个集合构造.（2）线性构造数据元素之间消失一对一的关系.例如,将学生信息数据按照其入学报到的时光先后次序进行分列,将构成一个线性构造.（3）树构造数据元素之间消失一对多的关系.例如,在班级的治理系统中,班长治理多个组长,每位组长治理多名组员,从而构成树形构造.（4）图构造或网状构造数据元素之间消失多对多的关系.例如,多位同窗之间的同伙关系,任何两位同窗都可所以同伙,从而构成图形构造或网状构造.个中树构造和图构造都属于非线性构造.四类根本逻辑构造关系图4．存储构造由哪两种根本的存储办法实现？答案：（1）次序存储构造次序存储构造是借助元素在存储器中的相对地位来暗示数据元素之间的逻辑关系,平日借助程序设计说话的数组类型来描写.（2）链式存储构造次序存储构造请求所有的元素依次存放在一片持续的存储空间中,而链式存储构造,无需占用一整块存储空间.但为了暗示结点之间的关系,须要给每个结点附加指针字段,用于存放后继元素的存储地址.所以链式存储构造平日借助于程序设计说话的指针类型来描写.5．选择题（1）在数据构造中,从逻辑上可以把数据构造分成（）.A．动态构造和静态构造 B．紧凑构造和非紧凑构造C．线性构造和非线性构造 D．内部构造和外部构造答案：C（2）与数据元素本身的情势.内容.相对地位.个数无关的是数据的（）.A．存储构造 B．存储实现C．逻辑构造 D．运算实现答案：C（3）平日请求统一逻辑构造中的所稀有据元素具有雷同的特征,这意味着（）.A．数据具有统一特色B．不但数据元素所包含的数据项的个数要雷同,并且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等答案：B（4）以下说法准确的是（）.A．数据元素是数据的最小单位B．数据项是数据的根本单位C．数据构造是带有构造的各数据项的集合D．一些概况上很不雷同的数据可以有雷同的逻辑构造答案：D解释：数据元素是数据的根本单位,数据项是数据的最小单位,数据构造是带有构造的各数据元素的集合.（5）算法的时光庞杂度取决于（）.A．问题的范围B．待处理数据的初态C．盘算机的设置装备摆设D．A和B答案：D解释：算法的时光庞杂度不但与问题的范围有关,还与问题的其他身分有关.如某些排序的算法,其履行时光与待排序记载的初始状况有关.为此,有时会对算法有最好.最坏以及平均时光庞杂度的评价.（6）以下数据构造中,（）长短线性数据构造A．树 B．字符串 C．队列 D．栈答案：A6．试剖析下面各程序段的时光庞杂度.（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;答案：O(1)解释：程序的履行次数为常数阶.（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;答案：O(m*n)解释：语句a[i][j]=0;的履行次数为m*n.（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;答案：O(n2)解释：语句s+=B[i][j];的履行次数为n2.（4）i=1;while(i<=n)i=i*3;答案：O(log3n)解释：语句i=i*3;的履行次数为⎣log3n⎦.（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;答案：O(n2)解释：语句x++;的履行次数为n-1+n-2+……＋1= n(n-1)/2.（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;答案：O(n)解释：语句y++;的履行次数为⎣n⎦.第2章线性表1．选择题（1）次序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是（）.A．110 B．108 C．100 D．120答案：B解释：次序表中的数据持续存储,所以第5个元素的地址为：100+2*4=108.（2）在n个结点的次序表中,算法的时光庞杂度是O(1)的操纵是（）.A．拜访第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后拔出一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在次序表中拔出or delete一个结点的时光庞杂度都是O(n),排序的时光庞杂度为O(n2)或O(nlog2n).次序表是一种随机存取构造,拜访第i个结点和求第i个结点的直接前驱都可以直接经由过程数组的下标直接定位,时光庞杂度是O(1).（3）向一个有127个元素的次序表中拔出一个新元素并保持本来次序不变,平均要移动的元素个数为（）.A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2.（4）链接存储的存储构造所占存储空间（）.A．分两部分,一部分存放结点值,另一部分存放暗示结点间关系的指针B．只有一部分,存放结点值C．只有一部分,存储暗示结点间关系的指针D．分两部分,一部分存放结点值,另一部分存放结点所占单元数答案：A（5）线性表若采取链式存储构造时,请求内存中可用存储单元的地址（）.A．必须是持续的 B．部分地址必须是持续的C．必定是不持续的 D．持续或不持续都可以答案：D（6）线性表Ｌ在（）情形下实用于运用链式构造实现.A．需经常修正Ｌ中的结点值Ｂ．需不竭对Ｌ进行删除拔出C．Ｌ中含有大量的结点Ｄ．Ｌ中结点构造庞杂答案：B解释：链表最大的长处在于拔出和删除时不须要移动数据,直接修正指针即可.（7）单链表的存储密度（）.A．大于1 B．等于1 C．小于1 D．不克不及肯定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和全部结点所占的存储空间之比,假设单链表一个结点本身所占的空间为D,指针域所占的空间为N,则存储密度为：D/(D+N),必定小于1.（8）将两个各有n个元素的有序表归并成一个有序表,其起码的比较次数是（）.A．n B．2n-1 C．2n D．n-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素,只须要用第二个表中的第一个元素依次与第一个表的元素比较,总计比较n次.（9）在一个长度为n的次序表中,在第i个元素（1≤i≤n+1）之前拔出一个新元素时须向后移动（）个元素.A．n-i B．n-i+1 C．n-i-1 D．I答案：B(10) 线性表L=(a1,a2,……a n),下列说法准确的是（）.A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的分列必须是由小到大或由大到小D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继.答案：D(11) 创建一个包含n个结点的有序单链表的时光庞杂度是（）.A．O(1) B．O(n) C．O(n2) D．O(nlog2n)答案：C解释：单链表创建的时光庞杂度是O(n),而要树立一个有序的单链表,则每生成一个新结点时须要和已有的结点进行比较,肯定合适的拔出地位,所以时光庞杂度是O(n2).(12) 以下说法错误的是（）.A．求表长.定位这两种运算在采取次序存储构造时实现的效力不比采取链式存储构造时实现的效力低B．次序存储的线性表可以随机存取C．因为次序存储请求持续的存储区域,所以在存储治理上不敷灵巧D．线性表的链式存储构造优于次序存储构造答案：D解释：链式存储构造温柔序存储构造各有优缺陷,有不合的实用处合.(13) 在单链表中,要将s所指结点拔出到p所指结点之后,其语句应为（）.A．s->next=p+1;p->next=s;B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D(14) 在双向链表存储构造中,删除p所指的结点时须修正指针（）.A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案：A(15) 在双向轮回链表中,在p指针所指的结点后拔出q所指向的新结点,其修正指针的操纵是（）.A．p->next=q; q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2．算法设计题（1）将两个递增的有序链表归并为一个递增的有序链表.请求成果链表仍运用本来两个链表的存储空间, 不别的占用其它的存储空间.表中不许可有反复的数据.[标题剖析]归并后的新表运用头指针Lc指向,pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点,从第一个结点开端进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取个中较小者从新链接在Lc表的最后.假如两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素,如许确保归并后表中无反复的元素.当一个表到达表尾结点,为空时,将非空表的残剩元素直接链接在Lc表的最后.[算法描写]void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//归并链表La和Lb,归并后的新表运用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;} //取较小者La中的元素,将pa链接在pc的后面,pa指针后移else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}//取较小者Lb中的元素,将pb链接在pc的后面,pb指针后移else //相等时取La中的元素,删除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb ;pb =q;}}pc->next=pa?pa:pb; //拔出残剩段delete Lb; //释放Lb的头结点}（2）将两个非递减的有序链表归并为一个非递增的有序链表.请求成果链表仍运用本来两个链表的存储空间, 不别的占用其它的存储空间.表中许可有反复的数据.[标题剖析]归并后的新表运用头指针Lc指向,pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点,从第一个结点开端进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取个中较小者从新链接在Lc表的表头结点之后,假如两个表中的元素相等,只摘取La表中的元素,保存Lb表中的元素.当一个表到达表尾结点,为空时,将非空表的残剩元素依次摘取,链接在Lc表的表头结点之后.[算法描写]void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ){//归并链表La和Lb,归并后的新表运用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点Lc->next=NULL;while(pa||pb ){//只要消失一个非空表,用q指向待摘取的元素if(!pa) {q=pb; pb=pb->next;}//La表为空,用q指向pb,pb指针后移else if(!pb) {q=pa; pa=pa->next;}//Lb表为空,用q指向pa,pa指针后移else if(pa->data<=pb->data) {q=pa; pa=pa->next;}//取较小者（包含相等）La中的元素,用q指向pa,pa指针后移else {q=pb; pb=pb->next;}//取较小者Lb中的元素,用q指向pb,pb指针后移q->next = Lc->next; Lc->next = q;//将q指向的结点插在Lc 表的表头结点之后}delete Lb; //释放Lb的头结点}（3）已知两个链表A和B分离暗示两个集合,其元素递增分列.请设盘算法求出A与B 的交集,并存放于A链表中.[标题剖析]只有同时出如今两集合中的元素才出如今成果表中,归并后的新表运用头指针Lc指向.pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点,从第一个结点开端进行比较,当两个链表La和Lb均为到达表尾结点时,假如两个表中相等的元素时,摘取La表中的元素,删除Lb表中的元素;假如个中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移.当链表La和Lb有一个到达表尾结点,为空时,依次删除另一个非空表中的所有元素.[算法描写]void Mix(LinkList& La, LinkList& Lb, LinkList& Lc){pa=La->next;pb=Lb->next;pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa&&pb){ if(pa->data==pb->data)∥交集并入成果表中.{ pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next; delete u;}else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;}else {u=pb; pb=pb->next; delete u;}}while(pa){u=pa; pa=pa->next; delete u;}∥ 释放结点空间while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间pc->next=null;∥置链表尾标识表记标帜.delete Lb; //释放Lb的头结点}（4）已知两个链表A和B分离暗示两个集合,其元素递增分列.请设盘算法求出两个集合A和B 的差集（即仅由在A中消失而不在B中消失的元素所构成的集合）,并以同样的情势存储,同时返回该集合的元素个数.[标题剖析]求两个集合A和B的差集是指在A中删除A和B中共有的元素,即删除链表中的响应结点,所以要保管待删除结点的前驱,运用指针pre指向前驱结点.pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点,从第一个结点开端进行比较,当两个链表La 和Lb均为到达表尾结点时,假如La表中的元素小于Lb表中的元素,pre置为La表的工作指针pa删除Lb表中的元素;假如个中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移.当链表La和Lb有一个为空时,依次删除另一个非空表中的所有元素.[算法描写]void Difference（LinkList& La, LinkList& Lb,int *n）{∥差集的成果存储于单链表La中,*n是成果集合中元素个数,挪用时为0 pa=La->next; pb=Lb->next;∥pa和pb分离是链表La和Lb的工作指针,初始化为响应链表的第一个结点 pre=La;∥pre为La中pa所指结点的前驱结点的指针while（pa&&pb）{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}∥ A链表中当前结点指针后移else if（pa->data>q->data）q=q->next;∥B链表中当前结点指针后移 else {pre->next=pa->next;∥处理A,B中元素值雷同的结点,应删除u=pa; pa=pa->next;delete u;} ∥删除结点}}（5）设盘算法将一个带头结点的单链表A分化为两个具有雷同构造的链表B.C,个中B 表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数,请求B.C表运用A表的结点）.[标题剖析]B表的头结点运用本来A表的头结点,为C表新申请一个头结点.从A表的第一个结点开端,依次取其每个结点p,断定结点p的值是否小于0,运用前插法,将小于0的结点拔出B表,大于等于0的结点拔出C表.[算法描写]void DisCompose(LinkedList A){ B=A;B->next= NULL;∥B表初始化C=new LNode;∥为C申请结点空间C->next=NULL;∥C初始化为空表p=A->next; ∥p为工作指针while(p!= NULL){r=p->next; ∥暂存p的后继if(p->data<0){p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法p=r;∥p指向新的待处理结点.}}（6）设计一个算法,经由过程一趟遍历在单链表中肯定值最大的结点.[标题剖析]假定第一个结点中数据具有最大值,依次与下一个元素比较,若其小于下一个元素,则设其下一个元素为最大值,反复进行比较,直到遍历完该链表.[算法描写]ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//假如下一个结点消失if(p->data > pmax->data) pmax=p;//假如p的值大于pmax的值,则从新赋值p=p->next;//遍历链表}return pmax->data;（7）设计一个算法,经由过程遍历一趟,将链表中所有结点的链接偏向逆转,仍运用原表的存储空间.[标题剖析]从首元结点开端,逐个地把链表L的当前结点p拔出新的链表头部.[算法描写]void inverse(LinkList &L){// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p拔出在头结点之后p = q;}}（8）设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素（mink 和maxk是给定的两个参数,其值可以和表中的元素雷同,也可以不合）.[标题剖析]分离查找第一个值>mink的结点和第一个值≥maxk的结点,再修正指针,删除值大于mink且小于maxk的所有元素.[算法描写]void delete(LinkList &L, int mink, int maxk) {p=L->next; //首元结点while (p && p->data<=mink){ pre=p; p=p->next; } //查找第一个值>mink的结点if (p){while (p && p->data<maxk) p=p->next;// 查找第一个值≥maxk的结点q=pre->next; pre->next=p; // 修正指针while (q!=p){ s=q->next; delete q; q=s; } // 释放结点空间}//if}（9）已知p指向双向轮回链表中的一个结点,其结点构造为data.prior.next三个域,写出算法change(p),交流p所指向的结点和它的前缀结点的次序.[标题剖析]知道双向轮回链表中的一个结点,与前驱交流涉及到四个结点（p结点,前驱结点,前驱的前驱结点,后继结点）六条链.[算法描写]void Exchange（LinkedList p）∥p是双向轮回链表中的一个结点,本算法将p所指结点与其前驱结点交流.{q=p->llink;q->llink->rlink=p;∥p的前驱的前驱之后继为pp->llink=q->llink;∥p的前驱指向其前驱的前驱.q->rlink=p->rlink;∥p的前驱的后继为p的后继.q->llink=p;∥p与其前驱交流p->rlink->llink=q;∥p的后继的前驱指向原p的前驱p->rlink=q;∥p的后继指向其本来的前驱}∥算法exchange停滞.（10）已知长度为n的线性表A采取次序存储构造,请写一时光庞杂度为O(n).空间庞杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素.[标题剖析]在次序存储的线性表上删除元素,平日要涉及到一系列元素的移动（删第i个元素,第i+1至第n个元素要依次前移）.本题请求删除线性表中所有值为item的数据元素,并未请求元素间的相对地位不变.是以可以斟酌设头尾两个指针（i=1,j=n）,从两头向中央移动,凡碰到值item的数据元素时,直接将右端元素左移至值为item的数据元素地位.[算法描写]void Delete（ElemType A[ ],int n）∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素.{i=1;j=n;∥设置数组低.高端指针（下标）.while（i<j）{while（i<j && A[i]!=item）i++;∥若值不为item,左移指针.if（i<j）while（i<j && A[j]==item）j--;∥若右端元素为item,指针左移 if（i<j）A[i++]=A[j--];}第3章栈和队列1．选择题（1）若让元素1,2,3,4,5依次进栈,则出栈次序不成能出如今（）种情形.A．5,4,3,2,1 B．2,1,5,4,3 C．4,3,1,2,5 D．2,3,5,4,1答案：C解释：栈是落后先出的线性表,不难发明C选项中元素1比元素2先出栈,违反了栈的落后先出原则,所以不成能消失C选项所示的情形.（2）若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为（）.A．i B．n-i C．n-i+1 D．不肯定答案：C解释：栈是落后先出的线性表,一个栈的入栈序列是1,2,3,…,n,而输出序列的第一个元素为n,解释1,2,3,…,n一次性全体进栈,再进行输出,所以p1=n,p2=n-1,…,pi=n-i+1.（3）数组Ｑ［ｎ］用来暗示一个轮回队列,ｆ为当前队列头元素的前一地位,ｒ为队尾元素的地位,假定队列中元素的个数小于ｎ,盘算队列中元素个数的公式为（）.A．r-f B．(n+f-r)%n C．n+r-fD．（n+r-f)%n答案：D解释：对于非轮回队列,尾指针和头指针的差值等于队列的长度,而对于轮回队列,差值可能为负数,所以须要将差值加上MAXSIZE（本题为n）,然后与MAXSIZE（本题为n）求余,即（n+r-f)%n.（4）链式栈结点为：(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保管到x中,则应履行操纵（）.A．x=top->data;top=top->link;B．top=top->link;x=top->link;C．x=top;top=top->link; D．x=top->link;答案：A解释：x=top->data将结点的值保管到x中,top=top->link栈顶指针指向栈顶下一结点,即摘除栈顶结点.（5）设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); }则盘算fact(n)须要挪用该函数的次数为（）.A． n+1 B． n-1 C． n D． n+2答案：A解释：特别值法.设n=0,易知仅挪用一次fact(n)函数,故选A.（6）栈在（）中有所运用.A．递归挪用B．函数挪用C．表达式求值D．前三个选项都有答案：D解释：递归挪用.函数挪用.表达式求值均用到了栈的落后先出性质.（7）为解决盘算机主机与打印机间速度不匹配问题,平日设一个打印数据缓冲区.主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中掏出数据.该缓冲区的逻辑构造应当是（）.A．队列 B．栈C．线性表D．有序表答案：A解释：解决缓冲区问题应运用一种先辈先出的线性表,而队列恰是一种先辈先出的线性表.（8）设栈S和队列Q的初始状况为空,元素e1.e2.e3.e4.e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2.e4.e3.e6.e5和e1,则栈S的容量至少应当是（）.A．2 B．3 C．4 D． 6答案：B解释：元素出队的序列是e2.e4.e3.e6.e5和e1,可知元素入队的序列是e2.e4.e3.e6.e5和e1,即元素出栈的序列也是e2.e4.e3.e6.e5和e1,而元素e1.e2.e3.e4.e5和e6依次进入栈,易知栈S中最多同时消失3个元素,故栈S的容量至少为3.（9）若一个栈以向量V[1..n]存储,初始栈顶指针top设为n+1,则元素x进栈的准确操纵是( ).A．top++; V[top]=x; B．V[top]=x; top++;C．top--; V[top]=x; D．V[top]=x; top--;答案：C解释：初始栈顶指针top为n+1,解释元素从数组向量的高端地址进栈,又因为元素存储在向量空间V[1..n]中,所以进栈时top指针先下移变成n,之后将元素x存储在V[n].（10）设计一个判别表达式中左,右括号是否配对消失的算法,采取（）数据构造最佳.A．线性表的次序存储构造B．队列C. 线性表的链式存储构造D. 栈答案：D解释：运用栈的落后先出原则.（11）用链接方法存储的队列,在进行删除运算时（）.A. 仅修正头指针B. 仅修正尾指针C. 头.尾指针都要修正D. 头.尾指针可能都要修正答案：D解释：一般情形下只修正头指针,但是,当删除的是队列中最后一个元素时,队尾指针也丧掉了,是以需对队尾指针从新赋值.（12）轮回队列存储在数组A[0..m]中,则入队时的操纵为（）.A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)答案：D解释：数组A[0..m]中共含有m+1个元素,故在求模运算时应除以m+1.（13）最大容量为n的轮回队列,队尾指针是rear,队头是front,则队空的前提是（）.A. (rear+1)%n==frontB. rear==frontC．rear+1==front D. (rear-l)%n==front答案：B解释：最大容量为n的轮回队列,队满前提是(rear+1)%n==front,队空前提是rear==front.（14）栈和队列的配合点是（）.A. 都是先辈先出B. 都是先辈后出C. 只许可在端点处拔出和删除元素D. 没有配合点答案：C解释：栈只许可在栈顶处进行拔出和删除元素,队列只许可在队尾拔出元素和在队头删除元素.。
