设输入元素为1、2、3、P和A，入栈次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可

(1)【◆题库问题◆】：[问答题] 设输入元素为1、2、3、P和A，入栈次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？

【◆参考答案◆】：
一般说，高级语言的变量名是以字母开头的字母数字序列。
故答案是：AP321，PA321，P3A21，P32A1，P321A。

(2)【◆题库问题◆】：[单选] 表达式a*（b+c）-d的后缀表达式是（）。
A．abcd+-
B．abc+*d-
C．abc*+d-
D．-+*abcd

【◆参考答案◆】：B

(3)【◆题库问题◆】：[判断题] 链表的每个结点中都恰好包含一个指针。
A．正确
B．错误

【◆参考答案◆】：正确

【◆答案解析◆】：链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

(4)【◆题库问题◆】：[单选] 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序

【◆参考答案◆】：A

(5)【◆题库问题◆】：[判断题] 凡是递归定义的数据结构都可以用递归算法来实现它的操作。
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[判断题] 一个无向连通图的生成树是图的极小的连通子图。
A．正确
B．错误

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[问答题] 有5个元素，其进栈次序为A．B．C．D．E，在各种可能的出栈次序中，以元素C．D最先出栈（即C第一个且D第一个出栈）的次序有哪几个？

【◆参考答案◆】：三个：CDEBA，CDBEA，CDBAE

(8)【◆题库问题◆】：[名词解释] 装填因子

【◆参考答案◆】：
是哈希表中填入的记录数和哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模的函数。（散列表的查找效率取决于三个因素：散列函数/处理冲突的方法和装填因子）

(9)【◆题库问题◆】：[单选] 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。
A．"Nanjing＆Shanghai"
B．"Nanjing＆Nanjing"
C．"ShanghaiNanjing"
D．"Shanghai＆Nanjing"

【◆参考答案◆】：D

(10)【◆题库问题◆】：[填空题] 求子串在主串中首次出现的位置的运算称为（）。

【◆参考答案◆】：模式匹配