数据结构习题集（参考）.doc

Heilongjiang University of Science and Technology 数据结构习题集 、 授课教师： 学生姓名： 所在班级： 计算机与信息工程学院 第1章 绪 论 1.1 基本内容 数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；算法的定义、设计的基本要求以及从时间和空间角度分析算法的方法。 学习要点 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。熟悉逻辑结构的四种基本类型和存储结构两种基本机内表示方法。 理解算法五个要素的确切含义：1）动态有穷性（能执行结束）；2）确定性（对于相同的输入执行相同的路径）；3）有输入；4）有输出；5）可行性（用以描述算法的操作都是可实现的）。 掌握计算语句频度和估算算法时间复杂度的方法。 1.3 习题 1、数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。 2、数据结构主要研究的三个内容为 、 以及定义在该结构上的 。 3、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于 。 4、数据结构被形式地定义为（D，R），其中D是 的有限集，R是D上的 有限集。 5、数据结构在计算机内存中的表示是指（ ） A）数据的存储结构 B）数据结构 C）数据的逻辑结构 D）数据元素之间的关系 6、线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。 7、树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。 8、图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9、常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、线性对数阶O(nlog2n)、立方阶O(n3)、指数阶O(2n)等等，这些数量阶之间的大小关系为__________________________ 。 10、算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___ 。 11、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）。 （1） sum=0; for(i=0;in;i++) for(j=0; jn; j++) sum+=a[i][j]; 执行频度： （2） sum=0; for(i=0;in;i++) for(j=0; j=i; j++) sum+=a[i][j]; 执行频度： （3）sum=0; for(i=0;in;i++) for(j=0; jm; j++) sum+=a[i][j]; 执行频度： 12、下述算法的时间复杂度为O（ ） x=2; while(xn/2) x=x*2; 13、下述算法的时间复杂度为O（ ） i=1; while(i=n) i=i*3; 14、下述算法的时间复杂度为O（ ） i=s=0; while(sn){ i++; s+=i; } 第2章 线性表 2.1 基本内容 本章主要讨论了线性表的概念、存储结构以及在各种存储结构下的基本运算的实现。 线性表是一种简单的数据结构，它是由相同数据类型的元素组成的有序序列。线性表常用的存储结构有两类：顺序存储结构和链式存储结构。 在线性表的顺序存储结构中，是将逻辑上相邻的两个元素存储到物理位置也相邻的存储单元里，所以只要知道了第一个元素的