C语言数据结构

为五月最后统考拼搏,稳做王者看谁与争锋?第一章概论 自测题答案 姓名 班级题号四五总分题分3315982015100得分ー、填空题（每空1分共33分）.ー个计算机系统包括硬件系统和软件系统两大部分.一台计算机中全部程序的集合称为这台计算机的 软件资源/（系统）.计算机软件可以分为系统软件和应用软件两大类科学计算程序包属于应用软件诊断程序属于系统软件（工具）.一种用助忆符号来表示机器指令的操作符和操作数的语言是 汇编语言.数据结构是ー门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系 和运算等的学科.数据结构被形式地定义为(DR)其中D是 数据元素 的有限集合R是D上的关系有限集合.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容.数据结构按逻辑结构可分为两大类它们分别是线性结构和非线性结构.线性结构中元素之间存在ー对ー关系树形结构中元素之间存在ー对多关系图形结构中元素之间存在多对多关系.在线性结构中第一个结点没有前驱结点其余每个结点有且只有1个前驱结点:最后ー个结点没有后续结点其余每个结点有且只有1个后续结点.在树形结构中树根结点没有前驱结点其余每个结点有且只有 1 个前驱结点;叶子结点没有后续结点其余每个结点的后续结点数可以任意多个.在图形结构中每个结点的前驱结点数和后续结点数可以任意多个.数据的存储结构可用四种基本的存储方法表示它们分别是顺序、链式、索引和散列.数据的运算最常用的有5种它们分别是插入、删除、修改、査找、排序

.ー个算法的效率可分为时间 效率和空间效率和若干个被调用的其它函数组. K00年省统考!!任何ー个C程序都由 和若干个被调用的其它函数组成.100年省统考题】变量ー经说明就确定该变量的取值范围(即存储单元)及确定变量所允许的运算就确定该变量的取值范围(即存储单元)及确定变量所允许的运算二、单项选择题(每小题1分共15分)(B)1.通常所说的主机是指:A)CPUB)CPU和内存 〇CPU、内存与外存 D)CPU、内存与硬盘(C)2.在计算机内部一切信息的存取、处理和传送的形式是:A)ACSII码B)BCD码C)二进制 D)十六进制(D)3.软件与程序的区别是:A)程序价格便宜、软件价格昂贵;B)程序是用户自己编写的而软件是由厂家提供的;0程序是用高级语言编写的而软件是由机器语言编写的;D)软件是程序以及开发、使用和维护所需要的所有文档的总称而程序只是软件的一部分(C)4.所谓"裸机”是指:A)单片机B)单板机〇不装备任何软件的计算机 D)只装备操作系统的计算机(D)5.应用软件是指:A)所有能够使用的软件 B)能被各应用单位共同使用的某种软件C)所有微机上都应使用的基本软件 D)专门为某ー应用目的而编制的软件(*A)6.K00年省统考!]C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举）四种（A）符号常量 （B）长整型常量（〇逻辑常量（D）二进制整数（*C）7.编译程序的功能是:A）发现源程序中的语法错误C）将源程序编译成目标程序语言程序举）四种（A）符号常量 （B）长整型常量（〇逻辑常量（D）二进制整数（*C）7.编译程序的功能是:A）发现源程序中的语法错误C）将源程序编译成目标程序语言程序（A）8.系统软件中最重要的是:A）操作系统B）语言处理系统理系统（C）9.可移植性最好的计算机语言是:A）机器语言 B）汇编语言B）改正源程序中的语法错误D）将某一高级语言程序翻译成另一种高级0工具软件 D）数据库管0高级语言D）自然语言（B）10.非线性结构是数据元素之间存在ー种:A）一对多关系 B）多对多关系 C）多对ー关系 D）ー对ー关系（C）11.数据结构中与所使用的计算机无关的是数据的A）存储B）物理（C）12.算法分析的目的是:A）找出数据结构的合理性0分析算法的效率以求改进结构:0逻辑 D）物理和存储B）研究算法中的输入和输出的关系D）分析算法的易懂性和文档性（A）13.算法分析的两个主要方面是:A）空间复杂性和时间复杂性0可读性和文档性B）正确性和简明性D）数据复杂性和程序复杂性（C）14.计算机算法指的是：A）计算方法 B）排序方法0解决问题的有限运算序列 D）调度方法（B）15.计算机算法必须具备输入、输出和 等5个特性A）可行性、可移植性和可扩充性0确定性、有穷性和稳定性B）可行性、确定性和有穷性D）易读性、稳定性和安全性三、简答题（每小题3分共9分）.我们知道计算机只能执行机器指令为什么它能运行用汇编语言和高级语言编写的程序?答:靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗?答:简单地说数据结构定义了一组按某些关系结合在一起的数组元素数据类型不仅定义了一组带结构的数据元素而且还在其上定义了一组操作.简述线性结构与非线性结构的不同点答：线性结构反映结点间的逻辑关系是ー对ー的非线性结构反映结点间的逻辑关系是多对多的四、R00年统考题》阅读下列C程序段写出相应的执行结果(每小题4分共8分)1.printf("Inputx");scanf("%d"&x);if(x<=30)if(x>20)y=x;elseif(x>10)y=2*x;if(x>0&&x<30)printf("x=%dy=%d"xy);elseprintf("输入数据错!”)；试写出当x分别为!88时的执行结果答:运行结果为:x=18y=36x=8y=运行前的值且从x=30开始为数据错五、【严题集1.8④】分析下面各程序段的时间复杂度(每小题5分共20分)六、设有数据逻辑结构S=(DR)试按各小题所给条件画出这些逻辑结构的图示并确定相对于关系R哪些结点是开始结点哪些结点是终端结点?(每小题5分共15分).【严蔚敏习题集P71.3②】D={dld2d3d4} R={(dld2)(d2d3)(d3d4))答:dlfd2fd3fd4 dl-无直接前驱是首结点 d4ー无直接后继是尾结点D={dld2d9}R={(dld2)(dld3)(d3d4)(d3d6)(d6d8)(d4d5)(d6d7)(d8d9))答:此图为树形结构 dlー无直接前驱是根结点 d2d5d7d9ー无直接后继是叶子结点D={dld2d9}R={(dld3)(dld8)(d2d3)(d2d4)(d2d5)(d3d9)(d5d6)(d8d9)(d9d7)(d4d7)(d4d6))答:此图为图形结构 dld2ー无直接前驱是开始结点 d6d7ー无直接后继是终端结点班级第2章自测卷答案题号班级四五六七总分题分1310101071040100得分ー、填空（每空1分共13分）.【严题集2.2①】在顺序表中插入或删除ー个元素需要平均移动表中一半元素具体移动的元素个数与表长和该元素在表中的位置有关.线性表中结点的集合是有限的结点间的关系是ー对ー的.向ー个长度为n的向量的第i个元素（IWiWn+l）之前插入一个元素时需向后移动n-i+1个元素.向ー个长度为n的向量中删除第i个元素（IWiWn）时需向前移动n-i个元素.在顺序表中访问任意ー结点的时间复杂度均为0（1）因此顺序表也称为随机存取的数据结构.【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻单链表中逻辑上相邻的元素的物理位置不一定相邻.【严题集2.2①】在单链表中除了首元结点外任ー结点的存储位置由其直接前驱结点的链域的值指示8,在n个结点的单链表中要删除已知结点・p需找到它的前驱结点的地址其时间复杂度为〇（n）二、判断正误（在正确的说法后面打勾反之打叉）（每小题1分共10分）（X）1.链表的每个结点中都恰好包含一个指针答:错误链表中的结点可含多个指针域分别存放多个指针例如双向链表中的结点可以含有两个指针域分别存放指向其直接前趋和直接后继结点的指针（X）2.链表的物理存储结构具有同链表一样的顺序错链表的存储结构特点是无序而链表的示意图有序（X）3.链表的删除算法很简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动错链表的结点不会移动只是指针内容改变（X）4.线性表的每个结点只能是ー个简单类型而链表的每个结点可以是一个复杂类型错混淆了逻辑结构与物理结构链表也是线性表!且即使是顺序表也能存放记录型数据(X)5.顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取错正好说反了顺序表オ适合随机存取链表恰恰适于"顺藤摸瓜”(X)6.顺序存储方式的优点是存储密度大旦插入、删除运算效率高错前一半正确但后一半说法错误那是链式存储的优点顺序存储方式插入、删除运算效率较低在表长为n的顺序表中插入和删除ー个数据元素平均需移动表长一半个数的数据元素(X)7.线性表在物理存储空间中也一定是连续的错线性表有两种存储方式顺序存储和链式存储后者不要求连续存放(X)8.线性表在顺序存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻错误线性表有两种存储方式在顺序存储时逻辑上相邻的元素在存储的物理位置次序上也相邻(X)9.顺序存储方式只能用于存储线性结构错误顺序存储方式不仅能用于存储线性结构还可以用来存放非线性结构例如完全ニ叉树是属于非线性结构但其最佳存储方式是顺序存储方式（后一节介绍）（X）10.线性表的逻辑顺序与存储顺序总是一致的错理由同7链式存储就无需一致三、单项选择题（每小题1分共10分）（C）1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称之为:（A）存储结构 （B）逻辑结构（C）顺序存储结构 （D）链式存储结构（B）2.ー个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是（A）110 （B）108 （〇!00 （D）120（A）3.在n个结点的顺序表中算法的时间复杂度是0（1）的操作是:（A）访问第i个结点（IWiWn）和求第i个结点的直接前驱（2<iWn）（B）在第i个结点后插入一个新结点（IWiWn）（〇删除第i个结点（IWiくn）（D）将n个结点从小到大排序（B）4.向ー个有!27个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动个元素（A）8 （B）63.5 （063 （D）7（A）5.链接存储的存储结构所占存储空间:分两部分一部分存放结点值另一部分存放表示结点间关系的指针只有一部分存放结点值（〇只有一部分存储表示结点间关系的指针（D）分两部分一部分存放结点值另一部分存放结点所占单元数（B）6.链表是ー种采用 存储结构存储的线性表;（A）顺序（B）链式 （C）星式 （D）网状（D）7.线性表若采用链式存储结构时要求内存中可用存储単元的地址:（A）必须是连续的 （B）部分地址必须是连续的一定是不连续的 （D）连续或不连续都可以（B）8.线性表L在 情况下适用于使用链式结构实现（A）需经常修改L中的结点值 （B）需不断对L进行删除插入（〇L中含有大量的结点 （D）L中结点结构复杂（C）9.单链表的存储密度（A）大于1： （B）等于1； （C）小于1； （D）不能确定（B）10.设al、a2、a3为3个结点整数P034代表地址则如下的链式存储结构称为P0P0—>al3—>a24—>A3（A）循环链表（B）单链表（C）双向循环链表（D）双向链表四、简答题（每小题5分共10分）.【严题集2.3②］试比较顺序存储结构和链式存储结构的优缺点在什么情况下用顺序表比链表好?答:①顺序存储时相邻数据元素的存放地址也相邻（逻辑与物理统ー）;要求内存中可用存储单元的地址必须是连续的优点:存储密度大（=1?）存储空间利用率高缺点:插入或删除元素时不方便②链式存储时相邻数据元素可随意存放但所占存储空间分两部分一部分存放结点值另一部分存放表示结点间关系的指针优点:插入或删除元素时很方便使用灵活缺点:存储密度小«1）存储空间利用率低顺序表适宜于做査找这样的静态操作;链表宜于做插入、删除这样的动态操作若线性表的长度变化不大且其主要操作是查找则采用顺序表；若线性表的长度变化较大且其主要操作是插入、删除操作则采用链表.【严题集2.1①】描述以下三个概念的区别:头指针、头结点、首元结点（第一个元素结点）在单链表中设置头结点的作用是什么?答:首元结点是指链表中存储线性表中第一个数据元素al的结点为了操作方便通常在链表的百元结点之前附设ー个结点称为头结点该结点的数据域中不存储线性表的数据元素其作用是为了对链表进行操作时可以对空表、非空表的情况以及对首元结点进行统ー处理头指针是指向链表屮第一个结点（或为头结点或为首元结点）的指针若链表中附设头结点则不管线性表是否为空表头指针均不为空否则表示空表的链表的头指针为空这三个概念对单链表、双向链表和循环链表均适用是否设置头结点是不同的存储结构表示同一逻辑结构的问题头结点head—>datalink头指针 首元结点简而言之头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针;头结点是在链表的首元结点之前附设的ー个结点;数据域内只放空表标志和表长等信息（内放头指针?那还得另配ー个头指针!！！）首元素结点是指链表中存储线性表中第一个数据元素al的结点五、【软考题】线性表具有两种存储方式即顺序方式和链接方式现有一个具有五个元素的线性表し={2317470531）若它以链接方式存储在下列100〜119号地址空间中每个结点由数据（占2个字节）和指针（占2个字节）组成如下所示:05U17X23V31Y47100120其中指针XYZ的值分别为多少?该线性表的首结点起始地址为多少?末结点的起始地址为多少?（10分）答:X=116Y=0 Z=100 首址=108 末址=112六、阅读分析题（10分）【严题集2.10②】指出以下算法中的错误和低效（即费时）之处并将它改写为・个既正确乂髙效的算法答:错误有两处:①参数不合法的判别条件不完整例如表长为!0若从第一位置(i=l)删除10个元素(k=10)要求合理但会被判为非法合法的入口参数条件为(0<i^a.length)"(0〈k〈a.length-i)应将if(i<lIIk<0IIi+k>a.length)returnINFEASIBLE改为:if(!((0〈iくa.length)"(oWkくa.length-i)))returnINFEASIBLE第二个FOR语句中元素前移的次序错误应将for(j=a.length;j>=i+l;j-)a.elem[j-l]=a.elem[j]：改为for(j>=i+l;j=a.length;j++)a.elem[j-l]=a.elem[j];七、编程题(每题10分共40分).【徐士良题集2002年1月省统考题】写出在顺序存储结构下将线性表逆转的算法要求使用最少的附加空间解:输入:长度为n的线性表数组A(l;n)输出:逆转后的长度为n的线性表数组A(l;n)C语言描述如下(其中ET为数据元素的类型)：.【严题集2.6②】已知L是无表头结点的单链表且P结点既不是首元结点也不是尾元结点请写出在P结点后插入S结点的核心语句序列答:此题答案不唯一但若从己给定序列中挑选则限制颇多Q=P;(11)P=L;while(P->next!=Q)P=P->next;(10)P=Q：(4)S->next=P->next;P->next=S;3.编写程序将若干整数从键盘输入以单链表形式存储起来然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）注:统计结点个数是【省统考样题】的要求也是教材P604-6计算链表长度的要求编程又简单很容易作为考题解：编写C程序划下（已上机通过）：全局变量及函数提前说明：#include<stdio.h>#include<stdlib.h>typedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p*q*r*head;intm=sizeof(test);voidmain() /・第一步从键盘输入整数不断添加到链表・/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999){printf(*/ninputaninteger[stopby'-9999']:");scanf(*%d*&i)；p->data=i; /*inputdataissaved*/p->link=(test*)malloc(m);/*m=sizeof(test));*/q=p;p=p->link;)q->link=NULL; /・原先用p->link=NULL似乎太晚!*/p=head;i=0; /*统计链表结点的个数并打印出来・/while(p->link!=NULL){printf(细d”p->data);p=p->link;i++；}printf[\nnodenumber=%d\n，zi-1)：/・结点的个数不包括ー9999*/}0301陈建武:.程序中统计结点数应是i个而不是i~l.假设链表表长为ni从〇开始则在统计某ー结点后i加一此时P已指向下一个结点第一结点统计结束i为1p指向第二结点即当P指向尾结点(第n个结点)时i的值为n-1while循环条件不符(指针域为null)退出循环即得统计的结点数为n-1.所以i的值就是结点数不必再减ー. 请编写26个字母按特定字母值插入或删除的完整程序可自行选用顺序存储或链表结构答:#include<stdio.h> /・全局变量及函数提前说明:*/#include<stdlib.h>typedefstructliuyu{chardata;structliuyu*link;}test;liuyu*p*head;intL; /・元素的个数・/intm=sizeof(test);voidbuildO； /・主函数中会被调用的函数应当预先说明・/voiddisplay();intinsertchar(charchar); /・插入一个字母在第字母Y之前若无字母则加到末尾・/intdelet_char(char); /・删除元素X注意保存X的前趋元素指针!*/voidbuildO{inti;voidbuildO{inti;head=(test*)malloc(m);p=head;for(i=l;iくL;i++){p->data=i+，a-1;p->link=(test*)malloc(m);p=p->link;}p->data=i+*a'-！.；p->link=NULL;/*字母链表的生成・//*m=sizeof(test);*//*'a'也可用其ASCII码97来表示/*m=sizeof(test));*//♦ */voiddisplay() /・字母链表的输出・/{p二head;while(p->link!=NULL){printf(*%c*p->data);p=p->link;}printf("%c\n"p->data);/* */intinsert_char(charXcharY) /*插入一个字母X在某个字母Y之前若找不到Y字母则加到末尾・/{p二head;r=(test*)malloc(m);rー)data二X;if(headー〉data=Y){head=r;r->link=p;}else{while((p->data!=Y)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==Y){q->link=r;r->link=p;}else{p->link=r;r->link=NULL;}L++；return(0);}/* */intdelet_char(charX)/・删除元素X注意保存X的前趋元素指针!*/{p二head;if(head->data==X){head=head->link;free(p);}else{while((p->data!=X)&&(p->link!=NULL)){q=P；p=p->link;}if(p->data==X){q->link二p->link;free(p); }elsereturn(-1);L—;return(0);}/♦ */voidmain(void) /・字母线性表的生成和输出・/(L=26;buildO;display();printf(insertreturnvalue二%d\ninsert_char('L''W'));display();printfldeletereturnvalue二％d\ndelet_char('z'));display();}附:屏幕上显示的执行结果是:abcdefghijklmnopqrstuvwxyzinsertreturnvalueニ0abcd9efghijklmnopqrstuvwxyzLdeletereturnvalueニ0abcdefghijklmnopqrstuvwxyL0301陈建武修改意见:一,display0函数代码可优化为四行voiddisplay() /・字母链表的输出・/{p=head;while(p->link!=NULL)〃改为while(p)因为当p指向尾结点时p不为null条件成立循环//printf()然后P被赋值为null此时循环条件不符退出正好.{printf("%c"p->data);p=p->link;}printf("%c\n"p->data);〃用while(p)此行可删二.对intinsert_char(charXcharY)若用带头结点的链表代码可减为10行我的程序如下(若参数没有slistp代码要多一行让q指向头指针)voidInsertFind(slistpcharinsertcharcharinsertpos)〃字母insertpos前插入字母insertchar{slistppriornewnode;〃ncwnode新结点pprior为插入位置结点的直接前驱newnode=newliuyu;//为新结点分配内存newnode->data=insertchar;〃对结点数据域初始化while(p) 〃当p指向尾结点时最后一次循环(pprior=p; 〃pprior从头指针开始//p从首元结点开始指向P的直接前驱p=p->next//p从首元结点开始不断前移直至最后p为nullif(p&&(p->data==insertpos))〃当p为null或者结点p的数据域为所要插入的字母break! 〃则退出循环}newnode->next=pprior->next!〃在找到的位置前插入pprior->next=newnode;}对删除结点的操作若有头结点同样可以减少代码由此可见创建一个头结点对简化程序有很大的帮助.上面的观点仅供参考不对之处清指教!第3章栈和队列自测卷答案 姓名 班级题号四五六总分题分151020202015100得分ー、填空题（每空1分共15分）.【李春葆】向量、栈和队列都是线性结构插入和删除元素;插入和删除元素;对于队列只能在队尾 插入和队首删除元素.栈是ー种特殊的线性表允许插入和删除运算的一端称为栈顶不允许插入和删除运算的一端称为 栈底.队列是被限定为只能在表的一端进行插入运算在表的另一端进行删除运算的线性表.在ー个循环队列中队首指针指向队首元素的前一个位置.在具有n个单元的循环队列中队满时共有n-1个元素.向栈中压入元素的操作是先移动栈顶指针后存入元素.从循环队列中删除ー个元素时其操作是先移动队首指针后取出元素.K00年统考题》带表头结点的空循环双向链表的长度等于 0解:二、判断正误（判断下列概念的正确性并作出简要的说明）（每小题1分共10分）（X）1.线性表的每个结点只能是ー个简单类型而链表的每个结点可以是一个复杂类型错线性表是逻辑结构概念可以顺序存储或链式存储与元素数据类型无关（x）2.在表结构中最常用的是线性表栈和队列不太常用错不一定吧?调用子程序或函数常用CPU中也用队列（ノ）3.栈是ー种对所有插入、删除操作限于在表的一端进行的线性表是ー种后进先出型结构（V）4.对于不同的使用者ー个表结构既可以是栈也可以是队列也可以是线性表正确都是线性逻辑结构栈和队列其实是特殊的线性表对运算的定义略有不同而已（X）5.栈和链表是两种不同的数据结构错栈是逻辑结构的概念是特殊殊线性表而链表是存储结构概念二者不是同类项（X）6.栈和队列是ー种非线性数据结构错他们都是线性逻辑结构栈和队列其实是特殊的线性表对运算的定义略有不同而已（V）7.栈和队列的存储方式既可是顺序方式也可是链接方式（V）8.两个栈共享一片连续内存空间时为提高内存利用率减少溢出机会应把两个栈的栈底分别设在这片内存空间的两端(x)9.队是・种插入与删除操作分别在表的两端进行的线性表是一种先进后出型结构错后半句不对(X)10.ー个栈的输入序列是12345则栈的输出序列不可能是12345错有可能三、单项选择题(每小题1分共20分)(B)1.K00年元月统考题!!栈中元素的进出原则是A,先进先出 B.后进先出C.栈空则进 D.栈满则出(C)2.K李春葆)!若已知一个栈的入栈序列是123n其输出序列为P1p2p3pn若pl=n则pi为C.n-i+1C.n-i+1D.不确定解释:当pl=n即n是最先出栈的根据栈的原理n必定是最后入栈的那么输入顺序必定是12则出栈的序列是n(B)3.K李春葆』判定一个栈ST(最多元素为mO)为空的条件是A.ST->top<>0B,ST->top=0 C.ST->topOmOD.ST->top=mO(B)4.K李春葆』判定一个队列QU(最多元素为mO)为满队列的条件是A.QU->rear—QU->front==mOB.QU->rear—QU->front-1==mOC.QU->front==QU->rear D.QU->front==QU->rear+l(D)5.数组Q[n]用来表示一个循环队列f为当前队列头元素的前一位置r为队尾元素的位置假定队列中元素的个数小于n计算队列中元素的公式为(A)r—f; (B)(n+f—r)%n;(C)n+r—f; (D)(n+r—f)%n6.198初程P71】 从供选择的答案中选出应填入下面叙述 ? 内的最确切的解答把相应编号写在答卷的对应栏内设有4个数据元素al、a2、a3和a4対他们分别进行栈操作或队操作在进栈或进队操作时按al、a2、a3、a4次序每次进入ー个元素假设栈或队的初始状态都是空现要进行的栈操作是进栈两次出栈一次再进栈两次出栈一次;这时第一次出栈得到的元素是 A第二次出栈得到的元素是 B是;类似地考虑对这四个数据元素进行的队操作是进队两次出队一次再进队两次出队一次；这时第一次出队得到的元素是 C第二次出队得到的元素是 D

经操作后最后在栈中或队中的元素还有E个供选择的答案:A〜D：①al②a2 ③a3④a4E：①1 ②2 ③3 @0答:ABCDE=241227.194初程P75】从供选择的答案中选出应填入下面叙述 ? 内的最确切的解答把相应编号写在答卷的对应栏内栈是ー种线性表它的特点是A设用ー维数组A[1n]来表示ー•个栈A[n]为栈底用整型变量T指示当前栈顶位置A[T]为栈顶元素往栈中推入(PUSH)ー个新元素时变量T的值B;从栈中弹出(POP)ー个元素时变量T的值C设栈空时有输入序列abc经过PUSHPOPPUSHPUSHPOP操作后从栈中弹出的元素的序列是D变量T的值是E供选择的答案：⑤随机进出⑥减2A：⑤随机进出⑥减2C：①加1②减1③不变 ④清0⑤加2D：①a

TOC\o"1-5"\h\zb ②bc ③ca ④ba ⑤cb @acE：①n+1 ②n+2 ③n④n-1 ⑤n-2答案:ABCDE=22164注意向地址的高端生长称为向上生成堆栈;向地址低端生长叫向下生成堆栈本题中底部为n向地址的低端递减生成称为向下生成堆栈8.191初程P77】从供选择的答案中选出应填入下面叙述 ? 内的最确切的解答把相应编号写在答卷的对应栏内在做进栈运算时应先判别栈是否A!在做退栈运算时应先判别栈是否B当栈中元素为n个做进栈运算时发生上溢则说明该栈的最大容量为C为了增加内存空间的利用率和减少溢出的可能性山两个栈共享一片连续的内存空间时应将两栈的D 分别设在这片内存空间的两端这样只有当E时ォ产生上溢供选择的答案:AB：①空②满C：①nT②nD： ①长度 ②深度③上溢④下溢③n+1 ④n/2③栈顶 ④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空且ー个栈的栈顶到达另ー个栈的栈底答案:ABCDE=21243四、简答题（每小题4分共20分）.【严题集3.2①和3.11①】说明线性表、栈与队的异同点刘答:相同点:都是线性结构都是逻辑结构的概念都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表即受限的线性表只是对插入、删除运算加以限制不同点：①运算规则不同线性表为随机存取而栈是只允许在一端进行插入、删除运算因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算因而是先进先出表FIFO②用途不同堆栈用于子程调用和保护现场队列用于多道作业处理、指令寄存及其他运算等等.【统考书P604T1难于严题集3.1①】设有编号为124的四辆列车顺序进入一个栈式结构的车站具体写出这四辆列车开出车站的所有可能的顺序刘答：至少有14种①全进之后再出情况只有1种:4321②进3个之后再出的情况有3种34234314③进2个之后再出的情况有5种2431 2341 213421432134④进1个之后再出的情况有5种431213421341243.【刘自编】假设正读和反读都相同的字符序列为"回文"例如'abba"和‘abcba,是回文'abcde,和‘ababab,则不是回文假设一字符序列已存入计算机请分析用线性表、堆栈和队列等方式正确输出其回文的可能性?答:线性表是随机存储可以实现靠循环变量(j-)从表尾开始打印输出;堆栈是后进先出也可以实现靠正序入栈、逆序出栈即可;队列是先进先出不易实现哪种方式最好要具体情况具体分析若正文在机内已是顺序存储则直接用线性表从后往前读取即可或将堆栈栈顶开到数组末尾然后直接用POP动作实现(但堆栈是先减后压还是 )若正文是单链表形式存储则等同于队列需开辅助空间可以从链首开始入栈全部压入后再依次输出.【统考书P604-13］顺序队的"假溢出"是怎样产生的?如何知道循环队列是空还是满?答;一般的ー维数组队列的尾指针已经到了数组的上界不能再有入队操作但其实数组中还有空位置这就叫"假溢出"采用循环队列是解决假溢出的途径另外解决队满队空的办法有三:①设置一个布尔变量以区别队满还是队空;②浪费ー个元素的空间用于区别队满还是队空③使用ー个计数器记录队列中元素个数(即队列长度)我们常采用法②即队头指针、队尾指针中有一个指向实元素而另ー个指向空闲元素判断循环队列队空标志是:f=rear 队满标志是:f=(r+l)%N5.【统考书P604-14I设循环队列的容量为40(序号从0到39)现经过一系列的入队和出队运算后有①front=llrear=19;②front=19rear=ll;问在这两种情况下循环队列中各有元素多少个?答:用队列长度计算公式:(N+r-f)%N①L=(40+19-11)%40=8 ②L=(40+11-19)%40=32五、阅读理解(每小题5分共20分至少要写出思路).【严题集3.7①】按照四则运算加、减、乘、除和幕运算(t)优先关系的惯例并仿照教材例3-2的格式画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-BXC/D+EtF答：.【严题集3.3②】写出下列程序段的输出结果(栈的元素类型SElemType为char)voidmain(){StackS;Charxy;InitStack(S);X='c';y='k，;Push(Sx);Push(S'a');Push(Sy)；Pop(Sx);Push(S't');Push(Sx);Pop(Sx);Push(S'sD；while(!StackEmpty(S)){Pop(Sy);printf(y);};Printf(x);)答:输出为“stack”.【严题集3.12②】写出下列程序段的输出结果(队列中的元素类型QElemType为char)voidmain(){QueueQ;InitQueue(Q);Charx='e';y='c';EnQueue(Q'h');EnQueue(Q'r');EnQueue(Q'y');DeQueue(Qx);EnQueue(Qx);DeQueue(Qx);EnQueue(Q'a');while(!QueueEmpty(Q)){DeQueue(Qy);printf(y);};Printf(x);}答:输出为"char".【严题集3.13②】简述以下算法的功能(栈和队列的元素类型均为int)voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Qd);Push(Sd):}；while(!StackEmpty(S)){Pop(Sd);EnQueue(Qd);答:该算法的功能是:利用堆栈做辅助将队列中的数据元素进行逆置六、算法设计（每小题5分共15分至少要写出思路）.【李春葆及严题集3./r/