2009年计算机学科专业基础综合试题 - 第42题回答
（1）先遍历一次链表得到链表的长度，然后与k进行比较。若链表长度小于k，则返回0；若链表长度大于k，则遍历链表L至第L.length-k个位置并输出该结点data域的值并返回1。
(2)设置链表L引用头结点，然后遍历L至链表下一结点为空，计算出结点的个数，对结点个数同k值进行比较，如果结点个数没有k个，就查找不到倒数第k个位置。如果结点个数大于k个，则倒数第k个结点为顺数结点数减k个位置，遍历头结点，找到该位置并输出，返回1。
（3）
int seek(link *list.int k){
link L=link;
int length=0;//计算链表长度
while(L->next!=NULL)
{
length++;
}
if(k>length){
return 0;
}else{
for (int i=0;i<length-k;i++){
list=list->next;
}
cout<<list->data;
return 1;
}
}
评分及理由
（1）得分及理由（满分5分）
得分：3分
理由：学生的设计思想是遍历链表得到长度，再计算倒数第k个结点的位置。这种方法虽然正确，但需要遍历链表两次（一次计算长度，一次定位结点），而题目要求"尽可能高效的算法"，标准答案采用一趟扫描的方法。因此，虽然思路正确，但效率不高，扣2分。
（2）得分及理由（满分5分）
得分：3分
理由：详细实现步骤描述基本清晰，但同样存在效率问题。学生描述了先计算链表长度再定位的方法，这与标准答案的一趟扫描方法相比效率较低。步骤描述还算完整，但未达到最优效率要求，扣2分。
（3）得分及理由（满分5分）
得分：2分
理由：代码实现存在多处逻辑错误：
1. 函数参数语法错误："link *list.int k"应为"link *list, int k"
2. "link L=link"语法错误，应为"link L = list"
3. while循环中缺少"L = L->next"，导致死循环
4. for循环中"list=list->next"会修改原始链表头指针
5. 缺少链表结点结构定义
6. 使用了C++的cout输出，但函数声明为C风格
虽然算法思路正确...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发