专业课程在职考试大纲.pdf

数据结构 第一章绪论 知识点 1 熟悉数据 数据结构 数据对象 数据元素 存储结构和数据类型等名词术语的含 义 掌握基本概念 特别是数据的逻辑结构和存储结构之间的关系 2 分清那些是逻辑结构的性质 那些是存储结构的性质 复习题 1 什么是数据与数据元素 2 什么是数据结构 什么是数据类型 什么是类型 3 什么是数据的逻辑结构与存储结构 举例说明 4 数据结构与软件的关系是什么 5 解决实际问题时 选取或者设计数据结构的原则是什么 数据 是能输入到计算机中并能被计算机程序处理的符号的总称 数据元素 是数据的基本单位 它在计算机处理和程序设计中通常作为一个整体进行考 虑和处理 一个数据元素可由若干数据项组成 数据对象 是具有相同特征的数据元素的集合 是数据的一个子集 数据结构 是数据元素的组织形式或数据元素相互之间存在一或多种特定关系的集合 数据的存储结构 是数据的逻辑结构在计算机内存中的存储方式 又称物理结构 数据类型 是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合 抽象数据类型 是指一个数学模型以及在该模型上定义的一套运算规则的集合 符合软件应用业务特点的数据结构可以使软件运行效率更高 但软件效率也和编译环 境 操作栈 硬件配置等其他因素有关 通常考虑算法运行所需的存储空间和时间 后 者又涉及四个方面 程序运行时所需输入的数据总量 对源程序编译所需时间 计算机 执行每一条指令所需时间和程序中指令重复执行的次数 6 下面程序的时间复杂度为 C For int i 0 i m i For int j 0 j n j a i j i j AO m2 B O n2 C O n m D O n m 第二章顺序表 知识点 1 了解顺序表的逻辑结构特性是数据元素之间存在着线性关系 熟练使用顺序存储结 构和链式存储结构表示这种关系 2 熟练掌握线性表在顺序存储结构上的基本操作 查找 插入 删除的算法 3 熟练掌握链表中头结点 头指针 和首结点的区别以及循环链表 双链表的的特点 在线性链表 循环链表 双向链表中实现线性表的基本操作 如建立链表 在链表 中查找某个指定元素并求出该指定元素在链表中出现的次数 在链表中插入元素 在链表中删除元素 求链表长度的算法 要求能根据实际的应用选择当前的链表结 构 或者生成新的数据结构 掌握数组的两种存储表示方法以及数组在顺序存储结构中地址计算方法 习题 7 描述以下概念的区别 头指针 头结点 首元节点 头指针变量和头结点的作用 并比 较顺序存储结构和链式存储结构的优缺点 首元结点 是指链表中的存储线性表中的第一个数据元素 a1 的结点 头指针 是指向链表中的第一个结点 或者为头结点或首元结点 的指针 若链表中 附设头结点 则不管线性表是否为空表 头指针均不为空 否则表示空表的链表的头指 针为空 头结点 通常在链表的首元结点之前附设一个结点 称为头结点 头指针变量和头结点的作用 8 在顺序表中 插入或移动一个元素 需要平均移动多少个元素 具体移动元素的个数与 什么有关 n 2 与元素所在的位置有关 9 顺序表中逻辑上相邻的元素的物理位置是否紧邻 数组中已知两个元素位置 如何计算 另一个元素地址 单链表中逻辑上相邻的元素的物理位置是否紧邻 在什么情况下 顺序表比链表好 10 设有一个二维数组 A M N 假设 A 0 0 存放位置在 644 10 A 2 2 在 676 10 每个元 素占一个空间 则 A 3 3 在位置 10 表示用十进制数表示 11 二维数组 A 1 20 1 10 按照行优先顺序存储 每个元素占 4 个单元 且 A 1 1 的地址是 1000 则 A 18 9 的存储地址是 1712 第三章栈和队列 知识点 1 掌握栈和队列的结构特点 2 使用顺序结构实现栈的基本操作 栈的定义 栈的压入 栈的弹出 读栈顶元素 判栈空或满 3 实现队列的基本操作 队列的定义 队列的插入 队列元素的删除 读队列的头结 点 判队列空或满 4 实现循环队列的基本操作 循环队列的定义 队列的插入 队列元素的删除 读队 列的头结点 判队列空或满 5 在相应的实际问题中正确选用它们 如回文的判断 复习题 12 写一个算法 借助栈将一个单链表倒置 template void LList reverse if head next NULL return First fix fence by pushing it forward one step if fence next NULL fence head else fence fence next link temp head next first node except header node while temp NULL push s temp temp temp next while EMPTY S POP s temp fence next temp fence fence next 13 简述栈和队列这两种数据类型的相同点和差异 栈的操作 先进先出 队列先进后出 14 一个栈的入栈序列是 a b c d e 则栈的不可能的输出序列是 C A edcbaB decbaC dceabD abcde 第四章串 知识点 1 掌握串的顺序存储结构和链式存储结构 2 在串的顺序存储结构上实现串的各种操作 连接两个串 取子串 删除子串 插入 子串 求子串的位置 3 在串的链式存储结构上实现串的各种操作 连接两个串 取子串 删除子串 插入 子串 复习题 15 区别空串和空格串 长度不同 空串长度为 0 空格长度为 1 16 设 s I AM A STUDENT t GOOD WORKER CONCAT Substr s 6 2 t A GOOD WORKER 17 广义表 A a 则表尾为空表 第五章二叉树和树 知识点 1 掌握二叉树的定义 性质和存储结构 2 熟练掌握二叉树的前序 中序 后序遍历的递归算法和前序 中序的非递归算法 了解栈在遍历过程中的作用和状态 3 熟练掌握二叉树的层次遍历算法 4 满树和完全树 5 堆 最大堆和最小堆 建立堆的算法 18 已知一颗度为 k 的树中有 n1 个度为 1 的结点 n2 个度为 2 的结点 nk 个度为 k 的结点 问该树中有多少个叶子结点 n1 19 找出满足在先序遍历和中序遍历中 得到的结点访问序列相同的所有二叉树 20 找出满足在后序遍历和中序遍历中 得到的结点访问序列相同的所有二叉树 21 找出满足在先序遍历和后序遍历中 得到的结点访问序列相同的所有二叉树 22 已知二叉树的前序序列为 ABECDFGHIJ 中序序列为 EBCDAFHIGJ 是否能确定唯一 二叉树 如果可以 请画出这棵二叉树并给出其后序序列 可以 Postorder enumeration EDCBIHJGFA INORDER EBDCAFIHGJ 23 假设字符 A B C D E F G F 的使用频度如下表 请构造一棵 Huffman 树 并写出各字母 的 Huffman 哈夫曼 编码 不唯一 计算编码平均长度 ABCDEFGH 255363611104 答案不唯一 因为编码不唯一 但平均码长唯一 Huffman code ABCDEFGH 10010000000101110110010001 24 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 B A 中序遍历B 前序遍历C 后序遍历D 按层次遍历 第六章图 知识点 1 掌握图的定义和术语 图的四种表示方法 数组表示法 邻接表 2 熟练图的两种遍历策略 深度优先和广度优先 3 熟练掌握生成最小生成树的方法 4 求最短路径长度 复习题 25 已知图为无向带权图 1 用 Dijkstra 算法找出从 C 到所有其他节点的最短路径写出邻接矩阵 2 用 Kruskal s 算法找出最小生成树 3 画出 从 A 出发的 DFS 深度优先搜索 树 第九章 查找 知识点 1 掌握顺序表和有序表的查找方法如折半查找 2 熟练掌握哈希表的构造方法以及解决冲突的方法 复习题 26 请写出在线性表 a b c d e f g 中进行折半查找 查关键字等于 e 的过程 A 3 d A 4 e 27 使用封闭哈希 closed hashing 插入码 22 41 53 46 30 13 1 67 到一个 11 槽的哈希表中 槽编号0到10 使用双哈希解决冲突 要使用的哈希函数为H1和H2定义为H1 k 3k mod 11 H2 k 7k mod 10 1 画出所有 8 个码已被插入后的哈希表 描述如何使用 H1 和 H2 进行哈希 H1 22 0 H1 41 2 H1 53 5 H1 46 6 no conflict When H1 30 2 H2 30 1 so 30 enters the 3rd slot H1 13 6 H2 13 2 so 13 enters the 8th slot H1 1 3 H2 1 8 so 1 enters 10 pass by 0 8 5 2 H1 67 3 H2 67 10 so 67 enters 1 pass by 2 226741305346131 012345678910 第十章 内部排序 知识点 熟练掌握各种排序方法 复习题 28 跟踪数组 int a 72 6 57 88 60 42 83 73 48 85 使用快速排序算法的状态 第一遍的 标尺为 60 第二遍是 6 和 73 第三遍为 57 和 88 以此类推 交换排序中如果标尺被交换 则交换者被换到最后位置 initial 72 6 57 88 60 42 83 73 48 85pivot 60 pass 1 48 6 57 42 60 88 83 73 72 85pivot 673 pass 2 6 42 57 48 60 72 73 85 88 83pivot 5788 pass 3 6 42 48 57 60 72 73 85 83 88pivot 4285 pass 4 6 42 48 57 60 72 73 83 85 88 final sorted array 6 42 48 57 60 72 73 83 85 88 补充练习 简答和算法题 29 将两个单链表重新链接成有序单链表 算法讨论 先判断两个链表中有没有空的 再进行边合并边倒置 也可以先合并再统一一 次倒置 每执行完一步需要判断链表是否有已经到尾的 Void Union LinkList a LinkList b LinkList c 已知非递减有序链表 a b 归并得到新链表 c 无重复元素 c LinkList malloc sizeof LNode ap a next bp b next cp c While ap bp 归并 tp LinkList malloc sizeof LNode cp next tp cp tp if ap cp ch bp ch bp bp next else if bp cp ch ap ch ap ap next else if ap ch bp ch cp ch ap ch ap ap next bp bp next else if ap ch bp ch cp ch ap ch ap ap next else cp ch bp ch bp bp next cp next NULL 30 设 n 个人围坐在一个圆桌周围 现在从第 s 个人开始报数 数到第 m 个人 让他出局 然后从出局的下一个人重新开始报数 数到第 m 个人 再让他出局 如此反复直到 所有的人全部出局为止 下面要解决的 Josephus 问题是 对于任意给定的 n s 和 m 求出这 n 个人的出局序列 请以 n 9 s 1 m 5 为例 人工模拟 Josephus 的求解过程以求得问题 的解 出局人的顺序为 5 1 7 4 3 6 9 2 8 31 已知序列 503 87 512 61 908 170 897 275 653 462 请给出采用起泡排序法 和快速排序法对该序列作升序排序时的每一趟的结果 61 503 87 512 170 908 275 897 462 653 61 87 503 170 512 275 908 462 897 653 61 87 170 503 275 512 462 908 653 897 61 87 170 275 503 462 512 653 908 897 61 87 170 275 462 503 512 653 897 908 32 用折半查找找出含有关键字值的记录 若找不到 输出比该值小的最大值或比该值大的 最小值所在记录位置 记录用数组存储 Return position of greatest element K int newbinary int array int n int K int l 1 int r n l and r beyond array bounds while l 1 r Search value not in array 若返回比 K 大的第一个最小整数所在处 修改 return r 且 r n 时返回 ERROR 33 使用 C 抽象类声明一个顺序表 写一个函数交换一个顺序表右方的首两个元素 Interchange the order of current and next elements void switch List L1 Elem temp if L1 remove temp cout ERROR L1 next L1 insert temp 34 列举你所知的各种排序算法并根据算法复杂度进行分类 相邻元素交换 步长为 1 类排序 冒泡排序 插入排序 选择排序 算法复杂度为 O n2 步长非 1 交换间隔不定或者增量类排序 SHELL 排序 交换排序 O nlog2n 其他排序 锦标赛 箱柜排序 树图排序等 35 叙述树的索引方法和哈希方法 树可以克服哈希方法的哪些缺点 36 什么是静态索引结构 什么是动态索引结构 它们各有哪些优缺点 37 线性表可用顺序表或是链表存储 此两种存储表示各有哪些优缺点 38 试编写一个算法 在带表头结点的单链表中寻找第 i 个结点 若找到 则函数返回第 i 个结点的地址 若找不到 则函数返回 0 template ListNode List GetANode int i 取得单链表中第 i 个结点地址 i 从 0 开始计数 i 0 时返回指针 0 i 0 时返回表头结 点地址 if i 1 return NULL ListNode p first int k 0 while p NULL 2 求 n 个整数的和 平方和 平方根取整之和 int Sum int Array int len if len 1 return Array len 1 else returnAr