数据结构-严蔚敏6

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

2019/9/28
人民邮电出版社
• (1) 预定义常量及类型
• //函数结果状态代码 • #define OK 1 • #define ERROR 0 • #define INFEASIBLE -1 • #define OVERFLOW -2 • // Status是函数返回值类型，其值是函数结
果状态代码。 • typedef int Status;
（5）赋值语句 （6）选择语句 （7）循环语句
2019/9/28
（8）使用的结束语句形式有：
函数结束语句 return 循环结束语句 break; 异常结束语句 exit（异常代码）；
2019/9/28
（9）输入输出语句形式有： 输入语句 cin (scanf( )) 输出语句 cout (printf( ))
学生数据对象 • 学生记录的集合
2019/9/28
5、数据结构（Data Structure）是相互之间
存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合， “结构”就是指数据元素之间存在的关系。
2019/9/28
数据结构的两个层次：
逻辑结构---
数据元素间抽象化的相互关系，与数据的存储无关，独 立于计算机，它是从具体问题抽象出来的数学模型。
离散数学、C语言 • 3.注意循序渐进：
基本概念、基本思想、基本步骤、算法设计 • 4.注意培养算法设计的能力
理解所讲算法、对此多做思考：若问题要求不同， 应如何选择数据结构，设计有效的算法
2019/9/28
考核方式
• 平时成绩 : 30%
–作业、小测验、实验 –课堂纪律
–无故迟到： –无故旷课：－５ –上机：玩游戏、上网聊天

第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。

（4）链接存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

（7）单链表的存储密度（）。

A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。

（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A．n B．2n-1 C．2n D．n-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。

（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。

31
4、效率与低存储量需求 、
通常，效率指的是算法执行时间；存储量指的是 算法执行过程中所需要的最大存储空间。两者都 与问题的规模有关。
32
算法效率的衡量方法和准则
通常有两种衡量算法效率的方法： 事后统计法 缺点：1、必须执行程序 2、其它因素掩盖算法本质 事后分析估算法 和算法执行时间相关的因素： 1算法选用的策略 2、问题的规模 3、编写程序的语言 4、编译程序产生的机器代码的质量 5、计算机执行指令的速度
5
–例
书目自动检索系统
线性表
书目文件
书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号： 003 高等数学 华罗庚 004 书名： 线性代数 栾汝书 …… 作者名： …… ……
按书名
高等数学 理论力学 线性代数 ……
S01 L01 S01 S02 ……
索引表
按分类号
分类号： 001， 003… … 樊映川 出版单位： 002， … … .. 华罗庚 出版时间： 004， … … 栾汝书 价格： … … ..
29
2、可读性 、
算法主要是为了人的阅读与交流，其次才是为计 算机执行。因此算法应该易于人的理解；另一方 面，晦涩难读的程序易于隐藏较多错误而难以调 试；
30
3.健壮性 健壮性
当输入的数据非法时，算法应当恰当地作出反映 或进行相应处理，而不是产生莫名奇妙的输出结 果。并且，处理出错的方法不应是中断程序的执 行，而应是返回一个表示错误或错误性质的值， 以便在更高的抽象层次上进行处理。
23
1.3 算法和算法分析
算法的概念和描述： 算法的概念和描述： 什么是算法？ 什么是算法？ 算法（ 算法（Algorithm)是为了解决某类问题而规定的一 是为了解决某类问题而规定的一 个有限长的操作序列。 个有限长的操作序列。一个算法必须满足以下五 个重要特性： 个重要特性：