銆婃暟鎹�缁撴瀯涓庣畻娉曘�?娓呭崕)鍏稿瀷渚嬮�� - 鐧惧害鏂囧簱

学习必备 欢迎下载

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

①A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法 ②A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性

解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。

[例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i

for(j=0；j

x=x+l：

A．O(2n) B．O(n) C．O(n2) D．O(1bn)

解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。本题 中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次， 显然此语句的执行次数为n×n＝n2次。由此可知，本题答案为：C。 二、填空题

[例6-5] 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。

解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数 据项；数据项。 三、应用题

[例6-6] 简述数据结构的定义。

解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包 括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上 定义的运算。用集合的观点可以把数据结构表示为一个二元组DS＝(D，R)。其中，D是数 据元素的有穷集合，R是D上关系的有限集合。 [例6-7] 分析以下程序段的时间复杂度。

for(i=0；i

x=x+1； //语句②

for(j=0；j<2*n；j++) //语句③ y++； //语句④ }

学习必备 欢迎下载

解析：语句的执行频度指的是语句重复执行的次数。一个算法中所有语句的执行频度之和构成了该算法的运行时间。在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n(2n+2)＝2n2-2n，语句④的执行频度是n(2n+1)＝2n2+n。该程序段的时间复杂度T(n)＝(n+1)+n+(2n2+2n)+(2n2+n)＝4n2+5n+1＝O(n2)。 实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句④为基本操作，其执行频度为2n2+n，因此， 该算法的时间复杂度T(n)＝2n2+n＝O(n2)。 [例6-8] 分析以下程序段的时间复杂度。 i=1；

while(i<=m) i=i*2；

解析：上述算法的基本操作语句是i＝i*2，设其执行频度为T(n)，则有：2T(n)≤n，即 T(n)≤lbn＝O(lbn)。因此，该程序段的时间复杂度为O(lbn)。

学习必备 欢迎下载

7.3 典 型 例 题

一、单项选择题

[例7-1] 在数据结构中，与所使用计算机无关的数据叫( ① )结构；链表是一种采用( ② )存储结构存储的线性表；链表适用于( ③ )查找；在链表中进行( ④ )操作的效率比在线性表中进行该操作的效率高。

①A．存储 B．物理 C．逻辑 D．物理和逻辑 ②A．顺序 B．网状 C．星式 D．链式 ③A．顺序 B．二分法 C．顺序及二分法 D．随机 ④A．二分法查找 B．快速查找 C．顺序查找 D．插入 解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。 [例7-2] 链表不具备的特点是( )。

A．插入和删除不需要移动元素 B．可随机访问任一结点

C．不必预分配空间 D．所需空间与其长度成正比

解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个 结点。本题答案为：B。

[例7-3] 不带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head_>next＝＝NULL C．head_>next＝＝head D．head!＝NULL

解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结 点，head＝＝NULL表示该单链表为空。本题答案为：A。 [例7-4] 带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL

解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝NULL表示该单链表为空。本题答案为：B。

[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL

解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝head表示该单链表为空。本题答案为：C。 [例7-6] 线性表采用链式存储时其存储地址( )。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以

解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。 [例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。

A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior； B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior； C．s—>next=p；s—>prior=p—>prior；p—prior=s；p—>prior—>next=s； D．s—>next=p；s—>prior=p—>prior；p—prior—>next=s；p—>prior=s；

解析：在双向链表的 * p结点前插入新结点 * s的操作如图7.12所示，图中虚线为所 作的操作，序号为操作顺序。本题答案为：D。

学习必备 欢迎下载

图7.12 双向链表插入结点的过程示意图

(例7-8) 若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。

A．单链表 B．双向链表

C．给出表头指针的循环单链表 D．给出尾指针的循环单链表

解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中， 只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案 为：D。

[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。

A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C．顺序输出前k个元素 D．交换其中某两个元素的值

解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。

(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。 A．只有表头指针的不带头结点的循环单链表 B．只有尾指针的不带表头结点的循环单链表 C．只有表尾指针的带头结点的循环单链表 D．只有尾指针的带表头结点的循环单链表 解析：本题答案为：A。具体算法如下： linklist * delfirst(linklist * h) {

Linklist * p＝h；

while(p—> next!＝h) //找到表尾结点 p＝p—>next；

p—>next=h—> next； free(h)；

returnp一>next； //返回头指针

}

二、填空题

[例7-11] 在单链表中结点 * p后插入结点 * s的指令序列为 ； 。 解析：在单链表中结点 * p后插入结点 * s，即将 * p 的后继结点变为 * s 的后继结点， * s 则成为 * p的后继结点。操作指令序列为：s—>next＝p—>next；p—>next＝s。

[例7-12] 在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 和 ；而根据指针的链接方式，链表又可分为 和 。 解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。 [例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。