计算机软件练习题汇总.docx
《计算机软件练习题汇总.docx》由会员分享，可在线阅读，更多相关《计算机软件练习题汇总.docx（35页珍藏版）》请在冰点文库上搜索。
计算机软件练习题汇总
软件工程与数据库部分：
一、填空题
1.软件是计算机程序、方法和规则相关的以及在计算机上运行它时所必须的数据。
2.软件是计算机程序、方法和规则相关的文档以及在计算机上运行它时所必须的。
3.软件是、方法和规则相关的文档以及在计算机上运行它时所必须的数据。
4.软件工程是从技术和两方面研究如何更好地开发和维护计算机软件的一门学科。
5.结构化方法由、、构成，是一种面向数据流的开发方法。
6.需求分析阶段产生的最重要的文档之一是。
7.数据流图中的箭头表示。
二、单项选择题
1.在数据流图中，○（圆圈）代表（）。
A、源点B、终点C、加工D、模块
2.在数据流图中，使用双线表示（）。
A、源点和终点B、数据存储C、加工D、模块
3.软件设计阶段一般分为两步：
（）。
A、逻辑设计与功能设计B、总体设计与详细设计
C、概念设计与物理设计D、模型设计与程序设计
4.软件生存周期可划分为三个时期：
计划期、开发期和（）。
A、调研期B、可行性分析期C、运行期D、测试期
5.软件工程的出现主要是由于（）。
A、程序设计方法学的影响B、其它工程科学的影响
C、软件危机的出现D、计算机的发展
6.软件生存周期可划分为计划期、开发期及运行期三个阶段，下列工作（）属于计划期阶段。
A、程序设计B、问题定义及可行性研究C、软件测试D、需求分析
7.软件生存周期可划分为计划期、开发期及运行期三个阶段，下列工作（）属于运行期阶段。
A、维护B、可行性分析C、测试D、问题定义
8.在需求分析阶段，系统分析人员采用数据流图和（）来表达自己对问题域用户需求的理解。
A、程序流程图B、判定表或判定树C、数据字典（DD）D、加工
9.在基于结构化分析与设计的软件开发方法中，系统分析人员在需求分析阶段应采用（）和数据字典来表达自己对问题域用户需求的理解。
A、程序流程图B、数据流图（DFD）C、数据流D、加工
10.软件测试的目的是（）。
A、要证明程序无错误B、发现软件中存在的错误
C、找出编程中的错误并设法改正D、检查软件的结构设计是否合理
11.软件测试方法中，黑盒、白盒测试法是常用的方法，其中白盒测试主要用于测试（）。
A、结构合理性B、软件外部功能C、程序正确性D、程序内部逻辑
三、判断题
1.（）软件就是程序。
2.（）在设计软件测试用例时不仅需选择对被测软件的预期功能是合理的输入数据，而且还应该选择不合理的输入数据。
3.（）软件测试中设计测试用例时只需选择对被测软件的预期功能是合理的输入数据，而不选择不合理的输入数据。
4.（）软件测试分为模块测试、组装测试和确认测试三个阶段。
5.（）黑盒测试不仅需要考虑程序的功能，还需要知道程序的内部细节、结构和实现方式。
6.（）黑盒测试只需要考虑程序的功能，不需要知道程序的内部细节、结构和实现方式。
7.（）白盒测试中的测试用例的设计需要考虑覆盖程序内部的逻辑结构。
8.（）白盒测试中的测试用例设计只需要考虑覆盖程序内部的逻辑结构，不需要考虑程序的预期功能。
9.（）模块测试能发现详细设计阶段和编（码）程阶段的错误。
10.（）组装测试能发现与模块接口有关的问题。
11.（）确认测试主要采用白盒测试方法。
12.（）软件总体设计的根本任务就是确定每个程序模块的内部特征，即确定模块内部的执行过程。
13.（）软件测试与软件调试的目的完全相同。
14.（）信息是人们用来对客观世界直接进行描述、可在人们之间进行传递的知识。
15.（）目前，在数据库技术中广泛应用的数据模型是层次模型。
16.（）软件详细设计的根本任务就是确定每个模块的内部特征，即确定模块内部的执行过程。
17.（）软件测试的目的是发现程序中的错误，然后找出错误的原因并加以纠正。
四、简答题
1.软件测试包括哪些步骤？
说明这些步骤的测试对象是什么？
2.数据库系统的定义是什么？
它由哪几部分组成？
线性数据结构部分：
一、填空题
1.数据结构包括数据的逻辑结构、和数据的运算三个方面。
2.数据结构包括、数据的存储结构和数据的运算三个方面。
3.在算法“正确”的前提下，评价算法主要有两个指标是：
时间复杂度和。
4.在算法“正确”的前提下，衡量算法效率的主要指标是：
及空间复杂度。
5.线性数据结构的逻辑特征是有且仅有一个和一个终端结点，且所有结点都最多只有一个直接前趋和一个。
6.线性数据结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个和一个直接后继。
7.数据的存储结构包含有、、和等四种基本的映像方法。
8.数据存储结构的四种基本形式是：
存储结构、存储结构、索引存储结构以及散列存储结构。
9.若频繁地对线性表进行插入与删除操作，该线性表应采用存储结构。
10.线性链表中数据元素的组成：
一是数据元素的值，二是直接后继元素的，这两部分信息组成数据元素的存储映像，即结点。
11.带头结点的单向链表L为空的判定条件是。
12.在一个单链表中p所指结点之后插入s所指结点时,应执行s->next=和p->next=的操作。
13.要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t,则应执行操作：
和。
14.单链表的结点的数据类型是：
typedefstructnode{
intdata;/*数据部分*/
structnode*next；/*指向下一个结点的指针*/
}LinkList;
LinkList*p,*q;
如果要求将由指针变量q所指向的表外结点插入到单链表中由p所指向的结点之后，则应执行的语句是：
（1）
（2）。
要将p所指向的结点的数据部分修改为25，应执行的语句是：
。
15.插入和删除只允许在表的同一端进行的线性表称为，它具有的特性。
16.将插入操作限定在表的一端而删除操作限定在表的另一端的线性表称为，它具有的特性。
17.对于一个以顺序存储实现的循环队列Q[0..10],队头、队尾的位置指示器分别是front,rear,初始时都被设置为-1，则在该循环队列中实现出队操作时,判空的条件是：
；入队操作时.判满的条件是：
。
18.二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是。
19.已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是。
20.线性表的三种基本查找方法是：
顺序查找、查找和查找。
二、单项选择题
1.线性表中（）称为线性表的长度。
A、元素的长度B、数据项的数目
C、数据的长度D、元素的个数
2.不属于线性表基本运算的是：
（）。
A、删除运算B、指针运算C、取结点运算D、插入运算
3.在下列关于线性表的叙述中，错误的是：
（）。
A、采用顺序存储的线性表，必须占用一片连续的存储单元
B、采用顺序存储的线性表，便于进行插入和删除操作
C、采用链式存储的线性表，不必占用一片连续的存储单元
D、采用链式存储的线性表，便于进行插入和删除操作
4.当线性表选择链表作为存储结构时，不具有的特点是：
（）。
A、可随机访问任一元素B、插入、删除时不需要移动大量元素
C、不必事先估计存储空间D、所需空间与线性表的长度成正比
5.算法具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（）。
A、可行性B、有零个或多个输入C、有穷性D、有零个或多个输出
6.衡量一个算法的质量除了正确性之外，最重要的是要考查（）。
A、可行性B、有穷性C、时间复杂度和空间复杂度D、输入和输出
7.在长度为n的线性表中，在第i个元素之前插入一个新的元素x，需要移动（）个元素。
A、nB、n-i+1C、n-iD、i+1
8.假设p是指向线性表中第i个数据元素结点的指针，则p->next是指向第i+1个数据元素结点的指针，若p->data=ai,则p->next->data=ai+1，那么p->next->next指向的是第（）个结点。
A、iB、i+1C、i+2D、i+3
9.以下哪一个不是队列的基本运算？
A、从队尾插入一个新元素B、从队列中删除第i个元素
C、判断一个队列是否为空D、读取队头元素的值
10.在初始为空的队列中顺序插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是（）。
A、aB、bC、cD、d
11.队列的顺序存储方式中判断循环队列为满的条件是（）。
A、front==rearB、front==（rear+1）%（maxsize+1）
C、front==（rear+1）%maxsizeD、front==rear%maxsize
12.单链表Head中，在指针q所指结点后面插入一个由指针P所指结点，则执行（）。
A、q->next＝p->next；p->next＝q；B、p->next＝q->next；q＝p；
C、q->next＝p->next；p->next＝q；D、p->next＝q->next；q->next＝p；
13.一个栈的输入序列是1，2，3，4，则下列序列中不可能是栈的输出序列的是（）。
A、1234B、4321C、2341D、4123
14.设在栈中，由顶向下已存放元素c，b，a，在第四个元素d入栈前，栈中元素可以出栈。
试问在d入栈后，不可能的出栈序列是：
（）。
A、dcbaB、cbdaC、cadbD、cdba
15.栈S最多能容纳4个元素。
现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列?
（）
A、EDCBAFB、BCEFADC、CBEDAFD、ADFEBC
16.设一个栈的入栈序列是abcde，则在下列输出序列中不可能的出栈序列是：
（）
A、edcbaB、decbaC、dceabD、abcde
17.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。
A、1和5B、2和4C、4和2D、5和1
18.设有9个数据记录组成的线性表，它们的排序键码字的取值分别是（11，15，20，27，30，35，46，88，120），已经将它们按照排序码递增有序的方式存放在一维结构数组a[0..8]中从下标0开始到下标8结束的位置，则当采用折半查找算法查找关键字值等于20的数据记录时，所需比较的元素的下标依次是：
（）。
（注：
计算中间位置时取下整）
A、0，1，2B、4，1，2C、4，2D、4，3，2
19.采用折半查找方法进行查找的数据文件应满足的条件是：
（）。
A、顺序存储B、链式存储C、顺序存储且已排序D、链式存储且已排序
三、判断题
1.（）单链表从任何一个结点出发，都能访问到所有结点。
2.（）顺序表是一种随机存取的存储结构。
3.（）线性表的逻辑顺序与存储顺序总是一致的。
4.（）线性表的链式存储结构优于顺序存储结构。
5.（）数据的存储结构是数据的逻辑结构在存储单元中的表示形式。
6.（）程序的执行效率与数据存储结构的选择没有直接的关系。
7.（）线性表的长度是指线性表所占存储空间的大小。
8.（）线性表的长度决定了线性表所占存储空间的大小，但它不等于线性表所占存储空间的大小。
9.（）在采用链式存储结构的线性表上查找某个元素的平均效率比在采用顺序存储结构的线性表上查找的平均效率高。
10.（）链式存储结构的线性表适用于对数据进行频繁的查找操作，而顺序存储结构的线性表则适宜于进行频繁地插入、删除操作。
11.（）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：
p->next=s;s->next=p->next;
12.（）二维数组是其数据元素为线性表的线性表。
13.（）N（N>1）维数组可以看作是线性表的推广。
14.（）循环队列也存在空间溢出问题。
15.（）队列和栈都是运算受限的线性表，插入或者删除运算只允许在表的同一端进行。
16.（）从数据元素插入、删除的规则来看，队列的本质特征是LIFO,栈的本质特征是FIFO。
17.（）所有插入排序算法均是稳定的。
18.（）顺序存储方式只能用于存储线性结构。
19.（）程序的执行效率只决定于算法设计的技巧，与程序设计中所采用的数据的表示方式及数据逻辑模型的实际存储形式无关。
20.（）线性表的特点是每个元素都有一个前驱结点和一个后继结点。
21.（）链表的每个结点中都包含一个指针。
22.（）算法一定要有输入和输出。
23.（）顺序查找算法可以用在顺序存储结构表示的线性表上查找数据元素，但不可以用在链式存储结构的线性表上查找数据元素。
24.（）折半查找方法只能用在采用顺序存储结构的有序线性表中来实现对某一数据项的快速查找。
25.（）折半查找方法可以用在采用单向链表形式存储的有序线性表中实现对某一数据项的快速查找。
26.（）判断某个排序方法的稳定性可以通过一次或几次输入数据序列，看排序结果是否改变了原始待排数据序列中关键字值相同的数据是否发生了相对次序的改变，从而作出该排序算法是否稳定的结论。
四、简答题
1.什么是算法？
具有哪些特性？
如何衡量一个算法的好坏？
算法与程序有何不同？
2.线性表顺序存储结构的优缺点是什么？
3.线性结构与非线性结构有何差别？
4.简述顺序表和链表之间的差异。
5.什么是排序方法的稳定性？
6.什么叫栈？
它有哪些基本操作？
各个基本操作的含义是什么？
7.什么叫队列？
它有哪些基本操作？
各个基本操作的含义是什么？
五、综合题
1.
给出下列稀疏矩阵A的三元组表示法的存储模型。
2.给出下列稀疏矩阵所对应的三元组表示方法存储模型。
3.给出下列稀疏矩阵A的三元组表示法的存储模型。
4.设单链表的结点为：
typedefstructnode
{intdata;
structnode*next}LinkList;
LinkList*p,q;
如果要求将由指针变量q所指向的结点插入到单向链接表中p所指向的结点之后，则应执行的语句是什么？
要将p所指向的结点的数据部分修改为23，应执行的语句是什么？
5.对于给定的一组关键字:
503,087,512,067,908,170,889,276,675,453；请按关键字递减排序，写出直接插入排序、冒泡排序的各趟运行结果。
6.某长度为10的有序表存储于一维结构数组中下标0~9的位置中,其中记录的关键键码值依次是：
5,10,18,21,33,47,48,55,80，125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“向下取整”的方法，写出折半查找的过程及查找结果。
7.有序表中关键字序列为：
5，10，19，21，31，37，42，48，55，150，现要查找k为37及32的记录，写出其折半查找过程。
8.设待排序的记录共7个，关键码分别为8，3，2，5，9，1，6。
试用直接插入、直接选择两种方法，以关键码的变化描述排序全过程（动态过程），要求按递减顺序排序。
9.设待排序文件共有12个记录，其关键字依次分别是28，55，06，33，161，81，91，11，25，55′，57，02，请按选择排序的思想写出降序排序的全过程。
10.设有待排序的8个数据记录，其排序用关键字的取值依次是14，35，18，5，7，21，35，8，请用简单选择排序法写出降序排序的每一趟结果。
11.设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，50，8，请按直接选择排序的思想写出升序及降序排序的每一趟结果。
12.假设待排序的一批记录的关键字序列为{14，35，18，5，7，21}，请给出按照简单选择排序方法依据关键字取值升序和降序两种情况下的排序过程。
13.一个有序表的一批记录的关键字序列为（7，11，15，20，32，45，63，70，82，91），存放在一个采用顺序存储结构表示的线性表中，其中数组元素的下标为0，…，9的位置上分别对应存储有序表的第一元素直到最后一个元素。
在折半查找中，中间位置指示器的计算式子中采用取下整的方法，请给出查找关键字值为82和关键字值为13的记录的查找过程。
14.某长度为10的有序表存储于一维结构数组中下标0~9的位置中，其中记录的关键码值依次是：
5,10,18,21,33,47,48,55,80,125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“取下整”的方法，写出折半查找的过程及查找结果。
15.设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，50，8，请用冒泡排序法写出升序排序的每一趟结果。
16.对于给定的一组关键字:
50,38,27,16,97,76,53,66；按关键字递减排序，写出冒泡排序的各趟运行结果。
六、算法分析与设计题
1.下面给出的算法的功能是在顺序存储结构表示的线性表中插入一个数据元素，请画出算法的流程图，在算法中对各个分支给出功能性注释。
#defineNull0
#defineMaxSize1024
typedefintDataType;
typedefstructnode
{
DataTypedata[MaxSize];
intlast;
}SequenList;
intInsert（SequenList*L,DataTypex,inti）
{
SequenList*p;
intj;
p=L;
if（p->last==（MaxSize-1））
{
printf（"\n线性表已经满了，无法再加入!
"）;
returnNull;
}
else
if（（i<1）||（i>（p->last+1）））
{
printf（"所给插入位置不在有效范围之内!
"）;
returnNull;
}
else
{
for（j=L->last;j>=i-1;j--）
L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->last=L->last+1;
}
return
（1）;
}
2.现要求完成同类型的两个线性表的合并运算，该运算将给定第二个线性表的元素追加到第一个线性表的最后一个元素之后，假定不会产生因空间不足而上溢的现象，运算完成后应修改第一个线性表的last分量以反映新的表长，运算不破坏第二个线性表。
预期的功能用下面的计算示例及算法流程图表示。
请将下列给定的算法设计填写完整。
算法功能描述：
计算前L1={1,3,5,7,9},L2={2,4,6,8}
计算后：
L1={1,3,5,7,9,2,4,6,8},L2={2,4,6,8}
线性表的顺序存储结构定义：
#defineMaxSize1024/*允许的最大数据元素数目*/
typedefintDataType;/*数据元素的类型*/
typedefstructnode{
DataTypedata[MaxSize];/*存储线性表中数据元素用的数组*/
intlast;/*存储表的最后一个元素存放在data数组中的下标号*/
}SequenList;
计算前：
在L1表的存储结构体变量中，
data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9
last=4;
在L2表的存储结构体变量中，计算前：
data[0]=2,data[1]=4,data[2]=6,data[3]=8
last=3
计算后：
在L1表的存储结构体变量中，
data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9,data[5]=2,
data[6]=4,data[7]=6,data[8]=8
last=8;
在L2表的存储结构体变量中，计算前：
data[0]=2,data[1]=4,data[2]=6,data[3]=8
last=3
待完成的算法如下：
voidMergeList（SequenList*L1,Sequenlist*L2）
{/*算法进入时：
L1指向第一个线性表的结构体变量
L2指向第二个线性表的结构体变量
算法退出后：
L1指向第一个线性表的结构体变量，其内容为合并后的表。
L2指向第二个线性表的结构体变量，其内容未变。
*/
inti,j;/*分别表示第一个表及第二个表的当前位置指示器*/
intk;/*循环控制变量*/
intn1,n2;/*分别用于存放表L1及表L2的长度*/
DataTypex;/*存放从表L2中读出的数据元素*/
n1=L1->last+1;
n2=L2->last+1;
i=L1->last+1;
j=0;
for（k=0;k<;k++）
{
x=;
L1->data[i]=x;
i++;
j++;
}
=n1+n2-1;
return;
}
算法流程图：
n
y
3.阅读下面的程序，绘制出主函数main（）的程序流程图，并说明本程序实现的功能。
#definemaxsize30
#defineNULL-1
typedefchardatatype;
typedefstructstack{
datatypeelements[maxsize];
inttop;
}S;
voidIniStack（S*s）{
s->top=-1;
return;
}
intPush（S*s,datatypech）{
if（s->top==maxsize-1）{
printf（"\nstackoverflow!
\n"）;
returnNULL;}
else{
s->top++;
s->elements[s->top]=ch;
return
（1）;}
}
intPop（S*s）{
if（s->top<0）{
printf（"\nStackisempty!
\n"）;
returnN
升级会员 