《软件技术基础》开放式考试试题.docx

《软件技术基础》开放式考试试题.docx

《《软件技术基础》开放式考试试题.docx》由会员分享，可在线阅读，更多相关《《软件技术基础》开放式考试试题.docx（10页珍藏版）》请在冰点文库上搜索。

《软件技术基础》开放式考试试题

2010级电气工程及自动化、自动化专业

《软件技术基础》课程开放式考试试题

任课教师：

王初阳

姓名：

学号：

递交日期：

2012/4/23

成绩：

说明

1.开放式考试不仅考察知识，同时考察学生查阅文献的能力；学生可以使用google、XX等搜索引擎，图书馆数字资源，如同方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分）

完全二叉树的存储结构变换。

给定一个数组存储的完全二叉树，

（1）编写c/c++函数将完全二叉树的数组存储结构转换为二叉链表;

（2）编写main函验证你的转换函数。

（20分）

一．答案：

总结：

线性表是一种线性结构，数据元素在线性表的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。

线性表在计算机中的存储结构是顺序存储结构。

线性表中所有元素所占的存储空间是连续的。

线性表中各数据元素的存储空间中是按顺序依次存放的，所以在线性表的顺序存储结构中其前后件连个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

栈是一种线性表，所以栈的存储结构也是顺序存储结构。

在栈中，插入与删除都只是在线性表的一端进行，另一端是封闭的不允许进行插入与删除，允许进行插入与删除的一端称为栈顶，不允许进行插入与删除的一端称为栈底。

栈顶元素是最后被插入的也是最先被删除的元素；栈底元素是最先被插入的也是最后被删除的元素。

栈是按照“先进后出”的原则组织数据的。

队列要求加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出元素。

所以队列是“先进先出”“后进后出”的线性表。

树是一种简单的非线性结构。

在树这种数据结构中，所有数据结构元素之间的关系具有明显的层次特性。

二叉树是一种很有用的非线性结构，采用链式存储结构。

图的数据节点之间的联系是任意的。

比较：

线性表，堆栈，队列是线性结构，存储结构是线性存储结构。

树和二叉树是非线性表，存储结构是非线性存储结构。

图是比线性表，树与二叉树更为复杂的一种数据结构。

（2）在线性表中插入一个元素需要在线性表中第i个元素之前插入一个新元素时首先要从最后一个元素（n）开始，直到第i个元素之间共n-i+1个元素向后移动一个位置，移动结束后。

第i个位置就被空出，然后将新元素插入就行了!

要删除第i个元素时则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。

栈是用一维数组S（1:

m）作为栈的顺序存储空间，栈底指针指向栈空间的低地址一端，通常用S（bottom）为栈底元素，S（top）为栈顶元素。

入栈时当占空间不满时栈顶指针进一（top+1）反之则出现“上溢”错误。

退栈时栈顶元素退一（top减1），如为空时出现“下溢”错误。

队列用一维数组作为队列的顺序存储空间，在循环队列中用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，循环队列的初始状态为空，即rear=front=m,每进行一次入队运算，队尾指针就进一。

当队尾指针rear=m+1时，则置rear=1。

每进行一次退栈运算，排头指针就进一，当排头指针front=m+1时，则置front=1.树在计算机中通常用多重链表表示，多重链表中的每个结点描述了书中对应结点的信息，而每个结点的链域个数将随树中该结点的度而定。

二叉树的链式存储结构分为两部分，数据域和指针域，在二叉树中，由于每个元素可以有两个后件，因此，用于存储二叉树的存储结点的指针域有两个，一个用于指向该节点的左子节点的存储空间，另一个用于指向该结点的右子结点的存储空间。

图是用邻接表来实现的，用一个顺序存储空间来存储图中各结点的信息，该顺序存储空间中的每一个存储结点有两个域：

数据域date与指针域link,date用于存放各结点的信息，指针域用与链接相应结点的的后件。

其次，对于图中每一个结点构成的单链表。

该单链表的头指针即为顺序空间中的对应存储结点的指针域。

单链表中的num域用于存放图中某个节点的编号，val域用于存放编号为num结点的前件到num结点之间的求值函数值f.如果不是有值图，则val域可以不要；next域用于指向与num结点是同一个前件的另一个后件信息的特点。

二.

（1）斐波那契数列中第n个数的递归和非递归c函数：

#include

voidmain（）

{

inta[n];

inti;

a[0]=1;

a[1]=1;

scanf（"%d",&n）;

for（i=2;i

a[i]=a[i-1]+a[i-2];

printf（"%12d",a[i]）;

}

五．

（1）二叉树前序建立二叉树的c++函数：

#include

usingnamespacestd;

//定义二叉链表结构类型

template

structBtnode

{Td;//数据域

Btonde*lchild;//左指针域

Btonde*rchild;//右指针域

}；

//二叉链表类

template//类模板，T为虚拟类型

classBinary_Tree

{private:

Btnode*BT;//二叉链表根节点指针

public:

//成员函数

Binary_Tree（）{BT=NULL;return;}//二叉链表初始化

viodcreat_Binary_Tree（T）;//生成二叉链表

voidpretrav_Binary_Tree（）;//前序遍历二叉链表

//生成二叉链表

template

voidBinary_Tree:

:

creat_Binary_Tree（Tend）

{Btnode*P;

Tx;

cin>>x;//输出第一个结点值

if（x==end）return;//第一个值为结束符值

p=newBtnode;//申请二叉链表根结点

p->d=x;p->lchild=NULL;p->rchild=NULL;

BT=P;//二叉树根结点

creat（p,1,end）;//输出左子结点值

creat（p,2,end）;//输出右子结点值

return;

}

template

staticcreat（Btnode*p,intk,Tend）

{Btnode*q;

Tx;

cin>>x;//输出结点值

if（x!

=end）//结点值为非结束符值

{q=newBtnode;//申请一个二叉链表结点

q->d=x;q->lchild=NULL;q->rchild=NULL;

if（k==1）p->lchild=q;//链接到左子树

if（k==2）p->rchild=q;//链接到右子树

creat（q,1,end）;//输出左子结点值

creat（q,2,end）;//输出右子结点值

}

return0;

}

//前序遍历二叉链表

template

voidBinary_Tree:

:

pretrav_Binary_Tree（）

{Btnode*p;

p=BT;

pretrav（p）;//从根结点开始前序遍历

cout<

return;

}

template

staticpretrav（Btnode*P）

{if（p!

=NULL）

{cout<d<<"";//输出根结点

pretrav（p->lchild）;//前序遍历左子树

pretrav（p->rchild）;//前序遍历右子树

}

return0;

}

（2）二叉树的层次遍历的代码：

//前序遍历二叉链表

template

voidBinary_Tree:

:

pretrav_Binary_Tree（）

{Btnode*p;

p=BT;

pretrav（p）;//从根结点开始前序遍历

cout<

return;

}

template

staticpretrav（Btnode*P）

{if（p!

=NULL）

{cout<d<<"";//输出根结点

pretrav（p->lchild）;//前序遍历左子树

pretrav（p->rchild）;//前序遍历右子树

}

return0;

}

//中序遍历二叉链表

template

voidBinary_Tree:

:

intrav_Binary_Tree（）

{Btnode*p;

p=BT;

intrav（p）;//从根结点开始中序遍历

cout<

return;

}

template

staticintrav（Btnode*p）

{if（p!

=NULL）

{intrav（p->lchild）;//中序遍历左子树

cout<d<<"";//输出根结点

intrav（p->rchild）;//中序遍历右子树

}

return0；

}

//后序遍历二叉链表

template

voidBinary_Tree:

:

postrav_Binary_Tree（）

{Btnode*P;

P=BT;

postrav（p）;//从根结点开始后序遍历

cout<

return;

}

template

staticpostrav（Btnode*P）

{if（p!

=NULL）

{postrav（p->lchild）;//后序遍历左子树

postrav（p->rchild）;//后序遍历右子树

cout<d<<"";//输出根节点值

}

return0；

}

（3）main函数如下：

#include"Binary_Tree.h"

intmain（）

{Binary_Treeb;//建立一个二叉树对象b,数据域为整型

cout<<"输出个结点值（-1为结束符值）:

"<

b.creat_Binary_Tree（-1）;//从键盘输入二叉树各结点值，以-1作为结束值

cout<<"前序序列:

"<

b.pretrav_Binary_Tree（）;//前序遍历二叉树对象b

cout<<"中序序列:

"<

b.intrav_Binary_Tree（）;//中序遍历二叉树对象b

cout<<"后序序列;"<

b.postrav_Binary_Tree（）;//后序遍历二叉树对象b

return0;

}