襄樊学院专升本《数据结构》考试大纲和样卷

襄樊学院专升本《数据结构》考试大纲 一、 考试性质 本考试是为在计算机专科生中招收本科生而实施的具有选拔功能的水平考试，其指导思想是既要有利于国家对高层次人材的选拔，又要有利于促进高等学校各类课程教学质量的提高。 二、 考试的基本要求 要求学生比较系统地理解数据结构的基本概念和基本知识，掌握表、栈、队列、树和图等数据结构的基本特征和在计算机上实现的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 和解决问题的能力，以及软件 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和编程能力。 三、 考试方法和考试时间 考试方法为闭卷笔试，考试时间为120分钟。 四、 考试内容和要求 1、 绪论 考试内容:数据结构基本概念和术语，算法、算法的描述和算法分析。 考试要求 （1）了解非数值问题的数学模型不是数学方程，而是表、树和图之类的数据结构。 （2）理解数据、数据元素、数据对象、数据结构和数据类型等的定义。 （3）掌握数据的逻辑结构和存储结构及其种类；算法的重要特征等。 （4）会根据语句的最大频度计算算法的时间复杂度的方法。 2、 线性表 考试内容:线性表的定义、线性表的逻辑结构、线性表的顺序存储结构和链式存储结构，单向链表、循环链表和双向链表，一元多项式的表示及相加。 考试要求 （1）了解线性表的定义和线性结构的特点。 （2）理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。 （3）掌握线性顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的插入、删除等有关操作。 （4）会用单链表编写插入、删除等有关算法。 （5）能够从时间和空间复杂度的角度综合比较两存储结构的特点及适用场合。 3、 栈和队列 考试内容:栈的定义、栈的表示和实现；队列的定义、队列的表示和实现，链队列、循环队列。 考试要求 （1）了解栈和队列的定义。 （2）理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。 （3）掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。 （4）会编写入栈和出栈，入队和出队的有关算法。 4、 串 考试内容:串的有关定义、串的逻辑结构、静态存储结构、动态存储结构和串的基本操作。 考试要求 （1）了解串的有关定义。 （2）理解串的逻辑结构和物理存储结构。 （3）掌握串的模式匹配传统方法。 （4）理解串的模式匹配的KMP算法。 5、 数组和广义表 考试内容:数组的定义和运算、数组的顺序存储结构，特殊矩阵、稀疏矩阵的定义、矩阵的压缩存储，广义表的定义、广义表的存储结构。 考试要求 （1）了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念和链表表示。 （2）理解矩阵的压缩存储的概念。 （3）掌握矩阵的压缩存储的有关计算方法。 （4）掌握一种广义表的链式储方法。 （5）学习利用分治法的算法设计思想编写递归算法。 6、 树和二叉树 考试内容:树的结构定义和基本操作、二叉树的定义、二叉树的性质、二叉树的存储结构、遍历二叉树和线索二叉树，树和森林、树的存储结构、森林与二叉树的转换、树的遍历，最优二叉树和哈夫曼编码。 考试要求 （1）了解树的定义和二叉树的定义。 （2）理解二叉树的性质、二叉树的存储结构。 （3）掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。 （4）会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题，会编写与二叉树有关的算法。 7、 图 考试内容:图的定义和术语、图的存储结构：邻接矩阵和邻接表，图的遍历：深度优先搜索和广度优先搜索，无向图的连通分量和生成树、最小生成树，拓扑排序。 考试要求 （1）了解图的定义和术语，生成树和最小生成树的概念。 （2）理解邻接矩阵中元素的含义和邻接表中结点的含义。 （3）掌握深度优先搜索和广度优先搜索算法。 （4）会用Prim算法和Kruskal算法构造最小生成树，会找出图中顶点的拓扑序列等。 8、 查找 考试内容:静态查找表：顺序查找、二分查找和分块查找，动态查找表：二叉排序树和平衡二叉树，哈希查找、哈希函数的构造方法和处理冲突的方法。 考试要求 （1）了解顺序查找、二分查找和分块查找的概念，二叉排序树和平衡二叉树、哈希查找等的概念。 （2）理解顺序查找、二分查找和分块查找算法，二叉排序树的性质。 （3）掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树的查找、插入和删除操作算法，相关查找方法的ASL。 （4）会用哈希函数、开放地址法或拉链法建立散列表。 9、 内部排序 考试内容:直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序。各种内部排序方法的比较。 考试要求 （1）了解排序算法的稳定性问题。 （2）理解直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想。 （3）掌握直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的算法和时间分析。 （4）会用希尔排序、快速排序、堆排序、二路归并排序方法写出每趟排序的结果，会编写与直接插入排序和简单选择排序有关的算法。 五、 考试题型及大致比例 判断题10%、选择题20%、填空题20%、应用题30%、编程题20%。 六、 考试内容大致比例： 内容 线性表 树和二叉树 图 排序 栈和队 查找 其它 比例 20% 20% 20% 15% 10% 10% 5%                 七、 参考教材 [1]《数据结构》 （C语言版）  严蔚敏  清华大学出版社 [2]《数据结构》              江  涛 中央广播电视大学出版社 [2]《数据结构算法设计指导》  胡学钢  清华大学出版社 襄樊学院专升本《数据结构》考试样卷 一、下列叙述中，你认为正确的小题题号有：                      （10*1`）。 1、 顺序循环队列Q满的条件是：Q.front+1==Q.rear 2、 哈夫曼树中没有度为1的结点。 3、 两分法插入排序所需比较次数与待排序记录的初始排列状态有关。 4、 当待排序记录已经基本有序时，快速排序的执行时间最省。 5、 在等概率查找情况下，分块查找平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 6、 用树的前序遍历和中序遍历结果可以导出树的后序遍历； 7、 树中所有结点的层数之和称为树的高度（深度）。 8、 三元组表是稀疏矩阵的一种顺序存储结构。 9、 直接插入排序是一种就地排序，它需要的辅助空间是O（n） 10、 C = ( ( x , ( a , b ) ) , y )是一个长度为3的广义表。 二、下列各小题提供的选项中，只有一个是正确的，请将你认为正确代码填入下列表格中（14*1.5`） 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 选择                                                           1、若哈夫曼树中其叶结点个数为n,则非叶结点的个数为         。 A  n-1    B  n      C  n+1    D  log2n 2、最优查找树为平均查找路径长度w1h1+ w2h2+……+ wnhn最小的树,其中n表示         。 A  树中叶结点数  B 树中的全部结点数    C 所有非叶结点数  D 查找成功的结点数 3、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？ A. 1，3，2，4      2，3，4，1    4，3，1，2    3，4，2，1 4、下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关？ A. 直接插入排序    . 起泡排序    . 快速排序      直接选择排序 5、若一棵二叉树具有10个度为2的结点，则该二叉树叶结点个数是 A. 9    11      12      不确定 6、在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做    次关键字比较。 A、2  B、3  C、4  D、5 7、对包含N个元素的散列表进行检索，平均检索长度为      。 A、为 o(log2N)  B、为o(N)  C、不直接依赖于N  D、上述三者都不是 8、假定有k个关键字互为同义词（发生冲突）,若用线性探测法把这k个关键字存入散列表中,至少要进行    次探测。 A  k-1    B  k    C  k+1    D  k(k+1)/2 9、给定一个整数集合{3，5，6，9，12}，下列二叉树      是该整数集合对应的哈夫曼（Huffman）树。 10、若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是    A  快速排序    B  堆排序    C  归并排序  D  直接插入排序 11、将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是      A  n  B  2n-1  C （n+1）/2  D  n-1 12、下列      方法可以用来判断出一个有向图中是否有环（回路） A 深度优先遍历  B  拓朴排序  C 求最短路径  D 求关键路径 13、假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为。 A连接  B.模式匹配  C求子串  D求串长 14、 如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用      。 A 快速排序  B.直接插入排序  C.堆排序  D.归并排序 三、 你认为正确的叙述填在各题的下划线上（10*2`）。 1、 串的主要存贮方式有：定长顺序存贮、            和块链存贮。 2、 堆的存储表示是            （顺序的，还是链接的）。 3、 在n个记录的哈希表中进行查找，最少的比较次数是      。 4、 n个顶点的连通图用邻接矩阵表示时,该矩阵至少有          个非零元素. 5、 评价一个算法好坏的主要 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 有            。 6、 若压缩存贮下三角矩阵Am*n的首地址为a,每个元素占空间为b字节,则元素aij的地址为      。 7、 栈和队列都是线性表，其中队列的特点是                      。 8、 若顺序二叉树中编号为n的结点的父结点和右儿子是存在的，则它们的编号应该分别是      9、 若一数组的记录数为400,采用分块查找，块长最好取      。 10、 就排序算法的稳定性而言，希尔排序和快速排序分别是      。 四、 应用题（5*6`） 1、 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。 2、 图1是用邻接表存储的图，画出此图，并写出从C点开始按深度(广度)优先遍历该图的结果，。 3、 试求按关键字序列（12，1，4，3，7，8，10，2）插入生成的二叉排序树和平衡二叉树。 4、 哈希函数为：H(key)=3*key mod  11,开放定址的di=i*(7*key  mod  10  +1) , 在区间[0，10]上构造关键字（22，41，53，46，30，13，01，67）的哈希表，并计算其平均查找长度。 5、 判别以下序列是否为小顶堆，如不是，请把它们整理成一小顶堆。 30，24，36，12，91，53，47，85 ，96 五、算法编程（6`+6`+7`） 1、 以带头结点的循环单链表来表示队列，且只设指向尾结点的尾指针L，试编写相应的队列初始化、入队和出队的算法。 2、 在T所指的二叉排序树中插入一个元素x，使其仍为二叉排序树。 3、 试基于图的深度优先遍历编写一算法，判断邻接表存贮的图G中，顶点v和顶点w是不是连通的。