[数据结构与算法] 数据结构题目收录（四）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构题目收录（四） -> 正文阅读

[数据结构与算法]数据结构题目收录（四）

1、已知表头元素为c的单链表在内存中的存储状态如下表所示。现将f存放于1014H处并插入单链表，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。

在这里插入图片描述

A：1010H，1014H，1004H
B：1010H，1004H，1014H
C：1014H，1010H，1004H
D：1014H，1004H，1010H

解析

答案：D

2、已知头指针h指向一个带头结点的非空单循环链表，结点结构为下图，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是（）。

在这里插入图片描述

A：h->next = h->next->next; q=h->next;free(q);
B：q=h->next;h->next=h->next->next;free(q);
C：q=h->next;h->next=q->next;if(p!=q)p=h;free(q);
D：q=h->next;h->next=q->next;if(p==q)p=h;free(q);

解析

在这里插入图片描述
如图1所示，要删除带头结点的非空单循环链表中的第一个元素，就要先用临时指针q指向待删结点，q=h->next；然后将q从链表中断开，h->next=q->next（这一步也可写成h->next=h->next->next）；此时要考虑一种特殊情况，若待删结点是链表的尾结点，即循环单链表中只有一个元素（p和q指向同一个结点），如图2所示，则在删除后要将尾指针指向头结点，即if(p==q)p=h;最后释放q结点即可。

答案：D

3、栈和队列具有相同的（）。

A：抽象数据类型
B：逻辑结构
C：存储结构
D：运算

解析

栈和队列的逻辑结构都是相同的，都属于线性结构，只是它们对数据的运算不同。

答案：B

4、设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（）。

A：只有表头结点指针，没有表尾指针的双向循环链表
B：只有表尾结点指针，没有表头指针的双向循环链表
C：只有表头结点指针，没有表尾指针的单向循环链表
D：只有表尾结点指针，没有表头指针的单向循环链表

解析

对于双向循环链表，不管是表头指针还是表尾指针，都可以很方便地找到表头结点，方便在表头做插入或删除操作。而单循环链表通过尾指针可以很方便地找到头结点，但通过头指针找尾结点则需要遍历一次链表。对于C，插入和删除结点后，找尾结点需要花费O(n)的时间。

答案：C

5、向一个栈顶指针为top的链栈（不带头结点）中插入一个x结点，则执行（）。

A：top->next=x;
B：x->next=top->next; top->next=x
C：x->next=top; top=x
D：x->next=top;top=top->next

解析

链表采用不带头结点的单链表表示时，进栈操作在首部插入一个结点x(即x->next=top)，插入完后需将top指向该插入的结点x。

答案：C

6、一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A：i-j-1
B：i-j
C：j-i+1
D：不确定

解析

当第i个元素第一个出栈时，则i之前的元素可以依次排在i之后出栈，但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈，所以第j个出栈的元素是不确定的。

答案：D

7、已知一个栈的入栈序列是1,2,3,4，其出栈序列为 $P_1$ , $P_2$ , $P_3$ , $P_4$ ，则 $P_2$ , $P_4$ 不可能是（）。

A：2，4
B：2，1
C：4，3
D：3，4

解析

逐个判断每个选项可能的入栈出栈顺序。

答案：C

8、一个栈的入栈序列为1,2,3,…,n，出栈序列是 $P_1$ , $P_2$ , $P_3$ ,…, $P_n$ 。若 $P_2$ =3，则 $P_3$ 可能取值的个数是（）。

A：n-3
B：n-2
C：n-1
D：无法确定

解析

3之后的4,5…,n都是 $P_3$ 可取的数（持续进栈直到该数入栈后立即出栈）。接下来分析1和2： $P_1$ 可以是3之前入栈的数（可能是1或2），也可以是4，当 $P_1$ =1时， $P_3$ 可取2；当 $P_1$ =2时， $P_3$ 可取1；当 $P_1$ =4时， $P_3$ 可取除1，3，4之外的所有数；故 $P_3$ 可能取值的个数为n-1。