数据结构第2章典型例题解析.doc

1、 数据结构典型例题解析 第 2章 线 性 表 典型例题解析 一、 选择题 1线性表是具有 n 个（ n 0） 的有限序列。 A表元素 B字符 C数据元素 D数据项 【分析】 线性表是具有相同数据类型的 n（ n 0）个数据元素的有限序列，通常记为(a1,a2, ,an)，其中 n 为表长， n=0 时称为空表。 【答案 】 C 2顺序存储结构的优点是 。 A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 【分析】 顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素 ，数据元素的逻辑顺序和物理次序一致。因此，其存储密度大 。 【答案 】 A 3带头结点的

2、单链表 head 为空的判断条件是 。 A head=NULL B head-next=NULL C head-next=head D head!=NULL 【分析】 链表为空时，头结点的指针域为空。 【答案 】 B 4若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表 【分析】 根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素， A和 B 都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项 C 双链

3、表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项 D 可通过尾指针直接找到线性表的最后 一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。 【 答案 】 D 5若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 【分析】 某线性表最常用的操作是存取任一 指定序号的元素和在最后进行插入和删除运第 2 章 线 性 表 算。因此不需要移动线性表种元素的位置。根据题意要求， 该线性表的存储应能够很方便

4、地找到线性表的 任一指定序号的元素 和最后一个元素 ， 顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。链表需要通过指针才能找到线性表的莫以指定序号的 元 素，需要一定的时间开销 。 【 答案 】 A 6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 【分析】 根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和最后一个元素的前驱元素， A和 B都不能很方便地通过头指针找到线性表的第一个元素； 选项 C 可以方便地找到 最后一个元素 ，单不能很快地找到其前

5、驱元素 ；选项 D 为双向循环链表，可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元素 。 【 答案 】 D 7 静态链表中指针表示的是 。 A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址 【分析】 静态链表采用的是链式方式存储线性表， 以数组方式存储链表的数据，指针域存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称为静态指针。 【 答案 】 B 8 链表不具有的特 点是 。 A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比 【分析】 链表是通过一组任意的存储单元来存储线性表中的数

6、据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放其后继 元素 所在的存储单元的地址。链表 不具有按序号随机访问第 i 个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第 i 个结点。 【 答案 】 B 9线性表的静态链表存储结构与顺序存储结构相比 优点是 。 A所有的操作算法简单 B便于插入和删除 C便于利用零散的存储器空间 D便于随机存取 【分析】 静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。 【 答案 】 B 10若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素算法的时间复

7、杂度为 。 A O(log2n) B O(1) C O(n) D O(n2) 【分析】 在第 i 个位置上插入新元素需要从最后一个元素开始后移直到第 i 个元素后移为止，后 移元素的次数为 n-i+1，即时间复杂度为 O(n)。 数据结构典型例题解析 【 答案 】 C 11 线性表（ a1,a2, ,an）以链接方式存储时，访问第 i 个 位置元素的时间复杂性为 。 A O(i) B O(1) C O(n) D O(i-1) 【分析】 线性表以链接方式存储时，访问第 i 个 位置元素 从第一个元素开始移动指针到第i 个元素，移动指针的次数为 n-i+1，即时间复杂度为 O(n)。 【 答案 】

8、 C 12将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是 。 A n B 2n-1 C 2n D n-1 【分析】 当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需 n 次。 【 答案 】 A 13 非空的循环单链表 head的尾结点 p满足 。 A p-next=head B p-next=NULL C p=NULL D p=head 【分析】 非空的循环单链表 head的尾结点的后继指针指向链表的头结点。 【 答案 】 A 14在双循环链表 p 所指结点之后插入 s 所指结点的操作是 。 A p-next=s; s-prior=p; p-next-prio

9、r=s; s-prior=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next; C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s; D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 【分析】 由于要将 s 所指结点插入到 p 所指结点之后， p 结点 为 s 结点的前驱， s 结点为 p结点的新后继，而结点 p 的原后继结点为结点 s 的后继结点，结点 s 为结点 p 的原后继结点的前驱结点 s。在选项 A、 B

10、 和 C 中均是先执行操作 p-next=s，就是修改了结点 p 的后继结点 s，然后再执行操作 p-next-prior=s，因此，无法使得结点 s 为结点 p 的原后继结点的前驱结点，这样的赋值会使 s 结点为其自身的前驱。应先执行操作 p-next-prior=s，再执行操作 p-next=s。 【 答案 】 D 15在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 结点和 p 结点之间插 入 s 结点，则执行 。 A s-next=p-next;p-next=s; B p-next=s-next;s-next=p; C q-next=s; s-next=p; D

11、p-next=s; s-next=q; 【分析】 由于是将 s 所指结点插入到 q 和 p 所指结点之间，即使其为 q 所指结点的后继结点，为 p 所指结点的前驱结点，因此 s-next 的取值应为 p， p-next 的取值无需改动， q-next的取值应改为 s，故 A、 B和 D 均是错误的。 【 答案 】 C 二、 判断题 1 线性表的特点是每个元素都有一个前驱和一个后继。 【分析】 线性表是一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关第 2 章 线 性 表 系。 线性表中除第一个数据元素和最后一个数据元素外，外每个元素都有一个前驱和一个后继。 【 答案 】错误 2顺序

12、存储的线性表可以按序号随机存取。 【分析】 因为顺序表在内存是用地址连续的空间存储的， 设 a1 的存储地址为 Loc(a1)，每个数据元素占 d 个存储地址，则第 i 个数据元素的地址为： Loc(ai)=Loc(a )+(i-1)d 1 i n 这就是说只要知道顺序表首地址和每个 数据元素所占地址单元的个数就可求出第 i 个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。 【 答案 】正确 3 链表中的头结点仅起到标识的作用。 【分析】 头结点是附加在第一个元素结点之前的一个结点，当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。

13、其作用是为了运算上的方便。 【 答案 】错误 4线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 【分析】 链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每 个数据元素，除了存放数据元素自身的信息之外，还需要存放其后继 元素 所在的存储单元的地址。链表中 结点的存储空间可以是不连续的，但结点内部的存储空间必须是连续的。 【 答案 】错误 5在单链表中和在顺序表中插入一个元素其时间复杂度均为 O(n)，因此说它们的执行时间是相等的。 【分析】 大 O 记法表示时间渐近复杂度，是指一个算法中的时间耗费，往往是问题规模 n的函数 T(n)，当

14、 n 趋向于无穷大时， T(n)的数量级称为算法的时间渐近复杂度。虽然两种存储结构下的插入操作时间复杂度均为 O(n)，但由于两者的基本操作不同，因此不能说 它们的执行时间是相等的。 【 答案 】错误 6 所谓静态链表就是一直不发生变化的链表。 【分析】 静态链表是指以数组方式存储链表的数据，数组的每个元素包含有数据域 data和指针域 next，其存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标）。其 存储空间不发生变化，而其 内容 可以发生变化。 【 答案 】错误 7 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 【分析】 静态链表是指以数组方式存储链表的数据，

15、对链表进行插入和删除运算时，只需改变指针，不需移动数据。 【 答案 】正确 8静态链表既有顺序 存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素数据结构典型例题解析 的时间与 i 无关。 【分析】 因为静态链表的存取特性与动态链表是一样的，只能顺序地找到第 i 个元素，不能随机地存取第 i 个元素，故其存取表中第 i 个元素的时间与 i 有关。 【 答案 】错误 9 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 【分析】因为 静态链表是以数组方式存储链表的数据，数组空间大小在数组定义时就已确定，一般不会发生变化。 【 答案 】正确 10 取线性表的第 i

16、个元素的时间同 i 的大小有关。 【分析】 存取线性表中数据元素的时间开销与其存储结构有关。顺序存储结构 具有按序号随机访问的特点， 同 i 的大小无关 。 【 答案 】错误 三、 简答题 1如图 2-11 所示的双向链表中，欲在结点 p 前插入一个结点 s，请完成有关操作。 s-prior=p-prior; p-prior=s; s-next=p; 【解答】 只能是“ s-prior-next=s;”而不能为 “ p-prior-next=s;”。 因为在上面的第二条语句中已经改变了结点 p 的前驱结点，结点 p 的前驱结点已经为 s结点，而 不是操作前的前驱结点。在下面的语句顺序下，可有两

17、个答案进行选择。 s-prior=p-prior; p-prior=s; s-next=p; 读者做这种题时，最好予以图示，不易出错。 2已知线性表非递减有序，存储于一个一维数组 A0.n-1 中（表长为 n，设为全局量），下面算法的功能是什么？ void del(DataType A) int i,j; i=1; while (inext) q=L; L=L-next; p=L; while (p-next) p=p-next; p-next=Q; q-next=NULL; return L; 【解答】 算法的功能是把单链表的第一个结点从表头移到了链尾。返回的 L 指向原链表的第二个结点。若

18、原链表表示的线性表是 (a1,a2, ,an)，则操作后表示的线性表为 (a2,a3, , an,a1)。 4试描述头指针、头结点、开始结点的区 别，并说明头指针和头结点的作用。 【解答】 头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表 H，链表 L 等，表示链表中第一个结点的地址存放在 H 和 L 中。 头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。 开始结点指第一个元素结点。 头指针的作用是用来唯一标识一个单链表。 头结点的作用有两个：一是使得对空表

19、和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的 操作一致，无需特殊处理。 5在单链表、双链表和单循环链表中，若仅知道指针 p 指向某结点，而不知道头指针，能否将结点 p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 【解答】 单链表：若结点 p 有后继结点，则可将结点 p 的后继元素数据放入结点 p 中，再将后继结点删除。时间复杂度为 O(1)；若结点 p 无后继结点，则不可以实现。 双链表：可以实现，时间复杂度为 O(1)。 单循环链表：像单链表那样进行操作，也可以从 p 开始，找结点 p 的直接前驱，然后再删除 p 结点，时间复杂度为 O(n)。 四、 算

20、法设计题 1设线性表存放在一 维数组 Aarrsize的前 num 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 数据结构典型例题解析 【分析】 直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定要将一维数组和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性确定插入元素的插入位置，后面的元素为它让出位置（也可以从高下标端开始一边比较，一边移位），然后插入 x，最后修 改表示表长的变量。 【

21、算法 】 InsertSeq(DataType A,int *num,DataType x) /设 num为表的最大下标 int i; if (*num=arrsize-1) return 0; else i=*num; while (i=0 i-; Ai+1=x; /找到的位置是插入位的下一位 (*num)+; return 1; 时间复杂度为 O(n)。 2假设在长度大于 1 的单循环链表中，既无头结点也无头指针。 s 为指向链表中某个结点的指针，试编写算法删除结点 s 的直接前驱结点。 【分析】 利用循环单链表的特点，通过 s 指针可循环找到其前驱结点 p 及 p 的前驱结点 q，然后可

22、删除结点 p。 【 算法 】 viod delepre(LNode *s) LNode *p,*q; p=s; while (p-next=s) q=p; p=p-next; q-next=s; delete p; 3已知两个单链表 A 与 B 分别表示两个集合，其元素递增排列，编写一个函数求出 A和 B 的交集 C，要求 C 同样以元素值递增的单链表形式存储。 【分析】 交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表 C 带有一个头结点，最后将其删除掉。算法中指针 p 用来指向 A 中的当前结点，指针 q 用来指向 B 中的当前结点，将其值进行比较，两者相等时，属于交

23、集中的 一个元素，两者不等时，将其较小者跳过，继续后面的比较。 第 2 章 线 性 表 【 算法 】 LinkNode *inter(LinkList A,B) LNode *q,*p,*r,*s,*C; C=new LNode; r=C; p=A; q=B; while (p else if (p-data=q-data) s=new LNode; s-data=p-data; r-next=s; r=s; p=p-next; q=q-next; else q=q-next; r-next=NULL; r=C-next; delete C; return r; 4单链表 L 是一个递减有序表

24、，试编写一个高效算法，删除表中值大于 min 且小于 max的结点（若表中有这样的结点），同时释放被删结 点的空间，这里 min 和 max 是两个给定的参数。并分析算法的时间复杂度。 【分析】 由于单链表 L 是一个递减有序表，即由大到小有序，故可从表头开始查找第一个比 max 小的结点，记住其位置，再接着向后查找第一个不大于 min 的结点，然后将它们之间的结点删除。 【 算法 】 LinkList delete(LinkList L,int min,int max) /设 L为带头结点的循环链表 LNode *p,*q,*s,*k; if(L-next) p=L-next; s=L; w

25、hile (p-data=max) s=p; p=p-next; /p指向第一个值小于 max的结点 ,s指向其前驱 while (p!=L /p 指向第一个值不大于 min的结点 while (s-next!=p) 数据结构典型例题解析 /删 除 *s 的后继至 * p的前驱之间的结点 k=s-next; s-next=k-next; delete k; 前两个 while 循环和起来最多循环 n 次，第三个 while 循环最多循环 n 次，即删除 n 个结点，故算法的时间复杂度为 O(n)。 5、编写一个算法，将一个头结点指针为 a 的单链表 A 分解为两个单链表 A 和 B，其头结点指

26、针分别为 a 和 b，使得 A 链表中含有原链表 A 中序号为奇数的元素（头结点紧接的下一个元素为第 1 个元 素），而 B 链表中含有原链表 A 中序号为偶数的元素，且保持原来的相对顺序。 【分析】 此题用一个 while 循环来处理，一次循环处理两个结点：将前一个仍留在 a 中，后一个从 a 中删除，链接到 b 的尾部，直到整个链表处理完毕。 【算法】 Int split(LNode *a,LNode *b) /若成功分解，返回 1，否则，返回 0 /a为指向单链表 a的指针， b为指向单链表 B的指针 LNode *cur_a,cur_b,temp; cur_a=a-next; cur_b=Init_List(); if(cur_b=NULL) Return 0; *b=cur_b; while(cur_a!=NULL cur_a=cur_anext; cur_bnext=temp; cur_b=cur_bnext; cur_bnext=NULL; return 1;