《数据结构》第一章习题殷人昆版

《《数据结构》第一章习题殷人昆版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》第一章习题一、判断题(在正确说法的题后括号中打“错误说法的题后括号中打“X”)1、一些表面上很不相同的数据可以有相同的逻辑结构。(“)2、用C语言等高级语言实现的算法就是程序。(X)3、课本P371.5题4、课本P371.6题二、单项选择题1、从逻辑上可以把数据结构分为(C)两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2、程序段for(inti=n-1;i>=1;i-)for(intj=1;jv二i;j++)if(A[j]>A[j+l])AB—//A[j]与A[j+1]交换值

2、其中n为正整数，则最后一行的语句频度在最坏情况下是(A)。A.O(n)B.O(nlogn)C.O(n3)D.O(n2)3、下面说法错误的是(c)(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(”)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(3)同一-个算法，实现语言的级别越高，执行效率就越低A.(1)B.(1),(2)C.(l),(4)D.(3)三、填空题1、数据的逻辑结构是指(从解决问题的需要出发，为实现必要的功能所建立的数据结构)。数据的物

3、理结构包括(顺序结构)的表示和(链式结构)的表示。2、数据结构的抽彖数据类型ADT可用三元组表示(D,S,P),其中D是数据对彖，S是D上的关系集，P是对D的基本操作集。3、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着—(直接存取结构)、(顺序存取结构)和(字典结构)的联系。4、顺序存储结构是通过(顺序表)表示元素之间的关系的；链式存储结构是通过(链表)表示元索之间的关系的。5、一个算法具有5个特性：有穷性、确切性、能行性、有零个或多个输入、有一个或多个输出。6、一算法的时间复杂度为(3n2+2nlog2n+4n-7

4、)/(5n),可近似表示为O(n)o四、综合题1、什么是数据结构？冇关数据结构的讨论涉及哪三个方而？答：数据结构由某一数据元素的集合和该集合中数据元素之间的关系组成。记：Data_Structure={D,R}数据结构包含三个方面：数据的逻辑结构，数据的存储结构和竅据的操作2、数据的存储结构由哪四种基木的存储方法实现？答：顺序存储方法，连接存储方法，索引存储方法，散列存储方法3、评价一个好的算法，可以从哪儿方面来考虑？答，可以从计算机系统，编译器，可用存储空间大小以及比较算法复杂性来评价算法优劣，其中最好的是从比较算法的复杂性來考虑。4、数据

5、结构与数据类型有什么区别？数据结构由某一数据元素的集合和该集合屮数据元素Z间的关系组成。按逻辑关系可以分为线性结构和非线性结构。数据类型是指一种类型，以及定义于这个值集合上的一组操作的总称，数据类型和数据结构的主要区別是前者面向系统，后者面向对象，是高…层的数据抽象，如果程序设计语言提供冇抽象数据类型设施,那么两者可以统一一起5、课本P391.13题1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。表示该遗产继承关系最合适的数据结构应该是（A）oA.树B.图C.数组D.二叉树2、在数据结构

6、屮，从逻辑上可以把数据结构分成（C）。A.动态结构和静态结构C.线性结构和非线性结构3、计算机算法是指（C）。A.计算方法论C.解决问题的有限运算序列4、以下说法正确的是（D）oB.紧凑结构和非紧凑结构D.内:部结构和外部结构B.排序方法D.调试方法A.数据元素是数据的最小单位B.数据项是数据的基木单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构5、在决定选取何种存储结构时，一般不考虑（A）。A.各结点的值如何时B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种结构是否方便6、与线性墩的链接存

7、储相符的特性是（A）oA.插入和删除操作灵活B.需要连续的存储空间C.便于随机访问团D.存储密度大7、在单向循环链表中，基头指针为h,那么p所指结点为尾结点的条件是（D）。A.p=NULLB.p.next=NULLC.p=hD.p.next=h8与线性表的链接存储不相符的特性是（B）A.插入和删除操作灵活B.需要连续的存储空间C.存储空间动态分配权D.需另外开辟空间来保存元素间的关系9、链表不具备的特点是（A）A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比10、带头结点的单链表head为空的

8、判定条件是(B)A.head==NULLB.head.next==NULLC.head.next==headD.head!=NULL