第10章 复杂数据类型.

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第7 章查找 (54)第8 章排序 (65)第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

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

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

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

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

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

例如：整数数据对象是集合N={0，± 1，± 2,, }，字母字符数据对象是集合C={ ‘ A',' B'，,，‘ Z',‘ a','b'，,，' z ' }，学生基本信息表也可是一个数据对象。

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

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

C语⾔各章节知识点总结第⼀部分“C语⾔基础知识”知识点1、C程序的基本结构C程序是由函数构成的。

每个程序由⼀个或多个函数组成，其中必须有且仅有⼀个主函数main( )。

main函数是⼀个可执⾏C语⾔程序的⼊⼝和正常出⼝，⽽不论其在整个程序中书写的位置如何。

在C语⾔中，⼤⼩写字母是有区别的。

（例如习惯使⽤⼩写字母定义变量，⽤⼤写字母定义常量）。

C程序的注释有两种⽅法，⼀种是⾏注释，使⽤“//”；另外⼀种是块注释，使⽤“/* */”，注意“/*”与“*/”不能嵌套使⽤。

C语⾔书写较为灵活，但是提倡采⽤缩进格式进⾏程序书写，以体现语句之间的层次感。

C程序每条语句以“分号”作为结束标志。

以下⼏种情况不得使⽤分号：（1）所定义的函数名称后不得使⽤分号；（2） if…else…语句是⼀个整体，中间不能使⽤分号将其分隔开；（3）预编译命令后不能使⽤分号。

2、C程序开发步骤C语⾔在计算机上的开发过程主要由以下四个步骤组成：第⼀步：编辑。

⽣成后缀名为“.c”的源⽂件第⼆步：编译。

⽣成后缀名为“.obj”的⽬标⽂件第三步：连接。

⽣成后缀名为“.exe”的可执⾏⽂件第四步：运⾏。

3、VC++6.0开发⼯具的使⽤按下功能键Ctrl+F7编译程序；按下功能键F7连接程序；按下功能键Ctrl+F5运⾏程序；若程序在编译和连接过程中有语法错误，则按下功能键F4定位错误所在⾏并根据错误提⽰信息改正错误（原则是先解决error，再解决warning）。

4、C语⾔中标识符的命名规则标识符由字母、数字、下划线组成；规定第⼀个字符必须为字母或下划线。

标识符定义的变量名、函数名、常量名等最好做到“见名知义”；⼤⼩写代表不同含义；不能使⽤关键字；最好不要与C语⾔的库函数同名。

5、C语⾔的数据类型C语⾔的数据类型由基本类型和复杂类型构成。

其中基本数据类型包括字符型（char）、整型（int，short，long）、实型（float，double）；复杂数据类型包括指针类型、数组、结构体、联合体。

第10章结构体与共用体1.以下叙述中错误的是()。

A) 可以通过typedef增加新的类型B) 可以用typedef将已存在的类型用一个新的名字来代表C) 用typedef定义新的类型名后，原有类型名仍有效D) 用typedef可以为各种类型起别名，但不能为变量起别名参考答案：A【解析】关键字typedef的作用只是将C语言中的已有的数据类型作了置换，并不是增加新的类型，所以A)错误。

2．以下关于typedef的叙述错误的是A) 用typedef可以增加新类型B) typedef只是将已存在的类型用一个新的名字来代表C) 用typedef可以为各种类型说明一个新名，但不能用来为变量说明一个新名D) 用typedef为类型说明一个新名，通常可以增加程序的可读性参考答案：A【解析】typedef并不是增加了新类型，而是用一个新名字替代已存在的类型，不能为变量说明一个新名，使用typedef可以增强移植性。

所以A选项错误。

3.若有以下语句typedef struct S{ int g; char h; } T;以下叙述中正确的是A) 可用S定义结构体变量B) 可用T定义结构体变量C) S是struct 类型的变量D) T是struct S类型的变量参考答案：B【解析】本题考查typedef重新声明一种结构体类型，那么T为结构体类型，而不是结构体变量，所以B选项正确。

4.设有以下语句typedef struct TT{ char c; int a[4]; } CIN;则下面叙述中正确的是A) CIN是struct TT类型的变量B) TT是struct类型的变量C) 可以用TT定义结构体变量D) 可以用CIN定义结构体变量参考答案：D【解析】本题考查typedef重新声明一种结构体类型，其中CIN为结构体类型名，而不是结构体变量，所以D 选项正确。

5.以下叙述中错误的是A) 可以用typedef将已存在的类型用一个新的名字来代表B) 可以通过typedef增加新的类型C) 用typedef定义新的类型名后，原有类型名仍有效D) 用typedef可以为各种类型起别名，但不能为变量起别名参考答案：B【解析】本题考查typedef的用法，typedef并不是增加一种新的类型，而是对已存在的类型用一个新的名字来代表，所以B选项错误。

C程序设计复习要点第一章概述1.C程序的构成与结构特点2.C程序上机调试过程与流程第二章数据类型、运算量与表达式1.数据类型的种类（基本数据类型和构造数据类型）2.常量的数据类型及其表示（表示方法、存储字节数与表数范围）——整、实、字符、字符串和转义字符3.变量的命名、定义方法与赋初值4.各种表达式及其运算规则——优先级、结合性、类型自动转换与强制转换●算术运算符、表达式及其构造（注意“/”和“%”特殊性）●自增、自减运算符及其简单表达式运算●赋值运算符及其表达式（注意复合赋值运算符的运算方法）●逗号运算符及其表达式第三章流程控制1.赋值语句的一般形式、赋值过程及赋值规则（注意左右数据类型的一致或兼容）2.输入和输出函数的格式、功能及用法（只要求常用的格式控制符d, f, c, s），提醒注意：●格式输出中域宽和小数位数的控制●格式输入与输出中普通字符的原样输入和输出问题●熟悉并区别以下函数：putchar()、printf()、puts()；getchar()、scanf()、gets()3.关系运算符及其表达式、逻辑运算符及其表达式和条件运算符及其表达式的运算规则（优先级、结合性）4.关系表达式与逻辑表达式的构造（根据已知条件写表达式）5.if语句的三种形式：if …语句、if …else …语句、if 语句的嵌套●if 语句的格式与用法：简单if、嵌套if、并列if●逻辑关系与执行过程●嵌套规则（重点掌握if …else …if …else …if …else）6.switch语句的格式与用法7.*熟练使用if和switch语句阅读和编写较为简单的选择结构程序8.三种循环语句：while() …、do …while()、for()的格式、执行过程及其用法●循环变量初始化、循环条件构造、循环体所要实现的任务和控制变量修改注意循环期间与结束时循环控制变量的取值问题9.结合例题理解和区别break与continue语句的作用及其用法10.本章涉及的主要算法：累加（计数）、累乘、递推、穷举、判素数、求最大公约与最小公倍等11.*熟练使用三种循环语句并结合以上算法阅读和编写较为简单的循环结构及其嵌套程序第四章复杂数据类型1.一维、二维数组的定义、初始化及其引用方法（数据输入、输出、存储与处理）2.字符数组的定义、初始化及其引用（字符串输入、输出、存储与处理）3.常用字符串处理函数：gets()、puts()、strlen()、strcmp()、strcpy()4.数组涉及的主要算法：排序、极值、逆序、回文和字符串的连接、复制、求长度等5.*熟练使用数组并结合以上算法阅读和编写较为简单的程序6.指针的概念：指针、指针变量、指针运算（＊、&、++、--、+、-）7.变量、数组和字符串指针的定义、指向与引用（仅限于一维数组）8.了解指针数组与二级指针的概念和定义9.*能够阅读并理解使用指针进行数据处理的相关程序（极值、逆序、回文和字符串的连接、复制、求长度等）10.结构体与共用体的概念、定义与引用（仅限概念）第五章结构化程序设计与应用1.熟悉程序的三种基本结构：顺序、选择和循环2.*通过其中部分例题掌握选择、循环语句的使用以及循环和数组涉及的主要算法第六章函数与编译预处理1.掌握函数的定义、声明和调用方法及参数传递方式2.*结合相关例题掌握一般函数和递归函数的定义与使用3.熟悉局部变量与全局变量的定义及作用范围，了解各种静态与动态变量的定义、作用范围与生存期4.了解内部函数与外部函数的定义及调用规则5.掌握宏定义与宏展开（重点掌握带参数宏的定义与展开）6.了解文件包含的作用及其使用场合第七章文件1.了解文件的概念2.熟悉文件打开、关闭及各种与文件读写有关函数的格式与用法特别提醒：以上带*部分主要涉及程序阅读、程序填空和编写程序，其余部分主要以选择和概念填空题出现3ae bc C语言程序设计参考题型说明：★本题仅反映考试的题型，作为考前复习参考。

《数据结构》习题集第一章序论思考题：1。

1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型作业题：1。

2设有数据结构（D，R）,其中D={d1, d2, d3, d4}R=｛r1，r2｝r1=｛<d1, d2〉，<d2，d3>，<d3，d4〉，〈d1, d4>，〈d4，d2>, 〈d4, d1〉}r2=｛（d1, d2)，（d1，d3)，（d1, d4)，（d2, d4）, (d2, d3）}试绘出其逻辑结构示意图。

1。

3设n是正整数。

试写出下列程序段中用记号“△”标注的语句的频度: （1）i=1; k=0;while（i〈=n-1）｛△k+=10*i;i++;}（2) i=1； k=0；do {△k+=10＊i;i++；}while（i〈=n-1)（3）i=1； k=0；do {△k+ = 10*i; i++；｝while（i==n）;（4) i=1； j=0；while(i+j≤n) ｛△if（i〈j) i++;else j++;}（5) x=n; y=0; //n是不小于1的常数while（x〉=（y+1）＊（y+1）)｛△y++;｝(6）x=91; y=100；while （ y>0 ）{△if(x>100) ｛ x—=10； y——; }else x++ ；}(7) for( i=0; i〈n； i++）for（ j=i； j〈n; j++）for( k=j； k〈n； k++)△x+=2;1。

4 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。

1.5 已知k阶斐波那契序列的定义为:f0=0,f1=0，……,f k—2=0，f k—1=1；f n=f n—1+f n-2+……+f n-k, n=k,k+1,……试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。