计算机考研数据结构统考历年真题答案2009-2015.doc

2009 1-5：BCDBC6-10：BADBA41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为ABC，事实上其最短路径为ADC。 42.（1）算法的基本设计思想：定义两个指针变量p和q，初始时均指向头结点的下一个结点。P指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。 （2）算法的详细实现步骤： count=0,p和q指向链表表头结点的下一个结点； 若p为空，转； 若count等于k,则q指向下一个结点;否则,count=count+1; p指向下一个结点，转步骤； 若count等于k,则查找成功,输出该结点的data域的值,返回1;返回； 查找失败,返回0; 算法结束。（3）算法实现：typedef struct LNode int dat