![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
还剩4页未读,继续阅读
文本内容:
数据结构与算法期末复习题3班级学号姓名
一、选择题《在每小题餐选答案中选一个最佳答案共15小题,每小题2分,共30分I、数据结构是D.A、-种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在•种或多种特定关系的数据元素的篥合
2、在线性表的下列运算中不改变数据元素之间结构关系的运尊是D.A插入B.删除C.排序D、查找
3、城性表果用鞋式存砧时其地址D.A.必须是连续的B、一定是不连续的C部分地址必须连续D.连续与否均可以
4、若进栈序列为123456且进栈和出筏可以穿插进行则,能出现的出栈序列为B.A、
32.6L
4.5B、342I.6,5C、L
2.
5.
3.
4.6D、
5.
6.
4.
2.
3.I
5、栈和队列的共同点足CA、都是先进先出B、都是先进后出C、只允许在端点处插入和州除元素D、没有共同点
6.在一个链队列中假定from和rear分别为头指针和尾指针删除个结点的操作是A.A、front=front-ncxB、rcar=rcar-ncxC、rcar-ncxt=frontD、front-ncxt=rcar
7、一个原序存储线性表的第一个元素的存储地址是90每个元素的长度是
2.则第6个元素的存储地址是B.A.98B100C.102D.
1068、下列排序匏法中某一趟结束后未必能迭出一个元素放在其最终位置上的是〈D.A.堆排序B.日泡排序C.快速排序D.H接插入排序
9、二分衣找要求关键字BA、无序、顺序存储B.t!序、泯序存储C、有序、琏接存储D、无序、链接存储
10、对图的深度优先遍历,类似于对树的哪种电历A.A.先序遍历B、中序遍历C、后序遍历D、层次遍历
11、对某个无向图的铺接矩喝来说.卜列叙逑正偷的矩A.A.第i行上的非零元素个数和第i列上的非零元素个数一定柢等B、矩阵中的非零元素个数等于图中的边数C、第i行与第列上的非零元素的总数等「顶点、,i的度数,D、矩阵中非全军行的行数等于图中的顶点数
12、求下列程序段的时间复杂慢B.i=l whilci=ni=i*3A.CN1B.XnC.On/3D.Xlogxn.已知组待排序的记求关城字初始排列如下
56.
34.
58.
26.
7932.
64.
37.
28.
84.
57.下列选择中C是快速排序一越排序的结果A、
84.
79.
64.
37.
57.
52.5826283456B、28M
52265657583779.
84.MC、
28.X
372652566479.
58.
84.57D、
52.
34.
64.
84.
56.
26.
3757.
58.
2879..在有n个结点的二义树的二义徒表表示中,空指计数为B.A、不定B*n+1C、nDhn-
115、在一个无向图中,所有顶点的度数之和等于图的边数的C倍A、IZ2
二、判断题I*大题共H小题,每小同I分,共10分
1、栈和队列的存储方式既可是顺序方式,也可以是链接方式.T
2.对于棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2个结点.
3、徒表的删除算法很简单因为当删除链中某个结点后.计算机会自动符后续各个单元向前移动.F
4、具有12个结点的完全二叉树有5个度为2的结点T
5、已知一棵树的先序序列和后序序列,一定能唯一构造出该树,F
6、顺序表就构适宜于进行顺序存取.而籁衣适宜于进行随机存取.F
7、一个无向图的连通分砥是其极大的连通了图.T
8、对一个堆按层次遍历不一定能得到一个有序序列.T
9、翎接表可以表示有向图.也可以表示无向图.T
10、哈希衣的装填因子小于
0.5的情况下.冲突可以避免.F
三、算法应用题本大题共5小JB.每小SJK分.共40分
1.已知一探二义树如下请分别写出按先序、中序、后序和层次邈历时得到的结点序列.并将此二叉构转化成森林.
2、已知一个图的邻接表如下面所示1画出该图的图结构形态.4分2根据铝接表分别写出从顶点a出发进行深度优先和广度优先遍历序列“分
3、己如一个放列表如下图所示:012345678910II12其微列函数为h(key户key%13处理冲突的方法为戌性探测再散列法F1答下列问胭1)将关健字
28、
29、
415425、38填入版列表中.(3分)
(2)对我中关键字
28.41和54进行查找时所需进行的比较次数各为多少?(3分3)该曲列表在等概率查找时查找成功的平均杳找长度为多少?(2分》
4、设给定一个权能集合W=
(357911)要求根据给定的权俏集合构造一棵哈夫及树并计算哈夫曼树的带权路径长过WPL
5、用prim算法求F图的最小生成树(从VI出发),写出最小生成树的生成过程,
四、算法分析题(本大d共2小区每小翘5分共10分)
1、简述下列算法实现的功能Ivoidpreorderbiree*TIbiircc♦stacklm:intop;ifT!=NULLop=kstacMtop|=T;while]opOp=stack|topj;up-printf*%d*.p-data;iftp-rchild!=NULL{op++;stackop=p-rchild;ifip-lchild!=NUI.L{op**;stack|op|=p-khild:}I功能是2voidconversionOStacks;incn;SElcmTpcc:initsockfs;printfi*Pleaseinputnumber::$canf%d”.n;whilenpushs.n%8n=n,8;}while!sackempiyspops.c:prinf%d.e:}1功能是:
五、算法设计题(本大JH共I小题,共10分)单链表结点的类犷定义如下lypcdefstructnodeIintdata;structnode4next:IlinkiMxie♦linklisu行一个带头结点的单鞋表.头指针为head.织写一个算法计算所有数据域为不簿于x的姑点的个数(不包括头站点)实现犯法的函数头给定如3填充函数内都,intcountnodclinklistheadintx。
![贤阅信息](/assets/images/honor-2.png)
![贤阅信息](/assets/images/honor-3.png)
![贤阅信息](/assets/images/honor-4.png)