最新解放军理工大学指挥自动化学院考研专业课离散数学与数据结构Word文档下载推荐.docx
《最新解放军理工大学指挥自动化学院考研专业课离散数学与数据结构Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《最新解放军理工大学指挥自动化学院考研专业课离散数学与数据结构Word文档下载推荐.docx（7页珍藏版）》请在冰点文库上搜索。
A
（2）分）给出<
B,R>
存在最大元的必要条件和此时最大元的解（7
析表达式。
四、（15分）
（1）分）证明：
顶点数大于2的树中，其最长路径的两个端点（7都是叶。
（2）分）用归纳法证明：
对任意有n个顶点，m条边，p个连（8通分支的无向简单图G，恒有：
n?
p≤m
（注意：
用其他方法证明满分为6分）五、（10分）设〈G，*〉是群，g∈G。
映射h：
G→G定义如下：
h（x）=g?
x?
g?
1
h：
G→G是同构映射。
2
数据结构部分六、（15分）下图是一个散列表A[17]。
用开放地址法解决冲突。
冲突时，使用增量序列di=6i。
表中标“#”的单元表示已有元素占用。
现在表中依次插入五个元素：
a，b，c，d，e；
已知它们的散列函数值依次等于：
5，3，8，11，9。
请将a，b，c，d，e填写在散列表中（直接填在下表中）。
A0123#45#6789#1011#12131415#16
七、（每小题5分，共15分）1、已知检索树的先序序列是“18，16，8，29，21，27，38”。
那么，它的后序序列是。
2、试画出由权14，7，8，2，5，4，23所构造的哈夫曼树，并求出该哈夫曼树的加权路径长度WPL（要求列出计算步骤）。
3、设数组a[MAX]用于存储两个栈S1和S2，这两个栈的栈底分别固定在数组的两端，使它们迎面增长。
试写出与下面进栈函数push相配套的退栈函数。
进栈函数：
intpush（inta[],int&
top1,int&
top2,intx,inti）//top1和top2分别是栈S1和S2的栈顶指针，其初值为，top1=-1，top2=MAX//i是栈号，i=1表示对栈S1操作；
i=2表示对栈S2操作
3
//x是准备进栈的元素//返回0：
表示栈满，进栈失败；
返回1：
表示进栈成功{if（top1+1==top2）return0;
if（i==1）a[++top1]=x;
elsea[--top2]=x;
return1;
}
退栈函数的函数头形如：
intpop（inta[],int&
top1,int&
top2,int&
x,inti）//返回0：
表示栈空，退栈失败；
表示退栈成功
八、（15分）算法填空题（注意：
编号相同的空内，填写相同内容）。
函数inition通过输入无向图的边序列，构造邻接表（供先深搜索用）。
#defineM50//定义最大顶点数typedefstructedge_node//边结点类型{intadjacent;
structedge_node*next;
}edge,*Eptr;
typedefstruct//表头结点类型{intmark;
Eptrfirstedge;
//邻接表首指针}hnode;
hnodeL[M];
//邻接表intn;
//定义顶点数构造邻接表的函数如下：
voidinition（）{intv,w;
Eptrp;
for（v=0;
v<
n;
v++）L[v].firstedge=
（1）;
printf（"
请输入边序列。
若顶点v的编号小于0，则表示输入结束\n"
）;
scanf（"
%d%d"
&
v,&
w）;
4
while（v>
=0）{p=（Eptr）malloc（sizeof（edge））;
p->
adjacent=w;
（2）=L[v].firstedge;
L[v].firstedge=（3）;
p=（Eptr）malloc（sizeof（edge））;
adjacent=（4）;
（2）=L[w].firstedge;
L[w].firstedge=（3）;
（5）;
}}
九、（15分）算法填空题（注意：
函数qksort实现非递归的快速排序算法。
其中，stele是栈结点类型名（定义如下）。
主调语句为：
qksort（a,n）。
typedefstruct{intleft,right;
}stele;
//定义栈结点类型//left和right分别是划分段的左右下标
voidqksort（inta[],intn）//a[]是待排序数组，n是参加排序的元素个数{ints,t,k,top=0;
stelestack[M];
//M是存储栈的长度stack[top].left=0;
//栈底存放一个假划分段stack[top++].right=0;
（1）=0;
（2）=n-1;
while（s<
t）{partition（a,s,t,k）;
if（
（1）<
k-1&
&
k+1<
（2））{stack[top].left=k+1;
（3）=t;
t=（4）;
}elseif（s<
k-1）__
（2）__=k-1;
5
elseif（k+1<
t）__
（1）__=k+1;
else{s=（5）;
t=stack[top].right;
}}}voidpartition（inta[],ints,intt,int&
k）{inti,j,x;
x=a[s];
i=s;
j=t;
while（i<
j）{while（（a[j]>
=x）&
（i<
j））j--;
if（i<
j）a[i++]=a[j];
while（（a[i]<
x）&
j））i++;
j）a[j--]=a[i];
}a[i]=x;
k=i;
十、（15分）算法设计题二叉树的“先序右链”存储结构属于一种顺序存储，用数组t[n]存储其先序序列，其中，t[i].data存储结点的值；
t[i].Rson存储其右儿子的下标（下标-1，表示没有右儿子）。
例如，下图所示的二叉树及其存储形式。
ABDEG
6
rootCF数组t0dataARson21B-12C-1345F-16G-1DE5-1
试写出“先序右链”存储结构下，递归的（二叉树）中序遍历函数，其中访问语句用“printf（"
%4d"
t[i].data）;
”表示。
主调语句形如：
inord（0,n-1）；
7
《离散数学与数据结构》参考答案离散数学与数据结构》参考答案离散数学部分参考答案离散数学部分参考答案参考
一、（15分）
（1）分）将下列语句用谓词公式形式化（用N（x）表示“x是自然数”（5，用G（x,y）表示“x大于y”：
）没有自然数大于所有的自然数，但每个自然数都有大于它的自然数。
解：
?
x（N（x）∧?
y（N（y）∧y≠x→G（x,y）））∧?
x（N（x）→?
y（N（y）∧G（y,x）））
（2）分）写出上述语句否定的表达式，将否定词深入到括号里面。
（4解：
y（N（y）∧y≠x→G（x,y）））∨?
y（N（y）∧G（y,x）））?
y（?
N（y）∨?
G（y,x）））（3）分）证明下列逻辑蕴涵式（证明方式不限）（6?
xQ（x）证：
x（?
P（x）→Q（x））?
x?
P（x）→?
xQ（x）?
xP（x）→?
xQ（x）二、（20分）设R，S，T都是集合A上的二元关系，IA是集合A上的相等关系，°
是关系间的合成运算，R表示关系R的补。
证明：
R=R（6证：
<
x,y>
∈IA°
R?
u（<
x,u>
∈IA∧∈R）?
x,x>
∈IA∧<
∈R?
<
∈R故IA°
R=R。
（2）分）若R?
SoT（6证：
∈RoT，设那么有u使得<
x,u>
∈R,∈T。
由于R?
S，故<
∈S，进而<
∈SoT。
RoT?
SoT得证。
8
证：
首先由于R自反，IA?
R，因此，R=IAoR?
RoR。
现证RoR?
R。
为此设<
x,y>
∈RoR，于是有u使得<
∈R,∈R。
进而由于R对称，∈R。
现反设<
R，那么<
∈R，由R的传递性，∈R,这与∈R矛盾。
故<
∈R。
RoR?
R得证。
命题证毕。
三、（15分）设A,B是集合，且A≠?
B≠?
，<
B,≤>
是有序集（又称偏序集，≤是B上的序关系）。
现定义BA上的二元关系R（注意：
B=f
{
f:
A→B}）
R是BA上的序关系。
（8证：
由于?
x（f（x）≤f（x）），故fRf，R自反得证。
设fRg，f，gR那么?
x（f（x）≤g（x）），x（g（x）≤h（x）），?
于是?
x（f（x）=g（x）），即f=g。
R反对称得证。
设fRg，gRh，那么?
x（f（x）≤g（x）），x（g（x）≤f（x）），?
x（f（x）≤h（x）），即fRh。
R的传递性得证。
（2）分）给出<
BA,R>
存在最大元的必要条件和此时最大元的解析表达式。
（7解：
存在最大元的必要条件是<
存在最大元，记为u。
此时<
的最大元f的解析表达式是f（x）=u。
顶点数大于2的树中，其最长路径的两个端点都是叶。
（7证：
反证之。
设最长路径的两个端点中有一个端点v不是叶。
则v的度数大于或等于2。
设它的另一个相邻结点为u。
若u在最长路径上，则构成回路，与树的定义矛盾；
u不若在最长路径上，则有一条比原路径更长的路径，与原路径是最长路径矛盾。
9
（2）分）（8用归纳法证明：
对任意有n个顶点，条边，个连通分支的无向简单图G，mp恒有：
用其他方法证明满分为6分）证：
对p归纳。
p=1时，G为树，确有n?
p=n?
1≤m。
设G有p+1个连通分支，须证n?
（p+1）≤m。
用一边连接其两个连通分支，得到图G1，G1有p个连通分支，n个顶点，m+1条边。
据归纳假设，G1满足
n?
p≤m+1
即n?
这正是我们要证明的。
五、（10分）设〈G，*〉是群，g∈G。
先证h：
G→G是单射和满射。
设h（x）=h（y）,则g*x*g-1=g*y*g-1。
由于G是群，据可约性，x=y。
h的单射性证得。
设y是G中任一元素，那么h（g-1*y*g）=g*（g-1*y*g）*g-1=y。
h的满射性证得。
又h（x*y）=g*（x*y）*g-1=g*（x*g-1*g*y）*g-1=（g*x*g-1）*（g*y*g-1）=h（x）*h（y）故h：
数据结构部分参考答案数据结构部分参考答案参考
六、（15分）每个数3分A0123a#
4b
5#
6d
8c
9#
10e
11#
12
13
14
15#
16
七、（每小题5分，共15分）1、答：
8，16，27，21，38，29，182、答：
所构造的哈夫曼树如下图。
10
63251114526478153823
（2）WPL=（2+4）*4+（5+7+8）*3+（14+23）*2=158注：
另一种简单的计算WPL的方法是，将所有内结点的权值相加：
WPL=63+25+38+11+15+6=1583、intpop（inta[],int&
top2,int&
x,inti）//返回0：
表示退栈成功{if（i==1）if（top1==-1）return0;
else{x=a[top1--];
return1;
}elseif（top2==MAX）return0;
else{x=a[top2++];
}}八、（15分）每个编号相同的空得3分。
答：
（1）NULL
（2）p->
next（3）p（4）v（5）scanf（"
w）九、（15分）每个编号相同的空得3分。
（1）s
（2）t（3）stack[top++].right（4）k-1（5）stack[--top].left十、（15分）算法设计题答：
voidinord（inti,intj）{if（i>
j）return;
if（t[i].Rson>
=0）inord（i+1,t[i].Rson-1）;
elseinord（i+1,j）;
=0）inord（t[i].Rson,j）;
11
升级会员 