数据结构 (华中科技大学) 中国大学mooc慕课答案满分完整版章节测试

第一章 绪论 第一章绪论单元测试    ______ 是数据的最小单位。答案: 数据项    以下说法不正确的是 ______。答案: 数据项可由若干个数据元素构成    数据结构是指 ______ 的集合以及它们之间的关系。答案: 数据元素    计算机所处理的数据一般具备某种内在联系，这是指 ______。答案: 元素和元素之间存在某种关系    在数据结构中，与所使用的计算机无关的是数据的 ______ 结构。答案: 逻辑    数据的逻辑结构可以分为 ______ 两类。答案: 线性结构和非线性结构    数据的逻辑结构是指 ______ 关系的整体。答案: 数据元素之间逻辑    以下是数据结构中 ______ 属非线性结构。答案: 平衡二叉树    以下属于逻辑结构是 ______。答案: 有序表    以下不属于存储结构是 ______。答案: 线性表    在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。答案: 数据元素之间的关系    数据结构在计算机内存中的表示是指 ______。答案: 数据的存储结构    在数据的存储中，一个节点通常存储一个 ______。答案: 数据元素    在决定选取任何类型的存储结构时，一般不多考虑 ______。答案: 各节点的值如何    数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。答案: 顺序存储结构    数据采用链式存储结构时，要求 ______。答案: 每个节点占用一片连续的存储区域    数据的运算 ______。答案: 与采用何种存储结构有关    _ 不是算法的基本特性。答案: 在规定的时间内完成    计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、_。答案: 可行性、有穷性和确定性    一个算法具有 __ 等设计目标。答案: 健壮性    以下关于算法的说法正确的是 ______。答案: 其他几个都是错误的    算法的时间复杂度与 _ 有关。答案: 问题规模    算法分析的主要任务之一是分析 _。答案: 算法的执行时间和问题规模之间的关系    算法的时间复杂度为O(n2)，表明该算法的 _。答案: 执行时间与成正比    算法分析的目的是 _。答案: 分析算法的效率以求改进    以下函数中时间复杂度最小的是 _。答案: T4(n)=20000log2n    以下函数中时间复杂度最小的是 _。答案: T1(n)=1000log2n    以下说法中错误的是 _。（1）原地工作算法的含义是指不需要任何额外的辅助空间（2）在相同的问题规模下n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法（3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限（4）一个算法的时间复杂度与实现算法的语言无关答案: （1）、（2）    以下数据结构中哪一个是非线性结构？答案: 二叉树    下面程序的时间复杂为 _。for（i=1，s=0； i    取算法的时间复杂度为O（），当n=5时执行时间为50s，当n=15时，执行时间为_。答案: 1350    下面程序的时间复杂度为 _。void fun( int n) { int i=1; while (i    下面程序的时间复杂度为 _。void fun( int n) { int i=1; while (i    下面程序的时间复杂度为 _。void fun( int n) { int i=1, k=100; while (i    数据元素是数据的最小单位。答案: 错误    数据对象就是一组任意数据元素的集合。答案: 错误    任何数据结构都具备3个基本运算：插入、删除、和查找。答案: 错误    数据的逻辑结构与数据元素在计算机中如何存储有关。答案: 错误    如果数据元素值发生改变，则数据的逻辑结构也随之改变。答案: 错误    逻辑结构相同的数据，可以采用多种不同的存储方法。答案: 正确    逻辑结构不相同的数据，必须采用多种不同的存储方法。答案: 错误    逻辑结构相同的数据，在设计存储结构时，它们的节点类型也一定相同。答案: 错误    数据的逻辑结构时指数据的各数据项之间的逻辑关系。答案: 错误    算法的优劣与算法描述语言无关，但与所用的计算机有关。答案: 错误    算法可以用不同的语言描述，如果用C或PASCAL语言等高级语言来描述，则算法实际上就是程序了。答案: 错误    程序一定是算法。答案: 错误    算法最终必须由计算机程序实现.答案: 错误    算法的可行性是指指令不能有二义性。答案: 错误    健壮的算法不会因非法输入数据而出现莫名其妙的状态。答案: 正确第二章 线性表 第二章线性表单元测试    线性表是具有n个 ______ 的有限序列。答案: 数据元素    线性表是 _。答案: 一个有限序列，可以为空    关于线性表的正确说法是 _。答案: 除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素    线性表采用链表存储时，其存放各个元素的单元地址是 _。答案: 连续与否均可以    链表不具备的特点是 _。答案: 可随机访问任一节点    线性表的静态链表存储结构与顺序存储结构相比，优点是 _。答案: 便于插入和删除    线性表的顺序存储结构和链式存储结构相比，优点是 _。答案: 便于随机存取    设线性表有n个元素，以下操作中，_在顺序表上实现比在链表上实现效率高。答案: 输入第i（1    对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用 _ 存储结构。答案: 链式    设线性表中有n个元素，以下操作，_ 在单链表上实现要比在顺序表上实现效率高。答案: 删除指定位置元素的后一个元素    以下属于顺序表的优点是 _。答案: 存储密度大    要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是 _。答案: 静态链表    如果最常用的操作时取第i个元素及前驱元素，则采用 _ 存储方式最节省时间。答案: 顺序表    与单链表相比，双链表的优点之一是 _。答案: 访问前后相邻节点更方便    在长度为n的顺序表中插入一个元素的时间复杂度为 _。答案: O(n)    在长度为n的顺序表中删除一个元素的时间复杂度为 _。答案: O(n)    在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为_。答案: n    将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_。（MIN表示取最小值）答案: MIN(m, n)    在带头节点的单链表L为空的判定条件是 _。答案: L->NEXT==NULL    对于一个具有n个元素的线性表，建立其单链表的时间复杂度为 _。答案: O(n)    在单链表中查找指定值的节点的时间复杂度是 _。答案: O(n)    以下关于单链表的叙述中，不正确的是 _。答案: 可以通过头节点直接计算第i个节点的存储地址    在单链表中，增加一个头节点的目的是为了 _。答案: 方便运算的实现    在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _。答案: O(n)    将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 _。答案: O(n)    已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _。答案: 找最小值节点的算法的时间复杂度为 O(1)    在一个长度为n（n>1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行_操作与链表的长度有关。答案: 删除单链表的尾节点    在一个双链表中，在p节点之后插入节点q的操作是 _。答案: q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；    在一个双链表中，在p节点之前插入节点q的操作是 _。答案: p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；    在一个双链表中， 删除*p节点的操作是 _。答案: p -> prior –>next= p-> next；p ->next-> prior = p -> prior；    在一个双链表中， 删除*p节点之后的一个节点，其时间复杂度为_。答案: O(1)    非空的循环单链表L的尾节点（由p所指向）满足 _。答案: p -> next == L    带表头结点的双循环链表L为空表的条件是 _。答案: L -> next == L    某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用 _ 存储方式最节省运算时间。答案: 循环双链表    如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用_。答案: 只有开始数据节点指针没有尾节点指针的循环双链表    在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采用_ 存储方式最节省时间。答案: 仅有尾指针的循环单链表    两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则 _。答案: 对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)    在长度为n的 _ 上，删除第一个元素，其算法的时间复杂度为O(n)。答案: 只有表头指针的不带表头节点的循环单链表    下面关于线性表的叙述错误的是 _。答案: 线性表采用顺序存储便于插入和删除操作的实现    对于双链表，在两个节点之间插入一个新节点是，需要修改 _ 个指针域。答案: 4    在单链表中，要删除某一指定的节点，必须找到该节点的 _ 节点。答案: 前驱    求一个单链表长度的算法的时间复杂度为 _。答案: O(n)    线性表中每个元素都有一个前驱元素和一个后继元素。答案: 错误    线性表中所有元素的排列顺序必须从小到大或从大到小。答案: 错误    静态链表既有顺序存储结构的优点，又有动态链表的优点，所以，利用它存取第i个元素的时间与元素个数n无关。答案: 错误    静态链表与动态链表在元素的插入、删除方面类似，不需要做元素的移动。答案: 正确    线性表的顺序存储结构优于链式存储结构。答案: 错误    在循环单链表中，从表中任一节点出发都可以通过前后移动操作遍历整个循环链表。答案: 错误    在单链表中，可以从头节点开始查找任何一个节点。答案: 正确    在双链表中，可以从任一节点开始沿着同一方向查找到任何其他节点。答案: 错误第三章 栈和队列 第三章栈和队列单元测试    元素A、B、C、D依次进栈后，栈顶元素是 _。答案: D    经过以下运算后， x的值是 _。InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x)答案: a    经过以下栈运算后，StackEmpty(s)的值是 _。InitStack (s); Push(s, a); Push(s, b); Pop(s, x); Pop(s,y)答案: 1    已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是 _。答案: push, push, push, pop, pop, pop    若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是 _。答案: afedcb    设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是_。答案: DABC    一个栈的进栈序列是abcde，则栈的不可能的输出序列是 _。答案: dceab    已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_。答案: 不确定    已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_。答案: n-i 1    设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若pn=1，则pi（1≤i≤n-1）的值是_。答案: n-i 1    设n个元素的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=3，则p2的值是_。答案: 不可能是1    设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=1，则p1的值是_。答案: 不可能是2    设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=3，则p1的值是_。答案: 可能是2    设有5个元素的进栈序列是a，b，c，d，e，其输出序列是c，e，d，b，a，则该栈的容量至少是 _。答案: 4    在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用_来保存这些数据。答案: 栈    判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为 _。答案: st.top==-1    判定一个顺序栈st为（元素个数最多为MaxSize）为栈满的条件为 _。答案: st.top==MaxSize-1    表达式a*(b c)-d的后缀表达式是 _。答案: a b c * d –    若一个栈用数组data[1..n]存储，初始栈顶指针top为n 1，则以下元素x进入栈的正确操作是 _。答案: top–; data[top]=x;    若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是 _。答案: data[top]=x;top–;    若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是 _。答案: top ; data[top]=x;    若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进入栈的正确操作是 _。答案: data[top]=x;top ;    链栈与顺序栈相比有一个明显的优点，即 _。答案: 通常不会出现栈满的情况    以下各链表均不带有头节点，其中最不合适用作链栈的链表是 _。答案: 只有表头指针没有表尾指针的循环单链表    如果以链表作为栈的存储结构，则退栈操作时 _。答案: 必须判断链栈是否空    向一个不带头节点的栈顶指针为lst的链栈中插入一个s所指向节点时，则执行 _。答案: s->next=lst; lst=s;    从一个不带头节点的栈顶指针为lst的栈链中删除一个节点时，用x保存被删节点的值，则执行 _。答案: x=lst->data; lst= lst->next;    栈和队列的不同点是 _。答案: 栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作    经过下列运算后，队头的元素是 _。InitQueue(qu); Enqueue(qu, ‘a’); EnQueue(qu, ‘b’); EnQueue(qu, ‘c’); DeQueue(qu);答案: b    若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变_。答案: rear    循环队列qu的队满条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是 _。答案: (qu.rear 1)%maxsize==qu.front    设循环队列中数组的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则元素个数为 _。答案: (r-f N)%N    最适合用做链队列的不带表头节点的链表是 _。答案: 只带尾节点指针的循环单链表    假设用一个不带表头节点的单链表表示队列，在进行删除操作时，_。答案: 头、尾指针可能都要修改    假设用一个不带头节点的单链表表示队列，队头和队尾指针分别为front和rear，则判断队空的条件是 _。答案: front == NULL    最不合适用做链队的不带头节点的链表是 _。答案: 只带队首节点指针的非循环单链表    假设用qu[0..M]实现循环队列，f、r分别为队首元素的前一个位置和队尾位置。若用“(r 1)%(M 1)==f”作为队满的标志，则 _。答案: 可用“f==r”作为队空的标志    若用一个大小为6的数组来实现循环队列，且当前rear 和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear 和front的值分别是_。答案: 2和4    栈底元素是不能删除的元素。答案: 错误    顺序栈中元素值的大小是有序的。答案: 错误    n个元素依次进栈，它们的出栈顺序和进栈顺序一定正好相反。答案: 错误    栈顶元素和栈底有可能是同一元素。答案: 正确    若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次；答案: 错误    栈是一种对进栈、出栈操作总次数做了限制的线性表。答案: 错误    栈是一种对进栈、出栈操作的次序做了限制的线性表。答案: 错误    对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。答案: 正确    空栈没有栈顶指针。答案: 错误    栈和队列都是限制存取端的。答案: 正确    队列是一种对进队、出队操作的次序做了限制的线性表。答案: 错误    若用“队首指针的值和队尾指针的值相等”作为循环顺序队为空的标识，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，在顺序表地址范围内不管什么值都可以。答案: 正确