习题答案解析
一、单项选择题
- 下列对顺序存储的有序表（长度为 n）实现给定操作的算法中，平均时间复杂度为 O(1)的是（）
• 答案：D
• 解析：顺序存储的有序表（如数组）中，获取第 i 个元素可以直接通过索引访问，不需要遍历或计算，所以时间复杂度是 O(1)。其他选项：查找需要遍历或二分查找（平均不是 O(1)）；插入和删除需要移动元素，平均时间复杂度是 O(n)。
- 下列程序段的时间复杂度是（）
int sum=0;
for(int i=1; i<n; i*=2)
for(int j=0; j<i; j++)
sum++;
• 答案：B. O(n)
• 解析：外层循环中，i 每次乘以 2（1, 2, 4, 8, ...），循环次数约为 log₂n。内层循环次数与 i 的值相等，所以总循环次数是 1 + 2 + 4 + ... + 2log₂n ≈ 2n，因此时间复杂度是 O(n)。
- 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（）
x=0;
while(n>=(x+1)*(x+1))
x=x+1;
• 答案：B. O(n¹/²)
• 解析：循环条件是 (x+1)² ≤ n，所以 x 从 0 开始增加，直到 x+1 > √n。循环次数约为 √n，因此时间复杂度是 O(√n)，即 O(n¹/²)。
- 下列函数的时间复杂度是（）
int func(int n){
int i=0, sum=0;
while(sum<n)
sum+=++i;
return i;
}
• 答案：B. O(n¹/²)
• 解析：sum 是累加 i 的值（1+2+3+...+k），当 sum ≥ n 时停止。k(k+1)/2 ≈ n，所以 k ≈ √(2n)，时间复杂度是 O(√n)，即 O(n¹/²)。
- 下列程序段的时间复杂度是（）
count=0;
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
count++;
• 答案：C. O(n log₂n)
• 解析：外层循环 k 每次乘以 2，循环次数为 log₂n。内层循环 j 从 1 到 n，循环 n 次。总时间复杂度是 O(n log n)。
- 已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）
• 答案：D. O(max(m,n))
• 解析：合并两个有序链表需要比较每个元素，最坏情况比较次数为 m+n，因此时间复杂度是 O(m+n)，即 O(max(m,n))。
- 求整数 n（n≥0）阶乘的算法如下，其时间复杂度是（）
int fact(int n){
if(n<=1)
return 1;
return n*fact(n-1);
}
• 答案：O(n)
• 解析：递归调用 n 次，每次操作是 O(1)，所以总时间复杂度是 O(n)。（注：原题选项缺失，但根据算法分析，答案为 O(n)。）
- 设 n 是描述问题规模的非负整数。下面程序片段的时间复杂度是（）
x=2;
while(x<n/2)
x=2*x;
• 答案：A. O(log₂n)
• 解析：x 从 2 开始，每次乘以 2，直到 x ≥ n/2。循环次数约为 log₂(n/2) = log₂n - 1，因此时间复杂度是 O(log n)。
- 下列说法正确的是（）
• 答案：D. 一个算法时间复杂度与空间复杂度无直接关系
• 解析：时间复杂度和空间复杂度是算法的两个独立指标，没有直接关联。一个算法可能时间高效但空间占用大，反之亦然。
- 下列时间复杂度中最坏的是（）
• 答案：D. O(n²)
• 解析：时间复杂度从小到大为：O(1) < O(log n) < O(n) < O(n²)。O(n²) 增长最快，最坏。
- 分析下面的程序，算法的时间复杂度为（）
for(k=1; k<n; k++)
for(j=1; j<n; j++)
x=x+1;
• 答案：C. O(n²)
• 解析：两层循环都从 1 到 n，循环次数为 n × n = n²，因此时间复杂度是 O(n²)。
- 下列 T(n) 表示各算法中最耗时操作的执行次数，n 表示数据量，请按照时间复杂度从小到大排列，正确的是（）
• T1(n)=100n+200log₂n
• T2(n)=3n²
• T3(n)=10000000
• T4(n)=300log₂n
• 答案：C. T3<T4<T1<T2
• 解析：T3 是常数 O(1)，T4 是对数 O(log n)，T1 是线性 O(n)，T2 是平方 O(n²)。所以从小到大为 T3 < T4 < T1 < T2。
- 若一个算法的时间复杂度用 T(n) 表示，其中 n 的含义是（）
• 答案：A. 问题规模
• 解析：n 通常表示输入数据的大小或问题规模，如元素个数。
- 计算机算法指的是（）
• 答案：C. 解决某一问题的有限运算序列
• 解析：算法是解决特定问题的有限步骤序列，具有明确性、有穷性等特点。
- 现有非空双向链表 L，其节点结构为 [prev, data, next]。若要在 L 中指针 p 所指向的节点（非尾节点）之后插入指针 s 指向的新节点，则在执行了语句序列“s->next=p->next; p->next=s;”后，下列语句序列中还需要执行的是（）
• 答案：B. p->next->prev=s; s->prev=p;
• 解析：在双向链表中插入节点后，需要更新前后节点的指针。已执行的操作将 s 插入到 p 之后，但还需设置 s 的前驱指针（s->prev=p）和原后继节点的前驱指针（p->next->prev=s）。
- 已知头指针 h 指向一个带头节点的非空单循环链表，节点结构为 [data, next]，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（）
• 答案：D. q=h->next; h->next=q->next; if(p==q) p=h; free(q);
• 解析：删除第一个元素（即头节点的后继节点）时，需调整头节点的指针。如果被删除的节点是尾节点（p==q），则尾指针 p 需指向头节点 h，以保持循环链表结构。
- 设某数据结构的二元组形式表示为 A=(D,R)，D={01,02,03,04,05,06,07,08,09}，R={r}，r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}，则数据结构 A 是（）
• 答案：B. 树形结构
• 解析：从关系 r 看，01 是根节点，指向 02、03、04；02 指向 05、06；03 指向 07、08、09。这是一棵树，每个节点有多个子节点，但整体是树形结构。
- 线性表的顺序存储结构中，数据元素的逻辑位置和物理位置的关系是（）
• 答案：B. 一致的
• 解析：顺序存储中，逻辑上相邻的元素在物理内存中也相邻，因此逻辑位置和物理位置一致。
- 表长为 n 的顺序存储的线性表，当在任何位置删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（）
• 答案：A. (n-1)/2
• 解析：删除第 i 个元素需要移动 n-i-1 个元素。概率相等时，平均移动次数为 (0+1+2+...+(n-1))/n = (n-1)/2。
- 在单链表指针为 p 的节点之后插入指针为 s 的节点，正确的操作是（）
• 答案：B. s->next=p->next; p->next=s;
• 解析：先让 s 的指针指向 p 的后继节点（s->next=p->next），再让 p 的指针指向 s（p->next=s），避免断链。
- 以下数据结构中哪一个是非线性结构？（）
• 答案：D. 二叉树
• 解析：队列、栈、线性表都是线性结构（元素一对一关系），而二叉树是非线性结构（元素一对多关系）。
- 用单链表形式的链式存储结构的线性表来存储元素时，以下描述中错误的是（）
• 答案：C. 逻辑上相邻的元素在物理位置上也相邻
• 解析：链式存储中，逻辑上相邻的元素在物理位置上不一定相邻，通过指针链接。其他选项正确：添加和删除不需要移动元素，无法随机访问。
- 若线性表最常用的操作是存取第 i 个元素及其前驱和后继元素的值，为了提高效率，应采用的存储方式是（）
• 答案：D. 顺序表
• 解析：顺序表（数组）支持随机存取，可以直接访问第 i 个元素及其前后元素，时间复杂度 O(1)。链表需要遍历。
- 设线性表有 n 个元素，以下算法中，（）在顺序表上实现比在链表上实现效率更高
• 答案：C. 输出第 i（0≤i≤n-1）个元素值
• 解析：顺序表直接通过索引访问第 i 个元素，时间复杂度 O(1)；链表需要遍历，时间复杂度 O(n)。其他选项：A 和 B 在两者上效率相近，D 都需要遍历。
- 下列关于线性表的描述，错误的是（）
• 答案：A. 顺序表不能进行插入操作
• 解析：顺序表可以进行插入操作，但需要移动元素。A 错误；其他选项正确：顺序表适宜随机存取，链表适宜顺序存取。
- 下列关于数据的逻辑结构的叙述中，不正确的是（）
• 答案：D. 数据的逻辑结构不仅反映数据间的逻辑关系，而且包含其在计算机中的存储方式
• 解析：逻辑结构只描述数据间的关系，不涉及存储方式；存储方式属于物理结构。
- 关于数据结构的描述，正确的是（）
• 答案：B. 一种逻辑结构可采用多种存储结构实现
• 解析：例如，线性表可以用顺序存储或链式存储实现。A 错误（逻辑结构分为线性、树形、图等）；C 错误（一种存储结构可实现多种逻辑结构）；D 错误（一对多关系用树形结构）。
- 链表不具有的特点是（）
• 答案：B. 可随机访问任一元素
• 解析：链表必须从头遍历访问元素，不支持随机访问。其他选项是链表的优点：插入删除方便、空间动态分配。
- 已知表头元素为 c 的单链表在内存中的存储状态如下表所示（表未提供），现将 f 存放于 1014H 处并插入到单链表中，若 f 在逻辑上位于 a 和 e 之间，则 a、e、f 的“链接地址”依次是（）
• 答案：D. 1014H, 1004H, 1010H（注：由于原表缺失，此答案基于常见链表插入操作推断。一般地，插入 f between a 和 e 时，a 的指针指向 f，f 的指针指向 e，e 的指针不变。）
• 解析：插入新节点 f 后，a 的 next 指向 f（地址 1014H），f 的 next 指向 e（地址 1004H），e 的 next 不变。但根据选项，可能地址顺序有特定排列，正确答案为 D。
- 已知一个带有表头节点的双向循环链表 L，节点结构为 [prev, data, next]。现要删除指针 p 所指的节点，正确的语句序列是（）
• 答案：D. p->next->prev=p->prev; p->prev->next=p->next; free(p);
• 解析：删除 p 节点时，需让 p 的前驱节点指向 p 的后继节点，p 的后继节点指向 p 的前驱节点，然后释放 p。
- 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间
• 答案：D. 仅有尾指针的单向循环链表
• 解析：仅有尾指针时，尾插入 O(1)（直接访问尾节点），删除第一个元素 O(1)（尾节点的 next 指向头节点，即第一个元素）。
- 下述哪一条是链式存储结构的优点？（）
• 答案：B. 插入、删除运算方便
• 解析：链式存储中，插入和删除只需修改指针，不需要移动元素。其他选项是顺序存储的优点。
- 具有 n 个元素的线性表采用顺序存储结构，在其第 i（1≤i≤n+1）个位置插入一个新元素的算法时间复杂度为（）
• 答案：O(n)
• 解析：插入操作平均需要移动 n/2 个元素，时间复杂度为 O(n)。（注：原题选项缺失，但根据分析答案为 O(n)。）
- 线性表采用顺序存储结构时，其元素地址（）
• 答案：A. 必须是连续的
• 解析：顺序存储要求元素在内存中连续存放。
- 关于顺序表和链接表的描述，错误的是（）
• 答案：C. 分别在具有 n 个数据元素的顺序表和链接表中查找数据元素 K，链接表的查找效率要高于顺序表
• 解析：顺序表和链表在无序情况下查找效率都是 O(n)，但顺序表缓存友好，实际可能更快；且顺序表支持二分查找（如果有序）。C 错误；其他选项正确。
- 在一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
• 答案：B. 63.5
• 解析：平均移动次数为 n/2 = 127/2 = 63.5。
- 在单链表中，存储每个节点有两个域，一个是数据域，另一个是指针域，指针域指向该节点的（）
• 答案：B. 直接后继
• 解析：单链表的指针域指向下一个节点（直接后继）。
- 在已知头指针的单链表中，要在其尾部插入一新节点，其算法的时间复杂度为（）
• 答案：D. O(n)
• 解析：需要遍历整个链表找到尾节点，时间复杂度 O(n)。
- 指针 p1 和 p2 分别指向两个无头节点的非空单循环链表中的尾节点，要将两个链表链接成一个新的单循环链表，应执行的操作为（）
• 答案：D. p=p1->next; p1->next=p2->next; p2->next=p;
• 解析：p1 是链表 1 的尾节点，p1->next 是链表 1 的头节点；p2 是链表 2 的尾节点，p2->next 是链表 2 的头节点。操作后，p1 指向链表 2 的头节点，p2 指向链表 1 的头节点，形成新循环链表。
- 每个节点有多个后继节点的数据结构有（）
• 答案：C. 图
• 解析：图中一个节点可以有多个后继（邻接节点）。线性表、队列、栈每个节点只有一个后继。
二、填空题
- 程序 for(int i=0;i<n;i+=5) 的时间复杂度为 ______
• 答案：O(n)
• 解析：循环次数为 n/5，因此时间复杂度是 O(n)。
- 数据的逻辑结构是对数据之间关系的描述，主要有 ______ 和 ______ 两大类。
• 答案：线性结构、非线性结构
• 解析：逻辑结构分为线性结构（元素一对一）和非线性结构（如树、图）。
- 在单链表（长度为 n）给定值 x 的节点后插入新节点的时间复杂度为 ______
• 答案：O(n)
• 解析：需要遍历链表找到值为 x 的节点（平均 O(n)），然后插入操作 O(1)，总时间复杂度 O(n)。
三、简答题
- 算法的五个特性是什么？
• 答案：
有穷性：算法必须在有限步骤内结束。
确定性：每一步操作必须有明确含义，无二义性。
可行性：算法中的操作可以通过基本运算实现。
输入：算法有零个或多个输入。
输出：算法有一个或多个输出。
• 解析：算法是解决问题的方法，必须满足这五个特性才能保证有效执行。
简述线性结构中数据元素间关系的特点，并列举常用的线性结构（3 种以上）。
• 答案：
• 特点：数据元素之间存在一对一的线性关系，每个元素最多有一个直接前驱和一个直接后继。
• 常用线性结构：线性表、栈、队列、数组、链表等。
• 解析：线性结构元素排列成线性序列，常见例子包括线性表（基本结构）、栈（后进先出）、队列（先进先出）。
