数据结构试题及答案.doc
版权申诉
125 浏览量
2022-05-04
21:46:50
上传
评论
收藏 359KB DOC 举报
设有一组初始记录关键字序列
（
，
，…，
），要求设计一
个算法能够在 的时间复杂度内
将线性表划分成两部分，其中左半
部分的每个关键字均小于
，右半
部分的每个关键字均大于等于
。
!"#
!"#$$%&'
#()
!"#$$#('#
&)
)
)
设有两个集合 * 和集合 +，要求
设计生成集合 ,*-+ 的算法，其
中集合 *、+ 和 , 用链式存储结构
表示。
.""'"
"/")!!
""!!/ !!
/ 0!!/$
!!///
' 121&%"
' 021&%"'
&%&%0"
'21!!
/3!!4"'!!&%&
%&%" )
)
)
三、算法设计题
设计在单链表中删除值相同的多余
结点的算法。
.""'."
.""'"."
"/")!!
"!"!!/$ "
!!///
' "21&%"
'&%"21
'&%&%&%"&
%"'""&%")
"!"&%")
)
)
设计在链式存储结构上交换二叉树中所
有结点左右子树的算法。
.""'"
"/! !/ !)0""
0""0""/0
0""/
'01"
0""0&%! !
0""0&% !
0&%! ! 0&%! !0&
% !0&% !
)
设计一个求结点 在二叉树中的双
亲结点算法。
.""'"."
"/! !/ !)0""
0""/11'1'!51
""0""/0
'021$$'!51
' 0&% '!5
")
"!" (6 1 0
""0&%! ! ""0&
% !)
)
"0""/0
""0
''( # (( ' &
%! !&% 77 &% !&%
0"
' '!51'8 ' 9
8
"!" ' # '8680&
%"!"'8"8
)
设单链表中有仅三类字符的数据元
素大写字母、数字和其它字符，
要求利用原单链表中结点空间设计
出三个单链表的算法，使每个单链
表只包含同类字符。
.""' ."
.""'"."
"/")!!
!!! / "!!
/$ !!/$ 0!!/$
!!/ 1 01 1
' "21 "
"&%"&%"1
' &%%:*: $$ &
%#:;:&%" )
"!" ' &%%:1: $$ &
%#:<:&%" 0 0)"!"&
%" )
)
)
在链式存储结构上建立一棵二叉排
序树。
="'"1
.""' " ".
"/! !/ !)0""
0"0""/$0".
' 0100""
/3!!4"'0"" 0&%".".0&
%! !0&% !1)
"!"'0&%".%".0"0&
%! !". "!" 0"0&
% !".
)
""0""0""/$0
'#((
0"0311
)
设计判断两个二叉树是否相同的算
法。
.""'"."
"/! !/ !)0""
5"0""0"" /00""
/0
'01$$01"
"!"'017701770&%2
0&%"1
"!" "5"0""0&
%! !0&%! !/5"0""0&
% !0&% !
)
设计两个有序单链表的合并排序算
法。
3"5"!!!! / !!
/ 0!!/$
!!/ 1
!" 21$$ 021
' &%# 0&%'1
"!"&%" ) &
%")
"!"'1 0"!"&
%" 0 0) 0 0&%")
' 1 &%" 0 "!" &
%"
)
设计在顺序有序表中实现二分查找
的算法。
"". ")
0" "
!13 5 &
!"!# 5
3!( 5 >
'3"."3(
"!" '3".% 5 3& "!"
!3(
)"1
)
设计判断二叉树是否为二叉排序树
的算法。
33&?@AB'!5
.""'""."
/! !/ !)0""
"0""/0
' 021 "0&%! !
'33%0&%".'!51 330&
%"."0&% !)
)
? 在链式存储结构上设计直接插入排
序算法
5 "!!
/$ "
!!///
' "1 77 "&%"1
"
"!" ' " "&%"21&
%"' "2&%"&%"
'&%%&%0"
'&%"
"!"&%"&%" &
%"&%" &%" &%&
%&%&%)
)
)
设计在链式结构上实现简单选择排
序算法。
3!""!"!!!!
/$ "
1
资源评论
