排序的算法其执行时间与待排序记录的初始状态有关。为此有时会对算法有最好、最坏以及平均时间复杂度的评价。
6以下数据结构中是非线性数据结构
A树
B字符串
C队列
D栈
答案A
6试分析下面各程序段的时间复杂度。
1x90y100
whiley0
ifx100
xx10y
elsex
答案O1
解释程序的执行次数为常数阶。
f2fori0i
i
forj0jmj
aij0
答案Om
解释语句aij0的执行次数为m
。
3s0
fori0i
i
forj0j
j
sBij
sums
答案O
2
解释语句sBij的执行次数为
2。
4i1
whilei
ii3
答案Olog3
解释语句ii3的执行次数为log3
。
5x0
fori1i
i
forj1j
ij
x
答案O
2
解释语句x的执行次数为
1
2……1
12。
6x
1
y0
whilex≥y1y1
y
答案O
解释语句y的执行次数为
。
f第2章线性表
1选择题
1顺序表中第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是。
A110
B108
C100
D120
答案B
解释顺序表中的数据连续存储所以第5个元素的地址为10024108。
2在
个结点的顺序表中算法的时间复杂度是O1的操作是。
A访问第i个结点1≤i≤
和求第i个结点的直接前驱2≤i≤
B在第i个结点后插入一个新结点1≤i≤
C删除第i个结点1≤i≤
D将
个结点从小到大排序
答案A
解释在顺序表中插入一个结点的时间复杂度都是O
2排序的时间复杂度为O
2或O
log2
。顺序表是一种随机存取结构访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位时间复杂度是O1。
3向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动的元素个数为。
A8
B635
C63
D7
答案B
解释平均要移动的元素个数为
2。
4链接存储的存储结构所占存储空间。
A分两部分一部分存放结点值另一部分存放表示结点间关系的指针
B只有一部分存放结点值
C只有一部分存储表示结点间关系的指针
D分两部分一部分存放结点值另一部分存放结点所占单元数
答案A
5线性表若采用链式存储结构时要求内存中可用存储单元的地址。
A必须是连续的
B部分地址必须是连续的
C一定是不连续的
D连续或不连续都可以
答案D
6线性表L在情况下适用于使用链式结构实现。
A需经常修改L中的结点值
B需不断对L进行删除插入
CL中含有大量的结点
DL中结点结构复杂
答案B
f解释链表最大的优点在于插入和删除时不需要移动数据直接修改指针即可。
7单链表的存储密度。
A大于1
B等于1
C小于1
D不能确定
答案C
解释存储密度是指一个结点数据本身所r