文档库 最新最全的文档下载
当前位置:文档库 › 软件基础习题2009-10答案

软件基础习题2009-10答案

软件基础习题2009-10答案
软件基础习题2009-10答案

数据结构习题答案

第一节概论

一、选择题

1.要求同一逻辑结构的所有数据元素具有相同的特性,这意味着( )。

A.数据元素具有同一的特点 *B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等

2.数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。

(1) A.操作对象 B.计算方法 *C.物理存储 D.数据映像

(2) A.结构 *B.关系 C.运算 D.算法

3.数据结构被形式地定义为(D,R),其中D是( (1) )的有限集合,R是D上( (2) )的有限集合。

(1) A.算法 *B.数据元素 C.数据操作 D.逻辑结构

(2)A.操作 B.映像 C.存储 *D.关系

4.在数据结构中,从逻辑上可以把数据结构分为( )。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构 *C.线性结构和非线性结构 D.内部结构和外部结构5.线性表的顺序存储结构是一种( )的存储结构。

*A.随机存取 B.顺序存取 C.索引存取 D.Hash存取

6.算法分析的目的是( )。

A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 *C.分析算法的效率以求改进 D.分析算法的易懂性和文档性

7.计算机算法指的是( (1) ),它必须具备输入、输出和( (2) )等五个特征。

(1) A.计算方法 B.排序方法 *C.解决某一问题的有限运算序列 D.调度方法

(2) A.可行性、可移植性和可扩充性 *B.可行性、确定性和有穷性 C.确定性,有穷性和稳定性 D.易读性、稳定性和安全性

8.线性表若采用链表存储结构,要求内存中可用存储单元的地址( )。

A.必须是连续的 B.部分必须是连续的 C.一定是不连续的 *D.连续不连续都可以

9.在以下的叙述中,正确的是( )。

A.线性表的线性存储结构优于链式存储结构 *B.二维数组是它的每个数据元素为一个线性表的线性表C.栈的操作方式是先进先出 D.队列的操作方式是先进后出

10.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的数据组织形式,其中解释错误的是( )。

*A.集合中任何两个结点之间都有逻辑关系但组织形式松散 B.线性结构中结点按逻辑关系依次排列形成一条“锁链” C.树形结构具有分支、层次特性,其形态有点像自然界中的树 D.图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接

11.以下说法正确的是( )。

A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带有结构的各数据项的集合*D.数据结构是带有结构的数据元素的集合

二、判断题

╳1.数据元素是数据的最小单位。

√2.数据结构是带有结构的数据元素的集合。

√3.数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。

╳4.数据项是数据的基本单位。

√5.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的。

√6.数据的物理结构是数据在计算机中实际的存储形式。

╳7.算法和程序没有区别,所以在数据结构中二者是通用的。

√8.顺序存储结构属于静态结构,链式存储结构属于动态结构。

三、填空题

1.所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。

2,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。

3.数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。

4.在线性结构中,开始结点__没有_前驱结点,其余每个结点有且只有__一个_个前驱结点。

5.在树形结构中,根结点只有___一个___,其余每个结点有且只有___一个___前驱结点;叶结点没有___后继__结点,其余每个结点的后继结点可以有__任意个__·

6.在图形结构中,每个结点的前驱结点和后继结点可以有___任意个___。

7.算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。

8.下列程序段的时间复杂度是__O(n)___。

for (i=1;i<=n;i++) A[i,i]=0;

9.下列程序段的时间复杂度是__ O(n2)___。

S=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) s=s+B[i,j];

sum=s;

10.存储结构是逻辑结构的___物理__实现。

11.从数据结构的观点看,通常所说的“数据”应分成三个不同的层次,即__数据__、__数据元素_和__数据项___。

12.根据需要,数据元素又被称为__结点__、__记录__、___元素__或__顶点_。

13.通常,存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式,称为四种基本存储方式。

14.通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法(包括程序)的质量。15.一个算法的时空性能是指该算法的_时间复杂度___和___空间复杂度_,前者是算法包含的__计算量__,后者是算法需要的___存储量__。

16.在一般情况下,一个算法的时间复杂度是__问题规模__的函数。

17.常见时间复杂度的量级有:常数阶O(__1_)、对数阶O(__log2n___)、线性阶O(__n__)、平方阶O(_n2_)和指数阶O(__2n_)。通常认为,具有指数阶量级的算法是__不可行__的。

18.数据结构的基本任务是数据结构的__设计__和__实现__。

19.数据对象是性质相同的__数据元素_的集合。

20.抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作。

四、应用题

1.分析下列程序段的时间复杂度。

……

i=1;

WHILE (i<=n) i=i*2;

……

答:O(log2n)

2.叙述算法的定义及其重要特性。

答:算法是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性:可行性、确定性、有穷性、输入和输出。

3.简述下列术语:数据,数据元素,数据结构,数据对象。

答:数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。

4.逻辑结构与存储结构是什么关系?

答:在数据结构中,逻辑结构与存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关,存储结构是数据元素之间的关系在计算机中的表示。

5.将数量级210,n,n2,n3,nlog2n,log2n,2n,n!,(2/3)n,n2/3按增长率进行排列。

答:(2/3)n,210,log2n,n2/3,n,nlog2n,n2,n3,2n,n!

6.设有数据逻辑结构为:D={k1,k2,k3,…,k9},R={},画出这个逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?

答:图略。开始结点k1、k2,终端结点k6、k7。

7.设有如图1.1所示的逻辑结构图,给出它的逻辑结构,并说出它是什么类型的逻辑结构。

答:数据逻辑结构为:D={k1,k2,k3,…,k8},R={},其逻辑结构类型为树型结构。

8.分析下列程序的时间复杂度(设n为正整数)。

(1)int rec(int n)

{if(n==1)return(1); else return(n*rec(n-1)); }

(2)x=91;y=100;

While (y>0) if(x>10) y--;

(3)i=1;j=0;

while(i+j<=n)

if(i>j)j++; else i++;

(4)x=n;y=0;

while(x>=(y+1)*(y+1)) y++;

答:(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2)

9.设n为正数。试确定下列各程序段中前面加记号@的语句的频度:

(1)i=1;k=0;

while(i<=n-1) {@k+=10*i; i++; )

(2) k=0;

for(i=1;i<=n;i++)

for(j=i;j<=n:j++) @k++;

答:(1)n-1 (2)n+(n-1)+……+1=n(n+1)/2

第二节线性表

一、选择题

1.线性结构中的一个结点代表一个( )。

*A.数据元素 B.数据项 C.数据 D.数据结构

2.线性表L=(a1,a2,…,ai,…,an),下列说法正确的是( )。

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.在含有n个结点的顺序存储的线性表中,在任一结点前插入一个结点所需移动结点的平均次数为( )。

A.n *B.n/2 C.(n-1)/2 D.(n+1)/2

8.在含有n个结点的顺序存储的线性表中,删除一个结点所需移动结点的平均次数为( )。

A.n B.n/2 *C.(n-1)/2 D.(n+1)/2

9.带头结点的单链表为空的条件是( )。

A.head=NULL *B.head->next=NULL C.head->next=head D.head!=NULL

10.非空单循环链表head的尾结点*p满足( )。

A.p->next=NULL B.p=NULL *C.p->next=head D.p=head

11.在双循环链表的*p结点之后插入*s结点的操作是( )。

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next; B.p->next=s;p->next->prior=s;s->prior=p:s->next=p->next; C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

*D.s->prior=p;s->next=p->next;p->next->pror=s;p->next=s;

12. 在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入结点*s,则执行( )。

A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; *C.q->next=s; s->next=p;D.p->next=s; s->next=q;

13. 在一个单链表中,若*p结点不是最后结点。在*p之后插入结点*s,则执行( )。

A.s->next=p;p->next=s; *B.s->next=p->next;p->next=s;

C.s->next=p->next; p=s; D.p->next=s; s->next=p;

14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素,则采用( )存储方式最节省时间。

*A.顺序表 B. 单链表 C.双链表 D.单循环链表

15.设rear是指向非空带头结点的单循环链表的尾指针,则删除表头结点的操作可表示为( )。

A.p=rear;rear=rear->next; free(p) B.rear=rear->next;free(rear); C.rear=rear->next->next; free(rear); *D.p=rear->next->next;rear->next->next=p->next;free(p);

16.在一个单链表中,若删除*p结点的后继结点,则执行( )。

*A.q=p->next;p->next=q->next;free(q); B.p=p->next;p->next=p->next->next;free(p); C.p->next=p->next;free(p->next); D.p=p->next->next;free(p->next);

17.设指针p指向双链表的某一结点,则双链表结构的对称性可用( )式来刻画。

A.p->prior->next->==p->next->next B.p->prior->prior==p->next->prior *C.p->prior->next-

>==p->next->prior D.p->next->next==p->prior->prior

18.在循环链表中,将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是( )。

A.rear和rear->next->next *B.rear->next和rear C.rear->next->next和rear D.rear和rear->next

19.循环链表的主要优点是( )。

A.不再需要头指针了 B.已知某个结点的位置后,容易找到它的直接前驱 C.在进行插入、删除操作时,能更好地保证链表不断开 *D.从表中任一结点出发都能扫描到整个链表

20.在线性表的下列存储结构中,读取元素花费时间最少的是( )。

A.单链表 B.双链表 C.循环链表 *D.顺序表

二、判断题

√1.顺序存储的线性表可以随机存取。

╳2.顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。

√3.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。

╳4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。

√5.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。

√6.在单链表中,可以从头结点开始查找任何一个元素。

╳7.线性表的链式存储结构优于顺序存储结构。

√8.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。

╳9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。

╳10.顺序存储方式只能用于存储线性结构。

三、填空题

1.为了便于讨论,有时将含n(n>0)个结点的线性结构表示成(a1,a2,…,an),其中每个ai代表一个__结点_。a1称为_第一个_结点,an称为__最后一个_结点,i称为ai在线性表中的_位置__。对任意一对相邻结点ai、ai+1(1≤i

2.线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接__前驱_外,其他结点有且仅有一个直接__前驱_;除终端结点没有直接__后继_外,其他结点有且仅有一个直接_后继__。

3.所有结点按一对一的邻接关系构成的整体就是__线性__结构。

4.线性表的逻辑结构是__线性_结构,其所含结点的个数称为线性表的___长度_。

5.在单链表中,删除p所指结点的直接后继的操作是__ q=p->next;p->next=q->next;free(q);___·6.非空的单循环链表head的尾结点(由指针p所指)满足__ p->next= head _____。

7.rear是指向非空带头结点的单循环链表的尾指针,则删除起始结点的操作可表示为__ p=rear->next;q=p->next;p->next=q->next;free(q);____。

8.对于一个具有n个结点的单链表,在p所指结点后插入一个结点的时间复杂度为__O(1)__,在给定值为x的结点后插入新结点的时间复杂度为__ O(n)__。

9.单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。

10.在顺序表中插入或删除一个元素,平均需要移动_一半_元素,具体移动的元素个数与__元素的位置_有关。11.在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时,需向后移动___ n-i+1__个元素。12.在一个长度为n的向量中删除第i(1≤i≤n)个元素时,需向前移动__ n-i __个元素。

13.在双链表中,每个结点有两个指针域,一个指向___前驱__,另一个指向___后继___。

14.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=__ p->next->next ;___。

15.设head指向单链表的表头,p指向单链表的表尾结点,则执行p->next=head后,该单链表构成__单循环链表___。

16.在单链表中,若p和s是两个指针,且满足p->next与s相同,则语句p->next=s->next的作用是_删除

__s指向的结点。

17.设r指向单循环链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的三条语句是

___s->next= r->next __;r->next=s;r=s;

18.在单链表中,指针p所指结点为最后一个结点的条件是__ p->next=NULL___。

19.在双循环链表中,若要在指p所指结点前插入s所指的结点,则需执行下列语句:s->next=p; s-

>prior=p->prior;__ p->prior->next __=s;p->prior=s;

20.在单链表中,若要在p所指结点之前插入s所指的结点,可进行下列操作:

s->next=___ p->next __; p->next=s; temp=p->data;

p->data=__ s->data ___; s->data=__ temp _;

四、应用题

1.描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。

答:首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点。头指针是指向链表中的第一个结点的指针。

2.何时选用顺序表,何时选用链表作为线性表的存储结构为宜?

答:从空间上来看,当线性表的长度变化较大、难以估计其规模时,选用动态的链表作为存储结构比较合适,但链表除了需要设置数据域外,还要额外设置指针域,因此当线性表长度变化不大、易于事先确定规模时,为了节约存储空间,宜采用顺序存储结构。从时间上来看,若线性表的操作主要是查找,很少进行插入和删除操作时,应选用顺序表。对于频繁进行插入和删除操作的线性表,宜采用链表作为存储结构。

3.在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?

答:平均移动表中大约一半的结点,插入操作平均移动n/2 个结点,删除操作平均移动(n-1)/2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。

4.为什么在单循环链表中设置尾指针比设置头指针更好?

答:单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点,但设置尾指针时,若在表尾进行插入或删除操作可在O(1)时间内完成,同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针,表尾进行插入或删除操作,需要遍历整个链表,时间复杂度为O(n)。

5.双链表和单循环链表中,若仅知道指针p指向某个结点,不知道头指针,能否将结点*p 从相应的链表中删除?若可以,其时间复杂度各为多少?

答:能删除。双链表上删除p所指向的结点的时间复杂度为O(1),单循环链表上删除p所指向的结点的时间复杂度为O(n)。

6.下列算法的功能是什么?

LinkList *testl(LinkList *L)

{//L是无头结点的单链表

LinkList *q,*p;

if(L&&L->next)

{ q=L; L=L->next; p=L;

while(p->next) p=p->next;

p->next=q; q->next=NULL;}

return L;}

答:如果长度大于1,则将首元结点删除并插入到表尾。

7.如果有n个线性表同时共存,并且在处理过程中各表的长度会发生动态变化,线性表的总长度也会自动地改变。在此情况下,应选择哪一种存储结构?为什么?

答:应选用链式存储结构。因为顺序表是静态存储结构,只能预先分配,不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间,因此适用于动态变化表长的线性表。

8.若线性表的总数基本稳定,且很少进行插入、删除操作,但要求以最快的方式存取线性表的元素,应该用哪种存储结构?为什么?

答:应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。

五、算法设计题

假设算法中用到的顺序表和链表结构如下:

#define maxsize 100;

Typedef struct node1 {datatype data[maxsize]; int length } SeqList;

Typedef struct node2 {datatype data; struct node2 *next } LinkedList ;

1.试用顺序表作为存储结构,实现将线性表(a0,a1,a2,…an-1)就地逆置的操作,所谓“就地”是指辅助空间为O(1)。

答:(1)顺序表的就地逆置

分析:分别用两个整型变量指向顺序表的两端,同时向中间移动,移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList *L){//顺序表的就地逆置

for(i=0;j=L->length-1;i

{t=L->data[i]; L->data[i]=L.data[j]; L->data[j]=t; } }

(2)链表的就地逆置

分析:本算法的思想是逐个地把L的当前元素r插入到新的链表头部。

void Linkedreverse(LinkedList *L){//链表的就地逆置

p=L->next;L->next=NULL;

while(p!=NULL)

{r=p,p=p->next;//r指向当前待逆置的结点,p记下下—个结点

r->next=L—>next;L->next=r;//放到表头

} }

2.设顺序表L是一个递增(允许有相同的值)有序表,试写一算法将x插入L中,并使L仍为一个有序表。答:分析:先找到x的正确插入位置,然后将大于x的元素从后向前依次向下移动,最后将x插入到其位置上,同时顺序表长度增1。

void SeqListinsert(SeqList *L,int x){//x插入到递增有序的顺序表L中

i=0;

while((i<=L->length-1)&&(x>=L->data[i])) i++;//找正确的插入位置

for(k=L->length-1;k>=i;k--) //元素从后往前依次后移

L->data[k+1]=L->data[k];

L->data[i]=x;//x插入到正确位置

L->length++;

)

3.设单链表L是一个递减有序表,试写一个算法将x插入其中后仍保持L的有序性。

答:分析:此问题的关键是在链表中找到x的插入位置,因此需要两个指针一前一后地依次向后移动。

void LinkListinsert(LinkedList *L,int x){//x插入有序链表L中

q=L;p=q—>next;

while(p!=NULL&&p—>data>x) //找到插入的位置

{q=p;p=p—>next; }

s=(LinkedList*)malloc(sizeof(LinkedList));//生成新结点

S—>data=x; S—>next=p; q—>next=s; }

4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。

答:分析:对不带头结点的链表操作时,要注意对第一个结点和其他结点操作的不同。

void LinkedListlnsert(LinkedList *L,int x,int i)

{//不带头结点的单链表的第i个元素之前插入一个元素

p=L:j=1;

while(p!=NULL&&j

{p=p—>next;j++;}

if(i<=0||p==NULL) printf(”插入位置不正确\n”);

else {q=(LinkedList*)malloc(sizeof(LinkedList));q—>data=x;

if(i==1) {q—>next=L;L=q;} //在第一个元素之前插入

else{q—>next=p—>next;p—>next=q;} //在其他位置插入

} }

5.设A、B是两个线性表,其表中元素递增有序,长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。

答:(1)分析:用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,将A、B表中较小的元素写入C 中,直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。

SeqList *Seqmerge(SeqList A,SeqList B,SeqList *C){//有序顺序表A和B归并成有序顺序表C

i=0;j=0;k=0;//i,i,k分别为顺序表A,B,C的下标

while(i

{if(A.data[i]

{C->data[k]=A.data[il;i++; ]

else {C->data[k]=B.data[j];j++;} //B中当前元素较小

k++; }

if (i==m) for(t=j;tdata[k]=B.data[t];k++;} //B表长度大于A表

else for(t=i;tdata[k]=A.data[t];k++;} //A表长度大于B表

C->length=m+n; return C;}

(2)

VOid Linkmerge(LinkedList *A,LinkedList *B,LinkedList *C)

{//有序链表A和B归并成有序链表C

pa=A—>next;pb=B—>next;C=A;pc=C;

while(pa&&pb) //A和B都不为空时

{if(pa—>datadata) //A当前结点值较小

{qa=pa->next; pC->next=pa; pc=pc->next; pa=qa;}

else {qb=pb->next;pc->next=pb:pc=pc->next;pb=qb;} //B当前结点值较小

}

if(pa)pc—>next=pa;//A没有结束,将A表剩余元素链接到C表

if(pb)pc—>next=pb;//B没有结束,将B表剩余元素链接到C表

free(B);//释放B表的头结点

}

本算法需要遍历两个线性表,因此时间复杂度为O(m+n)。

6.设指针la和lb分别指向两个不带头结点的单链表的首结点,设计从表la中删除第i个元素起共len个元素,并将这些元素插入到lb中第j个结点之前的算法。

答:分析:先在la中找到第i个结点,分别用两个指针pre和p指向第i-1和第i个结点,然后用指针q从第i个结点起向后走len个元素,使q指向此位置。然后在lb中找到第j个结点,将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。

void Deletelnsert(LinkedList *la,LinkedList *lb,int i,int j, int len)

{//删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前

if(i<0||j<0||len<0) exit(0);

p=la;k=1;pre=NULL;

while(p&&k

{pre=p; p=p->next; k++; }

if(!p) exit(0);

q=p;k=l;//p指向la表中第i个结点

while(q&&knext; k++;} //查找la表中第i+len-1个结点

if(!q) exit(0);

if(pre==la) la=q—>next;//i=1的情况

else pre—>next=q—>next;//完成删除

//将从la中删除的结点插入到lb中

if(j==1) {q->next=lb; lb=p; } //j=1时

else { r=lb; k=1;//j>1时

while(r&&knext; k++;} //查找Lb表中第i—1个元素

if(!r) exit(0);

q—>next=r—>next;r—>next=p;//完成插入

} }

7.单链表L是一个递减有序表,试写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点空间,这里min和max是两个给定的参数。

答:LinkedList delete(LinkedList *L,int min,int max)

{//删除递减有序单链表L中值大于min且小于max的结点

q=L;

if(min>max) {printf(”min>max\n”);exit(0);}

else p=L—>next;//q始终指向p的前驱

while(p—>data>=max) //当前元素大于或等于max,则p、q依次向后移动

{q=p;p=p—>next;}

while((p!=NULL)&&(p一>data>min))

{//当前元素的值比min大同时比max小,删除p指向的结点

q—>next=p—>next, free(p);p=q—>next; }

return L; }.

8.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa和pb,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序。

答:分析:用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点,将q所指向的结点从A表删除,并链接到B表。

void decompose(LinkedList *A,LinkedList *B)

{//单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B

p=A->next; B=(LinkedList*)malloc(sizeof(LinkedList));

r=B;

while(p!=NULL&&p->next!=NULL)

{q=p—>next;//q指向偶数序号的结点

p—>next=q—>next;//将q从A表中删除

r—>next=q;//将q结点链接到B链表的末尾

r=q;//r总是指向B链表的最后—·个结点

p=p—>next;//p指向原链表A中的奇数序号的结点

}

r—>next=NULL;//将生成B链表中的最后一个结点的next域置为空

}

9.假设以两个元素值递增有序排列的线性表A、B分别表示两个集合,要求另辟空间构造一个线性表C,其元素为两集合的交集,且表C中的元素值也递增有序排列。用顺序表实现并写出C的算法。

答:分析:用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,若A、B表中当前元素值相同,则写入C中,并使i、j、k值增1;若A表元素值较小,则使i增1;若B表元素值较小,则使j增1,直到有一个表先结束。

SeqLiSt *intersection(SeqList A,SeqList B,SeqList *C)

{//求元素依值递增有序排列的顺序表A、B的交集C

i=0; j=0;k=0;

while((i<=A.length-1)&&(j<=B.length-1))

{if(A.data[i]==B.data[j]) //找到值相同的元素

{C->data[k]=A.data[i];//相同元素写入C表中

k++;i++;j++; }

else

if(A.data[i]

else j++; }

C->length=k; return C; }

11.假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前驱结点。

答:分析:因为既不知道此单循环链表的头指针,也不知道其尾指针,所以找s的前驱就只能从s开始,顺次向后寻找。

void DeletePre(Linkedlist *s)

{//删除单循环链表中结点s的直接前驱

p=s;

while(p—>next—>next!=s) p=p—>next;//找到s的前驱的前驱p

q=p—>next;//q是p的后继,即s的前驱

p—>next=s;//将q删除

free(q); }

12.计算带头结点的循环链表的结点个数。

答:int number(Linkedlist *head)

{//计算单循环链表中结点的个数

p=head—>next; i=0;

while(p!=head) {i++;p=p->next;}

return i; }

13.已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其他字符),试编写算法构造三个以循环链表表示的线性表,使得每个表中只含有同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。

答:分析:p指向待处理的单链表的首元结点,构造三个空的单循环链表,分别存储三类字符,其中一个表可使用原来的单链表。q指向p的下一个结点,根据*p的数据域的值将其插入到不同的链表上。再把q的值给p,处理下一个结点。

void change(LinkedList *L,LinkedList *pa,LinkedList *pb,LinkedList *pc)

{//分解含有三类字符的单链表为三个以循环链表表示的线性表,使其分别含有三类字符

p=L—>next; pa=L;

pa—>next=pa;//分别构造三个单循环链表

pb=(LinkedList*)malloc(sizeof(LinkedList));

pc=(LinkedList*)malloc(sizeof(LinkedList));

pb—>next=pb;pc—>next=pc;

while(p!=L)

{q=p—>next;·//q记下L中下一个结点的位置

if(p—>data<=’z’&&p—>data>=’a’) //链接到字母链表的头部

{p—>next=pa—>next;pa—>next=p;}

else if (p—>data<=’9’ &&(p—>data>=’0’) //链接到数字链表的头部

{p—>next=pb—>next;pb—>next=p;}

else{p->next=pc->next;pc->next=p;}//链接到其他字母链表的头部

p=q; } }

14、己知A、B和C为三个递增有序的线性表,现要求对A表进行如下操作:删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注:题中未特别指明同一表中的元素值各不相同)。

答:分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始,凡小于same的元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个Same

SeqList IntersectDelete(SeqList *A,SeqList B,SeqList C)

{//对顺序表A删去那些既在B表中出现又在C表中出现的元素

i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置

while(ilength&&i

{if(B.data[j]

else if(B.data[j]>C.data[k]) k++;

else {same=B.data[j];//找到了相同元素same

while(B.data[j]==same) j++;

while(C.data[k]==same) k++;/j、k后移到新的元素

while(ilength&&A->data[i]

A->data[m++]=A->data[i++];//需保留的元素移动到新位置

while(i1ength&&A->data[i]==same; i++;//跳过相同的元素

}

}

while(ilength)

A->data[m++]=A->data[i++];//A的剩余元素重新存储

A->1ength=m; }

15.双循环链表中,设计满足下列条件的算法。

(1)在值为x的结点之前插入值为y的结点。(2)删除值为x的结点。

答:分析:在双循环链表中插入和删除结点要注意修改双向的指针。

typedef struct Node

{DataType data; struct Node *prior,*next;}DLNode,*DLinkedList;

void DLinsertl(DLinkedList L,int x,int y)

{ //在双循环链表中插入结点

p=L->next;

while(p!=L&&p->data!=x) p=p->next;//在链表中查找值为x的结点

if(p->data==x) //找到值为x的结点

{q=p->prior;//q指向值为x的结点的前驱

s=(DLinkedList)malloc(sizeof(DLNode));

s->data=y;

s->next=p; s->prior=q;//将y插入到q与p指向的结点之间

p->prior=s;q->next=s; }

else{printf(”没有值为x的结点”);exit(0);} }

void DLDelete(DLinkedList L,int x)

{//在双循环链表中删除结点

p=L->next;

while(p!=L&&p->data!=x)p=p->next;

if(p->data==x) {p->prior->next=p->next;p->next->prior=p->prior;free(p);}

else{printf(”没有值为x的结点”);exit(0);}

}

16.设有一个双循环链表,其中有一结点的指针为p,编写算法将p与其右边的一个结点进行交换。

答:typedef struct Node {DataType data; struct Node *prior,*next;}DLNode,*DLinkedList;

void DLchange(DLinkedList p)

{//将双循环链表中p指向的结点与其右边的一个结点进行交换

q=p—>next;//q指向p的后继

p—>prior—>next=q;q—>prior=p—>prior;//将p的前驱与q相链接

p—>next=q—>next;p—>prior=q;//将p插入到q之后

q->next—>prior=p;q—>next=p; }

17.设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个可访问频度域freq,在链表启用之前,其初始值均为0。每当链表进行一次LocateNode(L,x)操作时令元素值为x的结点中freq域的值加l,并调整表中结点的次序,使其按访问频度的递减次序排列,以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。

答:分析:先在双链表中查找值为x的结点,若找到则使其freq值增1,然后从头至尾扫描链表,将此结点插入到按freq递减顺序排列的正确位置。

typedef struct DLNode

{int data,freq;struct DLNode *prior,*next;}DLNode,*DLinkedList;

void LocateNode(DLinkedList head,int x)

{//双链表按访问频度域freq递减次序排列

p2=head; p1=p2—>next;//p2在前,p1在后

while(p1) //查找单链表中值为x的结点

if(pl—>data==x) {pl—>freq++; break;}//使值为x的结点的freq加1

else {p2=pl;p1=p2—>next;}

if(p1==NULL) printf(”Not found.\n”);

else{if(p1—>next==NULL) {p2—>next=p1—>next;temp=p1;}

//在链表中找temp所指向的结点,按freq值递减应插入的位置

else{p2—>next=p1—>next;//插入链表中间的某一位置

p1—>next->prior=p2; temp=pl;}

for(p2=head,p1=p2->next;pl&&p1->freq>temp->freq;p2=p1,pl=p2->next);//插入

if(p1==NULL) {p2->next=temp;temp->prior=p2;temp->next=NULL;}

else {p2->next=temp;temp->prior=p2;temp->next=pl;p1->prior=temp;}

} }

18.给出用单链表存储多项式的结构,并编写一个按指数值递增次序输入所产生的多项式链表的过程。

答:typedef struct PNode

{int coef;//系数

int exp;//指数

struct PNode *next;}*PLink;

PLink CreatPoly( )

{//建立多项式

head=(PLink)malloc(sizeof(struct PNode));

r=head;

printf(”输入系数和指数:”); scanf(&n,&m);

while(n!=0) //若n=0则退出循环

{s=(Plink)malloc(sizeof(struct PNode));

s->coef=n;s->exp=m;r->next=s;r=s;//把s链接到r的后面

printf(”输入系数和指数:”); scanf(&n,&m); }

r->next=NULL;head=head—>next;//删除头结点

return head; }

19.根据上题的多项式链表结构,编写一个过程实现两个多项式相加的运算。

答:分析:对所有指数相同的项,将其对应系数相加,若和不为0,则构造新“和多项式”的结点;将所有指数不同的项复制到和多项式中。

Plink add(PLink pa,PLink pb)

{//多项式相加

p=pa;q=pb;pc=(PLink)malloc(sizeof(struct PNode));r=pc;

while(p!=NULL&&q!=NULL)

{if(p->exp==q->exp)//两结点的指数相同时,将两系数相加生成新结点插入c中

{x=p->coef+q->coef;

if(x!=0){s=(PLink)malloc(sizeof(struct PNode));s->coef=x; s->exp=p->exp;

r->next=s; r=s; }

p=p->next;q=q->next;}

else if(p->exp>q->exp)//两结点的指数不同时,将较小系数的结点复制成新结点插入c中

{s=(PLink)malloc(sizeof(struct PNode));s->coef=q->coef;s->exp=q->exp;

r->next=s; r=s;q=q->next;}

else {s=(PLink)malloc(sizeof(struct PNode));s->coef=p->coef;

s->exp=p->exp;r->next=s;r=s;p=p->next; }

}

while(p!=NULL) //复制A的余下部分

{s=(PLink)malloc(sizeof(struct PNode));s->coef=p->coef;s->exp=p->exp;

r->next=s:r=s;p=p->next;}

while(ql=NULL) //复制B的余下部分

{s=(PLink)malloc(sizeof(struct PNode));s->coef=q->coef;s->exp=q->exp;

r->next=s;r=s;q=q->next; }

r->next=NULL;//最后结点的next域置为空

s=pc;pc=pc->next;//删除c的头结点

free(s); return pc; }

20.约瑟夫环问题:任给正整数n、k,按下述方法可得排列1,2,…,n的一个置换:将数字l,2,…,n环形排列,按顺时针方向从1开始计数;计满k时输出该位置上的数字(并从环中删去该数字),然后从下一个数字开始继续计数,直到环中所有数字均被输出为止。例如,n=10、k=3时,输出的置换是3,6,9,2,7,1,8,5,10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。

答:void Js1(int A[n],int N,iht K)

{//以数组为存储结构

for(i=0;i

j=0;

for(i=0;i

{s=0;

while(s

printf(”%d”,j);

A[j-1]=0;//将计满k值的数字输出,并将其位置标为0表明已删除

} }

void Js2(LinkedList last,int N,int K)

{//以不带头结点的、已知尾指针的单循环链表为存储结构

p=last; q=p->next;//此时q为头结点fp为q的前驱

while(N>0)

{for(j=2;j<=K;j++) //循环K-1次

{p=q;q=p->next;}

printf(”%d”,q->data); N--;

p->next=q->next; //删除q

q=p—>next; }

}

第三节栈和队列

一、选择题

1.设有一顺序栈s,元素s1,s2,s3,s4,s5,s6依次入栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是( )。

A.2 *B.3 C.5 D.6

2.若一个栈的输入序列是a、b、c,则通过入栈、出栈操作可能得到a、b、c的不同排列个数为( )。

A.4 *B.5 C.6 D.7

3.设有一顺序栈已经含有3个元素,如图3-1所示,元素a4正等待入栈。以下序列中不可能出现的出栈序列是( )。

*A.a3,a1,a4,a2 B.a3,a2,a4,a1 C.a3,a4,a2,a1 D.a4,a3,a2,a1

4.和顺序栈相比,链栈有一个比较明显的优势是( )。

*A.通常不会出现栈满的情况 B.通常不会出现栈空的情况 C.插入操作更容易实现 D.删除操作更容易实现

5.若一个栈的输入序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i个输出元素是( )。

A.不确定 B.n-i *C.n-i+1 D.n-i-1

6.以下说法正确的是( )。

*A.因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B.因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C.对于链栈而言,在栈满状态下,如果再进行入栈操作,则会发生“上溢” D.对于顺序栈而言,在栈满状态下,如果再进行入栈操作,则会发生“下溢”7.顺序队列的入队操作应为( sq.rear初值为-1 )。

*A.sq.rear=sq.rear+1;sq.data[sq.rear]=x; B.sq.data[sq.rear]=x;sq.rear=sq.rear+1;

C.sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear+1]=x; D.sq.data[sq.rear]=x;sq.rear=x;

sq.rear=(sq.rear+1)%maxslze;

8.循环队列的入队操作应为(sq.rear初值为-1 )。

A.sq.rear=sq.rear+1;sq.data[sq.rear]=x B.sq.data[sq.rear]=x;sq.rear=sq.rear+l;

*C.sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x; D.sq.data[sq.rear]=x;

sq.rear=(sq.rear+1)%maxsize;

9.顺序队列的出队操作为(sq. front初值为-1 )。

A.sq.front=(sq.front+1)%maxsize; *B.sq.front=sq.front+1; C.sq.rear=(sq.rear+1)%maxsize; D.sq.rear=sq.rear+1;

10.循环队列的出队操作为(sq. front初值为-1 )。

*A.sq.front=(sq.front+1)%maxsize; B.sq.front=sq.front+1;

C.sq.rear=(sq.rear+1)%maxsize; D.sq.rear=sq.rear+l;

11.循环队列的队满条件为( )。

A.(sq.rear+1)%maxsize==(sq.front+1)%maxsize; B.(sq.rear+1)%maxsize==sq.front+1;

*C.(sq.rear+1)%maxsize==sq.front; D.sq.rear==sq.front;

12.循环队列的队空条件为( )。

A.(sq.rear+1)%maxsize==(sq.front+1)%maxsize; B.(sq.rear+1)%maxsize==sq.front+1;C.(sq.rear+1)%maxsize==sq.front; *D.sq.rear==sq.front;

13.如果以链表作为栈的存储结构,则出栈操作时( )。

A.必须判别栈是否满 B.判别栈元素的类型 *C.必须判别栈是否空 D.对栈不做任何判别

14,向一个栈顶指针为Top的链栈中插入一个s所指结点时,其操作步骤为( )。

A.Top->next=s; B.s->next=Top->next;Top->next=s; *C.s->next=Top;Top=s; D.s-

>next=Top;Top=Top->next;

15.从栈顶指针为Top的链栈中删除一个结点,并将被删结点的值保存到x中,其操作步骤为( )。

*A.x=Top->data;Top=Top->next; B.Top=Top->next;x=Top->data; C.x=Top;Top=Top-

>next; D.x=Top->data;

16.在一个链队中,苕f、r分别为队头、队尾指针,则插入s所指结点的操作为( )。

A.f->next=s;f=s; *B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;

17.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是( )。

A.e,d,c,b,a B.d,e,c,b,a *C.d,c,e,a,b D.a,b,c,d,e

18.一个队列的入队序列是1,2,3,4,则队列可能的输出序列是( )。

A.4,3,2,1 *B.1,2,3,4 C.1,4,3,2 D.3,2,4,1

19.设计一个判别表达式中左,右括号是否配对出现的算法,采用( )数据结构最佳。

A.线性表的顺序存储结构 *B.栈 C.队列 D.线性表的链式存储结构

二、判断题

√1.在顺序栈栈满情况下,不能再入栈,否则会产生“上溢”。

╳2.与顺序栈相比,链栈的一个优点是插入和删除操作更加方便。

╳3.若一个栈的输入序列为1,2,3,…,n,其输出序列的第一个元素为n,则其输出序列的每个元素ai一定满足ai=i+1(i=1,2,…,n)。

√4.在链队中,即使不设置尾指针也能进行入队操作。

√5.在对链队(带头指针)做出队操作时,不会改变front指针的值。

╳6.循环队列中元素个数为rear-front。

╳7.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到4,3,1,2.

√8.一个栈的输入序列是1,2,3,4,则在栈的输出序列中可以得到1,2,3,4。

╳9.若以链表作为栈的存储结构,则入栈需要判断栈是否满.

√10.若以链表作为栈的存储结构,则出栈需要判断栈是否空。

三、填空题

1.向一个栈顶指针为Top的链栈中插入一个s所指的结点时,其进行的操作是__ s->next=Top;Top =s;__。2.从栈顶指针为Top的链栈中删除一个结点,并将结点保存在x中,进行的操作是_ x=Top->data;Top=Top->next;__。

3.在具有n个单元的循环队列中,队满时共有___n-1_个元素。

4.假设以S和X分别表示入栈和出栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为__ b,c,e,d,a ___。

5.设有数组A[m]作为循环队列的存储空间,front为队头指针,rear为队尾指针,则元素x执行入队操作的语句是_rear=(rear +1)%(m+1); A[rear]=x;__。

6.在一个链队中,如果f、r分别为队头、队尾指针,则插入s所指结点的操作是_r->next=s; r=s;___。7.栈的逻辑特点是__后进先出____,队列的逻辑特点是_先进先出__,二者的共同特点是_操作受限__。

8.___栈___可以作为实现递归函数调用的一种数据结构。

9.在队列中,新插入的结点只能添加到__队尾__。

10.链队在一定范围内不会出现__队满___的情况。当lq.front==lq.rear时,队中无元素,此时___队空

__。

11.设一个链栈的栈顶指针为ls,栈中结点的格式为data:next,栈空的条件是_ ls = NULL__;如果栈不为空,则出栈操作为p=ls; ___ ls = ls ->next __;free(p)。

12.对带有头结点的链队lq,判定队列中只有一个数据元素的条件是__lq->front->next= lq->rear___。13.设有一个空栈,现在输入序列为1,2,3,4,5,经过push,push,pop,push,pop,push后,栈顶指针所指元素是__4__。

14.设用一维数组A[n]来表示一个栈,令A[0]为栈底。用整型变量t来指示当前栈顶的位置,A[t]为栈顶元素。往栈中压入一个新元素时,变量t的值__加1___,从栈中弹出一个元素时,变量t的值___减1___。设空栈时,输入序列a,b,c经过push,pop,push,push,pop操作后,从栈中弹出的元素是___c__。

四、应用题

2.设有字符串为3*-y-a/y^2,试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作,用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如,ABC变为BCA的操作步骤为XXSXSS。

答:XSXXXSSSXXSXXSXXSSSS

3.设有一个输入序列a,b,c,d,元素经过一个栈到达输出序列,而且元素一旦离开输入序列就不能再回到输入序列,试问经过这个栈后可以得到多少种输出序列?

答:可以得到14种输出序列:abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc. 4.按照运算符优先法,画出对下面算术表达式求值时,操作数栈和运算符栈的变化过程:9-2*4+(8+1)/3。答:

5

答:因为链栈只在链表头插入和删除结点,不可能在链表中间插入或删除结点,算法实现很简单,所以一般不设置头结点。

第四节数组

一、选择题

1.数组通常具有的两种基本操作是( )。

A.建立和删除 B.索引和修改 *C.查找和修改 D.查找和索引

2.二维数组A[11,6]采用行序为主序方式存储,每个数据元素占4个存储单元,且A[0,0]的存储地址是1000,则A[8,4]的存储地址是( )。

*A.1208 B.1212 C.1368 D.1364

3.对矩阵压缩存储是为了( )。

A.方便运算 *B.节省空间 C.方便存储 D.提高运算速度

4.稀疏矩阵的压缩存储方法通常有两种,即( )。

A.二元数组和三元数组 B.三元组和散列 *C.三元组和十字链表 D.散列和十字链表

二、判断题

√ 1.数组是同类型值的集合。

√2.数组是一组连续的内存单元。

╳3.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的也不是树形的。

╳4.插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。

√ 5.使用三元组表示稀疏矩阵的元素,有时并不能节省存储空间。

三、填空题

1.二维数组A[10, 20]采用列序为主序方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是200,则A[6,12]的地址是___315___。

2.有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式)存储其下三角元素,且第一个元素A[0,0]的存储地址为1,则A[4,5]的地址是__14__,A[8,3]的地址是___31_。

3.下三角矩阵A[N,N]的下三角元素已压缩到一维数组S[N(N+1)/2]中,若按行序为主序存储,则A[i,j]对应的S中的存储位置是__I(I-1)/2+j(i≥j),n(n+1)/2+1(I

四、应用题

1.假设有二维数组A[6,8],每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始地址(基地址)为1000,计算:(1)数组A的容量。(2)按行优先方式存储时,元素A[1,4]的地址。(3)按列优先方式存储时,元素A[4,7]的地址。

答:(1)数组A的容量:6*8*6=288。(2)按行优先方式存储时,元素A[1,4]的地址=1000+3*6=1018。(3)按列优先方式存储时,元素A[4,7]的地址=1000+(6*6+3)*6=1234。

2.设有三对角矩阵A[n,n],将其三条对角线上的元素逐行存放于数组B[3n-3]中,使得B[k]=A[i,j],求:(1)用i,j表示k的下标变换公式。 (2)用k表示i,j的下标变换公式。

答:(1) k=2i+j-3 (2) I=(k+1)/3+1,j=k-2i+3。

3.画出图5-2所示的稀疏矩阵A的三元组表和十字链表。

答:

4.用三元组表表示图5-3所示的稀疏矩阵的转置矩阵。

答:

1.设计将数组A[n]中的所有奇数移到所有偶数之前的算法。要求不另外增加存储空间且时间复杂度为O(n)。

算法采用两个变量i和j分别表示数组的开头和末尾元素,同时向中间搜索:

void change(int a[n])

{ I=0; j=n-1;

while (I

{while (a[I]%2!=0&&I

while (a[I]%2==0&&I

if (I

{c=a[I];a[I]=a[j];a[j]=c; I++;j--;}

}

}

*2.当稀疏矩阵A和B均以三元组作为存储结构时,试写出矩阵相加的算法,其结果存放在三元组C中。略。

第五节树

(树根结点的高度为1)

一、选择题

1.以下说法错误的是( )。

*A.树形结构的特点是一个结点可以有多个直接前驱 B.线性结构中的一个结点至多只有一个直接后继C.二叉树与树是两种不同的数据结构 D.树(及一切树形结构)是一种“分支层次’结构

2.以下说法错误的是( )。

A.二叉树可以是空集 *B.二叉树的任一结点都有两棵子树 C.二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分

3.以下说法错误的是( )。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上,二叉树的求双亲操作很容易实现 C.在二叉链表上,求根以及求左、右孩子等操作很容易实现 *D.在二叉链表上,求双亲操作的时间性能很好

4.以下说法错误的是( )。

A.一般在哈夫曼树中,权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n棵二叉树,最终求得的哈夫曼树共有2n-1个结点 *D.若初始森林中共有n棵二叉树,进行2n-1次合并后才能剩下一棵最终的哈夫曼树

5.深度为6的二叉树最多有( )个结点。

A.64 *B.63 C.32 D.31

6.将含有41个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为21的双亲结点编号为( )。

*A.10 B.11 C.41 D.20

7.任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置( )。

A.肯定发生变化 B.有时发生变化 *C.肯定不发生变化 D.无法确定

8.设二叉树有n个结点,则其深度为( )。

A.n-1 B.n C.└log2n┘+1 *D.无法确定

9.设深度为k的二叉树上只有度为0和度为2的结点,则这类二叉树上所含结点总数最少( )个。

A.k+l B.2k *C.2k-1 D.2k+1

10.下列说法正确的是( )。

*A.树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B.树的前序遍历序列与其对应的二叉树的后序遍历序列相同 C.树的后序遍历序列与其对应的二叉树的前序遍历序列相同 D.树的后序遍历序列与其对应的二叉树的后序遍历序列相同

11.下列说法中正确的是( )。

A.任何一棵二叉树中至少有一个结点的度为2 B.任何一棵二叉树中每个结点的度都为2 C.任何一棵二叉树中的每个结点的度肯定等于2 *D.任何一棵二叉树中的每个结点的度都可以小于2

12.一棵二叉树满足下列条件:对任意结点,若存在左、右子树,则其值都小于它的左子树上所有结点的值,而大于右子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。

A.前序 *B.中序 C.后序 D.层次

13.设森林T中有4棵树,结点个数分别是n1、n2、n3、n4,当把森林T转换成一棵二叉树后,根结点的右子树上有( )个结点。

A.n1-1 B.n1 C.n1+n2+n3 *D. n2+n3+n4

14.对含有( )个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同。

A.0 *B.1 C.2 D.不存在这样的二叉树

15.如图6-1所示的二叉树的中序遍历序列是( )。

A.abcdgef *B.dfebagc C.dbaefcg D.defbagc

16.已知某二叉树的后序遍历序列是deacb,中序遍历序列是deabc,它的前序遍历序列是( )。

A.acbed *B.baedc C.dceab D.cedba

17.如果T1是由有序树转化而来的二叉树,那么T中结点的前序就是T1中结点的( )。

*A.前序 B.中序 C.后序 D.层次序

18.某二叉树的前序遍历的结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是( )。

A.bdgcefha B.gdbecfha C.bdgechfa *D.gdbehfca

19.在图6-2中的二叉树中,( )不是完全二叉树。(*C)

20.树最适合用来表示( )。

A.有序数据元素 B.无序数据元素 *C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

21.在计算递归函数时,如不使用递归过程,则一般情况下必须借助于( )数据结构。

*A.栈 B.树 C.双向队列 D.顺序表

22.设二叉树根结点的层次为0,一棵高度为h的满二叉树中的结点个数是( )。

A.2h B.2h-1 C.2h-1 *D.2h+1-1

23.以下说法错误的是( )。

A.存在这样的二叉树,对它采用任何次序的遍历,其结点访问序列均相同 *B.二叉树是树的特殊情形C.由树转换成二叉树,其根结点的右子树总是空的 D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

24.已知一个算式的中缀表达式为a+(b-c)/d,则其后缀表达式是( )。

A.a+(b-c)/d *B.abc-d/+ C.bc-d/a+ D.a+bc-d/

25.按照二叉树的定义,具有4个结点所能构造的不同的二叉树的个数是( )。

A.4 B.8 C.12 *D.14

26.在一棵度为3的树中,度为3的结点的个数为2,度为2的结点的个数为1,则度为0的结点的个数为( )。

A.4 B.5 *C.6 D.7

27.3个结点可构成( )棵不同形态的二叉树。

A.2 B.3 C.4 *D.5

28.哈夫曼树的带权路径长度是( )。

A.所有结点权值之和 *B.所有叶结点带权路径长度之和 C.带权结点的值 D.除根以外所有结点权值之和

29.设有一棵22个结点的完全二叉树,那么整棵二叉树有( )个度为0的结点。

A.6 B.7 C.8 *D.11

30.已知完全二叉树有26个结点,则整棵二叉树有( )个度为1的结点。

A.0 *B.1 C.2 D.13

31.在树的孩子兄弟表示法中,( )操作花时间最多。

A. 求某结点的兄弟 B.求某结点的第i个孩子 *C.求某结点的父结点 D.求树的根结点

32.已知如图6-3所示的哈夫曼树,那么电文CDAA的编码是( )。

A.110100 *B.11011100 C.010110111 D.11111100

33.在n个结点的完全二叉树中,对任一结点i(1≤i≤n),i的左孩子可能是( )。

A.i/2 B.2i+1 *C.2i D.都不是

34.已给出图6-3所示的二叉树,A,B,C,D的权值分别为7,5,2,4,则该树的带权路径长度为( )。

A.46 B.36 *C.35 D.都不是

35.下列叙述中不正确的是( )。

A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时有左右之分 *C.二叉树中必有度为2的结点 D.二叉树中结点最多有两棵子树,并且有左右之分

36.图6-4所示的几种结构中属于树形结构的是( )。(*B)

二、判断题

╳1.二叉树是树的特殊形式。

√2.树和二叉树之间最主要的差别是:二叉树的结点的子树要区分为左右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

√3.一棵有n个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在树的n*d个链域中,有n*(d-1)+1个是空链域,只有n-1个是非空的。

√4.前序遍历树和前序遍历与该树对应的二叉树,其结果相同。

╳5.中序遍历树和中序遍历与该树对应的二叉树,其结果不同。

√6.前序遍历森林和前序遍历与该森林对应的二叉树,其结果相同。

╳7.中序遍历森林和中序遍历与该森林对应的二叉树,其结果不同。

√8.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必须是该子树的前序遍历序列中的最后一个结点。

√9.二叉树中具有两个子女的父结点,在中序遍历序列中,它的后继结点最多只能有一个子女。

╳10.在二叉树中,具有一个子女的父结点,在中序遍历中,它没有后继的子女结点。

╳11.在二叉树中插入结点,该二叉树便不再是二叉树。

╳12.用一维数组存储二叉树时,总是以前序遍历存储结点。

√13.已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。

√14.不使用递归,也可以实现二叉树的前序、中序、后序遍历。

√15.在前序遍历二叉树的序列中,任何结点的子树的所有结点都是直接跟在该结点之后。

╳16.有n个结点的不同二叉树有n!棵。

╳17.在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应做特殊处理。

三、填空题

1.树(及一切树形结构)是一种__层次__结构。在树中,__根_结点没有直接前驱。对树上任一结点x来说,x是它的任一子树的根结点惟一的_双亲_。

2.一棵树上的任何结点(不包括根本身)称为根的__子孙__。若B是A的子孙,则称A是B的__祖先__。

3.二叉树第i(i>0)层上至多有__2i-1__个结点。

4.深度为k(k>0)的二叉树至多有__2k-1__个结点。

5.对任何二叉树,若度为2的节点数为n2,则叶子数n0=__n2+1__。

6.满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树,但反之不然。

7.具有n个结点的完全二叉树的深度为___│log2n│+1___。

8.在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是__ │log2i│ =│ log2j│ ____。9.如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i(0l,则X的双亲PARENT(X)的编号为__│i/2│___。(2)若2i>n,则结点x无__左孩子__且无__右孩子__;否则,X的左孩子LCHILD(X)的编号为__2i __。(3)若2i+1>n,则结点X无__右孩子__;否则,X的右孩子RCHILD(X)的编号为__2i+1__。

10.二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。

11.每个二叉链表还必须有一个指向__根__结点的指针,该指针具有标识二叉链表的作用。

12.对二叉链表的访问只能从___根__指针开始。

13.具有n个结点的二叉树中,一共有__2n__个指针域,其中只有__n-1_个用来指向结点的左右孩子,其余的__n+1__个指针域为NULL。

14.已知二叉树中叶子数为40,仅有一个孩子的结点数为20,则总结点数为__99(40+39+20)___。

15.二叉树有不同的链式存储结构,其中最常用的是_二叉链表___与__三叉链表__。

16.可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。

17.具有100个结点的完全二叉树的深度是__7___。

18.深度为90的满二叉树上,第10层有___512___个结点。

19.在__前序__遍历二叉树的序列中,任何结点的子树上的所有结点都是直接跟在该结点之后。

20.具有n个结点的完全二叉树,若按层次从上到下、从左到右对其编号(根结点为1号),则编号最大的分支结点序号是__│n/2│___,编号最小的分支结点序号是__1_,编号最大的叶结点序号是_n_,编号最小的叶结点序号是__│n/2│+1____。

21.若一棵二叉树的叶子数为n,则该二叉树中左、右子树皆非空的结点个数为__n-1__。

22.任意一棵具有n个结点的二叉树,若它有m个叶子,则该二叉树上度数为1的结点为__n-2m+1__个。23.设有30个值,用它们构造一棵哈夫曼树,则该哈夫曼树中共有___59__个结点。

24.现有按中序遍历二叉树的结果为ABC,有__5___种不同形态的二叉树可以得到这一遍历结果。

25.以数据集{4,5,6,7,10}为叶结点的权值所构造的哈夫曼树的带权路径长度为_63_.

26.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有__16_个叶结点。

27.设树T的度为4,其中度为1、2、3和4的结点个数分别是4、2、1和1,则T中叶结点的个数是__8_。28.如果结点a有三个兄弟,而b是a的双亲,则b的度是__4__。

29.一棵树的形状如图6-5所示,它的根结点是__A_,叶结点是__E,J,K,L,O,P,Q,R,N,I__,结点H的度是

__3__,这棵树的度是_4_,这棵树的深度是__5__,结点F的儿子结点是_J,K__,结点G的父结点是__C__。

30.设结点x有左孩子结点y、右孩子结点z,用三种基本遍历方法得到的遍历序列中x__不一定___是y的前驱,x__不一定__是z的后继,y__一定__是z的前驱(填“一定”,“不”、“不一定”)。

31.在树结构里,有且仅有一个结点没有前驱,称为根。非根结点有且仅有一个_前驱__,且存在一条从根到该结点的__惟一路径__。

32.含有2n个结点的二叉树高度至少是__n+1___,至多是__2n_(仅含根结点的二叉树高度为1)。

33.设高度为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为_2h-1__,至多为__2h-1__。四、应用题

1.分别画出含3个结点的树与二叉树的所有不同形态。

答:略。

2.设在树中,结点x是结点y的双亲,用来表示边。已知一棵树边的集合为:{,,},用树形表示法画出此树,并回答下列问题:

(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些是e的子孙? (6)哪些是f的兄弟? (7)结点b和j的层次各是多少? (8)树的深度是多少? (9)树的度数是多少?答:略。

3.任意一个有n(n>0)个结点的二叉树,已知它有m个叶结点,试证明非叶结点有m-1个度为2,其余度为1。答:设度为1的结点数n1, 设度为2的结点数n2,分支数B,则有:

m+n1+n2=n, B+1=n, B=1*n1+2*n2,即:

m+n1+n2=n, n1+2n2+1=n, 解之可得:n2=m-1

4.分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构。

答:略.

5.分别写出图6-7所示二叉树的前序、中序和后序序列。

答:前序:ABCDEF、中序:CBEFDA和后序:CFEDBA

6.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试画出这棵二叉树,并写出其前序遍历序列。

答:前序遍历序列:ABCDEFGH

7.二叉树中的结点进行按层次顺序(每层自左到右)的访问操作称为二叉树的层次遍历,遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二又树。

答:略.

8.将图6-9所示的森林转换成二叉树。

答:略.

9.分别画出图6-10所示二叉树对应的森林,并写出森林的前序和后序遍历序列。

答:前序:ABDGCEFHIJK,后序:DGBAECIHJKF。

10.设某密码电文由8个字母组成,每个字母在电文中的出现频率分别是7,19,2,6,32,3,21,10,试为这8个字母设计相应的哈夫曼编码。

答:略.

11.将代数式y=3*(x+a)-a/x2描述成表达式树,并写出前缀式和后缀式。

答:前缀式:-*3+xa/a*xx,后缀式:3xa+*axx*/-。

13.试证明:任一棵高度为h>1的二叉树,其内部结点(除根、叶子之外的结点)的数目小于2h-1-1,而叶结点数目小于或等于2h-1。

答:高度为h的满二叉树包含的结点个数最多,最下层是叶子,除根外,其余是内部结点,不包含叶子的子树高度

是h-1,该子树的最多结点数是2h-1-1. 除根外, 内部结点的数目应小于2h-1-1.而整个树所含的最多结点数是2h-1,所以,叶子数最多为2h-1-(2h-1-1)= 2h-1个.

14.编码{00,01,10,11}、{0,1,00,11,}、{0,10,110,111}哪一组不是前缀码?

答:编码{00,01,10,11}、{0,10,110,111}不是前缀码, {0,1,00,11}是前缀码.

15.一棵度为k的树有n1个度为1的结点,n2个度为2的结点,……,nk个度为k的结点,问该树中有多少

个叶结点?

答:n=n0+n1+……+nk=1*n1+2*n2+……k*nk

n0=1+n2+2n3+……+(k-1)nk

软件工程试题及答案34385

软件工程期末试卷(A) 说明:本试卷为04级计算机专业(专升本)软件工程期末试卷,总计100分,时间100分钟 一、选择题:(每题1分,共20分)(将答案写在题号前的()中) ( C )1. 软件是()。 A. 处理对象和处理规则的描述 B. 程序 C. 程序及其文档 D. 计算机系统 ( B )2. 软件需求规格说明的内容不应包括()。 A. 主要功能 B. 算法的详细描述 C. 用户界面及运行环境 D. 软件的性能 ( B )3. 程序的三种基本控制结构是()。 A. 过程、子程序和分程序 B. 顺序、选择和重复 C. 递归、迭代和回溯 D. 调用、返回和转移 ( D) 4. 面向对象的分析方法主要是建立三类模型,即( )。 A) 系统模型、ER模型、应用模型 B) 对象模型、动态模型、应用模型 C) E-R模型、对象模型、功能模型 D) 对象模型、动态模型、功能模型 ( C ) 5. 在E-R模型中,包含以下基本成分( )。 A) 数据、对象、实体 B) 控制、联系、对象 C) 实体、联系、属性 D) 实体、属性、操作 ( A ) 6. 各种软件维护的类型中最重要的是( )。 A) 完善性维护B) 纠错性维护C) 适应性维护D) 预防性维护 ( B ) 7.软件测试的目标是()。 A. 证明软件是正确的 B. 发现错误、降低错误带来的风险 C. 排除软件中所有的错误 D. 与软件调试相同 ( D )8.软件生命周期中所花费用最多的阶段是() A.详细设计 B.软件编码 C.软件测试 D.软件维护 ( C )9.若有一个计算类型的程序,它的输入量只有一个X,其范围是[-1.0, 1.0],现从输入的角度考虑一组测试用例:-1.001, -1.0, 1.0, 1.001.设计这组测试用例的方法是()A.条件覆盖法 B.等价分类法 C.边界值分析法 D.错误推测法 ( D )10、详细设计的基本任务是确定每个模块的( )设计 A.功能 B.调用关系 C.输入输出数据 D.算法 ( A )11.设函数C(X)定义问题X的复杂程序,函数E(X)确定解决问题X需要的工作量(时间)。对于两个问题P1和P2,如果C(P1)>C(P2)显然E(P1)>E(P2),则得出结论E(P1+P2)>E(P1)+E(P2)就是:() A.模块化的根据B.逐步求精的根据C.抽象的根据D.信息隐藏和局部化的根据 ( D )12.下面几种白箱测试技术,哪种是最强的覆盖准则() A.语句覆盖B.条件覆盖C.判定覆盖D.条件组合覆盖

软件工程考试题库

软件工程考试题库 Final approval draft on November 22, 2020

一填空题 1.用原型过程代替全部开发阶段,这种快速原型是(实验型或演化型)原型。 2.可行性研究实质上是进行一种简化、压缩了的(需求分析和设计)。 3.结构图的主要内容有(模块)、(模块的控制关系)、(模块的信息传递)。 4.模块之间的联系越紧密,其耦合性就越(强),模块的独立性就越(差)。 5.软件工程研究的主要内容包括软件开发技术和软件开发管理两个方面,在软件开发技术方面,主要是研究(软件开发方法)、(软件开发过程)、(软件开发工具和环境),在软件开发管理方面,主要是研究(软件管理学)、(软件经济学)、(软件心理学)。 6.状态图反映了(状态)与(事件)的关系,状态图确定了由事件序列引起的(状态序列)。 7.可行性研究实质上是进行一种简化、压缩了的(需求分析和设计)。 8.在数据流图中,(数据流)是数据在系统内传播的路径,因此由一组(成分固定的数据项)组成,加工(又称为数据处理)是对数据流进行某些(操作或交换)。 9.(偶然内聚)指一个模块内的各处理元素之间没有任何联系,这是内聚程度最(差)的内聚。 10假如n个相同的系统(硬件或软件)进行测试,它们的失效时间分别是t1,t2,tn,则平均失效等待时间MTTF=(1/n )。 11(维护申请报告)是一种由用户产生的文档,它用作计划维护任务的基础。 12在软件开发和维护过程中,一个软件往往有许多版本,版本控制工具用来存储、更新、恢复和管理一个软件的(多个版本)。 13软件工具通常由工具、(工具接口)和用户工具三个部分组成。 14类的实例化是(对象)。 15形式化规约语言由(语法)、(语义)和(一组关系)组成。 16 软件质量保证应从(产品计划和设计)开始,直到投入使用和售后服务的软件生存期的每一个阶段中的每一步骤。 17 为了提高软件的质量,软件质量保证的任务大致可归结为以下8类:(正确定义用户要求)、(技术方法的应用)、(提高软件开发的工程能力)、(软件的复用)、(发挥每个开发者的能力)、(组织外部力量协作)、(排除无效劳动)、(提高计划和管理质量)。 18 软件测试时需要的三类信息,分别是(软件配置)、(测试配置)、(测试工具)。 19 在面向对象方法中,信息隐蔽通过对象的(封装性)来实现,类结构分离了(接口)与(实现),从而支持了信息隐蔽。 20 增量模型在开发工程中以一系列(增量方式)开发系统,推迟某阶段的(细节),从而(尽早)产生工作软件。 二选择题 1.(A)是计算机程序及其说明程序的各种文档。 A 软件 B文档 C 数据 D 程序 2.软件生存周期包括可行性分析和项目开发计划、需求分析、概要设计、详细设计、编码、(B)和维护等活动。 A 应用 B 测试 C 检测 D 以上答案都不正确 3.建立原型的目的不同,实现原型的途径也有所不同,下列不正确的类型是(B)。 A 用于验证软件需求的原型 B 垂直原型 C 用于验证设计方案的原型 D 用于演化出目标系统的原型

常用工具软件课后习题及答案

模块一工具软件概述 一、选择题 1. 以下哪一种软件属于系统软件( B ) A. 办公软件 B. 操作软件 C. 图形图像软件 D. 多媒体软件 2. 以下哪一种软件不属于办公软件( A ) A. MySQL Server B. 金山WPS C. 永中Office D. 红旗贰仟RedOffice 3. 以下哪一种软件版本不属于正在测试的版本( C ) A. Alpha版 B. Beta版 C. Cardware版 D. Demo版 4. 以下哪一种软件授权允许用户自行修改源代码( D ) A. 商业软件 B. 共享软件 C. 免费软件 D. 开源软件 5. 保护软件知识产权的目的不包括(D)。C A. 鼓励科学技术创新 B. 保护行业健康发展 C.与国际接轨 D. 保护消费者的利益 二、思考题 1.系统软件都包括哪些类别为每个类别举出一个实例。 【参考答案】系统软件的作用是协调各部分硬件的工作,并为各种应用软件提供支持,使计算机用户和其他软件将计算机当作一个整体,不需要了解计算机底层的硬件工作内容,即可使用这些硬件实现各种功能。系统软件主要包括操作系统和一些基本的工具软件。 (1)操作系统,如Windows XP (2)编译软件,又被称作集成开发环境,如Microsoft Visual Studio (3)其他系统软件,除了操作系统和编译软件外,如Windows优化大师、Norton Ghost、 【参考答案】版本号就是版本的标识号。每一个软件都有一个版本号。版本号能使用户了解所使用的软件是否为最新的版本以及它所提供的功能与设施。每一个版本号可以分为主版本号与次版本号两部分。目前流行的版本号主要包括3种风格。 ① GNU(一种开源和自由软件的计划)风格 版本号格式:主版本号.子版本号[.修正版本号[编译版本号]] 示例 : , build-13124。 ② Windows风格 版本号格式:主版本号.子版本号[修正版本号[.编译版本号]] 示例 :如 2build-3300 ③ .NET Framework风格 版本号格式:主版本号.子版本号[.编译版本号[.修正版本号]] 示例 : 3.大多数软件在安装过程中都包括哪些步骤 【参考答案】在获取软件之后,即可安装软件。在Windows操作系统中,工具软件的安装通常都是通过图形化的安装向导进行的。用户只需要在安装向导的过程中设置一些相关的选项即可。大多数软件的安装都会包括确认用户协议、选择安装路径、选择软件组件、安装 【参考答案】专有软件,又称非自由软件、专属软件、私有软件等,是指由开发者开发

软件工程习题及答案

软件工程习题及答案 一、选择题: 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、1/6 B、1/5 C、1/4 D、1/3 7. 变换型和事务型是程序结构的标准形式。从某处获得数据,再对这些数据作处理,然后将结果送出是属于。 A、变换型 B、事务型 8. PAD(Problem Analysis Diagram)图是一种工具。 A、系统描述 B、详细设计 C、测试 D、编程辅助 9. 分层数据流图是一种比较严格又易于理解的描述方式,它的顶层描绘了系统的。 A、总貌 B、细节 C、抽象 D、软件的作者 10. 数据流图中,当数据流向或流自文件时,。 A、数据流要命名,文件不必命名 B、数据流不必命名,有文件名就足够了 C、数据流和文件均要命名,因为流出和流进数据流是不同的 D、数据流和文件均不要命名,通过加工可自然反映出 11. 分析员是。 A、用户中系统的直接使用者 B、用户和软件人员的中间人 C、软件的编程人员 D、用户和软件人员的领导 12. 在软件开发中,有利于发挥集体智慧的一种做法是。

软件工程试题及答案

4. 面向对象的分析方法主要是建立三类模型,即( D )。 A) 系统模型、ER模型、应用模型 B) 对象模型、动态模型、应用模型 C) E-R模型、对象模型、功能模型D) 对象模型、动态模型、功能模型 5. 在E-R模型中,包含以下基本成分( )。 A) 数据、对象、实体B) 控制、联系、对象C) 实体、联系、属性 D) 实体、属性、操作 9.若有一个计算类型的程序,它的输入量只有一个X,其范围是[, ],现从输入的角度考虑一组测试用例:, , , . 设计这组测试用例的方法是( c ) A.条件覆盖法 B.等价分类法C.边界值分析法 D.错误推测法 10、详细设计的基本任务是确定每个模块的( d )A.功能B.调用关系C.输入输出数据 D.算法 11.设函数C(X)定义问题X的复杂程序,函数E(X)确定解决问题X需要的工作量(时间)。对于两个问题P1和P2,如果C(P1)>C(P2)显然E(P1)>E(P2),则得出结论E(P1+P2)>E(P1)+E(P2)就是:( a ) A.模块化的根据 B.逐步求精的根据 C.抽象的根据 D.信息隐藏和局部化的根据13.面向数据流的设计方法把( D )映射成软件结构。 A.数据流 B.系统结构 C.控制结构 D.信息流 14.内聚程度最低的是( A.偶然 )内聚A.偶然 B.过程 C.顺序 D.时间 15.确定测试计划是在( D )阶段制定的.A.总体设计 B.详细设计 C.编码 D.测试 16.需求分析的产品是( D ) A.数据流程图案 B.数据字典 C.判定表D.需求规格说明书 17.数据字典是软件需求分析阶段的最重要工具之一,其最基本的功能是( C ) A.数据库设计 B.数据通信 C.数据定义 D.数据维护 18.( D )引入了“风险驱动”的思想,适用于大规模的内部开发项目。 A.增量模型 B.喷泉模型 C.原型模型D.螺旋模型 (×)2、系统测试的主要方法是白盒法,主要进行功能测试、性能测试、安全性测试及可靠性等测试。 (×)4、软件需求分析的任务是建立软件模块结构图。 (√)5、尽可能使用高级语言编写程序(×)6、以结构化分析方法建立的系统模型就是数据流图。 (×)7、进行总体设计时加强模块间的联系。(×)8、编码时尽量多用全局变量. (√)9、用CASE环境或程序自动生成工具来自动生成一部分程序.(×)10、软件测试是要发现软件中的所有错误。 1. 软件生命期各阶段的任务是什么答:软件生命期分为7个阶段:1、问题定义:要解决的问题是什么 2、可行性研究:确定问题是否值得解,技术可行性、经济可行性、操作可行性 3、需求分析:系统必须做什么 4、总体设计:系统如何实现,包括系统设计和结构设计 5、详细设计:具体实现设计的系统 6、实现:编码和测试 7、运行维护:保证软件正常运行。 2、软件重用的效益是什么?

软件工程考试题库

软件工程概述 一单项选择 1.软件生命周期一般包括:软件开发期和软件运行期,下述(D)不是软件开发期所应包含的内容。 A需求分析B结构设计C程序编制D软件维护 2.软件是一种逻辑产品,它的开发主要是(A)。 A研制B拷贝C再生产D复制 3.以文档作为驱动,适合于软件需求很明确的软件项目的生存周期模型是(C)。 A喷泉模型B增量模型C瀑布模型D螺旋模型 4.在软件生存周期中,(B)阶段必须要回答的问题是“要解决的问题是做什么?”。 A详细设计B可行性分析和项目开发计划C概要设计D软件测试 5.软件产品与物质产品有很大区别,软件产品是一种(C)产品 A有形B消耗C逻辑D文档 6.(C)把瀑布模型和专家系统结合在一起,在开发的各个阶段上都利用相应的专家系统来帮助软件人员完成开发工作。 A原型模型B螺旋模型C基于知识的智能模型D喷泉模型 7.(B)阶段是为每个模块完成的功能进行具体的描述,要把功能描述转变为精确的、结构化的过程描述。 A概要设计B详细设计C编码D测试 8.下列软件开发模型中,适合于那些不能预先确切定义需求的软件系统的开发的模型是(A)。 A原型模型B瀑布模型C基于知识的智能模型D变换模型 9.下列软件开发模型中,以面向对象的软件开发方法为基础,以用户的需求为动力,以对象来驱动的模型是(C)。 A原型模型B瀑布模型C喷泉模型D螺旋模型 10.下列软件开发模型中,支持需求不明确,特别是大型软件系统的开发,并支持多种软件开发方法的模型是(D)。 A原型模型B瀑布模型C喷泉模型D螺旋模型 11.软件特性中,使软件在不同的系统约束条件下,使用户需求得到满足的难易程度称为(C)。 A可修改性B可靠性C可适应性D可重用性 12.软件特性中,一个软件能再次用于其他相关应用的程度称为(B)。 A可移植性B可重用性C容错性D可适应性 13.软件特性中,(A)是指系统具有清晰的结构,能直接反映问题的需求的程度。 A可理解性B可靠性C可适应性D可重用性 14.软件特性中,软件产品交付使用后,在实现改正潜伏的错误、改进性能、适应环境变化等方面工作的难易程度称为(B)。 A可理解性B可维护性C可适应性D可重用性 15.软件特性中,软件从一个计算机系统或环境移植到另一个上去的难易程度指的是(C). A可理解性B可修改性C可移植性D可重用性 16.软件特性中,在给定的时间间隔内,程序成功运行的概率指的是(D)。 A有效性B可适应性C正确性D可靠性 17.软件特性中,允许对软件进行修改而不增加其复杂性指的是(A)。 A可修改性B可适应性C可维护性D可移植性 18.软件特性中,多个软件元素相互通讯并协同完成任务的能力指的是(B)。 A可理解性B可互操作性C可维护性D可追踪性 19.软件特性中,根据软件需求对软件设计、程序进行正向追踪,或根据程序、软件设计对软件需求进行逆向

计算机硬件和计算机软件习题及答案

计算机硬件和计算机软件习题及答案 一、单选题 1. 硬件系统由五大功能部件组成,即运算器、控制器、______、输入设备和输出设备。 A 存储器 B 处理器 C 输入设备 D 输出设备 2. ______是计算机的指挥中心。它的功能是取出指令、翻译并分析指令、将指令转化为各种电信号,从而使各个部件协同工作。 A 处理器 B 控制器 C 运算器 D 存储器 3. 总线是各个部件共享的传输介质,它由许多______和相关的控制电路组成,也是计算机系统中的一个比较复杂的部件。 A 传输电路 B 传输线 C 传输电缆 D 传输光缆 4. 按照总线中传输的信息的不同,系统总线分为地址总线、数据总线、______三类。 A 信息总线 B 通信总线 C 指令总线 D 控制总线 5. CPU是计算机系统的核心部件。它的主要任务是执行指令,它按照指令的要求完成对数据的运算和处理。CPU主要由运算器、控制器和______三部分组成。 A 存储器 B 缓冲器 C 寄存器组 D 译码器 6. 只读存储器(Reading Only Memory ,ROM)。它的特点是______,是能够永久性(或半永久性)地保存存储信息的存储器,属于非易失性存储器件,通常用来储存那些经常使用的固定不变的程序和数据。 A 只能读不能写、断电信息不消失 B 只能读不能写、断电信息消失 C 不能读只能写、断电信息不消失 D 既能读又能写、断电信息不消失 7. 读写存储器(Random access Memory ,RAM),它的特点是______,属于易失性存储器件,用来储存平常那些可以发生改变的程序和数据。 A 既能读又能写、断电信息不消失 B 既能读也能写、断电后信息会消失 C 只能读不能写、断电信息不消失 D 只能读不能写、断电信息消失 8. 辅助存储器也称为外部存储器。与内存相比,具有______、速度慢、成本低、可以脱机保存信息的特点。 A 效率低 B 技术含量高 C 容量大 D 容量小 9. 光盘存储器由光盘和光盘驱动器组成,按照其存取方式分为只读型和可记录型,按照记录

软件工程习题及答案

软件工程习题及答案

软件工程习题及答案 一、选择题: 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、1/6 B、1/5 C、1/4 D、1/3 7. 变换型和事务型是程序结构的标准形式。从某处获得数据,再对这些数据作处理,然后将结果送出是属于。 A、变换型 B、事务型 8. PAD(Problem Analysis Diagram)图是一种工具。 A、系统描述 B、详细设计 C、测试 D、编程辅助 9. 分层数据流图是一种比较严格又易于理解的描述方式,它的顶层描绘了系统的。 A、总貌 B、细节 C、抽象 D、软件的作者 10. 数据流图中,当数据流向或流自文件时,。 A、数据流要命名,文件不必命名 B、数据流不必命名,有文件名就足够了 C、数据流和文件均要命名,因为流出和流进数据流是不同的 D、数据流和文件均不要命名,通过加工可自然反映出

《软件工程》试题及参考答案(第6套)

第一部分选择题 一、单项选择题(本大题共20小题,每小题1分,共20分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1、()是软件生存期中的一系列相关软件工程活动的集合,它由软件规格说明、软件设计与开发、软件确认、软件改进等活动组成。 A 软件过程 B 软件工具 C 质量保证 D 软件工程 2、在各种不同的软件需求中,功能需求描述了用户使用产品必须要完成的任务,可以在用例模型或方案脚本中予以说明,()是从各个角度对系统的约束和限制,反映了应用对软件系统质量和特性的额外要求。 A 业务需求 B 功能要求 C 非功能需求 D 用户需求 3、软件测试计划开始于需求分析阶段,完成于()阶段。 A 需求分析 B 软件设计 C 软件实现 D 软件测试 4.下面关于面向对象方法中消息的叙述,不正确的是( )。 A. 键盘、鼠标、通信端口、网络等设备一有变化,就会产生消息 B.操作系统不断向应用程序发送消息,但应用程序不能向操作系统发送消息 C. 应用程序之间可以相互发送消息 D.发送与接收消息的通信机制与传统的子程序调用机制不同 5.美国卡内基—梅隆大学SEI提出的CMM模型将软件过程的成熟度分为5个等级,以下选项中,属于可管理级的特征是( )。 A.工作无序,项目进行过程中经常放弃当初的计划 B.建立了项目级的管理制度 C.建立了企业级的管理制度 D.软件过程中活动的生产率和质量是可度量的 6.在McCall软件质量度量模型中,()属于面向软件产品修改。 A.可靠性B.可重用性C.适应性 D.可移植性 7.软件生命周期中所花费用最多的阶段是() A.详细设计 B.软件编码 C.软件测 试 D.软件维护 8.需求分析阶段的任务是确定() A.软件开发方法 B.软件开发工具 C.软件开发费 D.软件系统的功能

软件工程题库

软件工程单元一(概述) 一单项选择 1.软件是一种逻辑产品,它的开发主要是(A )。 A研制B拷贝C再生产D复制 2.软件生命周期一般包括:软件开发期和软件运行期,下述(D )不是软件开发期所应包含的内容。 A需求分析 B 结构设计C程序编制D软件维护 3.以文档作为驱动,适合于软件需求很明确的软件项目的生存周期模型是( C )。 A喷泉模型 B 增量模型C瀑布模型D螺旋模型 4.在软件生存周期中,(B )阶段必须要回答的问题是“要解决的问题是做什么?”。 A详细设计 B 可行性分析和项目开发计划C概要设计D软件测试 5.软件产品与物质产品有很大区别,软件产品是一种(C )产品 A有形 B 消耗C逻辑D文档 6.(C )把瀑布模型和专家系统结合在一起,在开发的各个阶段上都利用相应的专家系统来帮助软件人员完成开发工作。 A 原型模型 B 螺旋模型 C 基于知识的智能模型 D 喷泉模型 7.( B )阶段是为每个模块完成的功能进行具体的描述,要把功能描述转变为精确的、结构化的过程描述。A概要设计 B 详细设计 C 编码 D 测试 8.下列软件开发模型中,适合于那些不能预先确切定义需求的软件系统的开发的模型是(A )。 A 原型模型 B 瀑布模型 C 基于知识的智能模型 D 变换模型 9.下列软件开发模型中,以面向对象的软件开发方法为基础,以用户的需求为动力,以对象来驱动的模型是( C )。 A 原型模型 B 瀑布模型 C 喷泉模型 D 螺旋模型 10.下列软件开发模型中,支持需求不明确,特别是大型软件系统的开发,并支持多种软件开发方法的模型是(D )。 A 原型模型 B 瀑布模型 C 喷泉模型 D 螺旋模型 11.软件特性中,使软件在不同的系统约束条件下,使用户需求得到满足的难易程度称为(C )。 A可修改性B可靠性C可适应性 D 可重用性 12.软件特性中,一个软件能再次用于其他相关应用的程度称为(B )。 A可移植性B可重用性 C 容错性 D 可适应性 13.软件特性中,(A )是指系统具有清晰的结构,能直接反映问题的需求的程度。 A可理解性B可靠性C可适应性 D 可重用性 14.软件特性中,软件产品交付使用后,在实现改正潜伏的错误、改进性能、适应环境变化等方面工作的难易程度称为(B )。 A可理解性 B 可维护性C可适应性 D 可重用性 15.软件特性中,软件从一个计算机系统或环境移植到另一个上去的难易程度指的是(C ). A可理解性B可修改性C可移植性 D 可重用性 16.软件特性中,在给定的时间间隔内,程序成功运行的概率指的是( D )。 A有效性B可适应性C正确性 D 可靠性 17.软件特性中,允许对软件进行修改而不增加其复杂性指的是(A )。 A可修改性B可适应性C可维护性 D 可移植性 18.软件特性中,多个软件元素相互通讯并协同完成任务的能力指的是(B )。 A可理解性B可互操作性C可维护性 D 可追踪性 19.软件特性中,根据软件需求对软件设计、程序进行正向追踪,或根据程序、软件设计对软件需求进行逆向追踪的能力指的是(C )。 A 可理解性 B 可互操作性C可追踪性 D 可维护性 20.软件的可修改性支持软件的(D )。 A 有效性 B 可互操作性C可追踪性 D 可维护性 21.软件的可移植性支持软件的(A )。 A 可适应性 B 可互操作性C可追踪性 D 有效性 22.软件的可理解性支持软件的(B )。

常用工具软件考试题及答案

一.判断题(每小题1分,共10分) 3. 压缩文件管理工具WinRAR只能压缩文件,不能对文件进行解压。(错) 4. Internet上所有电子邮件用户的E-mail地址都采用同样的格式:用户名@主机名。(对) 5. Adobe Acrobat Reader可以解压缩文件。(错) 6. ACDSee是目前最流行的数字图像处理软件,它能广泛应用于图片的获取、管理、浏览、优化,甚至和他人的分享。(对) 10. 系统长时间使用之后,会留下一堆堆垃圾文件,使系统变得相当臃肿,运行速度大为下降,但是系统不会频繁出错甚至死机。(对) 二.选择题(每小题2分,共40分) 1、下列不属于媒体播放工具的是() A、暴风影音 B、千千静听 C、Realone Player D、WinRAR 2、以下几种方法中()不能正常退出工具软件。 A、执行【文件】︱【关闭】命令 B、双击标题栏左侧的系统标 C、单击标题栏右侧的关闭按钮 D、双击标题栏 3、CuteFTP具有网际快车不具备的功能是:() A、视频播放 B、下载文件 C、断点续传 D、上传文件 4、WinRAR不可以解压下列哪些格式的文件() A、RAR B、ZIP C、CAB D、RSB 5、Adobe Acrobat ReadeR可以阅读的文件格式() A、doc B、pdf C、dbf D、txt 6、ACDSee不能对图片进行下列哪种操作() A、浏览和编辑图像 B、图片格式转换 C、抓取图片 D、设置墙纸和幻灯片放映 7、Windows优化大师提供的文件系统优化功能包括() ①优化磁盘缓存②优化桌面菜单③优化文件系统。 A、①② B、②③ C、①②③ D、①③ 8、关于Symantec Ghost软件,下列说法中错误的是:() A、可以创建硬盘镜像备份文件 B、备份恢复到原硬盘上 C、不支持UNIX系统下的硬盘备份 D、支持FAT16/32、NTFS、OS/2等多种分区的硬盘备份 10、分区魔术师PartitionMagic不具有的功能是( )。 A、创建系统备份 B、创建新分区 C、调整分区大小 D、合并分区 11、下列哪一个软件属于光盘刻录软件( A ) A、Nero-Buring Room B、Virtual CD C、DAEMON Tools D、Iparmor 15、用ACDSee浏览和修改图像实例时,用户可以对图片进行修改的类型为() A、颜色、透明度 B、颜色、形状及文件格式 C、颜色、透明度、形状及文件格式 D、透明度、形状及文件格式 17、不属于计算机病毒的特征是:() A、破坏性 B、潜伏性 C、隐蔽性 D、预知性 20、关于Windows优化大师说法不正确的是:( C ) A、可检测硬件信息 B、可备份系统驱动 C、可制作引导光盘镜像文件 D、可清理系统垃圾 三.填空题(每小题2分,共20分) 1、根据工具软件使用的领域不同,但是一般都包含有标题栏、菜单栏、( )、状态栏、工作区。 2、在进行实验操作时,为了不破坏现有的操作系统以及相关设置,我们可以使用()软件。 3、在使用虚拟机的时候,按键盘右边的()可以在虚拟机和宿主机之间切换。 4、CuteFTP是一个基于()客户端软件。 5、虚拟光驱是一种模拟()工作的工具软件,它能在操作系统中模拟出新的光盘驱动器,是对物理光驱的一种仿真。 6、利用()可以备份windows操作系统。 7、常见的压缩格式ZIP格式、()、CBA格式、ACE格式。 8、利用()软件可以上传网站文件。 9、Deamon Tools是一个优秀的( )工具。 10、虚拟光驱工具可以将光盘文件复制到硬盘上并虚拟成( )。 四、简答题(每小题10分、共30分)。 1、Ghost目前可以作哪些备份操作? 1,可以进行分区间的备份 2,可以进行硬盘对硬盘间的备份 3,可以通过网络进行多机备份 3、列举出一些常用的磁盘操作工具及其主要功能(最少列出四个)? 1、分区魔术师,对硬盘进行分区操作 2、Ghost克隆软件,对系统备份及还原操作 3、光盘虚拟工具,对光盘文件进行虚拟操作 4、光盘刻录工具,对数据文件进行刻录

软件工程试题及答案

综合练习一答案 一.选择题: 1.软件危机出现于____,为了解决软件危机,人们提出了用____的原理来设计软件,这是软件工程诞生的基础。 A.50年代末 B.60年代初C.60年代末 D.70年代初 A.运筹学B.工程学 C.软件学 D.软件学 E.数字 2.开发软件需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称作____。 A.软件投机B.软件危机C.软件工程D.软件产生 3.产生软件危机的原因有如下几点,除了______。 A、软件开发过程未经审查 B、软件开发不分阶段,开发人员没有明确的分工 C、所开发的软件,除了程序清单外,没有其他文档 D、采用工程设计的方法开发软件,不符合软件本身的特点 4.软件工程学是应用科学理论和工程上的技术指导软件开发的学科,其目的是____。 A.引入新技术提高空间利用率B.用较少的投资获得高质量的软件 C.缩短研制周期扩大软件功能D.硬软件结合使系统面向应用 5.请按顺序写出软件生命期的几个阶段____,____ ,____,____,____,____。 A.维护 B.测试 C.详细设计 D.概要设计 E.编码 F.需求分析6.瀑布模型把软件生存周期划分为软件定义、软件开发和____三个阶段,而每一阶段又可细分为若干个更小的阶段。 A.详细设计B.可行性分析C.运行及维护D.测试与排错7.划分软件生存周期的阶段时所应遵循的基本原则是_____。 A、各阶段的任务尽可能相关性 B、各阶段的任务尽可能相对独立 C、各阶段的任务在时间上连续 D、各阶段的任务在时间上相对独立 8.一个软件项目是否进行开发的结论是在______文档中作出的。 A、软件开发计划 B、可行性报告 C、需求分析说明书 D、测试报告 9.分析员是____。 A.用户中系统的直接使用者B.用户和软件人员的中间人 C.软件的编程人员 D。用户和软件人员的领导 10.下列叙述中,_______不属于数据字典的作用。 A、作为编码阶段的描述工具 B、为用户与开发人员之间统一认识 C、作为概要设计的依据 D、为需求分析阶段定义各类条目 11.使用结构化分析方法时,采用的基本手段是____。 A.分解和抽象 B.分解和综合C.归纳与推导D.试探与回溯12.结构化系统分析主要是通过____进行分析的。 A.算法分解B.控制结构分解 C.数据结构分解D.处理功能分解13.分层数据流图是一种比较严格又易于理解的描述方式,它的顶层描述了系统的____。 总貌B.细节C.抽象D.软件的作者 13.变换型和事务型是程序结构的标准形式。从某处获得数据,再对这些数据作处理,然后将结果送出是属于____。 A.变换型 B 事务型 14.需求分析说明书不能作为______。

软件工程考试题(带答案)..

一、选择题 1.软件开发瀑布模型中的软件定义时期各个阶段依次是:(B) A) 可行性研究,问题定义,需求分析。 B) 问题定义,可行性研究,需求分析。 C) 可行性研究,需求分析,问题定义。 D) 以上顺序都不对。 2.可行性研究主要从以下几个方面进行研究:(A) A)技术可行性,经济可行性,操作可行性。 B)技术可行性,经济可行性,系统可行性。 C)经济可行性,系统可行性,操作可行性。 D)经济可行性,系统可行性,时间可行性。 3 耦合是对软件不同模块之间互连程度的度量。各种耦合按从强到弱排列如下:(C) A) 内容耦合,控制耦合,数据耦合,公共环境耦合。 B) 内容耦合,控制耦合,公共环境耦合,数据耦合。 C) 内容耦合,公共环境耦合,控制耦合,数据耦合。 D) 控制耦合,内容耦合,数据耦合,公共环境耦合。4.在详细设计阶段所使用到的设计工具是:(A) A) 程序流程图,PAD图,N-S图,HIPO图,判定表, 判定树. B) 数据流程图,Yourdon 图,程序流程图,PAD图, N-S图,HIPO图。 C) 判定表,判定树,PDL,程序流程图,PAD图,N- S图。 D) 判定表,判定树,数据流程图,系统流程图,程序 流程图,层次图。 5 按照软件工程的原则,模块的作用域和模块的控制域之间的关系

是:(A) A)模块的作用域应在模块的控制域之内。 B)模块的控制域应在模块的作用域之内。 C)模块的控制域与模块的作用域互相独立。 D)以上说法都不对。 6在软件生命周期中,能准确确定软件系统的体系结构的功能阶段是(C) A.概要设计 B.详细设计 C.需求分析 D.可行性分析 7下面不是软件工程的3个要素的是(C) A过程 B.方法 C.环境 D.工具 8.下面不属于软件的组成的是(B) A程序 B.记录 C.文档 D.数据 9在瀑布模型中,将软件分为若干个时期,软件项目的可行性研究一般归属于(C) A.维护时期 B.运行时期 C.定义时期 D.开发时期 10.在瀑布模型中,下面(C)是其突出的缺点。 A.不适应平台的变动 B.不适应算法的变动 C.不适应用户需求的变动 D.不适应程序语言的变动 11下面不属于软件的特点的是(D)。 A软件是一种软件产品 B软件产品不会用坏,不存在磨损、消耗问题 C软件产品的生产主要是研制 D软件产品非常便宜 12 软件开发工具是协助开发人员进行软件开发活动所使用的软件或环境。下面不是软件开发工具的是(A)。

软件工程试题及答案(B)

B卷 一、选择题(每题2分,共40分) 1.软件项目的可行性研究要进行一次( C )需求分析。 A.详细的B.全面的C.简化的、压缩的D.彻底的 2、系统流程图用于可行性分析中的( A )的描述。 A.当前运行系统B.当前逻辑模型C.目标系统D.新系统 3、程序的三种基本控制结构的共同特点是( D ) A.不能嵌套使用B.只能用来写简单程序 C.已经用硬件实现D.只有一个入口和一个出口 4、维护中,因误删除一个标识符而引起的错误是( C )副作用。 A.文档B.数据C.编码D.设计 5、( D )是以提高软件质量为目的的技术活动。 A.技术创新B.测试C.技术创造D.技术评审 6、面向对象方法学的出发点和基本原则是尽可能模拟人类习惯的思维方式,分析、设计和 实现一个软件系统的方法和过程,尽可能接近于人类认识世界解决问题的方法和过程。因此面向对象方法有许多特征,如软件系统是由对象组成的;( C );对象彼此之间仅能通过传递消息互相联系;层次结构的继承。 A.开发过程基于功能分析和功能分解B.强调需求分析重要性 C.把对象划分成类,每个对象类都定义一组数据和方法D.对既存类进行调整 7、原型化方法是用户和设计者之间执行的一种交互构成,适用于( A )系统。 A.需求不确定性高的B.需求确定的C.管理信息D.实时 8、为了提高测试的效率,应该( D )。 A.随机地选取测试数据B.取一切可能的输入数据作为测试数据

C.在完成编码以后制定软件的测试计划D.选择发现错误可能性大的数据作为测试数据 9、使用白盒测试方法时,确定测试数据应根据( A )和指定的覆盖标准。 A.程序的内部逻辑B.程序的复杂结构C.使用说明书D.程序的功能 10、开发软件所需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称做( C ) A.软件工程 B.软件周期 C.软件危机 D.软件产生 11、软件按照设计的要求,在规定时间和条件下达到不出故障,持续运行的要求的质量特性 称为( B )。 A.可用性 B.可靠性 C.正确性 D.完整性 12、瀑布模型的关键不足在于( B ) A.过于简单 B.不能适应需求的动态变更 C.过于灵活 D.各个阶段需要进行评审 13、软件维护的副作用主要有以下哪几种( C ) A.编码副作用、数据副作用、测试副作用 B.编码副作用、数据副作用、调试副作用 C.编码副作用、数据副作用、文档副作用 D.编码副作用、文档副作用、测试副作用 14、在下面的软件开发方法中,哪一个对软件设计和开发人员的开发要求最高( B)。 A、结构化方法 B、原型化方法 C、面向对象的方法 D、控制流方法 15、软件工程方法学的目的是:使软件生产规范化和工程化,而软件工程方法得以实施的主 要保证是( C)。 A、硬件环境 B、软件开发的环境 C、软件开发工具和软件开发的环境 D、开发人员的 素质 16、软件开发模型是指软件开发的全部过程、活动和任务的结构框架。主要的开发模型有瀑 布模型、演化模型、螺旋模型、喷泉模型和智能模型。螺旋模型将瀑布模型和演化模型相结合,并增加了(1),它建立在(2)的基础上,沿着螺线自内向外每旋转一圈,就得到(2)的一个新版本。喷泉模型描述了(3)的开发模型,它体现了这种开发方法创建软件的过程所固有的(4)和(5)的特征。 B(1) A、系统工程 B、风险分析 C、设计评审 D、进度控制 D(2) A、模块划分 B、子程序分解 C、设计; D、原型 A(3) A、面向对象 B、面向数据流 C、面向数据结构 D、面向事件驱动 D(4) A、归纳 B、推理 C、迭代 D、递归 A(5) A、开发各阶段之间无“间隙” B、开发各阶段分界明显 C、部分开发阶段分界明显 D、开发过程不分段 二、判断题(每题2分,共30分) 1.螺旋模型是在瀑布模型和增量模型的基础上增加了风险分析活 动。( T ) 2.数据字典是对数据流图中的数据流,加工、数据存储、数据的源和终点进行详细定义。 ( F ) 3.JAVA语言编译器是一个CASE工具。( T )。

软件工程试题库集及答案

综合练习一答案 选择题: 1.软件危机出现于____,为了解决软件危机,人们提出了用____的原理来设计软件,这是软件工程诞生的基础。 A.50年代末B.60年代初C.60年代末D.70年代初 A.运筹学B.工程学C.软件学D.软件学E.数字2.开发软件需高成本和产品的低质量之间有着尖锐的矛盾,这种现象称作____。 A.软件投机B.软件危机C.软件工程D.软件产生 3.产生软件危机的原因有如下几点,除了______。 A、软件开发过程未经审查 B、软件开发不分阶段,开发人员没有明确的分工 C、所开发的软件,除了程序清单外,没有其他文档 D、采用工程设计的方法开发软件,不符合软件本身的特点 4.软件工程学是应用科学理论和工程上的技术指导软件开发的学科,其目的是____。 A.引入新技术提高空间利用率B.用较少的投资获得高质量的软件 C.缩短研制周期扩大软件功能D.硬软件结合使系统面向应用5.请按顺序写出软件生命期的几个阶段____,____ ,____,____,____,____。 A.维护B.测试C.详细设计D.概要设计E.编码F.需求分析6.瀑布模型把软件生存周期划分为软件定义、软件开发和____三个阶段,而每一阶段又可细分为若干个更小的阶段。 A.详细设计B.可行性分析C.运行及维护D.测试与排错7.划分软件生存周期的阶段时所应遵循的基本原则是_____。 A、各阶段的任务尽可能相关性 B、各阶段的任务尽可能相对独立 C、各阶段的任务在时间上连续 D、各阶段的任务在时间上相对独立 8.一个软件项目是否进行开发的结论是在______文档中作出的。 A、软件开发计划 B、可行性报告 C、需求分析说明书 D、测试报告 9.分析员是____。 A.用户中系统的直接使用者B.用户和软件人员的中间人 C.软件的编程人员D。用户和软件人员的领导

软件工程题库

软件工程题库 一单项选择 1.软件是一种逻辑产品,它的开发主要是(A )。 A研制B拷贝C再生产D复制 2.软件生命周期一般包括:软件开发期和软件运行期,下述(D )不是软件开发期所应包含的内容。 A需求分析 B 结构设计C程序编制D软件维护 3.以文档作为驱动,适合于软件需求很明确的软件项目的生存周期模型是( C )。 A喷泉模型 B 增量模型C瀑布模型D螺旋模型 4.在软件生存周期中,(B )阶段必须要回答的问题是“要解决的问题是做什么?”。 A详细设计 B 可行性分析和项目开发计划C概要设计D软件测试 5.软件产品与物质产品有很大区别,软件产品是一种(C )产品 A有形 B 消耗C逻辑D文档 6.(C )把瀑布模型和专家系统结合在一起,在开发的各个阶段上都利用相应的专家系统来帮助软件人员完成开发工作。 A 原型模型 B 螺旋模型 C 基于知识的智能模型 D 喷泉模型 7.( B )阶段是为每个模块完成的功能进行具体的描述,要把功能描述转变为精确的、结构化的过程描述。A概要设计 B 详细设计 C 编码 D 测试 8.下列软件开发模型中,适合于那些不能预先确切定义需求的软件系统的开发的模型是(A )。 A 原型模型 B 瀑布模型 C 基于知识的智能模型 D 变换模型 9.下列软件开发模型中,以面向对象的软件开发方法为基础,以用户的需求为动力,以对象来驱动的模型是( C )。 A 原型模型 B 瀑布模型 C 喷泉模型 D 螺旋模型 10.下列软件开发模型中,支持需求不明确,特别是大型软件系统的开发,并支持多种软件开发方法的模型是( D )。 A 原型模型 B 瀑布模型 C 喷泉模型 D 螺旋模型 11.软件特性中,使软件在不同的系统约束条件下,使用户需求得到满足的难易程度称为(C )。 A可修改性B可靠性C可适应性 D 可重用性 12.软件特性中,一个软件能再次用于其他相关应用的程度称为(B )。 A可移植性B可重用性 C 容错性 D 可适应性 13.软件特性中,(A )是指系统具有清晰的结构,能直接反映问题的需求的程度。 A可理解性B可靠性C可适应性 D 可重用性 14.软件特性中,软件产品交付使用后,在实现改正潜伏的错误、改进性能、适应环境变化等方面工作的难易程度称为( B )。 A可理解性 B 可维护性C可适应性 D 可重用性 15.软件特性中,软件从一个计算机系统或环境移植到另一个上去的难易程度指的是(C ). A可理解性B可修改性C可移植性 D 可重用性 16.软件特性中,在给定的时间间隔内,程序成功运行的概率指的是( D )。 A有效性B可适应性C正确性 D 可靠性 17.软件特性中,允许对软件进行修改而不增加其复杂性指的是(A )。 A可修改性B可适应性C可维护性 D 可移植性 18.软件特性中,多个软件元素相互通讯并协同完成任务的能力指的是(B )。 A可理解性B可互操作性C可维护性 D 可追踪性 19.软件特性中,根据软件需求对软件设计、程序进行正向追踪,或根据程序、软件设计对软件需求进行

相关文档