数构复习提纲.docx

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

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分别执行下列排序算法，写出第1趟排

3、序后的关键字序列：(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、空的顺序表；(2)输出顺序表中所有数据元素的值；(3)在第i个数据元素之前插入1个数据元素;(4)查找数据元素值≥e的数据元素;(6)删除顺序表中的第i个数据元素；(7)判断顺序表是否为空表；(8)销毁顺序表。折半查找：intBinSearch(KeyTypekey){left=1;right=L.n;//置区间初值while(left<=right){mid=(left+right)/2;if(key=L[mid].key)returnmid;if(key

7、ogn)链表、循环链表栈、队列、循环队列哈希表：直接定址法、线性探测再散列、查找方法树的基本概念完全二叉树先序、中序、后序遍历二叉树（非递归）先序后继线索哈夫曼树、哈夫曼编码;...二叉排序树、平衡二叉树插入排序、希尔排序、冒泡排序、树形选择排序快速排序、堆排序、归并排序、基数排序、计数排序图的基本概念与存储结构深度优先搜索遍历、广度优先搜索遍历最小生成树、最短路径、拓扑序列、关键路径1-6设数组A中只存放正数和负数。试