2022年数据结构面试题 .pdf
《2022年数据结构面试题 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构面试题 .pdf(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1.栈和队列的共同特点是(只允许在端点处插入和删除元素)4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构)5.下列关于栈的叙述正确的是(D)A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D. 栈有后进先出的特征6.链表不具有的特点是(B)A.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性表长度成正比7.用链表表示线性表的优点是(便于插入和删除操作)8.在单链表中,增加头结点的目的是(方便运算的实现)9.循环链表的主要优点是(从表中任一结点出发都能访问到整个链表)10.线性表 L( a1,a2,a3, ai, an) ,下列说法正
2、确的是(D)A.每个元素都有一个直接前件和直接后件B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件11.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)A. 必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以12.线性表的顺序存储结构和线性表的链式存储结构分别是(随机存取的存储结构、顺序存取的存储结构)13.树是结点的集合,它的根结点数目是(有且只有1)14.在深度为5 的满二叉树中,叶子结点的个数为(31)15.具有 3 个结点的二叉树有(5 种形态
3、)16.设一棵二叉树中有3 个叶子结点,有8 个度为 1 的结点,则该二叉树中总的结点数为( 13)17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( cedba)18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和 DBGEACHF ,则该二叉树的后序遍历为(DGEBHFCA )19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca)20.数据库保护分为:安全性控制、完整性控制、并发性控制和数据的恢复。1. 在计算机中,算法是指(解题方案的准确而完整的描述)2.
4、在下列选项中,哪个不是一个算法一般应该具有的基本特征(无穷性)说明: 算法的四个基本特征是:可行性、确定性、有穷性和拥有足够的情报。3. 算法一般都可以用哪几种控制结构组合而成(顺序、选择、循环)4.算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)5. 算法的空间复杂度是指(执行过程中所需要的存储空间)6. 算法分析的目的是(分析算法的效率以求改进)7. 下列叙述正确的是(C)A算法的执行效率与数据的存储结构无关B算法的空间复杂度是指算法程序中指令(或语句)的条数C算法的有穷性是指算法必须能在执行有限个步骤之后终止D算法的时间复杂度是指执行算法程序所需要的时间8.数据结构作为计算机的
5、一门学科,主要研究数据的逻辑结构、对各种数据结构进行的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 13 页 - - - - - - - - - 运算,以及(数据的存储结构)9. 数据结构中,与所使用的计算机无关的是数据的(C)A存储结构B物理结构C逻辑结构D物理和存储结构10. 下列叙述中,错误的是(B)A数据的存储结构与数据处理的效率密切相关B数据的存储结构与数据处理的效率无关C数据的存储结构在计算机中所占的空间不一定是连续的D一种数据的逻辑结构可以有多种存储结构1
6、1. 数据的存储结构是指(数据的逻辑结构在计算机中的表示)12. 数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)13. 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为(线性结构和非线性结构)14. 下列数据结构具有记忆功能的是(C) A队列 B循环队列C栈 D顺序表15. 下列数据结构中,按先进后出原则组织数据的是(B)A线性链表B栈C循环链表D顺序表16. 递归算法一般需要利用(队列)实现。17. 下列关于栈的叙述中正确的是(D)A在栈中只能插入数据B在栈中只能删除数据C栈是先进先出的线性表D栈是先进后出的线性表20. 由两个栈共享一个存储空间的好处是(节省存
7、储空间,降低上溢发生的机率)21. 应用程序在执行过程中,需要通过打印机输出数据时,一般先形成一个打印作业,将其存放在硬盘中的一个指定(队列)中,当打印机空闲时,就会按先来先服务的方式从中取出待打印的作业进行打印。22.下列关于队列的叙述中正确的是(C)A在队列中只能插入数据B在队列中只能删除数据C队列是先进先出的线性表D队列是先进后出的线性表23.下列叙述中,正确的是(D)A线性链表中的各元素在存储空间中的位置必须是连续的B线性链表中的表头元素一定存储在其他元素的前面C线性链表中的各元素在存储空间中的位置不一定是连续的,但表头元素一定存储在其他元素的前面D线性链表中的各元素在存储空间中的位置
8、不一定是连续的,且各元素的存储顺序也是任意的24.下列叙述中正确的是(A)A线性表是线性结构B栈与队列是非线性结构C线性链表是非线性结构D二叉树是线性结构25. 线性表 L( a1,a2,a3, ai, an) ,下列说法正确的是(D)A每个元素都有一个直接前件和直接后件B线性表中至少要有一个元素C表中诸元素的排列顺序必须是由小到大或由大到小D除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件26.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(连续不连续都可以)27. 链表不具有的特点是(B)A不必事先估计存储空间B可随机访问任一元素C插入删除不需要移动
9、元素D所需空间与线性表长度成正比28. 非空的循环单链表head的尾结点(由p 所指向),满足( p-next=head)29.与单向链表相比,双向链表的优点之一是(更容易访问相邻结点)30. 在( D)中,只要指出表中任何一个结点的位置,就可以从它出发依次访问到表中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 13 页 - - - - - - - - - 其他所有结点。A线性单链表B双向链表C线性链表D循环链表31. 以下数据结构属于非线性数据结构的是(C)A队列B线
10、性表C二叉树D栈32.树是结点的集合,它的根结点数目是(有且只有1)33.具有 3 个结点的二叉树有(5 种形态)34. 在一棵二叉树上第8 层的结点数最多是(128) 注: 2K-1 35. 在深度为5 的满二叉树中,叶子结点的个数为(16) 注: 2n-1 36. 在深度为5 的满二叉树中,共有(31)个结点。注: 2n 1 37.设一棵完全二叉树共有699 个结点,则在该二叉树中的叶子结点数为(350)说明: 完全二叉树总结点数为N,若 N 为奇数,则叶子结点数为(N+1)/2;若 N 为偶数,则叶子结点数为N/2。38. 设有下列二叉树,对此二叉树中序遍历的结果是(B)AABCDEF
11、BDBEAFC CABDECF DDEBFCA 39.已知二叉树后序遍历序列是dabec, 中序遍历序列debac, 它的前序遍历序列是 (cedba)40. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和 DBGEACHF ,则该二叉树的后序遍历为(DGEBHFCA )41.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca)42. 串的长度是(串中所含字符的个数)43.设有两个串p 和 q,求 q 在 p 中首次出现位置的运算称做(模式匹配)44. N 个顶点的连通图中边的条数至少为(N-1)45.N
12、 个顶点的强连通图的边数至少有(N)46.对长度为n 的线性表进行顺序查找,在最坏情况下所需要的比较次数为(N)47. 最简单的交换排序方法是(冒泡排序)48.假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为(n(n-1)/2 )49. 在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)50. 在最坏情况下,下列顺序方法中时间复杂度最小的是(堆排序)51. 希尔排序法属于(插入类排序)52. 堆排序法属于(选择类排序)53. 在下列几种排序方法中,要求内存量最大的是(归并排序)54. 已知数据表A 中每个元素距其最终位置不远,为节省时间, 应采用(直接插入排序)
13、55. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。1.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。1. 算法的复杂度主要包括时间复杂度和空间复杂度。2. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度。3.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。4.数据结构是指相互有关联的数据元素的集合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
14、 - 第 3 页,共 13 页 - - - - - - - - - 5.数据结构分为逻辑结构与存储结构,线性链表属于存储结构。6.数据结构包括数据的逻辑结构和数据的存储结构。7. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。8.数据元素之间的任何关系都可以用前趋和后继关系来描述。9.数据的逻辑结构有线性结构和非线性结构两大类。10.常用的存储结构有顺序、链接、索引等存储结构。11. 顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。12. 栈的基本运算有三种:入栈、退栈与读栈顶元素。13. 队列主要有两种基本运算:入队运算与退队运算。14. 在实际应用中,带链
15、的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。15.栈和队列通常采用的存储结构是链式存储和顺序存储。16.当线性表采用顺序存储结构实现存储时,其主要特点是逻辑结构中相邻的结点在存储结构中仍相邻。17. 循环队列主要有两种基本运算:入队运算与退队运算。每进行一次入队运算,队尾指针就进 1 。18.当循环队列非空且队尾指针等于对头指针时,说明循环队列已满,不能进行入队运算。这种情况称为上溢。19.当循环队列为空时,不能进行退队运算,这种情况称为下溢。20. 在一个容量为25 的循环队列中,若头指针front=16 ,尾指针 rear=9,则该循环队列中共有18 个元
16、素。注:当 rearfront 时,元素个数rearfront。1.判断链表是否存在环型链表问题:判断一个链表是否存在环,例如下面这个链表就存在一个环:例如 N1-N2-N3-N4-N5-N2就是一个有环的链表,环的开始结点是N5 这里有一个比较简单的解法。设置两个指针p1,p2。每次循环p1 向前走一步, p2 向前走两步。直到 p2 碰到 NULL 指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。struct link int data; link* next; ; bool IsLoop(link* head) link* p1=head, *p2 = head; if (h
17、ead =NULL | head-next =NULL) return false; do p1= p1-next; p2 = p2-next-next; while(p2 & p2-next & p1!=p2); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 13 页 - - - - - - - - - if(p1 = p2) return true; else return false; 2,链表反转单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题
18、。比如一个链表是这样的:1-2-3-4-5 通过反转后成为5-4-3-2-1 。最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中当前指针指向的下一个元素, 然后将当前节点元素的指针反转后,利用已经存储的指针往后面继续遍历。源代码如下:struct linka int data; linka* next; ; void reverse(linka*& head) if(head =NULL) return; linka*pre, *cur, *ne; pre=head; cur=head-next; while(cur) ne = cur-next; cur-next = pre;
19、 pre = cur; cur = ne; head-next = NULL; head = pre; 还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点,就是在反转后的最后一个结点会形成一个环,所以必须将函数的返回的节点的next 域置为 NULL 。因为要改变head指针,所以我用了引用。算法的源代码如下:linka* reverse(linka* p,linka*& head) if(p = NULL | p-next = NULL) head=p; return p; else 名师资料总结 - - -精品资料欢
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数据结构面试题 2022 数据结构 试题
限制150内