数据结构总结教学内容

1、数据结构总结精品文档命题说明章节第 1 章第 2 章第 3 章第 6 章第 7 章第 9 章第10章备注考核的重点及命题说明各种基本概念和术语 (0 分 )；掌握算法描述和分析的方法(0 分 )线性表的逻辑结构和各种存储表示方法(0 分)；以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算 (0 分)栈和队列的特点 (0 分)；栈在两种存储结构表示时的基本操作实现算法 (0 分)；循环队列和链队列的基本操作实现算法 (0 分)二叉树的各种存储结构的特点(0 分)；二叉树各种遍历策略的递归和非递归算法(0 分)；已知先序序列和中序序列或中序序列和后序序列建立二叉树的方法(0分

2、 )；二叉树的线索化过程； (0 分)树的各种存储结构及特点； (0 分 )建立最优树和哈夫曼编码的方法 (0 分)图的各种存储结构 (0 分)；图的两种搜索路径的遍历（深度和广度） (0 分)；最小生成树 (0 分)；拓扑排序 (0 分)；关键路径 (0 分)；最短路径 (0 分)顺序表和有序表的查找 (0 分)；二叉排序树的构造和查找(0 分 )；哈希表的构造方法 (0 分)各种排序方法的执行过程和其依据的原则 (0 分)；各种排序方法时间复杂度的分析 (0 分)收集于网络，如有侵权请联系管理员删除精品文档一、单项选择（每题2 分，共 20 分）1、分析下面程序段的时间复杂度：()i=1;

3、j=1;while(i<=n)i=i*3;while(j<=n)j+;A、O(n+log 3n)B、O(n)C、 O(log3n)D、 O(n*log 3n)2、下面关于串的的叙述中，哪一个是不正确的：（）A 、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储3、从逻辑上可以把数据结构分为两大类A动态结构、静态结构C线性结构、非线性结构4、若某线性表最常用的操作是存取任（）B顺序结构、链式结构D初等结构、构造型结构一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A 顺序表B双链表C带头结点

4、的双循环链表D单循环链表5、有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341566、最大容量为 n 的循环队列，队尾指针是rear，队头是 front ，则队满的条件是（）A. (rear+1) MOD n=frontB. rear=front收集于网络，如有侵权请联系管理员删除精品文档C rear+1=frontD. (rear-l) MOD n=front7、在一个长度为 n 的顺序表中删除第i 个元素，需向前移动（）个元素。A. nB.i-1C.n-iD.n-i+18、对一颗具有 n 个节点的

5、树，其中所有度之和等于（）。A. nB.n-1C.n-2D.n+19、某二叉树的前序和后序序列正好相反，则该二叉树一定是：()A、高度等于其结点数B、任意一个二叉树C、所有节点均无左孩子D、所有节点均无右孩子10、已知一棵完全二叉树的第6 层（根节点为第一层）有8 个叶子节点，则完全二叉树的节点个数至多是：A、 39B、 52C、111D、119()11、以下数据结构中，（）是非线性数据结构。A 树B字符串C队D栈12、设栈 N 和队列 M 初始状态为空，元素1,2,3,4,5,6依次通过栈 N，一个元素出栈后进队列 M ，若 6 个元素出队的序列是2,4,3,6,5,1,则栈 N 的容量至少

6、应该是：()A、2B、3C、4D、513、一棵完全二叉树上有100 个结点，其中叶子结点的个数是（）A 50B 51C52D4914、有关二叉树下列说法正确的是（）A二叉树的度为2B一棵二叉树的度可以小于2收集于网络，如有侵权请联系管理员删除精品文档C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为 215、一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（）A CABDEFGB ABCDEFGCDACEFBGD ADCFEG二、填空题（每题2 分，共 20 分）1、设一行优先顺序存储的数组A55 ， A00 的地址为 1000，且每个元素占2 个存储单元，则A2

7、3 的地址为。2、设循环队列用数组AM 表示，队首、队尾指针分别是front 和 rear，则循环队列的元素个数为。3、假定一棵二叉树的结点个数为200，则它的深度最少为。4、线性表 L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。5、带头结点的循环链表L 中只有一个元素结点的条件是：_三、简答题（每题5 分，共 1 0 分）1、什么是数据的逻辑结构？数据的逻辑结构主要有哪几种基本的类型？2、线性表有哪几种存储结构？分别有哪些优点？四、综合应用题（每题5 分，共 2 0 分）1、已知一棵二叉树的先序遍历为ABECDFGHIJ ，中序

8、遍历为 EBCDAFHIGJ 。（ 1）给出后序遍历序列，（2）将该二叉树转换为森林。收集于网络，如有侵权请联系管理员删除精品文档2、设有正文 AADBAACACCDACACAADBB,字符集为 A,B,C,D, 设计一套二进制编码，使得上述正文的编码最短。3、画出该逻辑结构的结构图。S=D,R, D=a,b,c,d,e,f,g, R=<a,b>,<b,d>,<c,d>,<e,f>,<f,g>,<c,f>,<d,g>4、已知图如下：(1) 给出该图的邻接矩阵和邻接表；(2) 若从顶点 V 1 出发对该图进行遍历

9、，分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；(3) 给出拓扑排序序列 。V1V2V4V35、给出如下图深度优先和广度优先遍历序列。ABE。CD6、应用普里姆算法和克鲁斯卡尔算法求图的最小生成树。（具体步骤）收集于网络，如有侵权请联系管理员删除精品文档15V0V1531102V59V2301412V4V322(v0,v4),(v0,v1),(v1,v2),(v1,v3),(v1,v5)(v0,v4),(v1,v2),(v1,v3),(v1,v5),(v0,v1)7、下图为带权有向图，求：（ 1）给出拓扑排序序列；（ 2）从顶点 A 到顶点 I 的关键路径。要求：给出具体计算过程，即

10、列出所有事件的最早和最晚开始时间，所有活动的最早和最晚开始时间。B1G2610A4EI417HC542DF8、给出 a 到其他顶点的单源最短路径，根据dijkstra 算法给出计算步骤。5b3da13112c4e9、已知有序顺序表的元素分别为：10,15,20,25,30,35,40,45,50,55,60（ 1）使用顺序查找时查找成功情况下的平均查找长度为多少？收集于网络，如有侵权请联系管理员删除精品文档（ 2）使用折半查找方法，画出二分查找树。10、输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），（ 1）画出按元素排列顺序输入生成的一棵二叉排序树。（ 2）请写出递归算法，从小到大输出该二叉排序树的所有结点。11、设散列函数为 H(K)=K %11, 解决冲突的方法分别为（1）线性探测法和（ 2）链地址法，试将下列关键字集合 35,67,42,21,29,86,95,47依次插入到散列表中（画出散列表的示意图），散列表长度为 11。画出两种冲突解决方法