数构复习提纲

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

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、}elsefor(inti=0;i<2;i++){x[t]=i;Backtrack(t+1);}}试按格式写出调用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

3、，9}构造一棵平衡二叉树(要求保留构造过程中的各棵不平衡二叉树)。 26．对关键字序列503，87，512，61，908，170，897，275，653，426分别执行下列排序算法，写出第1趟排序后的关键字序列：(1)冒泡排序；(2)链式基数排序。  三．设计题(含2个小题，每小题12分，计24分) 27．给定两个带头结点的链表La和Lb，试设计一个高效的算法，将La中自第i个结点起的m个结点，移到Lb中的第j个结点之前。返回链表La和Lb。 28．设计一种二进制编码，使传送数据a，act，case，

4、cat，ease，sea，seat，state，tea的二进制编码长度最短。要求描述：(1)数据对象；(2)权值集；(3)哈夫曼树；(4)哈夫曼编码。  期末复习范围2014年6月6日星期五22:54 数据结构基本概念·数据结构(DataStructure):相互之间存在一种或多种特定关系的数据元素的集合。Ä数据结构研究数据元素之间的相互关系，以及定义在其上的一组基本操作。·数据结构主要包括逻辑结构、存储结构和运算集合三部分的内容。·算法(Algorithm):是规则的有限集合，是求解特定问题的过程描

5、述、操作步骤或指令序列。Ä好的数据结构可以提高算法性能；通过算法研究可以加深理解数据结构。·算法的5个重要特性：1.有穷性(Finiteness)2.确定性(Definiteness)3.可行性(Effectiveness)4.输入项(Input)5.输出项(Output) 算法及其复杂性·算法复杂度：时间复杂度、空间复杂度。·与算法执行时间相关的因素：ü算法选用的策略；ü问题的规模；ü编写程序的语言；ü编译程序产生的机器代码的质量；ü计算机执行指令的速度。·算法所需的存储空间包括：ü输入数据所占的空

6、间；ü程序本身所占的空间；ü辅助变量所占的空间。·算法时间复杂度的估算方法：从算法中选取一种原操作(对于所研究的问题来说，该操作是基本操作)，将该操作重复执行的次数作为算法时间复杂度的衡量准则。时间复杂度与原操作的执行次数之和成正比。·判断算法的时间复杂度，常见的有：O(1)

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

8、t){mid=(left+right)/2;if(key=L[mid].key)returnmid;if(key