《软件技术基础》课程开放式考试试题。
任课教师：王初阳
姓名：_杨向龙。
学号：__100611234___
递交日期：_2023年4月23日_
成绩。1.总结和比较线性表、堆栈、队列、二叉树、树、图的各种存储结构，并说明它们是如何使用数组和指针的。(10分)
答：（1）.线性表：
一般常用顺序存储和链式存储。顺序存储的特点：在逻辑上相邻的数据元素，它们的物理位置也是邻接的，即线性关系利用物理上的相邻关系随机存取元素，容易实现来体现插入和删除结点。
但由于表中的结点是依次连续存放的，所以插入和删除一个结点时，必须将插入点和删除点以后的结点向后或向前依次移动；扩展不灵活，建立表时，若估计不到表的最大长度，就难以确定分配的空间，影响扩展；容易造成浪费分配的空间过大时，会造成预留空间浪费。链式存储的特点：用一组任意的存储单元存储线性表的数据元任利用指针，利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素，每个数据元素除存储本身信息外，还需存、储其直接后继的信息、结点、数据域、指针域。
一般定义一个一维数组来表示线性表的顺序储存结构的，链式存储需要指针域，需要用到头指针，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 是指向链表中第一个结点，是在链表的首元结点之前附设的一个结点。
2).堆栈：分顺序栈和链式栈，其用一维数组存储栈为顺序栈，链式栈的栈顶指针top指示的结点，是栈顶元素，堆栈的栈底元素师单链表的尾结点。
3).队列：可以采用顺序存储和链接存储，也是用一维数组存储队列，顺序队列容易造成浪费。链式队列是使头指针front指向队头结点，队尾指针rear指向队尾结点。
4).二叉树； 分顺序存储和链式存储，一般不宜采用顺序表示，一颗又n个结点的二叉树中，除根节点外其余每个结点均有一个出自某个指针域的指针指向该结点。
5).树： 包括n个结点的有限非空集合t，其中，一个特定的结点r称为根，其余的化成不同的子集，每个子集都是树，树称为树根r的子树，树具有层次结构的，树也可以用一维数组的，通过指针来分支的。
6).图； 林洁矩阵和关联矩阵树图的两种矩阵表示法，邻接矩阵表示一个图中顶点间的相邻接关系，关联矩阵表示图中边与顶点相关联的矩阵，最常用二位数组，释放一维指针数组。
2.斐波那契数列问题。(1) 编写求解斐波那契数列中第n个数的递归和非递归c/c++函数；(2)编写main函数，测试n=时，上述递归和非递归c/c++函数的执行时间。(10分)
答：(1).斐波那契数列的递归算法。
int fibonacci(int n)//函数名字。
if(n<=1)//当n的值小于2时返回。
return 1；//返回1
return fibonacci(n-1)+fibonacci(n-2);/返回两者之和。
斐波那契数列的非递归算法。
int fibonacci(int n)//函数名字。
long int f3,f1=1,f2=1,i; /定义所需的变量。
for(i=2;i<=n;i++)用for循环实现非递推，求出值。
f3=f2+f1;//f3为二者之和。
f1=f2;//把f2的值赋给f1
f2=f3;//把f3的值赋给f2
return f3;//返回斐波那契数列的值。
2).递归的main（）函数。
#include ""
#include<>
int fibonacci(int n)//函数名字。
if(n<=1)//当n的值小于2时返回。
return 1；//返回1
return fibonacci(n-1)+fibonacci(n-2);/返回两者之和。
void main()
int n,t;//定义所需的变量。
int start,finish;//定义所需的变量。
printf("请输入n:")输入需要球的数字。
scanf("%d",&n);/输入n
start=(int)clock();时间开始的时刻。
printf("%d",fibonacci(n));输出斐波那契数列的值。
finish=(int)clock();时间结束的时刻。
t=finish-start;//程序运行所需要的时间。
printf("");换行。
printf("%dms",t);/输出程序运行的时间。
非递归的main（）函数。
#include ""
int fibonacci(int n)//函数名字。
long int f3,f1=1,f2=1,i; /定义所需的变量。
for(i=2;i<=n;i++)用for循环实现非递推，求出值。
f3=f2+f1;//f3为二者之和。
f1=f2;//把f2的值赋给f1
f2=f3;//把f3的值赋给f2
return f3;//返回斐波那契数列的值。
void main()
int n,t;//定义所需的变量。
int start,finish;//定义所需的变量。
printf("请输入n:")输入需要球的数字。
scanf("%d",&n);/输入n
start=(int)clock();时间开始的时刻。
printf("%d",fibonacci(n));输出斐波那契数列的值。
finish=(int)clock();时间结束的时刻。
t=finish-start;//程序运行所需要的时间。
printf("");换行。
printf("%dms",t);/输出程序运行的时间。
3.括号匹配问题。(1) 编写c/c++函数，验证一个字符串形式的表达式中的括号是否匹配，其中括号包括圆括号、方括号和花括号。
(2) 编写main函数从键盘读入表达式，并调用你编写的函数。(10分)
答：（1）.括号匹配函数。
# define maxsize 100//定义maxsize为100
int match(char *exps)//定义函数名。
char st[maxsize];/申请一个容量为100的数组。
int top=0,i=0;//定义变量，并赋值。
int nomatch=0;//定义变量，并赋值。
while(exps[i]!=0'&&nomatch==0)//当字符没读完的时候而且nomatch为0时执行下列循环。
switch(exps[i])/当前字符。
':if(exps[top-1]==
i++;i的值加1
if(nomatch==0&&top==0)//如果nomatch的值和top的值为0
return 1;//返回值为1
elsereturn 0;//返回值为0
2）.main（）函数（只输入括号）
#include<>
# define maxsize 100//定义maxsize为100
int match(char *exps)//定义函数名。
char st[maxsize];/申请一个容量为100的数组。
int top=0,i=0;//定义变量，并赋值。
int nomatch=0;//定义变量，并赋值。
while(exps[i]!=0'&&nomatch==0)//当字符没读完的时候而且nomatch为0时执行下列循环。
switch(exps[i])/当前字符。
':if(exps[top-1]==
i++;i的值加1
if(nomatch==0&&top==0)//如果nomatch的值和top的值为0
return 1;//返回值为1
elsereturn 0;//返回值为0
void main()
4.排序问题。(1) 编写简单插入排序和基于二分查找的插入排序算法的c/c++函数；(2)设待排序数据个数为n，为每个n设计10个随机实例，然后测试当n大于多少时，二基于二分查找的插入排序的平均运行时间比简单插入排序算法的平均运行时间少四分之一。
平均运行时间指对每个n的10个随机实例上的运行时间的平均值。(15分)
自动化专业导论
前言 自动化这个属于已广为人知。生产生活的各个领域都涉及到了它，工业自动化，农业自动化，服务自动化，各种自动化设备在日常生活已随处可见。自动化已经成为一门独立的学科。自动化其英译名为 automation或automatization 是指机械设备 系统或过程 生产 管理过程 在没有人或较少人的直接...
自动化专业导论
学校 专业年级 姓名 摘要 随着21世纪经济的快速发展，科学技术的革新也日新月异，自动化技术也日趋成熟，应用领域也更加广泛，应用前景大好。人们也力求使生产发展变得更加快捷准确，处理过程更加自动一体化，减少人力劳动。本文主要介绍进行了自动化专业导论学习后对本专业的认识和感悟和发展。关键字 快捷准确 自...
自动化专业导论
自动化基本问题及应用。自动化是一门交叉学科，而随着信息技术的发展，不管是自动化技术还是自动化理念都已渗入了社会的各个领域，如国防，工业，办公，甚至是家用。而这种渗透还将继续，自动化应用的广度已无需再多加说明，正如大家所看到的，目前自动化已能应用到几乎所有领域而毫无违和感。自动化技术是一门综合性技术，...