各章例题-数据结构.PDF

各章例题 Contents 1 第1章例题 2 第4章例题 3 第4-1章例题 4 第4-2章例题 5 第5章例题 6 第7章例题 7 第8章例题 8 第9章例题 第1章例题 选择题 在数据结构中，从逻辑上可以把数据结构分成：（ ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 【答案】 C 第1章例题 判断题： 1、每种数据结构的逻辑结构与物理结构总是一致的 （） 2、数据元素是数据的最小单位 （） 3、数据项是具有独立含义的数据最小单位 （） 4、数据结构就是指数据在计算机中的存储结构 （） 【答案】 1、错误 2、错误 3、正确 4、错误 第1章例题 填空题： 1、存储结构的基本类型是 （顺序存储、链式存储、索引存储、散列存储 ）。 2、在算法正确的前提下，评价一个算法的两个标准是 （时间复杂度、空间复杂度 ） 3、数据结构的研究内容包括的三个方面是 （逻辑结构、存储结构、算法 ) 4、若各数据元素之间的逻辑关系可以用一个线性序列简单 的表示出来，则称之为（ 线性结构 ），否则称之为 （非线性结构 ）。 第1章例题 分析题： 设n为正整数，确定下列划线语句的执行频度。 for( i=0; in; i++) for( j=0; ji ; j++) for(k=0; kj; k++) x=x+1; 【分析】 语句的执行频度是该语句重复执行的次数。计算循环语句段中某 一语句的执行次数，要得到语句执行与循环变量之间的关系。 【解答】 这是一个三层嵌套循环，最内层的循环次数由j决定， 次内层的循环次数由i决定，而i从1变化到n。 所以划线语句的执行频度为： n i j i 1 j 1 第4章例题 概念题 1、描述以下三个概念的区别：头指针，头结点，首元结点 （第一个元素结点）。 【解答】 头指针是指向链表中第一个结点（头结点或首元结点） 的指针；在首元结点之前附设的一个结点称为头结点；首元 结点是指链表中存储线性表中第一个数据元素结点。若链表 中附设头结点，则不管线性表是否为空，头指针均不为空， 否则表示空表的链表的头指针为空。 第4章例题 2、简述线性表的两种存储结构的主要优缺点及各自适用的场合。 【分析】 线性表的两种主要存储结构各有其优点和缺点，不能简单地 说哪个好哪个差，要根据实际问题和其适用的场合使用。 【解答】 顺序存储可以按位置直接存取数据元素，方便灵活，效率高， 但插入、删除操作是将引起元素移动，降低了效率；链式存储元