上海交大十月份数据结构上机实验考试题 2012-11-17.doc

模拟题一、有一只猫抓了n (n1)个老鼠后向老鼠宣布：老鼠按自然数进行编号（1n），并按自然数顺序排队，以后先后次序不准变；于是猫每天吃掉编号为奇数的老鼠，剩下的老鼠再按原次序进行自然数编号，直至某一天只剩下一只小老鼠；而该小老鼠是猫从第一天起就想吃掉的那只，请问这只小老鼠的最初编号是几？（） 用链结构实现，链的每个节点所包含的“数据域”信息是老鼠的最初编号（从开始编号），另一个信息是链的下一节点地址。（） 建立一条有n个节点的链：先创建一个空链，然后向链尾插入n 个节点。（） 开始删除奇数节点：从链首开始删除“奇”节点，直至链尾；判断链是否只剩下一个节点？不是则循环执行上一步，是则结束循环。（） 输出结果。（） 程序编写完成后，请以f1.c或f1.cpp作为文件名存放到F盘上。答案：#include #include struct mouse /链“节点”类声明 int n; mouse *nextptr;int cat_mouse(int num) /函数定义 mouse *headptr=0,*tailptr=0,*frontptr,*p; int i;/先把1个老鼠加入链作为链首节点 headptr=tailptr=new mouse; assert(headptr!=NULL); /动态内存分配异常处理 headptr-n=1; /老鼠的编号 headptr-nextptr=NULL;/在链尾再添加n-1个老鼠 for(i=2;in=i; coutnnextptr=p; tailptr=p;tailptr-nextptr=NULL; /设置链尾节点的“下一节点地址”为空/开始删除老鼠while(headptr!=tailptr) /每循环一次，删除链上的奇节点，直至只剩下个节点 p=headptr-nextptr; /链的首节点总是先被删除 delete headptr; /析构首节点 headptr=frontptr=p; /本次循环的第个节点成为链的首节点 i=; /从第个节点开始循环：删除链的奇节点 while(p!=NULL) /从开始循环至链尾节点 if(i%2)=) /是奇节点 if (p-nextptr=NULL) /如果该奇节点是最后一个节点 frontptr-nextptr=NULL; /前一节点成为链的尾节点 tailptr=frontptr; delete p; p=NULL; /因本循环的判断条件是p!=NULL,到链尾，所以置为 else /是奇节点但不是尾节点，删除 frontptr-nextptr=p-nextptr; /从链上删除该奇节点 delete p; p=frontptr-nextptr; /下一节点的地址已保存在frontPtr的 nextPtr中 +i; /frontPtr成为被删节点的下一节点的上一节点，故值不变 else /不是奇节点，不删除 frontptr=p; p=p-nextptr; +i; return headptr-n; /返回最后一个节点的编号void main() /主函数 int i, num; docoutnum; if(num1) i=cat_mouse(num); cout最后剩下的一只老鼠是：iendl; while(num!=0);以下为软件运行环境实效（在C+6.0中书写好的答案截图）注意点：1、考试考号和座位号（上机号）