北京理工大学数据结构编程练习标准答案Word下载.docx
- 文档编号:3664018
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:127
- 大小:105.12KB
北京理工大学数据结构编程练习标准答案Word下载.docx
《北京理工大学数据结构编程练习标准答案Word下载.docx》由会员分享,可在线阅读,更多相关《北京理工大学数据结构编程练习标准答案Word下载.docx(127页珍藏版)》请在冰点文库上搜索。
pnext。
while(p!
=NULL)
{
if(p->
a!
=0)
f=1。
cout<
<
"
p->
a<
"
b<
>
。
pnext==NULL)
else
}
if(f==0)
}
voidadd(PDATEa,PDATEb,PDATEc)
PDATEp1,p2,p3。
p1=a。
p2=b。
p3=c。
if(p1!
=NULL)p1=p1->
//skiphead
if(p2!
=NULL)p2=p2->
while((p1!
=NULL)&
&
(p2!
=NULL))
if(p1->
b>
p2->
b)
p3->
pnext=(PDATE)malloc(sizeof(DATE))。
p3=p3->
a=p2->
a。
b=p2->
b。
pnext=NULL。
p2=p2->
elseif(p1->
a=p1->
b=p1->
p1=p1->
a+p2->
}//endwhile
if(p1==NULL)
pnext=p2。
if(p2==NULL)
pnext=p1。
intmain()
intflag。
intn。
PDATEP[6]={NULL}。
PDATEp=NULL。
for(inti=0。
i<
6。
i++)
P[i]=(PDATE)malloc(sizeof(DATE))。
P[i]->
a=0。
b=0。
cin>
flag。
if(flag==1)
for(inti=1。
4。
p=P[i]。
n。
while(n--!
p->
a>
output(P[i])。
add(P[1],P[2],P[4])。
output(P[4])。
add(P[4],P[3],P[5])。
output(P[5])。
0约瑟夫问题(10分)
0约瑟夫问题
成绩10分
折扣0.8
(本题要求用循环链表实现)
0,1,2,3题,只能选做三题.
约瑟夫问题是一个经典的问题。
已知n个人(不妨分别以编号1,2,3,…,n代表)围坐在一张圆桌周围,从编号为k的人开始,从1开始顺时针报数1,2,3,...,顺时针数到m的那个人,出列并输出。
然后从出列的下一个人开始,从1开始继续顺时针报数,数到m的那个人,出列并输出,…依此重复下去,直到圆桌周围的人全部出列。
n,k,m
按照出列的顺序依次输出出列人的编号,编号中间相隔一个空格,每10个编号为一行。
非法输入的对应输出如下
a)
:
n、k、m任一个小于1输出:
n,m,kmustbiggerthan0.
b)
k>
n
kshouldnotbiggerthann.
例
输入
9,3,2
输出
468137295
stdio.h>
math.h>
structdate*next。
PDATEsetnew(PDATEp,inta)
PDATEpt。
pt=(PDATE)malloc(sizeof(DATE))。
pt->
a=a。
next=p->
next。
next=pt。
returnpt。
intcount。
PDATEdel(PDATEp0)
if(!
count)
printf("
\n"
)。
count=10。
%d"
p0->
a)。
PDATEp=p0->
p0->
a=p->
free(p)。
count--。
returnp0。
intn=0,k=0,m=0。
scanf("
%d,%d,%d"
&
n,&
m,&
k)。
(n>
0&
m>
0))
n,m,kmustbiggerthan0.\n"
elseif(m>
n)
kshouldnotbiggerthann.\n"
PDATEhead=(DATE*)malloc(sizeof(DATE))。
head->
next=head。
a=1。
p=head。
for(inti=2。
=n。
p=setnew(p,i)。
while(p->
=m)
while(n)
//inttemp=k。
inttemp=k%n+n。
while(--temp)
del(p)。
n--。
2.综教楼后的那个坑
描述
在LIT综教楼后有一个深坑,关于这个坑的来历,有很多种不同的说法。
其中一种说法是,在很多年以前,这个坑就已经在那里了。
这种说法也被大多数人认可,这是因为该坑有一种特别的结构,想要人工建造是有相当困难的。
从横截面图来看,坑底成阶梯状,由从左至右的1..N个的平面构成(其中1≤N≤100,000),如图:
* *:
* *8
* ** *7
* ** *6
* ** *5
* *********4<
-高度
* *********3
**************2
**************1
平面 | 1 |2| 3 |
每个平面i可以用两个数字来描述,即它的宽度Wi和高度Hi,其中1≤Wi≤1,000、1≤Hi≤1,000,000,而这个坑最特别的地方在于坑底每个平面的高度都是不同的。
每到夏天,雨水会把坑填满,而在其它的季节,则需要通过人工灌水的方式把坑填满。
灌水点设在坑底位置最低的那个平面,每分钟灌水量为一个单位(即高度和宽度均为1)。
随着水位的增长,水自然会向其它平面扩散,当水将某平面覆盖且水高达到一个单位时,就认为该平面被水覆盖了。
请你计算每个平面被水覆盖的时间。
灌水
水满后自动扩散
|
*|
*
*
*V
V
*
....
*~~~~~~~~~~~~*
**
*~~~~**:
*~~~~**~~~~~~*
*~~~~**~~~~~~*
*********
*~~~~*********
*~~~~*********
**************
**************
4分钟后
26分钟后 50分钟后
平面1被水覆盖 平面3被水覆盖 平面2被水覆盖输入
输入的第一行是一个整数N,表示平面的数量。
从第二行开始的N行上分别有两个整数,分别表示平面的宽度和高度。
输出每个平面被水覆盖的时间。
longlong*timedate。
longh。
intw。
structdate*pl。
structdate*pr。
PDATEsetnew(PDATEp0,intw,longh,longlong*num)//p0为左邻
PDATEp=(PDATE)malloc(sizeof(DATE))。
timedate=num。
pl=p0。
pr=NULL。
pr=p。
h=h。
w=w。
returnp。
voidoutput(longlong*p,longn)
while(n--)
%lld\n"
*(++p))。
longlongmyclock。
longn。
PDATEp=NULL,pt=NULL。
//setleftp
PDATEleft=(PDATE)malloc(sizeof(DATE))。
left->
timedate=NULL。
pl=NULL。
h=1000000。
w=0。
p=left。
pt=left。
%d"
n)。
longlong*timedate=newlonglong[n+1]。
for(longi=0。
//cin>
w>
h。
%d%d"
w,&
h)。
p=setnew(p,w,h,timedate+i+1)。
if(pt->
h>
h)
pt=p。
PDATEright=setnew(p,0,1000000,NULL)。
p=pt。
myclock=0。
pl->
h!
=p->
pr->
*(p->
timedate)=myclock+p->
w。
//计算时间并删除合并
{
myclock+=(p->
h-p->
h)*p->
w+=p->
pr=p->
pr。
pl=p->
pl。
deletept。
elseif(p->
h<
//移至下一进水点
h&
continue。
h)//左移
else//右移
myclock+=p->
timedate)=myclock。
output(timedate,n)。
3.单词压缩存储(10分)
如果采用单链表保存单词,可采用如下办法压缩存储空间。
如果两个单词的后缀相同,则可以用同一个存储空间保存相同的后缀。
例如,原来分别采用单链表保存的单词Str1“abcdef”和单词Str2“dbdef”,经过压缩后的存储形式如下。
请设计一个高效的算法完成两个单链表的压缩存储,并估计你所设计算法的时间复杂度。
要求:
阅读预设代码,编写函数SNODE*ziplist(SNODE*head1,SNODE*head2)
ziplist的功能是:
在两个串链表中,查找公共后缀,若有公共后缀,则压缩并返回指向公共后缀的指针;
否则返回NULL
预设代码
前置代码
viewplaincopytoclipboardprint?
1./*
PRESET
CODE
BEGIN
-
NEVER
TOUCH
BELOW
*/
2.
3.#include
4.#include
5.
6.typedef
struct
sdata
7.{
char
data。
8.
sdata
*next。
9.}
SNODE。
10.
11.void
setlink(
SNODE
*,
*
),
outlink(
12.int
listlen(
13.SNODE
ziplist(
14.SNODE
findlist(
15.
16.int
main(
)
17.{
18.
head1,
head2,
*head。
19.
str1[100],
str2[100]。
20.
21.
gets(
str1
22.
str2
23.
24.
head1
=
(SNODE
*)
malloc(
sizeof(SNODE)
25.
head2
26.
head
27.
head->
next
head1->
head2->
NULL。
28.
29.
30.
str2)。
31.
32.
33.
34.
35.
36.
return
0。
37.}
38.
39.void
*head,
*str
40.{
41.
*p
42.
43.
while
(
!
'
\0'
44.
{
p
)
sizeof(
45.
data
*str。
46.
47.
str++。
48.
p。
49.
50.
}
51.
return。
52.}
53.
54.void
55.{
56.
NULL
57.
{
58.
printf(
%c"
->
59.
60.
61.
printf("
62.
63.}
64.
65.int
66.{
67.
int
len=0。
68.
69.
70.
len
++。
71.
72.
73.
len。
74.}
75.
76.SNODE
77.{
78.
m,
79.
*p1=head1,
*p2=head2。
80.
81.
m
82.
n
83.
84.
85.
p1
p1->
86.
m--。
87.
88.
89.
p2
90.
n--。
91.
92.
93.
while(
94.
95.
96.
97.
98.
99.}
100.
101./*
Here
is
waiting
for
you!
102./*
103.
zipli
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京理工大学 数据结构 编程 练习 标准答案