《c语言数据结构》第一章概论 自测题答案

《《c语言数据结构》第一章概论 自测题答案》由会员分享，可在线阅读，更多相关《《c语言数据结构》第一章概论 自测题答案（4页珍藏版）》请在金锄头文库上搜索。

1、第一章概论第一章概论 自测题答案自测题答案 姓名姓名 班级班级 题号题号一一二二三三四四五五六六总分总分题分题分3315982015100得分得分一、填空题（每空一、填空题（每空 1 分，共分，共 33 分）分）1. 一个计算机系统包括一个计算机系统包括 硬件系统硬件系统 和和 软件系统软件系统 两大部分。两大部分。2. 一台计算机中全部程序的集合，称为这台计算机的一台计算机中全部程序的集合，称为这台计算机的 软件资源软件资源 /（系统）（系统） 。3. 计算机软件可以分为计算机软件可以分为 系统系统 软件和软件和 应用应用 软件两大类。科学计算程序包属于软件两大类。科学计算程序包属于 应用软

2、件应用软件 ，诊断程序属于，诊断程序属于 系统软件（工具）系统软件（工具） 。4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是一种用助忆符号来表示机器指令的操作符和操作数的语言是 汇编语言汇编语言 。5. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象操作对象 以及它们之间以及它们之间 的的 关系关系 和运算等的学科。和运算等的学科。 6. 数据结构被形式地定义为（数据结构被形式地定义为（D, R） ，其中，其中 D 是是 数据元素数据元素 的有限集合，的有限集合，R 是是 D 上的上的 关系关系 有限集合。有限集合

3、。 7. 数据结构包括数据的数据结构包括数据的 逻辑结构逻辑结构 、数据的、数据的 存储结构存储结构 和数据的和数据的 运算运算 这三个方面这三个方面 的内容。的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是数据结构按逻辑结构可分为两大类，它们分别是 线性结构线性结构 和和 非线性结构非线性结构 。 9. 线性结构中元素之间存在线性结构中元素之间存在一对一一对一关系，树形结构中元素之间存在关系，树形结构中元素之间存在一对多一对多关系，图形结构关系，图形结构 中元素之间存在中元素之间存在多对多多对多关系。关系。 10 在线性结构中，第一个结点在线性结构中，第一个结点 没有没有 前驱结点

4、，其余每个结点有且只有前驱结点，其余每个结点有且只有 1 个前驱结点；个前驱结点； 最后一个结点最后一个结点 没有没有 后续结点，其余每个结点有且只有后续结点，其余每个结点有且只有 1 个后续结点。个后续结点。 11. 在树形结构中，树根结点没有在树形结构中，树根结点没有 前驱前驱 结点，其余每个结点有且只有结点，其余每个结点有且只有 1 个前驱结个前驱结 点；叶子结点没有点；叶子结点没有 后续后续 结点，其余每个结点的后续结点数可以结点，其余每个结点的后续结点数可以任意多个任意多个 。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以在图形结构中，每个结点的前驱结点数和后续结点数可

5、以 任意多个任意多个 。 13数据的存储结构可用四种基本的存储方法表示，它们分别是数据的存储结构可用四种基本的存储方法表示，它们分别是顺序顺序 、 链式链式 、 索引索引 和和 散列散列 。 14. 数据的运算最常用的有数据的运算最常用的有 5 种，它们分别是种，它们分别是插入插入 、 删除、修改、删除、修改、 查找查找 、排序、排序。 15. 一个算法的效率可分为一个算法的效率可分为 时间时间 效率和效率和 空间空间 效率。效率。16. 00 年省统考年省统考任何一个任何一个 C 程序都由程序都由 一个主函数一个主函数 和若干个被调用的其它函数组成。和若干个被调用的其它函数组成。17. 【0

6、0 年省统考题年省统考题】变量一经说明，就确定该变量的取值范围变量一经说明，就确定该变量的取值范围（即存储单元即存储单元）及及 确定变量确定变量所允许的运算所允许的运算 。二、单项选择题（每小题二、单项选择题（每小题 1 分，共分，共 15 分）分） （ B ） 1. 通常所说的主机是指通常所说的主机是指 A) CPUB) CPU 和内存和内存C) CPU、内存与外存、内存与外存D) CPU、内、内 存与硬盘存与硬盘（ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是在计算机内部，一切信息的存取、处理和传送的形式是 A) ACSII 码码 B) BCD 码码 C)二进制二进制 D)

7、十六进制十六进制 （ D ）3. 软件与程序的区别是软件与程序的区别是 A)程序价格便宜、软件价格昂贵；程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的；程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的；程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只 是软件的一部分。是软件的一部分。 （ C ）4. 所谓所谓“裸机裸机”是指是指 A) 单片机单片机B)单板机单板机C) 不装备任何软

8、件的计算机不装备任何软件的计算机D) 只装备只装备 操作系统的计算机操作系统的计算机 （ D ）5. 应用软件是指应用软件是指 A)所有能够使用的软件所有能够使用的软件 B) 能被各应用单位共同使用的某种软能被各应用单位共同使用的某种软 件件 C)所有微机上都应使用的基本软件所有微机上都应使用的基本软件 D) 专门为某一应用目的而编制的软件专门为某一应用目的而编制的软件 （ A ）6. 00 年省统考年省统考C 语言中的常量可分为整型常量、实型常量、字符型常量及语言中的常量可分为整型常量、实型常量、字符型常量及 (枚举枚举) 四种。四种。 （A）符号常量符号常量 （B）长整型常量）长整型常量

9、（C） 逻辑常量逻辑常量 （D）二）二 进制整数进制整数 （ C ）7. 编译程序的功能是编译程序的功能是 A)发现源程序中的语法错误发现源程序中的语法错误 B)改正源程序中的语法错误改正源程序中的语法错误 C)将源程序编译成目标程序将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高将某一高级语言程序翻译成另一种高 级语言程序级语言程序 （ A ）8. 系统软件中最重要的是系统软件中最重要的是 A) 操作系统操作系统 B) 语言处理系统语言处理系统 C) 工具软件工具软件 D) 数据库数据库 管理系统管理系统 （ C ）9. 可移植性最好的计算机语言是可移植性最好的计算机语言是 A)

10、 机器语言机器语言B)汇编语言汇编语言C) 高级语言高级语言D) 自然语言自然语言 （ B ）10. 非线性结构是数据元素之间存在一种：非线性结构是数据元素之间存在一种： A）一对多关系）一对多关系 B）多对多关系）多对多关系 C）多对一关系）多对一关系 D）一对）一对 一关系一关系 （ C ）11. 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 结构；结构； A) 存储存储 B) 物理物理 C) 逻辑逻辑 D) 物理和存储物理和存储 （ C ）12. 算法分析的目的是：算法分析的目的是： A) 找出数据结构的合理性找出数据结构的合理性 B) 研究算法中

11、的输入和输出的关系研究算法中的输入和输出的关系 C) 分析算法的效率以求改进分析算法的效率以求改进 D) 分析算法的易懂性和文档性分析算法的易懂性和文档性 （ A ）13. 算法分析的两个主要方面是：算法分析的两个主要方面是： A) 空间复杂性和时间复杂性空间复杂性和时间复杂性 B) 正确性和简明性正确性和简明性 C) 可读性和文档性可读性和文档性 D) 数据复杂性和程序复杂性数据复杂性和程序复杂性 （ C ）14. 计算机算法指的是：计算机算法指的是： A) 计算方法计算方法 B) 排序方法排序方法 C) 解决问题的有限运算序列解决问题的有限运算序列 D) 调调 度方法度方法 （ B ）15

12、. 计算机算法必须具备输入、输出和计算机算法必须具备输入、输出和 等等 5 个特性。个特性。 A) 可行性、可移植性和可扩充性可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性可行性、确定性和有穷性C) 确定性、有穷性和稳定性确定性、有穷性和稳定性 D) 易读性、稳定性和安全性易读性、稳定性和安全性三、简答题（每小题三、简答题（每小题 3 3 分分, ,共共 9 9 分）分） 1我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即

13、机器语言）答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言） 。2.【严题集严题集 1.2】数据结构和数据类型两个概念之间有区别吗？数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。的数据元素，而且还在其上定义了一组操作。3. 简述线性结构与非线性结构的不同点。简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是答：线性结构反映结点间的逻辑关系是 一对

14、一的，非线性结构反映结点间的逻辑关系是多对多的。一对一的，非线性结构反映结点间的逻辑关系是多对多的。四、四、00 年统考题年统考题阅读下列阅读下列 C 程序段，写出相应的执行结果（每小题程序段，写出相应的执行结果（每小题 4 分，共分，共 8 分）分）1.printf(“Input x”);scanf(“%d”,if (x20) y=x;else if (x10) y=2*x;if (x0else f=1;return(f);main()int n;long y;n=5; y=fact(n); printf(“%d,%ldn”,n,y); 答：运行结果为：答：运行结果为： 5，120 此题为递归运算此题为递归运算五、五、【严题集严题集 1.8】分析下面各程序段的时间复杂度（每小题分析下面各程序段的时间复杂度（每小题 5 分，共分，共 20 分）分）六、设有数据逻辑结构六、设有数据逻辑结构 S=（D,R） ，试按各小题所给条件画出这些逻辑结构的图，试按各小题所给条件画出这些逻辑结构的图 示，并确定相对于关系示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点？（每，哪些结点是开始结点，哪些结点是终端结点？（每 小题小题 5 分，共分，共 15 分）分）1. 【严蔚敏习题集严蔚敏习题集 P7 1.3】 D=d1,d2,d3,d4d1,d2,d3,d4 R=(d1