西安科技大学
2013年硕士研究生入学考试试题A
───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计
考生须知：
1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。
2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。
3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。
4、 试题要随答题纸一起交回。
一、单项选择题（每小题2分，共30分）
（1）并归排序的时间复杂度是（ ）。
A ．O(n 2)
B ．O(nlog 2n)
C ．O(n)
D ．O(log 2n)
（2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。
A ．单链表
B ．单循环链表
C ．带尾指针的单循环链表
D ．带头结点的双循环链表
（3）散列文件是一种（ ）。
A ．顺序文件
B ．索引文件
C ．链接文件
D ．计算机寻址文件
（4）常用于函数调用的数据结构是（ ）。
A ．栈
B ．队列
C ．数组
D ．链表
（5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。
A ．O(n 2)
B ．O(s 2)
C ．O(msn)
D ．O(mn)
（6）图的广度优先搜索遍历使用的数据结构是（ ）。
A ．栈
B ．队列
C ．集合
D ．树
（7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。
A ．直接前驱
B ．直接后继
C ．开始结点
D ．终端结点
（8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。
A ．O(n 2)
B ．O(1)
C ．O(n)
D ．O(log 2n)
（9）在链队列中执行入队操作，（ ）。
A ．需判断队是否为空
B ．限定在链表头p 进行
C ．需判断队是否为满
D ．限定在链表尾p 进行
（10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。
A ．（70，83，62，95）
B ．（70，62，83，95）
C．（62，70，83，95）D．（83，62，70，95）
（11）下列选项中与数据的存储结构无关的术语是（）。
A．栈B．链队列C．顺序表D．链表
（12）已知循环队列的存贮空间大小为m，对头指针front指向对头元素，对尾指针rear 指向对尾元素的下一个位置，则向对列中插入新元素时，修改指针的操作是（）。
A．rear=（rear-1）％m B．rear=（rear+1）％m
C．front=（front-1）％m D．front=（front+1）％m
（13）对于广义表A，若head(A) =tail(A)，则A为（）。
A．(( )) B．( ) C．(( ),( )) D．(( ),( ),( ))
（14）若一棵具有n个结点的二叉树的先序遍历和后序遍历的次序正好相反，则该二叉树应是（）。
A．结点均无左孩子的二叉树B．高度为n的二叉树
C．结点均无右孩子的二叉树D．存在度为2的结点的二叉树
（15）平均时间复杂度为O(nlog2n)的稳定排序算法是（）。
A．快速排序B．堆排序C．归并排序D．冒泡排序
二、填空题（每小题2分，共20分）
（1）数据结构由数据的逻辑结构、存贮结构和数据的三部分组成。
（2）广义表A=(a, b, (c, d, (e, f )), G)的长度为。
（3）以数据集{25,4,15,5,1}为权值构造一棵哈夫曼树，其带权路径长度为。（4）在高度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是。
（5）若某哈夫曼树有m个叶子结点，则该哈夫曼树共有个结点。
（6）向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和操作。
（7）在队列中，允许插入的一端称为。
（8）在一棵二叉树中，度为1的结点数是3，度为2的结点数是4，则该二叉树有个叶子结点。
（9）具有n个顶点的连通无向图，其生成树有条边。
（10）当关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序算法中，运行效率最高的是。
三、简答题（任选5道题，每小题8分，共40分）
（1）什么是线性表？通常有哪些存贮方式？其各自的优缺点是什么？
（2）什么是顺序队列的“假溢出”现象？有哪些处理方式？如何判断队满和队空？（3）什么是二叉树的顺序存储方式？其优缺点有哪些？
（4）图的存储结构有哪些？其各自的优缺点是什么？
（5）静态查找有哪三种方法？各自的查找效率如何？
（6）什么样的图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复杂度各为多少？他们分别适合于哪种类型的图？
四、应用题（每小题10分，共40分）
（1）已知待排序记录的关键字序列为{25,96,11,63,57,78,44}，请回答下列问题：（a）画出堆排序的初始堆（大根堆）；
（b）画出第2次重建堆之后的堆。
（2）已知关键字序列为{56,23,41,79,38,62,18}，用散列函数H(key)=key％11将其散列到散列表HT[0…10]中，采用线性探测法处理冲突，请回答下列问题：
（a）画出散列存储后的散列表；
（b）求在等概率下查找成功的平均查找长度。
（3）已知某二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，请回答下列问题：
（a）画出此二叉排序树；
（b）若将此二叉排序树看作森林的二叉链表存储，画出对应的森林。
（4）下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。请回答下列问题：
（a）画出该带权有向图的图形；
（b）从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；
（c）以顶点V1为起点的深度优先遍历的顶点序列及对应的生成树；
（d）由顶点V1到顶点V3的最短路径。
(顶点边)（出边表）
2
3
4
5
6
五、算法设计题（任选2题，每小题10分，共20分）
（1）假定二叉树结点的存储结构定义如下：
typedef struct node
{ char data；
struct node *lchild；
struct node *rchild；
}NODE；
试编写C（或Java）语言函数void exchange(NODE *t )，其功能是交换二叉树的各结点的左右子树（根结点指针为t）。
（2）以二叉链表为存储结构，编写按层次顺序（同一层自左至右）遍历二叉树的算法。（3）给定头指针为ha的单链表A，和头指针为hb的递增有序单链表B。试利用表A和表B的结点，将表A和表B归并为递增有序单链表C，其头指针为hc（允许有相同的data值，表A、B、C均带有头结点）。
阅读下面的函数merge（），请给有下划线的位置填空，使之成为完整的算法（程序）。
表结点的类型定义如下：
struct node { int data;
struct node *next; } ;
C语言算法如下：
void merge(struct node *ha, struct node *hb, struct node *hc)
{
struct node *pc, *qc, *pa, *fa;
int search;
hc=hb;
hb=NULL;
pa=ha->next;
free(ha);
while(pa)
{
pc=hc;
qc=hc->next;
search=1; //设置查找标志
while(qc&&search)
{
if(pa->data<=qc->data) ①;
else
{ pc=qc;
qc= ②; }
}
fa= ③;
pa= ④;
fa->next= ⑤;
⑥;
}
}
算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj
《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的
按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
超市POS管理系统 数据库设计 数据库在一个信息管理系统中占有非常重要的地位，数据库结构的设计好坏将直接对应用系统的效率以及实现的效果产生影响。数据库设计一般包括以下四个部分：数据库需求分析、数据库概念结构设计、数据库逻辑结构设计、数据库物理结构实现。 一、数据库需求分析 通过对超市管理工作过程的内容和数据流图分析，设计如下面的数据项和数据结构。 1、员工信息，包括的数据项有：员工编号，姓名，性别，职务，口令，权限级别、身份证号，所属部门编号等。 2、部门信息，包括的数据项有：部门编号，部门名称。 3、供应商信息，包括的数据项有：供应商编号，供应商名称，地址，邮政编码，电话号码，税号，银行帐号，开户银行，联系人，备注等。 4、会员信息，包括的数据项有：会员编号，姓名，性别，身份证号，消费总金额，积分等。 5、入库信息，包括的数据项有：入库编号，入库日期，商品编号，计量单位，入库价格，销售价格，数量，总金额，供应商编号，业务员编号等。 6、商品信息，包括的数据项有：商品编号，所属类别，数量，单价，商品名称等。 7、销售出货单主信息，包括的数据项有：销售日期，总金额，是否现金，是否会员，会员编号、收银号编号等。 8、销售出货单子信息，包括的数据项有：商品编号，数量，单价，折扣比例，金额等。 二、数据库概念结构设计 根据上面设计规划出的实体，我们对各个实体具体的描述E-R图如下：
图1 员工信息E-R图 图2 部门信息E-R图 图3 入库信息E-R图 图4 商品信息E-R图
图5 销售出货单主信息E-R图 图6 销售出货单子信息E-R图 图7 会员信息E-R图 图8 供应商信息E-R图
西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95）
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人
算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸
课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下：
#include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 数据库课程设计题目16个经典实例 1.机票预定信息系统 系统功能的基本要求： 航班基本信息的录入，包括航班的编号、飞机名称、机舱等级等。机票信息，包括票价、折扣、当前预售状态及经手业务员等。客户基本信息，包括姓名、联系方式、证件及号码、付款情况等。按照一定条件查询、统计符合条件的航班、机票等；对结果打印输出。 2.长途汽车信息管理系统 系统功能的基本要求： 线路信息，包括出发地、目的地、出发时间、所需时间等。汽车信息：包括汽车的种类及相应的票价、最大载客量等。票价信息：包括售票情况、查询、打印相应的信息。 3.人事信息管理系统 系统功能基本要求： 员工各种信息：包括员工的基本信息，如编号、姓名、性别、学历、所属部门、毕业院校、健康情况、职称、职务、奖惩等；员工各种信息的修改；对转出、辞退、退休员工信息的删除；按照一定条件，查询、统计符合条件的员工信息；教师教学信息的录入：教师编号、姓名、课程编号、课程名称、课程时数、学分、课程性质等。科研信息的录入：教师编号、研究方向、课题研究情况、专利、论文及著作发表情况等。按条件查询、统计，结果打印输出。 4.超市会员管理系统 系统功能的基本要求： 加入会员的基本信息，包括：成为会员的基本条件、优惠政策、优惠时间等。会员的基本信息，包括姓名、性别、年龄、工作单位、联系方式等。会员购物信息：购买物品编号、物品名称、所属种类，数量，价格等。会员返利信息,包括会员积分的情况，享受优惠的等级等。对货物流量及消费人群进行统计输出。 5.客房管理系统 系统功能的基本要求： 客房各种信息，包括客房的类别、当前的状态、负责人等；客房信息的查询和修改，包括按房间号查询住宿情况、按客户信息查询房间状态等。以及退房、订房、换房等信息的修改。对查询、统计结果打印输出。 6.药品存销信息管理系统 系统功能基本要求 药品信息，包括药品编号、药品名称、生产厂家、生产日期、保质期、用途、价格、数量、经手人等；员工信息，包括员工编号、姓名、性别、年龄、学历、职务等；客户信息，包括客户编号、姓名、联系方式、购买时间、购买药品编号、名称、数量等。入库和出库信息，包括当前库存信息、药品存放位置、入库数量和出库数量的统计。 1.什么是软件测试 使用人工和自动手段来运行或测试某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差异 2.软件测试的目的是什么 软件测试的目的在于发现错误；一个好的测试用例在于发现从前未发现的错误；一个成功的测试是发现了从前未发现的错误的测试。 3.软件测试的目标 软件测试以检验是否满足需求为目标。 4.什么是软件缺陷 满足下列五个规则之一才称为软件缺陷： 1）软件未达到产品说明书标明的功能。 2）软件出现了产品说明书指明不会出现的错误。 3）软件功能超出产品说明书指明的范围。 4）软件未达到产品说明书虽未指出但应该达到的目标。 5）软件测试人员认为软件难以理解、不易使用、运行速度缓慢，或者最终用户认为不好。 5.什么黑盒测试 黑盒测试是把测试对象看做一个黑盒子，测试人员完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。因此黑盒测试又叫功能测试或数据驱动测试。 6.黑盒测试方法都包括哪些 等价类划分、边界值分析、决策分析法、因果图分析、错误推测法等。 7.什么是等价类划分 把所有可能的输入数据(有效的和无效的)划分成若干个等价的子集(称为等价类)，使得每个子集中的一个典型值在测试中的作用与这一子集中所有其它值的作用相同. 可从每个子集中选取一组数据来测试程序 8.什么是边界值分析法 边界值分析法就是对输入或输出的边界值进行测试的一种黑盒测试方法.通常边界值分析法是作为对等价类划分法的补充 9.什么情况下使用决策分析法 在一些数据处理问题当中，某些操作的实施依赖于多个逻辑条件的组合，即：针对不同逻辑条件的组合值，分别执行不同的操作。决策表很适合于处理这类问题 10.你是如何利用决策分析法设计用例 （1）确定规则的个数。 有n个条件的决策表有2n个规则（每个条件取真、假值）。 （2）列出所有的条件桩和动作桩。 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 用户界面设计实例 ● 设计的系统名称：个人日常事务管理系统 ● 针对用户群是：广大电脑用户（有一定的电脑操作基础），officer 和广大学 生。 一、系统需求分析（The system requirement ） 针对officer 和学生们的需求分析，从我自身分析：对于我日常的安排我平 时会用专门的记事本记录和更改，对于日常各种事务可能会冲突或不变携带，现在针对这些需求，设计出符合此人群适合的一款系统来帮助人们更好的安排日程和完成工作。此系统是要面向个人的，同企业系统相比，此软件要力求操作简单，效率要高效，由于针对的人群是officer 和大学生，这些人都是年轻的一代人，对计算机和系统都比较了解，而且倾向于华丽的界面，但是该系统同时要解决高效，较少的操作较快地达到用户的需求。由于工作原因或计算机系统崩溃等用户在本机保存的日程安排等数据可能丢失的情况，同时，有些情况下可能无法连接网络，此系统应支持 1.、本机数据保存。2、可以上传到服务器数据库，用户注册可获得免费的空间，用户注册后，只要登录就能在随时随地获得自己的日程安排等信息。 二、系统功能定义（The function definitions ） 个人日程管理系统主要是提供个人时间日程安排系统软件，它具有相当方便的操作接口，让用户能够对所安排的行程一目了然，除去主要功能还附带了更多功能和小工具，安排的行程可以生成通行路线，并会根据天气预报提醒当天安排是否影响。而且用户可以注册，注册后用户有更多的服务，安排的日程数据可以保存到本地同时可以更新到服务器，这样用户就算到外地也可以随时查看自己的日程安排，同时其他功能有：时钟提醒、通讯录、效率评估等。 实现功能（主界面导航）： 个人日常事 务管理系统 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 数据库设计实例 数据库设计是数据库应用系统设计的一个组成部分，其核心是针对于特定的应用环境，设计合理的数据模型，创建数据库及其应用系统，使之能够有效地存储和处理数据，以满足用户的应用需求。从实用角度出发，数据库设计可分为如下几个步骤： 第一步：创建概念数据模型 ◆确定实体和关系 ◆确定属性 ◆规化数据 第二步：生成物理数据模型 第三步：验证设计 为便于学习者理解和掌握，下面结合具体的实例来讲解和展示数据库设计的详细过程。假定我们要开发一个小型的ERP系统，以管理公司部资源，其应用业务场景描述如下： v512工作室由IT业界专业人士组成，在提供高端IT培训业务的同时，还自主制作并免费发布大量公益性学习资源，工作室以公司形式运营，目前共拥有18名员工，这些员工分属于4个部门，且员工之间存在上下级管理关系。计划将来根据业务的发展设立更多的部门，聘用更多的员工。为保证质量，工作室对其成员的各项专业技能进行了级别评定。 8.5.1 确定实体和关系 1. 确定高级别的活动 要确定本ERP系统数据库设计中的实体和实体间关系，首先应明确要基于该数据库执行的高级别活动，这里所谓的高级别活动是指从用户的视角出发，确定本数据库设计中系统所涉及到的业务活动。比如，存储和维护员工的个人信息等。 在前述的应用业务场景中，v512工作室需要考虑的高级别活动包括： -聘用新员工 -解雇现有员工 -维护员工的个人信息 -增设新部门 -裁撤现有部门 -维护部门信息 -维护工作室业务相关的技能信息 -维护各员工的业务技能掌握情况 2. 确定实体 接下来要确定的是，针对上述的高级别活动需要记录和维护有关哪些事物的信息，这些事物将被转换为实体。其中，员工相关信息可抽象为“Employee”实体、部门相关信息可抽象为“Department”实体、技能相关信息抽象为“Skill”实体，为规和方便起见，这些实体均采用英文命名，并尽量在名称中体现其含义。 3. 确定关系 进一步对上述高级活动进行分析，以确定实体间存在何种关系。具体包括： -Employee-Department实体之间存在隶属关系 员工必须且只能隶属于某一个特定的部门，一个部门可以包含0～多名员工，此为一对多关系。 这种从两个方向上对同一个关系的细化描述被称为关系的角色，每个关系都对应两种角色。 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 《算法分析与设计》期末复习题 一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） " ; | A. void hanoi(int n, int A, int C, int B) 《 { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); ] move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } } 3. 动态规划算法的基本要素为（C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O 表示（B ）， 记号Ω表示（A ）， 记号Θ表示（D ）。 … A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= D. void hanoi(int n, int C, int A, int B) { if (n > 0) { | hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }数据库课程设计题目16个经典实例学习资料.doc
软件测试试题实例
算法设计与分析试卷及答案
用户界面设计实验-系统界面设计实例完整版.doc
天津科技大学数据结构与算法课程设计
算法设计与分析试卷(2010)
计算机算法设计与分析习题及答案
简单数据库设计实例
数据结构与算法设计知识点
计算机算法设计与分析期末考试复习题
《算法设计与分析》考试题目及答案
相关主题
文本预览