数据结构第一章练习题.doc

《数据结构第一章练习题.doc》由会员分享，可在线阅读，更多相关《数据结构第一章练习题.doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构第一章练习题1单项选择题数据结构第一章练习题1、单项选择题1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 A数据元素 B计算方法 C逻辑存储 D数据映像 A结构 B关系 C运算 D算法1.2数据结构被形式的定义为（K,R），其中K是（ ）的有限集，R是K上的（ ）有限集。A算法B数据元素C数据操作D逻辑结构A操

2、作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

3、数据复杂性和程序复杂性1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。A计算方法 B排序方法 C解决问题的有限运算序列 D调度方法A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性1.8在以下的叙述中，正确的是（ ）。A线性表和线性存储结构优于链表存储结构 B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出 D队列的操作方式是先进后出1.9在决定选择何种存储结构时，一般不考虑（ ）。A各结点的值如何 B结点个数的多少C对数据有哪些运算 D所用编程语言实现这种结构是否方便1.10在存储数据时，通常不仅要存储各

4、数据元素的值，而且还要存储（ ）。A数据的处理方法 B数据元素的类型C数据元素之间的关系 D数据的存储方法1.11下面说法错误的是（ ）。（1） 方法原地工作的含义是指不需要额外的辅助空间（2） 在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n)算法（3） 所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界（4） 同一个算法，实现语句的级别越高，执行效率越低A（1） B（10（2） C（1）（4） D（3）1.12通常要求同一逻辑结构中所有数据元素具有相同的特性，这意味着（ ）。A数据元素具有同一特点B不仅数据元素所包含的数据项个数要相同，而且对应的数据项类型要一致C

5、每个数据元素都一样D数据元素所包含的数据项的个数要相等1.13以下说法正确的是（ ）。A数据元素师数据的最小单位B数据项是数据的基本单位C数据结构是带结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构2、设计与分析题2.1设有数据逻辑结构为：B=(K,R)K=k1,k2,，k9R=,画出这个逻辑结构的图示，并确定相对关系R，哪些结点是开始结点，哪些结点是终端结点。k1k2k3k4k8k6k5k7k92.2设有如图所示的逻辑结构图示，给出它的逻辑结构。k1k2k3k4k8k6k5k7k92.3下面程序段的时间复杂度是（ ）。for (i=0;in;i+) for (j=0;jm;

6、j+) Aij=0;2.4下面程序段的时间复杂度是（ ）。 i=s=0; while (sn) i+; /i=i+1 s+=i; /s=s+i2.5下面程序段的时间复杂度是（ ）。s=0;for (i=0;in;i+) for (j+0;jn;j+) s+=Bij;sum=s2.6下面程序段的时间复杂度是（ ）。 i=1 while(in) i=i*3;2.7有如下递归函数fact(n),分析其时间复杂度。fact(int n) if (n1) return 1; else return (n*fact(n-1)2.8求两个n阶矩形的乘法C=A*B,其算法如下：#define MAX 100V

7、oid maxtrixmult(int n, float aMAXMAX),bMAXMAX,float cMAXMAX)int i,j,k;float x;for (i=1;n;i+) / for (j=1;jn;j+) / x=0; / for( k=1;k=n;k+) / x+=aik*bkj; / cij=x; / 3、填空题。1数据的物理结构包括 的表示和 的表示。2. 对于给定的n个元素,可以构造出的逻辑结构有 ， ， ，_ _四种。3数据的逻辑结构是指 。4一个数据结构在计算机中 称为存储结构。5抽象数据类型的定义仅取决于它的一组_ _，而与_ _无关，即不论其内部结构如何变化，只

8、要它的数学特征不变，都不影响其外部使用。6数据结构中评价算法的两个重要指标是 。7. 数据结构是研讨数据的_ _和_ _，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的 算法_。8 一个算法具有5个特性: 、 、 、 、 。9. 下面程序段中带下划线的语句的执行次数的数量级是： 。i=1； WHILE i1) sum=1； for (i=0;sumn;i+) sum+=1; 4、简答题。1. 数据结构是一门研究什么内容的学科？ 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象

9、数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4. 回答问题：（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。（4）评价各种不同数据结构的标准是什么？5评价一个好的算法，您是从哪几方面来考虑的？6解释和比较以下各组概念：（1）算法的时间复杂性 ；（2）算法；（3）频度；7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？8对于一个数据结构，一般包括哪三个方面的讨论？ 9. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？10数据的存储结构由哪四种基本的存储方法实现？ -