Question

数据结构题目

数据采用链式存储结构时，要求（)。A.每个节点占用一片连续的存储区域B.所有节点占用一片连续的
数据采用链式存储结构时，要求()。
A.每个节点占用一片连续的存储区域
B.所有节点占用一片连续的存储区域
C.节点的最后一个域必须是指针域
D.每个节点有多少后继节点，就必须设多少个指针域

Answer 1

选A
每个结点占用一片连续的存储区域。

链式存储结构不需要所有结点占用一片连续的存储区域，结点之间用指针相链接。
顺序存储才是需要所有结点都有一片连续的存储区域的。
但是无论是顺序存储还是链式存储，每个结点都要占用一片连续的存储区域。
结点的结构是

前驱指针—数据域—后继指针

注：首结点没有前驱，最后一个结点没有后继。
由此可得——cd错误.

Answer 2

用一个栈搞定。顺序逐字符扫描表达式，遇到（、[、{，入栈，遇到）、]、}，查看栈顶元素是否为对应的左符号，是则将栈顶符号出栈，然后继续判定，否则报错；最后看栈是否为空，空则正确，否则报错。

Answer 3

(1)B
删第一个结点，时间复杂度分别为O(1)和O(n)
两个链表用相同类型变量，占相同大小空间
(2)C
第h层和第h-1层都有可能有叶子结点
第h-1层有可能存在度为1的结点
(3)A
参照B树的插入算法
(4)C
q是p的前驱结点
(5)B
(6)C
(7)D
Tail(A)=((d,e,f))
Head(Tail(A))=(d,e,f)
Tail(Head(Tail(A)))=(e,f)
(8)A
(9)D
前面三个不一定是生成树
(10)C
过程很复杂
(11)B
关键是建立起Huffman树