第1章绪论

第第 1 1 章章绪论绪论 1.11.1 知识点：数据结构的定义知识点：数据结构的定义一、填空题填空题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2.数据结构被形式地定义为（ D, R），其中 D 是的有限集合，R 是 D 上的有限集合。 3.数据结构包括数据的、数据的和数据的这三个方面的内容。 4.数据结构按逻辑结构可分为两大类，它们分别是和。 5.对于给定的n个元素,可以构造出的逻辑结构有，，，四种。 6.数据的存储结构可用四种基本的存储方法表示，它们分别是、、和。 7.抽象数据类型是指一个以及定义在该模型上的一组操作。抽象数据类型的定义只取决于它的，而与其在计算机内部如何时表示和实现无关。二、二、判断题判断题 1.（）数据结构的抽象操作的定义与具体实现有关。 2.（）数据的逻辑结构是指数据的各数据项之间的逻辑关系。 3.（）数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 4.（）数据的物理结构是指数据在计算机内的实际存储形式。 5.（）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 6.（）数据结构的抽象操作的定义与具体实现有关。三、三、选择题选择题 1.（）数据结构中，与所使用的计算机无关的是数据的（）结构。 A．存储B.物理C. 逻辑D. 物理和存储 2.（）从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 3.（）以下属于逻辑结构的是（）。 A．顺序表B.哈希表C.有序表D. 单链表 4.（）以下与数据的存储结构无关的术语是（）。 A．循环队列B. 链表C. 哈希表D. 栈 5.（）以下哪一个术语与数据的存储结构无关？ A．栈B. 哈希表C. 线索树D.双向链表 6.（）在计算机的存储器中表示时，个元素的物理地址和逻辑地址的相对顺序相同并且是连续的，称之为（）。 A．逻辑结构B. 顺序存储结构C. 链式存储结构D.以上都对 7.（）可以用（）定义一个完整的数据结构。 A．数据元素B. 数据对象C. 数据关系D. 抽象数据类型四、四、简答题简答题 1.数据结构和数据类型两个概念之间有区别吗？ 2.数据结构是一门研究什么内容的学科？ 3.简述线性结构与非线性结构的不同点。 1.21.2 算法和算法分析算法和算法分析一、一、填空题填空题 1.一个算法的效率可分为效率和效率 2.数据结构中评价算法的两个重要指标是算法的和。二、二、选择题选择题 1.（）算法分析的目的是：()。 A．找出数据结构的合理性B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进D.分析算法的易懂性和文档性 2.（）计算机算法指的是：()。 A．计算方法B. 排序方法C.解决问题的有限运算序列D. 调度方法 3.（）计算机算法指的是（1），它必须具备（2）这三个特性。 (1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性D.易读性、稳定性、安全性 4.（）一个算法应该是（）。 A．程序B.问题求解步骤的描述C.要满足五个基本特性D. A 和 C 5.（）下面关于算法说法错误的是（）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 6.（）有以下算法，其时间复杂度为（）。 void fun (int n) { int i,j,x=0; for(i=1;i=i+1;j--) x++;} A． O(n)B.O(nlog2n)C.O(n 2) D.O(n 3) 7.（）某算法的时间复杂度为 O(n2)，表明该算法的（）。 A．问题规模是 n 2 B. 执行时间等于 n 2 C. 执行时间与 n 2成正比 D. 问题规模与 n 2成正比三、三、判断题判断题 1.() 算法的优劣与算法描述语言无关，但与所用计算机有关。 2.() 程序一定是算法。四、四、简答题简答题 1.分析下面各程序段的时间复杂度四、 2.将下列函数，按它们在 n→∝时的无穷大阶数，从小到大排序。 n, n-n 3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, n!, n2+logn (2)s=0; for i=0; in; i++) for(j=0; jn; j++) s+=B[i][j]; sum=s; (1)for (i=0;in; i++) for (j=0; jm; j++) A[i][j]=0; (3)x=0; for(i=1; in; i++) for (j=1; j=n-i; j++) x++; (4)i=1; while(i=n) i=i*3;