2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。
头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好？
解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。
解：2.5 画出执行下列各行语句后各指针及链表的示意图。
l=(linklist)malloc(sizeof(lnode));p=l;
for(i=1;i<=4;i++)
p->next=null;
for(i=4;i>=1;i--)ins_linklist(l,i+1,i*2);
for(i=1;i<=3;i++)del_linklist(l,i);
解：2.6 已知l是无表头结点的单链表，且p结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在p结点后插入s结点的语句序列是。
b. 在p结点前插入s结点的语句序列是。
c. 在表首插入s结点的语句序列是。
d. 在表尾插入s结点的语句序列是。
1) p->next=s;
2) p->next=p->next->next;
3) p->next=s->next;
4) s->next=p->next;
5) s->next=l;
6) s->next=null;
7) q=p;
8) while(p->next!=q) p=p->next;
9) while(p->next!=null) p=p->next;
10) p=q;
11) p=l;
12) l=s;
13) l=p;
解：a. (4) (1)
b. (7) (11) (8) (4) (1)
c. (5) (12)
d. (9) (1) (6)
2.7 已知l是带表头结点的非空单链表，且p结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 删除p结点的直接后继结点的语句序列是。
b. 删除p结点的直接前驱结点的语句序列是。
c. 删除p结点的语句序列是。
d. 删除首元结点的语句序列是。
e. 删除尾元结点的语句序列是。
1) p=p->next;
2) p->next=p;
3) p->next=p->next->next;
4) p=p->next->next;
5) while(p!=null) p=p->next;
6) while(q->next!=null)
7) while(p->next!=q) p=p->next;
8) while(p->next->next!=q) p=p->next;
9) while(p->next->next!=null) p=p->next;
10) q=p;
11) q=p->next;
12) p=l;
13) l=l->next;
14) free(q);
解：a. (11) (3) (14)
b. (10) (12) (8) (3) (14)
c. (10) (12) (7) (3) (14)
d. (12) (11) (3) (14)
e. (9) (11) (3) (14)
2.8 已知p结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a. 在p结点后插入s结点的语句序列是。
b. 在p结点前插入s结点的语句序列是。
c. 删除p结点的直接后继结点的语句序列是。
d. 删除p结点的直接前驱结点的语句序列是。
e. 删除p结点的语句序列是。
1) p->next=p->next->next;
2) p->priou=p->priou->priou;
3) p->next=s;
4) p->priou=s;
5) s->next=p;
6) s->priou=p;
7) s->next=p->next;
8) s->priou=p->priou;
9) p->priou->next=p->next;
10) p->priou->next=p;
11) p->next->priou=p;
12) p->next->priou=s;
13) p->priou->next=s;
14) p->next->priou=p->priou;
15) q=p->next;
16) q=p->priou;
17) free(p);
18) free(q);
解：a. (7) (3) (6) (12)
b. (8) (4) (5) (13)
c. (15) (1) (11) (18)
d. (16) (2) (10) (18)
e. (14) (9) (17)
2.9 简述以下算法的功能。
1) status a(linkedlist l)
2) void bb(lnode *s, lnode *q)
void aa(lnode *pa, lnode *pb)
解：(1) 如果l的长度不小于2，将l的首元结点变成尾元结点。
(2) 将单循环链表拆成两个单循环链表。
2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。
status deletek(sqlist &a,int i,int k)
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素。
if(i<1||k<0||i+k> return infeasible;//参数不合法。
else return ok;
解：status deletek(sqlist &a,int i,int k)
//从顺序存储结构的线性表a中删除第i个元素起的k个元素。
//注意i的编号从0开始。
int j;
if(i<0||i><0||k> return infeasible;
for(j=0;j<=k;j++)
return ok;
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
解：status insertorderlist(sqlist &va,elemtype x)
//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法。
int i;
if(for(i=>0,x<
线性表的完整程序数据结构C语言版
顺序表存储结构及常见操作 ifndef seqlist define seqlist include 顺序表存储空间长度的最小值 define listminsize 10 顺序表存储结构类型定义 typedef struct listdt base 顺序表空间基地址 int listsize 顺序...
数据结构实习报告
精选范文 数据结构实习报告 共2篇 一 需求分析1 程序所实现的功能 2 程序的输入，包含输入的数据格式和说明 3 程序的输出，程序输出的形式 4 测试数据，如果程序输入的数据量比较大，需要给出测试数据 5 合作人及其分工。二 设计说明1 主要的数据结构设计说明 2 程序的主要流程图 3 程序的主要...
数据结构 本科 形成性考核册答案
作业1一 单项选择题。1 c 2 d 3 b 4 c 5 d 6 c 7 b 8 c 9 a 10 b 11 c 12 d 13 c 14 a 15 b 16 c 17 c 18 b 19 b 20 d 二 填空题 1 n i 1 2 n i 3 集合线性结构树形结构图状结构 4 物理结构存储结构 ...