主要知识点
1.1数据结构有逻辑结构和物理(存储)结构之分。逻辑结构描述了数据元素的逻辑
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示及元素之间的逻辑关系,与计算机无关。物理结构描述了数据元素的存储表示以及元素之间逻辑关系的存储表示。
1.2 算法的基本特性之有穷性,程序≠算法。
1.3 算法的效率分析,包括时间效率和空间效率。算法的优劣不取决于算法的长短,而取决于算法的时间复杂度。
2.1 线性表的两种基本物理结构——顺序表与链表的特点:
顺序表(顺序存储结构的线性表)存放在一片连续的存储空间中;
链表(链式存储结构的线性表)以结点为基本存储单位,结点之间可不连续;
顺序表与链表的优缺点互补。顺序表的优点是可随机存取,存取速度快= O(1);
链表的优点是插入和删除操作效率高,借助于指针运算而避免了作大量的元素移动,适用于经常需要进行插入和删除操作的线性表。
2.2 循环单链表的首结点和尾结点的判定
设p指向某结点,则p==head->next —— p是首结点
p->next==head —— p是尾结点
3.1 栈和队列是操作受限的特殊线性表,可以是顺序结构也可以是链表结构。特点:先进后出,先进先出。
例题:
1. 设有一个空栈,现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,输出序列是___________________。2 3 5 4 1
2. 设有一个栈,元素的进栈次序为A,B,C,D,E,下列( C )是不可能的出栈序列。
A) A,B,C,D,E B) B,C,D,E,A
C) E,A,B,C,D D) E,D,C,B,A
4.1 广义表的元素、长度及深度
广义表的元素可以是单个元素(原子),也可以是嵌套的广义表(子表)。当广义表GL非空时,称第一个元素ai为表头,其余元素合称为表尾。
广义表表达式中括号的最大嵌套层数称为广义表的深度。
例,A=(a,b,(c,d),(e,(f,g))) 长度=4,即该广义表有4个元素,前2个是原子,后2个是子表,最后一个元素是个嵌套子表。深度为3 。
B=(( )) 长度=1
4.2 广义表的两个基本操作
head(GL) 获取表头,GL是广义表或子表的指针,返回表头的指针;
tail(GL) 获取表尾,GL是广义表或子表的指针,返回表尾的指针。
例题:
1. 对于广义表gl=(a,b,(c,d)),取出原子c的运算可如下:
tail(gl) 得*(b,(c,d))记作p1;
tail(p1)得*(c,d)记作p2;
head(p2)得*c
上述三步操作可表示成:head(tail(tail(gl)))
5.1二叉树的性质
(1)在二叉树的第k(k≥1)层上最多有2k-1个结点。
(2)深度为k(k≥1)的二叉树上至多有2k-1个结点。
(3)任意一棵二叉树中,若叶子结点的个数为n0,度为2的结点的个数为n2,则必有n0=n2+1。
(4)含有n个结点的二叉树的深度至少为「log2(n+1)]。
例题:
已知一棵完全二叉树第4层右端上有6个叶子,则整棵树至多/至少有多少个结点?
解:由题意,该二叉树有5层。根据性质1,第4层上应有23=8个结点,已知有6个叶子,故第5层上至少有2×2-1=3个结点,至多有2×2=4个结点。
由性质2,整棵树至少有15+3=18个结点,至多有15+4=19个结点
5.2 二叉树先序、中序、后序遍历
例题:
设p(x)、m(x)、b(x)分别表示结点x在先序遍历、中序遍历及后序遍历中的序号。
现有两个结点A和B,且A是B的祖先,试问,下面哪些关系是成立的?
p(A)>p(B) p(A)
m(B) m(A)b(B) b(A)=e[2i+1] e[i]>=e[2i+2]——大顶堆
堆排序的时间复杂度为O(nlogn)
但堆排序是不稳定的排序
浙公网安备 33021202002483