2010级电气工程及自动化、自动化专业《软件技术基础》课程开放式考试试题任课教师：王初阳学号：递交日期：2012/4/23成绩：_____________说明1.开放式考试不仅考察知识，同时考察学生查阅文献的能力；学生可以使用google.百度等搜索引擎，图书馆数字资源，如同方CNKI（中国学术期刊全文数据库）查阅资料，寻找答案和解题思路；2.可以使用各种工具帮助自己解题，可以相互讨论，但是不允许拷贝.复制、剽窃他人结果。如果发现雷同，按雷同人数，每次雷同从成绩中扣除10分。因不存在完美雷同标准，因此将根据批改教师的个人识别，进行雷同确认，因此为避免雷同，请自己设计代码或解题；3.每个编程问题都要首先说明思路，然后给出代码；程序以及求解方法描述的编辑应该美观；程序代码应该有层次缩进，以便阅读；4.每个编程冋题的C/C++代码的每一行必须有清晰的注释，说明改行中变量和语句的作用，如果注释和C/C++语句不符，则视为剽窃；5.可以使用C或C++语言，或者混合C.C++编程；6.每个编程问题要以C/C++函数形式进行解答，并且必须编写调用main函数调用调用该C/C++函数；7.如何测试算法的运行时间，可以参考课件第一讲内容；8.为存档需要，请将答案写在本文档中作答，并将文档打印上交；9.答案上交时间:最后一次上机。试题1•总结和比较线性表、堆栈.队列.二叉树.树.图的各种存储结构，并说明它们是如何使用数组和指针的。（10分）2.斐波那契数列冋题。（1）编写求解斐波那契数列中第n个数的递归和非递归c/c++函数；（2）编写main®数,测试n二｛10,20,30,40,50｝时，上述递归和非递归c/c++函数的执行时间。（10分）3.括号匹配冋题。（1）编写C/C++函数，验证一个字符串形式的表达式中的括号是否匹配，其中括号包括圆括号.方括号和花括号。（2）编写main函数从键盘读入表达式，并调用你编写的函数。（10分）4.排序问题。（1）编写简单插入排序和基于二分查找的插入排序算法的c/c++函数；（2）设待排序数据个数为n,为每个n设计10个随机实例，然后测试当n大于多少时，二基于二分查找的插入排序的平均运行时间比简单插入排序算法的平均运行时间少四分之一。平均运行时间指对每个n的10个随机实例上的运行时间的平均值。（15分）5.二叉树的层次遍历。设二叉树的存储结构为二叉链表，数据元素类型为整数,（1）编写二叉树前序建立二叉树的c/c++函数；（2）编写该二叉树的层次遍历的代码；（3）编写main函数，从文件读入二叉树的前序序列，建立二叉树,并输出层次遍历序列。（15分）6.树的层次遍历一。设树的存储结构为孩子链表，数据元素类型为整数，（1）编写建立树的c/c++函数；（2）编写该树的层次遍历的代码；（3）编写main函数，从文件读入并建立树，并输出层次遍历序列。（20分）7.完全二叉树的存储结构变换。给定一个数组存储的完全二叉树，（1）编写C/C++函数将完全二叉树的数组存储结构转换为二叉链表；（2）编写main函验证你的转换函数。（20分）—效卑-总结：①线性表是一种线性结构，数据元素在线性表的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。线性表在计算机中的存储结构是顺序存储结构。线性表中所有元素所占的存储空间是连续的。线性表中各数据元素的存储空间中是按顺序依次存放的，所以在线性表的顺序存储结构中其前后件连个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。②栈是一种线性表，所以栈的存储结构也是顺序存储结构。在栈中，插入与删除都只是在线性表的一端进行，另一端是封闭的不允许进行插入与删除，允许进行插入与删除的一端称为栈顶，不允许进行插入与删除的一端称为栈底。栈顶元素是最后被插入的也是最先被删除的元素;栈底元素是最先被插入的也是最后被删除的元素。栈是按照“先进后出”的原则组织数据的。③队列要求加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出元素。所以队列是“先进先出”“后进后出”的线性表。④树是一种简单的非线性结构。在树这种数据结构中，所有数据结构元素之间的关系具有明显的层次特性。⑤二叉树是一种很有用的非线性结构，采用链式存储结构。⑥图的数据节点之间...