（ 1 ）用 C 语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构）。数据结构的设计应考虑对问题的清楚描述和算法的效率；

（ 2 ）用 C 语言写出你的算法。算法应简洁、高效。对算法中的参数、变量、语句做必要的注释，以增加可读性；

（ 3 ）简单分析你的算法的空间开销和时间开销。

8．已知一棵树的边的结合为 {(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)}, 试画出这棵树，并回答下列问题：（ 20 分）

（ 1 ）哪个是根节点？    

（ 2 ）哪些是叶子节点？    

（ 3 ）树的深度是多少？     

（ 4 ）写出该树的前序遍历序列    

南京师范大学2007年GIS专业研究生入学《C语言程序设计》考试试题

C语言程序设计

（1）设S为一个长度为n的字符串，其中串的字符各不相同，写出具体程序并计算出S中互异的非平凡子串，非空且不同于S本身的个数。（本题15分）。

（2）编写一个程序，对输入的任意正整数n，打印出集合{0，1，2，3，...，n-1}的所有子集。（本题15分）。

（3）已知非空线性链表第一个节点由list指出，请写一个算法交换P所指的节点与其下一个节点在链表中的位置(设P指向的不是链表最后那个结点）。（本题20分）。

（4）对给定的n（n≤10)计算并输出K！（K=1，2，3，...，n)的全部有效数字。（本题20分）。

（5）用递归算法和栈实现m个相异元素构成的有序序列的二分查找，并计算出该栈的最小容量。（本题20分）。

（6）已知平面上（直角坐标系）的m个点，请编写一个函数，求同一条直线所能通过的最多点数。（本题20分）。

（7）用程序设计有n个叶子结点的Huffman树的结点个数。（本题20分）。

（8）依次输入表（30，15，28，20，24，10，12，68，35，50，46，55）中的元素，生成一棵二*排序树。（本题20分）。

      ①试画出生成之后的二*排序树。

      ②若该二*排序树作中序编历，试写出编历序列。

      ③假设每个元素的查找概率相等，试计算该二*排序树的平均查找长度。