for(j=1;j<=n-i;j++)
x++;
~0022
因为x++共执行了n-1+n-2+……+1=n(n-1)/2,所以执行时间为O(n2)
`002301A2
分析下面各程序段的时间复杂度:
i=1;
while(i<=n)
i=i*3;
~0023
O(log3n)
`002401E2
设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?
D={d1,d2,…,d9}
R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}
~0024
此图为图形结构d1,d2—无直接前驱,是开始结点d6,d7—无直接后继是终端结点
`002502B1
在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。
~0025
表中一半表长和该元素在表中的位置
`002603C1
判定一个栈ST(最多元素为m0)为空的条件是
A、ST->top<>0B、ST->top=0C、ST->top<>m0D、ST->top=m0
~0026
B
`002702B2
向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动个元素。
~0027
n-i+1
`002802B2
向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动个元素。
~0028
n-i
`002902B1
在顺序表中访问任意一结点的时间复杂度均为,因此,顺序表也称为的数据结构。
~0029
O
(1)随机存取
`003002B1
顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置相邻。
~0030
必定不一定
`003102B1
在单链表中,除了首元结点外,任一结点的存储位置由指示。
~0031
其直接前驱结点的链域的值
`003202B2
在n个结点的单链表中要删除已知结点*p,需找到它的,其时间复杂度为。
~0032
前驱结点的地址O(n)
`003302D1
链表的每个结点中都恰好包含一个指针。
()
~0033
X
`003402D1
链表的物理存储结构具有同链表一样的顺序。
()
~0034
X
`003502D1
链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。
()
~0035
X
`003602D1
线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
()
~0036
X
`003702D1
顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
()
~0037
X
`003802D1
顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
()
~0038
X
`003902D1
线性表在物理存储空间中也一定是连续的。
()
~0039
X
`004002D1
线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。
()
~0040
X
`004102D1
顺序存储方式只能用于存储线性结构。
()
~0041
X
`004202D1
线性表的逻辑顺序与存储顺序总是一致的。
()
~0042
X
`004302C1
数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为()
A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构
~0043
C
`004402C1
一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()
A、110B、108C、100D、120
~0044
B
`004502C1
在n个结点的顺序表中,算法的时间复杂度是O
(1)的操作是()
A、访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
B、在第i个结点后插入一个新结点(1≤i≤n)
C、删除第i个结点(1≤i≤n)
D、将n个结点从小到大排序
~0045
A
`004602C2
个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素
A、8B、63.5C、63D、7
~0046
B
`004702C2
链接存储的存储结构所占存储空间()
A、分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
B、只有一部分,存放结点值
C、只有一部分,存储表示结点间关系的指针
D、分两部分,一部分存放结点值,另一部分存放结点所占单元数
~0047
A
`004802C1
链表是一种采用()存储结构存储的线性表;
A、顺序B、链式C、星式D、网状
~0048
B
`004902C1
线性表若采用链式存储结构时,要求内存中可用存储单元的地址()
A、必须是连续的B、部分地址必须是连续的
C、一定是不连续的D、连续或不连续都可以
~0049
D
`005002C1
线性表L在()情况下适用于使用链式结构实现。
A、需经常修改L中的结点值B、需不断对L进行删除插入
C、L中含有大量的结点D、L中结点结构复杂
~0050
B
`005110B1
若索引文件采用稠密索引,则每个索引项与主文件中的______记录相对应,若索引文件采用稀疏索引,则每个索引项与主文件中的_______记录相对应.
~0051
一个一组(成若干条)
`005208E2
已知一堆数组A中的数据如下,试写出在快速排序的过程中每次划分后数据的排序情况.
12345678
┌─┬─┬─┬─┬─┬─┬─┬─┐
│45│28│64│53│15│36│74│30│
└─┴─┴─┴─┴─┴─┴─┴─┘
(1)
(2)
(3)
~0052
[30283615]45[537464]
[1528]30364553[7464]
1528303645536474
`005308C1
下列排序算法中,第一趟排序完毕后,其最大或最小元素不一定在其最终位置上的算法是()
A、归并排序B、直接选择排序C、树形选择排序D、冒泡排序
~0053
A
`005408C1
直接插入排序的时间复杂度为().
A、O(n)B、0(log2n)C、0(nlog2n)D、0(n2)
~0054
d
`005510B1
文件的检索和修改有两种方式______和______
~0055
实时的批量的
`005610C2
对顺序文件的检索方法可以是()
A、顺序存取B、随机存取C、按关键字存取D、前三种方法都可以
~0056
D
`005710B1
在查找索引文件时,首先要查找_______;然后再查找________
~0057
索引表主文件
`005808E3
利用堆排序的方法给已知数组A中的数据排序,写出在构成初始堆和利用堆排序的过程中,每次筛运算后数据的排列情况:
12345678
┌─┬─┬─┬─┬─┬─┬─┬─┐
A│45│28│49│16│37│82│56│75│
└─┴─┴─┴─┴─┴─┴─┴─┘
1.构成初始堆的过程
(1)
(2)
(3)
(4)
2.利用堆排序的过程
(1)
(2)
(3)
(4)
(5)
(6)
(7)
~0058
1.
(1)4528497537825616
(2)4528827537495616
(3)4575822837495616
(4)8275562837494516
2.
(1)7537562816494582
(2)5637492816457582
(3)4937452816567582
(4)4537162849567582
(5)3728164549567582
(6)2816374549567582
(7)1628374549567582
`005908E2
判断以下序列是否为堆,若不是,调整为堆
a.{12,15,23,35,28,87,49,86}
b.{35,12,28,87,49,86,15,23}
~0059
a为堆b不是堆
b相应的完全二叉树:
(35)(35)(35)(12)(12)
(12)(28)→(12)(28)→(12)(15)→(35)(15)→(23)(15)
(87)(49)(86)(15)(23)(49)(86)(15)(23)(49)(86)(28)(23)(49)(86)(28)(35)(49)(86)(28)
(23)(87)(87)(87)(87)
b调整为堆排序列之后为{12,23,15,35,49,86,28,87}
`006010C1
堆排序的最坏时间复杂度为()
A、0(n)B、0(log2n)C、0(nlog2n)D、0(n2)
~0060
c
`006110B2
设数组longintb[4][6]的首地址为s,按行主序方式存贮时元素b[2][4],b[3][4]的存贮地址分别为________
~0061
s+64s+88
`006210E3
设文件有12个记录,其关键字值分别为37,23,7,79,9,43,3,19,31,61,23',47,按非递减的次序进行排序试分别给出用下列方法排序时第一,二趟处理后的结果序列
1.冒泡排序2.选择排序3.快速排序
~0062
1.第一趟23,7,37,9,43,3,19,31,61,23',47,79
第二趟7,23,9,37,3,19,31,43,23,47,61,79
2.第一趟37,23,7,47,9,43,3,19,31,61,23',79
第二趟37,23,7,47,9,43,3,19,31,23',61,79
3.第一趟[23',23,7,31,9,3]37[43,61,79,47]
第二趟[3,23,7,19,9]23'[31]37,43,[61,79,47]
`006310B1
文件按记录的结构可分为两类______和______,按记录中关键字的多少可分为______和________
~0063
定长记录文件不定长记录文件单关键字文件多关键字文件
`006410B2
外部分类包括______和________
~0064
磁带文件的归并分类磁盘文件的归并分类
`006508B2
设一组关键字为{23,3,39,9,7,5,16,8},进行线性插入分类,试写出第一遍分类后关键字的排列次序________
~0065
[23]339975168
第一遍[323]39975168
第二遍[32339]975168
第三遍[3923397]5168
第四遍[3792339]5168
第五遍[35792339]168
第六遍[3579162339]8
第七遍[35789162339]
`006608B2
内部分类包括(任写六种)___________________________________
~0066
冒泡分类简单选择分类线性插入分类折半插入分类
希尔分类快速分类堆分类归并分类基数分类
`006710B1
磁带主要由______,______,______组成.
~0067
磁带介质读写磁头磁带驱动器
`006808B1
分类的目的是____________________________
~0068
便于查询和处理数据
`006908B2
你所学过的排序的方法中,哪些是稳定的____________
~0069
直接插入二分(折半)插入冒泡归并排序枚举
`007008C2
下列排序算法中,排序花费的时间不受数据开始排列特性影响的算法是()
A、直接插入排序B、冒泡排序C、直接选择排序D、快速排序
~0070
c
`007108C2
下列排序算法中,最好情况下时间复杂度为0(n)的算法是()
A、选择排序B、归并排序C、快速排序D、冒泡排序
~0071
d
`007208E3
利用堆排序的方法给已知数据A中的数据排序,写出在构成初始堆和利用堆排序的过程中每次筛运算后数据的排列情况(要求构造大根堆)
12345678
┌─┬─┬─┬─┬─┬─┬─┬─┐
A│45│28│49│16│37│82│56│75│
└─┴─┴─┴─┴─┴─┴─┴─┘
~0072
1:
4528497537825616
2:
4528827537495616
3:
4575822837495616
4:
8275452837495616
5:
7537452816495682
6:
5637452816497582
7:
4937452816567582
8:
4537162849567582
9:
3728164549567582
10:
2816374549567582
11:
1628374549567582
`007310B1
根据排序文件所处的位置不同,可将排序分为______和______两大类.
~0073
内部外部
`007408D1
堆排序是不稳定排序()
~0074
正确
`007510D1
文件中存取数据的基本单位是数据项()
~0075
错误
`007608E2
设文件有10个记录其关键字值分别为:
37,23,7,79,29,43,73,19,31,61,试给出用冒泡排序法,按非递减的次序进行排序过程中的每一趟结果序列.
~0076
3723779294373193161
第一趟23737294373193161|79
第二趟723293743193161|73
三7232937193143|61
四72329193137|43
五723192931|37
六7192329|31
`007708D2
堆排序与快速排序相比,堆比快速省时间()
~0077
错误
`007810D2
影响外排序的时间因素主要是内存与外设交换信息的总次数()
~0078
正确
`007910B1
ISAM文件由____,______,____和______组成.
~0079
主索引柱面索引磁道索引和主文件
`008010B1
顺序文件是指按记录进入文件的先后顺序存放,其________顺序和________顺序一致的文件.
~0080
逻辑物理
`008110B1
文件的存储结构是指文件在______上的组织形式
~0081
外存
`008210B1
常用的文件组织方式有______,________,______和______.
~0082
顺序文件.索引文件.散列文件.多关键字文件
`008310B1
文件是性质相同的______的集合.
~0083
记录
`008410B1
文件中存取的基本单位是________文件中可使用的最小单位是________
~0084
记录数据项
`008510B1
文件结构包括______,______以及在_______的各种操作
~0085
逻辑.物理.文件
`008610B1
文件上的基本操作主要有两类______和______
~0086
索引.维护
`008710B1
索引表中的每一项称为索引项,一段索引项都是由____和_____所在记录的物理地址组成的
~0087
主关键字.该关键字
`008810B1
在排序过程中,若整个文件被在内存中处理,排序时不涉及数据的内外存交换,则称之为______.
~0088
内排序
`008910B1
在排序过程中,若整个文件不完全在内存中处理,排序时涉及数据的内,外存交换,则称之为_______
~0089
外排序
`009010B1
直接插入排序的时间复杂度是_______.
~0090
0(n2)
`009108B1
快速排序的平均时间复杂度是________.
~0091
0(nlog2n)
`009208E2
对于给定的一组关键字:
38,64,52,13,47,85写出快速排序的各趟运行结果
~0092
初始关键字:
[38,64,52,13,47,85]
第一趟[13]38[64,52,47,85]
二1338[5247]64[85]
三1338[47]526485
最后结果133847526485
`009308B2
所谓归并是指将若干个__________的子文件合并成一个有序的文件.
~0093
已排序
`00940