.
C．线性结构和非线性结构 D．内部结构和外部结构 答案：C
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。
A．存储结构 B．存储实现 C．逻辑结构 D．运算实现 答案：C
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等 答案：B
（4）以下说法正确的是（ ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构 答案：D
解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构
的各数据元素的集合。
（5）算法的时间复杂度取决于（ ）。 A．问题的规模 答案：D
解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些
排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
（6）以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队列 D．栈 答案：A
6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100;
while(y>0)
if(x>100) {x=x-10;y--;}
else x++; 答案：O(1)
解释：程序的执行次数为常数阶。
B．待处理数据的初态 D．A和B
C．计算机的配置
精品
.
（2）for (i=0; i for (j=0; j 答案：O(m*n) 解释：语句a[i][j]=0;的执行次数为m*n。 （3）s=0; for i=0; i for(j=0; j s+=B[i][j]; sum=s; 2 答案：O(n) 解释：语句s+=B[i][j];的执行次数为n。 （4）i=1; while(i<=n) i=i*3; 答案：O(log3n) 解释：语句i=i*3;的执行次数为 （5）x=0; for(i=1; i 答案：O(n) 解释：语句x++;的执行次数为n-1+n-2+……＋1= n(n-1)/2。 （6）x=n; //n>1 y=0; while(x≥(y+1)* (y+1)) y++; 答案：O(n) 解释：语句y++;的执行次数为 n 2 log3n。 。 精品 . 第2章 线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入or delete一个结点的时间复杂度都是O(n)，排序的时间复杂 2 度为O(n)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直 接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（ ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 答案：D （6）线性表Ｌ在（ ）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂 答案：B 精品 . 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。 （7）单链表的存储密度（ ）。 A．大于1 B．等于1 C．小于1 D．不能确定 答案：C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。 （8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B．2n-1 C．2n D．n-1 答案：A 解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需 要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。 （9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．I 答案：B (10) 线性表L=(a1，a2,……an)，下列说法正确的是（ ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后 继。 答案：D (11) 创建一个包括n个结点的有序单链表的时间复杂度是（ ）。 A．O(1) B．O(n) C．O(n) D．O(nlog2n) 2 答案：C 解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成 一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。 (12) 以下说法错误的是（ ）。 时实现的效率低 B．顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构 A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构 答案：D 解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。 (13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。 精品