2014年4月全国高等教育自学考试数据结构导论试题_第2页

　　四、算法设计题(本大题共2小题，每小题7分，共14分)

　　34.设单链表及链栈S的结构定义如下：

　　typedef struct node

　　{ Data Type data;

　　struct node*next;

　　｝linkstack;

　　编写一个算法void ReverseList(1inkstack *head)，借助于栈S将带头结点单链表head中序号为奇数的结点逆置，序号为偶数的结点保持不变。(例如：单链表的逻辑结构为(a1，a2，a3，a4，a5，a6)，逆置后变为(a5，a2，a3，a4，a1，a6))。

　　说明：栈的初始化运算用InitStack(S);进栈运算用Push(S，x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。

　　35.以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。