2. 从业资格
  3. 若栈采用链式存储且仅设头指针，则( )时入栈和出栈操作最方便。A.采用不含头结点

若栈采用链式存储且仅设头指针，则( )时入栈和出栈操作最方便。A.采用不含头结点

考试题库2022-08-02  72
问题 若栈采用链式存储且仅设头指针，则( )时入栈和出栈操作最方便。A.采用不含头结点的单链表且栈顶元素放在表尾结点B.采用不含头结点的单链表且栈顶元素放在表头结点C.采用含头结点的单循环链表且栈顶元素随机存放在链表的任意结点D.采用含头结点的双向链表且栈顶元素放在表尾结点
选项 A.采用不含头结点的单链表且栈顶元素放在表尾结点
B.采用不含头结点的单链表且栈顶元素放在表头结点
C.采用含头结点的单循环链表且栈顶元素随机存放在链表的任意结点
D.采用含头结点的双向链表且栈顶元素放在表尾结点
答案 B
解析 本题考查数据结构基础知识。栈的操作要求是后进先出，而且仅在表尾一端加入和删除元素。对单链表进行操作时，必须从头指针出发。根据栈的操作要求，单循环链表和双向链表都是没有必要的，而且选项c中将栈顶元素任意存放是错误的。可以采用单链表作为栈的存储结构，将表头作为栈顶来使用。含头结点的单链表如下图所示，其中La为头指针，La指向的结点为头结点。不含头结点且栈顶元素放在表尾结点的单链表如下图所示，其中La为头指针，La指向的结点存储了先进入栈且没有出栈的元素。显然，因为要从La出发遍历至表尾才能进行入栈和出栈操作，在这种情况下出栈和入栈都是最低效的，时间复杂度都是O(n)。如果采用不含头结点且栈顶元素放在表头的单链表，如下图所示，出栈和入栈操作都在表头，时间复杂度都为O(1)。
转载请注明原文地址:https://tihaiku.com/congyezige/2425072.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)