还剩5页未读,继续阅读
文本内容:
第一章
1.怎样理解“算法+数据结构=程序”这个公式?举例说明算法是语句序列解决特定问题的固有程序片段数据结构是确定数据间的关系从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法,最后编写出程序寻求数学模型的是指就是数据结构要完成的工作参看书pl前两段的描述
2.数据结构的概念,它包含哪三方面的内容?数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科参看书p3包含三方面的内容:
1、数据之间的逻辑关系
2、数据在计算机中的存储方式
3、在数据上定义的运算的集合
3.数据、数据元素、数据项的基本概念举例说明数据元素和数据项的联系与区别数据描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合数据元素数据的基本单位,在计算机程序中通常作为一个整体进行考虑或处理数据项数据项是具有独立含义的最小标识单位,是数据元的一个具体值,是数据记录中最基本的、不可分的有名数据单位例1class A{int c[12司;int i;);class B{A a;)Bb;b.a是数据项,B是数据元素例2一本书的数目信息为一个数据元素,而数目信息中每一项(如书名、作者名等)为一个数据项
4.从逻辑结构来看,数据结构有哪四种基本结构,各自的特点是什么?
1、集合(数据元素之间同属于一个集合,再无其他关系)
2、线性结构(数据元素之间存在一对一的关系)
3、树形结构(数据元素之间一对多的关系)
4、图状结构或网状结构(数据元素之间多对多的关系)
5.从物理结构来看,数据结构有哪两种基本结构,各自的特点是什么?
1、顺序存储结构特点借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系
2、链式存储结构特定借助元素在存储地址的指针表示数据元素之间的逻辑关系
6.算法的5个特征,4个评价标准是什么?特征:有穷性、确定性、可行性、输入、输出评价标准正确性、可读性、健壮性、效率与低存储量需求
7.描述时间复杂度1x=0;y=0;z=0;for i=l;i=n;i++{x++;for j=l;j=n;j++{y++;for k=0;k=2*n;k++z++;}}程序片段中语句x=
0、x++、y++、z++的时间复杂度和整段程序的时间复杂度01On On A2On A3OnA3第二章线性表
1.描述线性结构的特点
2.判断对错,并解释说明1线性表中的数据元素可以是各种各样的,但同一线性表中的元素一定具有相同特性/2线性表采用顺序存储表示时,必须占用一片连续的存储单元/3线性表采用链式存储表示时,不能占用一片连续的存储单元x
3.顺序表的第一个元素的存储地址是101,每个元素的长度为3,计算出第6个元素的存储地址是多少?LOC a6=LOCal+5*L=101+5*3=
1164.长度为n的顺序表中,在第i个元素前插入一个新元素时,需要移动多少个元素?插入算法的平均移动次数是多少,时间复杂度是什么?参看书P24〜25,需要移动n・i+l个元素,平均移动次数为n/2,时间复杂度是On
5.长度为n的顺序表中,将第i个元素删除时,需要移动多少个元素?删除算法的平均移动次数是多少,时间复杂度是什么?参看书P24〜25,需要移动n・i个元素,平均移动次数为1/2,时间复杂度是On
6.线性链表的存储特点是?单链表中的结点由哪两部分构成,画图说明
7.在一个单链表中,q所指结点是p所指结点的直接前驱结点,若在q与p之间插入一个s所指的结点,写出执行的两条语句提示先链接、后断开s-next=p;q-next=s;或者s-next=q-next;q-next=s;
8.在单链表中,w所指结点是s所指结点的直接前驱结点删除s结点,写出执行的两条语句w-next=s-next;frees
9.画图说明单循环链表为空的状态,并写出循环链表判断是否为空的语句参看书P35图
2.12b判空语句H-next=H
10.双向链表中,要在指针q指向的结点后插入新结点t,写出执行的四条语句t-prior=q;t-next=q-next;q-next=t;t-next-prior=s
11.双向链表中,要删除指针q的后继结点,写出执行的两条语句T=q-next;q-next=t-next;freet;或者t=q-next;q-next-q-next-next;free(t)第三章栈和队列12判断对错(X)栈和队列是操作受限的线性表/
(2)栈的插入操作只需要在表尾端进行,队列的插入操作只需要在表头进行x
(3)栈的操作只和栈顶指针TOP相关,队列的操作只和队头指针FRONT相关x13栈的特点是?队列的特点是?(先进先出、先进后出中选择)栈的特点是先进后出(FILO)队列的特点是先进先出(FIFO)14用文字描述算法(参照我写的
(1)的算法描述完成)
(1)顺序存储的栈插入操作算法描述
(2)顺序栈的删除操作算法描述第一步,判断栈是否为空,如果栈空,不能进行删除操作;第二步,栈不空的时候,栈顶指针TOP减1,向下移动一位;第三步,将要删除的栈顶元素用新变量保存;
(3)链式存储的队列的插入操作算法描述第一步,利用指针创建新结点,新节点的数据域值为要入队列的元素,新结点的指针域复制为NULL;第二步,将链队列的尾节点链接上新结点;第三步,修改链队列的尾指针的指向,让它指向新结点;
(4)链栈的删除操作算法描述第一步,利用指针创建新结点,新节点的数据域值为要入栈的元素,新结点的指针域复制为NULL;第二步,新结点的指针域指向链栈的头结点;第三步,修改链栈的头指针TOP的指向,让它指向新结点;15假设栈为S,写出判断语句typedef structsqstack(int data[max];int top;Jsqstack;sqstack*s;
(1)顺序栈为空的条件判断语句s-top==0
(2)顺序栈为满的条件判断语句s-top==max16假设队列为Q,写出判断语句typedef structSqQueue intdata[MAX];int front;int rear;/*定义队头指针Front和队尾指针Rear*/;SqQueue*Q1循环队列为空的条件判断语句Q-rear==Q-front2循环队列为满的条件判断语句Q-rear+l%MAX==Q-front17总结说明,线性表的顺序存储与链式存储的区别?参看书P27第一段第六章树和二叉树
1.一棵二叉树的广义表表示为abc,d,ef,g,它含有双亲结点4个,单分支结点2个,叶子结点3个二叉树根为a;a有左孩子b,右孩子e;b有左孩子c,右孩子d;e只有左孩子f,f只有右孩子g
2.判断对错1在树中,如果从结点K出发,存在两条分别到达K、,K、、的长度相等的路径,则结点K、,K、、互为兄弟x,还可能是堂兄结点2完全二叉树的某结点若无左孩子,则必是叶结点/,由完全二叉树的性质决定3一棵完全二叉树按层次遍历的序列为A BCDEFGHI,则在后序遍历中结点B的直接后继是F/由于是完全二叉树,所以树中第一层是A,第二层从左向右是B和C,第三层是D、E、F、G,第四层从左向右是H和I画出二叉树,进行后序遍历,后序遍历序列为HIDEBFGCAo4二叉树的后序遍历序列中,任意一个结点均处在其子树结点的后面/后序遍历算法决定的,左、右、根5由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树*不唯一,因为只有在中序遍历中才能划分左右子树6树存储时采用双亲表示法时,求某个结点的孩子时需要遍历整个结构/7一棵有n n^l个结点的d叉树,若用多重链表表示,树中每个结点都有d个链域,则在树的nd个链域中,有n d-l+1个是空链域,只有ml个是非空链域/根据树的特性一对多,每个结点都有且仅有一个双亲结点,除了根结点外因此,n个结点的树中有n-1个结点都有且仅有一个双亲,这个关系表示在链式存储里就一定会占用它双亲的一个指针域,所以树中一定有n4个非空指针域,多叉树也适用8在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加2/解二叉链表中有n个结点时,一定存在2n个指针域,n+1个空链域,则非空链域为ml个,所以,空链域=非空链域+29树的后根遍历序列等同于该树对应的二叉树的中序遍历,,参看书P138笔记
(10)树利用孩子兄弟表示法转换后的二叉树中根结点一定不存在右子树/,参看书P137页最后一句话
3.二叉树根结点的层次为1,所有含有15个结点的二叉树中,最小高度是4o要想得出最小高度,必须是完全二叉树才能保证,因此这个题目考核的是有15个结点的完全二叉树的高度是?参看二叉树性质4,即可得出
4.设一棵二叉树结点的先根序列为ABDECFGH,中根序列为DEBAFCHG,则二叉树中叶子结点是(EFH)参看书P154例题
5.树的存储结构有几种?分别是?二叉树的存储结构有几种,分别是?树的存储结构有三种双亲表示法、孩子表示法、孩子兄弟表示法二叉树的存储结构有两顺序存储、链式存储(又叫二叉链表的表示法)在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加
(2)
6.若二叉树有7个度为2的结点,试问有?个终端结点由二叉树的性质3得出,nO=n2+L所以度为1的终端结点有7+1=8个
7.一棵有124个叶结点的完全二叉树,最多有?个结点首先,由二叉树的性质3得出,度为2的结点个数为1244=123个;又根据二叉树的定义可以得出这样的结论完全二叉树的前加1层
8.一棵完全二叉树上有1001个结点,其中叶子结点的个数是?500解设分支总数变量为b,则n=b+L得出分支数为1000分支数是偶数,所以不存在度为1的结点,只有度为2的结点和叶子结点根据性质3,n0=n2+l,所以1001=n0+n2=2*n0+l n0=500o
9.w={4,5,6,7,8},如何构建哈夫曼树?第9章查找
1.查找表的概念?这是四种经典数据结构中的哪一种?
2.静态查找和动态查找有什么联系和区别?
3.查找表中的关键字是数据元素还是数据项,有什么特点?
4.ASL表示什么?写出计算的公式,并解释公式中每个变量的含义
5.描述顺序查找的算法思想(用汉字描述,不是代码)
6.描述折半查找的算法思想
7.给定由以下元素组成的关键字序列(55,46,89,13,24,67,23,15),将他们存储在数组的第1位至第8位,现在要查找关键字为15和100的元素描述查找过程
8.画出包含8个元素的查找表对应的折半判定树树的深度为?
9.根据给定的序列Q1,54,43,76,87,65,32),生成一棵二叉排序树,并分析该二叉排序树的平均查找长度ASL;同时根据该序列,生成一棵平衡二叉树,并分析该平衡二叉树的平均查找长度ASLo第10章排序
1.比较分析9种排序方法的时间复杂度和稳定性排序方法平均时间最坏情况辅助空间稳定性直接插入排序On2On201稳定希尔排序On13On L301不稳定冒泡排序On2On2O⑴稳定快速排序Onlogn On2Ologn不稳定直接选择排序On2On201不稳定堆排序Onlogn Onlogn01不稳定归并排序Onlogn Onlogn011稳定基数排序Odn OdnOrd稳定
2.给定一组序列,按照一种排序方法写出排序过程(参看实验内容完成)
3.文字描述插入排序、交换排序、选择排序、归并排序方法的思想。