没有合适的资源?快使用搜索试试~ 我知道了~
计算机软件技术基础 复习题
需积分: 9 4 下载量 8 浏览量
2010-04-27
21:12:18
上传
评论 1
收藏 237KB DOC 举报
温馨提示
试读
37页
适用于考研复习《计算机软件技术基础》试题
资源详情
资源评论
资源推荐
《计算机软件技术基础》试题
线性表的链式存储结构与顺序存储结构相比优点是 。
所有的操作算法实现简单 便于随机存取
便于插入和删除 便于利用零散的存储器空间
线性表是具有 个 的有限序列。
表元素 字符 数据元素
数据项 信息项
若长度为 的线性表采用顺序存储结构,在其第 个位置插入一个新元素的算法的时间
复杂度为 。( )
设 是一个线性表
,采用顺序存储结构,则在等概率的前提下,平均每插
入一个元素需要移动的元素个数为 ,平均每删除一个元素需要移动的元素个数为
;若元素插在
与
之间的概率为 ,则平均每插入一个元
素所要移动的元素个数为 ;
下列函数中,按它们在 时的无穷大阶数,最大的是 。
n n
将下图所示的 所指结点加到 ! 所指的结点之后,其语句应为: 。
"#$%&!'!"#$%& '
(!#$%& '( #$%&(!#$%'
"#$%&!"#$%'!"#$%& "#$%'
"#$%&!"#$%'!"#$%& '
)将两个各有 个元素的有序表归并为一个有序表时,其最少的比较次数是 。
*下面的程序段是合并两个无头结点链表+ 和 +,为一个无头结点链表 + 的过程,作为
参数的两个链表都是按结点的 -% 域由大到小链接的。合并后新链表的结点仍按此方式
链接。请填写下述空框,使程序能正确运行。
!
#$%
#$% #$%
.-#/#0122
%3!#-#4 %567%-#8
%-%'
%567%-#(#$%'
9-#: %%3!#'
;-7<,#: %%3!#(+: %%3!#(+,8
: %%3!#(+(!'
+&: %%3!#(<7 =#4: %%3!#'
+"#$%&0122'
!&+'
>+#+&0122??+,&0122
4+"-%"&+,"-%8 (较大的元素先插入(
!"#$%&'
!&'
'
9
# #8
!"#$%&'
!&'
'
9
4+&&0122)'
4+,&&0122*'
+&+"#$%'
45##+'
9
参考答案: + !"#$% +&+"#$%
+, !"#$% +,&+,"#$%
)!"#$%&+, *!"#$%&+
@如果表 中所有元素
与表 的一个顺序子表,
:
,
:
,
:
完全相同(即
&,
:
&,
:
&,
:
),则称表 包含在表 中。设 +,+, 为带头结点的单链
表,分别表示有序表 和 ,下面的函数用于判别表 是否包含在表 中,若是,则返回
%56#,否则返回 4 #。(提示:用递归实现)
.-#/#%56#
.-#/#4 #
.-#/#0122
%3!#-#4 %567%-#8
%-%'
%567%-#(#$%'
9-#: %%3!#'
%76 : %%3!#(+: %%3!#(+,8
: %%3!#(!(!,'
!&+"#$%'
!,&+,"#$%'
'
>+#
4!"-%&!,"-% '
# # '
'
9
参考答案:
4!&&01225#%65%56#
!,&0122??!"-%"&!,"-%
5#%6576 !!,
!,&!,"#$%'
5#%654 #
在本题的程序中,函数 75#%#A:A %建立一个具有 个结点的循环链表;函数
B #!+6 <对由 75#%#A:A %所建立的具有 个结点的循环链表按一定的次
序逐个输出,并删除链表中的所有结点。参数 "指明循环链表的结点个数,参数
指明起始结点,参数 <(<" 是步长),指明从起始结点或前次被删除并输出
的结点之后的第 < 个结点作为本次被输出并删除的结点。例如,对于下图所示的具有 个
结点的循环链表,在调用 B #!+6 后,将输出 。请在空框处填上适
当内容,每框只填一个语句。
.-#/#0122
%3!#-#4 %567%-#8
%-%'
%567%-#(#$%'
9-#: %%3!#'
: %%3!#(75#%#A:A %%8
: %%3!#(+#-(!(C'
%'
+#-&0122'
4"8
+#-&: %%3!#(<7 =#4: %%3!#'
!&+#-'
45&'D&'8 (此循环用于建立一个链表,链表的内容从 至 (
!"-%&'
C&: %%3!#(<7 =#4: %%%3!#'
'
'
9
!"-%&'
' (建立从尾链到首的环形结构(
9
5#%65+#-'
9
;-E #!+6 %%B%<8
: %%3!#(!(C'
%B'
!&75#%#A:A %'
45'"' !&!"#$%'
'
>+#BD8
45&'D&<' !&!"#$%'
'
!5%4FG*-HC"-%'
'
45##C'
B&B'
9
9
参考答案:
!"#$%&C'
!&C'
!"#$%&+#-
B&
C&!"#$%'
!"#$%&C"#$%
在下列程序中,函数 -I#5#7#用于求两集合之差 &,即当且仅当 # 是
中的一个元素,且不是 中的元素时,# 是 中的一个元素。集合用有序链表实现,用一
个空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列,执行 &
之后,表示集合 和 的链表不变,若结果集合 非空,则表示它的链表应根据元素之值
按递增序排列。函数 !!#-用于在链表中添加结点。
.76-#D %-+"
.-#/#0122
%3!#-#4 %567%-#8
%-%'
%567%-#(#$%'
90'
0(!!#-0( %%$8
%"#$%&0(<7 =#40'
%"#$%"-%&$'
5#%65 %"#$%'
9
0(-I#5#7#0(0(8
0(( %'
& %&0(<7 =#40'
>+#
4"-%D"-%8
%&!!#- %"-%'
&"#$%'
9
# #
48
&"#$%'
&"#$%'
9
# #
'
>+#8
%&!!#- %"-%'
&"#$%'
9
'
%&'
&"#$%'
45## %'
5#%65'
9
参考答案:
&0122?&0122
"-%&&"-%
&"#$%'
&0122
%"#$%&0122'
阅读以下算法,填充空格,使其成为完整的算法。其功能是在一个非递减的顺序存储
线性表中从下标 处开始存储,删除所有值相等的多余元素。
.-#/#JKLM
%3!#-#4 %567%8
%##<NJKLMO'
%#%+'(表长(
9 C %%3!#'
;-#$< C %%3!#(28
%B'
&B&'
>+#8
42"##<NO&2"##<NBO
剩余36页未读,继续阅读
yan_ming
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0