j--; return (i);
5. fact(n)
{ if(n<=1)
return (1);
else
return (n*fact(n-1)); }
习题2 顺序表和链表 一、单项选择题
1. 线性表是________。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空
2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 个元素。
A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以
4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较____个元素结点。
A．n/2 B．n C．（n+1）/2 D．（n-1）/2
5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。
A． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。
A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;
7. 在一个长度为n的顺序表中向第i个元素(0< i A．n-i B．n-i+l C．n-i-1 D．i 8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行 A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q 9. 以下关于线性表的说法不正确的是______。 A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。 C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种_______的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 11. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小 12. 在等概率情况下，顺序表的插入操作要移动______结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在______运算中，使用顺序表比链表好。 A．插入 B．删除 C．根据序号查找 D．根据元素值查找 14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 A．O(1) B．O(n) C．O(n2) D．O(log2n) 15 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 16 下面关于线性表的叙述错误的是（ ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 17 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 (A) head==0 (B) head->next==0 (D) head!=0 (C) head->next==head 18 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 19 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。 (A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s； 20 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。 (A) 单向链表 (C) 双向链表 (B) 单向循环链表 (D) 双向循环链表 21 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。 (A) s->next=p->next；p->next=-s； (C) p->next=s->next；s->next=p； (B) q->next=s； s->next=p； (D) p->next=s；s->next=q； 22 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 (A) head==0 (C) head->next==head (B) head->next==0 (D) head!=0 23建立一个长度为n的有序单链表的时间复杂度为（ ） (A) O(n) 1．线性表中的所有元素都有一个前驱元素和后继元素。（F ） 2．线性表的顺序存储结构比链式存储结构更好。（ F ） 顺序表查找指的是在顺序存储结构上进行查找。（ F ） 对链表进行插入和删除操作时不必移动链表中结点。( T ) 非空的双向循环链表中任何结点的前驱指针均不为空。（ T ） (B) O(1) (C) O(n2) (D) O(log2n)