数构复习提纲.pdf

《数构复习提纲.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、..期末考试题型2014年6月6日星期五22:46一．单选题(含20个小题，每小题2分，计40分)二．简答题(含6个小题，每小题6分，计36分)21．综合比较顺序表和链表的主要特点。22．将中缀表达式16–9*(4+3)转换成对应的后缀表达式(要求按人工操作的步骤分步书写或描述)。23．设constintN=3，intx[N]={0};voidBacktrack(intt){if(t+1>N){printf("");for(inti=0;i

2、);}}试按格式写出调用Backtrack(0)的运行结果。24．设二叉树T按照二叉链表存储，试分析下列递归算法的主要功能。intLeafnode(BiTreeT){if(!T)return0;if(!T->Lchild&&!T->Rchild)return1;returnLeafnode(T->Lchild)+Leafnode(T->Rchild);}25．用依次插入关键字的方法，为序列{5，4，2，8，6，9}构造一棵平衡二叉树(要求保留构造过程中的各棵不平衡二叉树)。26．对关键字序列503，87，512，61，908，170，897，275，653，426分别执行下列排序算

3、法，写出第1趟排序后的关键字序列：(1)冒泡排序；(2)链式基数排序。;...三．设计题(含2个小题，每小题12分，计24分)27．给定两个带头结点的链表La和Lb，试设计一个高效的算法，将La中自第i个结点起的m个结点，移到Lb中的第j个结点之前。返回链表La和Lb。28．设计一种二进制编码，使传送数据a，act，case，cat，ease，sea，seat，state，tea的二进制编码长度最短。要求描述：(1)数据对象；(2)权值集；(3)哈夫曼树；(4)哈夫曼编码。期末复习范围2014年6月6日星期五22:54数据结构基本概念数据结构(DataStructure):相互之间

4、存在一种或多种特定关系的数据元素的集合。数据结构研究数据元素之间的相互关系，以及定义在其上的一组基本操作。数据结构主要包括逻辑结构、存储结构和运算集合三部分的内容。算法(Algorithm):是规则的有限集合，是求解特定问题的过程描述、操作步骤或指令序列。好的数据结构可以提高算法性能；通过算法研究可以加深理解数据结构。算法的5个重要特性：1.有穷性(Finiteness)2.确定性(Definiteness)3.可行性(Effectiveness)4.输入项(Input)5.输出项(Output)算法及其复杂性;...算法复杂度：时间复杂度、空间复杂度。与算法执行时间相关的因素：算

5、法选用的策略；问题的规模；编写程序的语言；编译程序产生的机器代码的质量；计算机执行指令的速度。算法所需的存储空间包括：输入数据所占的空间；程序本身所占的空间；辅助变量所占的空间。算法时间复杂度的估算方法：从算法中选取一种原操作(对于所研究的问题来说，该操作是基本操作)，将该操作重复执行的次数作为算法时间复杂度的衡量准则。时间复杂度与原操作的执行次数之和成正比。判断算法的时间复杂度，常见的有：23nO(1)

6、归函数和递归算法斐波那契、双递归函数、汉诺塔、背包问题、棋盘覆盖顺序表、折半查找算法定义：用一组地址连续的存储单元存储线性表的数据元素(a1,a2,⋯,an)。;...顺序表基本操作(1)构造一个空的顺序表；(2)输出顺序表中所有数据元素的值；(3)在第i个数据元素之前插入1个数据元素;(4)查找数据元素值≥e的数据元素;(6)删除顺序表中的第i个数据元素；(7)判断顺序表是否为空表；(8)销毁顺序表。折半查找：intBinSearch(KeyTypekey){left=1;right=L.n;//置区间初值while(left<=right){mid=(left+right)/2

7、;if(key=L[mid].key)returnmid;if(key