最新《数据结构与算法》(清华)典型例题.doc
《最新《数据结构与算法》(清华)典型例题.doc》由会员分享,可在线阅读,更多相关《最新《数据结构与算法》(清华)典型例题.doc(59页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、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 算法指的是( ),它必须具备( )这三个
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)。其中,D
4、是数据元素的有穷集合,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。图7
8、.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; free
10、(h); returnp一next; /返回头指针 二、填空题 例7-11 在单链表中结点 * p后插入结点 * s的指令序列为 ; 。 解析:在单链表中结点 * p后插入结点 * s,即将 * p 的后继结点变为 * s 的后继结点,* s 则成为 * p的后继结点。操作指令序列为:snextpnext;pnexts。 例7-12 在线性表的链式存储结构中,根据每个结点所含指针的个数,链表可分为 和 ;而根据指针的链接方式,链表又可分为 和 。 解析:本题答案为:单链表;多重链表;循环链表;普通链表(非循环链表)。 例7-13 在单链表中,要删除某一个指定的结点,必须找到该结点的 结点。 解
11、析:由单链表的特点可知,删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。本题答案为:前驱。 例7-14 在一个长度为n的顺序表中删除第i(0in一1)个元素,需向前移动 个元素。 解析:需将第i个元素后的元素依次前移一个位置,总共移动(n-1)-(i+1)+1个元素。本题答案为:n-i-1。 例7-15 在一个具有n个结点的单链表,在 * p结点后插入一个新结点的时间复杂度是 ;在给定值为x的结点后插入一个新结点的时间复杂度是 。 解析:在 * p结点后插入一个新结点 * s的操作是:s nextp next;pnexts;其时间复杂度为0(1)。 在给定值为x的结点后
12、插入一个结点,首先要找到该结点,然后再进行插入。找到该结点的时间复杂度为O(n),插入的时间复杂度为O(1)。本题答案为:O(1);O(n)。三、应用题 (例7-16) 设A是一个线性表(a0,a1,ai,an-1),采用顺序存储结构,则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在ai和ai+1之间(0in-1)的概率为,则平均每插入一个元素所需要移动的元素个数是多少? 解析:在等概率情况下,平均每插入一个元素需要移动的元素个数为:若元素插在ai和ai+l之间(0in-1)的概率为,则平均每插入一个元素所需要移动的元素个数为: (例7-17) 简述线性表采用顺序存储方式
13、和链式存储方式的优缺点。 解析:顺序表的优点是可以随机访问数据元素,而且不需要额外的空间存储元素间的逻辑关系;缺点是表的大小固定,增减结点需要移动大量元素。链表的优点是增减元素非常方便,只需要修改指针内容;缺点是只能进行顺序访问,另外在每个结点上增加指针域会造成存储空间增大。 例7-18 若频繁地对一个线性表进行插入和删除操作,则应采用何种存储结构来存储该线性表?为什么? 解析:应采用链式结构来存储该线性表。采用链式存储结构来存储线性表,在进行插入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上,查找过程中平均移动指针域的次数为表长的一半;而采用顺序存储结构存储线性表,在进行插入
14、和删除操作时的复杂度则体现在元素的移动上,平均需移动表中的一半元素。因为指针域的移动操作次数比元素的移动操作次数少得多,所以应采用链式结构来存储该线性表。 (例719) (1)写出在双向链表中的结点 * p前插入一个结点 *s的语句序列。 (2)写出判断带头结点的双向循环链表L为空表的条件。 解析:(1)spriorpprior;pprior nexts; snextp;ppriors; (2)(LLnext)&(LLprior) 例7-20 链表所表示的元素是否是有序的?如果有序,则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 解析:链表所表示的元
15、素是有序的,其有序性体现在逻辑有序,即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序,而且在物理结构上也有序。 四、算法设计题 (例7-21) 编写一个算法,将一个带头结点的单链表逆转。要求在原链表空间上进行逆转,即不允许构造新的链表结点; 解析:从单链表的一种构造方法头插法中可以得知,该方法构造的线性表中结点 的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表, 所构造的单链表即为原表的逆转。 具体算法如下: linklist * reverse(1inklist * h) linklist * p,*q,*r; phnext;
16、hnext=NULL; /构造空表 while(p!NULL) q=p; /拆下结点 p=p next; qnext=hnext; /用头插法插入 hnext=q; return h; (例7-22) 已知一个顺序表La的元素按值非递减有序,编写一个算法将元素x插人后保持该表仍然按值非递减有序。 解析:要让插入新元素后的顺序表仍然按值非递减有序,必须把x插入到表中第一个大于等于x的元素之前。应先在表中找到该位置,然后后移该元素,空出一个位置,再将x插入。 具体算法如下: insert(sqlist *La,datatype x) /La为指向顺序表的指针 int i=0,j; while(il
17、ast) /查找插入位置i if(xdatai) break; i+; for(j=Lalast+1;ji;j-) /后移所有大于等于x的元素 Ladataj=Ladataj-1; Ladataix; /将x插入 Lalast+; /表长度加1 (例7-23) 用顺序表A、B表示集合,编写算法求集合A和集合B的交集C(假设A、B表内无重复元素)。 解析:求CAB,C中元素是A、B中的公共元素。对于表A中的每个元素,在表B中扫描,若有与它相同的元素,则为交集元素,将其放到C中。 具体算法如下: intersection(sqlist A,sqlist B,sqlist * C) int i,j,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法 最新 数据结构 算法 清华 典型 例题
限制150内