第一章 概述 真题
16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)
for(j=1；j<=n；j++)
for(k=1；k<=n；k++)
s=i+j+k；
17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。
16.下列程序段的时间复杂度为________。
i=0；s=0；
while（i 17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。 1.数据的不可分割的最小标识单位是（ ） A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i for（j=0；j c［i］［j］=0； for（i=0；i for（j=0；j for（k=0；k c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为（ ） A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n) 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。 1.从逻辑上可以把数据结构分为（ ） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确的是（ ） A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为_____。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、_____和散列存储方式。 1.在数据结构中，数据的基本单位是( ) A.数据项 B.数据元素 C.数据对象 D.数据文件 1 2. k=1; for（i=0；i for（j=0；j A［i］［j］=k++； 上述程序段的时间复杂度为( ) A.O（n2） B.O（n） C.O（2n） D.O（1） 16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。 1.在数据结构中，从逻辑上可以把数据结构分成( ) A.线性结构和非线性结构 B.紧凑结构和非紧凑结构C.动态结构和静态结构 D.内部结构和外部结构 2.for（i=0；i for（j=0；j A［i］［j］=i*j； 上面算法的时间复杂度为( ) A.O(m2) B.O(n2) C.O(m×n) D.O(m+n） 16.如果操作不改变原逻辑结构的―值‖，而只是从中提取某些信息作为运算结果，则称该类运算为_ _型运算。 3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_______。 17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。 1.数据的基本单位是（ ）A.数据项 B.数据类型 C.数据元素 D.数据变量 2.下列程序的时间复杂度为（ ） i=0；s=0； while（s A.O（n） B.O（2n） C.O（n） D.O（n2） 16.在数据结构中，数据的逻辑结构分为集合、_____、树形结构和图状结构等四类。 17.通常从正确性、易读性、_____和高效率等4个方面评价算法（包括程序）的质量。 1.数据结构中所定义的数据元素，是用于表示数据的（ ） A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2.数据的四种基本存储结构是指（ ） A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构 C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构 16.数据表示和________________是程序设计者所要考虑的两项基本任务。 17.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 16.算法通常可分为程序、伪语言算法和__________三种类型。 17.时间复杂性描述量级中，若某算法达到__________量级，则该算法通常是不可计算的。 1.数据的四种基本逻辑结构是指( ) A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性 C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性 16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和_______两种基本 类型。 17.数据结构中的算法，通常采用最坏时间复杂度和______两种方法衡量其效率。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（ ） A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（ ） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 16.从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和___________。 17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为___________算法。 1．下列数据组织形式中，（ ）的各个结点可以任意邻接。 A．集合 B．树形结构 C．线性结构 D．图状结构 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 16．下列程序段的时间复杂性量级是_____________。 for (i=1;i 3 第二章 线性表 第三章 栈、队列、数组 真题 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+I C.i(j-i)／2+1 D.j(i-1)／2+l 18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点___的。 19.在栈结构中，允许插入的一端称为____________。 20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动____________个元素。 21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为____________。 22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是____________。 29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈) 1.在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ ） A.212 B.213 C.214 D.215 4.元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（ ） ．．． A.A，B，C，D，E B.B，C，D，E，A C.E，A，B，C，D D.E，D，C，B，A 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为( ) 2 A.O（1） B.O（log2n） C.O（n） D.O(n) 10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ ） A.单链表 B.双链表 C.顺序表 D.单循环链表 11.在栈中进行插入和删除操作的一端称为（ ） A.栈顶 B.栈底 C.任意位置 D.指定位置 15.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ） A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 4