- —四川最大高校综合门户网
说明： 1、本试卷分为数据结构和离散数学两部分。数据结构部分共六题， 满分100分：离散数学部分共四题满分50分。全试卷共十题， 满分150分。 2、答案一律写在答题纸上。 3、答卷应字迹清楚，语义确切。 数据结构部分 注意事项： 1、算法应说明基本思路，庆对主工数据
说明：
1、本试卷分为数据结构和离散数学两部分。数据结构部分共六题，
满分100分：离散数学部分共四题满分50分。全试卷共十题，
满分150分。
2、答案一律写在答题纸上。
3、答卷应字迹清楚，语义确切。
数据结构部分
注意事项：
1、算法应说明基本思路，庆对主工数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你所熟悉的高级语言编写，但要注明语种。
一、解答下列问题（共30分）
1、[5分]根据数据元素之间关系的不同特性，数据据的逻辑结构通常有哪些基本结构？数据元素之间的关系在计算机中有哪几种表示方式？
第1页
2、[5分]将N*N的上三角矩阵A（i>j时A[i][j]=0,i<=j时A[i][j]>0）的非零元存储在一维数组B（下标k从0开始），试给出B[k]与A[i][j]之间的元素对应关系。
3、[5分]写出后缀表达式ab cde/-f +的运算顺序。
4、[5分]画出广义表（a,(x,y),((x))）的存储结构。
5、[5分]比较哈希表与其它查找表的不同之处。
6、[5分]利用两个栈S1和S2模拟一个队列，写出入队算法和出队算法的算法思想。
二、[10分]已知树T的先序访问序列为：ABEFCDGHIK后序访问序列为：EFBCHIKGDA。
1、画出树T。
2、将树T转换为对应的二叉树BT。
3、将二叉树BT后序线索化。
三、[15分]有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，殷描待排序的表一趟，统计表中有多少个记录的关键码比该记
第2页
录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c（如C=0则当元素存放在新表的0号单元）。
编程实现计数排序算法。
四、[15分]编写一递归属算法，删除单链表中所有值为x的结点。
五、[15分]试写一算法，求二叉树T中任意指定两个结点最近的共同祖先结点。
六、[15分]试写一算法，判断的向图G中任意指定两个结点之间是否存在路径。
第3页
离散数学部分（共50分）
一、（共12分）
1、（6分）设命题A、B、C分别表示下面逻辑式
A：
B：
C：
请用蕴含联结词“ ”指出命题A、B、C之间的逻辑关系。
2、（6分）证明：
二、（12分）证明：若A为元限集，则存在A的真子集 ,使得 ~A。
三、（12分）设（G，·）为一个有限群，且 为偶数，证明存在非单位元 ，使得 ……）。
V2
V4
V5
V7
V1
V6
V8
四、（14分）证明图G=（V，E）中，如果每个回路的长度均为偶数，则G必为一个二部图（二分图）；指出下百给出的图G1是一个二部图，而且它是有8个顶点的二部图中，边数最多的间单平百图。
V3