冲刺必会代码100题.docx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《冲刺必会代码100题.docx》由用户(最好的沉淀)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 冲刺 代码 100
- 资源描述:
-
1、冲刺必会代码 100 题顺序表1、已知线性表(a1,a2,an)按顺序结构存储且每个元素为不相等的整数。设计把所有奇数移动到所有偶数前边的算法(要求时间最少,辅助空间最少)。【算法思想】:对于顺序表 L,从左向右找到偶数 L.datai,从右向左找到奇数L.dataj,将两者交换。循环这个过程直到 i 大于 j 为止。对应的算法如下:void move(SqList &L)int i = 0, j = L.length-1, k; ElemType temp;while(i = j) while(L.datai%2 = 1) while(L.dataj%2 = 0) if(i j) L.dat
2、ai = L.dataj; L.dataj = temp;/交换 L.datai和 L.datajtemp = L.datai;/j 指向一个偶数j-;/i 指向一个偶数i+;本算法的时间复杂度为 O(n),空间复杂度为 O(1)。2、设计一个高效算法,将顺序表 L 中所有元素逆置,要求算法的空间复杂度为 O(1)。【算法思想】:扫描顺序表 L 的前半部分元素,对于元素 L.datai,将其与后半部分对应元素 L.dataL. length-i-1进行交换。对应的算法如下:void reverse(SqList &L)int i; ElemType x;for(i = 0; i C.lengt
3、h)/表长超过return false; int i = 0, j = 0,k = 0; while(i A.length & jB.length) /循环,两两比较,小者存入结果表 if(A.datai = B.dataj) C.datak+ = A.datai+; else C.datak+ = B.dataj+; while(i A.length) C.datak+ = A.datai+; while(j B.length) C.datak+ = B.dataj+; C.length = k; return true;4、从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除元素的
4、值。空出的位置由最后一个元素填补。【算法思想】搜素整个顺序表,查找最小值元素并记在其位置,搜索结束后用最后一个元素填补空出的原最小值元素的位置。bool Delete_Min(SqList &L ,ElemType &value)/删除顺序表 L 中最小值元素结点,并通过引用型参数 value 返回其值 if(L.length = 0)return false; /表空,终止操作 value = L.data0;int pos = 0; /假设 0 号元素的值最小 for(int i = 1; iL.length; i+) /循环遍历,寻找具有最小值的元素 if(L.datai value)
5、/让 value 记忆当前具有最小值的元素 value = L.datai; pos = i;L.datapos = L.dataL.length-1; /空出的位置由最后一个元素填补 L.length-; return true;5、已知长度为 n 的线性表 L 采用顺序存储结构,编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法,该算法删除线性表中所有值为 x 的数据元素。【算法思想】解法 1:用 k 记录顺序表 L 中等于 x 的元素个数,边扫描 L 边统计 k,并将不为 x 的元素前移 k 位,最后修改 L 的长度。对应的算法如下:void del_x(SqList &L,
6、ElemType x)int k, i = 0;/k 用于记录 L 中值等于 x 的元素个数,初试值为 0 while(iL.length) if(L.datai = x)k+;/k 自增 else L.datai-k = L.datai;/将不为 x 的元素元素前移 k 个位置 i+; L.length = L.length-k;/顺序表长度较少 k解法 2:用 i 从头开始遍历顺序表 L,k 置初始 0。若 L.datai不等于 x,则将其存放在 L.datak中,k 增 1;若 L.datai等于 x,则跳过继续判断下一个元素。最后顺序表长度置为 k。对应算法如下。void del_x(
7、SqList &L, ElemType x)int i; k = 0;/k 用于记录 L 中值等于 x 的元素个数,初试值为 0for(i = 0; iL.length; i+) if(L.datai != x) L.datak = L.datai; k+;L.length = k;/表长置为 k6、设计一个算法,从一给定的顺序表 L 中删除元素值在 x 到 y(xy)之间的所有元素, 要求以较高的效率来实现,空间复杂度为 O(1)。【算法思想】解法一:本题是上诉题目的变形。可以采用上诉解法一的方法,只是将 L.datai = xint i,k = 0;for(i = 0; j= x & L.
8、datai = x & L.datai = y。void del_xy(SqList &L, ElemType x, ElemType y)解法二:void del_xy(SqList &L, ElemType x, ElemType y)int i = 0, k = 0; while(i= x & L.datai 1)个整数存放在一维数组R 中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法,将 R 中保存的序列循环左移 p( 0pn ) 个 位 置 , 即 将 R 中 的 数 据 由 ( x0,x1,xn-1 ) 变 换 为 ( xp, xp+1,xn-1,x0,x1,xp-1)。
9、要求:(1) 给出算法的基本设计思想;(2) 根据算法设计思想,采用 C 或 C+语言描述,关键之处给出注释(3) 说明你所设计算法的时间复杂度和空间复杂度。【算法思想】先将 n 个数据 x0,x1, ,xn-2,xn-1 原地逆置,得到 xn-1,xn-2,x,x0,然后再将 n-p 个数据和后 p 个数据分别原地逆置, 得到最终结果: xp, xp+1,xn-1,x0,x1,xp-1void Reverse(int R, int left, int right) /将数组原地逆置i = left, j = right;while(i 0 & pnext;/pa 是链表 La 的工作指针,初
10、始化为首元结点pa = La-next; while(pa & pb)if(pa-data data) /取较小者 Lb 中的元素,将 pb 链接在 pc 的后面,pb 指针后移pc-next = pa;pc = pa;/if pa = pa-next; else if(pa-data pb-data)pc-next = pb; /取较小者 Lb 中的元素,将 pb 链接在 pc 的后面,pb 指针后移pc = pb; pb = pb-next;/else if elsepc = pa; pc-next = pa; pa = pa-next;q = pa-next;free(pb);pb =
11、q; pc-next = pa?pa:pb;/将非空的剩余元素直接链接在 Lc 表的最好free(Lb);/释放 Lb 的头结点2、将两个非递减的有序表合并为一个非递增的有序表。要求结果链表仍然使用原来两个链表的存储空间,不占用另外的存储空间。表中允许有重复的数据。【算法思想】与上述题目类似,从原有两个链表中依次摘取结点,通过更改结点的指针域重新建立新的元素之间的线性关系,得到一个新链表。但与上面题目不同的点有两个:为保证新表与原表顺序相反,需要利用前插法建立单链表,而不能利用后插法;当一个表到达表尾结点为空时,另一个非空表的剩余元素应该依次摘取,依次链接在 Lc 表的表头结点之后,而不能全部
12、直接链接在 Lc 表的最后。算法思想是:假设待合并的链表为 La 和 Lb,合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针, 初始化为相应链表的首元结点。从首元结点开始进行比较,当两个链表 La 和 Lb 均为到达表尾结点时,依次摘取其中较小者重新链接在 Lc 表的表头结点之后, 如果两个表中的元素相等,只摘取 La 表中的元素,保留 Lb 表中的元素。当一个表到达表尾结点为空时,将非空表的剩余元素依次摘取,链接在 Lc 表的表头结点之后。最后释放链表 Lb 的头结点。void MergeList(LinkLi
13、st &La, LinkList &Lb, LinkList &Lc)/将两个非递减的有序表 La 和 Lb 合并为一个非递增的有序链表 LcLc-next = NULL;/用 La 的头结点作为 Lc 的头结点Lc = pc = La;/pb 是链表 Lb 的工作指针,初始化为首元结点pb = Lb-next;/pa 是链表的 La 的工作指针,初始化为首元结点pa = La-next;/La 表为空,用 q 指向 pb,pb 指针后移if(!pa)/只要有一个表未到达表尾指针,用 q 指向待摘取的元素while(pa | pb)q = pb; pb = pb-next;else if(!p
14、b)/Lb 表为空,用 q 指向 pa,pa 指针后移q = pa; pa = pa-next; else if(pa-data data)/去较小者 La 中的元素,用 q 指向 pa,pa 指针后移q = pa;/去较小者 Lb 中的元素,用 q 指向 pb,pb 指针后else pa = pa-next;移q = pb;pb = pb-next;Lc-next = q;free(Lb)q-next = Lc-next;3、已知两个链表 A 和 B 分别为两个集合,其元素递增排列。请设计一个算法, 用于求出 A 与 B 的交集,并存放在 A 链表中。【算法思想】A 与 B 的交集是指同时出
15、现在两个集合中的元素,因此,此题的关键点在于:依次摘取两个表中相等的元素重新进行链接,删除其他不等的元素。算法思想是:假设待合并的链表为 La 和 Lb,合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针, 初始化为相应链表的首元结点。从首元结点开始进行比较,当两个链表 La 和 Lb 均为到达表尾结点时,如果两个表中的元素相等,摘取 La 表中的元素,删除 Lb 表中的元素;如果其中一个表中的元素较小,删除此表中较小的元素,此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点为空时,依次删除另一个非空表
16、中的所有元素。最后释放链表 Lb 的头结点。void Intersection(LinkList &La, LinkList &Lb, LinkList &Lc)/pb 是链表 Lb 的工作指针,初始化为首元结点pb = Lb-next;/pa 是链表 La 的工作指针,初始化为首元结点pa = La-next;/相等,交集并入结果表中if(pa-data = pb-data)while(pa & pb)/用 La 的头结点作为 Lc 的头结点Lc = pc = La; pc-next = pa;pc = pa;u = pb; pa = pa-next; pb = pb-next;free(u
17、); else if(pa-data data)/删除较小者 La 中的元素 u = pa;pa = pa-next;free(u);else/删除较小者 La 中的元素u = pb;pb = pb-next;free(u);while(pa)/Lb 为空,删除非空表 La 中的所有元素u = pa;pa = pa-next;free(u);while(pb)/La 为空,删除非空表 Lb 中的所有元素u = pb;pb = pb-next;free(u);pc-next = NULL;free(Lb)4、已知两个链表 A 和 B 分别表示两个集合,其元素递增排列。请设计两个算法求出两个集合
18、A 和 B 的差集(即仅由在 A 中出现而不在 B 中出现的元素所构成的集合),并且以同样的形式存储,同时返回该集合的元素个数。【算法思想】求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素,即删除链表中的数据域相等的结点。由于要删除结点,此题的关键点在于:在遍历链表时,需要保存待删除结点的前驱。算法思想是:假设待求的链表为 La 和 Lb,pa 和 pb 分别是链表La 和 Lb 的工作指针,初始化为相应链表的首元结点。pre 为 La 中 pa 所指结点的前驱结点的指针,初始化为 La。从首元结点开始进行比较,当两个链表 La 和 Lb 均未到达表尾结点时,如果 L
展开阅读全文