第二章
1. 线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接【 前驱 】外，其他结点有且仅有一个直接【前驱 】;除终端结点没有直接【 后继】外，其它结点有且仅有一个直接【后继 】。
2. 线性表的顺序存储结构是指用一组【 地址连续 】的存储单元依次存储线性表中的各个元素，逻辑上相邻的元素，其物理位置【连续 】_。链式存储结构中，逻辑上相邻的元素，其物理位置【 不一定连续】 。
3. 线性表的顺序存储结构中，逻辑上相邻的元素，其物理位置【 连续 】。链式存储结构中，逻辑上相邻的元素，其物理位置【 不一定连续 】 。 4. 在顺序表中插入或删除一个元素，需要平均移动【 表长一半 】元素，具体移动的元素个数与【 插入或删除的位置】有关。 5. 单链表是线性表的的【链式 】存储结构。
6. 单链表表示法的基本思想是用【 指针域 】表示结点间的逻辑关系。 7. 循环链表与单链表的区别仅仅在于循环链表尾结点的链域值不是【 NULL 】，而是一个指向【 表头指针 】的指针。
8. 如右图所示，在单键表中，P指针所指结点之后插入一个新结点S，操作的语句是： 【 s->next=p-.>next】； 【p->next=s 】。
9. 顺序表的类型中，假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个（1≤i≤n）结点ai的存储地址为【 b+(i-1)*k 】。
10. 在单链表中，删除P 指针所指向的结点的后继（S指针指向的结点）的操作是【p->next=s->next 】；free(【 s 】)。
11. 以下为顺序表的插入运算，分析算法，请在空白处填上正确的语句。 void insert_seqlist(seqlist *L，datatype x，int i)
/*将x插入到顺序表L的位序为i的位置*/
{ if( L->last == maxsize-1 ) error(“表满”)；
if((i<1)||(i>L->last+2)) error(“非法位置”); for(j=L->last;j>=i-1;j--)【L->data[j+1]=L->data[j] 】; L->data[i-1]=x; 【L->last++ 】; }
12. }以下为顺序表的删除运算，分析算法，请在空白处填上正确的语句。
void delete_sqlist(sqlist *L,int i)
/*删除顺序表L中的第i-1个位置上
的结点*/
{ if((i<1)||(i>L->last))
error(“非法位置”)；
for(j=i+1;j=L->last;j++)
【 L->data[j-1]=L->data[j] 】;
L->last=L->last-1; }
13. 下列有关线性表的叙述中，正确的是（
D ）。
(A)一个线性表是n个数据元素的有限序列 (B)线性表中任何一个
元素有且仅有一个直接前驱
(C)线性表中任何一个元素有且仅有一个直接后继 (D)以上说法都不正确
14. 顺序表是线性表的（
B ）。
(A)链式存储结构 (B) 顺序存储结构 (C) 索引存储结构 (D) 散列存储结构
15. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动（ A）个元素。
(A)n-i (B)n-i+1 (C)n-i-1 (D)i
16. 一个长度为n的顺序表中第i个位置上插入新元素(1≤i≤n+1)时,需向后移动（ B）个元素。
(A)n-i (B)n-i+1 (C)n-i-1 (D)i
17. 下面的定义是（ typedef struct
B ）。
node
{ int data ;
struct node * next ; } linklist;
(A)顺序表 (B)单链表 (C)双向链表 (D)二叉链表
18. 下面的定义是（ typedef struct
A ）。
{ int data[Maxsize] ; int last ; } seqlist;
(A)顺序表 (B)单链表 (C)静态链表 (D)循环队列
19. 单链表的一个存储结点包含（
A ）。
(A)数据域或指针域 (B)指针域或链域 (C)指针域和链域 (D)数据域和链域
20. 单链表中，增加头结点的目的是为了（
C ）。
(A)使单链表至少有一个结点 (B) 标示表结点中首结点的位置 (C)方便运算的实现 (D)说明单链表是线性表的链式存储实现
21. 对于单链表表示法，以下说法错误的是（
D ）。
(A)指向链表的第一个结点的指针，称为头指针
(B)单链表的每一个结点都被一个指针所指 (C)终端结点的指针域就为NULL
(D)尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
22. 有一个含头结点的单链表，头指针为
head，则判断其是否为空的条件是（ B ）。
(A) head = = NULL (B) head->next = = NULL (C) head->next = = head (D) head != NULL
23. 在带头结点的非空单链表H中，指针p指向某的结点，求p结点的前驱结点指针q的算法是（ B ）。
(A)q=H ; while(q!=p) q=q->next; (B) q=H ; while(q->next!=p) q=q->next;
(C) q=H->next ; while(q!=p) q=q->next; (D) q=H->next ; while(q->next!=p) q=q->next;
24. 在带头结点的单链表
H中，求单链表长度len的算法是（ A ）。
(A) len=0,p=H ; while(p->next!=NULL){ len ++ ; p=p->next;} (B) len=0,p=H->next ; while(p->next!=NULL){ len ++ ; p=p->next;} (C) len=1,p=H ; while(p!=NULL){ p=p->next; len ++ ; }
(D) len=1,p=H->next ; while(p->next!=NULL){ p=p->next; len ++ ;}
25. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针后面插入结点s的操作是（ C ）。
(A) p->next=s;s=p->next; (B)p->next=s;s->next=p->next; (C) s->next=p->next;p->next=s; (D)s->next=p;p->next=s;
26. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针前面插入结点s的操作是（ 无正确答案）。
(A) s->next=p->next;p->next=s; (B)p->next=s; s->next=p->next; (C) p->next=s ; s=p->next; (D)s->next=p ; p->next=s;