必看!!!!!数据结构期末复习题及部分答案解析

} LNode, *Linklist;

5 写一算法，Contrary(linklist &L) ,对一带头结点且仅设尾指针L的循环单链表就地逆置。（即表头变表尾，表尾变表头。） 6 已知线性表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。试写一高效 的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释 放被删结点空间，并分析你的算法的时间复杂度。 单链表结点的类型定义如下： typedef struct LNode { int data;

struct LNode *next; } LNode, *Linklist;

7 写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注:不破坏A和B 的原有结构.)Merge(Linklist A, Linklist B, Linklist &C ) 8 写一算法Oplinklist(linklist L,int i;int j )

删除单链表中第i个元素,并将之插入至原表中的第j个元素之前. 9 写出求单链表长度算法 int length(linklist L) 10 若将循环队列Q的结构定义为： #define m 100 //最大队列长度 typedef struct

{ QElemType *base; //存储空间基址

int rear; //尾指针，若队列不空，指向队尾元素 int length; //当前队列的长度，即元素个数 } SqQueue;

试写出相应初始化、入队列和出队列的三个函数。 11二叉树用二叉链表存储表示。 typedef struct BiTNode { TelemType data;

Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;

试编写销毁二叉树T的算法DestroyBiTree ( BiTree &T)。

12二叉树用二叉链表存储表示。 typedef struct BiTNode { TelemType data;

Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;

试编写算法，求元素值为x的结点的左孩子（返回x的左孩子的指针）。 13 设计一算法，计算给定二叉树T中度为2的结点个数。 14编一算法：按层序遍历二叉树T。

15试编写先序遍历二叉树T的递归算法PreorderBiTree ( BiTree &T)。 16 写出一个将树中每个结点的左右孩子对换的算法 SWAPTREE(T) 即如:

原二叉树 转换后 T SWAPTREE(T)

↓ ↓

(A) (A)

/ \\ / \\ (B) (C) (C) (B) / \\ / \\ / \\ (D) (E) (F) (F) (E) (D) \\ \\ / /

(G) (H) (H) (G)

17 二叉树用二叉链表存储表示。

试编写后序遍历二叉树T的递归算法PostorderBiTree ( BiTree 18 写一个计算二叉树中叶子结点个数的递归算法。

T)。