数据结构、算法与应用(C++语言描述)》习题参考答案doc

head e1 头结点 …en head 头结点 （a）带头结点的非空循环链表 （b）带头结点的空循环链带头结点的循环链表

双向链表：双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下图（a）所示。

双向循环链表：如果将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的next指针与指向第一个结点，就构成了双向循环链表。下图（b）和（c）是双向链表和双向循环表的逻辑结构示意图。

first end e1 first prev data next （a）双向链表结点结构

e1 e2 （b）双向链表 … en e2 … en （c）双向循环链表

图 双向链表结点结构及双向链表

4．顺序表和线性链表分别有哪些优点和缺点

线性表的顺序存储与链式存储比较

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

①按员工号排序的员工基本情况表； ②奥运会各项比赛日程；

③按学号记录的学生的成绩单； 等等。

6. 对于顺序表和单向链表，如何实现统计重复元素个数的操作

在顺序表中实现统计重复元素个数的操作：

在教材的【描述2-1】中，增加一个统计重复元素个数的成员函数： int Count(const T&x); 一个栈的输入序列为1、2、3，试给出全部可能的出栈序列。

可分为三种情况：

①、当只有一个存储空间时，只有一种出栈序列：1、2、3.

②、当有两个存储空间时，有：1、2、3， 2、1、3， 2、3、1等3种出栈序列 ③、当存储空间大于等于三个时，有：1、2、3， 2、1、3， 2、3、1， 3、2、1

等4种出栈序列。

4．循环队列的优点是什么在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解决这个问题，常用的两种方法是什么

循环队列的优点有两点：一是可以避免发生顺序队列的“假上溢”现象；二是充分利用队列的存储空间。

两种判断队列是“空”还是“满”的方法：一是约定少用一个元素空间；二是使用计数器size记录当前队列的实际长度。

5. 简述在链接栈中插入一个元素的操作过程。

链接栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。 6．请列举出一些可以用栈和队列表示的实际问题。

所有“后进先出”(LIFO，Last In First Out）的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。

所有“先进先出”(FIFO，First In First Out）的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等。

第4章 数组、字符串与广义表

1.具有什么特征的数据结构被称为数组

数组可以看成是形如（index，value）的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；value表示数据元素的值。

2.设有二维数组a[5][6]，每个元素占相邻的8个字节，存储器按字节编址，已知a的起始地址是1000，试计算：

（1）数组a的最后一个元素起始地址； 1000+（30-1）*8=1232。

（2）按行序优先时，元素a[3][5]的起始地址； 1000+（3*6+5）*8=1184

（3）按行列序优先时，元素a[4][3]的起始地址。

1000+（3*5+4）*8=1152 3.请简述数组和矩阵的关系。

矩阵是指纵横排列的二维数据表格。在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。但矩阵的索引通常从1而不是像数组那样从0开始，并且使用A（i，j）而不是A[i，j]的形式来引用矩阵中的元素。 4.矩阵有哪些基本运算

矩阵的操作包括转置、加法、减法和乘法等。

5.稀疏矩阵的特点是什么为什么要对稀疏矩阵采用压缩存储技术

稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。 采用压缩存储技术主要是为了节省空间。

6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+B。 =i;[].c=j; [].d=A[i][j];++; } } } }

==[j].r) { if[i].c<[j].c) { [k].r=[i].r; [k].c=[i].c; [k].d=[i].d; i++;k++; } else if[i].c>[j].c) { [k].r=[j].r; [k].c=[j].c; [k].d=[j].d; j++;k++; } else { v=[i].d+[j].d; if(v!=0) { [k].r=[i].r; [k].c=[i].c; [k].d=v; k++; } i++;j++; } } else if[i].r<[j].r) { [k].r=[i].r; [k].c=[i].c;

[k].d=[i].d; i++;k++; } else { [k].r=[j].r; [k].c=[j].c; [k].d=[j].d; j++;k++; } } if (i== while (j< { [k].r=[j].r; [k].c=[j].c; [k].d=[j].d; j++;k++; } if (j== while (i< { [k].r=[i].r; [k].c=[i].c; [k].d=[i].d; i++;k++; } =k; return 1; }

<<'\\t'<<[i].c<<'\\t'<<[i].d<

述字符串与一维字符型数组的区别与联系。

字符串简称串，它是一种以字符为元素的特殊线性表。字符串可以看成是以字符为元素的一维数组。具体实现时，在C/C++中的字符串使用为字符型数组来表示。为了便于确定字符串的结尾，在字符型数组中使用\\0（就是0）作为字符串的截止符。 8.列举一些需要进行字符串模式匹配的应用场景。

例如，在文本编辑中经常要查找某一特定单词或者一段话在整篇文章中出现的位置，按照姓名查找某个学生、员工、居民。有效的模式匹配能极大地提高文本编辑程序的能力。 9.列举几个字符串的其他操作。

求字符串中某个子串出现的次数，删除满足条件的子串，字符串字符移位等。 10.什么是广义表广义表与线性表的区别是什么

广义表又称列表，是由n（n≥0）个元素组成的有穷序列：GL=（e1，e2，……en），但与线性表不同的是，广义表中的元素允许以不同的形式出现：它可以是一个原子（逻辑上不能