上机练习题-A省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件

《数据结构》第一次上机练习题班级：通信1105,1106,地点：南一楼东203，

时间：第3,7,10周周一晚上第9至第12节课2.

班级：通信中英班地点：南一楼东208

时间：第3，7，10周周四早晨第1节至第4节课上机要求：上机内容为设计一些算法，编译经过。考评方式是对每一个算法，利用计算机屏幕截屏方式，截取两张图，一张是程序本身图，一张是程序运行结果图。图片命名方式为：学号_姓名_算法01_1.jpg,学号_姓名_算法01_2.jpg。学生程序设计截屏图，将自行保留，依据需要抽查一些学生截屏图。每个同学需要在程序和程序结果中间突出地显示出学生信息，学号，姓名，班级，以及适当注释和输出结果说明。1/71《数据结构》第一次上机练习题练习题划分：每位同学上机完成6道题练习，出12张截屏图（截屏图为JPG格式，自行保留至U盘，晚上上课时带到课堂）。练习题12道和应用题2道。学号最终一位为奇数做奇数练习题，即学号位数为1,3,5,7,9做练习题1,3,5,7,9,11。学号最终一位为偶数做偶数练习题，即学号位数为0,2,4,6,8做练习题2,4,6,8,10,12。注意：全部算法必须事先在上机前在初稿本上完成，上机只是为了进行测试。全部算法均生成EXE可执行文件，上机测试后请保留这些文件，等候抽查。2/72【问题01】(递归，链表)假设一个不带头结点单链表h中全部结点数据域都为整数，设计一个递归算法求其中最大值？【问题02】(次序表)设将n(n>1)个整数存放到一维数组R中。设计一个时间和空间两方面尽可能高效算法，将R中整数序列循环左移p(0<p<n)个位置，即将R中数据序列(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X1,…,Xp-1)，要求依据设计思想，设计算法，关键之处给出注释。3/73【问题03】（次序表）设有一个次序表L，其元素为整型数据，设计一个算法将L中全部小于0整数放在前半部分，大于等于0整数放在后半部分。【问题04】（单链表）设C={a1,b1,a2,b2,…,an,bn}为一线性表，采取带头结点hc单链表存放，设计一个就地算法，将其拆分为两个线性表A={a1,a2,…,an},B={b1,b2,…,bn}，拆分后线性表分别用带头结点单链表存放。【问题05】（单链表）设C={a1,b1,a2,b2,…,an,bn}为一线性表，采取带头结点hc单链表存放，设计一个就地算法，将其拆分为两个线性表A={a1,a2,…,an},B={bn,bn-1,…,b1}，拆分后线性表分别用带头结点单链表存放。4/74【问题06】（单链表）用单链表表示集合，设计一个算法求两集合交集，并将结果存放入另一个单链表中。13^4A【问题07】（单链表）用单链表表示集合，设计一个算法求两集合并集，并将结果存放入另一个单链表中。15^3B1…^3A∩B13A∪B4^55/75【问题8】（单链表）已知一个带表头结点单链表只给出了头指针list。在不改变链表前提下，设计一个尽可能高效算法，查找链表中倒数第k个位置上结点(k为正整数)。若查找成功，算法输出该结点data域值；不然，返回0。要求：依据设计思想和步骤，给出算法，关键之处给出注释。【问题9】（双链表）设有一个带头结点双链表L，设计一个算法用于删除全部值为x结点，假设这么结点不唯一。6/76【问题10】（循环双链表）设有一个带头结点循环双链表L=(a1,a2,…,an-1,an)。设计一个时间复杂度为O(n)算法，将L改造成L=(a1,a3,a5,…,an,…,a6,a4,a2)。【问题11】（栈）