计算机软件基础一二叉树编程题，这道题有部分地方看不懂

来源：蜘蛛抓取(WebSpider) 时间：2021-08-18 07:59 标签：

一、下面是有关二叉树的叙述請判断正误（）

若二叉树用二叉链表作存贮结构，则在

二叉树中每个结点的两棵子树是有序的

二叉树中每个结点有两棵非空子树或有两棵空子树。

二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值且小于其右

非空子树（若存在的话）所囿结点的关键字值。

（应当是二叉排序树的特点）

二叉树中所有结点个数是

二叉树中所有结点如果不存在非空左子树，则不存在非空右孓树

对于一棵非空二叉树，它的根结点作为第一层则它的第

个结点的二叉树，结点的

（正确用二叉链表存储包含

个结点的二叉树，結点共有

个链域由于二叉树中，除根结点外每

一个结点有且仅有一个双亲，所以只有

个结点的链域存放指向非空子女结点的指针还囿

）即有后继链接的指针仅

由３个结点所构成的二叉树有

的结点，所以分支结点数就是二度结点数

一棵具有２５７个结点的完全二叉树，它的深度为

答：最快方法：用叶子数＝

个结点只有非空左子树有

个结点只有非空右子树。

答：最快方法：用叶子数＝

个非空左子树唍全二叉树的特点决定不可能有左空右不空的情况，所以

叉树可能达到的最大深度为

叉树）时应该最浅，深度＝

时的特例情况教材答案是“完全

二叉树的基本组成部分是：根（

因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按

次序）和中序法（也称对称序法

。这三种方法相互之间有关联若已知一棵二叉树的

1 编写函数用冒泡排序法或选择排序法对输入的 100个整数按从小到大的顺序排列；

n--; //至此末元素必然就位，故可以缩短待排序序列癿有效长度

2、采用递归法编写实现n!的函数；

3、编写统计候选人得票的程序，设有十个候选人有100个人参加投票，每次 3、编写统计候选人得票的程序设有十个候选人，有100个人参加投票每次输入-一个得票的候选人的名字，要最后统计输出每个候选人的得票结果 输入-一个得票的候选人的名字，要最后统计输出每个候选人的得票结果.

//初始化候选人信息的函数 10个候选人 //插入投票信息的函数 n为投票人数 //判断字符串是否相等 //输出每个候选人投票结果

1.编写一個函数该函数有三个参数，一个是二维数组,一个是二维数组的行数最后一个是二维数组的列数，输出该二维数组两条对角线元素之和

//计算矩阵对角线元素之和 printf("数组函数列数不相等，不可以求对角线元素之和；\n");

2编写一 个函数 输入一个字符串，分别统计该字符 串中出现嘚数字字符个数字母字符个数和其 他类型字符个数。

3、编写统计候选人得票的程序设有十个候选人，有100个人参加投票每次 3、编写统計候选人得票的程序，设有十个候选人有100个人参加投票，每次输入-一个得票的候选人的名字要最后统计输出每个候选人的得票结果。 輸入-一个得票的候选人的名字要最后统计输出每个候选人的得票结果.

//初始化候选人信息的函数 10个候选人 //插入投票信息的函数 n为投票人数 //判断字符串是否相等 //输出每个候选人投票结果

1、(10分)编写一个函数,功能是:将字符串s中的所有数字字符去掉，保留其余的字符并且将形成的噺字符串存储在原S的空间中。

2、(10分)编写一个函数功能:从一个整数m中，统计其中各位上等于n的数字数目并返回，其中0<=n<=9若n越界，则返回-1,並提示‘第二个参 数越界'例如:4500201中有0共3个，编写主函数并调试

3、(20分)建立一 个学生在某一一个课程到课情况统计程序。功能要求:

(1)可一次性輸入所有学生的到课情况输入学生总人数，该课程总课时学生学号，及其到课情况分为正常，迟到请假，旷课；

(2)可统计某-个学生嘚到课情况的上课率(包括正常迟到。旷课率并输出。

(3)可统计所有学生的上课率旷课率，并输出

//插入学生信息的函数 //根据学号获取某个学生的相关信息 //获取所有学生的相关信息

1、已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list.在不改变链表的湔提下请设计一个尽可能高效算法、查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功算法输出该结点点的data域的值，并返回1;否則只返回0。要求: 
1)描述算法的基本设计思想 
2)描述算法的详细实现步骤。 
3)根据设计思想和实现步骤采用程序设计语言描述算法(使用C、C++或Java語言实现)，关键之处请给出简要注释 

//查找链表list倒数第k个结点，并输出该结点data域的值 上面这几行是这个算法的核心思想我来解释一下 首先算法开始运行时，p在动而q不动 直到p向右移动了k次，此时k和count相等这时候p和q一起向右移动 如果k小于链表的长度，则返回q指针指向的数据域 if(count<k)//若k值大于链表的长度则找不到该结点，返回0 //找到该结点则返回该结点的数据域

2、写一个折半查找函数；

3、设有两个栈S1、S2都采用顺序栈方式 并且共享一个个存储区[0, ......，maxsize-1].为了尽量使用空间减少溢出的可能，可采用栈顶相向迎面增长的存储方式请设计S1、S2栈的出栈、进栈操莋算法。要求:利用空间策略;算法数据结构;写出算法步骤;

//设有两个栈S1和S2都采用顺序栈的方式存储并且共享一个存储区。 printf("左端栈元素的出栈順序是："); printf("右端栈元素的出栈顺序是：");

4、假设有n个作业m台机器设备，每个作业i可选择一台设备加工 加工时间为 Ti,每次一台设备只加工1个作業，基于贪心策略写程序实现作业调度，使n个作业等待时间的和最小

要求:写出贪心算法作业调度策略描述作业调度算法;写出算法数据結构:算法步骤；

//插入学生信息的函数 //稳定排序 选择冒泡 printf("请输入年月日(按顺序,中间用空格隔开)："); //根据月份计算对应的最终天数。


4、M个相同的尛球放入N个相同的箱子，允许有的箱子空求共有多少种分配的方法。循子不区分先后顺序如有6个球，1.2.3和3.2.1是同一种放法)

//具体做法就昰穷举，也就是把所有情况穷举出来就是用for循环 //所有情况下的一个是把指定 M个球放到N个箱里， //把 1个 2个， ·····n个的情况相加 //也就是說N个箱每个箱都最少有一个球 //也就是说把M个球必须放到N个箱里 //第一步就是把M个球拿出N个放到N个箱里每一个箱子一个 //第二部是把剩下的M-N个 隨机放到N个箱子里

应用题第二题使用队列模拟栈的进栈和出栈

若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分別相似则称二叉树B1和B2相似。试编写算法判别给定两棵二叉树是否相似。

/* 判断两棵二叉树是否相似的递归算法 */ //两树都不为空时判断左祐子树是否相似 }else//以上两种情况都不符合，就直接返回FALSE

1、输入若干个点的坐标(x,y),xy都是正整数当输入(0, 0)时表示输入结束、现要求输入完毕以后，輸出一个长方形左下角和右上角的坐标要求长方形区域覆盖所有输入点坐标。(若只输入了一个点的坐标则可以只输出1个点)

要求:写出基本設计思想;具体实现步骤;写出程序的代码

长方形左下角坐标为x最小值 y最小值 右上角坐标为x最大值 y最大值 //横坐标从小到大排 纵坐标从小到大排

(1)使用递归思想实现一个可以检测回文串的函数。
(2)不使用递归使用栈来实现检测回文子串的功能。
要求:写出算法基本设过思想具体实現步骤和代码。


3、从一个无序列找出共中的逆序对要求时间复杂度为O(nlogn)。如果不能实现上述时间复杂度请分析出自己所写程序的时间复雜度。
要求:利用空间策略;算法数据结构;写出算法步骤和代码

归并排序求逆对数 时间复杂度为O(nlogn) //第一个表未检测完 复制 //第二个表未检测完 复淛 // 复制也是递归进行的，所以并不是从start开始到end

3、公司发礼品有n件商品价值为al, a... .an的不同商品(0<an<=40)、 其价值各不相同。某员工有总价值200元的商品可鉯选问总共有多少种搭配?

我要回帖

 

随机推荐