论文网
关于数据结构论文范本,与计算机科学47相关论文格式范文
本论文是一篇关于数据结构论文格式范文,关于计算机科学47相关毕业论文的格式范文。免费优秀的关于数据结构及算法及结点方面论文范文资料,适合数据结构论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
)%mB.(rear-front+1)%mC.(front-rear+m)%mD.(rear-front+m)%m
二,判断题判断下列各个叙述的正误.对,在题号前的括号内填入"(",错,在题号前的括号内填入"(".
()1.算法的运行时间涉及加,减,乘,除,转移,存,取等基本运算.要想准确地计算总运算时间是不可行的.
()2.二维数组是数组元素为一维数组的线性表,因此二维数组元素之间是线性结构.
()3.顺序表用一维数组作为存储结构,因此顺序表是一维数组.
()4.通常使用两个类来协同表示单链表,即链表的结点类和链表类.
()5.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同.
()6.在使用后缀表示实现计算器类时用到一个栈类的实例,其作用是暂存运算对象.
()7.具有n个结点的完全二叉树的高度为(log2n(+1.(n(0,根在第0层)
()8.为度量一个搜索算法的效率,需要在时间和空间两个方面进行分析.
()9.闭散列法通常比开散列法时间效率更高.
()10.一棵m阶B树中每个结点最多有m个关键码,最少有2个关键码.
三,填空题把合适的内容添到横线上.
1.对于一个单链接存储的线性表,假定表头指针指向链表的第一个结点,则在表头插入结点的时间复杂度为________,在表尾插入结点的时间复杂度为________.
2.假定一棵三叉树(即度为3的树)的结点个数为50,则它的最小高度为________,假定树根结点为第0层.
3.一棵高度(假定树根结点为第0层)为4的完全二叉树中的结点数最少为________个,最多为________个.
4.在一个具有n个顶点的无向图中,要连通所有顶点则至少需要________条边.
5.从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时,其查找长度分别为________和________.
6.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个________.
7.在开散列表中,处理冲突的方法为________法,在闭散列表中,处理冲突的方法为____________法.
8.在堆排序的过程中,对任一分支结点进行筛运算(即调整为子堆的过程)的时间复杂度为________,整个堆排序过程的时间复杂度为________.
9.快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为________.
10.在二路归并排序中,对n个记录进行归并的趟数为________.
四,运算题
1.假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d),分别写出先根,后根,按层遍历的结果.
先根:
后根:
按层:
2.若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},从顶点A开始分别对该图进行深度优先搜索和广度优先搜索,要求顶点值小的邻接点被优先访问,则写出得到的深度优先搜索和广度优先搜索的顶点序列.
深度优先搜索得到的顶点序列:
广度优先搜索得到的顶点序列:
3.已知一个二叉搜索树的广义表表示为38(25(16),52(,74(68(,72),90))),在下表中填写出每个元素的比较次数.
12345678
3825521674689072
4.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探测法处理冲突,试求出每一元素在闭散列表中的初始散列地址和最终散列地址,画出最后得到的散列表,求出平均查找长度.
12345678910
元素32752963489425461870
初始散列地址
最终散列地址
0123456789101112
散列表
平均查找长度:
5.已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每一趟的排序结果.
五,算法分析题
1.给出下列每个递归过程的执行结果.
(1)voidunknown(intw){
if(w){
unknown(w-1),
for(inti等于1,i<,等于w,i++)cout<,<,w,
cout<,<,endl,
}
}
调用语句为unknown(4).
(2)voidunknown(intn){
cout<,<,n%10,
if(n/10)unknown(n/10),
}
调用语句为unknown(582).
(3)intunknown(intm){
intvalue,
if(！m)value等于3,
elsevalue等于unknown(m-1)+5,
returnvalue,
}
执行语句为cout<,<,unknown(3).
2.请写出下面算法的功能,其中Stack表示栈类,Queue表示队列类.
voidunknown(Queue&,Q)
{
StackS,intd,
S.InitStack(),//初始化S为空栈
while(！Q.IsEmpty()){//队列Q不为空则循环
Q.DeQueue(d),//出队列元素的值由变量d带回
S.Push(d),//d的值压入S栈
}
while(！S.IsEmpty()){//栈S不为空则循环
S.Pop(d),//出栈元素的值由变量d带回
Q.EnQueue(d),//d的值插入队列Q中
}
}
算法功能:
3.假定btnode为二叉树中的结点类型,它含有数值域data,左指针域lchild和右指针域rchild,下面函数中的参数BT指向一棵二叉树的树根结点,X为给定元素,请给出该函数的功能.
btnode*AAA(btnode*BT,datatypeX)
{
if(BT等于等于NULL)returnNULL,
else{
if(BT->,data等于等于X)returnBT,//返回值为X结点的指针
else{
btnode*mt,
if(mt等于AAA(BT->,lchild,X))returnmt,
elseif(mt等于AAA(BT->,rchild,X))returnmt,
elsereturnNULL,
}
}
}
六,算法设计题
1.设计一个算法,从树根指针为rbitreptr的二叉树中删除结点值为x的子树,若删除成功则返回1,否则返回0.假定在算法中不要求回收被删除子树中的所有街道,算法中的bitreptr为结点指针类型,所指结点类型包含三个域,即值域data,左指针域lchild和右指针域rchild.
intdeleteSubtree(bitreptr&,r,datatypex),
2.已知二叉搜索树中的结点类型用BtreeNode表示,被定义为:
structBtreeNode{ElemTypedata,BtreeNode*left,*right,},
其中data为结点值域,left和right分别为指向左,右孩子结点的指针域.假定具有BtreeNode*类型的指针参数BST指向一棵二叉搜索树的根结点,试根据下面的函数声明编写一个非递归算法,向BST树中插入值为item的结点,若树中不存在item结点则进行插入并返回1表示插入成功,若树中已存在item结点则不插入并返回0表示插入失败.
intInsert(BTreeNode*&,BST,constElemType&,item),
参考解答
一,单选题:
1.C2.D3.D4.D5.B6.B7.C8.A9.C10.D
二,判断题
1.(2.(3.(4.(5.(6.(7.(8.(9.(10.(
三,填空题
1.O(1)O(n)
2.4
3.1631
4.n-1
5.13
6.有序序列
7.链接开放定址
8.O(log2n)O(nlog2n)
9.O(nlog2n)O(n2)
10.(log2n(
四,运算题
1.先根:a,b,e,c,f,h,i,j,g,d,
后根:e,b,h,i,j,f,g,c,d,a,
按层:a,b,c,d,e,f,g,h,i,j
2.深度优先搜索&#
关于数据结构论文范本,与计算机科学47相关论文格式范文参考文献资料：