《软件技术基础》复习思考题.ppt

《软件技术基础》复习思考题.ppt

《《软件技术基础》复习思考题.ppt》由会员分享，可在线阅读，更多相关《《软件技术基础》复习思考题.ppt（125页珍藏版）》请在冰点文库上搜索。

软件技术基础,电子教案,复习思考题,2/125,目录,第1章导论第2章程序设计语言第3章算法与数据结构第4章操作系统第5章关系数据库系统第6章软件工程,软件技术基础电子教案,3/125,一、名词解释数据，数据元素，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，算法，时间复杂度二、填空题1从某种意义上说，数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干个_构成，数据元素可由若干个_构成。

2从逻辑关系上讲，数据结构主要分为两大类，它们是_和_。

第3章算法与数据结构

（一）,4/125,3把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是_。

4通常从_、_、_等几方面评价算法的质量。

5常见时间复杂性的量级有：

常数阶O（_）、对数阶O（_）、线性阶O（_）、平方阶O（_）和指数阶O（_）。

6在一般情况下，一个算法的时间复杂性是_的函数。

7一个算法的时空性能是指该算法的_和_，前者是算法包含的_，后者是算法需要的_。

5/125,三、问答题分析下列程序段的时间复杂度。

（1）i=1;k=0;while（ij）j+;elsei+;,6/125,线性表一、名词解释线性结构，非线性结构，顺序存储结构，链式存储结构，存储密度二、填空题1为了便于讨论，有时将含n（n0）个结点的线性结构表示成（a1，a2,，an），其中每个ai代表一个_。

a1称为_结点，an称为_结点，i称为ai在线性表中的_。

对于任意一对相邻结点ai、ai+1（1in）,ai称为ai+1的直接_，ai+1称为ai的直接_。

第3章算法与数据结构

（二）,7/125,2线性结构的基本特征是：

若至少含有一个结点，则除开始结点没有直接_外，其他结点有且仅有一个直接_；除终端结点没有直接_外，其它结点有且仅有一个直接_。

3线性表的逻辑结构是_结构。

其所含结点的个数称为线性表的_，简称_。

4表长为0的线性表称为_。

5顺序表的特点是_。

6假定顺序表的每个datatype类型的结点占用k（k1）个内存单元，b是顺序表的第一个存储结点的第一个单元的内存地址，那么第i个结点ai的存储地址为_。

8/125,7以下为顺序表的删除运算，分析算法，请在_处填上正确的语句。

voiddelete_sqlist（sqlist*L,inti）/删除顺序表L中的第i-1个位置上的结点if（iL-last）error（“非法位置”）；for（j=i+1;j=L-last;j+）_;L-last=L-last-1;8为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为_，其它结点称为_。

9/125,9以下是求带头结点的单链表长度的运算，分析算法，请在_处填上正确的语句。

intlength_linklist（linklist*head）/求表head的长度_;j=0;while（p-next!

=NULL）_;j+;return（j）;/返回表长度,10/125,10以下为带头结点的单链表的定位运算，分析算法，请在_处填上正确的语句。

intlocate_lklist（lklisthead,datatypex）/求表head中第一个值等于x的结点的序号。

不存在这种结点时结果为0p=head-next;j=0;while（_）p=p-next;j+;if（p-data=x）return（j）;elsereturn（0）;,11/125,11循环链表与单链表的区别仅仅在于其终端结点的指针域值不是_，而是一个指向_的指针。

12/125,三、选择题1线性结构中的一个结点代表一个（）。

A.数据元素B.数据项C.数据D.数据结构2对于顺序表，以下说法错误的是（）。

A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是：

逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是：

逻辑上相邻的元素存储在物理位置也相邻的单元中,13/125,3对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作。

A.条件判断B.结点移动C.算术表达式D.赋值语句4对于顺序表的优缺点，以下说法错误的是（）。

A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点C.插入和删除运算较为方便D.容易造成一部分空间长期闲置而得不到充分利用,14/125,5在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（）。

A.real和rear-next-nextB.rear-next和realC.rear-next-next和rearD.rear和rear-next6设指针P指向双向链表的某一结点，则双向链表结构的对称性可用（）来描述。

A.p-prior-next-=p-next-nextB.p-prior-prior-=p-next-priorC.p-prior-next-=p-next-priorD.p-next-next=p-prior-prior,15/125,7循环链表的主要优点是（）。

A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表,16/125,8设rear是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为（）。

A.p=rear;B.rear=rear-next;rear=rear-next;free（rear）;free（p）C.rear=rear-next-next;D.p=rear-next-next;free（rear）;rear-next-next=p-next;free（p）;,17/125,18/125,下面给出的算法段是要把一个新结点*q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。

不能正确完成要求的算法段是（）。

A.q-LLink=p-LLink;B.p-LLink=q;q-Rlink=p;q-Rlink=p;p-LLink=q;p-LLink-Rlink=q;p-LLink-Rlink=q;q-LLink=p-LLink;C.q-LLink=p-LLink;q-Rlink=p;p-LLink-Rlink=q;p-LLink=q;,19/125,10若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A.顺序表B.单链表C.双链表D.单循环链表,20/125,四、算法设计1设A=（a1,a2,a3,an）和B=（b1,b2,bm）是两个线性表（假定所含数据元素均为整数）。

若n=m且ai=bi（i=1,n），则称A=B；若ai=bi（i=1,j）且aj+1B。

试编写一个比较A和B的算法，当AB时，分别输出-1，0或1。

2分别以顺序表和单链表作存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1，a2,an）逆置为（an,a2,a1）。

21/125,3已知单链表L中的结点是按值非递减有序排列的，试写一算法，将值为x的结点插入表L中，使得L仍然有序。

4已知单链表L是一个递增有序表，试编写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。

请分析算法的时间复杂度。

5设A和B是两个单链表，表中元素递增有序。

试编写一个算法，将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O

（1），C表的头结点可另辟空间。

请分析算法的时间复杂度。

22/125,6已知一单链表中的数据元素含有三个字符（即字母字符、数字字符和其它字符）。

试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间（头结点可另辟空间）。

7已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：

删去那些既在表B中出现又在表C中出现的元素。

试分别以两种存储结构（顺序结构和链式结构）编写实现上述运算的算法。

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

23/125,栈和队列一、名词解释栈，顺序栈，链栈，队列，顺序队列，循环列队，链队二、填空题1栈修改的原则是_，因此，栈又称为_线性表。

在栈顶进行插入运算，被称为_，在栈顶进行删除运算，被称为_。

2对于顺序栈而言，top=0表示_，此时作退栈运算，则产生“_”；top=stack_maxsize-1表示_，此时作进栈运算，则产生“_”。

24/125,3以下运算实现在顺序栈上的进栈，请在_处用适当的语句予以填充。

25/125,5以下运算实现循环队列的初始化，请在_处用适当句子予以填充。

voidInitCycQueue（Cycqueue*6链队在一定范围内不会出现_的情况。

当lq-front=lq-rear时，称为_。

26/125,7以下运算实现在链队上取队头元素，请在_处用适当句子予以填充。

intGetFront（LinkQ*lq,DataType*x）LinkQ*p;if（lq-rear=lq-front）return（0）;else_;_=p-data;return

（1）;,27/125,三、选择题1设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（）。

A.2B.3C.5D.62一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde3一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde,28/125,29/125,5向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为（）。

A.Top-next=sB.s-next=Top-next;Top-next=sC.s-next=Top;Top=sD.s-next=Top;Top=Top-next6从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（）。

A.x=Top-data;Top=Top-nextB.Top=Top-next;x=Top-dataC.x=Top;Top=Top-nextD.x=Top-data,30/125,7循环队列的入队操作应为（）。

A.sq.rear=sq.rear+1;sq.datasq.rear=x;B.sq.datasq.rear=x;sq.rear=sq.rear+1;C.sq.rear=（sq.rear+1）%maxsize;sq.datasq.rear=x;D.sq.datasq.rear=x;sq.rear=（sq.rear+1）%maxsize;8循环队列的队空条件为（）。

A.（sq.rear+1）%maxsize=（sq.front+1）%maxsizeB.（sq.rear+1）%maxsize=sq.front+1C.（sp.rear+1）%maxsize=sq.frontD.sq.rear=sq.front,31/125,四、算法设计1回文是指从左向右读和从右向左读均相同的字符序列，如“level”是回文，但“good”不是回文。

试写一个算法判定给定的字符向量是否为回文。

（提示：

将一半字符入栈，然后出栈与另一半字符进行比较。

）2借助栈（可用栈的基本运算）来实现单链表的逆置运算。

3利用栈的基本运算将栈S中值为m的元素全部删除。

32/125,4假设一个算术表达式中包含三种括号：

圆括号“（”和“）”，方括号“”和“”以及花括号“”和“”，且这三种括号可按任意的次序嵌套使用，如（.（.）。

试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法intcorrect（exp）；其中exp为字符串类型的变量。

如果括号正确配对，则返回值1；否则返回值0。

（提示：

对表达式进行扫描，凡遇到“（”、“”或“”就入栈，当遇到“）”、“”或“”时，检查当前栈顶元素是否是对应的左括号，若是就退掉栈顶的“（”、“”或“”，否则不配对。

表达式扫描完毕，栈应为空。

）,33/125,34/125,串和数组一、名词解释串，顺序串，链串二、填空题1含零个字符的串称为_串，用_表示。

其他串称为_串。

任何串中所含_的个数称为该串的长度。

2当且仅当两个串的_相等并且各个对应位置上的字符都_时，这两个串相等。

一个串中任意个连续字符组成的序列称为该串的_串，该串称为它所有子串的_串。

35/125,3通常将链串中每个存储结点所存储的字符个数称为_。

当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上_。

4一般地，一个n维数组可视为其数据元素为_维数组的线性表。

数组通常只有_和_两种基本运算。

5通常采用_存储结构来存放数组。

对二维数组可有两种存储方法：

一种是以_为主序的存储方式，另一种是以_为主序的存储方式。

C语言数组用的是以_序为主序的存储方法。

36/125,6数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

若按行方式存放，则元素M85的起始地址为_；若按列优先方式存放，则元素M85的地址为_。

7二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要_个字节；M的第8列和第5行共占_个字节；若M按行方式存储，元素M85的起始地址与当M按列优先方式存储时的_元素的起始地址一致。

37/125,8需要压缩存储的矩阵可分为_矩阵和_矩阵两种。

9对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元素压缩存储到_个元素的存储空间中。

10假设以一维数组M（1.n（n+1）/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为_。

38/125,11上三角矩阵中，主对角线上的第t行（1tn）有_个元素，按行优先顺序在一维数组M中存放上三角矩阵中的元素aij时，aij之前的前i-1行共有_个元素，在第i行上，aij是该行的第_个元素，Mk和aij的对应关系是_。

当ij时，aij=c（c表示常量），c存放在M_中。

39/125,三、选择题1在串的基本运算中，能够改变串值的运算有（）。

A.EQAL（S,T）B.LENGTH（S）C.CONCAT（S,T）D.REPLACE（S,T,R）E.INDEX（S,T）2在串的基本运算中，不能够改变串值的运算有（）。

A.ASSIGN（S,T）B.INSERT（S1,i,S2）C.DELETE（S,i,j）D.SUBSTR（S,i,j）E.REPLACE（S,T,R）,40/125,3对于以行序为主序的存储结构来说，在数组Ac1.d1，c2.d2中，c1和d1分别为数组A的第一个下标的下界和上界，c2和d2分别为第二个下标的下界和上界，每个数据元素占K个存储单元，二维数组中任一元素ai,j的存储位置可由（）式确定。

A.Loc（i,j）=Loc（c1,c2）+（i-c1）*（d2-c2）+（j-c2）*kB.Loc（i,j）=Loc（c1,c2）+（i-c1）*（d2-c2+1）+（j-c2）*kC.Loc（i,j）=Loc（c1,c2）+（j-c2）*（d1-c1+1）+（i-c1）*kD.Loc（i,j）=Loc（c1,c2）+（j-c2）*（d1-c1）+（i-c1）*k,41/125,4对于C语言的二维数组DataTypeAmn,每个数据元素占K个存储单元，二维数组中任意元素ai,j的存储位置可由（）式确定。

A.Loc（i,j）=Loc（0,0）+i*（n+1）+j*kB.Loc（i,j）=Loc（0,0）+j*（m+1）+i*kC.Loc（i,j）=Loc（0,0）+（i*n+j）*kD.Loc（i,j）=Loc（0,0）+（j*m+i）*k5稀疏矩阵的压缩存储方法是只存储（）。

A.非零元素B.三元组（i,j,aij）C.aijD.i,j,42/125,6基于三元组表的稀疏矩阵，对每个非零元素aij,可以用一个（）唯一确定。

A.非零元素B.三元组（i,j,aij）C.aijD.i,j7二维数组Mi,j的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5。

若M按行存储，元素M3,5的起始地址与M按列存储时，元素（）的起始地址相同。

A.M2,4B.M3,4C.M3,5D.M4,48常对数组进行的两种基本操作是（）。

A.建立与删除B.建立与修改C.查找与修改D.查找与索引,43/125,四、问答及算法设计1简述下列各对术语的区别。

空串和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值,44/125,2设有A=“”,B=“mule”，C=“old”，D=“my”,试计算下列运算的结果（注：

A+B是CONCAT（A,B）的简写,A=“”表示含有两个空格的字符串）。

（a）A+B（b）B+A（c）D+C+B（d）SUBSTR（B,3,2）（e）SUBSTR（C,1,0）（f）LENGTH（A）（g）LENGTH（D）（h）INDEX（B,D）（i）INDEX（C,“d”）（j）INSERT（D,2,C）（k）INSERT（B,1,A）（l）DELETE（B,2,2）（m）DELETE（B,2,0）,45/125,3分别在顺序串和链串上实现串的判相等运算EQUAL（S,T）。

4若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆置。

5用串的其他运算构造串的子串定位运算index。

6利用C的库函数strlen、strcpy和strcat写一算法voidStrInsert（char*S,char*T），将串T插入到串S的第i个位置上。

若i大于S的长度，则插入不执行。

46/125,7利用C的库函数strlen、strcpy和strncpy写一算法voidStrDelete（char*S,inti,intm），删去串S中从位置i开始的连续m个字符。

若istrlen（S），则没有字符被删除；若i+mstrlen（S），则将S中从位置i开始直至末尾的字符均删去。

8设有三对角矩阵Ann，将其三条对角线上的元素逐行存于数组A（1.3n-2）中，使得Ak=aij。

求：

（1）用i、j表示k的下标变换公式；

（2）用k表示i、j的下标变换公式。

47/125,树和二叉树一、名词解释树，结点的度，叶子，树的度，父结点，子结点，兄弟，结点的层数，树的高度，二叉树，左孩子，右孩子，满二叉树，完全二叉树二、填空题1假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为。

2假定一棵二叉树的结点数为18个，则它的最小高度是，最大高度是。

第3章算法与数据结构（三）,48/125,3在一棵二叉树中第4层上的结点数最多为。

4如果结点A有三个兄弟，而且B是A的双亲，则B的出度是。

5在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点，否则没有左兄弟。

6对于一棵具有n个结点的树，该树中所有结点的度之和为。

7在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为；若它存在左孩子，则左孩子结点的下标为；若它存在右孩子，则右孩子结点的下标为。

8在一棵二叉排序树中，按遍历得到的结点序列是一个有序序列。

49/125,三、选择题1以下说法错误的是（）。

A.树形结构的特点是一个结点可以有多个直接前趋B.树形结构可以表达（组织）更复杂的数据C.树（及一切树形结构）是一种“分支层次”结构D.任何只含一个结点的集合是一棵树2深度为6的二叉树最多有（）个结点。

A.64B.63C.32D.313任何一棵二叉树的叶结点在其先序、中序、后序遍历序列中的相对位置（）。

A.肯定发生变化B.有时发生变化C.肯定不发生变化D.无法确定,50/125,4设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为（）个。

A.k+1B.2kC.2k-1D.2k+15一棵二叉树满足下列条件：

对于任意结点，其值都大于它的左子树上所有结点的值，而小于右子树上所有结点的值。

现采用（）遍历方式就可以得到这棵二叉树所有结点的递增序列。

A.先序B.中序C.后序D.层次6已知某二叉树的后序遍历序列是dabec，中序遍历序列是deabc，它的先序遍历序列是（）。

A.acbedB.deabcC.decabD.cedba,51/125,四、简答及算法设计1画出由3个结点所构成的所有形态的树（假设是无序树）。

2一棵深度为H的满k叉树有如下性质：

第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。

如果按层次自顶向下，同一层自左向右从1开始对全部结点进行编号，试问：

（1）各层的结点个数是多少？

（2）编号为i的结点的双亲结点（若存在）的编号是多少？

（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少?

（4）编号为i的结点有右兄弟的条件是什么？

右兄弟结点的编号是多少？

52/125,3分别描述满足下面条件的二叉树的特征：

（1）先序序列和中序序列相同。

（2）先序序列和后序序列相同。

（3）中序序列和后序序列相同。

4已知某二叉树的先序遍历序列为ABC，试画出能得到这一结果的所有二叉树。

5已知二叉树的后序序列DECBGIHFA和中序序列DCEBAFHGI，画出这棵二叉树。

6分别设计出先序和后序遍历二叉树的非递归算法。

53/125,7已知二叉树采用二叉链表存储结构，编写一个算法，交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。

8采用二叉链表结构存储一棵二叉树，编写一个算法，删除该二叉树中数据值为x的结点及其子树，并且输出被删除的子树。

9试以三种遍历为基础，分别写出在二叉树上查找指定结点的直接前趋或直接后继的算法。

10已知树（森林）的高度为4，所对应的二叉树的先序序列为ABCDE，请构造出所有满足这一条件的树或森林。

软件技术基础电子教案,54/125,11将深度为4的满二叉树转换为对应的树或森林。

12已知结点序列21，18，37，42，65，24，19，26，45，25，画出相应的二叉排序树，并画出删除结点37后的二叉排序树。

13试编写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。

软件技术基础电子教案,55/125,图一、名词解释图，无向完全图，有向完全图，子图，连通分量，图的遍历，拓扑排序二、填空题1一个具有n个顶点的完全无向图的边数为。

一个具有n个顶点的完全有向图的弧度数为。

2设x,yV，若E,则表示有向图G中从x到y的一条，x称为点，y称为点。

若（x,y）E，则在无向图G中x和y间有一条。

第3章算法与数据结构（四）,56/125,3在无向图中，如果从顶点v到顶点v有路径，则称v和v是的。

如果对于图中的任意两个顶点vi,vjV，且vi和vj都是连通的，则称G为。

4连通分量是无向图中的连通子图。

5若连通图G的顶点个数为n，则G的生成树的边数为。

如果G的一个子图G的边数_，则G中一定有环。

相反，如果G的边数，则G一定不连通。

6对于无向图的邻接矩阵，顶点vi的度是。

对于有向图的邻接矩阵，顶点vi的出度OD（vi）为，顶点vi的入度ID（vi）为。

软件技术基础电子教案,57/125,7图的深度优先搜索遍历类似