c++答案数据结构试卷及答案

《数据结构》试卷及答案.算法分析的目的是()。A.找出数据结构的合理性 B.研究算法中输入和输出的关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性.( )是具有相同特性数据元素的集合,是数据的子集。A.数据符号 B.数据对象 C.数据 D.数据结构.用链表表示线性表的优点是( )。A.便于随机存取 B.花费的存储空间比顺序表少C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同.输入序列为(A,B,C,D)不可能的输出有()〇A.(A,B,C,D) B.(D,C,B,A)C,(A,C,D,B)D.(C,A,B,D).在数组表示的循环队列中,front、rear分别为队列的头、尾指针,maxSize为数组的最大长度,队满的条件是()〇A.front=maxSize B.(rear+1)%maxSize=frontC.rear=maxSize D.rear=front.设有串t=,Iamagoodstudent\那么Substr(t,6,6)=()〇A.student B.agoods C.good D.agood.设有一个对称矩阵A,采用压缩存储方式，以行序为主序存储all为第一个元素,其存储地址为1,每个元素占ー个地址空间,则a85地址为()〇A.23 B.33 C.18 D.40.已知广义表LS=(A,(B,C,D),E)运用head和tail函数,取出LS中原子b的运算()〇A.Gethead(Gethead(LS)) B.Gettail(Gethead(LS))C.Gethead(Gethead(Gettai1(LS))) D.Gethead(Gettail(LS))9.若已知一棵ニ叉树先序序列为ABCDEFG,中序序列为CBDAEGF,则其后序序列为()〇A.CDBGFEA B.CDBFGEAC.CDBAGFE D.BCDAGFE.下列存储形式中,（）不是树的存储形式。A.双亲表示法 B.左子女右兄弟表示法C.广义表表示法 D.顺序表示法.对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩ー个元素为止。这样的排序方法是（）°A.直接选择排序 B.直接插入排序C.快速排序 D.起泡排序.采用折半查找方法进行查找,数据文件应为（）,且限于（）〇A.有序表顺序存储结构 B.有序表链式存储结构C.随机表顺序存储结构 D.随机表链式存储结构.就平均查找速度而言,下列几种查找速度从慢至快的关系是（）A.顺序折半哈希分块 B.顺序分块折半哈希C.分块折半哈希顺序 D.顺序哈希分块折半.执行下面程序段时,执行S语句的次数为（）for（intI=l；I<=n;I++）for(intj=l;j<=I;j++)S；A.n2B.n2/2C.n(n+l)D.n(n+l)/2.串是ー种特殊的线性表,其特殊性体现在()A.可以顺序存储 B.数据元素是ー个字符C.可以链接存储 D.数据元素可以是多个字符.树的基本遍历策略分为先根遍历和后根遍历;ニ叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论()是正确的。A.树的先根遍历序列与其对应的ニ叉树的先序遍历序列相同B.树的后根遍历序列与其对应的ニ叉树的先序遍历序列相同C.树的先根遍历序列与其对应的ニ叉树的中序遍历序列相同D.以上都不对.由五个分别带权值为9,2,3,5,14的叶子结点构成的ー棵哈夫曼树,该树的带权路径长度为()。TOC\o"1-5"\h\zA.60 B.66 C.67 D.50.一棵ニ叉树有67个结点,这些结点的度要么是〇,要么是2。这棵ニ叉树中度为2的结点有()个A.33 B.34 C.32 D.30.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时,()次比较后查找成功。A.1B.2 C.4 D.8.若有文件的关键字序列为:[265][301][751][129][937][863][742][694][076][438],以下为二路归并排序过程。第二趟为:A.[265301][129751][863937][694742][076438]B.[076129265301438694742751863937]C.[129265301694742751863937][076438]D.[129265301751][694742863937][076438]二、填空题(本大题共6小题,每空2分,共12分;答案填在下表内)!算法是指令的有限序列,其中每一条指令表示一个或多个操作,此外,ー个算法还具有五个重要特性,它们分别是ヽヽ、有零或多个输入和有一或多个输出。2算法优劣的五个标准是正确性、可使用性、ヽヽ〇3有n个球队参加的足球联赛按主客场制进行比赛，共需进行 场比赛。设有串t='Iamastudent',s='good',a[，么Concat(t,s)='Iamastudentgood',Substr(t,8,7)=05在解决计算机主机与打印机之间速度不匹配时通常设置ー个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个结构,其主要特点是〇6广义表((a),a)的表头是,表尾是〇三、判断题(对的打“J”,错的打“X”。每小题1分,共10分;答案填在下表内)1数据的逻辑结构与数据元素本身的内容和形式无关。2三个结点的ニ叉树和三个结点的树ー样,都具有三种不同的形态。3中序序列和后序序列相同的ニ叉树为:空树和缺右子树的单支树。4对于两棵具有相同关键字集合而形状不同的ニ叉排序树,中序遍历后得到的关键字排列顺序相同。序列｛30,40,50,15,25,35,38,10｝是堆。6对于无向图的生成树,从同一顶点出发所得的生成树相同。7若设哈希表长m=14,哈希函数H(key)=key%ll,表中已有4个结点。addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点的地址是9。8ー个深度为k的,具有最少结点数的完全ニ叉树按层次,(同层次从左向右)用自然数依此对结点编号则,则编号最小的叶子的序号是212+1;编号是i的结点所在的层次号是「log?i|+lo(riog2il表示向上取整」(根所在的层次号规定为1层)。9在ー棵7阶B树中,ー个结点中最多有6棵子树,最少有3棵子树。10算法可以没有输入,但是必须有输出。四、画出树的孩子兄弟表示法示意的树或森林。(4分)五、要求题（本大题共2小题,共12分）设关键字的输入序列为{4,5,7,2,1,3,6}.（8分）从空树开始构造平衡ニ叉树,画出每加入一个新结点时ニ叉树的形态,若发生不平衡,指明需做的平衡旋转类型及平衡旋转的结果。.（4分）上面的数据作为待排序的数据,写出用快速排序进行一趟划分后的数据序列六、按要求做题（本大题共2小题,共12分）1画出无向图G的邻接表存储结构,根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分）2用prim算法求下图的最小生成树,写出最小生成树的生成过程。（5分）七、算法分析设计题(本大题共5小题,共30分).写出程序段的功能,并给出ー个测试用例(ー个输入数据和一个输出结果)(5分)。voidconversion()(Stacks;intn;SElemTypee;initstack(s);printf(/zPleaseinputnumber/');scanf(“渝!”,&n);while(n){push(s,n%8);n=n/8;}while(!stackempty(s)){pop(s,e);printf("%d,?,e);.下面是一个使用栈stack实现对ニ叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。(每空1分,共5分)程序:Voidpreorder(bitree*T){bitree*stack[m];inttop;if(T!=NULL){top=l;stack[top]=(l);while((2)){p=stack[top];top—;printf(w%dM,p->data);if(p->rchild!=NULL){(3);stack[top]=p->rchild;}if((4)){top++;(5);)(1) (2) (3)(4) (5)3.请在标号处填写合适的语句。完成下列程序。(每空1分,共5分)intBinary_Search(S_TBLtbl,KEYkx){/・在表tbl中查找关键码为kx的数据元素,若找到返回该元素在表中的位置,否则返回〇・/intmid,flag=O；low=1；high=length；while(⑴&!flag_){ /・非空,进行比较测试・/TOC\o"1-5"\h\zmid=_(2) ；if(kx<tbl.elem[mid].key)(3) ；elseif(kx>tbl.elem[mid].key)(4) ；returnflag;(1) (2) (3)(5)4.下面是ー个采用直接选择排序方法进行升序排序的函数,请在标号处填写合适的语句。(每空1分,共5分)程序:inti,j,t,minval,minidx;for(i=l;i<=n-l;i++)一5for(j=i+2;j<=n;j++)if( (2)){(3);minidx=j;}if((4) ){t=A[i+U;A[minidx]=t;(1) (2) (3)(4) (5)5试写出求有向无环图的关键路径算法的设计思路（10分）数据结构试卷A答案选择题（本大题共20小题,每题1分,共20分;答案填在下表内）12345678910cB:C:D:B:D:B:C:A：c11121314151617181920：cA:B:D:B:A：c:ACD二、填空题（本大题共5小题,每空1分,共12分;答案填在下表内）1有穷性确定性可行性2可读性健壮性效率n(n-l)'student'队列 先进先出(a) (a)三、判断题(对的打“ノ”,错的打“X二每小题1分,共10分)1)true;2)flase;3)true;4)true;5)flase;6)flase;7)true;8)true;9)flase;10)true四、画岀树的孩子兄弟表示法示意的树或森林。（4分）其他形式的树形结构酌情给分。五、要求题（本大题共2小题,共12分）

ー趟划分后的数据序列3124756六、按要求做题（12分）DFS遍历序列vlv2v4v8v5v3v6v7(ー趟划分后的数据序列3124756六、按要求做题（12分）DFS遍历序列vlv2v4v8v5v3v6v7(或12485367)BFS遍历序列vlv2V3V4V5v6V7V8(或12345678)邻接点的顺序可以不同,可以有不同的深度优先和广度优先遍历序列。（5分,如有错误酌情扣分。）七、算法设计题（30分）1.将十进制转化成八进制数（5分）测试用例:输入10输出122(5分,每空1分)(1)Ttop>0top++p->lchild!=NULLstackLtop]=p->lchild3(5分,每空1分)Iow<=high(low+high)/2high=mid-llow=mid+l14.(5分,每空1分)minidx=i+lminval>A[j]minval=A[j]i!=jA[i+l]=A[minidx]5(10分,不同答案,酌情得分)输入顶点和弧信息,建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Ve[i]将得到的拓扑序列进栈按逆拓扑序列求顶点的VI[i]计算每条弧的e[i]和l[i],找出e[i]=l条]的关键活动第2学期数据结构试卷Aー、选择题(本大题共15小题,每题2分,共30分;答案填在下表内).从ー个长度为100的顺序表中删除第30个元素时需向前移动个元素A、70B、71C、69D、30.在ー个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为〇A、top不变B、top=0C、top=top-lD、top=top+l.从一个具有n个结点的单链表中査找其值等于x结点时,在查找成功情况下,则平均比较ー个结点。A、nB、n/2C、(n-l)/2D、(n+l)/2.在ー个单链表中,若要删除p指针所指结点的后继结点,则执行p->next;p->next=p->next->next;p->next=p->next->next;p=pー〉next;p=pー〉next->>next;.在ー个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行ー〇front->next=s；front=s；s->next=rear; rear=s；rear->next=s; rear=s；s->next=front; front=s；.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结

点数为1个,那么度为O的结点数为个A、6B、7C、8D、9.假定一棵ニ叉树的结点数为33个,则它的最小高度为最大高度为A、4,33B、5,33C、6,33D、6,32.在ー棵完全ニ叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为,〇A、2iB、2i+lC、2i-lD、i/2.在ー个有向图中,所有顶点的入度之和等于所有弧数和一倍。A、1B、2C,3D、4.对于ー个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为ー。A、NB、(N-l)2C、(N+l)2D、N2.已知一个图如图所示,在该图的最小生成树中各边上数值之和为ー一〇6 (36 (3) 18も、6A,21B、26C、28D、33.已知一个图如图所示,由该图行到的ー种拓朴序列为

.二维数组M的元素是4个字符（每个字符占ー个存储单元）组成的串,行下标i的范围从〇到4,列下标j的范围从。到5,M按行存储时元素M⑵⑷的起始地址与M按列存储时元素一的起始地址相同。A、m⑵[4]B、M[4]⑵C、M[3][l]D、M[3][l].具有6个结点的无向图至少应有条边オ能保证是连通图。A、5B、6C、7D、8.采用邻接表存储的图的深度优先遍历类似于ニ叉树的0A先序遍历B中序遍历C,后序遍历D.按层遍历二、填空题（本大题共5小题,每空1分,共8分;答案填在下表内）12345678.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示,根据数据元素之间关系的不同特性,通常有下列四类基本结构:集合、线性结构、⑴ 和⑵ 。.评价算法的标准很多,通常是以执行算法所需要的 （3）和所占用的（4）来判别ー个算法的优劣。.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的メリ也是相邻的。.空格串的长度为串中所包含（6）字符的个数,空串的长度为（7）.加上表示指向前驱和 （8）的线索的ニ叉数称为线索ニ叉树。三、判断题（对的打“丿”,错的打’'X二每小题1分，共10分）（）1.线性表的唯一存储形式是链表。（）2.已知指针P指向键表L中的某结点,执行语句P=Pー〉next不会删除该链表中的结点。（）3.在链队列中,即使不设置尾指针也能进行入队操作。（）4.如果一个串中的所有字符均在另ー串中出现,则说前者是后者的子串。（）5.设与一棵树T所对应的ニ叉树为BT,则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（）6.快速排序是不稳定排序。（）7.任一A0E网中至少有一条关键路径，且是从源点到汇点的路径中最短的ー条。（）8.若图G的最小生成树不唯一,则G的边数一定多于nT,并且权值最小的边有多条（其中n为G的顶点数）。（）9.给出不同的输入序列建造ニ叉排序树，一定得到不同的ニ叉排序树。〇10.基数排序是多关键字排序。从最低位关键字起进行排序。四、应用题。（共44分）L画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分）2.假设用于通信的电子由字符集｛岫,艰©£帥｝中的字母构成,这8个字母在电文中出现的概率分别为｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝画出哈夫曼树,并为这8个字母设计哈夫曼编码。（8分）.已知序列｛70,73,69,23,93,18,11,68｝请给出直接插入排序作升序排序每ー趟的结果和快速排序作升序排序时ー趟的结果。（10分）.设有一组关键字关键码集为｛47,7,29,11,16,92,22,8,3）,哈希表表长为11,Hash（key）=keymod11,用线性探测法处理冲突,构造哈希表,并求它成功查找的ASL。（8分）.ニ叉树的先序遍历序列为ABCDEFGHI,中序遍历序列为BCAEDGHFI,画出这棵ニ叉树。（6分）五、算法设计题（8分）

定义有序表抽象数据类型,并据此类型设计折半查找算法2学期数据结构试卷A参考答案及评分标准ー、选择题本大题共15小题,每题2分,共30分123456789101112131415ADDBCCCBADBADAA二、填空题（本大题共5ハ题,每空1分,共8分）12345678树型结构图型结构时间空间位置空格后继三、判断题（每小题1分,共10分）12345678910XVVXX-JXXXX四、应用题44分）（12分）011000101000100001010010000101001010AB0.2AB0.2A3ACDECDEF35ADFS序列:ABDEFCBFS序列:ABCDFE（8分）7192632321100010100000000010100001110113.（10分）直接插入排序70,73,69,23,93,18,11,68[70,73],69,23,93,18,11,68[70,69,73],23,93,18,11,68[23,70,69,73],93,18,11,68[23,70,69,73,93],18,11,68[18,23,70,69,73,93],11,68[11,18,23,70,69,73,93],68[11,18,23,68,70,69,73,93]快速排序168,11,69,23,18],70,[93,73]（8分）0 1 2345678910112247921637298ASL=5/3（6分）五、算法设计题(8分)typedefstruct{intkey;floatinfo;}JD;intbinsrch(JDr[],intn,intk){intlow,high,mid,found;low=l;high=n;found=0;while((low<=high)&&(found==0)){mid=(low+high)/2;if(k>r[mid].key)low=mid+l;elseif(k==r[mid].key)found=l;ドi;if(found==l)return(mid);elsereturn(O);程序设计教程ーー用C++语言编程（第二版习题解答）目录TOC\o"1-5"\h\z\o"CurrentDocument"第1章概述 24\o"CurrentDocument"第2章 基本数据类型和表达式 26\o"CurrentDocument"第3章程序的流程控制ーー语句 29第4章 过程抽象ーー函数 38\o"CurrentDocument"第5章 构造数据类型 47\o"CurrentDocument"第6章数据抽象ーー类 63\o"CurrentDocument"第7章操作符重载 82\o"CurrentDocument"第8章继承ーー派生类 106第9草类属（泛型）机制 模板 117第10章输入/输出（I/O） 123\o"CurrentDocument"第11章异常处理 130\o"CurrentDocument"第12章实例——面向对象的Windows应用程序框架 132第1章概述简述冯・诺依曼计算机的工作模型。答:冯・诺依曼计算机的工作模型是:待执行的程序从外存装入到内存中,CPU从内存中逐条地取程序中的指令执行:程序执行中所需要的数据从内存或从外设中获得,程序执行中产生的中间结果保存在内存中,程序的执行结果通过外设输出。简述寄存器、内存以及外存的区别。答：寄存器主要用于记录下一条指令的内存地址、当前指令的执行状态以及暂时保存指令的计算结果供下ー（几）条指令使用,其作用主要是减少访问内存的次数，提高指令的执行效率。内存用于存储计算机程序（指令和数据）,内存由许多存储单元构成,每个存储单元都有一个地址,对存储单元的访问是通过其地址来进行的，与寄存器相比，内存的容量要大得多，但指令访问内存单元所花费的时间比访问寄存器要多得多。外存是大容量的低速存储部件,用于永久性地存储程序、数据以及各种文档等信息，存储在外存中的信息通常以文件形式进行组织和访问,外存储了在容量和速度上与内存不同，另ー个区别在于内存中存储的是正在运行的程序和正在使用的数据,外存中存储的则是大量的、并非正在使用的程序和数据。CPU能执行哪些指令?答：CPU所能执行的指令通常有：算术指令：实现加、减、乘、除等运算。比较指令：比较两个操作数的大小。数据传输指令：实现CPU的寄存器、内存以及外设之间的数据传输。执行流程控制指令：用于确定下一条指令的内存地址，包括转移、循环以及子程序调用/返回等指令。什么是软件?软件是如何分类的?答：计算机软件是计算机系统中的程序以及有关的文档。程序是对计算任务的处理对象（数据）与处理规则（算法）的描述;文档是为了便于大理解程序所需的资料说明,供程序开发与维护使用。软件通常可以分为系统软件、支撑软件和应用软件。系统软件居于计算机系统中最靠近硬件的ー级，它与具体的应用领域无关，其他软件一般要通过系统软件发挥作用,如操作系统属于系统软件。支撑软件是指支持软件开发与维护的软件,一般由软件开发大员使用,如软件开发环境就是典型的支撑软件。应用软件是指用于特定领域的专用软件，如大口普查软件、财务软件等。什么是虚拟机?答:在由硬件构成的计算机（称为“裸机”）之上,加上ー些软件就得到了一个比它功能更强的计算机,称为“虚拟机”。十进制数0.1的二进制表示是什么?答:（0.1）10=（0.000110011…）2,它是无限循环小数。也就是说,十进制数0.1无法精确用二进制表示!简述程序设计范型。答：基于不同的计算模型来对计算进行描述就形成了不同的程序设计范型。典型的程序设计范型有：过程式、对象式、函数式以及逻辑式等。过程式程序设计是ー种以功能为中心、基于功能分解和过程抽象的程序设计范型。一个过程式程序由一些子程序构成,每个子程序对应ー个子功能，它实现了功能抽象。对象式程序设计是一种以数据为中心、基于数据抽象的程序设计范型。一个面向対象程序由一些对象构成，对象是由一些数据及可施于这些数据上的操作所组成的封装体。函数式程序设计是围绕函数来进行的，计算过程体现为ー系列的函数应用。逻辑程序设计是把程序组织成一组事实和一组推理规则，在事实基础上运用推理规则来实施计算。简述程序设计的步骤。答：程序设计ー一般遵循以下步骤:明确问题:系统设计:用某种语言进行编程:测试与调试:运行与维护低级语言与高级语言的不同之处是什么?答：低级语言是指与特定计算机体系结构密切相关的程序语言,它是特定计算机能够直接理解的语言（或与之直接对应的语言），包括机器语言和汇编语言。低级语言的优点在于:写出的程序效率比较高,包括执行速度快和占用空间少。其缺点是：程序难以设计、理解与维护,难以保证程序的正确性。高级语言是指人容易理解和有利于人对解题过程进行描述的程序语言。高级语言的优点在于:程序容易设计、理解与维护,容易保证程序正确性。高级语言的缺点是：用其编写的程序相对于用低级语言编写的程序效率要低,翻译成的目标代码量较大。简述编译与解释的区别。答:编译是指把高级语言程序首先翻译成功能上等价的机器语言程序或汇编语言程序,然后执行目标代码程序,在目标代码程序的执行中不再需要源程序。解释则是指対源程序中的语句进行逐条翻译并执行,翻译完了程序也就执行完了,这种翻译方式不产生目标程序。一般来说,编译执行比解释执行效率要高。简述C++程序的编译执行过程。在你的C++开发环境中运行1.3.2节中给出的简单C++程序。答:首先可以利用某个编辑程序把C++源程序输入到计算机中,并作为文件保存到外存中，文件名为“*.cpp”和“*.h”。然后利用某个C++编译程序对保存在外存中的C++源程序进行编译,编译结果作为目标文件保存到外存,文件名为“*.obj"。然后再通过ー个联接程序把由源文件产生的目标文件以及程序中用到的一些系统功能所在的目标文件联接起来,作为ー个可执行文件保存到外存，文件名为“*.exe"。最后通过操作系统提供的应用程序运行机制，把可执行文件装入内存,运行其中的可执行程序。在VisualC++6.0环境中,苜先要建立一个project（项目）;其次往该project中添加、编辑程序模块（源文件）;然后选择菜单Build中的Build...或RebuildAH;最后选择菜单Build中的Execute...运行程序。C++的单词分成哪些种类?答:构成C++的单词有:标识符、关键词、字面常量、操作符以及标点符号等。下面哪ー些是合法的C++标识符?extern,_book,Car,car_l,calr,Icar,friend,carl_Car,Car_Type,No.1,123答:合法的C++标识符:_book,Car,car_l,calr,carl_Car,Car_Type第2章基本数据类型和表达式C++提供了哪些基本数据类型?检查你的计算机上各种类型数据所占内存空间的大小（字节数）。答:C++提供了以下5种基本数据类型:整数类型、实数类型、字符类型、逻辑类型以及空值类型。一台计算机上各种数据类型的数据所占用的内存大小（字节数）可以通过“sizeof（类型名）”来计算。下面哪一些是合法的C++字面常量,它们的类型是什么?-5.23,.20,-000,red,-5.23,.20,-000,red,le+50,e5,A,'\r',105, 20-0.0e5,'Xn*,3.14',false答:字面常量是指在程序中直接写出常量值的常量。-5.23,le+50,-25,20,.20,le-5,-0.0e5,'\n',"000,'A', '5','\r','\f',"TodayisMonday.","ヽ""都是字面常量。其中:整数类型常量:-25,20,-000实数类型常量:-5.23,le+50,.20,le-5,-0.0e5字符常量:'\n', 'A', '5','\r','\f'字符串常量："TodayisMonday.", "\""什么是符号常量?符号常量的优点是什么?答：符号常量是指有名字的常量,在程序中通过常量的名字来使用这些常量。程序屮使用符号常量有以下优点：1）增加程序易读性2）提高程序对常量使用的一致性3）增强程序的易维护性如何理解变量?变量定义和声明的作用是什么?答:在程序中,其值可以改变的量称为变量。变量可以用来表示可变的数据。程序中使用到的每个变量都要有定义。变量定义指出变量的类型和变量名，另外还可以为变量提供ー个初值。C++中使用变量之前，必须对使用的变量进行声明（变量定义属于ー种声明，即：定义性声明）,变量声明指出了一个变量的类型，使得编译程序能对变量的操作进行类型检查并做相应的类型转换。整个程序中,某变量的定义只能由一个，但它的声明可以有多个。什么是表达式?其作用是什么?答：表达式是由操作符、操作数以及圆括号所组成的运算式。在程序设计语言中，对数据操作的具体实施是通过表达式来描述的。操作符的优先级和结合性分别是指的什么?答：运算符的优先级和结合性决定表达式中各个运算符的运算次序。操作符的优先级规定了相邻的两个操作符谁先运算：优先级高的先计算;如果相邻的两个操作符具有相同的优先级,则需根据操作符的结合性来决定先计算谁,操作符的结合性通常分为左结合和右结合:左结合表示从左到右计算,右结合表示从右到左计算。表达式中的类型转换规则是什么?下面的表达式计算时如何进行操作数类型转换?3/5*12.3'a'+10*5.212U+3.0F*24L答:表达式中类型转换规则是:基于单个操作符依次进行转换。3与5同类型,不转换,结果为〇,转换成double型后与12.3做乘法。10转换成double型与5.2做乘法,，a，转换成double型后与前者结果做加法。3.0F与24L均转换成double型后做乘法,12U转换成double型后与前者结果做加法。将下列公式表示成C++的表达式：…加+(可利用C++标准库中的求平方根的函数:sqrt(x))2aJs(s_a)(s_b)(s-c)答:1)(-l*b+sqrt(b*b-4*a*c))/(2*a)sqrt(s*(s-a)*(s-b)*(s-c))((a*b)/(c*d))*(3/(l+(b/(2.5+c))))+(4*pi*r*r*r/3)写出下列条件的C++表达式i能被j整除。Ch为字母字符。m为偶数。n是小于100的奇数。a、b、c构成三角形的三条边。答：1)i%j==0((ch>='a')&&(ch<='z'))||((ch>='A')&&(ch<='Z'))m%2==0(n<100)&&(n%2!=0)(a>0)&&(b>0)&&(c>0)&&(a+b>c)&&(b+c>a)&&(c+a>b)或((a+b)>c)&&(abs(a-b)<c) //(a>0)&&(b>0)&&(c>0)可以不用判断在你的计算机上运行下面的程序:#include<iostream>usingnamespacestd;intmain(){doublea=3.3,b=l.1;inti=a/b;cout<<i<<endl;return0;结果与你预期的是否相符?如果不符,请解释它的原因。答:运行结果为2。由于十进制小数3.3和1.1无法用double型精确表示。通过查看结果内存内的内容,最终结果比3.0略小,所以强制转换成int型后结果为2。不引进第三个变量,如何交换两个整型变量的值?答：方法一：a=b人a;b=aAb;a=bAa;方法二：a=a+b;b=a-b;a=a-b;举例说明把int类型转成float类型可能会丢失精度。答：如果int型与float型都是4个字节，由于在float型的数据表示中，有若干位用来表示指数,因此,尾数的位数不到4个字节(根据IEEE标准，只有23个二进制位)。如果ー个int型的数大于23位(二进制)，则无法用float型精确表示。例如：intx=0x01000001;floaty=x;//x的最后一位T’不是被截掉就是被舍入!cout«x«endl«setprecision(30)«y«endl;第3章程序的流程控制ーー语句编写ー个程序,将华氏温度转换为摄氏温度。转换公式为:c=|(f-32),其中，c为摄氏温度，f为华氏温度解：#include<iostream>usingnamespacestd;intmain(){doublec,f;cout«"PleaseinputanF-temperature:"«endl;cin»f;c=(f-32)*5/9;cout«"TheC-temperatureis:"«c«endl;return0;编写ー个程序,将用24小时制表示的时间转换为12小时制表示的时间。例如,输入20和16(20点】6分),输出8:16pm:输入8和16(8点16分),输出8:16am。解:#include<iostream>usingnamespacestd;intmain(){inthour,minute;charnoon;cout«"Pleaseinputatimein24-hourformat:"«endl;cout«"hour:";cin»hour;if(hour<0IIhour>23){cout«"Theinputhouriswrong!"«endl;return-1;if(hour>12){hour=hour-12;noon='p*;elsenoon=*a';cout«"minute:M;cin»minute;if(minute<0IIminute>59){cout«"Theinputminuteiswrong!"«endl;return-1;cout«endl«"Thetimein12-hourformatis:"«hour«”:"«minute;if(noon='p')cout«"pm"«endl;elsecout«"am"«endl;return0;编写一个程序,分别按正向和逆向输出小写字母a〜z。解:#include<iostream>usingnamespacestd;intmain(){charc;for(c=*a';c<=*z';C++)cout«c«"";cout«endl;for(c=,z,;c>='a';c-)cout«c«""；cout«endl;return0;编写ー个程序,从键盘输入ー个正整数,判断该正整数为几位数,并输出其位数解:#include<iostream>usingnamespacestd;intmain(){unsignedintgzint;intcount=0;while(1){cout«"Pleaseinputaninteger(greaterthanzero):"«endl;cin»gzint;if(gzint<=0)cout«"Yourinputiswrong!Pleaseinputagain..."«endl;elsebreak;while(gzint!=0){gzint=gzint/10;count++;cout«"Thenumberofdigitsintheintergeris:"«count«endl;return0;编写ー个程序,对输入的ー个算术表达式(以字符#结束),检查圆括号配对情况。输出配对、多左括号或多右括号。解:#include<iostream>usingnamespacestd;intmain(){intcount=0;charch;cout«"Pleaseinputanexpression:"«endl;fbr(cin»ch;ch!='#';cin»ch){if(ch==ncount++;elseif(ch==')')count-;if(count==0)cout«"配对!”«endl;elseif(count>0)cout«”多左括号!”«endl;elsecout«”多右括号!”vvendl;return0;编写ー个程序,输入一个字符串(以字符#结束),对其中的“〉不进行计数解:#include<iostream>usingnamespacestd;intmain(){intcount=0;charchl=\。',ch2;cout«"Pleaseinputastring(terminatedwith#):"«endl;for(cin»ch2;ch2!='#';cin»ch2){if(ch2='='&&chi=='>')count++;chi=ch2;cout«”Numberof>=:"«count«endl;return0;假定邮寄包裹的计费标准如下(重量在档次之间时往上ー挡靠):重量(克)收费(元)TOC\o"1-5"\h\z15 530 945 1260 14 (每满1000公里加收1元)60以上 15 (每满1000公里加收2元)编写ー个程序,输入包裹重量和邮寄距离,计算并输出收费数额解:#include<iostream>usingnamespacestd;intmain(){intcharge;doubleweight;cout«"Pleaseinputtheweightofthepackage:"«endl;cin»weight;if(weight<=0)cout«'Theinputweightiswrong!"«endl;elseif(weight<=15)charge=5;elseif(weight<=30)charge=9;elseif(weight<=45)charge=12;else{doubledistance;cout«"Pleaseinputthedistance:"«endl;cin»distance;if(distance<=0)cout«'Theinputeddistanceiswrong!"«endl;else{distance/=1000;if(weight<=60)charge=14+(int)distance;elsecharge=15+(int)distance*2;)}cout«charge«endl;return0;}编写ー个程序,计算圆周率。可利用公式:直到最后ー项的绝对值小于!0\解:#include<iostream>#include<cmath>usingnamespacestd;intmain(){doubleitem=1.0,sum=0.0;inti=l,sign=l;while(fabs(item)>=le-8){sum+=item;sign*=-1;i+=2;item=sign/(double)i;cout«setprecision(8)«sum*4«endl;return0;编写ー个程序,求所有这样的三位数,它们等于它们的各位数字的立方和。例如153=I3+334-53解:#include<iostream>usingnamespacestd;intmain(){for(intn=100;n<=999;n++){inti,j,k;i=n/100;〃百位数字j=n%100八〇;〃十位数字k=n%10;〃个位数字if(n==i*i*i+j*j*j+k*k*k)cout«n«endl;return0;1或#include<iostream>usingnamespacestd;intmain(){for(inti=1;i<=9;i++){intn=i*100,m=i*i*i;for(intj=0;j<=9;j++){intnl=n+j*IO,ml=m+j*j*j;for(intk=0;k<=9;k++){if(nl+k==ml+k*k*k)J_return0;编写・个程序,求a和b的最大公约数。解:#include<iostream>usingnamespacestd;intmain(){inta,b;cout«”Pleaseinputa,b:M«endl;cin»a»b;intc=(a>b)?b:a;while(c>0){if(a%c=0&&b%c==0)break;c-；cout«c«endl;return0;或#include<iostream>

usingnamespacestd;intmain(){inta,b;cout«"Pleaseinputa,b:M«endl;cin»a»b;intc;do{c=a-b*(a/b);a=b;b=c;}while(c!=0);cout«a«endl;return0;)或#include<iostream>usingnamespacestd;intmain(){inta,b;cout«"Pleaseinputa,b:"«endl;cin»a»b;intc=(a>b)?b:a;a=(a>b)?a:b;b=c;while(c>0){c=a%b;a=b;b=c;cout«a«endl;return0;编写ー个程序,输出十进制乘法表。12112224336991839396189272781解:#include<iostream>usingnamespacestd;intmain(){for(inti=0;i<10;i++){if(i!=0)cout«i;cout«へ”；for(intj=l;j<10;j++)if(i*j!=0)cout«i*j«'ヘビ;elsecout«j«”\t"；cout«endl;}return0;将下面的for循环重写为等价的while循环for(i=0;i<max_length;i++)if(input_line[i]==*?1)quest_count++解:i=0；while(i<max_length){if(input_line[i]=='?')quest_count++;i++；说明下面的三个程序可以用图3-6中的三种控制结构来表示

过程抽（的作用一段程序代码它通常完成一个独立的为其!!也地方通过子程域简述局部变量的作用。答:子程序是南在程斥过程抽（的作用一段程序代码它通常完成一个独立的为其!!也地方通过子程域简述局部变量的作用。答:子程序是南在程斥月名字来使用它们。除了能减少程有代码外,手用子程品勺主要作用是实现过程抽象,使用者只需知道子程序的功能,而不需要知道它是如何实现的,这有利于大型、复杂程序的设计和理解。第4章答:1、实现信息隐藏,使得函数外无法访问该函数内部使用的数据。2、减少名冲突,ー个函数可以为局部变量定义任何合法名字,而不用担心与其他函数的局部变量同名。2、局部变量的内存空间在栈中分配,函数调用完之后释放,因此,使用局部变量能节省程序的内存空间。简述变量的生存期和标识符的作用域。答:变量的生存期指程序运行时一个变量占有内存空间的时间段。C++把变量的生存期分为静态、自动和动态三种。标识符的作用域是指:ー个定义了的标识符的有效范围,即该标识符所标识的程序实体能被访问的程序段。在C++中,根据标识符的性质和定义位置规定了标识符的作用域。作用域分为:全局作用域、文件作用域、局部作用域、函数作用域、函数原型作用域、类作用域、名空间作用域。全局标识符与局部标识符在哪些方面存在不同?答:1、作用域不同2、生存期不同3、用途不同,全局标识符用于标识共享的实体,而局部标识符用于标识专用的实体。下面的声明中哪ー些是定义性声明?这些定义性声明的非定义性声明是什么?constinti=l;staticdoublesquare(doubledbl){returndbl*dbl;}char*str;structPoint;char*(*pFn)(int(*)(char*,int),char**);答:1)是。非定义性声明:externconstinti;2)是。非定义性声明:externdoublesquare(double);3)是。非定义性声明：externchar*str;4)不是。5)是。非定义性声明：externchar*(*pFn)(int(*)(char*,int),char**);下面的宏cubel和函数cube2相比,各有什么优缺点?#definecubel(x)((x)*(x)*(x))doublecube2(doublex){returnx*x*x;}答:小型函数的频繁调用会带来程序执行效率的严重下降,宏的出现解决了函数调用效率不高的问题,但宏本身也存在很多问题:(1)宏会出现重复计算,(2)不进行参数类型检查和转换,(3)不利于ー些工具对程序的处理。而函数可以很好的处理这些问题。另外,对于:inta;当a的值很大时,cube1(a)得不到正确结果!(因为结果类型为int,而如果a*a*a的结果超出了int型的范围,则结果将会截断!)编写ー个函数digit(n,k),它计算整数n的从右向左的第k个数字。例如:digit(123456,3)=4digit(1234,5)=0合:intdigit(intn,intk){for(inti=l;i<k;i++)n=n/10;分别用函数实现习题3.8中的第1、4、7和10题的程序功能。答:第1题：return(x-32)*5/9;第4题:intnum_ofldigits(intgzint){intcount=0;if(gzint<0)gzint=-gzint;while(gzint!=0){gzint=gzint/10;count++;returncount;第7题:doublecharge(doubleweight,doubledistance)(doublemoney=0;if(weight<=15)money=5;elseelseelseelseif(weight<=30)if(weight<=45)if(weight<=60)money=15+(int)money=9;money=12;money=14+(int)(distance/1000);(distance/1000)*2;returnmoney;|第10题:intgcd(inta,intb){intmax=a>b?a:b;for(inti=max;i>0;i—)if((a%i==0)&&(b%i==0))returni;写出下面程序的执行结果:#include<iostream>usingnamespacestd;intcount=0;intfib(intn){count++;if(n==lreturnelsereturn}IIn==2)1；fib(n-l)+fib(n-2);intmain(){cout«fib(8);cout<<','<<count<<endl;return0;}答:21,41分别写出计算Hermit多项式Hn(x)值的迭代和递归函数。Hn(x)定义如下:Ho(x)=1%(x)=2xHn(x)=2xHn-i(x)-2(n-1)Hn_2(x) (n>l)答:#include<iostream>usingnamespacestd;doubleHermit__Iterative(int,double); //迭代方法doubleHermit_Recursion(int,double); //递归方法voidmain(){constintn=3; 〃n与x可自行指定doublex=3.14;cout<<Hermit_Iterative(n,x)<<endl<<Hermit_Recursion(n,x)<<endl;doubleHermit_Iterative(intn,doublex)(if(n==0)return1;elseif(n==l)return2*x;else{doubleresl=l,res2=2*x;doubleResult=0;for(inti=2;i<=n;i++){Result=2*x*res2-2*(i-1)*resl;resl=res2;res2=Result;returnResult;doubleHermit__Recursion(intn,doublex)(if(n==0)return1;elseif(n==l)return2*x;elsereturn2*x*Hermit_Recursion(n-1,x)-2*(n-1)*Hermit_Recursion(n-2,x)写出计算Ackermann函数Ack(m,n)值的递归函数。Ack(m,n)定义如下(m20,n20)：Ack(0,n)=n+1Ack(mz0)=Ack(m-1,1)Ack(mzn)=Ack(m-1zAck(mzn-1)) (m>0zn>0)答:intAck.(intm,intn){if(m==0)returnn+1;elseif(n==0)returnAck(m-1/1);elsereturnAck(m-1,Ack(m,n-1));根据下图写ー个函数:intpath(intn);用于计算从结点1到结点n(n大于1)共有多少条不同的路径。答:intpath(intn){if(n=l)return1;if(n==2)return1;if(n==3)return2;if(n%2==0)returnpath(n-l)+path(n-2)+path(n-3);elsereturnpath(n-1)+path(n-2);)编程解决下面的问题:若一头小母牛,从出生起第四个年头开始每年生一头母牛,按此规律,第n年有多少头母牛?答:除了第•年到第三年外,每•年的母牛数应该是上・年的母牛数加上三年前的母牛数(现在它们是第四年T,要生小牛了!)intf(intn){if(n==lIIn==2I|n==3)return1;returnf(n-3)+f(n-1);假设有三个重载的函数:voidfunc(intzdouble);voidfunc(long,double);voidfunc(int,char);对下面的函数调用,指出它们分别调用了哪ー个重载函数;如果有歧义,指出导致歧义的重载函数定义。func('5,3.0);func(3L,3);func("three*',3.0);func(3L,*c');func(true,3);答:func('c*,3.0);与voidfunc(int,double);匹配func(3L,3);与voidfunc(long,double);匹酉ピfunc("three",3.0);没有与之匹配的函数func(3L,'c');与voidfunc(long,double);和voidfunc(int,char);均能匹配func(true,3);与voidfunc(int,double);和voidfunc(int,char);均能匹配下面的函数定义为什么是正确的?在函数f中如何区分(使用)它们?voidf(){intf;答:两个f的作用域不一样,voidf()中的f为全局作用域,intf;中的f为局部作用域。在函数f中如果使用局部变量,则用f;如果使用函数f,则用::f。为什么一般把内联函数的定义放在个头文件中?答:为了防止同一个内联函数的各个定义之间的不一致,往往把内联函数的定义放在某个头文件中,在需要使用该内联函数的源文件中用文件包含命令#include把该头文件包含进来。由于内联函数名具有文件作用域,因此,不会出现重复定义问题。用循环实现例4-12中的辗转相除法计算最大公约数。答:intgcd(intx,inty){while(y!=0){intt=y;y=x%y;x=t;returnx;第5章构造数据类型枚举类型有什么好处?C++对枚举类型的操作有何规定?答:使用枚举类型有利于提高程序的易读性;使用枚举类型也有利于保证程序的正确性。首先,可以对枚举类型实施赋值操作,但不同枚举类型之间不能相互赋值,而且不能把一个整型数直接赋值给枚举类型的变量。还可以对枚举类型实施比较运算。还可以对枚举类型实施算术运算,对枚举类型的运算前要转换成对应的整型值,且运算结果类型为算术类型,而且不能对枚举类型的值直接进行输入/输出。指针类型主要用于什么场合?引用类型与指针类型相比,其优势在哪里?答:指针类型主要用于参数传递和对动态变量的访问。在C++中,指针类型还用于访问数组元素,以提高访问效率。引用类型与指针类型都可以实现通过一个变量访问另ー个变量,但访问的语法形式不同:引用是采用直接访问形式,指针则采用间接访问形式。在作为函数参数类型时,引用类型参数的实参是一个变量，而指针类型参数的实参是ー个变量的地址。除了在定义时指定的被引用变量外,引用类型变量不能再引用其他变量;而指针变量定义后可以指向其他同类型的变量。因此,引用类型比指针类型要安全。引用类型的间接访问对使用者而言是透明的。写出下面程序的运行结果:#include<iostream>usingneunespacestd;voidf(int&xzinty){y=x+y;x=y%3;cout<<x<<‘、七’<<y<<endl;intmain(){intx=10,y=19;f(y,x)；cout<<x<<'\t'<<y<<endl;£(x,x);cout<<x<<'\t'<<y<<endl;return0;TOC\o"1-5"\h\z答:2 2910 22 202 2从键盘输入某个星期每一天的最高和最低温度,然后计算该星期的平均最低和平均最高温度并输出之。解:#include<iostream>usingnamespacestd;enumDay{SUN,MON,TUE,WED,THU,FRエ,SAT};intmain(){doublemax,min,maxsum=0for(Dayd=SUN;d<=SA{cout<<"Pleaseinput"switch(d){caseSUN:{cout<<"caseMON:{cout<<"caseTUE:{cout<<"caseWED:{cout<<"caseTHU:{cout<<"caseFRI:{cout<<"caseSAT:{cout<<",minsum=0;T;d=(Day)(d+1))JSunday";break;}Monday”；break;}Tuesday";break;}Wednesday";break;}Thursday";break;}Friday";break;}Saturday";break;}cout<<'*1stemperature(maxmin):"<<endl;cin>>max>>min;maxsum+=max;minsum+=min;cout<<"Theaveragetemperatureofmaxismis:"<<maxsum/7.0<<endlcout<<"Theaveragetemperatureofminismis:"<<minsum/7.0<<endlreturn0;编写ー个函数,判断其int型参数值是否是回文数。回文数是指从正向和反向两个方向读数字都ー样,例如,9783879就是ー个回文数。解:boolis_huiwen(intnum){charwei[100],i=0;while(num!=0){wei[i]=num%10;num/=10;i++；for(intj=0;j<=i/2;j++){if(wei[j]!=wei[i-j-1])returnfalse;returntrue;编写ー个函数int_to_str(imn,charstr口),把ー个int型数(由参数n表示)转换成・个字符串(放在str中)〇解:voidint_to_str(intnum,char*str){charc;inti=0;while(num!=0){str[i]=num%10+'0*;numI-10;i++；}str[i]='\0,;for(intj=0;j<i/2;j++){c=str[j];str[j]=strは-j-l];str[i-j-1]=c;编写ー个函数计算ー元二次方程的根。要求:方程的系数和根均用参数传递机制来传递。解:intqiugen(doublea,doubleb,doublec,double&xl,double&x2){inti=b*b-4*a*c;if(i>=0){xl=(sqrt(i)-b)/(2*a);x2=(0-sqrt(i)-b)/(2*a);return1;else{xl=(0-b)/(2*a);x2=sqrt(0-i)/(2*a);return0;编写ー个程序,从键盘输入ー个字符串,分别统计其中的大写字母、小写字母以及数字的个数解:#include<iostream>usingnamespacestd;intmain(){charstr[100];cout<<"Pleaseinputastring:\n";cin>>str;intcount_lower=0,count_upper=0,count_num=0;for(inti=0;str[i]!='、〇，i++){if(str[i]>='A'&&str[i]<=*Z')count_upper++;elseif(str[i]>='a'&&str[i]<='z')count_lower++;elseif(str[i]>=101&&str[i]<='9')count_num++;cout<<count_upper<<'\t*<<count_lower<<'\t'<<count_num<<endl;return0;021设有一个矩阵：102,现把它放在一个二维数组a中。写出执行下面的语句之后a的值120for(inti=0;i<=2;i++)for(intj=0;j<=2;j++)a[i][j]=a[a[i][j]][a[j][i]];解：0 2 020 02 2 0实现下面的数组元素交换位置函数:voidswap(inta[],intm,intn);该函数能够把数组a的前m个元素与后n个元素交换位置,即,交换前:81，a2，•••，3m/3^+1/3^+2/•••r3m+N交换后:3m+irHm+2，•一，aM+N，a]，a2，•••/3m要求：除数组a外,不得引入其它数组。解:voidswap(inta[]rintm,intn);{for(inti=0;i<m;i++){intt=a[0];for(intj=l;j<m+n;j++)a[j-1]=a[j];A[m+n-1]=t;编写ー个程序,计算ー个矩阵的鞍点。矩阵的鞍点是指矩阵中的ー个位置,该位置上的元素在其所在的行上最大、列上最小。(ー个矩阵也可能没有鞍点。)#include<iostream>usingnamespacestd;#defineM3#defineN3intmain()(inta[M][N];//存放矩阵inti,j;//输入矩阵元素for(i=0;i<M;i++)for(j=0;j<N;j++)

cin>>a[i][j];intlin_max[M],//存放各行的最大元素col__min[N];//存放各列的最小元素〃计算每行的最大元素for(i=0;i<M;i++){intmax=a[i][0];for(j=l;j<N;j++)if(a[i][j]>max)max=a[i][j];lin_max[i]=max;〃计算每列的最小元素for(j=0;j<N;j++){intmin=a[0][j];for(i=l;i<M;i++)if(a[i][j]<min)min=a[i][j];col_min[j]=min;//求鞍点for(i=0;i<M;i++){for(j=0;j<N;j++){if(a[i](j]==lin_max[i]&&a[i)[j]==col_min[j]){cout<<"鞍点是:"<<i<<*,'<<j<<endl;cout<<”没有鞍点、n”；return0;编程实现:在ー个由NXN(N为大于1的奇数)个方格组成的方阵中,填入1,2、3、...、M各个数,使得每一行、每一列以及两个对角线上数的和均相等(奇数幻方问题)。例如,下面是ー个3X3的幻方:TOC\o"1-5"\h\z8 1 65 79 2(提示:把1填在第一行最中间的格子中,然后按下面的方法依次来填其它的数:如果当前格子是方阵中最右上角的格子,则把下一个数填在下一行的同一列格子中;否则，如果当前格子在第一行上,则把下