数据结构章节练习题及答案2.docx

《数据结构章节练习题及答案2.docx》由会员分享，可在线阅读，更多相关《数据结构章节练习题及答案2.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章线性表1 .具有什么特征的数据结构被称为线性表？线性表是一种最常用、最简单的典型线性数据结构，应用非常广 泛。线性表是由n (n0)个数据元素组成的一个有限序列，线性表 中数据元素的个数n称为线性表的长度。当n=0时，称为空表。对于非空线性表，数据元素之间存在一对一的关系，具体特性如 下：第一个数据元素没有前驱；最后一个数据元素没有后继外；其他数据元素都是首尾相接、有且只有一个前驱和后继。2 .如何实现线性表的顺序存储结构？把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单 元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺 序表。线性表的顺序存储结构有如下特点： 线性表中

2、所有元素所占的存储空间是连续的； 线性表的逻辑顺序与物理顺序一致；数组中的每一个元素的位置可以用公式来确定。假设线性表中 的第一个数据元素的存储地址(指第一个字节的地址，即首地 址)为LOC(ei),每一个数据元素占k个字节，那么线性表中第 i个元素e在计算机存储空间中的存储地址为：LOC(ei)=LOC(e i )+(i-1 )k3.如何实现线性表的4种链式存储结构？数据结构中的每一个数据元素对应于一个存储单元，这种存储单 元称为存储结点，简称结点。每个结点分为两局部：一局部用于存放 数据元素的值，称为数据域；另一局部是指针，用于指向与该结点在 逻辑上相连的其他结点，称为指针域。对于线性表，

3、指针域用于指向 该结点的前一个或后一个结点（即前驱结点或后继结点）。通过结点 的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为 链式存储结构。单向链表：在线性链表中，用一个专门的指针指向线性表中第一 个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的 最后一个结点的指针为空（用NULL或0表示），表示链表终止， 这样的线性链表称为单向链表。下列图是单向链表示意图。线性表的单向链式存储循环链表：将单向链表最后一个结点的指针指向头结点，这样整 个链表就构成一个循环，这种链式存储结构称为单向循环链表，简称 循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链 表中最后一

4、个结点的指针域不再是NULL,而是指向头结点。只有头 结点的循环链表称为空循环链表。下列图是带头结点的非空循环链表和 空循环链表示意图。(a)带头结点的非空循环链表头结点(b)带头结点的空循环链头结点带头结点的循环链表双向链表：双向链表的每个结点含有两个指针域，一个指针指向 其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下列图 (a)所示。双向循环链表：如果将双向链表第一个结点的prev指针指向最(C)双向循环链表(C)双向循环链表(C)双向循环链表后一个结点，将最后一个结点的next指针与指向第一个结点，就构 成了双向循环链表。下列图(b)和(c)是双向链表和双向循环表的逻 辑结构

5、示意图。图双向链表结点结构及双向链表4 ,顺序表和线性链表分别有哪些优点和缺点?线性表的顺序存储与链式存储比拟比拟内容顺序存储链式存储结点存储空间少（不需要为表示结点的逻辑关系增加开销）多（需要增加指针域来表示 结点之间的逻辑关系）空间利用率低（采用数组，按表的最大长 度静态分配存储空间）高（根据表的实际长度动态分配存储空间）插入、删除操作慢（需要大量移动兀素）快（仅更改指针指向，不需 要移动元素）访问元素快（直接访问）慢（通过指针移动才能访问）实现难易程度相对容易（基于数组操作，一 般高级语言都提供数组类型）相对困难（基于指针操作）5 .请列举出一些线性表问题的实例。按员工号排序的员工基本情

6、况表；奥运会各项比赛日程；按学号记录的学生的成绩单；o6 .对于顺序表和单向链表，如何实现统计重复元素个数的操 作？在顺序表中实现统计重复元素个数的操作：在教材的【描述2.1】中，增加一个统计重复元素个数的成员函 数：int Count（const T&x）;/返回 x 出现的次数在教材的【描述2-2】中，增加查找重复元素个数的成员函数的 实现：实现统计重复元素个数templateint LinearList:Count(const T& x)int count=0;for (int i=0; ilength; i+)if(elementi=x)count+;return count;)在顺序表中实现统计重复元素个数的操作：在教材的【描述2-3中，增加一个统计重复元素个数的成员函 数：int Count(const T&x);/返回 x 出现的次数在教材的【描述2-4】中，增加查找重复元素个数的成员函数的 实现：实现统计重复元素个数templateint LinkList:Count(const T& x)(LinkNode * p=head-next;int count=0;while (p!=NULL &)if (p-data =x)count+;p=p-next;)return count;