循环链表是线性表的一种存储方式。

此题为判断题(对，错)。

A、顺序表

B、单链表

C、单循环链表

D、双向链表

A．线性表存储空间已满的情况下，继续插入的错误运算称为“上溢”

B．在线性表的第一个位置处插入新元素，不需要移动线性表中的所有元素

C．在线性表的末尾插入新元素，需要移动线性表中的所有元素

D．线性表的插入运算的时间主要花费在元素的插入上

A、将n个元素从小到大排序

B、从线性表中删除第i个元素(1≤i≤n)

C、查找第i个元素(1≤i≤n)

D、在第i个元素(1≤i≤n)后插人一个新元素

在以下有关静态链表的叙述中错误的是()。

(1)静态链表既有顺序存储的优点，又有链接存储的优点。所以，它存取表中第i个元素的时间与i无关

(2)静态链表中可容纳元素个数的最大数目在定义时就确定了，以后不能增加

(3)静态链表与动态链表在元素的插人、删除上类似，不需做元素的移动

A、(1)、(2)

B、(1)

C、(1)、(2)、(3)

D、(2)

设a和b是两个用带有附加头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c=a×b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m，试说明该算法的执行时间为O(nm²)或O(nm²)。试说明若a和b是稠密的，即其很少有系数为零的项，那么该乘积算法的时间代价为O(nm)，

设一棵二叉树的存储表示是二叉链表，编写一个用逆转链方法实现二叉树前序遍历的算法。这个方法的思想是在遍历过程中沿着结点的左子女或右子女方向“下降”时，临时改变其leftChild或rightChild的值，使之指向该结点的父结点，从商为以后的“上升”提供路径;在上升的过程中将结点的leftChild或rightChild的值恢复原来的值。为了在上升的过程中区分是从该结点的左子树上升的还是从右子树上升的，在结点中设置一个tag标志。进人算法时，所有结点的tag设为0，当遍历过程中进入结点的左子树时，将该结点的tag置为l、从左子树退出进人右子树时再将该结点的tag置为0.

设一棵二义树的存储表示是二叉链表、编写一个用Robson方法实现二叉树后序遍历的算法。Robson方法遍历二叉树的特点如下：

(1)沿袭5-60题使用逆转链遍历二叉树的思想。

(2)不使用tag标志，而是用内嵌的栈代替tag的作用。该内嵌的栈使用了叶结点作为栈的结构，没有另外定义栈的存储空间。

(3)利用栈解决在回溯时分辨究竟是从左子树还是右子树上升的问题，步骤是：

①当进入有非空左子树的结点的右子树时，将该结点的地址进栈。

②在回溯过程中如遇到结点的左、布子树都非空时，如果该结点就是存于栈顶的结点，则可判定当前是从该结点的右子树退回，该结点的右子女指针指向它的父结点;否则当前是从该结点的左子树退回，该结点的左子女指向它的父结点。