数据结构考试题库及答案2018.doc

数据结构期末考试题库及答案2018目 录第1章 绪论1第2章 线性表5第3章 栈和队列13第4章 串、数组和广义表26第5章 树和二叉树33第6章 图43第7章 查找54第8章 排序6529第1章 绪论1选择题（1）数据结构是指（1. A ）。A.数据元素的组织形式B.数据类型C.数据存储结构 D.数据定义（2）计算机内部数据处理的基本单位是（10. B ）。A.数据 B.数据元素C.数据项D.数据库（3）数据结构中，与所使用的计算机无关的是数据的 C 结构. A) 存储 B) 物理 C) 逻辑 D) 物理和存储【解析】解析 数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。（4）算法分析的目的是_C_ A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （5）计算机算法必须具备输入、输出和 B 等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 （6）在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构答案：C（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。A存储结构 B存储实现C逻辑结构 D运算实现答案：C（8）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等答案：B（9）以下说法正确的是（ ）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。（10）算法的时间复杂度取决于（ ）。A问题的规模B待处理数据的初态C计算机的配置DA和B答案：D解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。（11）以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队列 D栈答案：A2填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。09、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。10、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。11、一个算法的效率可分为(时间)效率和(空间)效率。12、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。13、一个数据结构在计算机中的(映射)称为存储结构。14、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。3判断题 01、数据元素是数据的最小单位。 02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。 03、算法的优劣与算法描述语言无关，但与所用计算机有关。 04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 05、算法可以用不同的语言描述，则算法实际上就是程序了。 06、程序一定是算法。 07、数据的物理结构是指数据在计算机内的实际存储形式。 08、数据结构的抽象操作的定义与具体实现有关。 09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。 10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。 12、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。第2章 线性表1选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A110 B108 C100 D120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。A访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。A8 B63.5 C63 D7答案：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个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。An B2n-1 C2n Dn-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。（9）在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（ ）个元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 线性表L=(a1，a2,an)，下列说法正确的是（ ）。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。答案：D(11) 创建一个包括n个结点的有序单链表的时间复杂度是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)答案：C解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。(12) 以下说法错误的是（ ）。A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构答案：D解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; 答案：D (14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;答案：A(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C2填空题1. 线性表是一种典型的_结构。1线性 2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移_个元素。2n-i+1 3. 顺序表中逻辑上相邻的元素的物理位置_。3相邻 4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。4前移，前，后5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。5物理存储位置，链域的指针值 6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。6前趋，后继7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。7顺序，链接 8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。8一定，不一定9. 在单链表中设置头结点的作用是_。9使空表和非空表统一；算法处理一致3判断题（ ）1. 链表的每个结点中都恰好包含一个指针。 （ ）2. 链表的物理存储结构具有同链表一样的顺序。 （ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 （ ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）7. 线性表在物理存储空间中也一定是连续的。 （ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ ）9. 顺序存储方式只能用于存储线性结构。 （ ）10. 线性表的逻辑顺序与存储顺序总是一致的。 第3章 栈和队列1选择题（1）设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C）。 AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A （2）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。（3）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）。Ai Bn-i Cn-i+1 D不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，n，而输出序列的第一个元素为n，说明1，2，3，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，pi=n-i+1。（4）栈中元素的进出原则是（ B ） 先进先出 后进先出 栈空则进 栈满则出 （5）在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C ）。 Atop不变 Btop=0 Ctop- Dtop+（6） 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（B）。 Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; （7） 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（D）。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front（8）在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（C）。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front（9）在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（A）。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next（10）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素个数的公式为（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。（11）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；答案：A解释：x=top-data将结点的值保存到x中，top=top-link栈顶指针指向栈顶下一结点，即摘除栈顶结点。（12）栈在（ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有答案：D解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。（13）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A队列 B栈 C 线性表 D有序表答案：A解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。（14）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2 B3 C4 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。（15）若一个栈以向量V1.n存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;DVtop=x; top-;答案：C解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V1.n中，所以进栈时top指针先下移变为n，之后将元素x存储在Vn。（16）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈答案：D解释：利用栈的后进先出原则。（17）用链接方式存储的队列，在进行删除运算时（）。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（18）循环队列存储在数组A0.m中，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解释：数组A0.m中共含有m+1个元素，故在求模运算时应除以m+1。（19）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解释：最大容量为n的循环队列，队满条件是(rear+1)%n=front，队空条件是rear=front。（20）栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（21）一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分答案：B2填空题1. 线性表、栈和队列都是（线性）结构，可以在线性表的（任何）位置插入和删除元素；对于栈只能在（栈顶）位置插入和删除元素，不允许插入和删除运算的一端称为（栈底）。；对于队列只能在（队尾）位置插入元素和在（队头）位置删除元素。 2. 对于一个栈作进栈运算时，应先判别栈是否为（栈满），作退栈运算时，应先判别栈是否为（栈空），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为（m）。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两个栈的栈顶在栈空间的某一位置相遇）时才产生上溢。3. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是（2、3）。4.（队列）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 5.在具有 n 个单元的循环队列中，队满时共有（ n - 1） 个元素。 解析：因为如果放置n个元素，首尾指针指向同一位置，与空队列无法区别，所以循环队列中认为当尾指针的后一个指针为首指针时，判定队列为满队列，即只能保存n-1个元素6.带表头结点的空循环双向链表的长度等于（ 0）。 3判断题（ ）1. 在表结构中最常用的是线性表，栈和队列不太常用。 （ ）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ ）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ）4. 栈和链表是两种不同的数据结构。 （ ）5. 栈和队列是一种非线性数据结构。 （ ）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ ）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）9. 一个栈的输入序列是 12345，则栈的输出序列不可能是 12345。第4章 串、数组和广义表1选择题（1）串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 答案：B（2）串下面关于串的的叙述中，（ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 （3）设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作：（ B ） 连接 模式匹配 求子串 求串长 （4）一个子串在包含它的主串中的位置是指（ D）。A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置（5） 下面的说法中，只有（C）是正确的。A.字符串的长度是指串中包含的字母的个数B.字符串的长度是指串中包含的不同字符的个数C.若T包含在S中，则T一定是S的一个子串D.一个字符串不能说是其自身的一个子串（6）两个字符串相等的条件是（D ）。A.两串的长度相等 B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同（7）若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“BeijingNanjing”，SUBSTR（S，4，5）=（B）。A. “ijing”B. “jing” C. “ingNa”D. “ingN”（8） 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（D ）。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”（9）在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（C ）。A.i0 B. in C.1in D.1in+1（10）串“ababaaababaa”的next数组为（ ）。A012345678999 B012121111212 C011234223456 D0123012322345答案：C（11）串“ababaabab”的nextval为（ ）。A010104101 B010102101 C010100011 D010101011 答案：A（12）串的长度是指（ ）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。（13）假设以行序为主序存储二维数组A=array1.100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（ ）。A808 B818 C1010 D1020答案：B解释：以行序为主，则LOC5,5=（5-1）*100+（5-1）*2+10=818。（14）设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（ ）。ABA+141 BBA+180 CBA+222 DBA+225答案：B解释：以列序为主，则LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（15）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B32 C33 D40答案：C（16）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（17）二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解释：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A8,5的起始地址为：M+（8-0）*10+（5-1）*1=M+84；若数组按列先存储，易计算出元素A3,10的起始地址为：M+（10-1）*9+（3-0）*1=M+84。故选B。（18）设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai,j在一维数组B中的下标为（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1答案：A解释：特殊值法。取i=j=1，易知A1,1的的下标为1，四个选项中仅有A选项能确定的值为1，故选A。（19）数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A55 B45 C36 D16答案：B解释：共有5*3*3=45个元素。（20）广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)的值为（ ）。A(g) B(d) Cc Dd答案：D解释：Tail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=( (c,d),(e,(f,g)； Head(Tail(Tail(A)= (c,d)；Tail(Head(Tail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（21）广义表(a,b,c,d)的表头是（ ），表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)答案：C、B解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，(a,b,c,d)的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，(a,b,c,d)的表尾为空表( )。（22）设广义表L=(a,b,c)，则L的长度和深度分别为（ ）。A1和1 B1和3 C1和2 D2和3 答案：C解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1，深度为2。2填空题 （1） 串是指（含n个字符的有限序列 （n0）。（2）空串是指（不含任何字符的串），空格串是指（仅含空格字符的字符串）。（3）一维数组的逻辑结构是（线性结构），存储结构是（顺序结构）；对于二维或多维数组，分为（以行为主序）和（以列为主序）两种不同的存储方式。（4）对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地址为（in+j个元素位置）。（5）一个广义表为(a,(a,b),d,e,(i,j),k)，则该广义表的长度为（ 5），深度为（3）。3判断题1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ 1. ）2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（2.）3. 以行为主序或以列为主序对于多维数组的存储没有影响。（3.）4. 对于不同的特殊矩阵应该采用不同的存储方式。（4. ）5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（5.）6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（6.）7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（7.）8. 距阵中的数据元素可以是不同的数据类型。（8.）9. 矩阵中的行列数往往是不相等的。（9.）10. 广义表的表头可以是广义表，也可以是单个元素。（10.）11. 广义表的表尾一定是一个广义表。（11.）12. 广义表的元素可以是子表，也可以是单元素。（12.）13. 广义表不能递归定义。（13. ）14. 广义表实际上是基本线性表的推广。（14.）15. 广义表的组成元素可以是不同形式的元素。（ 15. ）第5章 树和二叉树1选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A唯一的 有多种C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。（2）由3个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 答案：D解释：五种情况如下： （3）在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ C）个。A. 4B. 5C. 6D. 7（4）假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B ）个。A. 15B. 16C. 17D. 47（5） 在一棵二叉树上第4层的结点数最多为（ D）。A. 2B. 4 C. 6D. 8（6）利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历答案：C解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。A前序 B中序 C后序 D按层次答案：C解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。（9）在下列存储形式中，（ ）不是树的存储形式？A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法答案：D解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树答案：C解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。（11）设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。A99B100C101D102答案：B解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2*n0-1，得到n0=100。（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。AX的双亲 BX的右子树中最左的结点 CX的左子树中最右结点 DX的左子树中最右叶结点答案：C（13）引入二叉线索树的目的是（ ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一答案：A（14）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。An1BnCn + 1Dn + 2答案：C（15）n（n2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。A该树一定是一棵完全二叉树B树中一定没有度为1的结点C树中两个权值最小的结点一定是兄弟结点D树中任一非叶结点的权值一定不小于下一层任一结点的权值答案：A解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。2填空题（1）设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有（n+1）个。（2）对于一个有n个结点的二叉树，当它为一棵（完全）二叉树时具有最小高度，即为（），当它为一棵单支树具有（最大）高度，即为（n）。（3）对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（2n）个，其中（n-1）个用于链接孩子结点，（n+1）个空闲着。（4）在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=（n2+1）。（5）一棵含有n个结