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，其出栈序列为
,
,
,
，则,不可能是（）。
- A：2，4
- B：2，1
- C：4，3
- D：3，4
解析
逐个判断每个选项可能的入栈出栈顺序。
答案：C
8、一个栈的入栈序列为1,2,3,...,n，出栈序列是,,,...,
。若=3，则可能取值的个数是（）。
- A：n-3
- B：n-2
- C：n-1
- D：无法确定
解析
3之后的4,5...,n都是可取的数（持续进栈直到该数入栈后立即出栈）。接下来分析1和2：
可以是3之前入栈的数（可能是1或2），也可以是4，当
=1时，
可取2；当
=2时，
可取1；当
=4时，
可取除1，3，4之外的所有数；故
可能取值的个数为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：Ⅳ
解析
队列“先进先出”的特性表现在：先进队列的元素先出队列，后进队列的元素后出队列，进队列对应的是插入操作，出队列对应的是删除操作。Ⅰ和Ⅳ均正确。
