2022年数据结构复习提纲 .pdf

《2022年数据结构复习提纲 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习提纲 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构复习提纲复习内容：基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法；T（n） ，S（n）的理解。要学习的数据结构定义形式：n（n=0）个数据元素的有限集合。将约束： 1、数据元素本身。2、数据元素之间的关系。3、操作子集。大多有两种存储（表示、实现）方式：1、顺序存储。 2、链式存储。一、线性结构：1、线性表： n（n=0）个相同属性的数据元素的有限序列。12 种基本操作。顺序表： 9 种基本操作算法实现。单链表：11种基本操作算法实现。 （重点：插入、删除）顺序表与单链表之时间性能、空间性能比较。循环链表：类型定义与单链表同。算法实现只体现在循环终止的条件不同。双向链表：重

2、点插入、删除算法。 2、操作受限的线性表有：栈、队列。栈：顺序栈；链栈（注意结点的指针域指向）。 （取栈顶元素、入栈、出栈）队列：循环队列（三个问题的提出及解决）；链队列（注意头结点的作用）。 （取队头元素、入队、出队。链队列中最后一个元素出队） 3、数据元素受限的线性表有：串、数组、广义表。串：定长顺序存储；堆分配存储。块链存储（操作不方便）数组：顺序存储。特殊矩阵的压缩存储；稀疏矩阵（三元组表示、十字链表）广义表：长度、深度。取表头（可以是原子也可以是子表）；取表尾（肯定是子表） 。链式存储。二、树型结构：1、树： n（n=0）个数据元素的有限集合。这些数据元素具有以下关系：。（另有递归定

3、义。 ）术语；存储（双亲表示、孩子表示、孩子双亲表示、孩子兄弟表示）。 2、二叉树： n（n=0）个数据元素的有限集合。这些数据元素具有以下关系：。（另有递归定义）5 个性质（理解、证明；拓展）。遍历二叉树（定义、序列给出、递归算法、非递归算法）；遍历二叉树应用：表达式之前序表达式、后序表达式、中序表达式转换。线索二叉树（中序线索二叉树）。树森林与二叉树的转换。树与森林的遍历。赫夫曼树及其应用：定义、构造、赫夫曼编码。三、图形结构： n（n=0）个数据元素的有限集合。这些数据元素具有以下关系：。术语掌握。存储结构（数组表示法、邻接表；无向图的邻接多重表）。图的遍历及应用：无向图的最小生成树（普

4、里姆算法、克鲁斯卡尔算法）；拓扑排序、关键路径。四、查找（查找表） ：相关概念掌握。静态查找表：顺序表的查找；有序表的查找；动态查找表：二叉排序树、AVL 树的定义及调整。哈希表：定义及概念；HASH 函数；五、内部排序：概念掌握。插入排序：直接插入排序、折半插入排序、希尔排序交换排序：起泡排序、快速排序选择排序：冒泡、简单选择排序归并排序（外部排序基础）基数排序（链式基数排序）要求： 1、排序算法。 2、各种排序算法的O（n） 、稳定性。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页模拟卷一、填空题1、 在用于表示有向图的邻接

5、矩阵中，对第 i 行的元素进行累加，可得到第i 个顶点的（出 ）度，而对第 j 列的元素进行累加，可得到第j 个顶点的（入）度。2、 一个连通图的生成树是该图的（极小）连通子图。若这个连通图有n 个顶点，则它的生成树有（N-1）条边。3、对算法从时间和空间两方面进行度量，分别称为（） 、 （） 分析。4、二叉树第i 层上最多有（ 2i-1 ）个结点。一个二叉树中每个结点最多只有（ 2 ）个孩子。5、一棵二叉树有67 个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2 的结点有（）个。6.设一棵二叉树结点的先根序列为ABDECFGH ，中根序列为DEBAFCHG ，则二叉树中叶子结点是（

6、）7.设栈 S和队列 Q 的初始状态皆为空，元素a1，a2， a3，a4，a5 和 a6 依次通过一个栈，一个元素出栈后即进入队列Q，若 6 个元素出队列的顺序是a3，a5，a4，a6，a2， a1 则栈 S 至少应该容纳（4 ）个元素。8、循环队列判断队满的条件为（） 。9、将两个长度分别m 和 n(mn) 的排好序的表归并成一个排好序的表，至少要进行（n ）次键值比较。10. 已知在一棵含有n 个结点的树中， 只有度为k 的分支结点和度为0 的叶子结点， 则该树中含有的叶子结点的数目为(2+NK-2N)/K 。)。度：一个结点含有的子树的个数称为该节点的度；公式：一个有限图中，各点的度数总

7、和是边数的2倍；而树中的边数为点数减1。设有 x 个叶节点，那么分支节点数为N-x 各点度数总和为：x*0+(N-x)*K=2*(N-1); 最后计算得到叶节点个数为(2+NK-2N)/K 。11. 采用散列技术实现散列表时，需要考虑的两个主要问题是：构造 ( )和解决 ( )。12. 试计算下面程序段时间复杂度( )。for(i = 1; i = n; i+) for(j = 1; j=1,所以该函数存在单调递增的单值反函数所以边与顶点为增函数关系所以 28 个条边的连通无向图顶点数最少为8 个所以 28 条边的非连通无向图为9 个( 加入一个孤立点 )15. 己知有序表为(12,18,24

8、,35,47,50,62,83,90,115，134) ，当用折半查找方法查找90 时，需比较( )次查找成功，47 需比较 ( )次查找成功，查100 时，需比较 _( )次才能确定不成功。二、选择题：1.下列有关线性表的叙述中，正确的是(a ) A、线性表中的元素之间隔是线性关系B、线性表中至少有一个元素C、线性表中任何一个元素有且仅有一个直接前趋D、线性表中任何一个元素有且仅有一个直接后继2.分别用 front 和 rear 表示顺序循环队列的队首和队尾指针,则判断队空的条件是_. A.front+1=rear B.(rear+1) % maxSize = front C.front=0

9、 D.front=rear 3.下列关于串的叙述中，正确的是( ) A、一个串的字符个数即该串的长度B、一个串的长度至少是1 C、空串是由一个空格字符组成的串D、两个串 S1 和 S2 若长度相同， 则这两个串相等4.设结点 x 和结点 y 是二叉树T 中的任意两个结点，若在先根序列中x 在 y 之前， 而在后根序列中 x 在 y 之后，则x 和 y 的关系是 ( ) A、x 是 y 的左兄弟B、x 是 y 的右兄弟C、x 是 y 的祖先D、x 是 y 的后代5. 广义表 A=( a, b, ( c, d ), ( e, ( f, g ) ) ), 则 Head( Tail( Head( Ta

10、il( Tail( A ) ) ) ) ) 的值为. A. (g) B. (d) C. c D. d 6. 一个栈的输入序列为1 2 3 4 5 ，则下列序列中不可能是栈的输出序列的是（）A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 7. 一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（D ）A 250 B 500 C254 D501 对于满二叉树来讲，高度为9 得总结点数是511 个，高度为 10 得总结点数是1023 个。这样题目中要求的完全二叉树应是高度为10 的完全二叉树，完全二叉树的叶结点在最下面两层，本题中就是在第

11、9、第 10 两层出现。第 10 层叶结点数目是：1001-511=490（即总结点数 -前 9层结点的总数目） 。第 9 层叶结点数目是：对于满二叉树，第10 层的结点数应该是512个，而现在的完全二叉树的第10 层有 490 个结点，相对于完全二叉树少了22 个结点，少的这22 个结点将导致第 9 层出现 22/2=11 个叶结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页所以这棵完全二叉树得总的叶子结点数是：490+11=501。8. 三维数组A567 按行优先存储方法存储在内存中，若每个元素占2 个存储单元，数组元素

12、下标从0 开始，且数组中第一个元素的存储地址为120，则元素A445 的存储地址为（）A. 518 B. 520 C. 522 D. 524 9. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（C ）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表选择 C，明显带头节点的双向链表，查找尾元素最简单。这样插入元素最为方便。10. 在长度为n 的顺序表的第i(1 i n+1)个位置上插入一个元素，元素的移动次数为（A）A. n-i+1 B. n-i C. i D. i-1 (1) 顺序表中访问任意一个结点的时间复杂度均为0（1）(2) 在有

13、 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为0（n）. (3) 在一个长度为 n 的顺序表中删除第i 个元素，要移动 n-i 个元素。(4) 在一个长度为 n 的顺序表，如果要在第i 个元素前插入一个元素，要后移n-i+1 。(5) 等概率情况下，在有n 个结点的顺序表上做插入结点运算，需平均移动结点的数为 n/2. (6) 等概率情况下，在有n 个结点的顺序表上做删除结点运算，需平均移动结点的数目为 (n-1)/2. 11. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（） 。ACBEFDA B FEDCBA C CBEDFA D

14、不定已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和 DBGEACHF ， 则该二叉树的后序遍历是什么？先序遍历的第一个结点是根结点，所以 A 是根，然后在中序遍历中找到A， （DBGE ）A（CHF ），由中序遍历的定义知 （DBGE ）是左子树的中序遍历，（CHF ）是右子树的中序遍历。然后在先序遍历中把左子树和右子树划开，A（BDEG ）（CHF），所以B 是左子树根， C 是右子树根。然后继续在中序遍历中找到B 和 C，（D）B（GE）A（C（HF ）。对于 DBEG ，B 是根，D 是左子树， EG 是右子树的中序遍历，对于CHF，C 是根， HF 是右子树的中序遍历。因为仍

15、然有没划分完的部分，所以继续看先序。对于BDEG ，B 是根已知， D 是整个左子树已知，所以EG 是右子树的先序遍历，E 是右根，再对照中序可知G 是 E的左子树， CHF 同理。所以树的结构是A（B（D，E（G，）， C（，F（H，）把它画成图，后序遍历就是DGEBHFCA12. 一个 n 个顶点的连通无向图，其边的个数至少为（A ） 。An-1 Bn Cn+1 Dnlogn 13. 下面关于折半查找的叙述正确的是( ) A. 表必须有序， 表可以顺序方式存储，也可以链表方式存储B. 表必须有序，而且只能从小到大排列精选学习资料 - - - - - - - - - 名师归纳总结 - - -

16、 - - - -第 4 页，共 7 页C. 表必须有序且表中数据必须是整型，实型或字符型D. 表必须有序， 且表只能以顺序方式存储14. 以下哪个是不稳定的排序方法。( ) A起泡排序B归并排序C Shell 排序D直接插入排序15. n 个权构成一棵 Huffman 树，其节点总数为：（）A、2n-1 B、2n C、2n+1 D 、不确定三、应用题：1. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。void reverse(pointer h) /* h 为附加头结点指针；类型pointer 包括一个数据域data 一个指针域next*/ pointer p, q

17、; p=h-next; h-next=NULL; while( P!=NULL ) q=p; p=p-next; q-next=h-next; h-next= q ; 2在带头结点的head单链表的结点a 之后插入新元素x struct node elemtype data; node *next; ; void lkinsert (node *head, elemtype x) node *s, *p; s= ; s-data= ; p=head-next; while (p!=NULL) &( p-data!=a ) ; if (p=NULL) couti )&( R j R 0 ) j-

18、 -; if (ji) R i =R j ; i+; while (ij )& (R i R 0 ) i+; if (ip) qksort(R,p,j); if (iq) ; 5. 设有一组关键字19,01,23,14,55,20,84,27,68,11,10,77，采用散列函数：H(key) = key MOD 13 ，采用线性探测法解决冲突，试在 018 的散列地址空间中对该关键字序列构造散列表。 H(19)=19%13=6 H(01)=1%13=1 H(23)=23%13=10 H(14)=14%13=1 H(55)=55%13=3 H(20)=20%13=7 H(84)=84%13=6

19、 H(27)=27%13=1 H(68)=68%13=3 H(11)=11%13=11 H(10)=10%13=10 H(77)=77%13=126 有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为8、6、10、4、7，请构造相应的哈夫曼树（要求：左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页6. 画出下图的一棵最小生成树，并写出其邻接矩阵。四、综合设计题：1、2 叉排序树构造过程2、关键路径（如课件例题）3、排序算法。4 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21 ，30，42，42，42，51，70）将变作（ 7，10 ，21，30， 42，51， 70）1 2 4 5 7 8 3 6 10 2 5 4 6 4 2 9 7 7 5 8 8 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页