数据结构(客观题)

第一章绪论一、判断题数据的逻辑结构与数据元素本身的内容和形式无关。丁数据元素是数据的最小单位。X算法是对解题方法和步骤的描述。丁程序和算法原则上没有区别，在讨论数据结构时可以通用。X从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。丁数据的存储结构是数据的逻辑结构的存储映像。丁二、选择题数据结构通常是研究数据的(A)及它们之间的相互联系。存储结构和逻辑结构B.存储和抽象 C.联系和抽象 D.联系与逻辑下列与数据元素有关的叙述中错误的是(A)。数据元素是有独立含义的数据最小单位B.数据元素是描述数据的基本单位C.数据元素可以称做结点 D.数据元素可以称做记录数据结构中，在逻辑上可以把数据结构分成：(C)。动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(C)存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构非线性结构的数据元素之间存在(D)。一对一关系 B. 一对多关系 C.多对多关系 D.B或C在非线性结构中，每个结点(D)。无直接前驱只有一个直接前驱和个数不受限制的直接后继只有一个直接前驱和直接后继有个数不受限制的直接前驱和直接后继除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的(B)。C.硬件效率 D.C.硬件效率 D.软件效率删除运算方便B.数据的存储结构包括以上三个方面以下属于顺序存储结构优点的是(A)。存储密度大 B.插入运算方便D.可方便地用于各种逻辑结构的存储表示数据结构研究的内容是(D)。数据的逻辑结构C.建立在相应逻辑结构和存储结构上的算法链式存储的存储结构所占存储空间(A)。分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针只有一部分，存放结点值只有一部分，存储表示结点间关系的指针分两部分，一部分存放结点值，另一部分存放结点所占单元数一个正确的算法应该具有5个特性，除输入、输出特性外，另外3个特性是(A)。确定性、可行性、有穷性C确定性、可行性、有穷性C.有穷性、稳定性、确定性易读性、确定性、有效性D.可行性、易读性、有穷性以下关于数据的逻辑结构的叙述中正确的是(A)。数据的逻辑结构是数据间关系的描述数据的逻辑结构反映了数据在计算机中的存储方式数据的逻辑结构分为顺序结构和链式结构数据的逻辑结构分为静态结构和动态结构设问题的规模为n，分析以下程序段：k=n;/*n>l*/m=0;while(k>=(m+l)*(m-l))m++；以上程序段的算法时间复杂度是(A)O(n) B.O(1) C.O() D.O(n2)设问题的规模为n，分析以下程序段：a=10;b=l00;while(b>0){a++;b――；}以上程序段的算法时间复杂度是(A)。A.O(n) B.O(1) C.O() D.O(n2)设语句s=s+i的时间是单位时间，则语句：s=0;for(i=l;i<=n;i++)s=s+i;的时间复杂度为：(B)。A.O(l) B.O(n) C.O(n2) D.O(n3)(16)算法分析的主要任务是(C)。A.探讨算法的正确性和可读性 B.探讨数据组织方式的合理性为给定问题寻找一种性能良好的解决方案 D.研究数据之间的逻辑关系以下叙述中正确的是(C)。顺序存储方式只能用于存储线性结构链式存储方式只能用于存储线性结构,探讨数据组织方式的合理性，研究数据之间的逻辑关系顺序存储和链式存储都可以用于线性和非线性结构以上三种都不对以下叙述中正确的是(C)。A.数据元素是数据处理的最小单位 B.数据项是数据处理的基本单位C.关键字是能够惟一标识一个数据元素的数据项D.数据结构和数据类型的概念是等价的第二章线性表一、判断题线性表的链式存储结构优于顺序存储。X链表的每个结点都恰好包含一个指针域。X线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此

属于同一数据对象。丁在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。X在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。丁在线性表的顺序结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。X顺序存储方式的优点是存储密度大，插入、删除效率高。X在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。X顺序存储的线性表可以实现随机存取。丁线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。丁二、选择题线性表是(A)B.B.—个有限序列，不可以为空D.—个无限序列，不可以为空B.两者长度均固定D.两者长度均可变C.一个无限序列，可以为空一维数组与线性表的特征是(B)A.前者长度固定，后者长度可变C.后者长度固定，前者长度可变用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是B).A.当前结点所在地址域B.A.当前结点所在地址域B.指针域用链表表示线性表的优点是(B)。A.便于随机存取C.占用的存储空间较顺序表少在具有n个结点的单链表中，实现A.遍历链表和求链表的第i个结点便于进行插入和删除操作元素的物理顺序与逻辑顺序相同的操作，其算法的时间复杂度都是0(n)。A在地址为P的结点之后插入一个结点C.C.删除开始结点D.删除地址为P的结点的后继结点下面关于线性表的叙述中，错误的是(B)。线性表采用顺序存储必须占用一片连续的存储单元线性表采用顺序存储便于进行插入和删除操作线性表采用链式存储不必占用一片连续的存储单元线性表采用链式存储便于进行插入和删除操作已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的结点之后，下面的操作序列中正确的是(C)。A.q=p—>next;p一>next二q—>next;B. p —>next 二 q —>next;q二p—>next ;C. q —>next 二 p —>next;p—>next二q;D. p —>next 二 q ;q—>next二p—>next ;设al,a2,a3为三个结点；p,10,20代表地址，则如下的链表存储结构称为—BA.链表 B.单链表 C.双向循环链表 D.双向链表单链表的存储密度(C)。A.大于1 B.等于1 C.小于1 D.不能确定己知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址al,则第i个结点的地址为(A)。

在n个结点的顺序表中，算法的时间复杂度是0(1)的操作是(B)。访问第i个结点(1WiWn)和求第i个结点的直接前驱(2WiWn)在第i个结点之后插入一个新结点(1WiWn-1)删除第i个结点(1WiWn)将n个结点从小到大排序在线性表中(B)只有一个直接前驱和一个直接后继。A.A.首元素 B.中间元素对具有n个结点的线性表进行查找运算A.0(n2) B.0(nlog2n)线性表采用顺序存储的缺点是(D)。A.存储密度降低元素的逻辑顺序与物理顺序不一致尾元素 D.所有元素所需的算法时间复杂度为(D)。0(log2n) D.0(n)只能顺序访问插入、删除操作效率低以下链表结构中，从当前结点出发能够访问到任一结点的是(B)A以下链表结构中，从当前结点出发能够访问到任一结点的是(B)A.单向链表和双向链表C.单向链表和循环链表双向链表和循环链表单向链表、双向链表和循环链表线性表是具有n个(B)的有限序列。A.数据项 A.数据项 B.数据元素C.表元素D.字符若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度(B)。A.0(l) B.0(n) C.0(n2) D.0(log2n)指针P指向循环链表L的首元素的条件是(A)。A.P==L B.L-〉next==P C.P-〉next二二NULL D.P-〉next==L指针P所指的元素是双循环链表L的尾元素的条件是(D)。A.P==L(20)不带头结点B.P—〉prior==L勺单链表L为空的条件是(B)C.P==NULLD.P—>next==LA.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L(21)带头结点的单链表L为空的条件是(C)A.L!=NULLB.L==NULLC.L—>next==NULLD.L—>next==L两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是(B)。A.P—〉next==Q—〉nextB.P—〉next==Q C.Q—〉next==P D.P==Q在长度为n的顺序表中，若要删除第i(1WiWn)个元素，则需要向前移动元素的次数为(B)。A.1 B.n一i C.n一i+1 D.n一i一l在长度为n的顺序表中第i(1WiWn)个位置上插入一个元素时，为留出插入位置所需移动元素的次数为(C)。A.n—i B.iA.n—i B.iC.n—i+1D.n—i—l假定己建立以下动态链表结构，且指针Pl和P2已指向如图所示的结点：则以下可以将P2所指结点从链表中删除并释放该结点的语句组是(C)A.pl—〉next=p2—〉next;free(pl); B.pl=p2;free(p2);pl—〉next=p2—〉next；free(p2); D.pl=p2—〉next;free(p2);若已建立如图所示的单向链表：则以下不能将s所指的结点插入到链表尾部，构成新的单向链表的语句组是(D)。A.s一>next二a—〉next一>next;a—〉next—〉next二sa=a—〉next;a一>next二s;s一>next二NULL

s>next二NULL;a=a ■>next;a一■>next 二s;a =a一>next;s一>next 二a一>next;a—> next二 s一>next ;有如下函数：Voidfun(structnode*hl,structnode*h2){structnode*t;t=hl;while(t-〉next!='\0')t=t■>next;t->next=h2;}其中形参hl和h2分别指向2个不同链表的第一个结点，此函数的功能是(A)。将链表h2接到链表hl后 B.将链表hl接到链表h2后找到链表hl的最后一个结点由指针返回 D.将链表hl拆分成两个链表第三章栈■、判断题栈是运算受限制的线性表。丁在栈空的情况下，不能作出栈操作，否则产生溢出。丁栈一定是顺序存储的线性结构。X空栈就是所有元素都为0的栈。X不管堆栈采用何种存储结构，只要不为空，就可以任意的删除数据元素。X在c语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示栈满。X一个栈的输入序列为：A,B,C,D,可以得到输出序列：C,A,B,D°X二、选择题设用一维数组元素a[1]-a[n]存储一个栈，令a[n]为栈底，用整型变量t指示当前栈顶位置，a[t]为栈顶元素。当从栈中弹出一个元素时，变量t的变化为(A)。A.t=t+1 A.t=t+1 B.t=t-1有6个元素按6、5、4、3、2下可能的出栈序列是(B)。A.1、4、3、5、2、6C.3、l、4、2、6、5C.t不变 D.t=n1的顺序进栈，进栈过程中可以出栈，则以B.6、5、4、3、2、lD.3、6、5、4、2、l以下叙述中错误的是(C)。栈是限制存取操作只能在一端进行的线性表消除递归不是必须使用栈对同一组输入序列进行合法的入、出栈操作，得到的输出序列一定相同实现递归必定使用工作栈以下不属于栈的基本运算的是(B)。A.删除栈顶元素 B.删除栈底元素 C.判断栈是否为空 D.将栈置为空若以链表作为栈的存储结构，则退栈操作时(C)。A.必须判别栈是否满 B.必须判别栈元素的类型C.必须判别栈是否空 D.不用作任何判别设入栈序列是1、2、„、n，入栈过程中不允许中途出栈，则第i个输出的元素是(D)。铁路调度用“栈”，假设进栈车厢编队序列为“ABC"(进栈过程中可以出栈)，出栈则有许多编队序列，以下不可能出现的序列是(D)。"ABC" B."CBA" C."BAC" D."CAB"当栈中当前元素为n个，此时进行进栈运算时发生上溢，则该栈的最大容量为(C)。A.n/2B.n一1 C.nD.n+1(9)在栈中存取数据的原则是(B)。A.先进先出B.后进先出 C.后进后出D.随意进出(10)插入和删除只能在一端进行的线性表，称为(C)。A.队列B.循环队列 C.栈D.循环栈在栈中，出栈操作的时间复杂度为(A)。A.O(l) B.O(log2n) C.O(n) D.O(n2)顺序栈为空的判断条件是(C)。A.top==0 B.top==1 C.top==-1 D.top==m元素A,B,C,D依次进栈以后，栈顶元素是(D)A.A B. B C. C D.D顺序栈存储空间的实现使用(B)存储栈元素。A.链表 B.数组 C.循环链表 D.变量一个顺序栈一但说明，其占用空间的大小(A)。A.已固定 B.可以变动 C.不能固定 D.动态变化链栈LS的示意图如下，栈顶元素是(A)。第四章队列一、判断题队列是限制在两端进行操作的线性表。丁判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。丁在链队列做出队操作时，会改变front指针的值。丁在循环队列中，若尾指针rear大于头指针front,其元素个数为rear-front0X队列是一种“后进先出”的线性表。X在单向循环队列中，若头指针为h,那么p所指的结点为尾结点的条件是p=hoX二、选择题若用单链表来表示链队列，则应该选用(B)。A.带尾指针的非循环链表 B.带头指针的非循环链表C.带尾指针的循环链表 D.带头指针的循环链表设有一个空队列，若进入队列的序列为1,2,3,4，则合法的出队序列是(D)。A.3,2,4,1B.4,2,3,lC.4,3,2,1D.l,2,3,4若利用数组a[0]—a[n-1]作为一个循环队列，f为当前队头元素的前一个位置，r为队尾元素的位置，假定队中元素的个数总是小于n,则当前队中元素的个数为(A)oA.r一f B.n+f一r C.n+r一1 D.(n+r一f)%n栈和队列都是(C)。A.顺序存储的线性结构 B.链式存储的线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构以下不属于队列基本运算的是(B)。A.A.从队尾插入一个新兀素C.判断一个队列是否为空从队列中删除第i个元素读取队头元素的值在队列的顺序存储结构中，会产生队列中有剩余空间，但确不能执行入队操作的“假溢出”现象，在以下几种方法中，不能解决假溢出问题的是(D)。A.A.采用首尾相接的循环队列B.当有元素入队时，将己有元素向队头移动当有元素出队时，将己有元素向队头移动D.申请新的存储单元存放入队元素设队列空间n=40：队尾指针rear=6；队头指针front=25，则此循环队列中当前元素的数目是(A)。A.19 B.21 C.11 D.29设循环队列的队首指针用front表示，队尾指针用rear表示，则判断队空的条件是(A)A.front==rear B.front+1==rearC.rear+1=front D.rear==0设循环队列存储于数组元素a[1]—a[n]中，其队头和队尾指针分别用front和rear表示，则判断队满的条件是(C)。A.(rear一■1)%n==front B.(front+1)%n==rearC.(rear+1)%n==front D.(front一l)%n==rear循环队列的特点之一是不会产生(D)。A.上溢出 B.下溢出 C.队满 D.假溢出设用数组data[m+l]作为循环队列q的存储空间，front为队头指针，rear为队尾指针，则执行出队操作应执行的语句是(B)。A.front=front+1; B.front=(front+l)%(m+l);C.rear=(rear+l)%m; D.front=(front+l)%m;在队列中存取数据应遵循的原则是(A)。A.先进先出 B.后进先出 C.先进后出 D.随意进出设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)设长度为n的链队列用单循环链表示，若只设尾指针，则出队操作的时间复杂度为(C)。A.O(l) B. O(log2n) C.O(n) D. O(n2)队列是限定在(D)进行操作的线性表。A.中间 B.队头 C.队尾 D.端点一个循环队列一旦说明，其占用空间的大小(A)。A.已固定 B.可以变动 C.不能固定 D.动态变化在一个顺序存储的循环队列中，队头指针指向队头元素的(A)位置。A.前一个 B.后一个 C.后面 D.当前当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为(B)。A.n-2 B. n-1 C. n D.n+1从一个顺序循环队列中删除一个元素时，首先需要做的操作是(A)。A.队头指针减1 B.取出队头指针所指的元素C.队头指针加1 D.取出队尾指针所指的元素若4个元素按A,B,C,D,顺序进队Q，队头元素是(A)。第六章树和二叉树一、判断题树结构中每个结点最多只有一个直接前驱。丁二叉树中每个结点的度最大为2，因此二叉树是一种特殊的树。丁由树转化为二叉树，其根结点的右子树总是空的。丁若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的中序遍历序列中的第一个结点。X若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的中序遍历序列中的最后一个结点。丁若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树的前序遍历序列中的最后一个结点。丁若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的后序遍历序列中的最后一个结点。丁在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。X虽然已知二叉树的前序遍历和中序遍历序列，但还不能惟一确定出这棵二叉树，因为并不知道二叉树的根结点是哪一个。X中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。丁二叉树中一旦插入了结点，则该二叉树就不再是二叉树。X用一维数组存储二叉树时，总是以前序遍历存储结点。X在满二叉树中，存在度为1的结点。丁在任意一棵二叉树中，终端结点的个数等于度为2的结点个数加1。丁(15)哈夫曼树是带权值的树，且权值较大的结点离根较近。丁前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树的非空二叉树。丁中序遍历序列与后序遍历序列完全相同的二叉树有：空二叉树或任一结点均无右子树的非空二叉树。丁前序遍历序列与后序遍历序列完全相同的二叉树只有空二叉树。X完全二叉树一定是满二叉树。丁在中序线索二叉树中，右线索若不为空，则一定指向其双亲。X在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。V二叉树按某种顺序线索后，任一结点均有指向其前驱和后继的线索。V二叉树的前序遍历中，任意一个结点均处于其子树结点的前面。V二、选择题深度为h的二叉树至多有(B)个结点。2h B.2h-1 C.2h-1 D.2h-1-1对于二叉树来说，第K层至多有(C)个结点。A.2K B.2K-1 C.2K-1 D.2K-1-1结点前序为ABC的不同二叉树有(C)种形态。A.3 B.4 C.5 D.6某二叉树的先序遍历序列为：IJKLMN0,中序遍历序列为：JLKINM0,则后序遍历序列为(C)。A.JLKMN0I B.LKNJ0MI C.LKJN0MI D.LKN0JMI

某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC,则先序遍历序列为(D)。A.ACBED B.DECAB C.DEABC D.CEDBA具有35个结点的完全二叉树的深度为(B)。A.5 B. 6 C.7 D. 8二叉树按某种顺序线索化后,任一结点均有指向其前驱和后继的线索,这种说法(B)A.正确 B.错误 C.不确定 D.都有可能根据树的定义,具有3个结点的树有(A)种树型。A.2 B.3 C.4 D.5树最适合用来表示(D)。A.有序数据元素树最适合用来表示(D)。A.有序数据元素C.元素之间无联系的数据对于一棵满二叉树,m个树叶A.n=h+m B.h+m=2n无序数据元素元素之间有分支层次的关系n个结点,深度为h,则(D)。m=h-1 D.n=2h-l一棵n个结点的二叉树,其空指针域的个数为(B)。A.n B.n+l C.nT D.不确定任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序(A)。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对A,B为一棵二叉树上的两个叶子结点,在中序遍历时,A在B前的条件是(C)。A.A在B的右方B.A是B的祖先 C.A在B的左方 D.A是B的子孙线索二叉树是一种(A)结构。A.物理 B.逻辑 C.逻辑和存储 D.线性如果结点A是结点B的双亲,而且结点B有4个兄弟,则结点A的度是(D)。A.2 B.3 C.4 D.5设有一棵二叉树,其1度结点有m个,2度结点有n个,则该二叉树的结点总数为(D)。A.m+n B.2*m+n C.m+2*n D.m+2*n+l设有一棵二叉树,其先序遍历序列是：ABCDEFG,中序遍历序列是：CBDAFEG,则该二叉树的后序遍历序列是(A)。A.CDBFGEA B.CDFGBEA C.CDBAFGE D.CDBFEGA设有一棵树的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则这棵树中叶子结点的个数为(D)。A.5 B.6 C.7 D.8用顺序存储结构将完全二叉树的结点逐层存放在数组B[n]中，其根结点从B[1]开始存放，若结点B[i]有子女，则其左孩子结点应是()A.B[2i一l]B.B[2i+l] C.B[2i] D.B[i/2]设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为a,b和c，对应的二叉树根结点的右子树上的结点个数是(C)。A.a B.a+b C.c D.b+c设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有(D)。A.13 B.12 C.26 D.25设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为

6,23,3,5和12，按哈夫曼编码，则字母C的编码应是(D)。A.10B.110C.1110D.1111设树中有一结点x，在先根序列中的序号为Pre(x)，在后根序列中的序号为post(x),若树中的结点x是结点y的祖先，则下列4个条件中正确的是(B)。TOC\o"1-5"\h\zA.pre ( x ) < pre ( y )且 post ( x ) < post( y )pre ( x ) < pre ( y )且 post ( x ) > post( y )Pre ( x ) > pre ( y )且 post ( x ) < post( y )Pre ( x ) > pre ( y )且 post ( x ) > Post(y)有关二叉树的下列说法正确的是(A)。A.二叉树的度为2 B.二叉树中任何一个结点的度都为2C.一棵二叉树的度可以小于2 D.任何一棵二叉树中至少有一个结点的度为2已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是(C)。A.E B.F C.G D.J在完全二叉树中，如果一个结点是叶子结点，则它没有(C)。A.左孩子结点 B.右孩子结点 C.左、右孩子结点 D.左、右孩子结点和兄弟结点在一棵非空的二叉树的中序遍历序列中，其根结点的右边(A)。A.只有右子树上的所有结点 B.只有左子树上的所有结点C.只有右子树上的部分结点 D.只有左子树上的部分结点在下列存储形式中，不是树的存储形式的是(D)。A.双亲表示法 B.孩子链表表示法 C.孩子兄弟链表表示 D.顺序存储表示法在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序是(A)A.完全相同 B.先序和中序相同，但与后序不同C.都不相同 D.中序和后序相同，但与先序不同如下图所示的二叉树，按先根次序遍历得到的序列为(B)。D.HIDJEBFGCAD.D.HIDJEBFGCAD.6D.14由4个结点构造出的不同的树个数共有(C)。A.3 B.4 C.5由4个结点构造出的不同的二叉树个数共有(C)。A.8 B.10 C.12给定一个整数集合｛3,5,6,9,12｝，如图所示的二叉树中(B)是该整数集合对应的哈夫曼树。设一棵二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则：该二叉树结点的先序遍历序列为(B)。A.EGFACDB B.EACBDGF C.EAGCFBD D.EGACDFB该二叉树对应的树林中树的棵数共有(B )。A.1 B.2 C.3 D.4该二叉树对应的树林结点的前根次序序列为(B)。A.EGFACDB B.EACBDGF C.EAGCFBDD.EGACDFB在一棵满二叉树中，假设其叶子结点数为n分支数为B，则有B等于(C)。A.2n一1 B.2n＋1 C.2*(n一1) D.2*(n+1)设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历和后序遍历这3种基本遍历序列中B一定是C的(A)。A.前驱 B.后继 C.相邻结点 D.不相邻结点第七章图一、判断题图可以没有边，但不能没有顶点。丁在有向图中，〈vl,v2〉与〈v2,v1＞是两条不同的边。丁邻接表只能用于有向图的存储。X用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。丁若从某个顶点开始，对有n个顶点的有向图G进行深度优先遍历，所得的遍历序列惟一，则可以断定其弧数为n—1。丁有向图不能进行广度优先遍历。X若一个无向图以顶点vl为起点进行深度优先遍历，所得的遍历序列惟一，则可以惟一确定该图。丁带权图最小生成树是惟一的。丁二、选择题在一个图中，所有顶点的度数之和等于图的边数的(C)倍。TOC\o"1-5"\h\zA.1/2 B.1 C.2 D.4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B)倍。A.1/2 B.1 C.2 D.4有8个结点的无向图最多有(B)条边。A. 14 B. 28 C. 56 D. 112有8个结点的无向连通图最少有(C)条边。A. 5 B. 6 C. 7 D. 8有8个结点的有向完全图有(C)条边。A. 14 B. 28 C. 56 D. 112用邻接表表示图进行广度优先遍历时，通常采用(B)来实现算法的。A.栈 B.队列 C.树 D.图用邻接表表示图进行深度优先遍历时，通常采用(A)来实现算法的。A.栈B.队列C.树D.图(8)深度优先遍历类似于二叉树的(A)。A.先序遍历B.中序遍历C.后序遍历D.层次遍历(9)广度优先遍历类似于二叉树的(D)。A.先序遍历B.中序遍历C.后序遍历D.层次遍历(10)任何一个无向连通图的最小生成树(B)A.只有一棵B.一棵或多棵C. 定有多棵D.可能不存在(11)生成树的构造方法只有(B)。A.深度优先B.深度优先和广度优先C.无前驱的顶点优先D.无后继的顶点优先无向图顶点v的度是关联于该顶点(B)的数目A.顶点 B.边 C.序号 D.下标对如下所示的图，顶点V6的入度为(B)A.0 B.2 C.3 D.5对如下图所示的无向图G，若从顶点Vl开始，按深度优先搜索法进行遍历，则可能的访问顺序为(A)。A.VlV2V5V8V4V6V7V3 B.VlV2V3V4V5V6V7V8C.VIV2V3V4V8V5V6V7 D.VlV2V4V5V8V3V6V7对如图所示的无向图，若从顶点V1开始，按广度优先搜索法进行遍历，则可能访问的顺序为(D)。A.VIV2V3V4V5V6V7V8 B.VIV2V6V3V4V7V8V5C.VIV2V6V3V4V5V7V8 D.VIV2V4V7V3V8V6V5对如图所示的有向图G,它的拓扑序列是(C)。A.a,b,c,dB.a,d,b,cC.a,b,d,c D.b,a,d,c在有向图G的拓扑序列中，如果顶点vi在vj之前，则在下列情况中一定不可能出现的是(D)。A.G中有弧Vvi,vj> B.G中有一条从Vi到vj的路径C.G中没有弧VVi,vj〉 D.G中有一条从vj到Vi的路径对如下所示的图，它的生成树有(C)棵。A.1 B.5 C.6 D不确定下面哪一种图的邻接矩阵肯定是对称矩阵(B)。A.有向图 B.无向图 C.AOV网 D.AOE网如图所示的有向图的顶点可以排成(C)个不同的拓扑序列。A．3 B．5 C.7 D.9下面关于图的存储的叙述中正确的是(A)。用邻接矩阵存储图，占用的存储空间大小只与图中结点个数有关，而与边表无关。用邻接矩阵存储图，占用的存储空间大小只与图的边数有关，而与结点个数无关。用邻接表存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关。用邻接表存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。在一个无向图中，所有顶点的度数之和等于所有边数的(B)。A.1倍 B.2倍 C.1/2倍 D.不确定第八章查找一、判断题二分查找法要求待查表的关键字的值必须有序。丁哈希法是一种将关键字转换为存储地址的存储方法。丁在二叉排序树中，根结点的值都小于孩子结点的值。X对有序表而言，采用二分查找总比采用顺序查找法速度快。丁二叉排序树是一种特殊的线性表。X哈希表的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。丁一般来说，用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。丁对于满足二分查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找，折半查找和分块查找。X对于同一组待输入的关键值集合，虽然各关键值的输入顺序不同，但得到的二叉排序树是相同的。X对于两棵具有相同数据元素而形状不同的二叉排序树，按中序遍历它们得到的数据元素的排列次序是一样的。丁在二叉排序树中插入新结点时，不必移动其他结点，仅需改动某个结点的指针，使它由空变为非空即可。丁在二叉排序树上删除一个结点时，不必移动其他结点，只需将其双亲结点相应的指针域置空即可。X平衡的二叉排序树的任何子树都是平衡的二叉排序树。丁只有最下面的两层结点的度数可以小于2，其他结点的度数必须等于2的二叉树才是平衡的二叉树。X任意一棵二叉排序树的平均查找时间都小于用顺序查找算法搜索同一结点的顺序表的平均查找时间。X二、选择题查找表是以(A)为查找结构的。A.集合 B.图 C.树 D.文件顺序查找法适合于存储结构为(B)的线性表。A.哈希存储 B.顺序存储或链接存储C.压缩存储 D.索引存储对线性表进行二分查找时，要求线性表必须(D)。A.以顺序方式存储 B.以链接方式存储，且结点按关键字有序排序C.以链接方式存储 D.以顺序方式存储，且结点按关键字序排序采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为(C)。A.n B.n/2 C.(n+l)/2 D.(n-l)/2采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为(D)。A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)有l个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，(C)次比较后查找成功。A.2 B.3 C.4 D.5设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：add(15)=4add(38)=5add(61)=6add(84)=7

其余地址为空。如用二次探测再哈希处理冲突，关键字为49的结点的地址是(D)。A.8B.3C.5D.9有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为(B)。A.35/12B.37/12C.39/12D.43/12如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用()查找方法。A.分块 B.顺序 C.二分 D.哈希采用分块查找时，若线性表共有625个元素，查找每个元素的概率相等，假设采用顺序查找来确定结点所在的块时，每块分()个结点最佳。A.6 B.10 C.25 D.625100个元素采用二分查找时，最大的比较次数是(C)。A.25 B.50 C.7 D.10衡量查找算法效率的主要标准是(B)。A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易程度为了有效地利用散列查找技术，需要解决的问题是(B)。找一个好的散列函数设计有效的解决冲突的方法用整数表示关键码值A.①和③ B.①和② C.②和③ D.全部设有一个已按元素值排好序的线性表，长度大于2，对于给定的关键字值k，分别用顺序查找和折半查找算法查找一个关键字值与k相等的元素，比较的次数分别记为s和b,在查找不成功的情况下，正确的数量关系是(B)。A.总有s=b B总有s>b C总有s<b D.与k值大小有关散列表的地址区间为0一16，散列函数为Hl(K)=K%17，采用线性探测法解决冲突，将关键字序列26,25,72,38,8,18,59依次存储到散列表中。①元素59存放在散列表中的地址为(D)。A.8A.8B.9C.10②查找元素59，需要比较的次数为(C)。A.2B.3C.4D.11D.5对包含n个元素的散列表进行检索，平均检索长度为(D)。A.O(log2n)A.O(log2n)B.O(nlog2n)C.O(n)D不直接依赖于n对于具有144个记录的文件，若采用分块查找法，并采用折半查找法确定块，且每块长度为8，则查找成功时的平均查找长度为(B)。A.143 B.14 C.13 D.9具有4层结点的二叉平衡树中结点个数至少有(D)。A.16 B.15 C.8 D.7在如下图所示的四棵二叉树中，属于平衡二叉树的是(B).

第九章排序一、判断题大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。丁快速排序在任何情况下都比其他排序方法速度快。X快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。丁如果某种排序算法不稳定，则该排序方法就没有实际应用价值。X⑸对n个记录的进行快速排序，所需要的平均时间是0(nlog2n)°J⑹冒泡排序是不稳定的排序。X堆排序所需的时间与待排序的记录个数无关。X当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。X对快速排序来说，初始序列为正序或反序都是最坏的情况。丁二、选择题A. 1 , 2 , 3 , 4 , 5C. 3 , l , 2 , 4 , 5对以下几个关键字序列进行快速排序A. 4 , l , 2 , 3 , 6 , 5 , 7C. 4 , 2 , l , 3 , 6 , 7 , 5对以下几个关键字序列进行快速排序A. A. 1 , 2 , 3 , 4 , 5C. 3 , l , 2 , 4 , 5对以下几个关键字序列进行快速排序A. 4 , l , 2 , 3 , 6 , 5 , 7C. 4 , 2 , l , 3 , 6 , 7 , 5对以下几个关键字序列进行快速排序A. 2 , 3 , l , 4 ,C. 2 , l , 3 , 4 ,堆排序属于(CA.插入排序6,56,7）。B.交换排序B.2,l,D.5,3,以第一个元素为轴，B.4,3,D.l,2,3,4,5l,2,4一次划分效果不好的是（D）。l,7,6,3,4,5,每次划分效果都好的是（B4,3,l4,1,2B.D.）。6,5,假设待排序数据元素序列为［4,2,己知一趟的结果为［)。B.直接选择C.,1,82,4法进行按递增序排序，选用的排序方法为(CA.冒泡(从后向前)枢轴)(9)设待排序数据元素序列为［4,l,2,3］C.选择排序,7,6,1,3,7,二路归并排序D.归并排序

］，应用一种排序方5,6,9］，则所D.快速(以2为应用一种排序方法进行递增序排序，已(1)假设待排序数据元素序列的关键字序列为2,1,2'，应用选择排序方法排降序得到的结果为(C)。A.2',2,1 B.1,2',2C.2,2',1 D.l,2,2'(2)假设待排序数据元素序列的关键字序列为1,2,2',1'，应用冒泡(插入、归并)排序方法按递增序排序得到的结果为(A)。A.1,l',2,2'B.1,1',2',2C.l',l,2,2'D.1',1,2',2快速排序每次划分的效果好坏和以下何种因素有直接关系(C)。A.关键字的排列情况 B.数据元素的个数 C.轴的相对大小 D.关键字值的最大值对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果最好的是(C)。知两趟后的结果为［1,2,3,4］，则所选用的排序方法为(C)。A.直接插入 B.直接选择 C.冒泡(从前向后)D.冒泡(从后向前）（10）设待排序数据元素序列为［2,4,1,3,7,1'］，应用一种排序方法进行递增序排序，已知最终的结果为［1',1,2,3,4,7，］则所选用的排序方法为（B）。A.直接插入 B.直接选择 C.冒泡（从前向后） D.二路归并（11） 设待排序数据元素序列有n个记录，应用直接插入排序方法，进行一趟排序，所需比较和移动记录的最少次数分别为（A）。A.1、2 B.2、1 C.1、1 D.2、2（12） 假设待排序数据元素序列有n个记录，应用冒泡排序方法，进行一趟排序，所需比较和移动记录的最少次数分别为（C）。A.1、2 B.n一1、1 C.n一l、0 D.n一l、n一1（13） 设待排序数据元素序列有n个记录，应用冒泡排序方法，进行一趟排序，所需比较和交换记录的最多次数分别为（D）。A.n、n B.n一1、n C.n一l、0 D.n一l、n一1（14） 设待排序数据元素序列有n个记录，应用快速排序方法，进行一次划分，所需比较和移动记录的最少次数分别为（C）。A.1、1