武汉科技大学856数据结构C语言版都有答案考研真题+答案Word文件下载.docx
《武汉科技大学856数据结构C语言版都有答案考研真题+答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《武汉科技大学856数据结构C语言版都有答案考研真题+答案Word文件下载.docx（48页珍藏版）》请在冰点文库上搜索。
i++）sum+=1;
2.数据结构由数据的逻辑结构、存储结构和数据的（）三部分组成。
3.长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为（）。
4.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。
若为front=8，rear=6，则队列中的元素个数为（）。
5.将有关二叉树的概念推广到三叉树，一颗有244个结点的完全三叉树的深度为（）。
6.设一颗完全二叉树共有101个结点，它有（）叶子结点。
7.出栈操作时应判别栈是否（）。
8.带头结点的单链表Head为空的条件是（）。
9.快速排序的时间复杂度为（）。
10.某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。
三、判断题（10小题，每题2分，共20分）
1.数据元素是数据的最小单位。
2.折半查找方法要求待查表必须是顺序存储结构的有序表。
3.当两个字符出现的频率相同时，则其哈夫曼编码也相同。
4.如果某种排序算法是不稳定的，则该算法是没有实际意义的。
5.将一棵树转换为二叉树后，根结点没有右子树。
6.串既可采用顺序存储，也可采用链式存储。
7.一个广义表的表尾总是一个广义表。
8.完全二叉树的叶子结点只可能在层次最大的一层上出现。
9.顺序存储结构的主要缺点是不利于插入或删除操作。
10.算法是对特点问题求解步骤的一种描述，因此它可以没有输入和输出。
四、综合应用题（6小题，每题10分，共60分）
1.下表列出了某工序之间的优先关系和各工序所需时间。
要求：
（1）画出AOE网
（2）列出各事件的最早开始时间、最迟开始时间
（3）找出关键路径并指明完成该工程所需最短时间。
工序代号
所需时间
前驱工序
a1
6
无
a7
9
a4,a5
a2
4
a8
7
a3
5
a9
a2,a6
a4
1
a10
2
a5
a11
a8,a9
a6
a12
3
2.若一棵完全二叉树中叶子结点的个数为n,且最底层结点数≧2，则此二叉树的深度H=？
3.已知一颗二叉树的中序序列为BJFKDGAELIMHC，后序序列为JKFGDBLMIHECA，画出该二叉树的先序线索二叉树。
4.在n×
n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij（1≤i,j≤n）的值均为0，现将A中其它元素按行优先顺序依次存储到长一维数组sa中，其中元素a1，n存储在sa［0］。
（1）设n=10，元素a4，9存储在sa［p］，写出下标p的值；
（2）设元素ai，j存储在sa［k］中，写出由i,j和n计算k的一般公式。
5.假定对有序表（1,9,15,21,24,35,52,54,61,65,97）进行折半查找，试回答问题：
（1）画出描述折半查找过程的判定树；
（2）分别求等概率情况下查找成功和不成功时的平均查找长度。
6.已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题：
（1）写出堆排序的初始堆（大根堆）关键字序列；
写出堆排序1趟以后（交换与调整之后）的关键字序列；
（2）写出快速排序1趟以后的关键字序列；
写出快速排序2趟以后的关键字序列。
（3）写出冒泡排序1趟以后的关键字序列；
五、算法设计与编程（3小题，每题10分，共30分）
1.函数digit（n,k）的功能是求正整数n中从右端开始的第k（≥1）个数字的值（k从1开始），如果k超过了n的位数，则函数返回－1；
否则返回n中第k个数字。
例如：
digit（264539,3）=5
digit（7622,5）=-1
要求分别用递归和非递归设计该函数。
2.设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：
（要求用最少的时间和最小的空间）
⑴确定在序列中比正整数x大的数有几个（相同的数只计算一次）。
⑵在单链表中将比正整数x小的数按递减次序排列。
⑶将比x大的偶数从单链表中删除。
3.在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。
二O一四年招收硕士研究生入学考试试题
1.算法分析的主要内容是（）。
A）正确性B）可读性和稳定性C）简单性D）空间复杂性和时间复杂性
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A）必须是连续的B）部分地址必须是连续的
C）一定是不连续的D）连续或不连续都可以
3.设有6个元素按1、2、3、4、5、6的顺序进栈，下列不合法的出栈序列是（）。
A）234165B）324651C）431256D）546321
4.设有二维数组A[1..12,1..10]，其每个元素占4个字节，数据按行优先顺序存储，第一个元素的存储地址为100，那么元素A[5,5]的存储地址为（）。
A）76B）176C）276D）376
5.已知一棵二叉树的先序序列为ABDGCFK，中序序列为DGBAFCK，则后序序列为（）。
A）ACFKDBGB）GDBFKCAC）KCFAGDBD）ABCDFKG
6.在二叉树结点的先序，中序和后序序列中，所有叶子结点的先后顺序（）。
A）都不相同 B）完全相同
C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同
7.图的深度优先遍历类似于二叉树的（）。
A）先序遍历B）中序遍历C）后序遍历D）层次遍历
8.下面（）算法适合构造一个稠密图G的最小生成树。
A）Prim算法B）Kruskal算法C）Floyd算法D）Dijkstra算法
9.对关键码{46,79,56,38,40,84}采用堆排序,则初始化堆（小堆）后最后一个元素是（）。
A）84B）46C）56D）38
10.在Hash函数H（k）=kMODm中，一般来讲m应取（）。
A）奇数B）偶数C）素数D）充分大的数
1.在单向链表某P结点之后插入S结点的操作是（）。
2.线性表Ｌ用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。
3.一个栈的输入序列是：
1，2，3则不可能的栈输出序列是（）。
4.一棵二叉树高度为h,所有结点的度或为0，或为2，则该二叉树最少有（）结点。
5.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是（）。
6.若无向图G=（V,E），其中V={a,b,c,d,e}E={（a,b）,（a,d）,（a,c）,（d,c）,（b,e）}，现采用图的（）遍历方法从顶点a开始遍历图，得到的序列为abecd。
7.求最短路径的Dijkstra算法的时间复杂度为（）。
8.假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（）次探测。
9.设在已排序的线性表中共有元素n个，若用二分法查找表中的元素。
若查找成功，至少要比较（）次
10.对一组记录（54,38,96,23,15,2,60,45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。
三、综合应用题（7小题，每题10分，共70分）
1.已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？
2.请给出一棵哈夫曼树中分支数B与叶子节点数n0所满足关系式，并证明你的结论。
3.下面的排序算法的思想是：
第一趟比较将最小的元素放在r[0]中，最大的元素放在r[n-1]中，第二趟比较将次小的放在r[1]中，将次大的放在r[n-2]中，…,依次下去，直到待排序列为递增序。
（注：
<
-->
代表两个变量的数据交换）。
voidsort（SqList&
r,intn）
{i=0;
while（
（1））
{min=max=i;
for（j=i+1;
（2）;
++j）
{if（（3））min=j;
elseif（r[j].key>
r[max].key）max=j;
}
if（（4））r[min]<
r[i];
if（max!
=n-i-1）
{if（（5））r[min]<
r[n-i-1];
elser[max]<
i++;
}
}//sort
4.如下图所示的AOE网
（1）写出所有的拓扑序列
（2）求各顶点代表的事件的最早发生时间和最迟发生时间
（3）求各条弧代表的活动的最早开始时间和最迟开始时间
（4）给出其关键路径
5.设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，10），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
（1）线性探测法
（2）链地址法
6.全国有10000人参加竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。
而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？
为什么？
7.假定对有序表（3,4,5,17,24,35,40,54,58,72,80,123）进行折半查找，试回答问题：
（2）若查找元素54，需依次与那些元素比较?
（3）若查找元素20，需依次与那些元素比较?
（4）分别求等概率情况下查找成功和不成功时的平均查找长度。
四、算法设计与编程（4小题，每题10分，共40分）
1.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。
在链表被启用前，其值均初始化为零。
每当在链表中进行一次Locate（L,x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。
试编写符合上述要求的Locate（L,x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
2.已知二叉树用下面的顺序存储结构，写出先序遍历该二叉树的算法。
8
data
A
B
C
D
E
F
G
H
I
Lc
Rc
3.编写在后序线索二叉树中求任一结点直接前驱的算法（结点结构包括数据域data、左孩子域left、右孩子域right、左标志域ltag和右标志域rtag，标志域为0表示没有孩子，孩子域为线索）。
4.有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。
双向冒泡排序即相邻两趟排序向相反方向冒泡）。
参考答案（A）
1.B2.C3.B4.D5.B6.B7.C8.A9.A10.D
1.O（n）2.运算或操作3.33/11=34.985.6
6.517.空8.Head->
next==NULL9.O（nlogn）
10.空或一个结点或单分支
1.×
2.√3.×
4.×
5.√6.√7.√8.×
9.√10.×
1.
事件
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
最早发生时间
14
16
18
21
最迟发生时间
10
19
关键路径：
a1->
a4->
a8->
a11->
完成该工程所需最短时间：
2.
设具有n个结点的完全二叉树的深度为H
由完全二叉树的定义可知：
第i（1≤i≤H－1）层上的结点数将达到最大（2i-1）,第H层上的结点数将≥2且≤2k-1
∴1＋2＋……＋2H-2＋2≤n≤1＋2＋……＋2H-2＋2H-1
2H-1+1≤n≤2H-12H-1<
n<
2H
H-1<
log2n<
∴H=[log2n]
3.
4.
（1）p=8
（2）k=i*（i-1）/2+i+j-n-1
5.
查找成功时的平均查找长度:
（1*1+2*2+3*4+4*4）/11=3
查找不成功时的平均查找长度:
（4*3+8*4）/12=44/12=3.33
6.
堆排序的初始堆（大根堆）关键字序列:
96637825571144
堆排序1趟以后的关键字序列:
78634425571196
快速排序1趟以后的关键字序列:
11259663577844
快速排序2趟以后的关键字序列:
11254463577896
冒泡排序1趟以后的关键字序列:
25116357784496
1.
intdigit（intn,intk）
{if（n==0）return-1;
elseif（k==1）returnn%10;
elsereturndigit（n/10,k-1）;
{while（n）
{if（k==1）returnn%10;
k--;
n=n/10;
return-1;
voidcompare（intx,Node*L）
{
intcount=0,comp=0,status=0;
Node*p,*t,*pre,*end,*work=NULL;
p=L->
next;
pre=L;
end=L;
while（p）
{
if（p->
data<
x）status=1;
if（comp!
=p->
data&
&
status==0）{count++;
comp=p->
data;
if（status==0）
if（p==L&
p->
data%2==0）{t=p;
L->
next=p->
free（t）;
elseif（p!
=L&
data%2==0）{t=p;
pre->
p=pre->
else{pre=p;
p=p->
end=pre;
if（status==1）
{t=pre->
next=work;
work=p;
p=t;
end->
3．
typedefstruct
BiTreet;
inttag;
//tag=0表示左子女被访问，tag=1表示右子女被访问
}stack;
voidSearch（BiTreebt,ElemTypex）
{
stacks[];
top=0;
while（bt!
=null||top>
0）
{
while（bt!
=null&
bt->
data!
=x）
{s[++top].t=bt;
s[top].tag=0;
bt=bt->
lchild;
}
if（bt->
data==x）
{
printf（“所查结点的所有祖先结点的值为:
\n”）;
for（i=1;
i<
=top;
i++）printf（s[i].t->
data）;
return;
while（top!
=0&
s[top].tag==1）top--;
if（top!
=0）{s[top].tag=1;
bt=s[top].t->
rchild;
}
}
intQiuzu（Node*Head）
if（Head==null）return0;
if（Head->
data==x）return1；
if（Qiuzu（Head->
Lchild）||Qiuzu（Head->
Rchild））
cout<
Head->
date<
endl;
return1;
elsereturn0;
1.D2.D3.C4.C5.B6.B7.A8.A9.A10.C
1.s->
p->
next=s;
2.（n-1）/23.3124.2h-15.[log2i]=[log2j]
6.深度7.O（n2）8.k（k+1）/29.[log2i]+110.2
根据完全二叉树的性质，A[i]的双亲是A[i/2]，双亲的双亲是A[i/2/2]，...
同理，A[j]的双亲是A[j/2]，双亲的双亲是A[j/2/2]，...
if（i==j）A[i]和A[j]的最近的共同祖先就是A[i/2];
else
while（i!
=j）{if（i>
j）i=i/2;
elsej=j/2;
A[i]和A[j]的最近的共同祖先就是A[i];
设总结点数为n，度为1和2的结点数分别为n1和n2
n=B+1=n0+n1+n2n1=0n2=n0-1
B=2n0-2
（1）i<
n-1-i
（2）j<
=n-1-i（3）r[j].key<
r[min].key
（4）i!
=min（5）max==i
（1）1562738415627834156723841567283415678234
（2）
最早发生时间Ve
30
50
65
17
25
35
最迟发生时间Vl
15
27
44
59
（3）
活动
1-2>
1-5>
1-4>
2-3>
3-4>
5-2>
5-6>
最早开始时间e
最迟开始时间l
20
6-2>
6-3>
6-7>
7-3>
7-4>
7-8>
8-4>
34
36
62
49
（4）给出其
升级会员 