《据结构习题与解析》（C语言版）

數据结构习题与解析C语言篇) 从逻辑上可以把数据结构分为线性结构和非线性结构。在线性结构中有且仅有一个终 端结点和一个开始结点,并且所有结点都最多只有一个前驱和后续,顺序表就是典型的线性 结构。非线性结构中可能有多个终端结点和多个开始结点,每个结点可能有多个前驱和多个 后续。非线性结构中最重要的是树形结构和图形结构。 l.1.2存储方式 1.线性结构的存储方式 线性结构的数据有顺序、链式素引和散列等四种存储方式。 顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里,结点之间的关 系由存储单元的邻接关系来体现。其优点是占用最少的存储空间,其缺点是由于每个结点只 能使用一整块存储区域,因此可能产生较多的碎片现象。另外,在作插入或删除操作时需移 动大量元素。 链式存储方式是将结点所占的存储单元分为两部分,一部分存放结点本身的信息即为 数据项;另一部分存放该结点的后续结点所对应的存储单元的地址,即为指针项。其优点是 充分利用所有的存储单元,不会出现碎片现象,其缺点是每个结点占用较多的存储空间。 索引方式是用结点的索引号来确定结点存储地址,其优点是检索速度快,其缺点是增加 了额外的素引表会占用较多的存储空间。另外,在增加和删除数据时还要修改索引表因而 会花费较多时间 散列方式是根据结点的值确定它的存储地址其优点是检索、增加和删除结点的操作都 很快,其缺点是采用不好的散列函数时可能出现结点存储单元的冲突,为解决冲突需要额外 的时间和空间开销 2树形结构的存储方式 在树形结构的数据中每个结点可能有多个后续结点因此一般只能采用链接的方式进 行存储链接的方式正好能表达树形结构中的父子和兄弟两种层次关系由于链接的方式不 能表达任意多个儿子结点,所以常常使用较规则的树如二叉树,来限制后续结点的最多个 数。而其他几种存储方式难以达到这种要求 也可以在特定规则的情况下采用顺序结构(如一维数组)来存储树形结构如图1.1的 颗二叉树,用以下数组来存储 图1.1一颗二叉树

第1章概述 3图形结构的存储方式 在图形结构的数据中,每个结点可能有多个前驱结点和多个后续结点因此一般只能采 用链接的方式进行存储同样,由于链接的方式不能表达任意多个后续结点,因此将链接方 式改进成邻接表,即图形结构中的每个结点对应有一个链表,该链表存储这个结点的所有相 邻结点。 另处还可以采用矩阵存储图形结构即用矩阵表示图形结构中任意两个结点之间的关 系,这种矩阵称为邻接矩阵。 1.1.3算法及其评价 算法是解决某一特定类型问题的有限运算序列。描述一个算法可以采用某一种计算机 语言,也可以采用流程图等。本书的算法是采用C语言描述的。 算法具有5个基本持性:有穷性、确定性、可行性输入和输出。 评价一个算法一般从4个方面进行:正确性运行时间、古用空间和简单性。 正确性是指算法是否正确运行时间是指一个算法在计算机上运行所花费的时间,采用 时间复杂度来量度,所谓时间复杂度是指算法中包含简单操作的次数,一般不必精确计算出 算法的时间复杂度,只要大致计算出相应的数量级,如O(1)、O(log2n)、O(n)或O(n2)等。O 的形式定义为:若f(n)是正整数n的函数,则xn=O(f(n)表示存在一个正的常数M,使得 当n≥n时满足|xn≤M(n)。一般地常用的时间复杂度有如下关系 O(1)≤O(logn)≤O(n)≤O(nlg:n)≤O(n)≤O(n)≤…≤O(n)≤O(2) 占用空间是指在计算机存储器上所占用的存储空间,主要考虑在算法运行过程中临时 占用的存储空间的大小,称之为空间复杂度、一般以数址级形式给出。简单性是指算法的易 读性等 例1.分析以下程序段的时间复杂度 for〔i=lai<n;i→+) y=y-1 tor(i=0=(2“n)++) 语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该 妒法的运行时间。在本例算法中,其中语句①的频度是n-1,语句②的频度是(n-1)(2n+ 1)=2n2-n-1。则该程序段的时间复杂度T(n)=2n2-n-1=O(n2)。 例2分析以下程序段的时间复杂度 while (i<=n i=1*2 其中语句①的频度是1,设语句②的频度f(n),则有:

数据结构习题与解析(C语言篇) 即f(n)≤log2n,取最大值fn)=logn 则该程序段的时间复杂度T(n)=1+f(n)=1+ log2n=O(logn)。 例3分析以下程序段的时间复杂度 ① tor(l=2;<=n++) 8=s 其中语句①的频度是2;语句②的频度是n;语句③的频度是n-1;语句④的频度是n l;语句⑤的频度是n-1。则该程序段的时间复杂度T(n)=2+n+3*(a-1)=4a-1=O 例4.有以下程序,分析其中 order()函数的时间复杂度。 inta[]=2,5,1,7,936,8} Int I, temp i(<m) fo(=小<=mri++) If(a[]<a[] temp=aD] a[i]-a[i]; a[]=tem order(. m) maIno) int is order(0·7); for(|=0;<=7;++ print("%d",a[i]) order(函数是一个递归排序过程,设T(m)(n=m+1)是排序n个元素所需要的时间

第L章概述 在排序n个元素时,算法的计算时间主要花费在递归调用 order()上。第一次调用时,处理的 元素个数为n-1,也就是对余下的n-1个元素进行排序,这部分所需要的计算时间应为T n-1) 又因为在其中的循环中,需要n-1次比较,所以排序n个元素所需要的时间为: T(n)=T(n-1)+n-1 这样得到如下方程: T(n)=(r(n-1)+n-1 求解过程为: T(n)=[T(n-2)+(n-2)]+(n-1) [Tn-3)+(n-3)]+(n-2)+(n-1) 1)+1)+2 =0+1+2+,,,+n n(n-1)/2 =O(n2) 故 order()函数的时间复杂度为O(n2)。 1.2基本题 1.2.1单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和 运算等的学科 jA.操作对象B.计算方法C.逻辑存储D数据映象 2A.结构 B.关系 C.运算 D.算法 答:CA2B 2.数据结构被形式地定义为(K,R),其中K是①的有限集合,R是K上的②有限集合 A.算法 B.数据元素C.数据操作D.逻辑结构 2λ.操作 B.映象 C.存储 D.关系 答①B2D 3.在数据结构中,从逻辑上可以把数据结构分成① A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 答: 4线性表的顺序存储结构是一种①的存储结构线性表的链式存储结构是一种②的

数据绪构习题与解析C语言篇 存储结构 A.随机存取B.顺序存取C.索引存取D.散列存取 答:①A②B 5.算法分析的目的是①,算法分析的两个主要方面是② ①A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 ②A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答:①C②A 6.计算机算法指的是①,它必具备输入、输出和②等五个特性 ①A.计算方法 B.排序方法 C.解决问题的有限运算序列D.调度方法 ②A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答:①C②B 7.线性表的逻辑顺序与存储顺序总是一致的,这种说法①。 A.正确 B.不正确 答:O 8.线性表若采用链式存储结构时,要求内存中可用存储单元的地址① A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 答:①D 9.在以下的叙述中,正确的是①。 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.找的操作方式是先进先出 D.队列的操作方式是先进后出 答:①B 0.每种数据结构都具备三个基本运算:插入、删除和查找,这种说法① A.正确 B.不正确 答:①B