数据的逻辑结构与数据元素本身的内容和形式无关计算机数据挖掘与模式识别_高等教育-大学课件.pdf

《数据的逻辑结构与数据元素本身的内容和形式无关计算机数据挖掘与模式识别_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《数据的逻辑结构与数据元素本身的内容和形式无关计算机数据挖掘与模式识别_高等教育-大学课件.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、A.存储结构和逻辑结构 B 存储和抽象 (2)下列与数据元素有关的叙述中错误的是(A.数据元素是有独立含义的数据最小单位 C.数据元素可以称做结点 D(3)数据结构中，在逻辑上可以把数据结构分成：A.动态结构和静态结构 B C.联系和抽象 D.联系与逻辑)。B.数据元素是描述数据的基本单位(4)数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为()。.顺序存储结构.多对多关系 D.链式存储结 D.B 或 C 实现算法所用的辅助空间的多少称为算法 C.硬件效率 D.软件效率 C.删除运算方便.数据的存储结构 D.包括以上三个方面 第一章 绪论 一、判断题(1)数据的逻辑结构与

2、数据元素本身的内容和形式无关。(2)数据元素是数据的最小单位。(3)算法是对解题方法和步骤的描述。(4)程序和算法原则上没有区别，在讨论数据结构时可以通用。(5)从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。(6)数据的存储结构是数据的逻辑结构的存储映像。二、选择题(l)数据结构通常是研究数据的()及它们之间的相互联系。A.存储结构 B 逻辑结构 C 构(5)非线性结构的数据元素之间存在()。A.对一关系 B.一对多关系 C(6)在非线性结构中，每个结点()。A.无直接前驱 B.只有一个直接前驱和个数不受限制的直接后继 C.只有一个直接前驱和直接后继 D.有个数不受限制的直接前驱和

3、直接后继(7)除了考虑存储数据结构本身所占用的空间外，的()。A.时间效率 B.空间效率(8)以下属于顺序存储结构优点的是()。A.存储密度大 B.插入运算方便 D.可方便地用于各种逻辑结构的存储表示(9)数据结构研究的内容是()。A.数据的逻辑结构 B C.建立在相应逻辑结构和存储结构上的算法(10)链式存储的存储结构所占存储空间()。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B.只有一部分，存放结点值 C.只有一部分，存储表示结点间关系的指针 D.分两部分，一部分存放结点值，另一部分存放结点所占单元数(11)一个正确的算法应该具有 5 个特性，除输入、输出特性外，另

4、外 3 个特性是()。A.确定性、可行性、有穷性 B.易读性、确定性、有效性 C.有穷性、稳定性、确定性 D.可行性、易读性、有穷性(12)以下关于数据的逻辑结构的叙述中正确的是()。A.数据的逻辑结构是数据间关系的描述 B.数据的逻辑结构反映了数据在计算机中的存储方式客观题 (13)c.数据的逻辑结构分为顺序结构和链式结构 D.数据的逻辑结构分为静态结构和动态结构 设问题的规模为n，分析以下程序段：k=n;/*n I*/m=0;while(k =(m+I)*(m-I)m+;以上程序段的算法时间复杂度是()(14)A.O(n)B.O(1)C.O(设问题的规模为n，分析以下程序段:a=10;b=

5、100;while(b 0)a+;b -;以上程序段的算法时间复杂度是(、n)D.0(n(15)(16)A.O(n)B.O(1)C.O(设语句s=s+i的时间是单位时间，则语句：s=0;for(i=l;i=n;i+)s=s+i;的时间复杂度为：(A.O(l)B.O(n)算法分析的主要任务是(17)C.O(n A.探讨算法的正确性和可读性 B C.为给定问题寻找一种性能良好的解决方案 以下叙述中正确的是(A顺序存储方式只能用于存储线性结构 n)2)D.O(n D.O(n 3)探讨数据组织方式的合理性 研究数据之间的逻辑关系 B.链式存储方式只能用于存储线性结构，探讨数据组织方式的合理性，研究数据

6、之间的 逻辑关系 C.顺序存储和链式存储都可以用于线性和非线性结构 D.以上三种都不对(18)以下叙述中正确的是(A.数据元素是数据处理的最小单位 B C.关键字是能够惟一标识一个数据元素的数据项 数据项是数据处理的基本单位 数据结构和数据类型的概念是等 价的 第二章 线性表(1)(2)(3)(4)(5)判断题 线性表的链式存储结构优于顺序存储。链表的每个结点都恰好包含一个指针域。线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属 于同一数 据对象。在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。在单链表中，任何两个元素的存储位置之间都有固定

7、的联系，所以可以从头结点开始查找 任何一个 兀素。对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除

8、了考虑存储数据结构本身所占用的空间外的时间效率空间效率以A.B.C.D.现要将指针 q.单链表)。.等于1(10)己知一个顺序存储的线性表，设每个结点需占 A.链表(9)单链表的存.双向循环链表.双向链表.小于1 D m个存储单元，若第一个结点的地址 不能确定 al,D.al+(i+1)*m 0(1)的操作是(个结点的直接前驱(2 i n-1).所有元素 线性表采用顺序存储必须占用一片连续的存储单元 线性表采用顺序存储便于进行插入和删除操作 线性表采用链式存储不必占用一片连续的存储单元 线性表采用链式存储便于进行插入和删除操作 已知单链表的每个结点包括一个指针域 next，它指向该结点的后继结

9、点。指向的新结点插入到指针 p指向的结点之后，下面的操作序列中正确的是(A.q=p 一n ext;p 一n ext=q 一n ext;B.p 一next=q 一next;q=p 一next;C.q 一next=p 一next;p 一next=q;D.p 一next=q;q 一next=p 一next;(8)设a I,a2,a 3为三个结点；p,10,20 代表地址，则如下的链表存储结构称为 10 则第i个结点的地址为(A.al+(i-1)*m B.al+i*m C.al-i*m(11)在n个结点的顺序表中，算法的时间复杂度是 A.访问第i个结点(1 i n)和求第i B.在第i个结点之后插入一

10、个新结点(1 C.删除第i个结点(1 w i next D.0(log 2n)(18)=P C.P-next=NULL D.P-next L(19)指针P所指的元素是双循环链表 A.P=L B.P-prior L的尾元素的条件旦=L C.P 是()。=NULL D.P-next(20)不带头结点的单链表 L为空的条件是()A.L!=NULL B.L=NULL L(21)带头结点的单链表L为空的条件是()A.L!=NULL B.L=NULL C.L-next C.L-next=NULL D.L-next=NULL D.L-next L(22)两个指针P和Q,分别指向单链表的两个元素，P所指元素是

11、Q所指元素前驱的条件 是()。A.P-next=Q-next B.P-next=Q C.Q-next=P D.P=Q(23)在长度为n的顺序表中，若要删除第 i(1 w i n ext=p2-next;free(pl);B.pl=p2;free(p2);C.pl-next=p2-next;free(p2);D.pl=p2-next;free(p2);(26)若已建立如图所示的单向链表：(14)线性表采用顺序存储的缺点是()。A.存储密度降低 B A.n-i B.i C.n-i+1 D.n-i-l(25)假定己建立以下动态链表结构，且指针Pl和P2已指向如图所示的结点:将P2所指结点从链表中删除

12、并释放该结点的语句组是()对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所

13、占用的空间外的时间效率空间效率以info link 则以下不能将S所指的结点插入到链表尾部，构成新的单向链表的语句组是(对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的

14、直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以 next;=0)存储一个栈，令 an 为栈底，用整型变量 t 指示当前栈顶位 t 的变化为(不变(1)设用一维数组元素 a1-an 置，at 为栈顶元素。当从栈中弹出一个元素时，变量 C.t、1 的顺序进栈，进栈过程中可以出栈，则以下 At=t+1 B(2)有 6 个元素按 6、可能的出栈序列是(A.1、4、3、C.3、l、4、(3)以下叙述中错误的是(栈是限制存取操作只能在一端进行的线性表 消除递归不是必须使用栈 对同一组输入序列进行合法的入、出栈操作，实现递归必定

15、使用工作栈(4)以下不属于栈的基本运算的是()。A.删除栈顶元素 B 删除栈底元素 置为空栈(5)若以链表作为栈的存储结构，则退栈操作时(A.必须判别栈是否满 C.必须判别栈是否空(6)设入栈序列是 1 素是()。A.不确定(7)铁路调度用“栈”有许多编队序列，以下不可能出现的序列是(A.ABC B.CBA C.BAC 5、)。5 2 t=t-1 4、2、6、)。)。D t=n A B C D 得到的输出序列一定相同 C 判断栈是否为空 将栈)。B D n，入栈过程中不允许中途出栈，则第 i 个输出的元 必须判别栈元素的类型 不用作任何判别 C.n-i B.i，假设进栈车厢编队序列为“D.n-

16、i+1 ABC (进栈过程中可以出栈)，出栈则)。D.CAB(8)当栈中当前元素为 n 个，此时进行进栈运算时发生上溢，则该栈的最大容量为()。A.s 一next=a-next 一next;a-next-next=s;B.a=a-next;a 一next=s;s 一next=NULL;C.s 一next=NULL;a=a 一next;a 一next=s;D.a=a 一next;s 一next=a 一next;a-next=s(27)有如下函数：Void fun(struct node*hl,struct node*h2)struct node*t;t=hl;while(t-n ext!t=t

17、一next;t-next=h2;其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此函数的功能是()。A.将链表h2接到链表hl后 B 将链表hl接到链表h2后 C.找到链表hl的最后一个结点由指针返回 D.将链表hl拆分成两个链表 第三章 栈 一、判断题(l)栈是运算受限制的线性表。(2)在栈空的情况下，不能作出栈操作，否则产生溢出。(3)栈一定是顺序存储的线性结构。(4)空栈就是所有元素都为 0 的栈。(5)不管堆栈采用何种存储结构，只要不为空，就可以任意的删除数据元素。在c语言中设顺序栈的长度为 MAXLEN，则top=MAXLEN 时表示栈满。(7)一个栈的输入序列为：A

18、,B,C,D，可以得到输出序列：C,A,B,D。二、选择题 对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和

19、直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以A.n/2 B.n(9)在栈中存取数据的原则是()A.先进先出 B.后进先出(10)插入和删除只能在一端进行的线性表，称为 A.队列 B.循环队列(11)在栈中，出栈操作的时间复杂度为(A.O(l)B.O(log(12)顺序栈为空的判断条件是(C.n D.n+1.后进后出 随意进出 D.循环栈 2n)C.0(n)D.0(n 2)A.top=0 B.top=1 C.top=-1(13)元素A,B,C,D 依次进栈以后，栈顶元素是 A.A B.B C.C(14)顺序栈存储空间的实现使用()存储栈元素。A.链表 B.数组(15)一个顺

20、序栈一但说明，其占用空间的大小(A.已固定 B.可以变动 化(16)链栈LS的示意图如下，栈顶元素是(D.top=m D.D.循环链表 不能固定 B.B C,C D.D.变量 动态变 第四章 队列(I)(2)(3)(4)(5)(6)判断题 队列是限制在两端进行操作的线性表。判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。在链队列做出队操作时，会改变 front 指针的值。在循环队列中，若尾指针 rear大于头指针front,其元素个数为rear-front 队列是一种“后进先出”的线性表。在单向循环队列中，若头指针为 h,那么 选择题 p所指的结点为尾结点的条件是 p=h (1)若用单

21、链表来表示链队列，则应该选用(A.带尾指针的非循环链表 B C.带尾指针的循环链表 D 设有一个空队列，若进入队列的序列为 1,2,3,4 .带头指针的非循环链表.带头指针的循环链表，则合法的出队序列是(A.3,2,4,1 B.4,2,3,I C.4,3,2,1 D.I,2,3,4(3)若利用数组a0 an-1作为一个循环队列，f为当前队头元素的前一个位置，队尾元素的位置，假定队中元素的个数总是小于 n，则当前队中元素的个数为(C.n+r 一 1 D.(n+r A.r 一 f f)%n(4)栈和队列都是(A.顺序存储的线性结构 B.n+f C.限制存取点的线性结构(5)以下不属于队列基本运算的

22、是(A.从队尾插入一个新元素 C.判断一个队列是否为空.链式存储的线性结构 限制存取点的非线性结构 从队列中删除第i个元素 读取队头元素的值 (6)在队列的顺序存储结构中，会产生队列中有剩余空间，但确不能执行入队操作的“假溢 出”现象，在以下几种方法中，不能解决假溢出问题的是()。对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它

23、们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以 A.采用首尾相接的循环队列 头移动 C.当有元素出队时，将己有元素向队头移动 D(7)设队列空间 n=40：队尾指针 rear=6；队头指针 元素的数目是()。A.19 B.21(8)设循环队列的队首指针用()A.front=rear B(9)设循环队列存储于数组元素 示，则判断队满的条件是(A.(rear

24、一 1)%n=C.(rear+1)%n=front C.11 D.29 front 表示，队尾指针用 当有元素入队时，将己有元素向队 申请新的存储单元存放入队元素 front=25，则此循环队列中当前 rear 表示，则判断队空的条件是 front+1=rear C.rear+1=front D.rear=0 a1 an 中，其队头和队尾指针分别用 front 和 rear 表)。=front B.(front+1)%n=rear D.(front l)%n=rear(10)循环队列的特点之一是不会产生(A.上溢出 B.下溢出(11)设用数组 datam+l 作为循环队列 q 尾指针，则执行出

25、队操作应执行的语句是(A.front=front+1;B.)。C 队满 的存储空间，front)。D 为队头指针，假溢出 rear 为队 front=(front+l)C.rear=(rear+l)%m;D.front=(front+l)%m;(12)在队列中存取数据应遵循的原则是()A.先进先出 设长度为 A.O(l)设长度为 A.O(l)(13)(14)(15)B 后进先出 的链队列用单循环链表表示，B.O(log 2n)的链队列用单循环链表示，B.O(log 2n)进行操作的线性表。B 队头 队列是限定在(A.中间(16)一个循环队列一旦说明，其占用空间的大小 A.已固定 B.可以变动

26、C 若只设头指针，C.O(n)若只设尾指针，C.O(n)先进后出 则入队操作的时间复杂度为 D.O(n 则出队操作的时间复杂度为 D.O(n D.随意进出()。2)(2)。队尾)。不能固定(17)在一个顺序存储的循环队列中，队头指针指向队头元素的()位置。端点 动态变化 A.前一个 B 后一个 C 后面 (18)当利用大小为 n 的数组顺序存储一个队列时，该队列的最后一个元素的下标为(A.n-2 B.n-1 C.n D.n+1(19)从一个顺序循环队列中删除一个元素时，首先需要做的操作是(A.队头指针减1 C.队头指针加1(20)若 4 个元素按 A,B,C,D A.A B.B)。B.取出队头

27、指针所指的元素 D.取出队尾指针所指的元素，顺序进队 Q，队头元素是()。C.C D.D 第五章 串 当前)。一、判断题(1)串中任意个字符组成的子序列称为该串的子串。(2)设 S 串的长度为 n，子串的长度为 m，那么子串定位算法的平均时间复杂度在最好情 况下是 0(n+m)。(3)在顺序存储结构中，串的插入算法是非常方便的。设有两个串si和S2,其中s2是si的子串，把s2在si中首次出现的位置找出来的算 法叫作求子串 的算法。(5)空串是任意串的子串。对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是

28、数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以(1)下面关于串的叙述中，错误的是(A.串是由字符组成的有限序列 C.空串是由空格组成的串)。B.模式匹配是串的一种主要运算 D.串

29、可以顺序存储，也可以链式存储 一个字符(6)设有 S1,S2,S3,S4,S5,S6 六个字符串，=，S3=t is ,S4=boot,s5=S4,S5,S6 A.S2,S3,S6(7)设有两个串 p A 连接 中，S5 其值分别为:S1=It is a book ,S6=It is ，则在 属于字符串 S1 的子串的是(,S6 B.S3,S6 C.)。S2,S3,S5 D.，求 q 在 p 中首次出现的位置的运算称作()。模式匹配 C 求子串 D 的 串 值 分 别 为 s1=ABCDEFG,s2=PQRST，)的结果串(D.BCDEFEF(8)设 两 个 字 符 串(SubStr(s1,2

30、,LenStr(s2),SubStr(s1,LenStr(s2),2)A.BCDEF B.BCDEFG(9)串是(A.不少于一个字母的序列 C.BCPQRST)。C.不少于一个字符的序列(10)以下论断正确的是()。A.是空串，空格串 C.somethingSomethig(11)若字符串ABCDEFG采用链式存储，则该字符串的存储密度为(A.20%B.40%(12)上题若需提高存储密度至 也占用 1 个字节)。A.2 B.3 任意个字符的序列 有限个字符的序列 B.beijing)。C.50%D.33.3%50%，则每个结点应存储()。是 bei jing，S2 S2,S3,S3,S5,求串

31、长 则 ConcatStr 的子串 个字节，每个指针占用 2 个字节。)个字符(假设字符串的结束标志(13)某串的长度小于 一个常数，则采用()存储方式最节省空间。A 链式 B 顺序 C 堆结构(14)在实际应用中，要输入多个字符串，且长度无法预定，则应该采用 适。A 链式 B 顺序 C 堆结构 D)存储方式比较合(6)串的长度是指串中不同字符的个数。(7)串是 n 个字母的有限序列。(8)空串不等于空白串。(9)如果两个串含有相同的字符，则说明它们相等。(10)如果一个串中所有的字符均在另一个串中出现，则说明前者是后者的子串。、选择题 假设有两个字符串 S1和S2,其中SI=ABCDXYZ,

32、S2=REST，那么如果进行了下面 的运算 concatstr(substr(S1,3,2),Substr(S1,Strlen(S2),3)，其 结果应是()。A.CDXYZ B.CDDXY C.CDREST D.CDRES (3)设有一个字符串 S=ABC 123 XYZ，问该串的长度为()。A.9 B.10 C.11 D.12 (4)设有一个字符串 S=windows，其子串的数目是()。A.25 个 B.26 个 C.27 个 D.28 个(5)串是一种特殊的线性表，其特殊性表现在()。A.串中允许有空串 B.串可以顺序存储 C.串可以链式存储 D.数据兀素是 第六章 树和二叉树对解题方

33、法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以(

34、1)深度为 h 的二叉树至多有()个结点。A.2 h B.2 h-1 C.2 h-1(2)对于二叉树来说，第 K 层至多有()个结点。KK A.2 K B.2 K-1 C.2(3)结点前序为 ABC 的不同二叉树有()种形态。A.3 B.4 C.5 D.6 K-1 h-1 D.2 h-1-1 K-1 D.2 K-1-1 一、判断题(1)树结构中每个结点最多只有一个直接前驱。(2)二叉树中每个结点的度最大为 2，因此二叉树是一种特殊的树。(3)由树转化为二叉树，其根结点的右子树总是空的。(4)若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的 中序遍历序列中的第一个结点

35、。(5)若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的 中序遍历序列中的最后一个结点。(6)若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树的 前序遍历序列中的最后一个结点。(7)若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的 后序遍历序列中的最后一个结点。(8)在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个子 女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(9)虽然已知二叉树的前序遍历和中序遍历序列，但还不能惟一确定出这棵二叉树，因为并 不知道二叉树的根结点是

36、哪一个。(10)中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。(11)二叉树中一旦插入了结点，则该二叉树就不再是二叉树。(12)用一维数组存储二叉树时，总是以前序遍历存储结点。(13)在满二叉树中，存在度为 1 的结点。(14)在任意一棵二叉树中，终端结点的个数等于度为 2 的结点个数加 1(15)哈夫曼树是带权值的树，且权值较大的结点离根较近。(16)前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树的 非空二叉树。(17)中序遍历序列与后序遍历序列完全相同的二叉树有：空二叉树或任一结点均无右子树的 非空二叉树。(18)前序遍历序列与后序遍历序列完全相

37、同的二叉树只有空二叉树。(19)完全二叉树一定是满二叉树。(20)在中序线索二叉树中，右线索若不为空，则一定指向其双亲。(21)在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。(22)二叉树按某种顺序线索后，任一结点均有指向其前驱和后继的线索。(23)二叉树的前序遍历中，任意一个结点均处于其子树结点的前面。二、选择题 某二叉树的先序遍历序列为：IJKLMNO,中序遍历序列为：JLKINMQ则后序遍历序列为()。A.JLKMNOI B.LKNJOMI C.LKJNOMI D.LKNOJMI 某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC则先序遍历序列为

38、()。A.ACBED B.DECAB C.DEABC D.CEDBA (6)具有 35 个结点的完全二叉树的深度为()。A.5 B.6 C.7 D.8(7)二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法()A.正确 B.错误 C.不确定 D.都有可能(8)根据树的定义，具有 3 个结点的树有()种树型。A.2 B.3 C.4 D.5(9)下列 4 棵树，()不是完全二叉树。对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下

39、列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以(11)A.有序数据元素 C.元素之间无联系的数据 对于一棵满二叉树，m个树叶,(12)D 个结点，C.m=h-1 一棵n个结点的二叉树，其空指针域的个数为(A.n B.n+l C.n-1 D.

40、无序数据元素.元素之间有分支层次的关系 深度为h,则()。D.n=2)。h-l(13)任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序(A.不发生改变 B.发生改变 C.不能确定 D.A在B前的条件疋 在B的左方 D.A(14)A,B为一棵二叉树上的两个叶子结点，在中序遍历时,A.A在B的右方 B.A 是B的祖先 C.A 不确定)。以上都不对)。是B的子 孙(15)(16)|线索二叉树是一种(A.物理 B I如果结点A是结点 A.2 B.3|设有一棵二叉树，其1)。(17)(A.m+n n+I)结构。逻辑 的双亲，而且结点 C.4 度结点有m个,B.2*m+n C.m+2*n(1

41、8)设有一棵二叉树，其先序遍历序列是:二叉树的后序遍历序列是()。C B D.5 2度结点有n个，则该二叉树的结点总数为.逻辑和存储 D.线性 个兄弟，则结点A的度是(D.m+2*ABCDEFG，中序遍历序列是：CBDAFEG则该 A.CDBFGEA B.CDFGBEA C.(19)设有一棵树的度为 4,其中度为1、2、3 1,则这棵树中叶子结点的个数为()。A.5 B.6 C.7 D.8 CDBAFGE D.4的结点个数分别为 4 CDBFEGA(20)用顺序存储结构将完全二叉树的结点逐层存放在数组 放，若结点Bi有子女，则其左孩子结点应是(Bn中，其根结点从B1开始存)。A.B 2i 一

42、I B.B 2i+I C.B 2i D.B i/2 (21)设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为 a,b 和c,对应 的二叉树根结点的右子树上的结点个数是()。A.a B.a+b C.c D.b+c A.13 B.12 C.26 D.25(24)设树中有一结点x,(x),若树中的结点 A.pre(x)pre(y B.pre(x)pre(y D.Pre(x)pre(y post)。(22)设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有()。(23)设电文中出现的字母为 A、B、C、D和E,每个字母在电文中出现的次数分别 为：6,23,3,5 和12，按哈夫曼

43、编码，则字母 C的编码应是()。在先根序列中的序号为 Pre(x)，在后根序列中的序号为 x是结点y的祖先，则下列4个条件中正确的是(。且 post(x)post(y)。且 post(x)P ost(y)A.10 B.110 C.1110 D.1111 A,B.C.D.B 对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的

44、相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以.二叉树中任何一个结点的度都为 2.任何一棵二叉树中至少有一个结点 的度为2(26)已知一棵二叉树的先序遍历序列为 根的右子树的根是()。A.E B.F C.G.只有左子树上的所有结点.只有左子树上的部分结点)C.孩子兄弟链表表示 D.顺序存储 所有叶子结点的先后顺序是().先序和中序相同，但与后序不同.中序和后序相同

45、，但与先序不同)(25)有关二叉树的下列说法正确的是(A.二叉树的度为2 B C.一棵二叉树的度可以小于 2 D EFHIGJK,中序遍历序列为 HFIEJGK,则该二叉树 D.J (27)在完全二叉树中，如果一个结点是叶子结点，则它没有()。A.左孩子结点 B.右孩子结点 C.左、右孩子结点 D.左、右孩子结 点和兄弟结点(28)在一棵非空的二叉树的中序遍历序列中，其根结点的右边()。A.只有右子树上的所有结点 B C.只有右子树上的部分结点 D(29)在下列存储形式中，不是树的存储形式的是(A.双亲表示法 B.孩子链表表示法 表示法(30)在二叉树结点的先序序列、中序序列和后序序列中，A.

46、完全相同 B C.都不相同 D(31)如下图所示的二叉树，按先根次序遍历得到的序列为(C.HDIBEJAFCG D.(32)由4 个结点构造出的不冋的树个数共有()A.3 B.4 C.5 D.6(33)由4 个结点构造出的不冋的二叉树个数共有()A.8 B.10 C.12 D.14 (34)给定一 个整数集合 3,5,6,9,12 ，如图所示的二叉树中 A.ABCDEFGHIJ B.ABDHIEJCFG HIDJEBFGCA 合对应的哈夫曼树。)是该整数集 对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是

47、数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成联系和抽象联系与逻辑数据元素是描述数据的基本单位动态结构和静态结构数据结构通常是研究数据的及它们之间的相互联系数据在计算机存储器内表示时物理地址和逻辑地址相同并且是连续的顺序存储结存在对一关系在非线性结构中每个结点无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外的时间效率空间效率以 (35)设一棵二叉树结点的中序遍历序列为 ABCDEFG，后序遍历序列为 BDCAFGE，则：该二叉树结点的先序遍历序列为()。A

48、.EGFACDB B.EACBDGF C.EAGCFBD D.EGACDFB 该二叉树对应的树林中树的棵数共有()。A.1 B.2 C.3 D.4 该二叉树对应的树林结点的前根次序序列为()。A.EGFACDB B.EACBDGF C.EAGCFBD D.EGACDFB (36)在一棵满二叉树中，假设其叶子结点数为 n，分支数为B，则有B等于()。A.2n 1 B.2 n+1 C.2*(n 1)D.2*(n+1)(37)设结点A有左孩子结点B,右孩子结点C,则在先序遍历、中序遍历和后序遍历这 3 种基本遍历序列中 B-定是C的()。A.前驱 B.后继 C.相邻结点 D.不相邻结点 第七章 图

49、一、判断题(I)图可以没有边，但不能没有顶点。在有向图中，Vl,V 2与V2,v l是两条不同的边。(3)邻接表只能用于有向图的存储。(4)用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图 中顶点个数 有关，而与图的边数无关。(5)若从某个顶点开始，对有n个顶点的有向图 G进行深度优先遍历，所得的遍历序列惟一，则可以断 定其弧数为n 1。(6)有向图不能进行广度优先遍历。(7)若一个无向图以顶点 VI为起点进行深度优先遍历，所得的遍历序列惟一，则可以惟一确 定该图。(8)带权图最小生成树是惟一的。二、选择题(1)在一个图中，所有顶点的度数之和等于图的边数的()倍。

50、A.1/2 B.1 C.2 D.4(2)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A.1/2 B.1 C.2 D.4(3)有8个结点的无向图最多有()条边。A.14 B.28 C.56 D.112 (4)有8个结点的无向连通图最少有()条边。A.5 B.6 C.7 D.8(5)有8个结点的有向完全图有()条边。A.14 B.28 C.56 D.112对解题方法和步骤的描述程序和算法原则上没有别在讨论数据结构时可以通用从逻辑关系上讲数据结构主要分为线性结构和非线性结构两类数据的存储结构是数据的逻辑结构的存储映像二选择题存储结构和逻辑结构存储和抽象下列辑上可以把数据结构分成