数据结构考试题型

1、、单选(？?？ = ?、填空(？? = ?,三、判断(？?？ = ?1、多行注释:2、逻辑结构：集合结构：同属一个整体线性结构：存在明确的顺序关系，1对1树形结构：1对多图形结构：多对多3、物理(存储)结构顺序存储：物理相邻则逻辑相邻链式存储：逻辑相邻，物理不一定相邻4、算法算法定义：求解问题的计算过程的严格描述算法性质：有穷性、可行性、确定性、输入/输出5、常用算法穷举法、贪心法、分治法、回溯法、动态规划6、常见算法时间复杂度常量阶：0(1) 对数阶：O(logn)线性阶：0(n) 线性对数阶：O(n*logn)平方阶：0(?)立方阶：0(?)指数阶(2?)注驾鲤常福比口和以切应的阿数)商写

2、质Ign7、面向对象特点封装、继承、多态8、面向对象程序标准易复用、易扩展、易维护9、组合类型字符串、列表、元组、字典、集合10、类定义变量：保存数据方法：执行功能属性：特殊方法，获取或设置变量11、_init_特殊方法，完成初始化_slots一数据成员限制12、特殊方法_str一对象字符串信息_eq对象判等方法13、运算符重载add二力口法_sub _减法_mul_ 乘法_floordiv_：整除_truediv_:除法14、继承语法子类名后圆括号中列出父类集，如：SubClass(Parent1, Parent2, )Python支持多重继承子类继承父类所有成员15、线性表的定义多个数据元

3、素组成的有限序列，可以为0个通常，数据元素类型相同除首尾元素，每个元素有且仅有一个直接前驱，有且仅有一个直接后继。元素个数称为线性表的长度16、线性表的通用操作初始化操作、清空操作求长度、判空查询：按值查询、按位置查询增加元素：尾部追加、定位插入删除元素：定位删除、按值删除17、顺序表的操作求长度：len(ls) O(1)常量时间判空：长度是否为0 O(1)常量时间按位置查找：ls索引O(1)常量时间；索引合法范围：卜n, n-1按值查找：ls.index(值)，返回指定元素第一次出现的位置，找不到触发异常;顺序查找：O(n)时间复杂度18、顺序表的操作添加元素：可能发生动态扩容尾部追加：Is

4、.append(e) 0(1)定位插入：ls.insert(i, e) 0(n)需要注意的是：Python索引有正向和负向两 种，越界情况，内部处理为头部插入或尾部插入19、顺序表的操作清空操作：ls.clear()列表删除：dells20、单链表逻辑相邻，物理不一定相邻节点(Node):除保存数据信息外，需要存储下一个节点的地址信息21、单链表的操作模仿list,保持接口一致，方便使用特殊方法：初始化、可迭代、索引访问(读、写、删除)、字符串化(_str_通用方法：定位插入、查找指定元素、删除指定元素、清空链表、链表拷贝22、单链表的实现选择头指针头节点：存储额外的头节点，不用额外检查空表情

5、况；头节点数据域可存储 元素个数23、单链表类LinkList定义：初始化操作：初始化头节点重写特殊方法_len_求长度24、单链表类LinkList定义:定位插入：前插：找插入位置的前一个节点，O(n)索引位置处理：支持正向、负向，正向越界处理为尾部插入，负向越界处理 为头部插入修改链接关系，完成新节点插入，0(1)修改元素个数信息25、单链表类LinkList定义：查找指定元素位置：查找第一个匹配元素，找到返回索引，否则抛出异常。 0(n)利用可迭代对象forelse吉构应用26、栈的定义特殊线性表，只在一端操作LIFO (Last in First out):先进后出(后进先出)27、栈

6、的常用操作初始化、判空、入栈、出栈获取栈顶元素(最后入栈的元素)28、栈(Stack)的顺序实现内部采用列表listStack类定义，包含数据成员elems构造方法：初始化为空列表is_empty(self)：判空push(self, elem)：入栈pop(self):出栈，返回栈顶元素；栈空则返回 Nonepeek(self)：获取栈顶元素；栈空则返回29、队列定义特殊线性表，一端进，一端出FIFO) (First in First out):先进先出30、队列的常用操作初始化、判空、入队、出队31、堆定义堆是一棵完全二叉树双亲节点优先级高于或等于子节点(如果存在) 小元素在顶端，则称为小

7、顶堆(最小堆)大元素在顶端，则称为大顶堆(最大堆)32、优先级队列堆实现入队操作：enqueue核心实现上浮 出队操作：dequeue核心实现下沉取顶端元素：peek33、TreeMap常用操作键索引访问值：Mk添加或修改：Mk = v删除：del Mk辅助操作：取第1个元素：first()取最后元素：last()取节点的中序前驱：before(n)取节点的中序后继：after(n) 中序迭代器操作：_iter_()34、图的定义图：Graph顶点：Vertex边：Edge图是由非空的顶点集 V和一个边（弧）集E构成的数据结构。有向图和无向图边集表示顶点之间的邻接关系，两个顶点形成一个二元组（

8、V2, V6）35.图的相关概念1、完全图无向完全图：每两个顶点之间都存在没有方向的一条边有向完全图：每两个顶点之间都存在方向相反的两条边2、顶点的度有向图为出度和入度之和3:边数二各顶点的度数之和的一半3、图的相关概念路径：两个顶点通过相连的边可达，则通过的顶点组成一条路径。路径长度=路径上的边数简单路径：各顶点不重复简单回路：除起点和终点相同的简单路径37 .、图的相关概念连通图：图中任意两个顶点均可达强连通有向图最小连通无向图：n个顶点，n-1条边38、图的相关概念子图、连通子图、连通分量39 .、图的遍历_采度优先从图中某个顶点V0出发，访问此顶点，然后依次从 V0的各个未被访问的 邻

9、接点出发深度优先搜索遍历图，直至图中所有和 V0有路径相通的顶点都被访 问到。40 .、图的遍历广度优先从图中的某个顶点V0出发，并在访问此顶点之后依次访问 V0的所有未被 访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点， 直 至图中所有和V0有路径相通的顶点都被访问到。四、应用题（？?？ = ?'1、给定字符串Sbcd”，求其前缀子用、后缀子串（例如：abcd”，前缀子申 为x+y+d', x为前缀子用，y可以为空；后缀子用为'a+y+x, y可以为空， x为后缀子用）。前缀子用：a,ab,abc后缀子用：d,cd,bcd2、已知有序列1、2、3、

10、4按顺序进行入栈、出栈（1永远在2前入栈，2 永远在1前出栈）。1、2、3、4 （依次入栈、出栈）4、3、2、1 （先全部入栈再全部出栈）合法括号：2 对括号：（）（）、（）（2 种）3 对括号:（）（）（）、（）（）、（）（）、（）、（）（）（5 种）卡特兰数：？?- ?1 （可用来求合法括号的种数，n为括号的对数） n=2? - ? = 2n=3? - ? = 53、已知某系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H其概率分别为：0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11试写出每个字符的哈夫曼编码。A:0001, B:10, C:11

11、10, D:1111, E:110, F:01, G:00001, H:001.4、已知中序遍历、后序遍历画出二叉树并写出先序遍历； 已知先序遍历、中序遍历画出二叉树并写出后序遍历。中序遍历:HDMIBJNEAFKCG 后序遍历：HMIDNJEBKFGCA先序遍历：ABDHIMEJNCFKG 先序遍历为:ABDEGMNCFH,中序遍历为：DBMGNEACHF后序遍历：DMNGEBHFCA5、链表reverse方法代码改错6、birthdayCount 代码改错7、对于一棵3个无编号的节点的有根二叉树，有多少种形态？? - ? = 5（种）8、给定表达式，写出先根、中根、后根表达式表达式：2+ （3*5-1 ）（中根遍历）先根遍历:+2-*351后根遍历：235*1-+9、叶节点（？）和度数为2的节点（？?）之间的关系：证明：？= ?+ 1。二.总度数 n =?+?+ ?边数？?= n- 1?= 2? + ?（度数为2的节点有两条边，度数为1的节点有一条边）由 可得：n- 1 = 2?+