数据结构(c语言版)第三版习题解答

1 《数据结构与算法》（c语言版）期末考复习题

一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构

C．线性结构和非线性结构 D．内部结构和外部结构

2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系

3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理

4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型

C．数据元素之间的关系 D．数据的存储方法

5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少

C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位

2 B．数据元素是数据的最小单位

C．数据结构是带结构的数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

C．分析算法的效率以求改进 C．分析算法的易读性和文档性

（2）A．空间复杂度和时间复杂度 B．正确性和简明性

C．可读性和文档性 D．数据复杂性和程序复杂性

8．下面程序段的时间复杂度是 O(n2) 。

s =0;

for( I =0; i

for(j=0;j

s +=B[i][j];

第1章 绪论

1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中

4,3,2,1ddddD，rR，4,3,3,2,2,1ddddddr

试按图论中图的画法惯例画出其逻辑结构图。

解：

1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：

ADT Complex{

数据对象：D={r,i|r,i为实数}

数据关系：R={}

基本操作：

InitComplex(&C,re,im)

第二章 习题与解答

一 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二 单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；

(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n

3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的； (B) 部分地址必须是连续的；

(C) 一定是不连续的； (D) 连续与否均可以。

4．用链表表示线性表的优点是（ ）。

(A)便于随机存取

(B)花费的存储空间较顺序存储少

(C)便于插入和删除

(D)数据元素的物理顺序与逻辑顺序相同

5． 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

数据结构c语言版第三版习题解答

数据结构 C 语言版第三版习题解答

在学习计算机科学与技术的过程中，数据结构是一门非常重要的基础课程。而《数据结构 C 语言版第三版》更是众多教材中的经典之作。其中的习题对于我们理解和掌握数据结构的概念、原理以及算法实现起着至关重要的作用。接下来，我将为大家详细解答这本书中的一些典型习题。

首先，让我们来看一道关于线性表的习题。题目是这样的：设计一个算法，从一个有序的线性表中删除所有其值重复的元素，使表中所有元素的值均不同。

对于这道题，我们可以采用双指针的方法来解决。定义两个指针 p

和 q，p 指向线性表的开头，q 从 p 的下一个位置开始。当 q 所指向的元素与 p 所指向的元素相同时，我们就将 q 所指向的元素删除，并将 q

向后移动一位。当 q 所指向的元素与 p 所指向的元素不同时，我们将 p

向后移动一位，并将 q 所指向的元素赋值给 p 所指向的位置，然后再将 q 向后移动一位。当 q 超出线性表的范围时，算法结束。

下面是用 C 语言实现的代码：

｀｀｀c

void removeDuplicates(int arr, int n) ｛ int p ＝ 0, q ＝ 1;

while （q ＜ n) ｛

if （arrp ＝＝ arrq) ｛

for （int i ＝ q; i ＜ n 1; i+＋） ｛

arri ＝ arri ＋ 1;

｝

（n)；

｝ else ｛

p+＋；

arrp ＝ arrq;

｝

q+＋；

｝

｝

｀｀｀

再来看一道关于栈的习题。题目是：利用栈实现将一个十进制数转换为八进制数。 我们知道，将十进制数转换为八进制数可以通过不断除以 8 取余数的方法来实现。而栈的特点是后进先出，正好适合存储这些余数。

以下是 C 语言实现的代码：

｀｀｀c

include ＜stdioh>

include ＜stdlibh>

define MAX_SIZE 100