在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _。答案: O(n)

在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _。

答案: O(n)

本门课程完整答案：点击这里，查看数据结构 (华中科技大学) 中国大学mooc答案满分完整版章节测验 m106314

相关试题

将长度为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次；

答案: 错误

栈是一种对进栈、出栈操作总次数做了限制的线性表。

答案: 错误

栈是一种对进栈、出栈操作的次序做了限制的线性表。

答案: 错误

对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。

答案: 正确

空栈没有栈顶指针。

答案: 错误

栈和队列都是限制存取端的。

答案: 正确

队列是一种对进队、出队操作的次序做了限制的线性表。

答案: 错误

若用“队首指针的值和队尾指针的值相等”作为循环顺序队为空的标识，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，在顺序表地址范围内不管什么值都可以。

答案: 正确

在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _。 答案: O(n)

第三章 栈和队列 第三章栈和队列单元测试

在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _。

答案: O(n)

第三章栈和队列第三章栈和队列单元测试