数据结构考试重点

通常有集中复习、分散复习、穿插复习三种形式。课后复习宜于分散、经常进行。以记忆为主的学习内容，如英语的单词、语文的背诵课文，要今年多次重复以强化记忆，应分散复习。阶段复习最好集中用整块时间，一次复习深透为好。当然集中复习又可将性质不同的课程（如史地、数理）交替安排，穿插复习，使大脑各神经区得到轮换休息，脑的工作效率高。

考数据结构的学校压缩矩阵是重点。在考数据结构的考试中，矩阵的存储和操作是非常重要的一个内容，其中压缩矩阵也是数据结构中的一种重要存储结构，因此通常也会在考试中考察。但是具体来说，考试的重点和难点会因不同学校、不同教师的教学内容而有所不同，所以您最好结合自己的学校和教师要求来确定学习的重点。

数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的（关系）和运算等等的学科。数据：客观对象的符号表示。 数据结构：带有结构和操作的数据元素集合 结构：数据元素之间的关系； 操作：对数据的加工处理 ； 数据结构的表示 1 图示表示 2 二元组表示图示表示：由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系；二元组表示：用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。数据的逻辑结构 ：数据之间的结构关系，是具体关系的抽象。四种逻辑结构：（1）集合 结构中的元素之间除了“同属一个集合”的关系之外，别无其他的关系。（2）线性结构 结构中的元素存在一个对一个的关系。（3）树状结构 结构中的元素存在一对多的关系。（4）网状结构 结构中的元素存在多对多的关系。 两种存取结构：（1）顺序存储结构 顺序存储借助元素的相对位置来表示元素之间的逻辑关系。 用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；(2) 链式存储结构 链式存储借助指示元素的指针表示数据元素之间的逻辑关系。用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。数据的存储结构： 数据结构在计算机内存中的表示。语句频度是指该语句在一个算法中重复执行的次数。好的算法包括 正确性、可读性、健壮性、效率与低存储量需求。线性表有两种基本的存储结构：顺序存储结构和链式存储结构。线性表的逻辑结构： 除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。线性表的链式存储结构 用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。每个存储结点都包含两部分：数据域和 指针域(链域) 在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。 链表不具备的特点是 可随机访问任一节点 。具备 插入删除不须要移动元素 ③不必事先估计存储空间 ④所需空间与其长度成正比带头结点的单链表head为空的判定条件是 ___head->next==NULL____如果最常用的操作是取第i个结点及其前驱，则采用__顺序表___存储方式最节省时间。向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动__n-i+1_ 个元素。在单链表中，要删除某一指定的结点，必须找到该结点的 __直接前驱__ 结点。访问单链表中的结点，必须沿着___指针____ 一次进行。在一个单链表中p所指结点之后插入一个s所指结点时，应执行两个____s->next=p->next和p->next=S__的操作。栈的特点是 ___先进后出_ 队列的特点是__先进先出__栈和队列的共同特点是__只允许在端点处插入和删除元素__。一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 dceab若已知一个栈的进栈序列是p1，p2，p3， … ，pn 。其输出序列为1，2，3，…，n ，若p3=1，则p1为___不可能是2__设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是_____2、3 _____ 栈顶指针是___1003H ___一个队列的入对序列是若1，2，3，4，则队列的输出序列是______1，2，3，4__ 。若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是____2和4 ___。1栈是限定仅能在表尾一端进行插入、删除操作的线性表；2 表尾称为栈顶，表头称为栈底；3 栈的具有后进先出的特点；4 栈顶元素的位置由一个栈顶指针指示；5 进栈、出栈操作要修改栈顶指针；6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为： abc,acb,bac,bca,cba空串与空白串是相同的，这种说法 ____不正确 ____。串是一种特殊的线性表，其特殊性体现在___数据元素可以是多个字符 __。__”21AB”__是C语言中”abcd321ABCD”的子串。两个串相等的充分必要条件是__两个串的长度相等且对应位置的字符相同 ___ 。空串是零个字符的串 ，其长度等于零 。空白串是由一个或多个空格字符组成的串 其长度等于其包含的空格个数 。模式串t=‘abaabcac”的next函数值序列为 -1 0 0 1 1 2 0 1 ，nextval函数值序列为 -1，0，-1，1，0，2，-1，1 。由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 错误 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 完全二叉树深度为5的二叉树至多有 31 个结点。根据使用频率为5个字符设计的哈夫曼编码不可能是 001，000，01，11，10树和二叉树的主要差别是(1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；) (2. 树的结点无左、右之分，而二叉树的结点有左、右之分。) 深度为k的完全二叉树至少有 ___(2的K-1次方)_ 个结点，至多有（2的k次方）-1 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 （2的k-2次方）+1 _________。 一棵二叉树的第i(i³1)层最多有 (2的i-1次方) 个结点；一棵有n（n>0）个结点的满二叉树共有(2的logn次方) 个叶子结点和 （2的logn次方）-1 个非叶子结点。1 二叉树的顺序结构:通过二叉树结点的相对位置，表示结点之间结构关系2二叉链表：通过保存每个结点的左、右孩子结点的存储位置，表示结点之间的结构关系。3 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、后序遍历 LRD5设p是指向二叉链表某结点的指针，请写出将左孩子结点数据赋值给变量e的主要操作语句：q=p-lchild;.e=q->data;6 加上结点前趋后继信息的二叉树称为线索二叉树7 在线索链表中左右指针域或指向孩子结点或指向前趋后继结点一个n个顶点的无向图最多有___n(n-1)/2 ___条边。在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 ___1____ 倍。关键路径是事件结点网络中 __从源点到汇点的最长路径 ___ 。下面不正确的说法是 __任何一个关键活动提前完成，将使整个工程提前完成__，正确的是 关键活动不按期完成就会影响整个工程的完成时间 所有关键活动都提前，则整个工程提前完成 某些关键活动若提前完成，将使整个工程提前完成。一个图的____邻接矩阵___ 表示法是惟一的 邻接表表示法是不惟一的。在有n个顶点的有向图中，每个顶点的度最大可达___2(n-1)_ 。采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为__(n+1)/2 _ 在一个长度为12的有序表，按折半查找法对改表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为___37/12 ___查找效率最高的二叉排序树是 ___平衡二叉树 ___以下说法错误的是___散列表的结点中只包含数据元素自身的信息，不包含任何指针__ 。正确的是 散列法存储的基本思想是由关键码值决定数据的存储地址 装填因子是散列法的一个重要参数，它反映了散列表的装填程度 散列表的查找效率主要取决于散列表造表时选取的散列函数何处理冲突的方法 散列表的平均查找长度___与处理冲突方法有关与表长无关___ 。设线性表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较____9___ 次。一个无序序列可以通过构造一棵___二叉排序___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。在散列存储中，装填因子a的值越大，则存取元素时___发生冲突的可能性就越大___ ；a的值越小，则存取元素时____发生冲突的可能性就越小__排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为___插入排序 _在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是__直接选择排序___对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是_希尔排序___在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是__选择排序 ___在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 ___5____ 次。每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_____交换__ 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 ___二路归并__ 排序。____快速___ 排序方法采用的是二分法的思想 ____堆____ 排序方法其数据的组织采用完全二叉树结构。稳定的：直接插入排序，折半插入排序， 归并排序，基数排序，冒泡不稳定的：希尔排序，快速排序，简单选择排序，堆排序1、分别用直接插入、快速和基数排序算法对整数序列75, 17,12, 8, 70,89, 3, 65, 77,9进行升序排序，写出第一趟的排序结果。 答： 直接插入排序：17，75，12，8，70，89，3，65，77，9 快速排序：｛9，17，12，8，70，65，3｝75｛77，89｝ 基数排序：1.用LSD：70，12，3，75，65，17，77，8，89，9 2.用MSD：8，3，9，17，12，65，75，70，77，892、 分别写出三种排序算法的时间复杂度、空间复杂度及稳定性。答：直接插入排序：时间复杂度O(n^2)，空间复杂度O(1),稳定快速排序：时间复杂度:最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)空间复杂度：最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)排序不稳定基数排序：时间复杂度为：O (mn)空间复杂度：O(n)稳定性：稳定排序方法 平均时间 最坏情况 辅助存储 稳定排序 适合情况插入排序 O(n2) O(n2) O(1) 稳定 记录数较少希尔排序 O(n(log2n)2) O(n2) O(1) 不稳定 不太多快速排序 O(nlog2n) O(n2) O(log2n) 不稳定 较多堆排序 O(nlog2n) O(nlog2n) O(1) 不稳定 多归并排序 O(nlog2n) O(nlog2n) O(n) 稳定 都可以基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) 稳定 关键字位数少