数据结构（C语言版）《严蔚敏、吴伟民编著》课件（习题配套答案）

习题答案

需积分: 9 54 浏览量更新于2023-03-16 评论收藏 393KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

第一章绪论参考答案

一、名词解释（略）

二、填空题

1、数据表示数据处理 2、机内表示

3、逻辑结构逻辑结构上的基本运算存储结构和运算评价和选择

4、逻辑性基本运算 5、存储

6、机外表示逻辑结构存储结构

7、处理要求基本运算和运算算法

8、数据数据元素数据项

9、元素结点顶点记录

10、字段域 11、数据元素数据项

12、集合线性结构树形结构图状结构

13、加工引用 14、定义在 S 上的运算 S 上运算

15、归纳 16、机内表示

17、存储结点数据元素之间关联方式的表示附加设施

18、顺序存储方式链式存储方式索引存储方式散列存储方式

19、给定逻辑结构 S 的存储实现存储映象

20、程序算法设计

21、运行终止的程序可执行部分伪语言算法非形式算法

22、时空性能算法分析 23、正确性能易读性健壮性高效性

24、时间性能（或时间效率）空间性能（或空间效率）计算量存储量

25、标准操作标准操作计算量

26、最坏情况时间复杂性最坏情况时间复杂度平均时间复杂性平均时间复杂度

27、时间复杂性时间复杂度 28、算法输入规模

29、作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数

30、1 log

n n n

实际不可计算高效

31、设计实现

32、数据结构的定义数据结构的实现数据结构的评价选择

33、数据的逻辑结构 34、线性结构非线性结构

34、O（n

） 36、o(log

n)。

三、单项选择题

1.② 2.① 3.② 4.③ 5.① 6.② 7.④ 8.③ 9.③

10.③ 11.② 12.② 13.④ 14.④ 15.②

四、简答及应用

1．凡能被计算机存储、加工的对象通称为数据。

数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话

说，

数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数

据

元素又被称为元素、结点、顶点或记录。

在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的

实际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是

数据的不可分割的最小标识单位。

从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据

可由若干个数据元素构成，而数据元素又可由若干个数据项构成。

２、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间

逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑

结构的以下几点需特别注意：

（１）、逻辑结构与数据元素本身的形成、内容无关。

（２）、逻辑结构与数据元素的相对位置无关。

（３）、逻辑结构与所含结点个数无关。

由此可见，一些表面上很不相同的数据可以有相同的逻辑结构，因此，逻辑

结构是数据组织的某种“本质性”的东西，是数据内部组织的主要方面。

　　　　３、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中

的表示，它包括数据元素的表示及其关系的表示。

　　　　４、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一

个运算的实现是指一个完成该运算功能的程序。

　　　　　　相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。

　　　　　　不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心

是处理步骤。

　　　　５、类Ｃ语言基本上是标准Ｃ语言的简化。类Ｃ语言与标准Ｃ语言的主要区别如

下：

（１）局部量的说明可以省略（但形参表中及函数类型的说明需保留），重要

的变量需在注解中用文字说明基类型和作用。

（２）分情形语句可以采用下述形式：

　switch

{ case 条件１：语句序列１；break;

case 条件 2：语句序列 2；break;

……

case 条件 n：语句序列 n；break;

default: 语句序列 n+1;

}

其中“default: 语句序列 n+1;”可以省略。

（３）不含 goto 语句，增加了一个出错处理语句 error（字符串），其功能

是终止它所在算法的执行并回送表示出错信息的字符串。

（４）输入输出语句有：

输入语句 scanf([格式串]，变量度，……，变量 n);

输出语句 printf([格式串]，变量度，……，变量 n);

(５) 类Ｃ语言的形参书写比标准Ｃ语言简单，如 int abc (int a,int b,int c)可以

简写为 int abc(int a,b,c)。

　　　五．算法设计

　　　　１．（１）int locate(dataytpe A[1..n],dateytpe k)

{ i=n;

26、(p->next!=NULL)&&(p->data!=x)

27、(p!=NULL)&&(p->next!=NULL) p->next

28、mailloc(size) p->next

29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n

)

30、p=q p->next=NULL O(n)

31、单向循环链表（简称循环链表）双向循环链表（简称双链表）

32、NULL 头结点 33、双链表

34、字符数组赋值 35、空 ф 非空字符

36、长度相同子主 37、非紧缩紧缩

38、结点大小不属于字符集的特殊符号

三、单项选择题

1、② 2、① 3、① 4、② 5、① 6、② 7、③ 8、③ 9、④

10、② 11、④ 12、③ 13、⑤ 14、④ 15、③ 16、① 17、② 18、③

19、④ 20、④ 21、④ 22、223、② 24、③ 25、④ 26、② 27、③

28、④ 29、① 30、④ 31、② 32、② 33、④ 34、④ 35、③ 36、③

37、② 38、③ 39、② 40、① 41、④

四、简答及应用

1、线性表的数据元素的类型为 datatype，则在语言上可用下述类型定义来描述顺序表：

const maxsize=顺序表的容量；

typedef struct

{ datatype data[maxsize]

int last;

}sqlist;

sqlist L;

数据域 data 是一个一维数组，线性表的第 1，2……，n 个元素分别存放在此数组

的第 0，1，……，last-1 个分量中，数据域 last 表示线性表当前的长度，而 last-1 是线

性表的终端结点在顺序表中的位置。常数 maxsize 称为顺序表的容量，从 last 到

maxsize-1 为顺序表当前的空闲区（或称备用区）。

Sqlist 类型完整地描述了顺序表的组织。L 被说明为 sqlist 类型的变量，即为一顺

序表，其表长应写为 L.last，而它的终端结点则必须写为 L.data[L.last-1]。

2、假设数据元素的类型为 datatype。单链表的类型定义如下：

typedef struct node *pointer

struct node

{datatype data;

pointer next;

};

typedef pointer lklist;

其中，① ponter 是指向 struct node 类型变量的指针类型;②struct node 是结构

体类型规定一个结点是由两个域 data 和 next 组成的记录，其中 data 的结点的数据

域,next 是结点的链域；③ lklist 与 pointer 相同类型，用来说明头指针变量的类型，因而

lklist 也就被用来作为单链表的类型。

3、typedef struct dnode *dpointer;

struct dnode

{datatype data;

dpointer prior,next;

}

typedaf dpinter dlklist;

链域 prior 和 next 分别指向本结点数据域 data 所含数据元素的直接前趋和直接后继

所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就

得到双向循环链表。

4、顺序串的类型定义与顺序表类似，可描述如下：

　const maxlen=串的最大长度

typedef struct

{char ch[maxlen]

int curlen;

}string

5、链串的类型定义为：

const nodesize=用户定义的结点大小;

typedef struct node *pointer;

struct node

{char ch[nodesize]

poinernext;

}

typedef pointer strlist;

当结点大小为 1 时，可将 ch 域简单地定义为：char ch

6、head 称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头

指针变量是用于存放头指针的变量。

为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，

称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结

点。　

头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的

头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到

头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。

头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表

长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起

来。

7、循环单链表、循环双链表。

8、空串和空格串：含 0 个字符的串称为空串，其长度为 0。空格串是含有一个或多处空格

字符组成的串，其长度不为 0。

串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执

行过程中是可以改变和重新赋值的。

主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所

剩余57页未读，继续阅读

sumencench

粉丝: 1
资源: 12

会员权益专享

数据结构（C语言版）《严蔚敏、吴伟民编著》课件（习题配套答案）

评论0

会员权益专享

最新资源

数据结构（C语言版）《严蔚敏、吴伟民编著》课件（习题配套答案）

评论0

数据结构（C语言版）清华大学严蔚敏、吴伟民编著课本习题答案全部源代码

数据结构（C语言）第二版课后习题答案（严蔚敏 李冬梅 吴伟民）.doc

【免积分】数据结构（严蔚敏、吴伟民）书籍+光盘+笔记+习题答案+课件+讲义

数据结构（c语言版） 严蔚敏吴伟民编著课本买

《数据结构》c语言版 严蔚敏 吴伟民 试题

数据结构c语言版严蔚敏

数据结构c语言版严蔚敏第一版

数据结构 c语言版 严蔚敏

数据结构c语言版 严蔚敏

数据结构c语言版严蔚敏电子版

数据结构c语言版严蔚敏CSDN

数据结构c语言版严蔚敏期末复习考点

数据结构c语言版严蔚敏pdf 带目录

数据结构c语言版本 source 严蔚敏

数据结构c语言版严蔚敏第二版案例2.3 图书信息管理

数据结构(c语言版)严蔚敏,吴伟民清华大学出版社

数据结构题集 c语言版 严蔚敏

《数据结构-c语言版》(严蔚敏,吴伟民版)课本源码

数据结构严蔚敏吴伟民 pdf

数据结构题集c语言版答案严蔚敏

会员权益专享

最新资源

数据结构（C语言）第二版课后习题答案（严蔚敏李冬梅吴伟民）.doc

数据结构（c语言版）严蔚敏吴伟民编著课本买

《数据结构》c语言版严蔚敏吴伟民试题

数据结构 c语言版严蔚敏

数据结构c语言版严蔚敏

数据结构题集 c语言版严蔚敏