《数据结构》课程教学资源（试卷习题）第1章 概论空题（无答案）

第一章概论自测题 姓名 班级」 题号丁 33 15 得分 填空题（每空1分，共33分） 1. 一个计算机系统包括 和 两大部分 一台计算机中全部程序的集合，称为这台计算机的 3.计算机软件可以分为 软件和 软件两大类。科学计算程序包属于」 ，诊断得序显 于 4. 一种用助亿符号来表示机器指令的操作符和操作数的语言是 567 数据结构是力所究非数值计算的程李设计问题中计算机的 它们之间的 和运算等的学科。 为D,R 的有 R是D上的 这三个方面 结物可为两大举。它们公别是 0 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 系 10. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点：最后一个结 点 后续结点，其余每个结点有且只有1个后续结点。 11.在树形结构中，树根结点没有」 结点，其余年个结点有且只有 个前驱结点：叶子结点没有 结 点，其余每个结点的后 续结点数可以 12.在图形结构中，每个结点的前驱结 点数和后续结点数可以 的存 用四种 平的 表示，它们分别是 算法的微 用 有5种，它们分 任何 和若干个被调用的其它函数组成 17. 变量一经说明，就确定该变量的取值范围及 单项选择题（每小题1分，共15分） )1通常所说的主机是指： ACPU B)CPU和内存 CCPU、内存与外存 D)CPU、内存与硬盘 )2,在计算机内部，一切信息的存取、处理和传送的形式是： A)ACSI码 B)BCD码 C二进制 D)十六进制 )3.软件与程序的区别是： A 程序价格便宜、软件价格昂贵： B) 程序是用户自己编写的，而软件是由厂家提供的： 9程序是用高级语言编写的，而软件是由机器语言编写的： D) 件是 序 及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 B单板机 9不装备任何软件的计算机D)只装备操作系统的计算机 A)所有能够使用的软件 B)能被各应用单位共同使用的某种软件 C所有微机上都应使用的基本软件 D)专门为某一应用目的而编制的软 )6.C语言中的常量可分为整型常量、实型常量、字符型常量及 四种。 (A)符号常量 B)长整型常量 (C)逻辑常量 (D)二进制整数 )1.编译程序的功能是： A)发现源程序中的语法错误 B)改正源程序中的语法错误 C)将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高级语言程序 )8.系统软件中最重要的是：

1 第一章 概论 自测题 姓名 班级 题号 一 二 三 四 五 六 总分 题分 33 15 9 8 20 15 100 得分 一、填空题（每空 1 分，共 33 分） 1. 一个计算机系统包括 和 两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的 。 3. 计算机软件可以分为 软件和 软件两大类。科学计算程序包属于 ，诊断程序属 于 。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是 。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中 D 是 的有限集合，R 是 D 上的 有限集合。 7. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是 和 。 9. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 10． 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结 点 后续结点，其余每个结点有且只有 1 个后续结点。 11. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结 点，其余每个结点的后续结点数可以 。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是 。 14. 数据的运算最常用的有 5 种，它们分别是 。 15. 一个算法的效率可分为 效率和 效率。 16. 任何一个 C 程序都由 和若干个被调用的其它函数组成。 17. 变量一经说明，就确定该变量的取值范围及 。 二、单项选择题（每小题 1 分，共 15 分） （ ） 1. 通常所说的主机是指∶ A) CPU B) CPU 和内存 C) CPU、内存与外存 D) CPU、内存与硬盘 （ ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII 码 B) BCD 码 C)二进制 D)十六进制 （ ）3. 软件与程序的区别是∶ A) 程序价格便宜、软件价格昂贵； B) 程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ ）4. 所谓“裸机”是指∶ A) 单片机 B)单板机 C) 不装备任何软件的计算机 D) 只装备操作系统的计算机 （ ）5. 应用软件是指∶ A)所有能够使用的软件 B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件 D) 专门为某一应用目的而编制的软件 （ ）6. C 语言中的常量可分为整型常量、实型常量、字符型常量及 四种。 （A） 符号常量 （B）长整型常量 （C） 逻辑常量 （D）二进制整数 （ ）7. 编译程序的功能是∶ A)发现源程序中的语法错误 B)改正源程序中的语法错误 C)将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高级语言程序 （ ）8. 系统软件中最重要的是∶

A)操作系统 B吲语言处理系统 C工具软件 D)数据库管理系统 ( )9.可移植性最好的计算机语言是： A)机器语言 B)汇编语言 C)高级语言D)自然语言 ( )10.非线性结构是数据元素之间存在一种： 对多天茶 B)多对多关系 C)多对一关系 D)一对一关系 ( )L.数据结构中，与所使用的计算机无 是数据的 的目的 C)逻鞠 D)物理和存储 法的效率以求： ( )13.算法分析的两个主要方面是： A)空间复杂性和时间复杂性 B)正确性和简明性 C)可读性和文档性 D)数据复杂性和程序复杂性 )14.计算机算法指的是 A)计算方法 )排序方法C)解决问题的有限运算序列 D)调度方法 ）15.计算机算法必须具备 前入、出和 等5个特性。 A)可 、可移植性 和可扩充性 、确定性和有穷性 足性 D)易读性、稳定性和安全性 (每小题3 二我情知道机职执行机暴指，为升么它能运行用汇语直和商级语直写的序 共9分) 2数据结构和数据类型两个概念之间有区别吗？ 3.简述线性结构与非线性结构的不同点。 、凤读下C程段。写出湘应的执行果《每4分共8分 printf("Input x): 2.long int fact(n) scanf“%d”,&x): if(20)y=x; else if (x>10)=*x; ifn>)f=n*fact(a-l方 if(x>0&&x30)printf("x=%d.y=%d".xy); else f=l: return(f): else printf“输入数据错I”: 试写出当x分别为18,8时的执行结果。 main() long y; n=5: y=fact(n) printf(%d,%ldn”,n,y片

2 A) 操作系统 B) 语言处理系统 C) 工具软件 D) 数据库管理系统 （ ）9. 可移植性最好的计算机语言是∶ A) 机器语言 B)汇编语言 C) 高级语言 D) 自然语言 （ ）10. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ ）11. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ ）12. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （ ）13. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ ）14. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ ）15. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题（每小题 3 分,共 9 分） 1．我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？ 2.数据结构和数据类型两个概念之间有区别吗？ 3. 简述线性结构与非线性结构的不同点。 四、 阅读下列 C 程序段，写出相应的执行结果（每小题 4 分，共 8 分） 1. printf(“Input x”); scanf(“%d”,&x); if (x20) y=x; else if (x>10) y=2*x; if (x>0&&x1)f=n*fact(n-1); else f=1; return(f); } main() {int n; long y; n=5; y=fact(n); printf(“%d,%ld\n”,n,y); }

五、分析下面各程序段的时间复杂度（每小题5分，共20分） 1.for(i-0:i<n;it+) 2. -0 for(j-0;j<m;j++) for (i=0;i<n;i++) j0店 for() 3.x=0: 4: 六、设有数据逻辑结构S(D,R),试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R, 哪些结点是开始结点，哪些结点是终端结点？（每小题5分，共15分） 1.D={dl,d2,d3,d4 R={dl,d2).(d2,d3,d3,d4} 2.D={d1,d2,",9y R={d1,d2),d1,d3),d3,d4)d3,d6)-d6,d8),d4,d5),(d6,d7),d8.d9)} 3.D={d1,d2,.,d9} R={dl,d3,(dl,d8).(d2,d3).d2,d4.d2,d5).d3,d9,(d5,d6,(d8,d9).d9,d7,(d4,d7(d4,d6} 3

3 五、分析下面各程序段的时间复杂度（每小题 5 分，共 20 分） 六、设有数据逻辑结构 S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系 R， 哪些结点是开始结点，哪些结点是终端结点？（每小题 5 分，共 15 分） 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4)} 2. D={d1,d2,.,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) } 3. D={d1,d2,.,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)} 2. s=0; for (i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s; 1. for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 3. x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++; 4. i=1; while(i<=n) i=i*3;