#M9013. 线性表
线性表
- 元素入栈的顺序为。如果第1个出栈的是,那么第5个出栈的不可能是? {{ select(1) }}
- R1
- R2
- R4
- R5
- 双向链表中有两个指针域llink和rlink,分别指向该结点的前驱及后继。设p指向链表中的一个结点,它的左右结点均非空。现要求删除结点p,则下面语句序列中错误的是? {{ select(2) }}
- p->rlink->llink = p->rlink; p->llink->rlink = p->llink; delete p;
- p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
- p->rlink->llink = p->llink; p->rlink->llink->rlink = p->rlink; delete p;
- p->llink->rlink = p->rlink; p->llink->rlink->llink = p->llink; delete p;
- 填空题
队列快照是指在某一时刻队列中的元素组成的有序序列。例如,当元素1、2、3入队,元素1出队后,此刻的队列快照是"2 3"。当元素2、3也出队后,队列快照是"",即为空。现有3个正整数元素依次入队、出队。已知它们的和为8,则共有_________种可能的不同的队列快照(不同队列的相同快照只计一次)。例如,"5 2 1"、"4 2 2"、""都是可能的队列快照;而"7"不是可能的队列快照,因为剩下的2个正整数的和不可能是1。
{{ input(3) }}
- 在含有n个元素的双向链表中查询是否存在关键字为k的元素,最坏情况下运行的时间复杂度是? {{ select(4) }}
- ()是一种先进先出的线性表? {{ select(5) }}
- 栈
- 队列
- 哈希表(散列表)
- 二叉树
- 如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a,b,c,另有元素d已经出栈,则可能的入栈顺序是? {{ select(6) }}
- a, d, c, b
- b, a, c, d
- a, c, b, d
- d, a, b, c
- 下图中所使用的数据结构是?
{{ select(7) }}
- 哈希表
- 栈
- 队列
- 二叉树
- 链表不具备的特点是? {{ select(8) }}
- 可随机访问任何一个元素
- 插入、删除操作不需要移动元素
- 无需事物估计存储空间大小
- 所需存储空间与存储元素个数成正比
- 线性表若采用链表存储结构,要求内存中可用存储单元地址? {{ select(9) }}
- 必须连续
- 部分地址必须连续
- 一定不连续
- 连续不连续均可
- 今有一空栈 S,对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈,进栈,出栈,进栈, 进栈,出栈的操作,则此操作完成后,栈 S 的栈顶元素为? {{ select(10) }}
- f
- c
- a
- b
- 对于入栈顺序为 a,b,c,d,e,f,g 的序列,下列( )不可能是合法的出栈序列? {{ select(11) }}
- a, b, c, d, e, f, g
- a, d, c, b, e, g, f
- a, d, b, c, g, f, e
- g, f, e, d, c, b, a
- 有 6 个元素,按照 6、5、4、3、2、1 的顺序进入栈 S,请问下列哪个出栈序列是非法的? {{ select(12) }}
- 5 4 3 6 1 2
- 4 5 3 1 2 6
- 3 4 6 5 2 1
- 2 3 4 1 5 6
- 链表和数组的区别包括? {{ select(13) }}
- 数组不能排序,链表可以
- 链表比数组能存储更多的信息
- 数组大小固定,链表大小可动态调整
- 以上均正确
- 假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据,每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作,不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈,队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是( )个数据? {{ select(14) }}
- 2
- 3
- 4
- 6
- 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果(其中,next 域为结点的直接后继,prev 域为结点的直接前驱)? {{ select(15) }}
- p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
- p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
- s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
- s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
- 假设有一个链表的节点定义如下:
现在有一个指向链表头部的指针:Node* head。如果想要在链表中插入一个新节点,其成员data的值为42,并使新节点成为链表的第一个节点,下面哪个操作是正确的?
{{ select(16) }}
- Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
- Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
- Node* newNode = new Node; newNode->data = 42; head->next = newNode;
- Node* newNode = new Node; newNode->data = 42; newNode->next = head;