数据结构题目收录（四）

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。

答案：C

9、下列关于栈的叙述中，错误的是（）。

Ⅰ. 采用非递归方式重写递归程序时必须使用栈
Ⅱ. 函数调用时，系统要用栈保存必要的信息
Ⅲ. 只要确定了入栈次序，即可确定出栈次序
Ⅳ. 栈是一种受限的线性表，允许在其两端进行操作

• A：仅Ⅰ
• B：仅Ⅰ、Ⅱ、Ⅲ
• C：仅Ⅰ、Ⅲ、Ⅳ
• D：仅Ⅱ、Ⅲ、Ⅳ

解析

Ⅰ的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。
Ⅲ的反例：入栈序列为1，2，进行Push，Push，Pop，Pop操作，出栈次序为2，1；进行Push，Pop，Push，Pop操作，出栈次序为1，2.
Ⅳ的反例：栈是一种受限的线性表，只允许在一端进行操作。

答案：C

10、队列的“先进先出”特性是指（）。

Ⅰ. 最后插入队列中的元素总是最后被删除
Ⅱ. 当同时进行插入、删除操作时，总是插入操作优先
Ⅲ. 每当有删除操作时，总要先做一次插入操作
Ⅳ. 每次从队列中删除的总是最早插入的元素

• A：Ⅰ
• B：Ⅰ和Ⅳ
• C：Ⅱ和Ⅲ
• D：Ⅳ

解析

队列“先进先出”的特性表现在：先进队列的元素先出队列，后进队列的元素后出队列，进队列对应的是插入操作，出队列对应的是删除操作。Ⅰ和Ⅳ均正确。

答案：B

学海无涯苦作舟