一、选择题
1．组成数据的基本单位是( c )。
(A)数据项 (B)数据类型 (C)数据元素(D)数据变量
2．数据结构是研究数据的( c )以及它们之间的相互关系。
(A)理想结构，物理结构 (B)理想结构，抽象结构
(c)物理结构，逻辑结构 (D)抽象结构，逻辑结构3．下列程序的时间复杂度为( A )
for(i=0;i for(j=0;j for(k=0;k c[i][j]= c[i][j]+ a[i][k]* b[k][j]; (A) O(mnt) (B) O(m+n+t) (C) O(m+n) (D) O(mt+n) 4．如果某数据结构的数据元素的集合为S＝{A，B，C，D，E，F，G}，数据元素之间的关系为R＝{＜A，D ＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F＞}，则该数据结构是一种( B )。 (A)线性结构 (B)树结构 (C)图结构 (D)链表结构 5．已知某算法的执行时间为， n为问题规模，则该算法的时间复杂度是( D )。 〔A)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n) 二、填空题 1．一个算法，如果不论问题规模大小，运行所需 时间都一样，则该算法的时间复杂度是___常量阶__。 2．巳知某算法的执行时间为(n+n2)/2+log2 (2n+1)，n为问题规模，则该算法的时间复杂度是___ O(n2)__________。 3．数据结构有线性结构、树结构、___集合、_图 状结构或网状结构等几种逻辑结构。 4．数据结构有_逻辑结构和物理结构等两种物 理结构。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 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. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (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．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 数据结构练习第一章绪论 一、选择题 1.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（）。 A.数据项 B. 数据类型 C.数据元素 D. 数据变量 5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 A. O(n) B. O(nlog 2 n) C. O(n2) D. O(n3/2) 6．下列程序段的时间复杂度为（）。 for(i=0； i 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 第1章习题解答 1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 第一章概论 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D ) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 一、选择题 1、数据结构通常是研究数据的（）及它们之间的相互联系。 A、存储和逻辑结构 B、存储结构 C、顺序结构 D、链式存储结构 2、数据在计算机存储器内表示时，物理地址和逻辑位置相同并且是连续的，称之为（） A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构 3、线性结构是数据元素之间存在一种（） A、一对多关系 B、多对多关系 C、多对一关系 D、一对一关系 4、计算机算法指的是（），它具备输入、输出和（）等五个特性。 1）A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法2）A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、确定性和安全性 5、在计算机中数据有链式和顺序两种存储方式，在存储空间利用率上，链式存储比顺序存储更（） A、高 B、低 C、相同 D、不确定 6、计算机内部数据处理的基本单位是（） A、数据 B、数据元素 C、数据项 D、数据库 7、设语句x++的时间是单位时间，则语句： for(I=1;I<=n;I++) x++; 时间复杂度为（） A、O（1） B、O（n） C、O（n2） D、O（n3） 二、填空题 1、数据结构按逻辑结构可分为两大类，分别是（线性结构）和（非线性结构）。 2、一个算法的效率可分为（时间）效率和（空间）效率。 3、在树型结构中，根结点没有（双亲）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（孩子）结点，其余每个结点的都可以（一个或多个）个这种结点。 4、下面程序段的时间复杂度是（O(N1/2)） I=s=0; while (s 《数据结构》习题集 第一章序论 思考题： 1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型 作业题： 1.2设有数据结构（D，R），其中 D={d1, d2, d3, d4 } R={r1, r2} r1={ (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 数据结构第一章绪论习题 一、【单选题】 1. （A）是数据的基本单位。 Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构 2. （C）是数据的不可分割的最小单位。 Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构 3. 若采用非顺序映象，则数据元素在内存中占用的存储空间（C）。 Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续 4. 若采用顺序映象，则数据元素在内存中占用的存储空间（A）。 Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续 5. 在数据结构中，从逻辑上可以把数据结构分为（C） Ａ、动态结构和静态结构Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构Ｄ、内部结构和外部结构 6. 在树形结构中，数据元素间存在（B）的关系。 Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 7. 下列说法中错误的是（B）。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 8. 计算机算法指的是（C）。 Ａ、计算方法Ｂ、排序方法Ｃ、解决问题的有限运算序列Ｄ、调度方法 9. 下列不属算法特性的是（D）。 Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 10.算法分析的目的是（C）。 Ａ、找出数据结构的合理性Ｂ、研究算法中的输入和输出的关系Ｃ、分析算法的效率以求改进Ｄ、分析算法的易读性和文档性 11.算法分析的两个主要方面是（A）。 Ａ、空间复杂性和时间复杂性Ｂ、正确性和简明性Ｃ、可读性和文档性Ｄ、数据复杂性和程序复杂性 12.算法的计算量的大小称为算法的（A）。 Ａ、效率Ｂ、复杂性Ｃ、现实性Ｄ、难度 13.在下面的程序段中，对x的赋值语句的频度为（C）。 for(i=1;i<=n;++i) for(j=1;j<=n;++j) x=x+1; Ａ、2nＢ、nＣ、n2Ｄ、log2n 14.设n为正整数，则如下程序段中最后一行的语句频度在最坏情况下是（D）。 for(i=n-1;i>=1;--i) for(j=1;j<=i;++j) if(A[j]>A[j+1]) A[j]←→A[j+1]; Ａ、nＢ、n(n-1)/2Ｃ、n(n+1)/2Ｄ、n2 数据结构与算法上机作业第一章绪论 一、选择题 1、数据结构是一门研究非数值计算程序中计算机的○1A 以及它们之间的○2B 和运算等的学科。 ○1 A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映像 ○2 A. 结构 B. 关系 C. 运算 D. 算法 2、线性结构的顺序存储结构是一种○1 A 的存储结构，线性结构的链式存储结构是一种○2 B 的存储结构。 ○1 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 ○2 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 3、下面程序的时间复杂度为 C 。 for(i=0; i 本门课程研究的对象为：数据结构、算法。 一、算法 1.算法具有五个基本特征： (1)有穷性，算法的执行必须在有限步内结束。 (2)确定性，算法的每一步骤必须是确定无二义性的。 (3)可行性，算法中的运算都必须是可以实现的。 (4)输入，算法可以有0个或多个输入。 (5)输出，算法一定有输出结果。 算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。 2.如何衡量一个算法的好坏： 时间复杂度：对一个算法执行效率的度量。 空间复杂度：是指一个算法在执行过程中所占用的存储空间的度量。 3.时间复杂度的计算： 事前分析估算法：通常用高级程序设计语言编写的程序在计算机上运行时消耗的时间取决于下列因素。 (1)算法选用何种策略。 (2)问题的规模。 (3)所使用的程序设计语言，就同一个算法而言，用级别越高的语言实现，其执行的效率越 低。 (4)编译程序所产生的机器代码的质量。 (5)机器执行指令的速度。 4.时间复杂度简单判别： (1)若算法中不存在循环，则算法平均时间复杂度为常量T(n)=O(1)； (2)若算法中仅存在单重循环，则决定算法时间复杂度的基本操作是算法中该循环中语句对 应的基本操作。n为循环语句基本操作执行的次数,平均时间复杂度为T(n)=O(n)；(3)若算法中存在多重循环，则决定算法时间复杂度的基本操作是算法中循环嵌套层数最多 的语句对应的基本操作重复的次数。例如两重循环，外层循环n次，内层循环n次，则平均时间复杂度T(n)=O(n2) 二、数据结构分为两个方面 1.逻辑结构。研究一种数据结构怎么抽象成通用的描述和表示，包括这种结构是什么样的，怎么去操作这种结构以及结构里的元素。这是一种逻辑上的概念，是抽象的。 2.存储结构。研究怎么将一种数据的逻辑结构存储在我们的计算机内存里面，以及怎么使用计算机编程语言实现其对应的操作。这是一种物理上的概念。 而从逻辑上讲，数据结构可以划分为：线性结构、集合结构、树形结构、图状（网状）结构。后三种是非线性的。 而从存储上讲，数据结构可以换分为：顺序存储结构、链式存储结构、索引存储结构、哈希（或散列）存储结构。顺序存储结构、链式存储结构是我们主要学习的对象。数据结构第1章作业
数据结构第一章试题
数据结构练习 第一章 绪论
数据结构课后习题及解析第一章
数据结构课程作业
《数据结构》习题汇编01 第一章 绪论 试题
数据结构作业第1章
数据结构第一章练习题
数据结构第一章课后习题与答案
数据结构作业及答案
数据结构第1章习题解答..
数据结构第1章 练习题及答案
数据结构(C语言版)第一章绪论练习及答案
数据结构习题
《数据结构》吕云翔编著第1章绪论习题解答
数据结构第一章 绪论 答案
数据结构 绪论 关键知识点
相关主题
文本预览