第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√）3.数据元素是数据的最小单位。（×）4.数据的逻辑结构和数据的存储结构是相同的。（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√）7.数据的存储结构是数据的逻辑结构的存储映象。（√）8.数据的物理结构是指数据在计算机内实际的存储形式。（√）9.数据的逻辑结构是依赖于计算机的。（×）10.算法是对解题方法和步骤的描述。（√）二、填空题1.数据有逻辑结构和存储结构两种结构。2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。4.树形结构和图形结构合称为非线性结构。5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。7.数据的存储结构又叫物理结构。8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。9.线性结构中的元素之间存在一对一的关系。10.树形结构中的元素之间存在一对多的关系。11.图形结构的元素之间存在多对多的关系。12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。14.算法是一个有穷指令的集合。15.算法效率的度量可以分为事先估算法和事后统计法。16.一个算法的时间复杂度是算法输入规模的函数。17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学科。三、选择题1.数据结构通常是研究数据的（A）及它们之间的相互关系。A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑2.在逻辑上可以把数据结构分成（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构。3.数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构4.非线性结构中的每个结点（D）。A．无直接前驱结点．B．无直接后继结点．C．只有一个直接前驱结点和一个直接后继结点D．可能有多个直接前驱结点和多个直接后继结点5.链式存储结构所占存储空间（A）。A．分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。B．只有一部分，存放结点的值。C．只有一部分，存储表示结点间关系的指针。D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素6.算法的计算量大小称为算法的（C）。A．现实性B．难度C．时间复杂性D．效率7.数据的基本单位（B）。A．数据结构B．数据元素C．数据项D．文件8.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为（A）结构。A．顺序结构B．链式结构C．索引结构D．散列结构9.每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）。A．顺序B．链式C．索引D．散列10.以下任何两个结点之间都没有逻辑关系的是（D）。A．图形结构B．线性结构C．树形结构D．集合11.在数据结构中，与所使用的计算机无关的是（C）。A．物理结构B．存储结构C．逻辑结构D．逻辑和存储结构12.下列4种基本逻辑结构中，数据元素之间关系最弱的是（A）。A．集合B．线性结构C．树形结构D．图形结构13.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）。A．逻辑结构B．存储结构C．逻辑实现D．存储实现14.每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。A．顺序B．链式C．索引D．散列15.算法能正确的实现预定功能的特性称为算法的（A）。A．正确性B．易读性C．健壮性D．高效性16.算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。A．正确性B．易读性C．健壮性D．高效性17.下列时间复杂度中最坏的是（D）。A．O（1）B.O（n）C.O(log2n)D.O(n2)18.下列算法的时间复杂度是（D）。for(i=0;i
prior->next=p->next；p->next->prior=p->prior20.在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用语句S->next->next=p->next和P->next=S；来实现该操作。p∧abs三、选择题1.在具有n个结点的单向链表中，实现（A）的操作，其算法的时间复杂度都是O(n).A.遍历链表或求链表的第i个结点B.在地址为P的结点之后插入一个结点C.删除开始结点D.删除地址为P的结点的后继结点2.设a、b、c为3个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B）。pa10b20c∧A．循环链表B．单向链表C．双向循环链表D．双向链表3.单向链表的存储密度（C）。A.大于1B.等于1C.小于1D.不能确定4.已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（A）。A.B+(i-1)×mB.B+i×mC.B-i×mD.B+(i+1)×m5.在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（B）。A．O（1）B.O（n）C.O(n2)D.O(log2n)6.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。A.P==LB.P->front==LC.P==NULLD.P->rear==L7.两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（B）A．P->next==Q->nextB.P->next==QC.Q->next==PD.P==Q8.用链表存储的线性表，其优点是（C）。A．便于随机存取B．花费的存储空间比顺序表少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同9.在单链表中，增加头结点的目的是（C）。A．使单链表至少有一个结点B．标志表中首结点的位置C．方便运算的实现D．说明该单链表是线性表的链式存储结构10.下面关于线性表的叙述中，错误的是（D）关系。A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素11.L是线性表，已知LengthList(L)的值是5，经DelList(L，2)运算后，LengthList(L)的值是（C）。A．2B．3C．4D．512.单向链表的示意图如下：LABCD∧PQR指向链表Q结点的前驱的指针是（B）。A．LB．PC．QD．R13.设p为指向单循环链表上某结点的指针，则*p的直接前驱（C）。A．找不到B．查找时间复杂度为O（1）C．查找时间复杂度为O（n）D．查找结点的次数约为n14.等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（8）。A．nB.(n-1)/2C.n/2D.(n+1)/215.在下列链表中不能从当前结点出发访问到其余各结点的是（C）。A.双向链表B.单循环链表C.单向链表D.双向循环链表16.在顺序表中，只要知道（D），就可以求出任一结点的存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小17.在双向链表中做插入运算的时间复杂度为（A）。A．O（1）B.O（n）C.O(n2)D.O(log2n)18.链表不具备的特点是（A）。A．随机访问B.不必事先估计存储空间C.插入删除时不需要移动元素D.所需空间与线性表成正比19.以下关于线性表的论述，不正确的为（C）。A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继D.存在这样的线性表，即表中没有任何结点20.在（B）的运算中，使用顺序表比链表好。A.插入B.根据序号查找C.删除D.根据元素查找第3章栈一、判断题1.栈是运算受限制的线性表。（√）2.在栈空的情况下，不能作出栈操作，否则产生下溢。（√）3.栈一定是顺序存储的线性结构。（×）4.栈的特点是“后进先出”。（√）5.空栈就是所有元素都为0的栈。（×）6.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示栈满。（×）7.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（√）8.一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（×）9.递归定义就是循环定义。（×）10.将十进制数转换为二进制数是栈的典型应用之一。（√）二、填空题1.在栈结构中，允许插入、删除的一端称为栈顶。2.在顺序栈中，当栈顶指针top=-1时，表示栈空。3.在有n个元素的栈中，进栈操作时间复杂度为O（1）。4.在栈中，出栈操作时间复杂度为O（1）。5.已知表达式，求它的后缀表达式是栈的典型应用。6.在一个链栈中，若栈顶指针等于NULL，则表示栈空。7.向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top;top=p；操作。8.顺序栈S存储在数组S->data[0…MAXLEN-1]中，进栈操作时要执行的语句有：S->top++。(或S->top+1)S->data[S->top]=x9.链栈LS，指向栈顶元素的指针是LS->next。10.从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。11.由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。12.已知顺序栈S，在对S进栈操作之前首先要判断栈是否满。13.已知顺序栈S，在对S出栈操作之前首先要判断栈是否空。14.若内在空间充足，链栈可以不定义栈满运算。15.链栈LS为空的条件是LS->next=NULL。16.链栈LS的栈顶元素是链表的首元素。17.同一栈的各元素的类型相同。18.若进栈的次序是A、B、C、D、E，执行3次出栈操作以后，栈顶元素为B。19.A+B/C-D*E的后缀表达式是ABC/+DE*-。20.4个元素A、B、C、D顺序进S栈，执行两次Pop(S,x)运算后，x的值是C。三、选择题1.插入和删除操作只能在一端进行的线性表，称为（C）。A．队列B．循环队列C．栈D．循环栈2.设有编号为1，2。3，4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（D）。A．1234B．1243C．1324D．14233.如果以链表作为栈的存储结构，则出栈操作时（B）。A．必须判别栈是否满B．必须判别栈是否为空C．必须判别栈元素类型D．栈可不做任何判别4.元素A、B、C、D依次进栈以后，栈顶元素是（D）A．AB．BC．CD．D5.顺序栈存储空间的实现使用（B）存储元素。A．链表B．数组C．循环链表D．变量6.在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（A）。A．已固定B．不固定C．可以改变D．动态变化7.带头结点的链栈LS的示意图如下，栈顶元素是（A）。LSHABCD∧A．AB．BC．CD．D8.链栈与顺序栈相比，有一个比较明显的优点是（B）。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便9.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列（d）命令。A．x=top;top->next;B.top=top->next;x=top->dataC.x=top->data;D.x=top->data;top=top->next10.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列（B）命令。A.HS->next=SB.S->next=HS->next;HS->next=S;C.S->next=HS->next;HS=S;D.S->next=HS=HS->next11.4元素按A、B、C、D顺序进S栈，执行两次Pop(S，x)运算后，栈顶元素的值是（B）。A．AB．BC．CD．D12.元素A、B、C、D依次进栈以后，栈底元素是（A）。A．AB．BC．CD．D13.经过下列栈的运算后，再执行ReadTop(s)的值是（A）。InitStack(s);Push(s，a);Push(s，b);Pob(s);A.aB.bC.1D.014.经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s，a);Push(s，b);ReadTop(s)；Pob(s，x);A.aB.bC.1D.015.经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Pob(s，x);Push(s,b);Pob(s，x);A.aB.bC.1D.016.经过下列栈的运算后,SEmpty(s)的值是（C）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pob(s，x);Pob(s，x);A.aB.bC.1D.017.向顺序栈中输入元素时（B）。A．先存入元素，后移动栈顶指针B．先移动栈顶指针，后存入元素C．谁先谁后无关紧要D．同时进行18.初始化一个空间大小为5的顺序栈S后，S->top的值是（B）。A．0B．-1C．不再改变D．动态变化19.设有一个入栈的次序A、B、C、D、E，则栈不可能的输出序列是（C）。A．EDCBAB．DECBAC．DCEABD．ABCDE20.设有一个顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是B、D、C、F、E、A，则栈的容量至少应是（A）。A．3B．4C．5D．6第4章队列一、判断题1.队列是限制在两端进行操作的线性表。（√）2.判断顺序队列为空的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
是头指针和尾指针都指向同一个结点。（√）3.在链队列上做出队操作时，会改变front指针的值。（×）4.在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。（√）5.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。（×）6.链队列在一定范围内不会出现队满的情况。（√）7.在循环链队列中无溢出现象。（×）8.栈和队列都是顺序存储的线性结构。（×）9.在队列中允许删除的一端称为队尾。（×）10.顺序队和循环队关于队满和队空的判断条件是一样的。（×）二、填空题1.在队列中存取数据应遵循的原则是先进先出。2.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。3.在队列中，允许插入的一端称为队尾。4.在队列中，允许删除的一端称为队首（或队头）。5.队列在进行出队操作时，首先要判断队列是否为空。6.顺序队列在进行入队操作时，首先在判断队列是否为满。7.顺序队列初始化后，初始化后，front=rear=-1。8.解决顺序队列“假溢出”的方法是采用循环队列。9.循环队列的队指针为front，队尾指针为rear，则队空的条件为front==rear。10.链队列LQ为空时，LQ->front->next=NULL。11.设长度为n的链队列用单循环表表示，若只设头指针，则入队操作的时间复杂度为O(n)。12.设长度为n的链队列用单循环表表示，若只设尾指针，则入队操作的时间复杂度为O(1)。13.在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。14.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==(rear+1)%MAXLEN。15.在一个链队列中，若队首指针为front，队尾指针为rear，则判断队列只有一个结点的条件为front==rear或front!。16.向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。17.读队首元素的操作不改变或不影响队列元素的个数。18.设循环队列的容量为40（序号0～39），现经过一系列的入队和出队的运算后，front=11，rear=19，则循环队列中还有8个元素。19.队列Q，经过下列运算：InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；QEmpty(Q)；后的值是8。20.队列Q经过InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是a。三、选择题1.队列是限定在（D）进行操作的线性表。A．中间者B.队首C.队尾D.端点2.队列中的元素个数是（B）。A．不变的B.可变的C.任意的D.03.同一队列内的各元素的类型（A）。A.必须一致B.不能一致C.可以不一致D.不限制4.队列是一个（C）线性表结构。A.不加限制的B.推广了的C.加了限制的D.非5.当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B）。A.n-2B.n-1C.nD.n+16.一个循环队列一旦说明，其占用空间的大小（A）。A.已固定B.可以变动C.不能固定D.动态变化7.循环队列占用的空间（A）。A.必须连续B.不必连续C.不能连续D.可以不连续8.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（B）。A.0～10B.0～9C.1～9D.1～109.若进队的序列为A、B、C、D，则出队的序列是（C）。A.B、C、D、AB.A、C、B、DC.A、B、C、DD.C、B、D、A10.4个元素按A、B、C、D顺序连续进队Q，则队尾元素是（D）A．AB．BC．CD．D11.4个元素按A、B、C、D顺序连续进队Q，执行一次QutQueue(Q)操作后，队头元素是（B）。A.AB.BC.CD.D12.4个元素按A、B、C、D顺序连续进队Q，执行4次QutQueue(Q)操作后，再执行QEmpty(Q)；后的值是（B）。A.0B.1C.2D.313.队列Q，经过下列运算后，x的值是（B）。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；A.aB.bC.0D.114.循环队列SQ队满的条件是（B）。A.SQ->rear==SQ->frontB.(SQ->rear+1)%MAXLEN==SQ->frontC.SQ->rear==0D.SQ->front==015.设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针，若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（A）操作。A.s->next=top->next;top->next=s;B.top->next=s;C.s->next=top;top->next;D.s->next=top;top=s;16.带头结点的链队LQ示意图如下，链队列的队头元素是（A）。LQ->frontHABCD∧LQ->rearA．AB．BC．CD．D17.带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）。LQ->frontHABCD∧LQ->rearA.LQ->frontB.LQ->rearC.LQ->front->nextD.LQ->rear->next18.带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A).LQ->frontHABCD∧LQ->rearA.始终不改变B.有时改变C.进队时改变D.出队时改变19.队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C）。InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.aB.bC.0D.120.若用一个大小为6数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（B）。A.5和1B.4和2C.2和4D.1和5第5章串一、判断题1.串是n个字母的有限序列。（×）2.串的数据元素是一个字符。（√）3.串的长度是指串中不同字符的个数。（×）4.如果两个串含有相同的字符，则说明它们相等。（×）5.如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（×）6.串的堆分配存储是一种动态存储结构。（√）7.“DT”是“DATA”的子串。（×）8.串中任意个字符组成的子序列称为该串的子串。（×）9.子串的定位运算称为模式匹配。（√）10.在链串中为了提高存储密度，应该增大结点的大小。（√）二、填空题1.由零个或多个字符组成的有限序列称为字符串（或串）。2.字符串按存储方式可以分为顺序存储、链接存储和堆分配存储。3.串的顺序存储结构简称为顺序串。4.串顺序存储非紧凑
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
的缺点是空间利用率低。5.串顺序存储紧凑格式的缺点是对串的字符处理效率低。6.串链接存储的优点是插入、删除方便，缺点是空间利用率。7.在C或C++语言中，以字符\0表示串值的终结。8.空格串的长度等于空格的个数。9.在空串和空格串中，长度不为0的是空格串。10.两个串相等是指两个串长度相等，且对应位置的字符都相同。11.设“S=MyMusic”，则LenStr(s)=8。12.两个字符串分别为；S1=”Todayis”、S2=”30July，2005”，ConcatStr(S1，S2)的结果是Todayis30July,2005。13.求子串函数SubStr(“Todayis30July，2005”，13，4)的结果是July。14.在串的运算中，EqualStr(aaa,aab)的返回值<0。15.在串的运算中，EqualStr(aaa,aaa)的返回值0。16.在子串的定位运算中，被匹配的主串称为目标串，子串称为模式。17.模式匹配成功的起始位置称为有效位移。18.设S=”abccdcdccbaa”，T=”cdcc”，则第6次匹配成功。19.设S=”c:/mydocument/text1.doc”，T=”mydont”，则字符定位的位置为0。20.若n为主串长度，m为子串长度，n>>m，则模式匹配算法最坏情况下的时间复杂度为(n-m+1)*m。三、选择题1.串是和种特殊的线性表，其特殊体现在（B）。A．可能顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符2.某串的长度小于一常数，则采用（B）存储方式最节省空间。A．链式B．顺序C．堆结构D．无法确定3.以下论述正确的是（C）。A．空串与空格串是相同的B．”tel”是”Teleptone”的子串C．空串是零个字符的串D．空串的长度等于14.以下论述正确的是（B）。A．空串与空格串是相同的B．”ton”是”Teleptone”的子串C．空格串是有空格的串D．空串的长度等于15.以下论断正确的是（A）。A．全部由空格组成的串是空格串B．”BEUIJING”是”BEIJING”的子串C．”something”<”Something”D．”BIT”=”BITE”6.设有两个串S1和S2，则EqualStr（S1，S2）运算称作（D）。A．串连接B．模式匹配C．求子串D．串比较7.串的模式匹配是指（D）。A．判断两个串是否相等B．对两个串比较大小C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置8.若字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为（D）。A．20%B．40%C．50%D．33.3%9.若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个结点应存储（A）个字符。A.2B.3C.4D.510.设串S1=”IAM”，S2=”ASDUDENT”，则ConcatStr(S1，S2)=（B）。A．”IAM”B.”IAMASDUDENT”C.”IAMASDUDENT”D.”ASDUDENT”11.设S=””，则LenStr(S)=（A）。A.0B.1C.2D.312.设目标串T=”AABBCCDDE”，模式P=”ABCDE”，则该模式匹配的有效位移为（A）。A.0B.1C.2D.313.设目标串T=”AABBCCDDEEFF”，模式P=”CCD”，则该模式匹配的有效位移为（D）。A.2B.3C.4D.514.设目标串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外层循环进行了（D）次。A.1B.9C.4D.515.模式匹配算法在最坏情况下的时间复杂是（D）。A.O(m)B.O(n)C.O(m+n)D.O(m×n)16.S=”morning”,执行求子串函数SubSur(S,2,2)后结果为（B）。A.”mo”B.”or”C.”in”D.”ng”17.S1=”good”，S2”morning”，执行串连接函数ConcatStr(S1，S2)后结果为（A）。A.”goodmorning”B.”goodmorning”C.”GOODMORNING”D.”GOODMORNING”18.S1=”good”,S2=”morning”执行函数SubSur(S2,4,LenStr(S1))后的结果为（B）。A.”good”B.”ning”C.”go”D.”morn”19.设串S1=”ABCDEFG”，S2=”PQRST”，则ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr（S2），2））的结果串为（D）。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF20.若串S=”SOFTWARE”，其子串的数目最多是（C）。A．35B.36C.37D.38第6章多维数组和广义表一、判断题1.n维多维数可以视为n-1维数组元素组成的线性结构。（√）2.稀疏矩阵中非零元素的个数远小于矩阵元素的总数。（√）3.上三角矩阵主对角线以上（不包括主对角线的元素），均为常数C。（×）4.数组元素可以由若干数据项组成。（√）5.数组的三元组表存储是对稀疏矩阵的压缩存储。（√）6.任何矩阵都可以进行压缩存储。（×）7.广义表是线性表的推广，所以广义表也是线性表。（×）8.广义表LS=（a0，a1，……an-1），则an-1是其表尾。（×）9.广义表（（a，b）a，b）的表头和表尾是相等的。（√）10.一个广义表的表尾总是一个广义表。（√）二、填空题1.多维数组的顺序存储方式有按行优先顺序存储和按优先顺序存储两种。2.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取结构。3.在n维数组中的每一个元素最多可以有n个直接前驱。4.输出二维数组A[n][m]中所有元素值的时间复杂度为n(n*m)。5.数组元素a[0…2][0…3]的实际地址是2000，元素长度是4，则LOC[1，2]=2024。6.稀疏矩阵的三元组有3列。7.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。8.n阶对称矩，如果只存储下三角元素，只需要n(n-1)/2个存储单元。9.稀疏矩阵A如图6-19所示，其非零元素存三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第4项。10.稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。11.任何一个非空广义表的表尾必定是广义表（或子表）。12.tail(head((a，b)(c，d)=b。13.设广义表（（a，b，c））则将c分离出来的运算是head(tail(tail(head(L))))。14.广义表现出（（a，b）c，d），表尾是(c,d)。15.n阶下三角矩阵，因为对角线的上方是同一个常数，需要n(n-1)/2+1个存储单元。16.稀疏矩阵中有n个非零元素，则三元组有n行。17.广义表LS=（a,（b）,（（c,（d））））的长度是3。18.广义表LS=（a,（b）,（（c,（d））））的深度是4。19.广义表LS=（（），L）,则L的深度是∞。20.广义表LS=（a,（b）,（（c,（d））））的表尾是((b),((c,(d))))。三、选择题1.在一个m维数组中，（D）恰好有m个直接前驱和m个直接界后继。A.开始结点B.总终端结点C.边界结点D.内部结点2.对下述矩阵进行压缩存储后，失去随机存取功能的是（D）。A.对称矩阵B.三角矩阵C.三对角矩阵D.稀疏矩阵3.在按行优先顺序存储的三元组表中，下述陈述错误的是（D）。A.同一行的非零元素，是按列号递增次序存储的B.同一列的非零元素，是按行号递增次序存储的C.三元组表中三元组行号是递增的D.三元组表中三元组列号是递增的4.对稀疏矩阵进行压缩存储是为了（B）。A.降低运算时间B.节约存储空间C.便于矩阵运算D.便于输入和输出5.若数组A[0‥m][0‥n]按列优先顺序存储，则aij的地址为（A）。A.LOC(a00)+[j×m+i]B.LOC(a00)+[j×n+i]C.LOC(a00)+[(j-1)×n+i-1]D.LOC(a00)+[(j-1)×m+i-1]6.下列矩阵是一个（B）。A．对称矩阵B．三角矩阵C．稀疏矩阵D．带状矩阵100023004560789107.在稀疏矩阵的三元组表示法中，每个三元组表示（D）。A．矩阵非零元素的值B．矩阵中数据元素的行号和列号C．矩阵中数据元素的行号、列号和值D．矩阵中非零数据元素的行号、列号和值8.已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存储存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（B）。A．872B．860C．868D．8649.广义表是线性表的推广，它们之间的区别于（A）。A．能否使用子表B．肥否使用原子项C．是否能为空D．表的长度10.下列广义表属于线性表的是（B）。A.E=(a,E)B.E=(a,b,c)C.E=(a,(b,c))D.E=(a,L);L=()11.广义表（（a,b）,c,d）的表尾是（D）。A．aB．dC．(a,b)D．(c,d)12.广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（A）。A．xB．(a,b)C．(x,(a,b))D．A13.tail(head((a,b),c,(c,d)))的结果是（B）。A．bB．(b)C．(a,b)D．(d)14.若广义表满足head(L)=tail(L),则L的形式是（B）。A．空表B．若L=（a1,…,an）,则a1=(a2,…,an)C．若L=（a1,…,an）,则(a1=a2,=…an)D．((a1)(a1))15.数组是一个（B）线性表结构。A.非B.推广了的C.加了限制的D.不加限制的16.数组A[0：1，0：1，0：1]共有（D）元素。A.4B.5C.6D.817.广义表（（a,b）,c,d）的表头是（C）。A.aB.dC.(a,b)D.(c,d)18.广义表A=(a),则表尾为（C）。A.aB.(())C.空表D.(a)19.以下（C）是稀疏矩阵的压缩存储方法。A.一维数组B.二维数组C.三元数组D.广义表20.设广义表D=(a,b,c,d),其深度为（D）。A.2B.3C.4D.∞第7章树和二叉树一、判断题1.树结构中每个结点最多只有一个直接前驱。（√）2.完全二叉树一定是满二叉树。（×）3.在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（×）4.一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√）5.二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（√）6.由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）7.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（√）8.在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。（×）9.含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（×）10.具有n个叶子结点的哈夫曼树共有2n-1个结点。（√）二、填空题1.在树中，一个结点所拥有的子树数称为该结点的度。2.度为零的结点称为叶（或叶子，或终端）结点。3.树中结点的最大层次称为树的深度（或高度）。4.对于二叉树来说，第i层上至多有2i-1个结点。5.深度为h的二叉树至多有2h-1个结点。6.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。7.有20个结点的完全二叉树，编号为10的结点的父结点的编号是5。8.哈夫曼树是带权路径长度的最小的二叉树。9.由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。10.某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为DABEC。11.设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H。12.已知完全二叉树的第8层有8个结点，则其叶结点数是68。13.由树转换二叉树时，其根结点无右子树。14.采用二叉链表存储的n个结点的二叉树，一共有2n个指针域。15.采用二叉链表存储的n个结点的二叉树，共有空指针n+1个。16.前序为A，B，C且后序C，B，A的二叉树共有4种。17.三个结点可以组成2种不同形态的树。18.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i。19.给定如图7-36所示的二叉树，其前序遍历序列为：ABEFHCG。20.给定如图7-37所示的二叉树，其层次遍历序列为：ABCEFGH。AABCBCEFG图7-36二叉树1EFG图7-37二叉树2HDHD三、选择题1.树最适合用来表示（D）。A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间有分支的层次关系2.前序为A，B，C的二叉树共有（D）种。A.2B.3C.4D.53.根据二叉树的定义，具有3个结点的二叉树有（C）种树型。A.3B.4C.5D.64.在一棵具有五层的满二叉树中，结点的点数为（B）。A.16B.31C.32D.335.具有64个结点的完全二叉树的深度为（C）。A.5B.6C.7D.86.任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对7.A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。A.A和B右方B.A是B祖先C.A和B左方D.A是B子孙8.下列4棵树中，（B）不是完全二叉树。A．AB.AC.AD.ABCBCBCBCDEHDGDEFDED9.如图7-38所示的二叉树，后序遍历的序列是（D）。A.ABCDEFGHIAB.ABDHIECFG图7-38二叉树3C.HDIBEAFCGBCD.HIDEBFGCADEFGHI10.对于图7-39所示的二叉树，其中序序序列为（A）。A．DBEHAFCGB.DBHEAFCGC.ABDEHCFGD.ABCDEFGHABCDEFG图7-39二叉树4H11.某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为（D）。A.ACBEDB.DECABC.DEABCD.CEDBA12.具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是（D）。A.2iB.2i+1C.2i-1D.不存在13.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子14.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。A.46B.47C.90D.9115.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A.98B.99C.50D.10016.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。A.正确B.错误C.不确定D.都有可能17.下列陈述正确的是（D）。A.二叉树是度为为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树必有度为2的结点D.二叉树中最多只有两棵子树，且有左右子树之分18.用5个权值{3，2，4，5，1}构造的哈夫曼树的带权路径长度是（B）。A.32B.33C.34D.1519.在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。A.3B.4C.5D.620.二叉树的叶结点个数比度为2的结点的个数（C）。21.A.无关B.相等C.多一个D.少一个第8章图一、判断题1.图可以没有边，但不能没有顶点。（√）2.在无向图中，(v1，v2)与（v2，v1）是两条不同的边。（×）3.邻接表只能用于有向图的存储。（×）4.一个图的邻接矩阵表示是唯一的。（√）5.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（×）6.有向图不能进行广度优先遍历。（×）7.若一个无向图以顶点v1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（√）8.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（√）9.用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（×）10.若从一个无向图中任一顶占出发，进行了一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。（√）二、填空题1.图常用的存储方式有邻接矩阵和邻接表等。2.图的遍历有：深度优先搜和广度优先搜等方法。3.有n条边的无向图邻接矩阵中，1的个数是2n。4.有向图的边也称为弧。5.图的邻接矩阵表示法是表示顶点之间相邻关系的矩阵。6.有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度。7.n个顶占e条边的图若采用邻接矩阵存储，则空间复杂度为：On2。8.n个顶占e条边的图若采用邻接表存储，则空间复杂度为：O(n+e)。9.设有一稀疏图G，则G采用邻接表存储比较节省空间。10.设有一稠密图G，则G采用邻接矩阵存储比较节省空间。11.图的逆邻接表存储结构只适用于有向图。12.n个顶点的完全无向图有n(n-1)/2条边。13.有向图的邻接矩阵表表示适于求顶点的出度。14.有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点vi的入度。15.对于具有n个顶点的图，其生成树有且仅有n-1条边。16.对有n个顶点，e条弧的有向图，其邻接表表示中，需要n+e个结点。17.从图中某一顶点出发，访遍历图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。18.无向图的邻接矩阵一定是对称矩阵。19.一个连通网的最小生成树是该图所有生成树中权最小的生成树。20.若要求一个稠密图G的最小生成树，最好用Prim算法来求解。三、选择题1.在一个图中，所有顶点的度数之和等于图的边数的（C）倍。A.1/2B.1C.2D.42.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。A.1/2B.1C.2D.43.对于一个具有n个顶点的有向图的边数最多有（B）。A.nB.n(n-1)C.n(n-1)/2D.2n4.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。A.nB.n+1C.n-1D.n/25.有8个结点的有向完全图有（C）条边。A.14B.28C.56D.1126.深度优先遍历类似于二叉树的（A）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历7.广度优先遍历类似于二叉树的（D）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历8.任何一个无向连通图的最小生成树（A）。A.只有一棵B.一棵或多棵C.一定有多棵D.可以不存在9.无向图顶点v的度是关联于该顶点B）的数目。A.顶点B.边C.序号D.下标10.有n个顶点的无向图的邻接矩阵是用（B）数组存储。A.一维B.n行n列C.任意行n列D.n行任意列11.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。A.n-1B.n+1C.nD.n+e12.在图的表示法中，表示形式唯一的是（A）。A.邻接矩阵表示法B.邻接表表示法C.逆邻接表表示法D.邻接表和逆邻接表表示法13.在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。A.nB.eC.2nD.2ev11aav2v323bcbceev4v545dfdf图8-23度为3的结点图8-24（15）题图8-25从顶点a出发图8-26优先遍历14.图8-23中，度为3的结点是（B）。A.V1B.V2C.V3D.V415.图8-24是（A）。A.连通图B.强连通图C.生成树D.无环图16.如图8-25所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b17.如图8-26所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,e,b,c,f,dD.a,e,d,f,c,b18.最小生成树的构造可使用（A）算法。A.Prim算法B.卡尔算法C.哈夫曼算法D.迪杰斯特拉算法19.下面关于图的存储结构的叙述中正确的是（A）。A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C.用邻接存储图，占用空间大小只与图中顶点数有关，而与边数无关D.用邻接存储图，占用空间大小只与图中边数有关，而与顶点数无关20.连通分量是（C）的极大连通子图。A.树B.图C.无向图D.有向图第9章查找一、判断题1.二分查找法要求待查表的关键字值必须有序。（√）2.对有序表而言采用二分查找总比采用顺序查找法速度快。（×）3.在二叉排序树中，根结点的值都小于孩子的结点的值。（×）4.散列存储法的基本思想是由关键字的值的决定数据的存储地址。（√）5.哈希表是一种将关键字转换为存储地址的存储方法。（√）6.选择好的哈希函数就可以避免冲突的发生。（×）7.在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（×）8.采用分块查找，既有实现线性表所希望的查找速度，又能适应动态变化的需要。（√）9.哈希查找的效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（√）10.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。（×）二、填空题1.顺序查找法，表中元素可以任意存放。2.在分块查找方法中，首先查找索引，然后再查找相应的块。3.顺序查找、二分查找、分块查找都属于静态查找。4.静态查找表所含元素个数在查找阶段是固定不变的。5.对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n)。6.对于长度为n的线性表，若采用二分查找，则时间复杂度为O(log2n)。7.理想情况下，在散列表中查找一个元素的时间复杂度为：O(1)。8.在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较4次才找到。9.设有100个元素，用二分查找法查找时，最大的比较次数是7次。10.对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点值小，则继续在左子树中查找。11.二叉排序树是一种动态查找表。12.哈希表是按散列存储方式构造的存储结构。13.哈希法既是一种存储方法，又是一种查找方法。14.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。15.设散列函数H和键值k1，k2，若k1≠k2，而H（k2）H（k2），则称这种现象为冲突。16.处理冲突的两类主要方法是开放定地址法和拉链法（或链地址法）。17.散列表（或散列）查找法的平均查找长度与元素个数n无关。18.在哈希函数H（key）=key%P中，P一般应取质数。19.在查找过程中有插入元素或删除元素操作的，称为动态查找。20.各结点左、右子树深度之差的绝对值至多为1的二叉树称为平衡二叉树。三、选择题1.查找表以（A）为查找结构。A.集合B.图C.树D.文件2.顺序查找法适合于存储结构为（B）的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储3.在表长为n的链表中进行线性查找，它的平均查找长度为（B）。A.ASL=nB.ASL=(n+1)/2C.ASL=+1D.ASL≈log2
浙公网安备 33021202002483