资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构与算法习题册(课后部分参考答案)数据结构与算法课程组目录目录课后习题部分第一章 绪论1第二章 线性表3第三章 栈和队列5第四章 串8第五章 数组和广义表10第六章 树和二叉树13第七章 图16第九章 查找20第十章 排序23课后习题部分 第一章绪论第一章 绪论一. 填空题1. 从逻辑关系上讲,数据结构的类型主要分为 集合 、线性结构、树结构和 图结构。2. 数据的存储结构主要有 顺序存储和 链式存储 两种基本方法,不论哪种存储结构,都要存储两方面的内容:数据元素 和 数据元素之间的关系 。3. 算法具有五个特性,分别是 有穷性 、 确定性、可行性、 输入 、 输出 。4. 算法设计要求中的健壮性指的是 算法在发生非法操作时可以作出处理的特性。二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的,链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。A 线性结构 B 非线性结构 C 存储位置 D 指针2. 假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是 B 。A 树 B 图 C 线性表 D 集合3. 算法指的是 A 。A 对特定问题求解步骤的一种描述,是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理三. 简答题1. 分析以下各程序段,并用大O记号表示其执行时间。(1) (2)i=1;k=0;i=1;k=0;While(in-1)do k=k+10*i; k=k+10*i; i+; i+; while(inext =rear-next; rear-next =s; rear =s;;删除开始结点的操作顺序为q=rear-next-next; rear-next-next=q-next; delete q; 。 二. 选择题1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的,称之为: C A存储结构 B逻辑结构 C顺序存储结构 D链式存储结构2. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: A A 访问第i个结点(1in)和求第i个结点的直接前驱(2in) B 在第i个结点后插入一个新结点(1in)C 删除第i个结点(1in) D 将n个结点从小到大排序3. 线性表L在 B 情况下适用于使用链式结构实现。A 需经常修改L中的结点值 B 需不断对L进行删除插入C L中含有大量的结点 D L中结点结构复杂4. 单链表的存储密度 C A大于1 B等于1 C小于1 D不能确定三. 判断题1. 线性表的逻辑顺序和存储顺序总是一致的。 F 2. 线性表的顺序存储结构优于链接存储结构。 F 3. 设p,q是指针,若p=q,则*p=*q。 F 4. 线性结构的基本特征是:每个元素有且仅有一个直接前驱和一个直接后继。 F 四. 简答题1. 分析下列情况下,采用何种存储结构更好些。(1)若线性表的总长度基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素。(2)如果n个线性表同时并存,并且在处理过程中各表的长度会动态发生变化。(3)描述一个城市的设计和规划。 应选用顺序存储结构。很少进行插入和删除操作,所以空间变化不大,且需要快速存取,所以应选用顺序存储结构。 应选用链式存储结构。链表容易实现表容量的扩充,适合表的长度动态发生变化。 应选用链式存储结构。因为一个城市的设计和规划涉及活动很多,需要经常修改、扩充和删除各种信息,才能适应不断发展的需要。而顺序表的插入、删除的效率低,故不合适。五. 算法设计1. 已知数组An中的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为O(n)。2. 线性表存放在整型数组Aarrsize的前elenum 个单元中,且递增有序。编写算法,将元素x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。int insert (datatype A,int *elenum,datatype x)/*设elenum为表的最大下标*/if (*elenum=arrsize-1) return 0;/*表已满,无法插入*/else i=*elenum; while (i=0 & Aix)/*边找位置边移动*/Ai+1=Ai;i-; Ai+1=x;/*找到的位置是插入位的下一位*/ (*elenum)+;return 1;/*插入成功*/O(n)课后作业部分 第三章 栈和队列第三章 栈和队列一. 填空题1. 设有一个空栈,栈顶指针为1000H,现有输入序列为1. 2. 3. 4. 5, 经过push,push,pop,push,pop,push,push后,输出序列是 23 ,栈顶指针为 1003H 。2. 栈通常采用的两种存储结构是 顺序栈 、 链栈 ;其判定栈空的条件分别是 TOP=-1 、 TOP=NULL ,判定栈满的条件分别是 TOP=数组长度 、 存储空间满 。3. 栈 可作为实现递归函数调用的一种数据结构。4. 表达式a*(b+c)-d的后缀表达式是 abc+*d- 。二. 选择题1. 若一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是 D 。A 不确定 B n-i C n-i-1 D n-i+12. 设栈S和队列Q的初始状态为空,元素e1. e2. e3. e4. e5. e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2. e4. e3. e6. e5. e1,则栈S的容量至少应该是 C 。A 6 B 4 C 3 D 23. 一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是 C 。A 54321 B 45321 C 43512 D 12345 三. 判断题 1. 有n个元素依次进栈,则出栈序列有(n-1)/2种。 F 2. 栈可以作为实现过程调用的一种数据结构。 T 3. 在栈满的情况下不能做进栈操作,否则将产生“上溢”。 T 4. 在循环队列中,front指向队头元素的前一个位置,rear指向队尾元素的位置,则队满的条件是 front=rear。 F 四. 简答题1. 设有一个栈,元素进栈的次序为A,B,C,D,E,能否得到如下出栈序列,若能,请写出操作序列,若不能,请说明原因。 C,E,A,B,D C,B,A,D,E不能,因为在C、E出栈后,A一定在栈中,而且在B的下面,不可能先于B出栈可以,设为进栈操作,为入栈操作,则其操作序列为IIIOOOIOIO。2. 在操作序列push(1). push(2). pop. push(5). push(7). pop. push(6)之后,栈顶元素和栈底元素分别是什么?(push(k)表示k入栈,pop表示栈顶元素出栈。)栈顶元素为6,栈底元素为1。3. 在操作序列EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后,队头元素和队尾元素分别是什么?(EnQueue(k)表示整数k入队,DeQueue表示队头元素出队)。队头元素为5,队尾元素为9。4. 简述以下算法的功能(栈的元素类型SElemType为int)。 (1) status algo1(Stack S,int e) Stack T; int d; InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d); Push(S,d); /S中如果存在e,则删除它。(2) void algo2(Queue &Q)Stack S; int d; InitStack(S);whi
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号