数控铣中级工考证理论习题集-mis-广州铁路职业技术学院(常用版)

数控铣中级工考证理论习题集-mis-广州铁路职业技术学院（常用版）(可以直接使用，可编辑完整版资料，欢迎下载）

第一章机器的组成与制造数控铣中级工考证理论习题集-mis-广州铁路职业技术学院（常用版）(可以直接使用，可编辑完整版资料，欢迎下载）一、单项选择题1．车床的主轴箱属于车床的()。A．动力部分B．传动部分C．工作部分D．控制部分2．在数控机床中，对工作台实际位移量进行自动检测，并与指令进行比较，用差值进行控制调节，这种控制系统称为()。A．模拟控制系统B．数字控制系统C．闭环控制系统D．开环控制系统3．由零件、部件组成的，具有确定的相对运动，可进行能量转换或做机械功的实体组合称为()。A．机构B．机器C．构件D．生产线4．以下论述正确的是()。A．机器的工作部分是直接完成机器预定功能的部分B．具有相对运动的构件组合称为机构C．机器传动部分的功能是将动力传递到工作部分D．机器是机械和机构的统称5．四冲程内燃机的活塞组由活塞、活塞环和活塞销等组成，所以活塞组是()。A．零件B．构件C．机构D．制造单元6．将原材料变为产品的全过程称为()。A．生产服务过程B．生产过程C．零件加工过程D．生产工艺过程7．以工序为单位，说明一个工件全部加工过程的卡片称为()。A．工序卡片B．工艺过程卡片C．生产卡片D．技术卡片8．车床床身的毛坯大都是()而成。A．铸造B．锻造C．焊接D．切削加工9．压力加工过程中，使坯料产生变形的原因是()。A．内应力作用B．外力作用C．重力作用D．热应力作用10．钎焊时()。A．被焊金属熔化B．钎料熔化C．被焊金属和钎料都熔化D．被焊金属和钎料都不熔化11．将毛坯上的多余材料去除，从而获得几何形状、加工精度和表面粗糙度都符合要求的零件加工方法称为()。A．铸造B．锻造C．焊接D．切削加工12．对重要零件进行热处理的主要目的是()。A．改变零件尺寸B．改变零件形状C．改变材料性能D．提高零件精度13．下列工作中，()不属于机器装配工作范围。A．热处理B．检验C．油漆D．包装14．由()可以看出机器零件尺寸精度的高低。A．基本尺寸B．最小极限尺寸C．上偏差D．尺寸公差15．尺寸公差的数值()。A．可以为零B．可以为正值C．可以为负值D．可以为正值、负值，但不可以为零16．一根φ40的光轴，直径按下列精度进行加工均能满足使用要求，尺寸公差为()加工费最低。A．IT5B．IT6C．IT7D．IT817．下列有关公差的论述中，不正确的是()。A．加工合格的零件，其实际尺寸可能大于也可能小于基本尺寸B．圆跳动属于形状公差C．位置精度是指加工后零件有关要素，相互之间的实际位置与理想位置的符合程度D．零件上同一表面的同一尺寸形状公差不允许大于尺寸公差值18．轮廓算术平均值Ra是评定表面粗糙度的一种数值，其单位为()。A．mB．cmC．mmD．μm19．轴和孔之间依靠配合传递扭矩时，轴的公差带应()。A．完全在孔的公差带之下B．完全在孔的公差带之上C．与孔的公差带有部分重合D．与孔的公差带完全重合20．生产纲领是指()。A．工艺方案B．工艺文件C．工艺规程D．年产量21．用()方式制造出来的Y160-4型电动机转子制造成本最高。A．单件产量B．小批产量C．大批产量D．大量产量22．采用某种工艺方案进行生产所需的年度工艺成本可按Cn=D·Q+B进行计算，公式中B是()。A．生产纲领B．原材料费用C．可变费用D．不变费用二、多项选择题1．下列论述中不正确的有()。A．零件是机器的制造单元B．构件都是可动的C．具有相对运动的构件组合称为机构D．通常以机械这个词作为机构和机器的统称E．机器工作部分的结构形式取决于机械本身的组成情况2．从动能角度进行分析，机器由()组成。A．动力部分B．传动部分C．控制部分D．能量转换部分E．工作部分3．在机器金属零件的生产中，获得毛坯的主要方法有()。A．铸造B．锻造C．冲压D．焊接E．热处理4．下列热处理工艺中()属于普通热处理。A．退火B．正火C．淬火D．回火E．渗碳5．零件的加工精度主要包括()等方面。A．表面粗糙度B．尺寸精度C．位置精度D．形状精度E．装配精度6．一般情况下，机器零件表面的轮廓算术平均值偏差Ra的数值越小，机器零件()越好。A．配合的稳定性B．耐磨性C．工作精度D．形状精度E．抗腐蚀性7．下列论述中正确的有()。A．零件加工质量的主要指标是尺寸精度和表面粗糙度B．零件的尺寸公差主要用来限制零件的尺寸误差C．尺寸公差不可以为负值，也不可以为零D．零件尺寸公差数值越小，其加工成本越高E．零件的表面粗糙度主要影响美观，对机器的使用没有什么影响8．下列项目中，属于形状公差的项目有()。A．圆度B．圆柱度C．圆跳度D．对称度E．面轮廓度9．下列焊接方法中属于熔焊的有()。A．气焊B．电弧焊C．电阻焊D．电渣焊E．等离子焊10．下列生产方法中属于压力加工的有()。A．自由锻造B．模锻C．冲压D．特种加工E．回火11．下列生产方法中，通过()可以改变合金钢的性能。A．改变合金钢的成分B．进行特种加工C．进行热处理D．提高加工精度E．提高零件的表面粗糙度12．通过()对机器零件进行表面热处理。A．表面淬火B．回火C．正火D．渗碳E．渗氮13．下列项目中属于钳工加工内容的有()。A．錾削B．锉削C．镗削D．划线E．绞孔14．通常()制造厂的主要产品属于大量生产。A．水压机B．汽车C．轴承D．自行车E．重型机床15．与单件生产相比，大量生产()。A．要求操作工技术高B．广泛使用专用机床和自动机床C．使用高效专用夹具、刀具和量具D．采用生产线进行生产E．生产成本高16．下列工艺成本项目中()为不变成本。A．通用夹具维护折旧费B．专用夹具维护折旧费C．调整工人工资与调整杂费D．机器的电费E．原材料费用17．下列论述中，正确的有()。A．工艺成本不变费用的变化与年产量成正比B．单件产品的工艺成本与年产量成双曲线关系C．工艺方案的回收期应小于所采用设备的使用年限D．在进行工艺方案经济分析时，应考虑改善劳动条件E．在进行工艺方案经济分析时，应考虑本企业的具体情况三、综合分析题1．从功能角度分析，机器由哪几部分组成?各组成部分有何功用?2．机器与机构的区别是什么?3．何谓机器的生产过程?何谓机器的制造工艺过程?4．为什么了解产品工艺过程就可以了解产品的生产情况?5．获得毛坯的方法有哪些?6．什么是切削加工?7．对零件进行热处理能提高加工精度吗?8．什么是加工精度?什么是加工误差?二者之间有何关系?9．机器零件加工质量的主要指标有哪些?10．什么是表面粗糙度?表面粗糙度对机器零件的使用性能有哪些影响?11．什么是形状公差?什么是位置公差?它们各有哪些项目?12．一对孔和轴，图纸上规定孔的尺寸为，轴的尺寸为。生产合格的孔、轴在装配中是如何配合并求出其极值。13．根据什么来确定生产类型?生产类型有哪几种?14．各种生产类型的主要工艺特征是什么?15．什么是生产成本?什么是工艺成本?16．工艺成本分为哪几类?17．分析说明单件产品的工艺成本与年产量的关系。参考答案第一章机器的组成与制造一、单项选择题1．B2．C3．B4．A5．B6．B7．B8．A9．B10．B11．D12．C13．A14．D15．B16．D17．B18．D19．B20．D21．A22．D二、多项选择题1．CE2．ABCE3．ABCD4．ABCD5．BCD6．ABCE7．BCD8．ABE9．ABDE10．ABC11．AC12．ADE13．ABDE14．BCD15．BCD16．BC17．BCDE三、综合分析题1．[答]按功能分析，机器由动力、传动、工作和控制四个部分组成。(1)动力部分：将其他形式的能量转变为机械能。其中，将一次能源直接转化为机械能的称为一次动力机，例如水轮机、内燃机等；而将二次能源如电能等转化为机械能的称为二次动力机，如电动机等。(2)传动部分：介于动力部分和工作部分之间，其功能是传递动力和运动、分配能量、改变速度和运动形式。按照传动的工作原理分为机械传动、流体传动、电力传动和磁力传动。(3)工作部分：直接完成机器预定功能的部分，是机器设备区分和分类的主要依据。(4)控制部分：完成被控参数的调节。控制部分由给定值发生器、比较器、驱动部件和执行机构、检测及变换元件四个部分组成。2．[答]机构由若干构件组成，各个构件之间具有确定的相对运动，并能实现运动和动力的传递。机器和机构一样，由若干构件组成，各个构件之间具有确定的相对运动，能实现运动和动力的传递，并且能够实现机械能和其他形式能量的转换。机器与机构的区别在于机器能实现能量的转换或代替人的劳动去做有用功，而机构没有这种功能。3．[答]机器的生产过程是指使原材料转变为产品的全过程，包括生产服务过程、技术准备过程、毛坯制造过程、零件加工过程和产品装配过程。机器生产的工艺过程，是指在产品生产过程中按照一定顺序，改变生产对象的形状、尺寸、相对位置或性质等使其成为产品或半成品的过程。包括毛坯制造、机械加工、热处理以及装配等过程。4．[答]加工工艺规程是将零部件或产品的制造工艺过程和操作方法，用表格或文字形式确定下来，作为组织生产、指导生产、编制生产计划的根据。了解了工艺规程，就可以了解原材料的供应、生产使用的机器的种类和数量、生产中需用的工艺装备、生产作业计划安排、劳动力的组织以及生产成本核算等。由此，了解生产工艺规程就可以了解产品的生产情况。5．[答]毛坯是根据零件或产品所需要的形状工艺尺寸而制成的供进一步加工的对象。获得毛坯的主要方法有：铸造、压力加工和焊接等。6．[答]切削加工是指利用刀具或特种加工，切去多余金属层，从而获得几何形状、尺寸精度和表面粗糙度都符合要求的零件的加工方法。7．[答]热处理是指金属材料在固态下加热、保温和冷却来改变金属内部的组织，从而获得所需性能的一种工艺方法。热处理工艺在机器零件制造过程中应用非常广泛，它能提高工件的使用性能，还可以改善工件的加工性能。对机器零件进行热处理不但不能提高零件的尺寸精度、形状精度和位置精度，相反，在热处理过程中零件产生变形，使零件的尺寸精度、形状精度、位置精度降低。8．[答]加工精度系指零件加工后，其实际几何参数(尺寸、形状和位置)与理想几何参数符合的程度。加工误差则指实际几何参数与理想几何参数的偏离程度。加工精度和加工误差这两个概念在评定零件几何参数中的作用是相同的。9．[答]机器零件加工质量的主要指标包括加工精度和表面粗糙度两个方面。零件的加工精度又包括尺寸精度、形状精度和位置精度。10．[答]表面粗糙度是指加工表面上具有较小间距的峰谷组成的微观集合形状特性。常用轮廓算术平均偏差来衡量，即在一定测量长度内，轮廓上各点至中线距离绝对值的算术平均值，记为Ra，单位为μm。Ra值越小，被测表面越光滑；反之，Ra值越大，表面越粗糙。表面粗糙度对机器零件的配合性质、耐磨性、工作精度、耐腐蚀性等有较大影响。11．[答]构成机器零件的几何要素如轴线、平面、圆柱面、曲面等，当仅对其本身形状给出公差要求时，称为单一实际要素，单一实际要素的形状所允许的变动量，称为形状公差。形状公差的项目有：直线度、平面度、圆度、圆柱度、线轮廓度和面轮廓度。构成机器零件的几何要素中，有些要素对其他要素有方向和位置要求。与其他要素有功能关系的要素称为关联要素。用来确定被测要素方位的要素，称为基准要素。关联实际要素的位置对基准．所允许的变动全量称为位置公差。位置公差的项目有：平行度、垂直度、倾斜度、同轴度、对称度、位置度、圆跳动和全跳动。12．[答]孔的最大极限尺寸为φ25.021，最小极限尺寸为φ25。轴的最大极限尺寸为φ24.993，最小极限尺寸为φ24.980。由上可知，此孔轴的配合中，孔公差带完全在轴公差带上，故为间隙配合，现计算其最大间隙和最小间隙。配合后最大间隙等于孑L的最大极限尺寸减去轴的最小极限尺寸，即：最大间隙=25.021-24.980=0.041(mm)。配合后最小间隙等于孔的最小极限尺寸减去轴的最大极限尺寸即：最小间隙=25-24.993=0.007(mm)。13．[答]根据产品的大小、复杂程度和生产纲领确定生产类型。生产类型分为单件生产、成批生产和大量生产三种。14．[答](1)单件生产：加工对象经常更换，一般使用通用机床，需要熟练的技术工人，只需编写简单的工艺卡片。(2)成批生产：毛坯精度中等：采用通用机床和一部分专用机床；一般采用专用夹具，较多采用专用刀具及量具；需要技术比较熟练的工人，要求编写工艺卡片。(3)大量生产：加工对象固定不变，广泛使用专用机床和自动机床，使用高效的毛坯加工方法，对于操作工的技术要求比较低，需要编写详细的工艺卡片和工序卡片。15．[答]制造一个零件或一台产品所必需的一切费用总和就是零件或产品的生产成本。其中，与工艺方案有关的费用总额就是工艺成本。16．[答]工艺成本分为两类：第一类为可变费用，这种费用与产品的产量成正比。第二类为不变费用，这部分在单位时间内完全或基本上不随产量的变化而变化。17．[答]单件产品的工艺成本与年产量呈双曲线关系。年产量很低时，单件工艺成本受年产量的影响很大，即年产量稍有增加，单件工艺成本就会显著下降；但当年产量增加到一定数值以后，单件工艺成本受年产量的影响就不再显著，这时，即使年产量有较大幅度增加，单件工艺成本的下降也十分有限。《数据结构习题集》习题1绪论1.1单项选择题1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上可以把数据结构分成。A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法分析的目的是①，算法分析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性1.2填空题（将正确的答案填在相应的空中）1.数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。4.在图形结构中，每个结点的前驱结点数和后续结点数可以。5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6.算法的五个重要特性是____,____,____,____,____。7.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;8.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。for(i=0;i<n;i++)for(j=0;j<i;j++)A[i][j]=0;9.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)s=s+B[i][j][k];sum=s;10.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。i=s=0;while(s<n){i++;s+=i;//s=s+i}11.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。i=1;while(i<=n)i=i*2;1.3算法设计题试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。习题答案1.11.C,A2.B,D3.C4.C,A5.C,B1.21.线性结构、树形结构、图形结构，非线性结构2.没有、1、没有、13.前驱、1、后续、任意多个4.任意多个5.一对一、一对多、多对多6.有穷性、确定性、可行性、输入、输出7.最大语句频度：n2，时间复杂度：.O(n2)8.最大语句频度：n(n+1)/2，时间复杂度：.O(n2)9.最大语句频度：n3，时间复杂度：.O(n3)10.最大语句频度：n，时间复杂度：.O(n)11.最大语句频度：log2n，时间复杂度：.O(log2n)习题2线性表2.1单项选择题1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。A.110B.108C.100D.1202.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取3.线性表的逻辑顺序与存储顺序总是一致的，这种说法___。A.正确B.不正确4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以5.在以下的叙述中，正确的是___。线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构6.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法___。A.正确B.不正确7.不带头结点的单链表head为空的判定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL8.带头结点的单链表head为空的判定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL9.非空的循环单链表head的尾结点（由p所指向）满足____。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;B.q->next=s;s->next=p;C.p->next=s;s->next=q;12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;C.p->next=s;s->next=p;13.在一个单链表中，若删除p所指结点的后续结点，则执行____。A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；C.p->next=p->next;D.p=p->next->next；14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/215.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.给定有n个元素的向量，建立一个有序单链表的时间复杂度是____。A.O(1)）B.O(n)C.O(n2)D.O(n*log2n)2.2填空题（将正确的答案填在相应的空中）1.单链表可以做____的链接存储表示。2.在双链表中，每个结点有两个指针域，一个指向______，另一个指向_____。3.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时，可执行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=;//填空s->next=;//填空4.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q=p->next;p->next=____;//填空delete;//填空5.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=____和p->next=____的操作。6.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是____；在给定值为x的结点后插入一个新结点的时间复杂度是____。2.3算法设计题:1.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,….an）逆置为(an,an-1,….,a1)。3.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。4.试写一算法，实现单链表的就地逆置(要求在原链表上进行)。习题答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.B12.B13.A14.D15.B16.C2.21.线性结表2.前驱结点、后继结点3.s,p4.q->next,q5.p->next,s6.O(1),O(n)习题3栈和队列3.1单项选择题1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。A.edcbaB.decbaC.dceabD.abcde2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。A.iB.n=iC.n-i+1D.不确定3.栈结构通常采用的两种存储结构是____。A.顺序存储结构和链式存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构4.判定一个顺序栈ST（最多元素为m0）为空的条件是____。A.top!=0B.top==0C.top!=m0D.top==m0-15.判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。A.top！=0B.top==0C.top！=m0D.top==m0-16.栈的特点是____，队列的特点是____。A.先进先出B.先进后出7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。(不带空的头结点)HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。(不带空的头结点)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;9.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，110.判定一个循环队列QU（最多元素为m0）为空的条件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是____。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front13.栈和队列的共同点是____。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点3.2填空题（将正确的答案填在相应的空中）1.向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。4.向栈中压入元素的操作是____。5.对栈进行退栈时的操作是____。6.在一个循环队列中，队首指针指向队首元素的____。7.从循环队列中删除一个元素时，其操作是____。8.在具有n个单元的循环队列中，队满时共有____个元素。9.一个栈的输入序列是12345，则栈的输出序列43512是____。10.一个栈的输入序列是12345，则栈的输出序列12345是____。3.3算法设计题:1.输入一个任意的非负十进制整数,输出与其等值的八进值数。2.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E↑F3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。习题答案3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C11.A12.A13.C3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i4.先移动栈顶指针，后存入元素5.先取出元素，后移动栈顶指针6.前一个位置7.先移动队首元素，后取出元素8.n-19.不可能的10.可能的习题4串4.1单项选择题1．以下叙述中正确的是。A.串是一种特殊的线性表 B.串的长度必须大于零C.串中无素只能是字母 D.空串就是空白串2．空串与空格串是相同的，这种说法____。A.正确B.不正确3．串是一中特殊的线性表，其特殊性体现在____。A.可以顺序存储 B.数据元素是一个字符C.可以链接存储 D.数据元素可以是多个字符4．设有两个串p和q，求q在p中首次出现的位置的运算称作____。A.连接 B.模式匹配C.求子串 D.求串长5．设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是____。A.BCDEF B.BCDEFGC.BCPQRST D.BCDEFEF6．设串的长度为n，则它的子串个数为。A.n B.n(n+1) C.n(n+1)/2 D.n(n+1)/2+14.2填空题（将正确的答案填在相应的空中）1．串的两种最基本的存储方式是____。2．两个串相等的充分必要条件是____。3．空串是____，其长度等于____。4．空格串是____，其长度等于____。5．设s=’I︺AM︺A︺TEACHER’,其长度是____。4.3判断题1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。 （）2．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际使用的价值。 （）3．KMP算法的最大特点是指主串的指针不需要回溯。 （）4．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。（）5．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）4.3算法设计题1．编写算法，从串s中删除所有和串t相同的子串。2．编写算法，实现串的基本操作Replace(&S,T,V)。3．写一个递归算法来实现字符串逆序存储，要求不另设存储空间。习题答案4.11．A 2．B3．B4．B5．D6．C4.21．顺序存储方式和链接存储方式2．两个串的长度相等且对应位置的字符相同3．零个字符的串、零4．由一个或多个空格字符组成的串、其包含的空格个数5．144.3 × × √ √ ×4.43.voidreverse(chararr[]){charch;inti=1; do{cin>>ch;reverse(arr);arr[i]=ch;i++;}while(ch!=’#’&&i<n)}习题5数组和广义表5.1单项选择题1.常对数组进行的两种基本操作是____。A.建立与删除B.索引和修改C.对数据元素的存取和修改D.查找与索引2.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M至少需要①__个字节；M数组的第8列和第5行共占②____个字节。①A.90B.180C.240D.540②A.108B.114C.54D.603.二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。A.80B.100C.240D.2704.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。A.SA+141B.SA+144C.SA+222D.SA+2255.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。A.SA+141B.SA+180C.SA+222D.SA+2255.2填空题（将正确的答案填在相应的空中）1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_______。2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。3.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。4．求下列广义表操作的结果：(1)GetTail[GetHead[((a,b),(c,d))]];(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分别从下列广义表中分离出来.(1)L1=(((apple)),((pear)),(banana),orange);(2)L2=(apple,(pear,(banana),orange));5.3算法设计题:1.假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。2.假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？其中m和n分别为A，B矩阵中非零元的数目。3．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。习题答案5.11.C2.D,A3.C4.C5.B5.21.LOC(A[0][0])+(n*i+j)*k2.200+（6*20+12）=3263.1000+((18-10)*6+(9-5))*4=12084．(1).(b)(2).(d)5.(1)GetHead[GetHead[GetTail[GetTail[L1]]]];(2)GetHead[GetHead[GetHead[GetTail[L2]]]];习题6树和二叉树6.1单项选择题1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。A.正确B.错误2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。A．15 B．16 C．17 D．473.按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。A.3B.4C.5D.64.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。A.5B.6C.30D.325.深度为5的二叉树至多有____个结点。A.16B.32C.31D.106.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。 A.2hB.2h-1C.2h+1D.h+17.对一个满二叉树，m个树叶，n个结点，深度为h，则____。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。A.不发生改变B.发生改变C.不能确定D.以上都不对9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。A.uwvtsB.vwutsC.wuvtsD.wutsv10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。A.正确B.错误11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.在一非空二叉树的中序遍历序列中，根结点的右边____。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点13.如图6.1所示二叉树的中序遍历序列是____。A.abcdgefB.dfebagcC.dbaefcgD.defbagcggcefdbaaagedbchf图6.2图6.114.一棵二叉树如图6.2所示，其中序遍历的序列为____。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgha15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。aA．a在b的右方 B．a在b的左方C．a是b的祖先 D．a是b的子孙16.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。A.acbedB.decabC.deabcD.cedba17.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构18.如图6.3所示的4棵二叉树，____不是完全二叉树。(A)(B)(C)(D)(A)(B)(C)(D)图6.319.如图6.4所示的4棵二叉树，____是平衡二叉树。（A）（A）（B）（C）（D）图8.84棵二叉树(A)(B)(C)(D)图6.420.在线索化二叉树中，t所指结点没有左子树的充要条件是____。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不对21.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。A.正确B.错误22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。A.正确B.错误23.具有五层结点的二叉平衡树至少有____个结点。A.10B.12C.15D.1724.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对25.树最适合用来表示____。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据k1k111kkkkkk21435671.有一棵树如图6.5所示，回答下面的问题：⑴这棵树的根结点是____；⑵这棵树的叶子结点是____；⑶结点k3的度是____；⑷这棵树的度是____；⑸这棵树的深度是____；⑹结点k3的子女是____；图6.5一棵树⑺结点k3的父结点是____；图6.5一棵树2.指出树和二叉树的三个主要差别____、____、____。3.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是____。4.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为____。12123456789101112131415161718192021eafdgcjlhb图6.6一棵二叉树的顺序存储数组t6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=____。7.一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。8.结点最少的树为____，结点最少的二叉树为____。iaiae d bchHf图6.7一棵二叉树gi10.由如图6.7所示的二叉树，回答以下问题：⑴其中序遍历序列为____；⑵其前序遍历序列为____；⑶其后序遍历序列为____；6.3简答题1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。gcgcefdba图6.8一棵树3.由如图6.7所示的二叉树，回答以下问题：（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树的后序线索二叉树；（3）画出该二叉树对应的森林。4.已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。5.以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。6.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?7.证明:一棵满k叉树上的叶子结点数n和非叶子结点数n之间满足以下关系:n=(k-1)n+16.4算法设计题1.编写按层次顺序（同一层自左至右）遍历二叉树的算法。2．试编写算法，对一棵二叉树,统计叶子的个数。3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。7.假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。8.试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。习题答案6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A11.D2.A13.B14.B15.B16.D17.C18.C19.B20.B21.B22.B23.B24.A25.C6.21.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k1eaEfjcdeaEfjcdlghb图6.9树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分；3.树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。4.如图6.9所示5.2k-1、2k-1、2k-2+16.n2+17.2i-12[log2n+1]-12[log2n+1]–18.只有一个结点的树；空的二叉树9.5；如图6.10所示a图6.10树形5种aaaaa图6.10树形5种aaaacccccbbbbbbEBEFAECEBEFAECDKGHIJ图6.12图6.11树形5种2.二叉树如图6.12所示。图6.11树形5种3.中序线索二叉树如图6.13（左）所示；后序线索二叉树如图6.13（右）所示；该二叉树转换后的的森林如图6.14所示。图6.13图6.13aa11dhjbkc图6.14对应的森林ief4.图6.8的树转化为一棵二叉树如下，图6.15：aabcedig图6.15一棵树的孩子兄弟表示5.画出构造Huffman树如图6.16所示，计算其带权路径长度为。62623725191813121096745图6.16Huffman树6.一棵含有N个结点的k叉树,可能达到的最大深度h=N-k+1，最小深度各为:logkN+1。习题7图7.1单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的_A___倍。A.1/2B.1C.2D.42．任何一个无向连通图的最小生成树B。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。A.1/2B.1C.2D.44．一个有n个顶点的无向图最多有___C_条边。A.nB.n(n-1)C.n(n-1)/2D.2n5．具有4个顶点的无向完全图有__A__条边。A.6B.12C.16D.206．具有6个顶点的无向图至少应有__B_条边才能确保是一个连通图。A.5B.6C.7D.87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要__A__条边。A.nB.n+1C.n-1D.n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是__D__。A.nB.(n-1)2C.n-1D.n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①__A_；所有邻接表中的接点总数是_②___B。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①_A_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b1212345324524^^^^^baecdf 图7.2一个有向图的邻接表存储结构图7.1一个无向图图7.2一个有向图的邻接表存储结构图7.1一个无向图11．已知一有向图的邻接表存储结构如图7.2所示。⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。A.求关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法15．关键路径是事件结点网络中。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路16．下面不正确的说法是。（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；（2）AOE网工程工期为关键活动上的权之和；（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A.（1） B.（2） C.（3） D.（1）、（2）17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是。A.逆拓朴有序的 B.拓朴有序的 C.无序的18．在图7.3所示的拓朴排列的结果序列为。A.125634 B.516234 C.123456 D.521634图7.3有向图图7.3有向图19．一个有n个顶点的无向连通图，它所包含的连通分量个数为。A.0 B.1 C.n D.n+120．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为。A.k1 B.k2 C.k1-k2 D.k1+k221．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为。A.k1 B.k2 C.k1-k2 D.k1+k27.2填空题（将正确的答案填在相应的空中）1．n个顶点的连通图至少____条边。2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于____。4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。v1v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3图7.4图G的邻接表5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。7．如果含n个顶点的图形成一个环，则它有棵生成树。8．一个非连通无向图，共有28条边，则该图至少有个顶点。9．遍历图的过程实质上是。BFS遍历图的时间复杂度为，DFS遍历图的时间复杂度为，两者不同之处在于，反映在数据结构上的差别是。10．一个图的表示法是唯一的，而表示法是不唯一的。11．有向图中的结点前驱后继关系的特征是。12．若无向图G的顶点度数最小值大于等于时，G至少有一条回路。13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是的。7.3综合题15156243（1）每个顶点的入/出度；（2）邻接距阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。图7。5一个有向图图7。5一个有向图2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树：（1）babadcef16111515151613141221图7.661261213212495201516106154372图7.73．试列出图7.8中全部的拓扑排序序列。1123456图7.8图7.84．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。5543223356abdfce图7.95．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。∝645∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝习题答案7.1 1.C 2.B 3.B 4.C 5.A 6.A 7.C8.D 9.AC 10.DB 11.CB 12.A 13.D 14.D 15.A 16.A 17.A 18.B 19.B 20.B 21.A7.21.n-1 2.1;03.14.v1,v2,v3,v6,v5,v4；v1,v2,v5,v4,v3,v65.求矩阵第i列非零元素之和6.将矩阵第i行全部置为零7.n8.99.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）；遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过的结点。10．邻接矩阵邻接表11．一个结点可能有若干个前驱，也可能有若干个后继12．2151562437.31.2.babadce1115131412f6612495106154372（2）3．152364152634156234561234516234512634512364W=3W=7W=3W=7W=9W=6W=543233abdfce5．(1)该AOE图为：(2)完成整个计划需要18天。(3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2，V5，V8，V9，）习题8查找8.1单项选择题1.顺序查找法适合于存储结构为____的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2.对线性表进行二分查找时，要求线性表必须____。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。A．O（n2）B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序树的时间性能____。A.相同B.不相同6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。A.1B.2C.4D.87.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是____。A.8B.3C.5D.98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。A.35/12B.37/12C.39/12D.43/129．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10．解决散列法中出现的冲突问题常采用的方法是。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址。A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于。A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D两种表都不适合13.散列表的平均查找长度。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关8.2填空题（将正确的答案填在相应的空中）1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。3.折半查找的存储结构仅限于____，且是____。4.假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。5.对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行次查找可确定成功；查找47时，需进行次查找成功；查找100时，需进行次查找才能确定不成功。7．二叉排序树的查找长度不仅与有关，也与二叉排序树的有关。8．一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过程即为对