《数据结构典型例题集》由会员分享，可在线阅读，更多相关《数据结构典型例题集（59页珍藏版）》请在金锄头文库上搜索。
1、基本概念 典型例题一、单项选择题 例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 算法指的是( )，它必须具备( )这三
2、个特性。 A计算方法 B排序方法 C解决问题的步骤序列 D调度方法 A可执行性、可移植性、可扩充性 B可执行性、确定性、有穷性 C确定性、有穷性、稳定性 D易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本题答案为：B。 例6-4 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；in；i+) for(j=0；jn；j+) x=x+l： AO(2n) BO(n) CO(n2) DO(1bn) 解析：语句的执行频度即语句重复执行的次数，属于算法的时间
3、复杂度类题目。本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为nnn2次。由此可知，本题答案为：C。二、填空题例6-5 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。 解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数据项；数据项。三、应用题 例6-6 简述数据结构的定义。 解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。用集合的观点可以把数据结构表示为一个二元组DS(D，R)。其中，
4、D是数据元素的有穷集合，R是D上关系的有限集合。 例6-7 分析以下程序段的时间复杂度。 for(i=0；in；i+) /语句 x=x+1； /语句for(j=0；j2*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+1O(n2)。 实际上，可以用算法中基本操作重复执行的频度作
5、为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句为基本操作，其执行频度为2n2+n，因此，该算法的时间复杂度T(n)2n2+nO(n2)。 例6-8 分析以下程序段的时间复杂度。 i=1； while(inextNULL Chead_nexthead Dhead!NULL 解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，headNULL表示该单链表为空。本题答案为：A。 例7-4 带头结点的单链表head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dhead!NULL 解析：
6、在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，headnextNULL表示该单链表为空。本题答案为：B。 例7-5 带头结点的循环单链表head中，head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dhead!NULL 解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，headnexthead表示该单链表为空。本题答案为：C。 例7-6 线性表采用链式存储时其存储地址( )。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以解析：链式存储采用动态存
7、储，地址一般不连续。本题答案为：D。例7-7 在双向链表的* p结点前插入新结点*s的操作为( )。 Apprior=s；snext=p；ppriornext=s；sprior=pprior； Bpprior=s；ppriornext=s；snext=p；sprior=pprior； Csnext=p；sprior=pprior；pprior=s；ppriornext=s； Dsnext=p；sprior=pprior；ppriornext=s；pprior=s； 解析：在双向链表的 * p结点前插入新结点 * s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。本题答案为：D。图
8、7.12 双向链表插入结点的过程示意图 (例7-8) 若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。 A单链表 B双向链表 C给出表头指针的循环单链表 D给出尾指针的循环单链表 解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案为：D。 例7-9 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。 A删除所有值为x的元素 B在最后一个元素的后面插入一个新元素 C顺序输出前k个元素 D交换其中某两个元素的值 解析：对
9、于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。 (例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。 A只有表头指针的不带头结点的循环单链表 B只有尾指针的不带表头结点的循环单链表 C只有表尾指针的带头结点的循环单链表 D只有尾指针的带表头结点的循环单链表 解析：本题答案为：A。具体算法如下： linklist * delfirst(linklist * h) Linklist * ph； while(p next!h) /找到表尾结点 ppnext； pnext=h next； fre
10、e(h)； returnp一next； /返回头指针 二、填空题 例7-11 在单链表中结点 * p后插入结点 * s的指令序列为 ； 。 解析：在单链表中结点 * p后插入结点 * s，即将 * p 的后继结点变为 * s 的后继结点，* s 则成为 * p的后继结点。操作指令序列为：snextpnext；pnexts。 例7-12 在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 和 ；而根据指针的链接方式，链表又可分为 和 。 解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。 例7-13 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。 解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。本题答案为：前
