数据结构习题汇编01第一章绪论试题

1、数据结构与算法设计习题册第一章绪论一、单项选择题以及它们之间的 和运D.数据映象D.算法1 .数据结构是一门研究非数值计算的程序设计问题中计算机的 算等的学科。A.数据元素B.计算方法C.逻辑存储A.结构B.关系C.运算2 .数据结构被形式地定义为（K, R）,其中K是 的有限集,R是K上的 有限集。A.算法B.数据元素C.逻辑结构D.数据操作A.操作B.存储C.映象D.关系3 .在数据结构中，从逻辑上可以把数据结构分成 。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性2构D.内部结构和外部结构4 .数据结构在计算机内存中的表示是指 。A.数据的存储结构B.数据结构C.数据

2、的逻辑结构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.易读性、稳定性和

3、安全性8 . 在以下叙述中，正确的是 。A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出9 .在决定选取何种存储结构时，一般不考虑 。A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便10 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法11 .下面说法错误的是 。12 .(1)算法原地工作的含义是指不需要任何额外的辅助空间13 .(2)在相同的规模n下，复杂度O(n)的算法在时

4、间上总是优于复杂度O(2n)的算法14 .(3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界15 .(4)同一个算法，实现语句的级别越高，执行效率越低A. (1)B. (1)、(2)C. (1)、(4)D. (3)16 .通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 。A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等17 .以下说法正确的是。A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带结构的各数据项的集合D. 一些表面上很不相同的数据

5、可以有相同的逻辑结构二、填空题1 . 一个数据结构在计算机中的 称为存储结构。2 .数据逻辑结构包括、 和 三种结构,树形结构和图形结构合称为3 .在线性结构中，第一个结点 前驱结点,其余每个结点有且只有 个前驱结点;最后一个结点 后继结点,其余每个结点有且只有个前驱结点。4 .在树形结构中，树根结点没有 结点,其余每个结点有且只有个前驱结点;叶子结点没有结点,其余每个结点的后继结点可以有个。5 .在图形结构中，每个结点的前驱结点数和后继结点数都可以有 个。6 .线性结构中元素之间存在 _一关系，树形结构中元素之间存在关系，图形结构中元素之 间存在 关系。7 . 算法的五个重要特性是 、输入和

6、输出。8 .算法可以用不同的语言描述，如果用 C语言或PASCA用言等高级语言来描述，则算法实现上就是程 序了。这个断言是 (正确的或错误的)。三、简答题1. 设有数据逻辑结构为：2. B=(K,R) K=k1,k2,.,k93. R=<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,4. <k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>5. 画出这个逻辑结构的图示，并确定相对关系R,哪些

7、结点是开始结点，哪些结点是终端结点。6. 设有如图1所示的逻辑结构图示，给出它的逻辑结构。图17. 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种 结构。8. (1) A=(K,R),其中：K=a,b,c,d,e,f,g,h R=r9. r=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>10. (2) B=(K,R)其中：K=a,b,c,d,e,f,g,h R=r11. r=<d,b>,<d,g>,<d,

8、a>,<b,c>,<g,e>,<g,h>,<e,f>12. (3) C=(K,R)其中：K=1,2,3,4,5,6 R=r13. r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)14. 这里的圆括号对表示两结点是双向的。15. (4) D=(K,R)其中：K=48,25,64,57,82,36,75 R=r1,r216. r1=<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>

9、17. r2=<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>18.19. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑四、算法设计题1. 下面程序段的时间复杂度是 。2. for(i=0;i<n;i+)3. for(j=0;j<m;j+)4. Aij=0;5. 下面程序段的时间复杂度是 。6. i=s=0;7. while(s<n)8. i+; s+=i;9. 10. 下面程序段的时间复杂度是 。11. s=0;12. for(i=0;i<n;

10、i+)13. for(j=0;j<n;j+)14. s+=Bij;15. sum=s;16. 下面程序段的时间复杂度是 。17. i=1;18. while(i<=n)19. i=i*3;20.21. 有如下递归函数fact(n),分析其时间复杂度。22. fact(int n)23. if(n<=1) return 1;24. else return (n*fact(n-1);25. 26. 指出下列个算法的时间复杂度。27. (1) prime(int n) m和有n个整数的递减有序数组b1.n,试写一个算法，将数组 a和b归并为递增有序数组c1.m+n,要求算法的时间复杂度为O(m+n)。28. 求解盘片为n的汉诺塔问题的算法如下，分析其算法时间复杂度。29. void hanoi(int n,char x,char y,char z)30. if(n=1) printf( Move disk %d from %c to %c.n ”,n,x,z);31. else32. hanoi(n-1,x,z,y);33. printf( M