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

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

1、一、1数据元素是数据的基本单位。2在一个单链表中，若删除p 所指结点的后继结点，则执行p-next=p-next-next;3 在循环双链表的p所指结点之后插入s所指结点的操作是s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;4若希望从链表中快速确定一个结点的前驱，则链表最好采用双向链表方式。5设有 50 行的二维数组A5060，其元素长度为4 字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为 4376 。6广义表(a,b,(c,(d)的表尾是 (b,(c,(d)。7队列的特点是先进先出。8设计一个判别表达式中左、右括号是否配

2、对出现的算法,采用栈数据结构最佳.9 判 定 一 个 循 环 队 列QU(maxsize=m0)为 满 队 列 的 条 件 是QU-front=(QU-rear+1)%m0 。10树最适合用来表示元素之间具有分支层次关系的数据。11在二叉树的第i 层上至多有 2i-1个结点(i 1)。12对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为 h或 h+1 。13如图所示二叉树的中序遍历序列是 dfebagc 。acgbdef14已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是cedba 。15在线索二叉树中，一个结点是

3、叶子结点的充要条件为它的左、右线索标志均为1 。16若一棵二叉树中度为l 的结点个数是3，度为 2 的结点个数是4，则该二叉树叶子结点的个数是 5 。17 由权值分别为3、8、6、2、5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 55 。18无向图的邻接矩阵是一个对称矩阵。19 具有 n 个顶点的无向图最多有 n(n-1)/2 条边。20具有 5 个顶点的无向图至少应有 4 条边才能确保是一个连通图。21下列命题正确的是一个图的邻接矩阵表示是唯一的，邻接表表示不唯一。22已知一有向图的邻接表存储结构如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 17 页 -54321

4、3245424从顶点 V1出发，进行深度优先遍历，所得的顶点序列是 V1 V3 V4 V5 V2。23 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是选择排序。24快速排序方法在要排序的数据已基本有序情况下蜕化为起泡排序。25内部排序的方法有许多种，选择排序方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。26一组记录的关键字为46，79，56，38，40，84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 40，38，46，56，79，84 。27递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是堆栈。28对线性表进行二分查

5、找时,线性表必须顺序存储并有序。29按中序遍历二叉排序树得到的序列是一个有序序列。30在图 G 中求两个结点之间的最短路径可以采用的算法是迪杰斯特拉（Dijkstra）算法。31线性表是具有n 个数据元素的有限序列。32在一个长度为n 的顺序存储结构的线性表中，向第i 个元素（1i n+1）之前插入一个新元素时需向后移动 n-i+1 个元素。33若进栈序列为1、2、3、4，进栈过程中可以出栈，则 1 4 2 3 不可能是一个出栈序列。34由三个结点构成的二叉树，共有 5 种不同的结构。35先序遍历和中序遍历结果相同的二叉树是所有结点只有右子树的二叉树。36在一棵具有五层的满二叉树中，结点总数为

6、 31 。37由分别带权为9，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 44 。38在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍。39在有向图的逆邻接表中，每个顶点邻接表链接着该顶点的所有入边邻接点。40对线性表进行折半查找时，要求线性表必须以顺序方式存储，且数据元素有序。41一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 (40,38,46,56,79,84)。42从长度为n 的采用顺序存储结构的线性表中删除第i 个元素（1i n）,需向前移动 n-i 个元素。名师资料总结-精品资料欢

7、迎下载-名师精心整理-第 2 页，共 17 页 -43从邻接矩阵A=010101010可以看出，该图共有 3 个顶点。44排序趟数与序列的原始状态有关的排序方法是冒泡排序。45在一个具有n 个单元的采用顺序存储结构的栈中，假定以地址低端（即下标为1 的单元）作为栈底，以top 作为栈顶指针，则当作出栈处理时，top 变化为 top=top-1;。46在具有N个结点有序单链表中插入一个新结点并仍然有序的时间复杂度为 O(N)。47在一棵二叉树中，第五层上的结点数最多为 16 个。48在一棵度为3 的树中，度为 3 的结点数为2 个，度为 2 的结点数为1 个，度为 1 的结点数为 2 个，那么度

8、为0 的结点数为 6 个。49已知 8 个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 5 。50设无向图的顶点个数为N，该无向图最多有 N(N-1)/2 条边。51在具有N个单元的采用顺序存储结构的循环队列中，假定FRONT 和 REAR分别为队首指针和队尾指针，则判断队满的条件是 (REAR+1)%N=FRONT 。52对一个具有n 个顶点和 E 条边的无向图，所有顶点邻接表中的结点总数为 2E 。53采用顺序查找法查找长度为N的线性表时，在等概率情况下，顺序查找的平均查找长度为 (N+1)/2 。54当两个元素相比

9、较出现反序（即逆序）时就相互交换位置的排序方法叫交换排序。55若二叉树采用二叉链表存储结构，要交换其所有结点左右子树的位置，利用先序遍历方法最合适。56设栈 S 和队列 Q的初始状态为空，元素E1、E2、E3、E4、E5和 E6 依次通过栈S，一个元素出栈后即进入队列Q，若 6 个元素出列的顺序为E2、E4、E3、E6、E5和 E1，则栈 S的容量至少应该是 3 。57将 10 阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为 55 。58设结点A有 3 个兄弟结点且结点B 为结点 A的双亲结点，则结点B 的度数为 4 。59根据二叉树的定义可知二叉树共有 5 种不同的形态。60设有以下

10、四种排序方法，则快速排序的空间复杂度最大。61算法指的是解决问题的有限运算序列。62线性表采用链式存储时，结点的存储地址连续与否均可。63将长度为 n 的单链表链接在长度为m的单链表之后的算法的时间复杂度为 O（m）。64由两个栈共享一个向量空间的好处是：（节省存储空间，降低上溢发生的几率）65设数组datam 作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为 front=(front+1)%m 。66如下陈述中正确的是串是一种特殊的线性表。67设结点A有 4 个兄弟结点且结点B 为结点 A的双亲结点，则结点B 的度数为 5。68一个

11、非空广义表的表头可以是子表或原子。69递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是堆栈。70在一棵度为3 的树中，度为3 的结点个数为2，度为 2 的结点个数为1，度为 1 的结点名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 17 页 -数为 2 个，则度为0 的结点个数为 6 。71在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为 n2 2e 。72假设一个有n 个顶点和e 条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是 O(n+e)。73用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20

12、）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是快速排序。74设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是 42，40，45，55，80，85 。75不定长文件是指记录的长度不固定。76 设一维数组中有n 个数组元素，则读取第i 个数组元素的平均时间复杂度为 O(1)。77设一棵二叉树的深度为k，则该二叉树中最多有（2k-1）个结点。78设某无向图中有

13、n 个顶点 e 条边，则该无向图中所有顶点的入度之和为 2e 。79在二叉排序树中插入一个结点的时间复杂度为（O(log2n)）。80设某有向图的邻接表中有n 个表头结点和m个表结点，则该图中有 m 条有向边。81设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行 3 趟的分配和回收才能使得初始关键字序列变成有序序列。82设用链表作为栈的存储结构，则退栈操作必须判别栈是否为空。83下列四种排序中快速排序的空间复杂度最大。84设某二叉树中度数为0 的结点数为N0，度数为1 的结点数为Nl，度数为2 的结点数为N2，则下列等式成立的是 N0=N2+1 。85

14、设有序顺序表中有n 个数据元素，则利用二分查找法查找数据元素X 的最多比较次数不超过 log2n。86先序遍历和中序遍历结果相同的二叉树是所有结点只有右子树的二叉树。87设线性表中有10 个元素，则用顺序查找法查找元素X最多需要比较 10 次。88设连通图G中的边集 E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点 a 出发可以得到一种深度优先遍历的顶点序列为 acfebd 。89设输入序列是1、2、3、,、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第 i 个输出元素是 n+1-i 。90.设线性表中有20 个元素，则用顺序查找法查

15、找元素X最多需要比较 20 次。91.若将数据结构形式定义为二元组(K，R)，其中 K是数据元素的有限集合，则 R是 K上关系的有限集合。92.在长度为n 的顺序表中删除第i 个元素(1 i n)时，元素移动的次数为 n-i 。93.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 head=NULL。94.引起循环队列队头位置发生变化的操作是出队。95.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 2，3，5，1，6，4 。96.字符串通常采用的两种存储方式是顺序存储和链式存储。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页

16、，共 17 页 -97.树最适合用来表示元素之间具有分支层次关系的数据。98.设有 50 行的二维数组A5060，其元素长度为4 字节，按行优先顺序存储，基地址为 200，则元素 A1825的存储地址为 4376 。99.对广义表L=(a,b),(c,d),(e,f)执行操作 tail(tail(L)的结果是 (e,f)。100.按排序过程中依据的原则分类，快速排序属于交换类的排序方法。101.n个顶点的强连通图中至少含有 n条有向边。102.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3 的一趟希尔排序的结果为 (19，23，67，56，34，78，92，88)。

17、103.若在9 阶 B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为8。104.由同一关键字集合构造的各棵二叉排序树其形态不一定相同，平均查找长度也不一定相同。105.ISAM 文件和VSAM 文件的区别之一是前者建立静态索引结构，后者建立动态索引结构。106设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是树型结构。107下面程序的时间复杂度为 O(n2)。for（i=1，s=0；i=n；i+）t=1；for(j=1；j 60)OR（性别=“女”）AND（年龄 55）。136.下面程序段的时间

18、复杂度为O(n2)。s=0；for(i=1；in；i+)for(j=1；jnext=s-next；s-next=p；。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -138.在计算机内实现递归算法时所需的辅助数据结构是栈。139.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针 rear 指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 (rear-length+m)m 。140.通常将链串的结点大小设置为大于1 是为了提高存储密度。141.带行表的三元组表是稀疏矩阵的一种顺序存储结构。142.表头和表尾均为空表的广义表是 ()。143.用

19、二叉链表表示具有n 个结点的二叉树时，值为空的指针域的个数为 n+l 。144.为便于判别有向图中是否存在回路，可借助于拓扑排序算法。145.连通网的最小生成树是其所有生成树中边的权值之和最小的生成树。二、1数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（或存储结构）无关，是独立于计算机的。2在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head可用 p 表示为 head=p next next 。3栈顶的位置是随着进栈和退栈操作而变化的。4在串 S=”structure”中，以 t 为首字符的子串有 12 个。5假设一个9 阶的上三角矩阵A按列优先顺序压缩存

20、储在一维数组B 中，其中 B0 存储矩阵中第 1 个元素 a1,1，则 B31 中存放的元素是 a4,8。6已知一棵完全二叉树中共有768 结点，则该树中共有 384 个叶子结点。7 已 知一 个图 的 广度 优 先生 成树 如 下图 所 示，则与 此 相应 的 广度 优先 遍 历序 列 为abefcdg 。8一颗深度为k 且有 2 k-1个结点的二叉树称为满二叉树。9在有序表（12，24，36，48，60，72，84）中二分查找关键字72 时所需进行的关键字比较次数为。10多重表文件和倒排文件都归属于多关键字文件。11设顺序循环队列Q0：m-1 的队头指针和队尾指针分别为F 和 R，其中队头

21、指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为 F=(F+1)%m ;。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -12设线性表中有n 个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为O(n)。13设一棵二叉树中有n 个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有2n 个指针域，n+1 个空指针域。14设指针变量p 指向单链表中结点A，指针变量s 指向被插入的结点B，则在结点A的后面插入结点B的操作序列为 s-next=p-next;p-next=s 。15设无向图G中有 n 个顶点和 e 条边，则

22、其对应的邻接表中有n 个表头结点和 2e 个表结点。16已知一棵完全二叉树中共有768 结点，则该树中共有 384 个叶子结点。17设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为CBA 。18设一棵完全二叉树中有21 个结点，如果按照从上到下、从左到右的顺序从1 开始顺序编号，则编号为8 的双亲结点的编号是4，编号为 8 的左孩子结点的编号是 16 。19两个空串联接得到的串的长度为 0 。20设一个连通图G中有 n 个顶点 e 条边，则其最小生成树上有 n-1 条边。21当问题的规模n 趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。22在链

23、表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。23已知链栈的结点结构如下图，栈顶指针为top，则实现将指针p 所指结点插入栈顶的语句依次为p-next=top;和 top=p;。24空串的长度是 0 。25假设一个6 阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A0存储矩阵的第一个元素b11，则 A14存储的元素是 b63。26在一棵度为3 的树中，度为2 的结点个数是1，度为 0 的结点个数是6，则度为3 的结点个数是 2 。27如图所示的有向无环图可以排出 12 种不同的拓扑序列。date next 名师资料总结-精品资料欢迎下载-名师精心整理-第 8

24、 页，共 17 页 -28 利 用 筛 选 法 将 关 键 字 序 列(37，66，48，29，31，75)建 成 的 大 根 堆 为(75,66,48,29,31,37 )。29对长度为20 的有序表进行二分查找的判定树的高度为 5 。30在多重表文件中，次关键字索引的组织方式是将次关键字相同的记录链接成一个链表。31.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。32.多重表文件和倒排文件都归属于多关键字文件。33.栈下溢是指在栈空时进行出栈操作。34.已知 substr(s,i,len)函数的功能是返回串s 中第 i 个字符开始长度为len 的子串，strlen(s)函数的功

25、能是返回串s 的长度。若s=”ABCDEFGHIJK”，t=”ABCD”，执行运算 substr(s,strlen(t),strlen(t)后的返回值为”EFGH”。35.去除广义表LS=(a1,a2,a3,，an)中第 1 个元素，由其余元素构成的广义表称为LS 的表尾。36.已知完全二叉树T 的第 5 层只有 7 个结点，则该树共有 11 个叶子结点。37.在有向图中，以顶点v 为终点的边的数目称为v 的入度。38.当关键字的取值范围是实数集合时，无法进行箱排序和基数排序。39.产生冲突现象的两个关键字称为该散列函数的同义词。40.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，

26、当需要插入新的记录时，该桶中已有 m个同义词的记录（或：已有m个记录；或：已满）。41.数据的逻辑结构描述数据元素之间的逻辑关系（或关系），与存储方式无关。42.在一个长度为100 的顺序表中删除第10 个元素时，需移动 90 个元素。43.队列的队尾位置通常是随着入队操作而变化的。44.两个空串联接得到的串的长度为 0 。45.控制区间和控制区域是 VSAM 文件的逻辑存储单位。46.已知一棵哈夫曼树含有60 个叶子结点，则该树中共有 59 个非叶子结点。47.如下图所示的有向图中含有 2 个强连通分量。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 17 页 -48.已知一组

27、关键字为15，36，28，97，24，78，47，52，13，86，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是15，28，36，97，24，47，52，78，13，86。49.从空树起，依次插入关键字1l，27，35，48，52，66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为 4 。三、1算法是对特定问题求解步骤的一种描述，是指令的有限序列。2数据类型是一个值的集合和定义在这个值集上的一组操作的总称。3二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。4二叉排序

28、树或者是一棵空树，或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。(3)它的左、右子树也分别为二叉排序树。5假设在矩阵Amn中，有 s 个元素不为零，若s 远远小于矩阵元素的总数（即：snext)q=L；L=L next；p=L；S1：while(pnext)p=p next；S2：pnext=q；qnext=NULL；A B C D E 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -return L；请回答下列问题：（1）说明语句S1 的功能；查询

29、链表的尾结点（2）说明语句组S2 的功能；将第一个结点链接到链表的尾部，作为新的尾结点（3）设链表表示的线性表为（a1,a2,an）,写出算法执行后的返回值所表示的线性表。（a2,a3,an,a1）9.已知用有序链表存储整数集合的元素。阅读算法fun：int fun(LinkList ha,LinkList hb)/LinkList 是带有头结点的单链表/ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针LinkList pa,pb;pa=ha-next;pb=hb-next;while(pa&pb&pa-data=pb-data)pa=pa-next;pb=pb-next;if(p

30、a=NULL&pb=NULL)return 1;else return 0;（1）写出执行fun（a,b）的返回值，其中a 和 b 分别为指向存储集合2，4，5，7，9，12 和2，4，5，7，9 的链表的头指针；0（2）写出算法fun 的时间复杂度；O(n)（3）简述算法fun 的功能。判断两个有序整数集合的链表是否相同（结点个数相同，对应结点的值相等），若相同，返回1；不同，返回0。10.设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4 趟简单选择排序和第4 趟直接插入排序后的结果。第 4 趟简单选择排序后的结果(22，40，45，48，80，78)名师资料

31、总结-精品资料欢迎下载-名师精心整理-第 14 页，共 17 页 -第 4 趟直接插入排序后的结果(40，45，48，80，22，78)11 利用广义表的head和 tail 操作，可从广义表L=(a，b)，(c，d)中分解得到原子c，其操作表达式为head(head(tail(L)；分别写出从下列广义表中分解得到b 的操作表达式。(1)L1=(a.，b，c，d)；答：L1=(a.，b，c，d)(2)L2=(a)，(b)，(c)，(d)。答：L2=(a)，(b)，(c)，(d)12画出与下列二叉树对应的森林。答：14要在 0.n-l的向量空间中建立两个栈stackl和stack2，(1)应该如

32、何设计这两个栈才能充分利用整个向量空间？采用双向栈的形式，stack1的栈底设置在从数组下标为0的元素处，stack2的栈底设置在数组下标为 n-1的元素处。(2)若stackl的栈顶指针为 topl,stack2 的栈顶指针为 top2，如果需要充分利用整个向量空间，则：栈stackl空的条件是：_ top1=0_；栈stack2空的条件是：_ top2=n-1_；栈stackl和栈 stack2满的条件是：_ top1-1=top2_。15无向图G（如下图所示），用普里姆算法构造最小生成树所走过的边的集合为：E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)名师资料总结-精品资

33、料欢迎下载-名师精心整理-第 15 页，共 17 页 -16(1)英文缩写 DAG的中文含义是：有向无环图。(2)此DAG图的全部拓扑排序。序列 1：a b d c f e g 序列 2：a b d c e f g 序列 3：a d b c f e g 序列 4：a d b c e f g 17对 7 个关键字进行快速排序，在最好的情况下仅需进行10 次关键字的比较。(1)假设关键字集合为1,2,3,4,5,6,7，试举出能达到上述结果的初始关键字序列；4 7 1 3 6 5 2(2)对所举序列进行快速排序，写出排序过程。初始关键字：4 7 1 3 6 5 2 一次划分后得：(2 3 1)4(

34、6 5 7)继续划分后得：(1)2(3)(5)6(7)18假设以数组seqnm存放循环队列的元素，设变量rear 和 quelen 分别指示循环队列中队尾元素的位置和元素的个数。则：队满的条件表达式：quelen=m 队空的条件表达式：quelen=0 若 m=40,rear=13,quelen=19，则队头元素的位置为：35 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -一般情况下队头元素位置的表达式为：(rear-quelen+1+m)%m 19已知二叉树：对应的森林：20已知广义表如下：A=(B,y)B=(x，L)L=(a，b)(1)写出下列操作的结果tail(A)=（y）。head(B)=x _。(2)画出广义表A 对应的图形表示。名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -