文档介绍：一、判断题
1算法可以没有输入语句。
2数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类，线性的数据结构指数据元素只有一个前驱，非线性的则有多个前驱。
3数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。
二、选择题
1算法的时间复杂度取决于
.问题的规模 (B).待处理数据的初态
.编码的语言 (D).占用内存的大小
2算法与程序的主要区别在于程序可以不满足算法的
.确定性 (B).有穷性
o
(A).空间复杂性和时间复杂性
(C).可读性和文档性
.可行性 (D).健壮性
.正确性和简明性
.数据复杂性和程序复杂性
三、填空题
1若算法中语句频度之和为T(〃) = 3720〃 + 4zzlog2 n ,则算法的时间复杂度为—。
2数据的存储结构分为—、、和四种。
3在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和的关系。
4算法的计算工作量大小和实现算法所需的存储单元多少，分别称为计算的
和»
四、应用题
1计算带下划线语句的执行次数，n为已知的正整数。
x = 91,y = n;
while ( y > 0 )
{ if(x> 100) ( x = xT0; y—; }
else x ++;
}
j=0, k = 0;
while (k < n) { j ++; k+= 10*j; }
2 一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。
1, n - 1
7(〃)= \
2T(〃/2) + 〃，〃 > 1
其中：n是问题的规模，为简单起见，可设n是2的整数幕。
一、判断题
1线性关系的逻辑结构与存储结构总是一致的。
2每种数据结构都包括插入、删除和查找这二种基本运算。
3线性表中的每个结点最多只有一个前驱和一个后继。
4线性的数据结构既可以顺序存储，也可以链接存储；非线性的数据结构则只能链接存储。
5顺序存储方式只能用于存储线性结构。
6多维数组是向量的推广。
7设串s的长度为n,则s的子串个数最多为n (n+l)/2。
8单链表从任何一个结点出发，都能访问到所有结点。
9线性表的长度是线性表所占用的存储空间的大小。
10双循环链表中，任意一结点的后继指针均指向其逻辑后继。
11数据结构、数据元素、数据项在计算机中的映象(或表示)分别称为存储结构、结点、数据域。
12线性表的顺序存储结构优于链式存储结构。
二、选择题
1若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为，元素的移动次数为( 0< i <n)=
(A). 0(0) (B). 0(1) (C). O(n) (D). O(n2)
. n-i+1 (F). n-i (G). i (H). i 1
2在长度为n的顺序存储的线性表中，删除第i个元素(0<i<n-l)时，需要从前向后依次前移个元素。
(A), n-i (B). n-i+1 (C). n-i-1 (D). i
3从解决问题的需要出发，为实现必要的功能所建立的数据结构，称为 o
(A).物理结构 (B).逻辑结构 (C).数据类型 (D).数据对象
4若长度为n的线性表采用顺序存储结构，在其第i(0<i <n )个位置插入一个新元素的平均移动元素移动次数为,在其第i(0WiWn-l )个位置删除一个元素的平均移动元素移动次数为。
(A), n (B). (n+l)/2 (C). n/2 (D). (n-l)/2
5若长度为n的无序线性表采用顺序存储结构，在其中查找某个元素时，所需要的平均比较的次数为 O
(A), n (B). (n-l)/2 (C). n/2 (D). (n+l)/2
6对于只在首、尾两端进行插入操作的线性表，宜采用的存储结构为 o
(A).顺序表 (B).带头指针的单链表
.带尾指针的单循环链表 (D).单链表
7在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 O
(A). q->link = p->link； p->link = q； (B). p->link = q->link； q = p；
(C). q->link = p->link； p = q； (D). p->link = q->link； q->link = p；
8在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 o
(A). HL = p; p->next = HL; (B). p->link = HL; HL = p;
(C)・ p->link = HL; p = HL;