数据结构练习第一章绪论

1、、选择题数据结构练习 第一章 绪论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， 06，03，07，03，08，03，09，则数据结构 A 是（ ）。D. 图型结构二叉树04，02，A. 线性结构 B. 树型结构 C. 物理结构 3下面程序的时间复杂为()for (i=1 ，s=0； i=n ； i+ ) t=1 ；for(j=1 A. O(n)B.O(n 2)C. O(n 3)4数据的最小单位是(）

2、。A. 数据项B. 数据类型5程序段 s=i=0 ；do i=i+1 ； A. O(n)B. O(nlog 2n)6下列程序段的时间复杂度为( for(i=0 ； im ； i+) for(j=0；j=i ；j+) t=t*j ；s=s+t ； D. O(n 4)C.数据元素D.s=s+i ；while(i=n)C. O(n 2)。； jt ； jt数据变量；的时间复杂度为（ D. O（n 3/2）。for(i=0 ； im ； i+) for(j=0 cij=cij+aik*bkjA. O(m*n*t) B. O(m+n+t) C. O(m+n*t) D. O(m*t+n) 7下列程序段的时

3、间复杂度为(i=0 ，s=0； while (sn) s=s+i；i+ ； 1/2 1/3A. O(n 1/2)B. O(n 1/3 )C. O(n)8 A 9 A）。j+) cij=0 ； j+) for(k=0 ； kn ； k+)B. O（n 1/3 ） 某程序的时间复杂度为（ 3n+nlog 2n+n2+8） O（n）B O（nlog 2n） CO（n2）线性表是一个具有 n 个（）的有限序列。 表元素 B .字符 C数据元素 10从逻辑上可以把数据结构分为（ A. 动态结构、静态结构 C.线性结构、非线性结构丨11关于算法的描述，不正确的是（ A. 算法最终必须由计算机程序实现 B

4、.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界C. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态D. 算法的优劣与算法描述语言无关 12在数据结构中，数据的基本单位是A. 数据项 B. 数据元素 13k=1;for （i=0 ；in ；i+ ）for （j=0 ；jn ；j+） Ai j =k+；D. O（n 2）, 其数量级表示为（D O（log 2n）D 数据项D.）B.顺序结构、链式结构初等结构、构造型结构 ）（ ）C. 数据对象 D. 数据文件）。18上述程序段的时间复杂度为A.O（ n2）14. for （i=0 ； for （j=0 ;A i :B.Oim； i+

5、） jn ; j+） Cj : =i*j ；()(n)C.O (2n)D.O (1)上面算法的时间复杂度为（ A.O（m）15从逻辑关系来看，数据元素的直接前驱为 A.线性结构C.线性结构和树型结构16.)B.O( n2)D.下列程序的时间复杂度为（）i=0 ; s=0;while （svn） i+ ； s=s+i ；C.O（nnX n） D.O（m+r）0个或1个的数据结构只能是（B.树形结构线性结构和图状结构A.OC.O (n)D.0 (n2)17.A.最小单位B.最大单位18. 数据的四种基本存储结构是指（A. 顺序存储结构、索引存储结构、直接存储结构、倒排存储结构数据结构中所定义的数据

6、元素，是用于表示数据的（ C.基本单位）D.不可分割的单位B. 顺序存储结构、索引存储结构、链式存储结构、散列存储结构C. 顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D. 顺序存储结构、链式存储结构、19. 下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（A.集合树型存储结构、图型存储结构B.线性结构）数据是数据元素的基本单位数据元素是数据项中不可分割的最小标识单位 数据可由若干个数据元素构成数据项可由若干个数据元素构成20. 下列说法正确的是（A.B.C.D.21 .数据结构的基本任务是（A.逻辑结构和存储结构的设计 C数据结构的评价与选择22. 一个数组元素ai

7、与（A *（a+i） B. a+i C. *a+i23. 对于两个函数，若函数名相同，A.参数类型B.参数个数24. 若需要利用形参直接访问实参，A.指针B .引用 C.25. 下面程序段的时间复杂度为（for（i nt i=0; im; i+）for（i nt j=0; j n; j+）C.树形结构D. 图形结构）B.数据结构的运算实现D.数据结构的设计与实现 ）的表示等价。D. & a+i但只是（）不同则不是重载函数。C.函数类型 则应把形参变量说明为（值）。）参数aij=i*j;A. 0(m2)B. 0(n2)26执行下面程序段时，执行for(int i=1; i=n; i+) for(

8、int j=1; j=i; j+)S;A. n 2B. n2/227下面算法的时间复杂度为int f( unsigned int n ) if ( n=0 | n=1 ) returnA. 0(1)B . 0(n)28组成数据的基本单位是(A. 数据项 B. 数据类型 29如某数据结构的数据元素的集合为 为 R=, ，则该数据结构是一种(A.线性结构B .树结构30下面程序段的时间复杂度为(for(i=1;i=n;i+) for(j=i;j=n;j+) s+;C . 0(m*n)S语句的次数为(D. 0(m+n)。A O(1)BO(n)C. n(n+1)D. n(n+1)/2)。1; else

9、C. 0(n)returnn*f(n-1);D. O(n!)C数据元素D .数据变量S=A,B,C,D,E,F,G ，数据元素间的关系)。C链表结构D.队列结构)。O(nlog2n) D O(n2 )31算法分析的目的是(A.找出数据结构的合理性C. 分析算法的效率以求改进 32算法的计算量的大小称为计算的A.效率33多项选择：A.可行性C. 确定性 34下面说法错误的是(1) 算法原地工作的含义是指不需要任何额外的辅助空间 ( 2) 算法( 3)( 4)A(1)B.(1),(2) C.(1),(4)D.(3)35在数据结构中，从逻辑上可以将之分为 A.动态结构和静态结构B.C. 内部结构和外

10、部结构 36以下数据结构中，哪一个是线性结构(A.广义表 B. 二叉树 C.稀疏矩阵37数据结构中数据元素之间的逻辑关系被称为( )B.D.B. 复杂性一个算法具有(B. 至少有一个输入量D. 健壮性)研究算法中的输入和输出的关系分析算法的易懂性和文档特点)。C. 现实性)等特点。D.难度在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度 0(2n)的所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低)。紧凑结构和非紧凑结构 D. 线性结构和非线性结构 )。D. 串A.数据的存储结构B.数据的基本操作 C.程序的算法 构38在下面的

11、程序段中,对 x 的赋值语句的频度为(FOR i:=1 TOFOR j:=1 TO x:=x+1;A O(2n)D. 数据的逻辑结DODOO(n)CO(n2)D O(log 2n)39以下哪个数据结构不是多型数据类型(A.栈B.广义表40下列数据中,(A.栈B. 队列41以下属于逻辑结构的是(C 有向图)是非线性数据结构。C. 完全二叉树D字符串D. 堆)。C. 有序表A.顺序表 B. 哈希表 42计算算法的时间复杂度是属于一种 ( ) A.事前统计的方法B.事前分析估算的方法C.事后统计的方法D.事后分析估算的方法 43可以用 ( ) 定义一个完整的数据结构 :A. 数据元素 B. 数据对象

12、 C.D. 单链表数据关系D.抽象数据类型44多项选择：数据结构研究的内容涉及 ( ) 。A. 数据如何组织 BC. 数据的运算如何实现 45算法分析的目的是( A. 找出数据结构的合理性 系C. 分析算法的效率以求改进 46多项选择： 设计一个“好A. 是可行的 B. 是健壮的. 数据如何存储D. 算法用什么语言来描述)。B.研究算法中的输入和输出的关D.分析算法的易懂性和文档性的算法应考虑达到的目标有( C. 无二义性 D. 可读性好)。47计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、 输出、( B )等 5 个特性。A. 可执行性、可移植性和可扩充性C. 确定性、有

13、穷性和稳定性 48具有线性结构的数据结构是(A. 图 B. 树49算法分析的目的是(A. 找出数据结构的合理性C.分析算法的效率以求改进C.C)B.D.B.D.D) 广义表可执行性、有穷性和确定性易读性、稳定性和确定性D.研究算法中的输入和输出的关系分析算法的易懂性和文档特点二、填空题 1通常从四个方面评价算法的质量： 、 易读性 强壮性 高效率2个算法的时间复杂度为(n3+n2log2n+14n)/ n2,其数量级表示为 pO(n)3数据的物理结构主要包括 和两种情况。顺序存储结构、链式存储结构4 数据结构从逻辑上划分为三种基本类型：。正确性。线性结构，树型结构，图型结构5. for（i=1

14、 , t=1 , s=0; i=n ； i+） t=t*i ; s=s+t; 的时间复杂度为 。0（n）6. 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、和和所占用的7 评价算法的标准很多，通常是以执行算法所需要的判别一个算法的优劣。8.数据的存储结构被分为、_种。顺序结构、链接结构、索引结构、散列结构 算 法 应具。有穷性、确定性、可行性、输入、输出10. 在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为。逻辑关系11. 存储结点通常有四种基本存储方式，即顺序

15、存储方式、索引存储方式、 和散列存储方式。链式存储和图状结构。树12. 数据的逻辑结构通常包括集合、线性结构、 结构13. 如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为型运算。引用14. 在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为。图结构15. 每个存储结点只含一个数据元素， 所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。 按这种方式 组织起来的存储结构称为。索引结构16. 通常从正确性、易读性、和高效率等4个方面评价算法（包括程 序）的质量。健壮17. 顺序表的存储密度为

16、100% ，而链表的存储密度为 100%。 18表示逻辑关系的存储结构可以有四种方式， 即顺序存储方式、链式存储方式、 和散列存储方式。 索引存储方式19. 数据表示和 是程序设计者所要考虑的两项基本任务。算法设计20. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、和的联系。1:1、1:N、M:N21. 一种抽象数据类型包括 和 个部分。数据定义、操作声明，以节省参数值的或指针形参） 则该形参应说明为22. 当一个形参类型的长度较大时，应最好说明为 传输时间和存储参数的空间。引用形参（。引用23. 当需要用一个形参访问对应的实参时， 类型（或指针类型）的修改，对实参、值24

17、. 在函数中对引用形参的修改就是对相应形参的修改只局限在该函数的内部，不会反映到对应的实参上。头文头文25. 当需要进行标准I/O操作时，则应在程序文件中包含 件，当需要进行文件I/O操作时，则应在程序文件中包含 件。iostream.h 、fstream.h26.在包含有 文件的程序文件中，使用 能够产生出020之间的一个随机整数。stdiib.h 、rand( ) %2127个数组a所占有的存储空间的大小即数组长度为 ,下标为i的元素 ai 的存储地址为 , 或者为28.函数重载要求、_类型、数量、次序 29对于双目操作符，其重载函数带有 勺类型。2、用户自定义 sizeof(a) 、a+

18、i*sizeof(a0) 、a+i个参数，其中至少有一个为或所不同。参数30.若对象ra和rb中至少有一个是属于用户定义的类型，则执行 ra=rb时， 需要调用 载函数，该函数的第一个参数应与 勺类型相同，第二个参数应与的类型相同。=、ra、rb31从一维数组an中顺序查找出一个最大值元素的时间复杂度为 ，输出一个二维数组 bmn中所有元素值的时间复杂度为 。O(n)、O(m* n),p*=j语句的执行次数32.在下面程序段中，s=s+p语句的执行次数为 为 该程序段的时间复杂度为 int i=0,s=0; while(+i1)F面程序段的时间复杂度为i. sum=1ii.for (i=0;s

19、um vn ;i+) sum+=1;O(n)以下是该函数的程序段，请将未完成的部分填入，使之完整int f(m, n)int m,n;if(m=1)return (1) ;44. 设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种 表示方式的数目。例f(5,3)=5 ，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1, 1+1+1+1+1。a)1.a)2.if(n=1)return (2) ;if(m n)return f(m,m);if (m=n)return 1+ (3) ; return f(m, n-1)+f(m-n, (4)执行程序，f(6,4)

20、= 。(1)1 (2)1 (3)f(m, n-1) (4)n 945. 设有两个算法在同一机器上运行，其执行时间分别为100n2和丫，要使前者快于后者，n至少为()。(当 n2n,而 n=15 时 1002)46. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为。问题规模_三、判断题1. ()如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。X)数据元素是数据的最小单元。)数据的基本单位是数据项。 X)数组元素之间的关系，既不是线性的，也不是树形的。)算法和程序没有区别，所以在数据结构中二者是通用的。)算法的优劣与算法描述语言无关，但与所用计算机有关。2

21、. () 一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系 3(4.5.6.7.四、简答题 1简述下列概念 数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计 算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、 顶点、记录等。数据类型是对数据的取值范围、 数据元素之间的结构以及允许施加操作的一种总 体描述。每一种计算机程序设计语言都定义有自己的数据类型。“数据结构”这一术语有两种含义， 一是作为一门课程的名称； 二是作为一个科 学的概念。作

22、为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括 三个方面， 一是数据的逻辑结构， 二是数据的存储结构， 三是对数据进行的操作 （运算）。而数据类型是值的集合和操作的集合， 可以看作是已实现了的数据结 构，后者是前者的一种简化情况。数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或 “邻接关系”） ，数据的存储结构是数据结构在计算机中的表示， 包括数据元素 的表示及其关系的表示。 数据的运算是对数据定义的一组操作， 运算是定义在逻 辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。 数据结构在计算机中的表示称为物理结构， 又称存储结构。 是逻辑结构在存储器

23、中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。 算法是对特定问题求解步骤的一种描述， 是指令的有限序列。 其中每一条指令表 示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输 入和输出。2 数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？ 【解答】数据的逻辑结构分为线性结构和非线性结构。 （也可以分为集合、线性 结构、树形结构和图形即网状结构）。 逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。3试举一个数据结构的例子，叙述

24、其逻辑结构、存储结构、运算三方面的内容。 【解答】学生成绩表，逻辑结构是线性结构， 可以顺序存储（也可以链式存储） ， 运算可以有插入、删除、查询，等等。4简述算法的五个特性，对算法设计的要求。 【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多 个输出。对算法设计的要求： 正确性， 易读性，健壮性，和高的时空间效率 （运算速度快， 存储空间小）。(2) i=1;j=0; while(i+jj)j+; else i+; (4)x=91;y=100; while(y0) if(x100) x=x-10; y-; else x+;5设 n 是正整数，求下列程序段中带 记号的语句

25、的执行次数。（1）i=1;k=0; while（in）k=k+50*i; i+;（3）x=y=0;for（i=0;in;i+） for（j=0;jn;j+）x+;for（k=0;k4 算法A2好于A1。设n是偶数，且有程序段：i:=1 to n Do【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2log n。显 然， 时，11.For if 2*in/2 ”就不再执行。故总的 执行次数为：2 2(n-1)+( n-3)+, +3+1=( n/2) =n/4第一层for循环判断 n+1次，往下执行 n次，第二层 for执行次数为 (n+(n-1)+(n-2)+ , +1)，

26、第三层循环体受第一层循环和第二层循环的控制，其执 行次数如下表：i= 123j=n n n nj=n-1 n-1 n-1 n-1j=3j=2j=112.332 21调用下列C函数f(n)(编者注：略去PASACA函数f(n)回答下列问题：试指出f(n)值的大小，并写出f(n)值的推导过程；假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。C 函数：int f(i nt n) int i,j , k,sum= 0;for(i=l; ivn+1;i+)for(k=1;kvj+1;k+ ) sum+;prin tf(sum=%dn,sum)for(j=n;ji-1; j-)1.2.3.

27、return (sum);【解答】执行次数为(1+2+, +n)+(2+3+, +n)+, +n=n*n(n+1)/2-n(n 2-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15sum=29sum=41sum=50sum=5513设n是偶数，试计算运行下列程序段后 m的值并给出该程序段的时间复杂度。m:=0;FOR i:=1 TO n DOFOR j:=2*i TO n DOm:=m+1;【解答】Omjm的值等于赋值语句m:=m+1的运行次数，其计算式为 五、应用题第一章绪论1.在如下数组A中链接存储了一个线性表，表头指针为A 0.next ，试写出该线性表。A 0123 45 67data605078903440n ext3572041【解答】线性表为：(78, 50, 40, 60, 34, 90)2. 设指针变量P指向双向链表中结点A,指针变量q指向被插入结点B,要求给 出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别 为 llink 和 riink )。【解答】q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;3 .斐波那契数列Fn定义如下F0=