武汉科技大学856数据结构C语言版都有答案考研真题+答案Word文件下载.docx
- 文档编号:408188
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:48
- 大小:265.86KB
武汉科技大学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.线性表L用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是()。
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)给出其
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 武汉 科技大学 856 数据结构 语言版 答案 考研