单项选择题6. 若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾摊针的单向循环链表(不含头结点)时，______。
- A.插入和删除操作的时间复杂度都为O(1)
- B.插入和删除操作的时间复杂度都为O(n)
- C.插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
- D.插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
A B C D
C
[解析] 设尾指针的单项循环链表(不含头结点)如下图所示。
设结点的指针域为next，新结点的指针为s，则在尾指针所指结点后插入结点的操作如下：
S-＞next=t-＞next; t-＞next=S; t=s;也就是插入操作的时间复杂度为O(1)。
要删除尾指针所指结点，必须通过遍历操作找到尾结点的前驱结点，其操作序列如下：
if (t-＞next=t) free(t);
else {
p=t-＞next;
while (P-＞next!=t)
p=p-＞next;
P-＞next=t-＞next;
free(t);
t=p;
}
也就是说，删除操作的时间复杂度为O(n)。
F={元件号→元件名称，(元件号，供应商)→库存量，供应商→供应商所在地}
元件关系的主键为______，该关系存在冗余以及插入异常和删除异常等问题。为了解决这一问题需要将元件关系分解为______，分解后的关系模式可以达到______。 逻辑覆盖标准主要用于______。它主要包括条件覆盖、条件组合覆盖、判定覆盖、条件及判定覆盖、语句覆盖、路径覆盖等几种，其中除路径覆盖外最弱的覆盖标准是______。25. 以下关于二叉排序树(或二叉查找树、二叉检索树)的叙述中，正确的是______。
A．对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B．含有n个结点的二叉排序树高度为
C．从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点
D．从左到右排列同层次的结点，其关键字呈现有序排列的特点
A B C D
D
[解析]
本题考查数据结构基础知识。
二叉查找树又称为二叉排序树或二叉检索树，它或者是一棵空树，或者是具有如下性质的二叉树：①若它的左子树非空，则左子树中所有结点的值均小于根结点的值；②若它的右子树非空，则右子树中所有结点的值均大于根结点的值；③左、右子树本身就是二叉查找树。某二叉排序树如下图所示。
以上图为例，对非空二叉排序树进行中序遍历，得到递增有序的序列，先序和后序序列则不是。因此，选项A的说法是错误的。
二叉排序树中结点在左、右子树上的分布并不均匀，极端情况下，n个结点的二叉排序树的高度为n。因此，选项B的说法是错误的。
以上图为例，从46到25的路径上的结点关键码序列为46，13，38，25，并不是一个有序序列。因此，选项C的说法是错误的。
深色：已答题 浅色：未答题