破解php网站后台账号密码,wordpress二维码 插件下载,网站开发需要什么人,安庆网络推广和竞价昔我往矣#xff0c;杨柳依依 今我来思#xff0c;雨雪霏霏 契子✨ 有道是#xff1a;得选择题者得天下。临近考试#xff0c;便总结一下数据结构选择题的常考题型吧#xff0c;以及预测一下考点#xff0c;一来是为了备考#xff0c;二来可以水文。祝各位老铁 “挂柯南… 昔我往矣杨柳依依 今我来思雨雪霏霏 契子✨ 有道是得选择题者得天下。临近考试便总结一下数据结构选择题的常考题型吧以及预测一下考点一来是为了备考二来可以水文。祝各位老铁 “挂柯南”
春风得意马蹄疾一日看尽长安花
哈哈 ~ 首先我先来预言一波题型虽然我们的考卷可能不是同一张但是知识点大差不差
1求一个程序的时间复杂度
这个题型对各位老铁来说是送分项但是越是简单越要谨慎小心有坑 ~
简单出道题吧让大家熟悉一下其实没什么要讲 分析以下函数的时间复杂度 A.O(n) B.O(n^2) C.O(nlogn) D.O(logn) void fun(int n)
{int il;while(in)ii*2;
} 答案D 解析: 此函数有一个循环但是循环没有被执行n次i 每次都是 2倍 进行递增所以循环只会被执行 log2(n) 次 这类题型只会出道程序并要求算出时间复杂度没有什么概念的东西考的是对程序的理解复习的时候了解一下便可 2顺序表考基本概念
到了顺序表这里基本上就是考概念了比如指定位置的插入、删除要移动多少个位置什么时候操作需要干什么。有时候还会和链表结合起来考比如比起链表顺序表的优势是什么
这里总结一下之前做到的题型前面的都很简单直到树后面就有点难度了 在长度为 n 的顺序表下标为 i 的位置前插入一个元素1 ≤ i ≤ n1元素的移动次数为
A.n - i 1
B.n - i
C.i
D.i - 1 答案B 解析 方法一这里先教提醒老铁们一个简单笨方法你就不要去想直接模拟就行 ~ 根据上图所示长度为 n 我设置数字长度为 5 模拟插入一个元素要挪动几次 我们先要插在 数组2 的位置挪动了 3 次是不是和我们的选项 B n-i相符合 这相当于知道结果去推答案但是做的出来就行 方法二顺序表插入元素需要移动元素这里需要把[i, n - 1]区间的元素全部向后移动一次故移动的次数为n - 1 - i 1也就是n-i 在一个长度为n的顺序表中删除第i个元素要移动_______个元素。
如果要在第i个元素前插入一个元素要后移_________个元素。
A、n-in-i1
B、n-i1n-i
C、n-in-i
D、n-i1n-i1 答案A 解析 这里再出一个类似的题顺序表还是比较喜欢考这个 我们先来分析一下 要删除顺序表中的第 i 个元素就是将区间 [i1n] 的元素全部向前移动一个单位再加一也就是 n - (i1) 1 也就是 n-i 要在顺序表第 i 个元素前插入数据就是在区间 [in] 的元素全部向后移动一个单位再加一也就是 n - i 1 为什么要加 1 呢因为数组是从 0 开始的 动态顺序表中操作需要检查是否需要扩容A.删除
B.插入
C.初始化
D.清空 这道题简单直接说答案吧看这就是送分题是对顺序表概念的考察 答案B 解析插入操作需要考虑空间是否足够如果不够需要先增容再进行插入 3链表考概念和结构
顺序表和链表都是比较简单的数据结构个人感觉考的不会很多但是也不能不复习是吧接下来我将归纳一下大概率会考的知识点
1链表和顺序表的功能优异
2链表的链接顺序极大概率、因为真的没什么考的了个人感觉勿喷
3双向循环链表可以看一下
接下来我将会以选择题的形式带各位老铁回忆以往的知识点 对于双向循环链表每个结点有两个指针域next和prior分别指向前驱和后继。
在p指针所指向的结点之后插入s指针所指结点的操作应为
A、p-nexts;p-next-priors;s-priorp;s-nextP-next;
B、s-priorp;s-nextp-next;p-nexts;p-next-priors;
C、p-nexts;s-priorp;p-next-priors;s-nextp-next;
D、s-priorp;s-nextp-next;p-next-priors;p-nexts; 双向循环链表也是链表链接的方法都一样可以试试做做这道题看看链表的结构自己到底掌握了多少 我们先来回顾一下双向链表的结构 既然是结构题考链表的结构那么就少不了画图我们先将图简单画一下要求是 P 指针之后插入 S节点 。链接方法有很多但是不要傻傻的不看选项不看自己模拟这样效率不高还容易将自己搞混。 最实在的办法就是看选项判对错我先带老铁们走一遍 先来到选项A p-nexts;p-next-priors;s-priorp;s-nextP-next; 这个时候就变这样了这个样子 p 先和 q 断了联系转身牵起 s 的手这个时候 p 已经没有 q 的联系方式了又怎么能通过 p 找到 q 呢p 的现任是 s 啊p 的 next 存的是 s 的联系方式。所以一下的这段代码逻辑是有问题的 p-next-priors 这个时候 p 的下一个存的应该是 s 的联系方式那么毫无疑问 A 不能选 那么方法我已经教会你了就是根据选项画图模拟其三角恋的过程 我们再看一个选项吧我们来到选项B s-priorp;s-nextp-next;p-nexts;p-next-priors; 1 2 错的还是这个地方 p-next-priors; 通过 p-nexts 操作p 已经没有 q 的联系方式了但是题目还想让我们用原来的联系方式找到 q p 的现任是 s 啊p 的 next 存的是 s 的联系方式所以 B 也不能选不知道我这么说老铁们听不听得懂应该很好理解吧 相信老铁们应该很快掌握了该题的方法了吧我就直接公布答案了 答案D 在单链表指针为p的结点之后插入指针为s的结点正确的操作是
A.p-nexts; s-nextp-next;
B.p-nexts-next; p-nexts;
C.s-nextp-next; p-nexts;
D.p-nexts-next; p-nexts; 上面的那道题会了的话这道题就是小试牛刀了 别的不说考试的时候我们不求快但要求稳不熟的话还是先画个图吧 因为很简单嘛我就直接模拟正确答案了 s-nextp-next p-nexts 这样我们的链表就链接成功了 所以正确答案自然选择 C 在一个单链表中q 的前一个节点为 p删除 q 所指向节点时以下代码正确的执行语句及次序是
A、q-nextp-next;
B、p-nextq-next;
C、delete p;
D、delete q; 以后碰到这种结构题不会的都要给我画图模拟一下不要看到就不知所措 1 2 3 答案D 解析 首先要更新链接再删除 q 节点 以下属于链表的优点的是
A、用数组可方便实现
B、插入操作效率高
C、不用为节点间的逻辑关系而增加额外的存储开销
D、可以按元素号随机访问 然后就是链表的概念题了很简单。我只是放出题型让大家兜个底其实就是基本的概念。链表和顺序表要考的话也是与栈和队列联系起来考的多 答案B毫无疑问、不用挪动数据效率贼高 下列关于链表的说法哪个是正确的
A.插入或删除时无需移动其他元素
B.数据在内存中一定是连续的
C.需要事先估计存储空间
D.可以随机访问表内的元素 答案A 解析链表插入删除元素只需要修改指针指向不需要移动元素。链表是用指针链接前后节点数据在内存中不一定连续每次插入元素都是先出开一个节点的空间不需要事先估计存储空间并且链表没有索引不能随机访问 关于链表和顺序表间的区别叙述错误的是
A.链表和顺序表都属于线性表
B.链表不能随机访问其中的某个元素顺序表可以
C.链表能做的事顺序表都可以完成只是操作方法不同效率不同
D.链表在进行插入和删除的时候速度总是比顺序表快 答案D 解析链表的插入和删除不是所有情况下都比顺序表快比如尾插尾删顺序表的时间复杂度为O1并且如果是单链表如果要在中间某个节点的前面插入/删除一个节点则需要遍历。所以时间的快慢要分情况看待哦 在长度为n(n1)的单链表上设有头和尾两个指针执行操作与链表的长度有关。
A.在单链表第一个元素前插入一个新元素
B.在单链表最后一个元素后插入一个新元素
C.删除单链表中的第一个元素
D.删除单链表中的最后一个元素答案D 解析A选项为头插不需要遍历链表B选项为尾插也不需要遍历链表C选项为头删不需要遍历链表只有D选项为尾删需要遍历单链表找到尾节点的前一个节点。所以与长度有关 4栈考入栈出栈逻辑、先进后出的结构
根据我以前做题的经验来看栈最喜欢考入栈出栈逻辑从概率学的角度讲期末考的可能性高达百分之八十。废话不多说我先分析一下考点。还是水文水多了忘记放图缓解一下了 1入栈出栈逻辑通常是给出入栈顺序判断出栈顺序是否正确
2先进后出的概念题一般与队列先进先出的结构结合起来考
3我们知道我们的栈分为顺序栈和链栈、顺序栈考的多但是链栈也要看一下真没见过什么链栈的题、了解一下概念即可
4就是有些难题可能会用栈模拟队列最好了解一下、下面的题型都会提到 一个栈的入栈序列为ABCDE则不可能的出栈序列为
A.ABCDE
B.EDCBA
C.DCEBA
D.ECDBA 这里先来给老铁提供一下做这种题的思路 虽然我们知道入栈顺序、但是出栈往往并不是等所有数据入完再出的而是你的栈里有数据我便可以在这个时候出数据而出数据必须从栈顶出、顺序很重要。 那我们该如何判断呢如果你把所有的情况枚举一遍再判断毫无疑问效率十分低下最好的办法就是从选项入手通过画图模拟的方法判断 首先我们来看看选项 A ABCDE 虽然我们的数据 A 先入了栈但是 A 也可以先出因为栈顶的元素就是 A 本身 这么考虑的话A选项 的这种出栈顺序是可行的 因为 B选项 很好看出来我们不妨分析一下 C 选项 DCEBA 因为 D 先出栈的话那么 A、B、C 皆以入栈那么 D 出栈后栈顶便是 C所以 C 可以直接出栈如果这个时候 E 入栈也可以直接出根据入栈数量我们来还剩下 A、B根据入栈顺序我们便知道栈顶元素就是 B所以 C 的逻辑也没有问题 因为正确选项一般很容易分辨出来大家学会逻辑便可我们分析一下这个选项D ECDBA 这个时候我们就要开始思考了如果是 E 先出栈的话那么 A、B、C、D 皆以入栈而这个时候 D 就应该是栈顶如果再要出栈应该是D而不应该是C这就是出栈先后的逻辑问题 故答案应该选择 D 我们再来看一道概念题 ~ 下列关于栈的叙述正确的是
A.栈是一种“先进先出”的数据结构
B.栈可以使用链表或顺序表来实现
C.栈只能在栈底插入数据
D.栈不能删除数据 这就是考概念的题了应该难不倒你吧我放出来就是为了让你知道可能会出怎样的题型 A 错误栈是一种后进先出的数据结构队列是先进先出的 B 正确顺序表和链表都可以用来实现栈不过一般都使用顺序表因为栈想当于是阉割版的顺序表只用到了顺序表的尾插和尾删操作顺序表的尾插和尾删不需要搬移元素效率非常高故一般都是使用顺序表实现 C 错误栈只能在栈顶进行输入的插入和删除操作 D 错误栈是有入栈和出栈操作出栈就是从栈中删除一个元素 链栈与顺序栈相比比较明显的优点是
A.插入操作更加方便
B.删除操作更加方便
C.入栈时不需要扩容 链栈如果要考的话应该也只是考概念就像以上类型差不多和顺序栈作比较体现其功能 链栈的话顾名思义就是用链表模拟栈。入栈出栈一般需要进行头插或者头删操作插入操作则需要扩容在链接删除操作还需要移动头指针在进行释放。而顺序栈一般进行尾插和尾删操作。因为是数组插入操作直接入元素再 size 便可删除操作直接 size-- 便可。所以这两个操作毫无疑问是顺序表更为方便。 而链栈的优势就是链式结构实现栈时每次入栈相当于链表中头插一个节点没有扩容一说 故答案应该选择 C 下列关于用栈实现队列的说法中错误的是
A.用栈模拟实现队列可以使用两个栈一个栈模拟入队列一个栈模拟出队列
B.每次出队列时都需要将一个栈中的全部元素导入到另一个栈中然后出栈即可
C.入队列时将元素直接往模拟入队列的栈中存放即可
D.入队列操作时间复杂度为O(1) 这道题就是我们之前提到过的用栈模拟队列考的是对栈、队列结构的了解程度 我们先来看一下选项A 这道题如果在力扣刷过题的老铁应该能一眼就能排除 栈和队列的特性是相反的一个栈实现不了队列所以需要双栈的思想是正确的故A正确 我们再来分析一下选项B 一个栈模拟入队列一个栈模拟出队列出队列时直接弹出模拟出队列栈的栈顶元素当该栈为空时将模拟入队列栈中所有元素导入即可不是每次都需要导入元素故B错误 选项C一个栈模拟入队列一个栈模拟出队列入队列时将元素直接往模拟入队列的栈中存放故C正确 选项D入队列就是将元素放到栈中因此时间复杂度就是O(1)故D正确 故答案应该选择 B 5队列考概念、结构还有循环队列 队列先进先出的数据结构反正概念是必考的大概率会与栈结合来考。简单复习一下应该没什么问题其次便是结构了我们的队列也有顺序队列、链式队列链式队列没什么考点而顺序队列还可以考进入循环的条件很大概率、画个重点复习
废话说完了先预测一下考点吧
1队列先进先出的结构与概念喜欢与栈结合起来考所以两个数据结构都要懂
2循环队列的循环条件
其他的好像就没怎么遇到了那我们先来讲一讲这两个知识点的题吧 下列关于队列的叙述错误的是
A.队列可以使用链表实现
B.队列是一种“先入先出”的数据结构
C.数据出队列时一定只影响尾指针
D.数据入队列时一定从尾部插入 我们先来一道概念题吧熟悉一下 ~ 答案C 解析 出队操作一定会影响头指针如果出队之后队列为空会影响尾指针 用无头单链表存储队列其头指针指向队头结点尾指针指向队尾结点则在进行出队操作时
A.仅修改队头指针
B.队头、队尾指针都要修改
C.队头、队尾指针都可能要修改
D.仅修改队尾指针 像这种题就是结构题了需要对队列的结构有比较清晰的认识 对付结构题的最好方法就是画图画图画图 通过画图我们可以清晰的了解到我们用单链表模拟的队列是从尾指针的地方入数据、头指针的地方出数据的结构这里就不画了) 而题目要求进行入队操作时怎么样这其实隐藏着一个大坑稍有不慎便可能陷进去 因为他没说现在是什么状态队列中有多个元素还是只有一个元素这里要分两种情况 如果有多个元素就是上面图片的那一种情况但是如果只有一个元素呢 我们就还需要多进行一步操作 首尾指针都要置为空因为此时队列为空 答案C 解析 出队操作一定会修改头指针如果出队之后队列为空需要修改尾指针 个人感觉字多犯困 ~ 放个图缓解一下氛围 下面关于栈和队列的说法中错误的是多选题
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”栈是“先入后出” 队列与栈还喜欢结合起来一起考 ~ 就像这道题一样简单来讲就是间接考了两者的概念与结构 要不你们先思考一下我先摸个鱼 ~ 我先来看一下选项A 栈是尾部插入和删除一般使用顺序表实现队列是头部删除尾部插入一般使用链表实现所以A错误 B也错误栈是后进先出尾部插入和删除队列是先进先出尾部插入头部删除 C正确栈只能访问栈顶元素不支持随机访问队列也不支持 D就不用说了吧 故此答案选择A、B 现有一循环队列其队头为front队尾为rear(rear指向队尾数据的下一个位置)循环队列长度为N,最多存储N-1个数据。其队内有效长度为
A.(rear - front N) % N 1
B.(rear - front N) % N
C.(rear - front) % (N 1)
D.(rear - front N) % (N - 1) 循环队列大概率会考我相信我的直觉 ~ 因为再不考就没东西考了复习的时候看一下 所以我为各位老铁准备了两道循环队列的题 以上便是其中之一废话说完了先来分析一下题目 不知道循环队列的结构大家是否还记得 回到正题首先我们来看题目说求有效长度 有效长度如果根据我们数组来计算的话就是 rear - front 但是这里是循环队列环形也就是说 rear 可能比 front 还要小减完之后可能是负数所以需要 N此时结果刚好是队列中有效元素个数。 但是如果 rear 大于 front 减完之后就是有效元素个数了再加 N 后有效长度会超过 N 这么整岂不是越界了不要急我们只要 % N 就可以了 所以答案选择 B 下列关于顺序结构实现循环队列的说法正确的是
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构 这道题便是循环队列的概念题 ~ 所以概念不熟的赶紧去复习吧 A错误循环队列的长度都是固定的 B错误队头和队尾在同一个位置时队列可能是空的也可能是满的因此无法判断 C正确设置计数即添加一个字段来记录队列中有效元素的个数如果队列中有效元素个数等于空间总大小时队列满如果队列中有效元素个数为0时队列空 D错误循环队列也是队列的一种是一种特殊的线性数据结构 故选择 C 6二叉树考概念和画图 个人感觉二叉树的题目会考的相对多一点因为考点多、难度刚刚好吧既没有栈和队列那般简单也没有图那么刁钻。废话不多说先来总结一下题型
1给出一个二叉树的结点数求叶子节点这类题型很多有给出叶子求结点数的也有给出结点数求深度的考概念 -- 边与度的关系
2画图题根据前或后序加一个中序推出另一个后或前序为什么我要把它归为画图题呢因为画图便是解法这里简单提一下吧通过前或后序中序便可以画出二叉树的图形通过二叉树的图形便可以推出另一个二叉树序列。这种类型题很重点个人感觉必考题需要加强复习
3二叉树的性质记住左孩子右兄弟和数组表示法便可大概就是给出孩子节点求双亲节点
4堆的概念可能也会考不过是结合排序来考以后总结排序的时候再讲
5哈夫曼树主要也是考带权路径长度
关于二叉树我之前总结过了感觉大差不差今天就拿过来用吧主要就是想水
二叉树选择题集合点击链接便可跳转 今天就分享到这吧 ~ 我还要去搞 UE 在自己设计的游戏中当男主
往后会总结串、图的内容
关于这一期主要是帮助那些学的不是很扎实的老铁提供一下复习思路顺便自己在回顾一下
就这样 ~ 下期再见
