第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65 第 1 章　 数据结构 65 10 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 865 A B C D E F G 姓名 学号 成绩 班级 李红 9761059 95 机97.6

1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 表头 表尾 其中: n为线性表长度(n=0称为空表)，表中相邻元素之间存在着顺序关系。a1 ：表头元素；an ：表尾元素；ai-1称为ai的直接前驱；ai+1 称为ai的直接后继。

1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) (1)有且只有一个根结点a1，无前驱 。 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 3) 线性结构特点: (1)有且只有一个根结点a1，无前驱 。 (2)有且只有一个终端结点an ，无后继 。 (3)其他结点有且只有一个直接前驱和一个直接后继。

1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 3) 线性结构特点: 4) 线性表的分类 (1)简单线性表： 数据元素是简单项(数字、字母、季节名等)。 如:(12,34,4,67,8) (2)复杂线性表： 数据元素由若干个数据项组成，此时数据元素称为记录或结点, 如学生成绩表. 简单线性表：一副扑克的点数 （2，3，4，…，J，Q，K，A）

姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 …….. …….

1.2 线性表 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 1.顺序表基本概念 顺序表： 1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 用一组地址连续的存储空间依次存放线性表的各元素 。 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 顺序表： 采用顺序存储结构的线性表称为顺序表(一维数组)

4.2 线性表 1.顺序表基本概念 4.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 其中: m：每个元素占m个存储单元 Loc(a1)第一个元素地址(基址) 对数组而言

存储地址 存储状态 数据元素在线性表中的位序 b an－1 …….. ai a1 a0 1 2 从存取方式看,线性表的顺序存储结构是可以随机存储的存储结构. b+m b+i*m i b+n*m n 空闲

1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 存取: 访问线性表的第i个元素，使用或改变数据元素的值。 查找: 在线性表中查找满足某种条件的数据元素。 插入: 在线性表的第i个元素之前，插入一个同类型的元素。 (***) 删除: 删除线性表中第i个元素。 (***) 求表长: 求出线性表中元素的个数。 置空表: 建立一个空表。 清除表: 将已有线性表变为空表，即删除表中所有元素。 2) 第i个元素地址

1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 ….. … 先移动 后插入 ….. … … … 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 1)顺序表的插入运算: 在线性表的第i个元素之前插入一个新的元素，先移动，后插入。 x ai-1 ….. a2 a1 an … ai+1 ai 先移动 后插入 ai-1 ….. a2 a1 ai … an x ai ai … ai+1 an …

(1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入”空出”的第i个位置 步骤： (1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入”空出”的第i个位置 举例：(在第4个和第5个元素之间插入元素91) 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 21 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 91

插入程序举例(在8个数中任意位置插入一个数)： #define N 8 main() { int a[N+1]={12,34,45,6,78,9,10,91}, i,j,x; printf(“input the location to be inserted:”); scanf(“%d,%d”,&i,&x); a[i-1]=x; for(j=0;j<=N;j++) printf(“%d,”,a[j]); } for(j=i-1;j<=N-1;j++) a[j+1]=a[j]; for(j=N-1;j>=i-1;j--) a[j+1]=a[j];

插入运算时间性能分析： 插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)： <例>在一线性表(a1,a2,a3)中插入任意一数i，求平局移动元素次数: pi：在第i个位置上作插入的概率。 在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i+1)个元素。 (n-i+1) i 移动次数(n-i+1) 1(插入到第1个数a1前) 3 2 (插入到第2个数a2前) 2 3 (插入到第3个数a3前) 1 (插入到第3个数a3后) 0 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 等差数列求和公式: ((首项+末项)×项数)/2 线性表(a1,a2,a3)平局移动元素个数: (¼)*(3+2+1+0)=1.5

1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。 1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。 原表长为n：( a1，a2，…ai-1，ai ，ai+1， … an ) 新表长为n-1：( a1，a2，…ai-1，ai+1， …， an ) 步骤： (1)将ai+1 ~ an， 顺序向前移动 (2)表长减一

时间消耗与插入运算相同，平均移动元素次数： 举例：(删除第五个元素21) 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 67 41 26 4 8 9 16 0 1 2 3 4 5 6 7 8 67 时间性能分析： 时间消耗与插入运算相同，平均移动元素次数： qi:在第i个位置上作插入的概率。设qi=1/n 共需移动(n-i)个元素。

<例>在一线性表(a1,a2,a3)中删除任意一数i，求平局移动元素次数: 作业：有一数组，存储十个数， 编程序删除其中任意一个数。 <例>在一线性表(a1,a2,a3)中删除任意一数i，求平局移动元素次数: i 移动次数(n-i) 1(删除第1个数a1) 2 2 (删除第2个数a2) 1 3 (删除第3个数a3) 0 线性表(a1,a2,a3)平局移动元素个数: (1/3)*(2+1+0)=1

1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点： 1.2.2 线性表的顺序存储结构 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点： 逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。 缺点： 插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。

1.2 线性表 1.2.3 线性表的链式存储结构 链式存储结构特点: 存储空间可以不连续。 不要求逻辑上相邻的元素在物理位置上也相邻。 1.2.3 线性表的链式存储结构 链式存储结构特点: 存储空间可以不连续。 不要求逻辑上相邻的元素在物理位置上也相邻。 数据元素间逻辑关系由指针域确定。 即 链表存储结构是一种动态数据结构，其特点是它包含的据对象的个数及其相互关系可以按需要改变，存储空间是程序根据需要在程序运行过程中向系统申请获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。

结构体元素 结构体元素的地址 结构体元素的成员是地址型数据 zhang 335 3108＃ 2548# name p strcpy(p->name,”zhang”)； p->sum=335; p->next=? sum next 结构体元素的成员是地址型数据 struct student { char name[10]; int sum; struct student *next; }; struct student *p;

有四个结构体元素： p3 p1 p2 head zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao 352 3188＃ 3148# wu 347 0＃ 3188# p3 p1 p2 head

有四个结构体元素： head zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao 352 3188＃ 3148# wu 347 0＃ 3188# head

（1）头指针变量head──指向链表的首结点。 zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao 352 3188＃ 3148# wu 347 NULL 3188# （1）头指针变量head──指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域──存储结点本身的信息。 2）指针域──指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志 struct student { char name[10]; int sum; struct student *next; };

1.2 线性表 定义：线性表的链式存储结构称为线性链表 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 定义：线性表的链式存储结构称为线性链表 线性链表中 结点组成： 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 前一个结点或后一个结点 分类：单链表、循环单链表、双向链表

(bat，cat，eat，fat，hat，jat，lat，mat) <例>有一线性表: (bat，cat，eat，fat，hat，jat，lat，mat) 其单链表示意图如下： ……… …… hat 200 ……. cat 135 eat 170 …. mat Null bat 130 fat 110 jat 205 lat 160 …… 110 130 135 160 头指针 head 165 170 200 205 链尾 简化为： 略 165

也就是说：LinkList等价与struct node head bat cat eat mat ^ … 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 新的类型名代换旧的类型名， 也就是说：LinkList等价与struct node 例如：若头指针名是head，则把链表称为表head。 用C语言描述的单链表如下： struct node { char name[20]; struct node *next; }; struct node *head; typedef struct node { char name[20]; struct node *next; }LinkList; LinkList *head;

1.2 线性表 3 .单链表: 例：线性单链表( A, B, C, D, E, F ) 1.2.3 线性表的链式存储结构 链式存储结构特点: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 定义：由n个结点链接，且每个结点中只包含一个指针域的链表。 例：线性单链表( A, B, C, D, E, F ) 逻辑状态 A B C D E head F 其中: head称为单链表的头指针,指向表中的第一个结点

物理状态 A B C D E F 头指针 存储地址 数据域 指针域 19 E 7 F NULL B 25 A 13 C 31 D 1 head A B C D E F 物理状态 头指针 存储地址 数据域 指针域 19 1 7 13 19 25 31 E 7 F NULL B 25 A 13 C 31 D 1 单链表存取:必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素,因此说线性表的链式存储结构是一种顺序存储的存储结构。

（1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 B C D E F head A B C D E F 带头节点的单链表 编程：创建带头节点的单链表。 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p->next=s; （6）p=s; （7）回到第（3）步; 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

head=p=(strutc node*) malloc(sizeof(struct node)); 对带头结点的复杂链表的基本操作——创建 head p 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p->next=s; （6）p=s; （7）回到第（3）步; head=p=(strutc node*) malloc(sizeof(struct node));

对带头结点的复杂链表的基本操作——创建 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p->next=s; （6）p=s; （7）回到第（3）步; s->data=getchar();

对带头结点的复杂链表的基本操作——创建 程序算法： （1）定义三个结构体类型的指针变量head, p, s B A 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p->next=s; （6）p=s; （7）回到第（3）步;

A B C D E F A B C D E F 带头节点的单链表 head head 编程：创建带头节点的单链表。 typedef struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf("input letters to create a list:\n"); while((ch=getchar())!='\n') {s=(Linklist *)malloc(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; 带头节点的单链表 编程：创建带头节点的单链表。 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

Linklist *head,*p,*s; char ch; 带头节点的单链表 typedef struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf("input letters to create a list:\n"); p=head; while((ch=getchar())!='\n') {s=(Linklist *)malloc(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; ··············· data next B 2000 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

Linklist *head,*p,*s; char ch; typedef s struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf("input letters to create a list:\n"); p=head; while((ch=getchar())!='\n') {s=(Linklist *)malloc(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; ··············· A 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

Linklist *head,*p,*s; char ch; typedef s s struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf("input letters to create a list:\n"); p=head; while((ch=getchar())!='\n') {s=(Linklist *)malloc(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; ··············· A B 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

Linklist *head,*p,*s; char ch; typedef s s struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf("input letters to create a list:\n"); p=head; while((ch=getchar())!='\n') {s=(Linklist *)malloc(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; ··············· A B C NULL 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

1.2 线性表 3 .单链表: 在指针p所指结点之后插入一个指针s所指的结点 修改p和s所指结点的指针域的指针即可 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (1)单链表插入：增加新结点,修改链接指针 后插结点 在指针p所指结点之后插入一个指针s所指的结点 修改p和s所指结点的指针域的指针即可

插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext 修改p指针域, 使其指向新结点s: pnext＝s p A B C X s 考虑上述两步骤若颠倒会怎样？

插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext 修改p指针域, 使其指向新结点s: pnext＝s p A B C X s 它们占用着内存空间，程序却找不到它们了 考虑上述两步骤若颠倒会怎样？ 后面的结点都将从链表中脱离

1.2 线性表 3 .单链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (2)单链表删除：不需要移动元素,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可

C B A C B A 删除步骤 qnext＝qnextnext 修改q结点指针域 qnext＝pnext p free(p); 先找到p的前驱结点q 修改q结点指针域 qnext＝pnext C p B A 删除前 free(p); q p C B A 删除后

1.2 线性表 3 .单链表: 4.循环链表 特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。 带头节点的循环链表

优点：从表中任一结点出发均可找到表中其它结点。 对带头结点的单循环链表head为空的判定条件是 head->next=head 带头结点的空循环链表

1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。 data prior next 结点构成：

对指向双向链表任一结点的指针p，有下面的关系： p->next->priou=p->priou->next=p 作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。 next p head ... an a2 a1 next next prious prious prior 对指向双向链表任一结点的指针p，有下面的关系： p->next->priou=p->priou->next=p

1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 (1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。 p 插入前 c b a x 待插入的结点:q

①p结点作为q结点的前驱:q->prior=p； a b c ④ ① ② ③ x q 确定新结点q的前驱和后继 ①p结点作为q结点的前驱:q->prior=p； ②p结点的后继作为q结点的后继:q ->next=p->next； ③q结点作为p 结点的后继结点的前驱结点:p->next->prior=q ④q结点作为p结点的后继:p->next=q； (p的后继指向新结点q)

1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 (2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。 p 删除前 c b a

① p a b c ② ① p的后继结点作为p结点前驱结点的后继 (a c) p->prior->next = p->next； ② p的前驱结点作为p结点后继结点的前驱 ( a c) p->next->prior= p->prior； free(p)；

1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 习题讲解 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 2. 在单链表中，增加头结点的目的是______。 A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现 BA

A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 3 用链表表示线性表的优点是______。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_______. A. 248 B. 247 C. 246 D. 244 AD

5. 下列对于线性链表的描述中正确的是______。(05.4月 ） A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 A

A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 6. 线性表是（） A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 7．在一个长度为n的线性表中，删除值为x的元素时需要比较元 素和移动元素的总次数为（） A. （n+1）/2 B.n/2 C. n D.n+1 8. 一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1) 位置插入一个新元素时，需要从后面向前依次后移（ ）个元 素。 A. n-i B. n-i+1 C. n-i-1 D. i ACC ——详见《计算机基础综合实训教程》P175

9.设单链表中指针p指向结点ai,若要删除ai之后的结点（若存 在），则需修改指针的操作为（）。 A. p->next= p->next->next B. p=p->next C. p=p->next->next D. next=p 10.设单链表中指针p指向结点ai,指针q指向将要插入的新结点 x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先 修改 q->next=p->next，后修改（）即可。 A. p->next= q B. p->next= p->next->next C. p->next=q->next D. q->next=null 11.在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则需要相继修改（）个指针域的值。 A. 1 B. 2 C. 3 D.4 AAB

12.不带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL C. L->next = = L D. L! = NULL 13．带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL C. L->next = = L D. L! = NULL 14.在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D.6 15.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（） A. p->prior B. p->next C. p->next->next D. p->prior ->prior 16.线性表采用链式存储时，其地址（） A. 必须是连续的 B. 一定是不连续的 C. 部分地址必须是连续的 D. 连续与否均可以 ABCBD

1.数据结构分为逻辑结构和存储结构，循环队列属 于 ———— 结构。（05.9月） 填空题 1.数据结构分为逻辑结构和存储结构，循环队列属 于 ———— 结构。（05.9月） 存储结构 2.在一个单链表中删除指针p所指向结点时，应执行一下操作： q=p->next; p->data= p->next->data; p->next=_____； free(q); p->next->next p q A B B C

4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_____赋值操 3. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把___ __的值赋给q->next，然后把_____的值赋给p->next。 p->next q 4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_____赋值操 作，然后执行_____赋值操作。 p->next=head head=p head p

5. 在一个单链表中删除指针p所指向结点的后继结点时，需要把_____的值赋给p->next指针域。 p->next->next 循环 6. 在_____链表中，既可以通过设定一个头指针也可 以通过设定一个尾指针来确定它，即通过头指针或 尾指针可以访问到该链表中的每个结点。 7. 在一个带有头结点的双向循环链表中的p所指向的结 点之前插入一个指针s所指向结点时,可执行如下操作： (1) s ->prior=_____； (2) p->prior->next=s; (3) s->next=_____; (4) p->prior=_____; p->prior p s p s

8. 线性表的长度是指_______。 线性表中包含数据元素的个数 9.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_______和_______。 单链表、双链表 10. 循环单链表与非循环单链表的主要不同是循环单链表的尾结 点指针______，而非循环单链表的尾结点指针______。 指向链表头节点 指向空 11.访问单链表中的结点，必须沿着______依次进行。 指针域 12. 在双向链表中，每个结点有两个指针域，一个指向______， 另一个指向______。 后续节点 前驱节点 13. 在一个双向链表中删除指针p所指向的结点时，需要对 p->next->prior指针域赋值为______。 p->prior

14.设head为单循环链表L的头结点，则L为空表的条件是______。 head->next=head 15.假设以S和X分别表示进栈和退栈操作，则对输入序列a, b, c ,d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是 ______。 bceda 16. 在一个长度为n的顺序表中的删除第i个元素（0≤i≤n-1），需 要向前移动______个元素。 n-i 17. 线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的 概率相同，则删除一个元素平均需要移动元素的个数是 。 (n-1)/2 18.一含N个元素的顺序表，若在第i个元素之前插入一个元素，需移动 个元素。 n-i+1

19.从链表种删除q结点之后的p结点，语句为：q->next= 。 p->next 20.链表中每个结点包含两部分内容，一部分为数据域，另一部 分为 域。 指针 21. 在单链表中，要删除某一指定的结点，必须找到该结点的 _______。 前驱

B) (*p).next=(*q).next; free(q); C) q=(*q).next; (*p).next=q; free(q); 练1 假定建立了以下链表结构，指针p、q分别指向如图所示的结点，则以下可以将q所指结点从链表中删除并释放该结点的语句组是 A) free(q); p->next=q->next; B) (*p).next=(*q).next; free(q); C) q=(*q).next; (*p).next=q; free(q); D) q=q->next;p->next=q;p=p->next; free(p); head 8 4 3 p q date next

练2 若已建立如下图所示的单向链表结构,在该链表结构中，指针p、s分别指向图中所示结点，则不能将s所指的结点插入到链表末尾仍构成单向链表的语句组是 A) p =p->next; s->next=p; p->next=s; B) p =p->next; s->next=p->next; p->next=s; C) s->next=NULL; p=p->next; p->next=s; D) p=(*p).next; (*s).next=(*p).next; (*p).next=s; head   E F \0 p date next G s