数据结构课后习题答案
上传者:高智杰|上传时间:2015-05-07|密次下载
数据结构课后习题答案
参考答案
第一章、绪论
一、选择题 1 B;2 A; 3 B; 4 C ;5 C; 6 B;7 C;8 C; 9 D; 10 B。
二、填空题1、存储 ;2、无 ,1,无,1; 3、前驱,1,后继,任意多个;4、一对一,一对多,多对多;5、时间复杂度,空间复杂度;6、集合,线性结构,树形结构,图形结构;
7、顺序结构,链式结构,索引结构,散列结构;8、顺序。
三、问答题与算法题
1、3 ;
2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ; T4 ( n ) = 1.5 n 2 + O ( n ) 。T4 ( n ) 较优,T3 ( n )较劣。
3、见课本。
第二章 线性表
一、选择题 1C;2A;3D;4B;5D;6B;7C;8B;9A;10C;11D;12D;13C;14C.
二、填空题 1、O ( 1 ), O ( n );2、单链表,双链表;3、地址,指针;4、4,2;5、便于访问尾结点和头结点;6、前驱;7、L->next== L且L->prior== L;8、顺序。
三、问答题与算法题
1、头指针:结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址,从头指
针出发可以找到链表中所有结点的信息。
头结点:是附加在链表的第一个结点之前的一个特殊结点,其数据域一般不存放信息。
其作用是为了简化运算,将空表与非空表统一起来,将第一个结点与其他结点的处理统一起来。
首结点:是链表的第一个结点。
2、(1)基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。
(2)基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之, 若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。
3、尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表,则查找终端结点的时间为O(n)
4、S=P->Prior; P->Prior=S->Prior; S->Prior->Next=P; S->Prior=P; S->Next=P->Next; P->Next=S;S->Next->Prior=S;
5、:将开始结点摘下链接到终端结点之后成为新的终端结点,而原来的第二个结点成为新的开始结点,返回新链表的头指针
6、15,26,51,37,48,,55。
7、CreatList_L(LinkList &L int n) {
L= (LinkList) molloc (sizeof (Lnode));//头结点
L->next==NULL; q=L;
For(i=1;i<=n;++i)
41
{ P= (LinkList) molloc (sizeof (Lnode));
Scanf(&(p->data));
p->next=NULL; q->next=p; q=p;}
returen OK;
}
8、Void sinsert(Sqlist &S, int x)
{int i=0; n=S.Length;
while(x<S.elem[i]&& i<n) i++; //查找插入点
if(i==n) S.elem[n]=x; //插在最后一个结点的后面
else {for(j=n-1;j>=i;j++)
S.elem[j+1]=S.elem[j]; //元素后移
S.elem[i]=x; //插入
}
}
9、int ListLength(LinkList L)
{q=L->next; i=0;
while(q)
{i++; q=q->next; }
return i;
10、int delete(LinkList &L, int x) {
p=L->next; //p为定位指针
q=L; //q为定位指针的前导
while((p->data!=x) && p)
{ q=p; //q前进
p=p->next; //p前进
}
if(!q) return ERROR; //查找失败
q->next=p->next ;
free(p);
return OK;
}
11、void mergelist(linklist &La, linklist Lb)
{pa=La->next; pb=Lb->next;pc=La;
while (pa && pb)
if (pa->data< pa->data) {pc->next=pa;pc=pa;pa=pa->next;}
else if(pa->data== pa->data) {pc->next=pa; pc=pa; pa=pa->next; pb=pb->next;} else ({pc->next=pb;pc=pb;pb=pb->next;}
pc->next=pa? pb:pb;
}
12、Void invertlinklist(linklist &L)
{if(!L) return OK; //空表
p=L->next;
if(!p) return OK; //仅有一个结点的表
else{q=p->next; //q指向p的后继
42
p->next=NULL;
while(q)
{ r=q->next ; //r指向q的后继
q->next=p; //逆置
p=q; //p前进
q=r; //q前进
}
L=p; //第一个结点
}
}
13、Void delDuplicate(int A[],int & n)
{ for(i=0;i<n-1;i++)
for(j=i+1;j<=n-1;j++)
if(a[i]==a[j])
{n--;
for(k=j+1;k<=n-1;k++)
a[k-1]=a[k];
}
}
第三章 栈和队列
一、选择题1A;2D;3C;4C;5D;6C;7C;8B;9C;10C;11D,B;12D;13B。
二、填空题
1、栈顶;2、满,空,n;3、后进先出,先进先出;4、头;5、L->next==NULL,S.top==S.base, S.top-S.base==S.stacksize,L==NULL,Q.front==Q.rear,(Q.rear+1)%maxQsize ==Q.front;
6、Q.rear-Q.front+n)%n;7、1nC2n;8、n-1。 n?1
三、问答题与算法题
1、 1324;
2、(1) int push_L(Linkstack &s SelemType e)
{ p= (LinkStack) molloc (sizeof (Snode));
if(!p) return ERROR;
p->data=e;
p->next=s;
s=p;
Return Ok;
}
(2)int pop_L(Linkstack &s SelemType &e)
{ if(!S) return ERROR;
q=s;
e=s->data;
s=s->next;
free(q);
Retuen Ok;
}
43
3、(1)int EnQueue_L(Queueptr &QL QelemType e) { p= Queueptr} molloc (sizeof (Qnode));
if(!p) return ERROR;
p->data=e;
p->next=QL->next->next;
QL->next->next= p;
Retuen Ok;
}
(2)int DeQueue_L(Queueptr &QL QelemType &e) { if(QL->next==QL)} return ERROR;
p= QL->next
while(p->next!=QL) p =p->next;
p->next=QL->next;
e=QL->next;
free(QL);
QL=p;
Return Ok;
}
4、(1) 栈S元素反序存放;
(2) 把栈s1复制到s2;
(3) 把栈S中值等于m的元素删除;
(4) 队列Q元素反序存放;
(5) 链表中的元素反序存放;
5、Int hw4(LinkList L)
{ initstack(S);
bool=1;n=0;
p=L->next;
while(p){n++; p=p->next;} //求串长
p=L->next; //p指向第一个结点 for(i=0; i<n/2; i++) {push(S,p->data); p=p->next;} if(n%2==1) p=p->next; //对照解法1
while(p&&bool)
{pop(S,ch);
if(ch!=p->data) bool=0;
p=p->next;
}
return bool;
}
6、void ClearStack( LinkStack &S)。
{while(!S)
{p=s;
s=s->next;
free(p);
44
}
return OK;
}
7、int Stacksize( LinkStack S)。
{ n=0;
p=s;
While(!p)
{n++;
p=p->next;
}
return n;
}
8、见4、(5)
第四章 串
一、选择题
1 B;2B;3D;4 B;5C;6 D。
二、填空题
1、空格串;2、静态分配的顺序串、动态分配顺序串、块连串;3、?\0? 4、块的大小;
5、2;6、StrAssing,StrCompare,StrLength,Concat,SubString;7、13,6;8、模式,目标(主)。
三、问答题与算法题
1、 ●空串是指不包含任何字符的串,它的长度为零。
空格串是指包含一个或多个空格的串,空格也是字符, 长度不为零。
●串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
●主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串的子串,而包含
子串的串就称为主串。
●目标串和模式串:在串匹配运算过程中,将主串称为目标串,而将需要匹配的子串称为
模式串,两者是相对的。
2、(1) "Stocktom, March51999";(2) 正数;(3) 正数;(4)18
3、void StrInsert(char *S, char *T, int i)
{//将串T插入到串S的第i个位置上
char *Temp;
if(i<=strlen(S))
{Temp=(char *)malloc(sizeof(char[Maxsize])); // 设置一个临时串
strcpy(Temp,&S[i]); //将第i位起以后的字符拷贝到临时串中
strcpy(&S[i], T); /将串T拷贝到串S的第i个位置处,覆盖后面的字符
strcat(S,Temp); //把临时串中的字符联接到串S后面
free( Temp );
}
}
4、void StrDelete(char *S, int i , int m) //串删除
{ char Temp[Maxsize]; //定义一个临时串
if(i+m<strlen(S))
45
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- TOP10水浒传十大娇花:第一美女是她万万想不到!
- 北师大版小学一年级语文上册《小书架》教学反思
- 人教版小学二年级语文上册《赠刘景文》教学反思
- 秦琼——凌烟阁二十四功臣之一
- 人教版小学语文一年级下册第四单元教学计划
- 人教版八年级语文下册《岳阳楼记》教学反思
- 交通肇事罪中刑事附带民事赔偿范围
- 六年级下册语文教学计划
- 三年级语文下册教学计划
- 商品房预售合同定金纠纷处理规则商品房买卖合同实务问题解析(五)
- 试析金庸武侠小说人物归隐结局
- 一年级语文上册期中考试试卷分析
- 论共同犯罪中的主犯
- 苏教版小学四年级语文上册《九寨沟》教学反思
- 四年级下册语文教学计划
- 交付发票是税法上的义务还是合同法上的义务?
- 苏教版四年级语文上册《田园诗情》教学反思
- “精彩极了”和“糟糕透了”教案设计
- 金庸小说对中国武侠小说的超越
- 中国历史上最美的皇后:古代著名的“五大艳后”
- 3-5年级舞蹈课教学计划
- 一代贤后卫子夫是怎么死的
- 物权善意取得制度还有存在的必要吗
- 大主宰和作者天蚕土豆的故事
- 股权转让合同中“不办理工商变更登记”的约定是否有效?
- 小学三年级语文上册《花钟》教学反思
- 小学四年级语文上册《一块特别的石头》教学反思
- 金庸小说中20位反派高手排行榜
- 西汉废帝刘贺当了几天皇帝?
- 一年级语文教学计划
网友关注视频
- 二年级下册数学第一课
- 冀教版英语三年级下册第二课
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925
- 沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
- 3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
- 六年级英语下册上海牛津版教材讲解 U1单词
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
- 二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
- 青岛版教材五年级下册第四单元(走进军营——方向与位置)用数对确定位置(一等奖)
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 苏教版二年级下册数学《认识东、南、西、北》
- 七年级下册外研版英语M8U2reading
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
- 沪教版八年级下册数学练习册21.4(1)无理方程P18
- 沪教版八年级下册数学练习册一次函数复习题B组(P11)
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 沪教版八年级下册数学练习册21.3(2)分式方程P15
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 七年级英语下册 上海牛津版 Unit3
- 冀教版小学数学二年级下册第二单元《租船问题》
- 化学九年级下册全册同步 人教版 第22集 酸和碱的中和反应(一)
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 沪教版牛津小学英语(深圳用)五年级下册 Unit 1
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
- 河南省名校课堂七年级下册英语第一课(2020年2月10日)
- 沪教版八年级下次数学练习册21.4(2)无理方程P19
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理