数据结构课后练习-第2章.ppt

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加 学习要点 了解线性表的逻辑结构特性，即数据元素之间存在着线 性关系，在计算机中表示这种关系两类不同的存储结构 ：顺序存储结构和链式存储结构。用前者表示的线性表 简称为顺序表，用后者表示的线性表简称为链表。 熟练掌握这两类存储结构的描述方法，如一维数组中一 个区域ij的上、下界和长度之间的变换公式（L=j-i+1, i=j-L+1, j=i+L-1），链表中指针p和结点*p的对应关系（ 结点*(p-next)是结点*p的后继等），链表中头结点、头 指针和首元结点（第一个元素的结点）的区别及循环链 表、双向链表的特点等。链表是本章的重点和难点，掌 握指针操作和内存动态分配的编程技术。 学习要点 熟练掌握在顺序存储结构上线性表的基本操作，如查 找、插入和删除的算法。 熟练掌握在各种链表结构中线性表的基本操作，能在 实际应用中选用适当的链表结构。 能够从时间与空间复杂度方面综合比较线性表两种存 储结构的不同特点及其适用场合。 一、判断对错题 1. 线性表中的元素可以是各种各样的，但同一线性表中 的数据元素具有相同的特性，因此属于同一数据对象 。（ ） 2. 线性表的链式存储结构优于顺序存储。（ ） 3. 在单链表中，任何两个元素的存储位置之间都有固定 的联系，所以可以从头结点开始查找任何一个元素。 （ ） 4. 顺序存储的线性表可以实现随机存取。（ ） 二、单项选择题 1. 用单链表方式存储的线性表，存储每个结点需要两个域 ，一个数据域，另一个是_。 A. 当前结点所在的地址域B. 指针域 C. 空指针域D. 空闲域 2. 在具有n个结点的单链表中，实现_的操作，其算法 的时间复杂度都是O(n)。 A. 遍历链表和求链表的第i个结点 B. 在地址为p的结点之后插入一个结点 C. 删除开始结点 D. 删除地址为p的结点的后继结点 B A 二、单项选择题 3. 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一 个结点的地址为da1，则第i个结点的地址为_。 A. da1+(i-1)mB. da1+im C. da1-imD. da1+(i+1)m 4. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。 A. 访问第i个结点（1in）和求第i个结点的直接前驱（2in） B. 在第i个结点之后插入一个新结点（1in） C. 删除第i个结点（1in） D. 将n个结点从小到大排序 A A 二、单项选择题 5. 两个指针p和q，分别指向单链表的两个元素，p所指 元素是q所指元素前驱的条件是_。 A. p-next=q-nextB. p-next=q C. q-next=pD. p=q B 三、填空题 1. 在链表中逻辑上相邻的元素的物理位置_相连 。 2. 在n个结点的顺序表中删除一个结点平均需要移动 _个结点，具体的移动次数取决于 _ 。 3. 在单链表中要在已知结点*p之前插入一个新结点，需找 到_。 不一定 (n-1)/2 顺序表的长度与被删元素在表中的位序 结点*p的直接前驱结点（的地址） 四、简答题 1. 简述线性表的存储结构及各自的优点。何时选用顺序 表、何时选用链表作为线性表的存储结构为宜？ 从空间上来看：当线性表的长度变化较大、难以估计 其规模时，选用动态的链表作为存储结构比较合适。 但链表除了需要设置数据域外，还要额外设置指针域 ，因此当线性表长度变化不大、易于事先确定规模时 ，为了节约存储空间，宜采用顺序存储结构。 四、简答题 1. 简述线性表的存储结构及各自的优点。何时选用顺序 表、何时选用链表作为线性表的存储结构为宜？ 从时间上来看：若线性表的操作主要是查找，很少进 行插入和删除操作时，应选用顺序表。对于频繁进行 插入和删除操作的线性表，宜采用链表作为存储结构 。 四、简答题 2. 什么是头指针、头结点、首元结点。 首元结点：链表中存储的线性表中的第一个数据元素 的结点。 头结点：为了操作的方便，通常在链表的首元结点之 前附设一个结点，称头结点。 头指针：指向链表中的第一个结点（或为头结点或为 首元结点）的指针。 四、简答题 3. 在顺序表中插入和删除一个结点需平均移动多少个结 点？具体的移动次数取决于哪两个因素？ 插入结点：移动元素次数n-i+1； 删除结点：移动元素次数n-i。 决定因素：顺序表的长度以及插入、删除元素在表中 的位序。 4. 分析下述三个算法的具体功能。 ListNode *Demo1(LinkList L, ListNode *p) /L是有头结点的单链表 ListNode *q=L-next; while(q if(q) return q; else Error(“*p not in L“); 算法功能：寻找*p结点的直 接前驱结点*q。 4. 分析下述三个算法的具体功能。 void Demo2(ListNode *p, ListNode *q) /p，*q是链表中的两个结点 DataType temp; temp=p-data; p-data=q-data; q-data=temp; 算法功能：*p结点和*q结点 的值互换。 4. 分析下述三个算法的具体功能。 LinkList test1( LinkList L ) /L是无头结点的单链表 LinkList *q, *p; if ( L L=L-next; p=L; while ( p-next ) p=p-next; p-next=q; q-next=NULL; return L; 算法功能：如果表长度 大于1，则将首元结点删 除并插入到表尾。 或者可以这么说：把表 (a1,a2,ai,an)改成 (a2,a3,ai,an,a1)。 5. 设有多项式 请画出 的单链表存储表示。 设 ，求得并画出的单链表存储表示。 9 08 19 45 10 -2 122 7-5 10 A B 9 06 19 422 7 C 五、程序设计题 1. 对给定的带头结点的单链表L，编写一个删除L中值为x的 结点的直接前驱结点的算法。 x 被删结点 pq Status ListDelete _L( LinkList L， ElemType x ) /在带头结点的单链表L中，删除值为x的结点。 LNode *p,*q; p = L; while ( p-next p = p-next; /寻找值为x的结点，并令p指向其前驱（被删结点）； /指针q指向*p结点的前驱结点。 if ( !(p-next) ) return ERROR; /表中不存在值为x的结点 。 pnext=qnext; /删除元素（结点）x的前驱结点。 free( p ) ; /释放结点的存储空间。 return OK; 线性表的结构定义： -线性表的动态分配顺序存储结构- #define LIST_INIT_SIZE 100 /顺序表的初始分配量 #define LISTINCREMENT 10 /顺序表的分配增量 typedef struct ElemType *elem; /存储空间基址：即数组的起始地址 int length; /顺序表的当前长度：实际的元素个数 int listsize; /当前分配的存储容量（以sizeof（ElemType） 为单位） SqList; 2. 将一个顺序表中从第i个结点开始的k个结点删除。 Status ListDelete_Sq ( SqList /i的位置不合法 if (kL.length ) return ERROR; /k的取值不合法 ElemType *p, *q; p = /需要被删除的第i个元素（下标为i-1） q = L.elem + L.length 1; /从最后一个元素开始 if ( k=(q-p)+1) ) /第i个元素后的所有元素均被删除 L.length = i-1; return OK; else for( ; k=1; k=1; -k; ) for ( +p; p next; /找到插入位置 while( p!=NULL s=( LinkList )malloc( sizeof(LNode) ); /生成新