数据结构复习提纲

资料结构复查简介第一章(1)四种形式的数据结构；(2)算法的五大特征；(3)算法设计要求；(4)算法效率测量方法；第二章(1)线性顺序表示法(2)处理线性表格中的链表现法和拓朴第三章(1)堆栈和队列定义(2)堆栈和队列的基本操作；第四章(1)二叉树的定义；(2)二叉树的本质；(3)二叉树遍历方法；(4)二叉树递归算法；(5)树和二叉树转换(6)森林和二叉树的转换；(7)胡夫曼木结构第五章(1)图的存储结构(2)最小生成树解决方案(3)关键路径解决方案(4)拓扑排序(5)最短路径解决方案第六章(1)二进制排序树的定义(2)二进制排序树配置方法(3)平衡二叉树的定义及其构造方法(4)B- tree定义和组织方法(5)哈希表的定义和组织方法第七章(1)直接对齐(2)对齐定位台阶(3)快速排序(4)选择对齐试卷类型一、选择题1.算法的空间复杂性为()。a)运行算法所需的基本操作数b)算法程序中的指令带数c)运行算法所需的存储空间d)运行算法程序所需的时间2.数据结构是在非数值计算的编程问题上研究计算机的关系和计算等的科学。a)计算过程b)数据元素c)数据操作d)逻辑存储结构以下过程的时间复杂性为()。for(I=0)；I n；I)for(j=0)；j m；j)aIj=0；A) O(m)B) O(n)C) O(m * n)D) O(m/n)4.从长度为n的顺序存储的线性表中删除第I个元素(1In)时，必须首先移动前后()元素。A) n-iB) n-i 1C) n-i-1D) I5.选项()是堆栈和队列的共同点。a)后进先出b)先进先出c)先进先出d)仅允许在端点插入和删除6.包含n个节点的二进制树的层I最多可以包含()个节点。A) 2iB) 2i-1C) 2i-1D) 2n7.如果二叉树T2是从树T1转换的二叉树，则T1中节点的第一个顺序是T2中节点的()。a)第一顺序b)中间顺序c)以下顺序d)无匹配8.使用树叶节点的权重值3，6，8，12生成只有权重路径长度()的半树。A) 38B) 58C) 29D) 559.在具有n个节点的无向图中，如果有e个边，则所有顶点的角度之和为()。A) nB) eC) 2eD) n e10.判断直接图形是否有环(环)的方法是()。a)查找节点角度b)拓扑排序c)查找关键路径d)寻找最短路径二、填空1.数据的逻辑结构分为线性结构和非线性结构，堆栈属于线性结构，树属于结构。2.要在右图所示的双向连接列表中*p之前插入节点*s，请在下面的空间中输入正确的语句。s-prior=p-prior；p-prior=s；s-next=p；节点的子树数称为节点。4.对于任意二叉树t，如果相应的终端节点数为n0，度为2的节点数为N2，则n0和N2之间存在特性。5.如果根的级别为1，则深度为8的完整二进制树至少有一个节点，具有100个节点的完整二进制树的最大级别数为。6.二进制树的第一个和中间顺序遍历序列分别为ABCDEFGH、CBEDFAGH和下一个顺序遍历序列为。7.图的遍历算法首先具有并扩大了搜索遍历算法。8.1，3，9，12，32，41，45，62，75，77，82，95，100的已排序表格。此表格第二次成功寻找值为82的资料。9.对于关键字序列：12、13、11、18、60、15、7、20、25、100，您必须使用筛选方法建立堆集，并以值为的关键字开始。三、简单的回答1.什么是堆栈？将堆栈数据移动到堆栈和堆栈之外的原则是什么？2.什么是二进制排序树？气泡排序的基本思路简述。4.使用Prim (prim)算法配置下图中的最小生成树之一。建立此最小跨距树状目录的每个层级。5.下图中显示的AOE网络(顶点v1、v2、v3、v4、v5、v6表示事件；弧A、B、C、D、E、F、G、H表示活动)，然后回答以下问题：(1)求出所有事件的最早发生时间和最晚发生时间。(2)列出所有主要活动。6.已知下图中显示的二进制树是从森林转换而来的。绘制原始森林7.从空木头开始(1)绘制通过在第三级B树中插入关键码而创建的树(仅创建最终创建的树，而不创建树)。依次插入的关键字为20，30，50，52，60，68，70。(2)绘制基于步骤(1)设置的第三级B-树，删除关键字50后的B-树。(3)绘制在步骤(2)运行后生成的B- tree，删除关键字68之后的B- tree。8.用于设置记录的键(key)集合包括：K=15，25，26，4，5，20，3，12，2(1)设置哈希表长度m=16，然后选择H(key)=key MOD 15格式的哈希函数、使用线性探测和散列处理冲突的哈希表格式、满足所提供条件的哈希表，以及显示哈希表存储结构的k的值。(2)使用快速排序方法，在根据集合k的关键字按升序排序时，创建第一行之后的结果。四、算法设计问题1.非主导节点的单个链接列表头(注意：如果头指针名称为head，则将单个链接列表称为表头)存储如下图所示：Typedef struct LNodeElemType dataStruct LNode * nextLNode，* LinkList从此单个链接列表中删除具有重复值的重复节点，以创建具有不同表中每个节点值的函数void Delete(LinkList head)。2.二进制树使用二进制链接列表作为以下结构的存储结构：Struct BTreeNo