计算机软件技术基础所有题目答案自学

11数据结构习题答案2第一节概论2第二节线性表5第三节栈和队列16第五节树19第七节查找25第八节排序29操作系统练习题参考答案3222数据结构习题答案第一节概论一、选择题1要求同一逻辑结构的所有数据元素具有相同的特性，这意味着。A数据元素具有同一的特点B不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等2数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算的学科。1A操作对象B计算方法C逻辑存储D数据映像2A结构B关系C运算D算法3数据结构被形式地定义为D，R，其中D是1的有限集合，R是D上2的有限集合。1A算法B数据元素C数据操作D逻辑结构2A操作B映像C存储D关系4在数据结构中，从逻辑上可以把数据结构分为。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构5线性表的顺序存储结构是一种的存储结构。A随机存取B顺序存取C索引存取DHASH存取6算法分析的目的是。A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性7计算机算法指的是1，它必须具备输入、输出和2等五个特征。1A计算方法B排序方法C解决某一问题的有限运算序列D调度方法2A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性，有穷性和稳定性D易读性、稳定性和安全性8线性表若采用链表存储结构，要求内存中可用存储单元的地址。A必须是连续的B部分必须是连续的C一定是不连续的D连续不连续都可以9在以下的叙述中，正确的是。A线性表的线性存储结构优于链式存储结构B二维数组是它的每个数据元素为一个线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出10根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是。A集合中任何两个结点之间都有逻辑关系但组织形式松散B线性结构中结点按逻辑关系依次排列形成一条“锁链”C树形结构具有分支、层次特性，其形态有点像自然界中的树D图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11以下说法正确的是。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D数据结构是带有结构的数据元素的集合33二、判断题1数据元素是数据的最小单位。2数据结构是带有结构的数据元素的集合。3数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。4数据项是数据的基本单位。5数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6数据的物理结构是数据在计算机中实际的存储形式。7算法和程序没有区别，所以在数据结构中二者是通用的。8顺序存储结构属于静态结构，链式存储结构属于动态结构。三、填空题1所谓数据的逻辑结构指的是数据元素之间的_逻辑关系_。2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_数据的逻辑结构、数据的存储结构、对数据施加的操作_。3数据的逻辑结构包括_集合结构_、_线性结构_、_树型结构_和_图状结构_四种类型。4在线性结构中，开始结点_没有_前驱结点，其余每个结点有且只有_一个_个前驱结点。5在树形结构中，根结点只有_一个_，其余每个结点有且只有_一个_前驱结点；叶结点没有_后继_结点，其余每个结点的后继结点可以有_任意个_6在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。7算法的五个重要特性是_可行性_、_确定性_、_有穷性_、_输入_、_输出_。8下列程序段的时间复杂度是_O（N）_。FORI1；I，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点答图略。开始结点K1、K2，终端结点K6、K7。7设有如图11所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。答数据逻辑结构为DK1，K2，K3，K8，R，其逻辑结构类型为树型结构。8分析下列程序的时间复杂度设N为正整数。1INTRECINTNIFN1RETURN1；ELSERETURNNRECN1；2X91；Y100；WHILEY0IFX10Y；3I1；J0；WHILEIJJJ；ELSEI4XN；Y0；WHILEXY1Y1Y；答1ON2O13ON4ON1/2559设N为正数。试确定下列各程序段中前面加记号的语句的频度1I1；K0；WHILEINEXTNULLCHEADNEXTHEADDHEADNULL10非空单循环链表HEAD的尾结点P满足。APNEXTNULLBPNULLCPNEXTHEADDPHEAD11在双循环链表的P结点之后插入S结点的操作是。APNEXTS；SPRIORP；PNEXTPRIORS；SNEXTPNEXT；BPNEXTS；PNEXTPRIORS；SPRIORPSNEXTPNEXT；CSPRIORP；SNEXTPNEXT；PNEXTS；PNEXTPRIORS；DSPRIORP；SNEXTPNEXT；PNEXTPRORS；PNEXTS；6612在一个单链表中，已知Q结点是P结点的前驱结点，若在Q和P之间插入结点S，则执行。ASNEXTPNEXT；PNEXTS；BPNEXTSNEXT；SNEXTP；CQNEXTSSNEXTP；DPNEXTSSNEXTQ；13在一个单链表中，若P结点不是最后结点。在P之后插入结点S，则执行。ASNEXTP；PNEXTSBSNEXTPNEXT；PNEXTS；CSNEXTPNEXT；PS；DPNEXTS；SNEXTP14若某线性表中最常用的操作是取第I个元素和找第I个元素的前驱元素，则采用存储方式最节省时间。A顺序表B单链表C双链表D单循环链表15设REAR是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为。APREAR；REARREARNEXT；FREEPBREARREARNEXT；FREEREAR；CREARREARNEXTNEXT；FREEREAR；DPREARNEXTNEXT；REARNEXTNEXTPNEXT；FREEP；16在一个单链表中，若删除P结点的后继结点，则执行。AQPNEXT；PNEXTQNEXT；FREEQ；BPPNEXT；PNEXTPNEXTNEXT；FREEP；CPNEXTPNEXT；FREEPNEXT；DPPNEXTNEXT；FREEPNEXT；17设指针P指向双链表的某一结点，则双链表结构的对称性可用式来刻画。APPRIORNEXTPNEXTNEXTBPPRIORPRIORPNEXTPRIORCPPRIORNEXTPNEXTPRIORDPNEXTNEXTPPRIORPRIOR18在循环链表中，将头指针改设为尾指针REAR后，其头结点和尾结点的存储位置分别是。AREAR和REARNEXTNEXTBREARNEXT和REARCREARNEXTNEXT和REARDREAR和REARNEXT19循环链表的主要优点是。A不再需要头指针了B已知某个结点的位置后，容易找到它的直接前驱C在进行插入、删除操作时，能更好地保证链表不断开D从表中任一结点出发都能扫描到整个链表20在线性表的下列存储结构中，读取元素花费时间最少的是。A单链表B双链表C循环链表D顺序表二、判断题1顺序存储的线性表可以随机存取。2顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。3线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。4在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。5在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。6在单链表中，可以从头结点开始查找任何一个元素。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。9在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。10顺序存储方式只能用于存储线性结构。三、填空题1为了便于讨论，有时将含NN0个结点的线性结构表示成A1，A2，AN，其中每个AI代表一个_结点_。A1称为_第一个_结点，AN称为_最后一个_结点，I称为AI在线性表中的_位置77_。对任意一对相邻结点AI、AI11INEXT；PNEXTQNEXT；FREEQ；_6非空的单循环链表HEAD的尾结点由指针P所指满足_PNEXTHEAD_。7REAR是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为_PREARNEXT；QPNEXT；PNEXTQNEXT；FREEQ；_。8对于一个具有N个结点的单链表，在P所指结点后插入一个结点的时间复杂度为_O1_，在给定值为X的结点后插入新结点的时间复杂度为_ON_。9单链表表示法的基本思想是用_指针_表示结点间的逻辑关系。10在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与_元素的位置_有关。11在一个长度为N的向量的第I1IN1个元素之前插入一个元素时，需向后移动_NI1_个元素。12在一个长度为N的向量中删除第I1IN个元素时，需向前移动_NI_个元素。13在双链表中，每个结点有两个指针域，一个指向_前驱_，另一个指向_后继_。14在一个带头结点的单循环链表中，P指向尾结点的直接前驱，则指向头结点的指针HEAD可用P表示为HEAD_PNEXTNEXT；_。15设HEAD指向单链表的表头，P指向单链表的表尾结点，则执行PNEXTHEAD后，该单链表构成_单循环链表_。16在单链表中，若P和S是两个指针，且满足PNEXT与S相同，则语句PNEXTSNEXT的作用是_删除_S指向的结点。17设R指向单循环链表的最后一个结点，要在最后一个结点之后插入S所指的结点，需执行的三条语句是_SNEXTRNEXT_；RNEXTS；RS；18在单链表中，指针P所指结点为最后一个结点的条件是_PNEXTNULL_。19在双循环链表中，若要在指P所指结点前插入S所指的结点，则需执行下列语句SNEXTP；SPRIORPPRIOR；_PPRIORNEXT_S；PPRIORS；20在单链表中，若要在P所指结点之前插入S所指的结点，可进行下列操作SNEXT_PNEXT_；PNEXTS；TEMPPDATA；PDATA_SDATA_；SDATA_TEMP_；四、应用题1描述以下三个概念的区别头指针，头结点，首元结点第一个元素结点。答首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。2何时选用顺序表，何时选用链表作为线性表的存储结构为宜答从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。3在顺序表中插入和删除一个结点需平均移动多少个结点具体的移动次数取决于哪两个因素88答平均移动表中大约一半的结点，插入操作平均移动N/2个结点，删除操作平均移动（N1）/2个结点。具体移动的次数取决于表长和插入、删除的结点的位置。4为什么在单循环链表中设置尾指针比设置头指针更好答单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O1时间内完成，同样在表头进行插入或删除操作也可在O1时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为ON。5双链表和单循环链表中，若仅知道指针P指向某个结点，不知道头指针，能否将结点P从相应的链表中删除若可以，其时间复杂度各为多少答能删除。双链表上删除P所指向的结点的时间复杂度为O1，单循环链表上删除P所指向的结点的时间复杂度为ON。6下列算法的功能是什么LINKLISTTESTLLINKLISTL/L是无头结点的单链表LISTNODEQ，P；IFLWHILEPNEXTPPNEXT；PNEXTQQNEXTNULL；RETURNL；答如果长度大于1，则将首元结点删除并插入到表尾。7如果有N个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构为什么答应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。8若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构为什么答应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O1。五、算法设计题1试用顺序表作为存储结构，实现将线性表A0，A1，A2，AN1就地逆置的操作，所谓“就地”是指辅助空间为O1。答1顺序表的就地逆置分析分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。VOIDSEQREVERSESEQLISTL顺序表的就地逆置FORI0；JL1ENGTH1；INEXT；LNEXTNULL；WHILEPNULLRP，PPNEXT；R指向当前待逆置的结点，P记下下个结点RNEXTLNEXT；LNEXTR；放到表头2设顺序表L是一个递增允许有相同的值有序表，试写一算法将X插入L中，并使L仍为一个有序表。99答分析先找到X的正确插入位置，然后将大于X的元素从后向前依次向下移动，最后将X插入到其位置上，同时顺序表长度增1。VOIDSEQLISTINSERTSEQLISTL，INTXX插入到递增有序的顺序表L中I0WHILEILDATAII；找正确的插入位置FORKLLENGTH1KI；K元素从后往前依次后移LDATAK1LDATAK；LDATAIX；X插入到正确位置L1ENGTH；3设单链表L是一个非递减有序表，试写一个算法将X插入其中后仍保持L的有序性。答分析此问题的关键是在链表中找到X的插入位置，因此需要两个指针一前一后地依次向后移动。VOIDLINKLISTINSERTLINKEDLISTL，INTXX插入有序链表L中QL；PQNEXT；WHILEPNULLWHILEPNULLK；IFPEXIT0；QP；KL；P指向LA表中第I个结点WHILEQK1；J1时WHILERI指示A中元素原来的位置，M为移动后的位置WHILEICDATAKKELSESAMEBDATAJ；找到了相同元素SAMEWHILEBDATAJSAMEJ；WHILECDATAKSAMEK；J、K后移到新的元素WHILEINEXT；WHILEPL20约瑟夫环问题任给正整数N、K，按下述方法可得排列1，2，N的一个置换将数字L，2，N环形排列，按顺时针方向从1开始计数；计满K时输出该位置上的数字并从环中删去该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，N10、K3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。答VOIDJS1INTAN，INTN，IHTK以数组为存储结构FORI0；INEXT；此时Q为头结点FP为Q的前驱WHILEN0FORJ2；JNEXT；PRINTF”D”，QDATA；N；PNEXTQNEXT删除Q1616QPNEXT；第三节栈和队列一、选择题1设有一顺序栈S，元素S1，S2，S3，S4，S5，S6依次入栈，如果6个元素出栈的顺序是S2，S3，S4，S6，S5，S1，则栈的容量至少应该是。A2B3C5D62若一个栈的输入序列是A、B、C，则通过入栈、出栈操作可能得到A、B、C的不同排列个数为。A4B5C6D73设有一顺序栈已经含有3个元素，如图31所示，元素A4正等待入栈。以下序列中不可能出现的出栈序列是。AA3，A1，A4，A2BA3，A2，A4，A1CA3，A4，A2，A1DA4，A3，A2，A14和顺序栈相比，链栈有一个比较明显的优势是。A通常不会出现栈满的情况B通常不会出现栈空的情况C插入操作更容易实现D删除操作更容易实现5若一个栈的输入序列是1，2，3，4，N，输出序列的第一个元素是N，则第I个输出元素是。A不确定BNICNI1DNI16以下说法正确的是。A因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况B因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况C对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢”D对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”7顺序队列的入队操作应为。ASQREARSQREAR1；SQDATASQREARXBSQDATASQREARX；SQREARSQREAR1；CSQREARSQREAR1MAXSIZE；SQDATASQREAR1XDSQDATASQREARX；SQREARXSQREARSQREAR1MAXSLZE；8循环队列的入队操作应为。ASQREARSQREAR1；SQDATASQREARXBSQDATASQREARX；SQREARSQREARL；CSQREARSQREAR1MAXSIZE；SQDATASQREARX；DSQDATASQREARX；SQREARSQREAR1MAXSIZE；9顺序队列的出队操作为。ASQFRONTSQFRONT1MAXSIZE；BSQFRONTSQFRONT1；CSQREARSQREAR1MAXSIZE；DSQREARSQREAR110循环队列的出队操作为。ASQFRONTSQFRONT1MAXSIZE；BSQFRONTSQFRONT1；CSQREARSQREAR1MAXSIZE；DSQREARSQREARL；171711循环队列的队满条件为。ASQREAR1MAXSIZESQFRONT1MAXSIZE；BSQREAR1MAXSIZESQFRONT1；CSQREAR1MAXSIZESQFRONT；DSQREARSQFRONT；12循环队列的队空条件为。ASQREAR1MAXSIZESQFRONT1MAXSIZE；BSQREAR1MAXSIZESQFRONT1；CSQREAR1MAXSIZESQFRONT；DSQREARSQFRONT；13如果以链表作为栈的存储结构，则出栈操作时。A必须判别栈是否满B判别栈元素的类型C必须判别栈是否空D对栈不做任何判别14，向一个栈顶指针为TOP的链栈中插入一个S所指结点时，其操作步骤为。ATOPNEXTS；BSNEXTTOPNEXT；TOPNEXTS；CSNEXTTOP；TOPS；DSNEXTTOP；TOPTOPNEXT；15从栈顶指针为TOP的链栈中删除一个结点，并将被删结点的值保存到X中，其操作步骤为。AXTOPDATA；TOPTOPNEXT；BTOPTOPNEXT；XTOPDATA；CXTOP；TOPTOPNEXT；DXTOPDATA；16在一个链队中，苕F、R分别为队头、队尾指针，则插入S所指结点的操作为。AFNEXTS；FS；BRNEXTS；RS；CSNEXTR；RS；DSNEXTF；FS；17一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是。AE，D，C，B，ABD，E，C，B，ACD，C，E，A，BDA，B，C，D，E18一个队列的入队序列是1，2，3，4，则队列的可能的输出序列是。A4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，119设计一个判别表达式中左，右括号是否配对出现的算法，采用数据结构最佳。A线性表的顺序存储结构B栈C队列D线性表的链式存储结构二、判断题1在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。2与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。3若一个栈的输入序列为1，2，3，N，其输出序列的第一个元素为N，则其输出序列的每个元素AI一定满足AII1I1，2，N。4在链队中，即使不设置尾指针也能进行入队操作。5在对链队带头指针做出队操作时，不会改变FRONT指针的值。6循环队列中元素个数为REARFRONT。7一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,28一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。9若以链表作为栈的存储结构，则入栈需要判断栈是否满10若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、填空题1向一个栈顶指针为TOP的链栈中插入一个S所指的结点时，其进行的操作是_SNEXTTOP；TOPS；_。2从栈顶指针为TOP的链栈中删除一个结点，并将结点保存在X中，进行的操作是_XTOPDATA；TOPTOPNEXT；_。3在具有N个单元的循环队列中，队满时共有_N1_个元素。4假设以S和X分别表示入栈和出栈操作，则对输入序列A，B，C，D，E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_B，C，E，D，A_。18185设有数组AM作为循环队列的存储空间，FRONT为队头指针，REAR为队尾指针，则元素X执行入队操作的语句是_REAR（REAR1）（M1）；AREARX_。6在一个链队中，如果F、R分别为队头、队尾指针，则插入S所指结点的操作是_RNEXTSRS_。7栈的逻辑特点是_后进先出_，队列的逻辑特点是_先进先出_，二者的共同特点是_操作受限_。8_栈_可以作为实现递归函数调用的一种数据结构。9在队列中，新插入的结点只能添加到_队尾_。10链队在一定范围内不会出现_队满_的情况。当LQFRONTLQREAR时，队中无元素，此时_队空_。11设一个链栈的栈顶指针为LS，栈中结点的格式为DATANEXT，栈空的条件是_LSNULL_；如果栈不为空，则出栈操作为PLS_LSLSNEXT_；FREEP。12对带有头结点的链队LQ，判定队列中只有一个数据元素的条件是_LQFRONTNEXTLQREAR_。13设有一个空栈，现在输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH后，栈顶指针所指元素是_4_。14设用一维数组ALN来表示一个栈，令AN为栈底。用整型变量T来指示当前栈顶的位置，AT为栈顶元素。往栈中压入一个新元素时，变量T的值_加1_，从栈中弹出一个元素时，变量T的值_减1_。设空栈时，输入序列A，B，C经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素是_C_。四、应用题1试证明若借助栈由输入序列1，2，3，N得到输出序列P1，P2，PN它是输入序列的一个排列，则在输出序列中不可能出现这样的情形存在I0层上至多有_2I1_个结点。4深度为KK0的二叉树至多有_2K1_个结点。5对任何二叉树，若度为2的节点数为N2，则叶子数N0_N21_。6满二叉树上各层的节点数已达到了二叉树可以容纳的_最大值_。满二叉树也是_完全_二叉树，但反之不然。7具有N个结点的完全二叉树的深度为_LOG2N1_。8在顺序存储的二叉树中，编号为I和J的两个结点处在同一层的条件是_LOG2ILOG2J_。9如果将一棵有N个结点的完全二叉树按层编号，则对任一编号为I0L，则X的双亲PARENTX的编号为_I/2_。2若2IN，则结点X无_左孩子_且无_右孩子_；否则，X的左孩子LCHILDX的编号为_2I_。3若2I1N，则结点X无_右孩子_；否则，X的右孩子RCHILDX的编号为_2I1_。10二叉树通常有_顺序_存储结构和_链式_存储结构两类存储结构。11每个二叉链表还必须有一个指向_根_结点的指针，该指针具有标识二叉链表的作用。12对二叉链表的访问只能从_根_指针开始。13具有N个结点的二叉树中，一共有_2N_个指针域，其中只有_N1_个用来指向结点的左右孩子，其余的_N1_个指针域为NULL。14已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为_99_。15二叉树有不同的链式存储结构，其中最常用的是_二叉链表_与_三叉链表_。16可通过在非完全二叉树的“残缺”位置上增设_空指针_将其转化为完全二叉树。232317具有100个结点的完全二叉树的深度是_7_。18深度为90的满二叉树上，第10层有_512_个结点。19在_前序_遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。20具有N个结点的完全二叉树，若按层次从上到下、从左到右对其编号根结点为1号，则编号最大的分支结点序号是_N/2_，编号最小的分支结点序号是_1_，编号最大的叶结点序号是_N_，编号最小的叶结点序号是_N/21_。21若一棵二叉树的叶子数为N，则该二叉树中左、右子树皆非空的结点个数为_N1_。22任意一棵具有N个结点的二叉树，若它有M个叶子，则该二叉树上度数为1的结点为_N2M1_个。23设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有_59_个结点。24现有按中序遍历二叉树的结果为ABC，有_5_种不同形态的二叉树可以得到这一遍历结果。25以数据集4，5，6，7，10为叶结点的权值所构造的哈夫曼树的带权路径长度为_53_26已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_12_个叶结点。27设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶结点的个数是_8_。28如果结点A有三个兄弟，而B是A的双亲，则B的度是_4_。29一棵树的形状如图65所示，它的根结点是_A_，叶结点是_E,J,K,L,O,P,Q,R,N,I_，结点H的度是_3_，这棵树的度是_4_，这棵树的深度是_5_，结点F的儿子结点是_J,K_，结点G的父结点是_C_。30设结点X有左孩子结点Y、右孩子结点Z，用三种基本遍历方法得到的遍历序列中X_不一定_是Y的前驱，X_不一定_是Z的后继，Y_一定_是Z的前驱填“一定”，“不”、“不一定”。31在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_前驱_，且存在一条从根到该结点的_惟一路径_。32含有2N个结点的二叉树高度至少是_N1_，至多是_2N_仅含根结点的二叉树高度为1。33设高度为H的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_2H1_，至多为_2H1_。四、应用题3任意一个有NN0个结点的二叉树，已知它有M个叶结点，试证明非叶结点有M1个度为2，其余度为1。答设度为1的结点数N1,设度为2的结点数N2,分支数B,则有MN1N2N,B1N,B1N12N2,即MN1N2N,N12N21N,解之可得N2M15分别写出图67所示二叉树的前序、中序和后序序列。2424答前序ABCDEF、中序CBEFDA和后序CFEDBA6已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。答前序遍历序列ABCDEFGH9分别画出图610所示二叉树对应的森林，并写出森林的前序和后序遍历序列。答前序ABDGCEFHIJK，后序DGBAECIHJKF。11将代数式Y3XAA/X2描述成表达式树，并写出前缀式和后缀式。答前缀式3XA/AXX，后缀式3XAAXX/。13试证明任一棵高度为H1的二叉树，其内部结点除根、叶子之外的结点的数目小于2H11，而叶结点数目小于或等于2H1。答高度为H的满二叉树包含的结点个数最多,最下层是叶子,除根外,其余是内部结点,不包含叶子的子树高度是H1,该子树的最多结点数是2H11除根外,内部结点的数目应小于2H11而整个树所含的最多结点数是2H1,所以,叶子数最多为2H12H112H1个14编码00，01，10，11、0，1，00，11，、0，10，110，111哪一组不是前缀码答编码00，01，10，11、0，10，110，111是前缀码,0，1，00，11不是前缀码15一棵度为K的树有N1个度为1的结点，N2个度为2的结点，NK个度为K的结点，问该树中有多少个叶结点答NN0N1NK1N12N2KNKN01N22N3K1NK16一棵含有N个结点的K叉树，可能达到的最大深度和最小深度各是多少答最大深度N，最小深度LOGKNK11五、算法设计题1以二叉链表作为存储结构，试编写求二叉树深度的算法。答INTBDEPTHBTREETIFTNULLRETURN0ELSELBDEPHTTLCHILDRBDEPHTTRCHILDRETURNLRLR1；2525第七节查找一、选择题1顺序查找法适合于存储结构的查找表。A压缩B散列C索引D顺序或链式2对采用折半查找法进行查找操作的查找表，要求按方式进行存储。A顺序存储B链式存储C顺序存储且结点按关键字有序D链式存储且结点按关键字有序3设顺序表的长为N，用顺序查找法,则其每个元素的平均查找长度是。AN12BN12CN2DN4设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用折半查找法查找键值为35的结点时，经次比较后查找成功。A2B3C4D65长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是。A2410B2411C3910D39116在表长为N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为。ANLB1CNDN17在采用链地址法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值。A一定都是同义词B不一定都是同义词C都相同D一定都不是同义词8用顺序查找法对具有N个结点的线性表查找的时间复杂度量级为。AON2BONLOG2NCONDOLOG2N9用折半查找法对具有N个结点的线性表查找的时间复杂度量级为。AON2BONLOG2NCONDOLOG2N10在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值。A一定都是同义词B不一定都是同义词C都相同D一定都不是同义词11设哈希函数为HKEYKEY7，一组关键字为37，21，9，20，30，19，46，哈希表T的地址空间为06，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为。A01234562120379463019B01234562146379301920C01234562119937304620D0123456203730214619912设有一个用线性探测法解决冲突得到的哈希表0123456789101325801617614哈希函数为HKEYKEY11，若要查找元素14，探测的次数是。A3B6C7D913在哈希函数HKEYKEYM中，一般来讲，M应取。A奇数B偶数C素数D充分大的数14分块查找的时间性能。2626A低于折半查找B高于顺序查找而低于折半查找C高于顺序查找D低于顺序查找而高于折半查找15以下说法错误的是。A哈希法存储的基本思想是由关键字的值决定数据的存储地址B哈希表的结点中只包含数据元素自身的信息，不包含任何指针C装填因子是哈希法的一个重要参数，它反映哈希表的装填程度D哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法16以下说法正确的是。A前序遍历二叉排序树的结点就可以得到排好序的结点序列B任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间C对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的D采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要17已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是。A将该元素所在的存储单元清空B将该元素用一个特殊的符号代替C将与该元素有相同散列地址的后继元素顺次前移一个位置D用与该元素有相同散列地址的最后插入表中的元素替代18设哈希表长为M14，哈希函数HKEYKEY11。表中已有4个结点ADDR154，ADDR385，ADDR616，ADDR847，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是。A3B，8C9D1019有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为。A3212B3512C3712D391220采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应个结点最佳。A25B10C6D62521如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。A分块B顺序C折半D散列22有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行次探测。AK1BKCKLDKK1223在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与查找方法量级相当。A分块B顺序C折半D散列24在具有N个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为。AONBO1COLOG2NDON225哈希表的平均查找长度。A与处理冲突的方法有关而与表的长度无关B与处理冲突的方法无关而与表的长度有关C与处理冲突的方法有关且与表的长度有关D与处理冲突的方法无关且与表的长度无关26若对长度为M的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为D，则第3次计算的哈希地址为。AD1MBD1MCD4MDD4M27以下说法正确的是。A数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况，并且键值的位数比散列地址的位数多B除余法要求事先知道全部键值C平方取中法需要事先掌握键值的全部分布情况D随机数法适用于键值不相等的场合28有数据49,32,40,6,45,12,56，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列输入序列。2727A45，12，49，6，40，56，32B40，12，6，32，49，45，56C6，12，32，40，45，49，56D32，12，6，40，45，56，4929在一棵深度为H的具有N个元素的二叉排序树中，查找所有元素的最长查找长度为。ANBLOG2NCH12DH二、判断题1分块查找方法的平均查找长度低于顺序查找，高于折半查找。2若采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。3前序遍历二叉排序树的结点就可以得到排好序的结点序列。4在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。5虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。6对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。7在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。8在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。三、填空题1任何结点之间都不存在_逻辑_关系，这是集合这种逻辑结构的基本特点。2在开散列表上查找键值等于K的结点，首先必须计算该键值的_散列地址_，然后再通过指针查找该结点。3在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域块内最大_元素_值和块_首_位置。4索引顺序表上的查找分两个阶段一、_确定元素所在的块_；二、_在块内查找元素_。该查找方法称为_分块_查找。5二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值_大_于其左孩子及其子孙的键值且_小_于其右孩子及其子孙的键值。6在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值_大_的结点，只需通过结点X的右指针到它的右子树中去找。7中序遍历一棵二叉排序树所得到的结点访问序列是键值的_递增_序列。8二叉排序树上的查找长度不仅与_元素个数_有关，也与二叉排序树的_输入序列_有关。9二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为_顺序_查找，平均查找长度上升为_（N1）/2_。10_散列_查找法的平均查找长度与元素个数N无关。11在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为_1_，比较两次查找成功的结点数为_2_，比较五次查找成功的结点数为_5_。总的平均查找长度为_37/10_。12当所有结点的值都相等时，用这些结点构造的二叉排序树上只有_一个结点_。13折半查找方法仅适用于这样的表表中的记录必须_有序_，其存储结构必须是_顺序存储_。15设线性表LA1，A2，ANN2，表中元素按值的递增顺序排列。对一个给定的值K，分别用顺序查找法和折半查找法查找与K相等的元素，比较次数分别为S和B，若查找不成功，则S和B的数量关系是_SB_。16某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为_10001/2_，最大比较次数为_10000_。现把10000个元素按排列顺序划分成若2828干组，使得每一组中有G个元素最后一组可能小于G。查找时，先从第一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的G是_100_，此时的平均比较次数是_101_。17长度为225的表，采用分块查找法，每块的最佳长度是_15_，应分_15_块，若每块的长度为10，则平均查找长度为_35/2_。18已知有序表为13,17,20,32,48,54,65,79,86,91,97，当采用折半查找法查找86时需进行_2_次比较可确定查找成功，查找48时需进行_4_次比较可确定查找成功，查找100时需进行_4_次比较才能确定查找不成功。四、应用题1已知有长度为9的表16,29,32,5,89,41,14,65,34，它们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情况下查找成功的平均查找长度不超过3。1该哈希表的长度M应设计成多大2设计相应的哈希函数。3将数据填入到哈希表中。4计算查找成功时的平均查找长度。答1该哈希表的长度M122HKEYKEY11301234567891011893414165294132651211211124ASL121121112/912/94/32假定有N个关键字，它们具有相同的哈希函数值，用线性探测法把这N个关键字存入到哈希表中要做多少次探测答N个关键字都是同义词，因此用线性探测法解决冲突都会发生冲突，所以探测次数为12NNN1/23地址空间为014的哈希表中，对关键字序列JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC构造哈希函数HKEYI2，其中I为关键字中第一个字母在字母表中的序号。用线性探测法和链地址法分别求出这两个哈希表在等概率情况下查找成功和查找不成功的平均查找长度。答1用线性探测法01234567891011121314APRAUGDECFEBJANMARMAYJUNJULSEPOCTNOV121111245256查找成功ASL121111245256/1231/12查找不成功ASL543219876543211/1561/152链地址法图略。查找成功ASL172431/1218/123/2查找不成功ASL312214331211111/1527/159/54有一个400项的表，欲采用索引顺序查找方法进行查找，问1分成多少块最为理想2每块的理想长度是多少3平均查找长度是多少答1分成20最为理想2每块的理想长度是203平均查找长度是（201）/2（201）/2215设有一组关键字19，05，21，24，45，20，68，27，70，11，10，用哈希函数HKEYKEY13，采用线性探测再散列方法解决冲突，试在014的散列地址空间中对该关键字序列构造哈希函数，并求查找成功和查找不成功时的平均查找长度。答012345678910111213142768051945212070241110111121361242929查找成功ASL（11112136124）/1123/11查找不成功ASL（1212110987654321）/1562/159设二叉排序树中的关键字由1100内