2022年数据结构复习题知识 .pdf

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

1、复习题一、选择题1、若广义表S满足 Head(S)=Tail(S)，则 S为_。A.（ ） B.（ （） ， （） ） C.（ （） ， （） ， （） ） D.（ （ ） ）2、设有一个二维数组Amn ，假设 A00存放位置在644（10），A22存放位置在676（ 10），每个元素占一个空间，则A45在_位置，（10）表明用 10 进制表示。A.696（10） B.709（10） C.724（ 10） D.626（10）3、一个二叉树按顺序方式存储在一个一维数组中（根结点层数为0） ，如图示 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 则结点 E在二叉树的第 _层

2、。A.4 B.3 C.2 D.1 4、执行下面程序段时，S语句的执行次数为_。for ( int i=1; i n; i+) for(int j=1; jlink=HL; B.p-link=HL; HL=p; C.p-link=HL; p=HL; D.p-link=HL-link; HL-link=p; 6、表达式 a*(b+c)-d的后缀表达式是 _ 。A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd 7、 无向图 G= （ V，E） ，其中： V= a,b,c,d,e,f , E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d

3、) 对该图进行深度优先遍历，得到的顶点序列正确的是A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 8、循环队列A0.m-1存放其元素值，用front和 rear分别表示队头及队尾，则当前队列中的元素数是_。A.(rear - front + m)%m B.rear - front + 1 C. rear - front - 1 D.rear-front 9、若某线性表中最常用的操作是删除第i个元素和找第i个元素的前趋元素，则采用_存贮方式最节省运算时间。A.单链表 B. 双链表 C. 单循环链表 D. 向量10、栈的插入和删除操作

4、在_进行。A.栈顶 B.栈底 C.任意位置 D.指定位置A B C D E F G H I J 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 11、广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为_。Head(Tail(Head(Tail(Tail(A) A.(g) B.(d) C.c D.d 12、 有六个元素6， 5， 4， 3， 2， 1 按顺序进栈， 问下列哪一个不是合法的出栈序列？_ A.5 4

5、3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 13、算术表达式a+b*（c+d/e ）转为后缀表达式后为_。A.ab+cde/* B.abcde/+*+ C.abcde/*+ D.abcde*/+ 14、在单链表中指针为p 的结点之后插入指针为s 的结点，正确的操作是：_。A.p-link=s; s-link=p-link; B.s-link=p-link; p-link=s; C.p-link=s; p-link=s-link; D.s-link=p; p-link=s; 15、以下程序段的时间复杂度为：_ for(i=1;in;i+)

6、y=y+1; for(j=0;j=(2*n);j+) x+; A.O(n) B. O(n3) C.O(log2n) D. O(n2) 16、 在数据结构中，从逻辑上可以把数据结构分为_。A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构17、 下面程序段的时间复杂度是_。s=0; for(int i=1;i=n;i+) for(int j=1;j=n;j+) s+=bij; A. O(n) B. O(1) C. O(log2n) D. O(n2) 18、 下面程序段的时间复杂度为_。 for (int i=0;im;i+) for (int

7、 j=0;jlink = NULL; C. first-link = first; D. first != NULL; 21、在一个单链表中，若删除p所指结点的后继结点不是最后结点，则执行：_ A.plink=plinklink; B.p=plink;plink=plinklink; C.plink=plink; D.p=plinklink; 22、一个顺序存储的线性表第一个元素的存储地址是100，每个元素的长度为2，则第 5 个数据元素的地址是：_ A.110 B.108 C.100 D.120 23、在一个单链表中，若q 结点是 p 结点的前驱结点，若在q 与 p 之间插入结点s，则执行_

8、。A. s link = plink; p link = s; B. p link = s; s link = q; C. p link = slink; s link = p; D. q link = s; s link = p; 24、在一个顺序队列中，队首指针指向队首元素的_位置。A. 前一个 B. 后一个 C. 当前 D.A 、B、C都不对25、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个 _结构。A.堆栈 B. 队列 C.数组 D. 线性表26、一个栈的入栈序列是a，

9、b， c，d，e，则栈的不可能的输出序列是：_ A.edcba B.decba C.dceab D.abcde 27、判断一个循环队列QU （最多元素为m ） ，为满队列的条件是：_ A.QUfront=QUrear B.QUfront!=QUrear C.QUfront=(QUrear+1)%m D.QUfront!=(QUrear+1)%m 28、将一个递归算法改为对应的非递归算法时，通常需要使用_。A. 栈 B. 队列 C. 循环队列 D. 优先队列29、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为_。A. 2,3,4,1 B. 3,2,4,1 C. 1,2,3,4 D.

10、4,3,2,1 30、二维数组M的元素是4 个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从 0 到 4， 列下标 j 的范围从0 到 5，M按行存储时元素M35的起始地址与M按列存储时元素 _的起始地址相同。A.M24 B.M34 C.M35 D.M44 31、设有广义表D(a,b,D),其深度为 _。A. B. 3 C. 2 D. 5 32、一个深度为L 的完全二叉树至少有_个结点，（设根结点深度为1） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 1

11、2 页 - - - - - - - - - A. 2*L B. 2L-1 C. 2L D. 2L+133、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_的二叉树。A. 空或只有一个结点 B. 高度等于其结点数C. 任一结点无左孩子 D. 任一结点无右孩子34、 已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为_。A.130 B.129 C.131 D.不确定35、在有向图中每个顶点的度等于该顶点的_。A. 入度 B. 出度C. 入度与出度之和D. 入度与出度之差36、任何一个无向连通图的最小生成树_。A. 只有一棵 B.有一棵或多棵 C. 一定有多棵 D. 可能不存在

12、37、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用_。A. 求关键路径的方法 B. 求最短路径的Dijkstra方法C. 深度优先遍历算法D. 广度优先遍历算法38、在数组A中，每一个数组元素Aij占用 3 个存储字节，行下标i 从 1 到 8，列下标j 从 1 到 10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字节数是 _。A. 80 B. 100 C. 240 D. 270 39、广义表 A(a), 则表尾为 _。A. a B. ( ) C. 空表 D. (a) 40、在一个长度为n 的线性表中顺序查找值为x 的元素时，查找成功时的平均查

13、找长度为_。A.n B.n/2 C.(n+1)/2 D.(n-1)/2 41、 设哈希表长为14，哈希函数是H(key)=key%11 ，表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A.8 B.3 C.5 D.9 42、利用关键码分别为10，20，30，40 的四个结点， 能构造出 _种不同的二叉搜索树。A.14 B.8 C.12 D.24 二、判断题1、算法可以没有输入，但是必须有输出。2、如果一个串中的所有字符均在另一个串上出现，则说明前者是后者的子串。3、线性表若采用链式存储表示时所有存储单元的地址可

14、连续也可不连续。4、AOE网中，完成工程的最短时间等于从源点到汇点的最短路径的长度。5、对于无向图的生成树，从同一顶点出发所得的生成树相同。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 6、一个树中的叶子数一定等于其对应的二叉树中的叶子数。7、一个广义表的表尾总是一个广义表。8、求图的最小生成树有两种算法，其中kruskal算法适合于求稀疏图的最小生成树。9、在相同的规模n 下，复杂度O(n) 的算法在时间上总是优于复杂度O

15、(2n) 的算法。10、由一棵二叉树的前序序列和后序序列可以唯一确定它。11、每种数据结构都应具备三种基本运算：插入、删除、搜索。12、线性表的长度是线性表占用的存储空间的大小。13、顺序存储的线性表可以随机存取。14、线性表的逻辑顺序与物理顺序总是一致的。15、通常递归的算法简单、易懂、容易编写，而且执行的效率也高。16、队列只能采用链式存储方式。17、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。18、两个字符串有相同的字符，则两个字符串相等。19、数组可以看成是线性表的一种推广，但是不可以进行插入、删除等运算。20、空串与由空格组成的串没有区别。21、对于一棵具有

16、n 个结点，其高度为h 的二叉树，进行任一种次序遍历的时间复杂度为O(h) 。22、树（或森林）转化为对应的二叉树后，两者的分支数相等。23、完全二叉树也是满二叉树。24、若有一个结点是二叉树中某个子树的后序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的第一个结点。25、连通分量是无向图中的极大连通子图。26、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。27、任何一个关键活动提前完成，那么整个工程将会提前完成。28、任何无环的有向图，其结点都可以排在一个拓扑序列里。29、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。3

17、0、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。31、在排序算法中，就平均时间而言，直接选择排序最好。32、在排序算法中，若待排序数据已有序时，花费时间最多的是快速排序。33、直接选择排序是一种稳定的排序方法。34、在排序算法中，就平均时间而言，希尔排序比直接选择排序要好。35、对二叉排序树遍历的结果是一个有序序列。36、希尔排序是一种稳定的排序方法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - -

18、37、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。三、填空题1、广义表 A=（c, d, e） ，取出 A中原子 e 的操作是 _。2、若一棵度为3 的树中，有2 个结点的度为1，1 个结点的度为2，2 个结点的度为3，则该树中度为0 的结点个数是 _，树中总的结点个数有_个。3、对于一个具有n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 _和_个。4、检测有向图中是否有回路（即有向环）的方法是_。5、稀疏矩阵一般的压缩存储方法有两种，它们是用 _ _和_ _ 表示。6、队列是一种只允许_的线性表。7、 一个算法具有5 个特性 : _

19、、 _ 、 _ ，有零个或多个输入、有一个或多个输出。8、在数据结构中， 与所使用的计算机无关的数据叫_结构，与所使用的计算机有关的数据叫 _结构。9、一种抽象数据类型包括_和_两个部分。10、算法是对特定问题的求解步骤的一种描述，它是_（用来表示一个或多个操作）的有限序列。11、线性结构反映结点间的逻辑关系是一对一的，图中的数据元素之间的关系是_的，树形结构中数据元素间的关系是_的。12、对于一个具有n 个结点的单链表， 在给定值为x 的结点后插入一个新结点的时间复杂度为_。13、静态搜索时，在等概率的情形下搜索到所需对象的平均搜索长度ASL=_。14、从一个链栈中删除一个结点时，需要把栈顶

20、结点的_域的值赋给 _。15、栈中存取数据的原则_，队列中存取数据的原则_。16、在一个循环队列Q中，判断队空的条件为_。17、一个广义表中的元素分为_元素和 _元素两类。18、设 s=” I#AM#A#TEACHER” ，其长度是 _。 （其中“ #”表示空格）19、广义表 (a),(b),c),(d)的表尾是 _。20、构造 AOV网络的拓扑有序序列，主要用于检测_。21、一个算法的时间复杂度为(4n3+2nlog2n+8)/(2n2) ，其大 O表示为 _。22、有 n 个叶子的 Huffman 树，其总结点数为_。23、由一棵二叉树的前序序列和_可唯一确定这棵二叉树。24、设高度为h

21、的空二叉树的高度为-1 ，只有一个结点的二叉树的高度为0，若设二叉树只名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 有度为 2 和度为 0 的结点，则该二叉树中所含结点至少有_个。25、在一个具有n 个顶点的无向完全图中，包含有_条边。26、对于有 n 个顶点的无向连通图至少有_条边，最多有_条边。27 、 已 知 一 个 图 的 邻 接 矩 阵 表 示 ， 计 算 第i个 结 点 的 入 度 的 方 法 是_ 。28、在无

22、向图G的邻接矩阵A中，若 Aij等于 1，则 Aji等于 _。29、 对于一个具有n个顶点和 e条边的连通图， 其生成树中的顶点数为_、 边数为 _。30、假定一组记录的排序码为（46,79,56,38,40,80,25,34） ，则对其进行快速排序的第一次划分后，得到的结果为：_。31、有一个有序表为 3,12,24,37,45,53,61,78,90,100 ，当二分查找值为24 的数据时_次比较成功。32、锦标赛排序算法总的时间复杂度为_。33、对 20 个记录进行二路归并排序时，共需要进行_趟归并。34、在堆排序的过程中，对 n 个记录建立初始堆需要进行_次筛运算， 由初始堆到堆排序结

23、束，需要对树根结点进行_次筛运算。35、冒泡排序算法总的时间复杂度为_。四、简答题1、设有一个10 10 的对称矩阵A，将其下三角部分按行存放在一个一维数组B中， A00存放于 B0 中，那么A85存放于 B中什么位置。2、画出下面广义表的图形表示和它们的存储表示：D(A(c), B(e), C(a, L(b, c, d) 3、假定一棵二叉树广义表表示为a(b(c),d(e,f)，分别写出对它进行先序、中序、后序、按层遍历的结果。4、已知一棵树的先根遍历次序为：ABEFGCDHI ，后根遍历次序为：EFGBCHIDA ，试画出此树，并画出转化后的二叉树。5、假定一棵二叉树广义表表示为A(B(,

24、D(G),C(E,F)，画出该二叉树的图形表示和双亲存储表示，并分别写出对它进行前序、中序、后序及按层遍历的结果6、设二叉树bt 的二叉链表静态存储结构如下：leftchild 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i rightchild 0 0 0 9 4 0 0 0 0 0 要求： （1）请画出该二叉树bt 的图形表示；（2）请分别写出前序、中序、后序遍历二叉树bt 的序列。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页

25、，共 12 页 - - - - - - - - - 7、现有稀疏矩阵A如图所示，要求画出其三元组表示法。15 0 0 22 0 15 0 13 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 8、请画出与下列二叉树对应的森林。9、将下面的森林变换成二叉树。10、已知一组数列为 13, 5, 6, 17, 32, 15，构造一棵霍夫曼树，并计算带权路径长度WPL 。 （要求：详细写出构造霍夫曼树的每一步）11、给定权值集合15 ，03，10，05，07，11，25，36 ，构造相应的Huffman 树，并计算它的带权路径长度。

26、（要求：详细写出构造霍夫曼树的每一步）12、已知某字符串共有8 种字符，下表为各字符在该串中的出现次数，对该字符串进行Huffman编码，问字符串的编码总长有多少位？并列举出各字符的编码。（要求：详细写出构造的每一步）a b c d e f g h 2 1 4 5 7 3 4 9 A C D B S R X W T U V 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 13、对给定的有7 个顶点（ v0,v1,v2,v3,v

27、4,v5,v6）的有向图的邻接矩阵如下：（1） 、画出该有向图；（2） 、若将图看成AOE网，列出其关键活动及相应的有向边。14、已知带权连通图 G(V, E)如下 : （1） 、用普里姆 (Prim) 算法，画出图的最小生成树（请写出生成过程）。（2） 、去掉图中的权值，画出从顶点1 出发的深度优先生成树和广度优先生成树。 16 21 11 5 196 33 14 6 18 15、已知带权连通图 G(V, E)如下所示，请用克鲁斯卡尔（Kruskal ）算法，画出该图的最小生成树。（请写出生成过程）16、已知一个无向图的顶点集为a,b,c,d,e，其邻接矩阵如下所示，0 1 0 1 1 1

28、0 0 1 0 0 0 0 1 1 1 1 1 0 1 10 1 1 0 (1) 画出该图的图形；(2) 根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。a b c d e 573553172352名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 17、将给定的图简化为最小的生成树，要求从顶点1 出发。18、已知：单链表La 和 Lb 的元素按值非递减排列，归并La 和 Lb，得到新的单链表Lc，L

29、c的元素也按值非递减排列。请分析该算法并填空。void Mergelist(linklist &la,linklist &lb,linklist &lc) pa=la-link; pb=lb-link; lc=pc=la; while(_) if(pa-datadata) _ _ _ elsepc-link=pb;pc=pb;pb=pb-link; 19、已知长度为n 的非空线性表A采用顺序存储结构，并且元素按值大小非递减排序。请写一算法，在线性表A中插入一个值为item 的元素， 使得线性表仍然按非递减排序。（注： 下标从 1 开始）int lenth=n; void INSERT(int

30、A,int n,int item) int i; if(item = An) _ else i=1; while (_) i+; for(int j=n; j=i;j-) _ _ 1 3 2 5 4 7 6 8 5 15 3 10 12 2 7 9 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - _ 20、有一哈希表HT, 表长 n=16, 哈希函数 H(key)=key mod 13，试用开地址法中的线性探测法，将一组

31、关键字序列 19, 14, 33, 01, 68, 20, 84, 27 加入 HT 中。 ( 只需画出空间分配 , 不需要写出算法) 21、分别画出在有序表3,11,26,32,45,59,67中进行折半搜索，查找关键字等于59 和 26的过程。22、已知序列17，31，13，11，20，35， 25，8，4，11， 24，40，27。请画出由该输入序列构成的二叉搜索树，并求出在等概率的情况下查找成功的平均查找长度ASL 。23、 判断序列 05,56,20,23,40,38,29,61,35,76,28,100是否是最小堆？如果不是，请调整。若删除一个元素后，应如何调整为最小堆？（请画图说

32、明步骤）24、给定序列 56,78,34,21,89,23,12,2 ，请建立一个最小堆，若删除一个元素后，应如何调整为最小堆，请画图说明。五、算法设计题1、试写出在单循环链表中寻找结点值为X的算法，假设P指针指向链表的头结点，要求打印寻找过程（所经过的结点值），若找到则将该结点删除，找不到则打印“找不到”。2、设在一个带表头结点的单链表中所有元素结点的数据值按递增顺序排列，试编写一个函数，删除表中所有大于min，小于 max的元素（若存在） 。3、试编写一个函数，将一个有n 个非零元素的整数一维数组An 拆分为两个一维数组，使得 A 中大于零的元素存放在B 中，小于零的元素存放在C 中。4、

33、编写向类型为List的线性表 L 中第 i 个元素的前面插入一个元素的算法，假定不需要对i 的值进行有效性检查，同时不需要检查存储空间是否用完。 void Insert(List& L, int i, ElemType x) 5、设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。 要求逆转结果链表的表头指针h指向原链表的最后一个结点。6、假设有两个按元素值递减次序排列的线性表la 和 lb ，均以带表头的单链表形式存储。请编写算法将la 和 lb 归并为一个按元素值递增次序排列的单链表，要求利用原来两个单链表的结点存放归并后的单链表，表

34、中允许有重复数据。 提示 ：设单链表的抽象数据类型List已定义完成，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 只需定义并实现算法函数void merge(List la,List lb)。 Class List; Class ListNode friend class list; private: int data; ListNode *link; public: ,；Class List private: List

35、Node *first; public: ,；7、修改冒泡排序算法为双冒泡排序。即在正反两个方向交替进行扫描，第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面，如此反复进行。 提示 ：使用下面已定义的顺序表抽象数据类型datalist来存放待排序的数据元素，将该算法定义为普通外部函数void dbubble(datalist &lisgt)并实现。 Class datalist private: int *Vector, MaxSize, CurrentSize; public: , 8、已知二叉树中的结点类型用BTreeNode 表示，被定义为: struct

36、 BTreeNode char data; BTreeNode *leftChild, *rightChild; ; 其中 data 为结点的数据域， leftChild和 rightChild分别为指向左、 右子女结点的指针域。根据下面的函数声明，编写统计并返回一棵二叉树中所有叶子结点个数的递归算法。（假定参数 BT为指向这棵二叉树的根结点的指针） int Count ( BTreeNode* BT ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -