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

软件技术基础,电子教案,复习思考题,2,目录,第1章 导论第2章 程序设计语言 第3章 算法与数据结构第4章 操作系统第5章 关系数据库系统第6章 软件工程,软件技术基础电子教案,3,一、名词解释数据，数据元素，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，算法，时间复杂度二、填空题1从某种意义上说，数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干个_构成，数据元素可由若干个_构成。2从逻辑关系上讲，数据结构主要分为两大类，它们是_和_。,第3章 算法与数据结构(一),4,3把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是_。4通常从_、_、_等几方面评价算法的质量。5常见时间复杂性的量级有：常数阶O(_)、对数阶O(_)、线性阶O(_)、平方阶O(_)和指数阶O(_)。6在一般情况下，一个算法的时间复杂性是_的函数。7一个算法的时空性能是指该算法的_和_，前者是算法包含的_，后者是算法需要的_。,5,三、问答题分析下列程序段的时间复杂度。(1)i=1;k=0;while(ij)j+;else i+;,6,线性表 一、名词解释线性结构，非线性结构，顺序存储结构，链式存储结构，存储密度二、填空题1为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2,，an)，其中每个ai代表一个_。a1称为_结点，an称为_结点，i称为ai在线性表中的_。对于任意一对相邻结点ai、ai+1(1in),ai称为ai+1的直接_，ai+1称为ai的直接_。,第3章 算法与数据结构(二),7,2线性结构的基本特征是：若至少含有一个结点，则除开始结点没有直接_外，其他结点有且仅有一个直接_；除终端结点没有直接_外，其它结点有且仅有一个直接_。3线性表的逻辑结构是_结构。其所含结点的个数称为线性表的_，简称_。4表长为0的线性表称为_。5顺序表的特点是_。6假定顺序表的每个datatype类型的结点占用k(k1)个内存单元，b是顺序表的第一个存储结点的第一个单元的内存地址，那么第i个结点ai的存储地址为_。,8,7以下为顺序表的删除运算，分析算法，请在_处填上正确的语句。void delete_sqlist(sqlist*L,int i)/删除顺序表L中的第i-1个位置上的结点 if(iL-last)error(“非法位置”)；for(j=i+1;j=L-last;j+)_;L-last=L-last-1;8为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为_，其它结点称为_。,9,9以下是求带头结点的单链表长度的运算，分析算法，请在_处填上正确的语句。int length_linklist(linklist*head)/求表head的长度 _;j=0;while(p-next!=NULL)_;j+;return(j);/返回表长度,10,10以下为带头结点的单链表的定位运算，分析算法，请在_处填上正确的语句。int locate_lklist(lklist head,datatype x)/求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0 p=head-next;j=0;while(_)p=p-next;j+;if(p-data=x)return(j);else return(0);,11,11循环链表与单链表的区别仅仅在于其终端结点的指针域值不是_，而是一个指向_的指针。,12,三、选择题1线性结构中的一个结点代表一个()。A.数据元素 B.数据项 C.数据 D.数据结构2对于顺序表，以下说法错误的是()。A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是：逻辑上相邻的元素存储在物理位置也相邻的单元中,13,3对顺序表上的插入、删除算法的时间复杂性分析来说，通常以()为标准操作。A.条件判断 B.结点移动 C.算术表达式 D.赋值语句4对于顺序表的优缺点，以下说法错误的是()。A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点C.插入和删除运算较为方便D.容易造成一部分空间长期闲置而得不到充分利用,14,5在循环链表中，将头指针改设为尾指针(rear)后，其头结点和尾结点的存储位置分别是()。A.real和rear-next-next B.rear-next 和realC.rear-next-next和rear D.rear和rear-next6设指针P指向双向链表的某一结点，则双向链表结构的对称性可用()来描述。A.p-prior-next-=p-next-next B.p-prior-prior-=p-next-priorC.p-prior-next-=p-next-prior D.p-next-next=p-prior-prior,15,7循环链表的主要优点是()。A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表,16,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,18,下面给出的算法段是要把一个新结点*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,10若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用()存储方式最节省时间。A.顺序表 B.单链表 C.双链表 D.单循环链表,20,四、算法设计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,3已知单链表L中的结点是按值非递减有序排列的，试写一算法，将值为x的结点插入表L中，使得L仍然有序。4已知单链表L是一个递增有序表，试编写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删除结点的空间，这里min和max是两个给定的参数。请分析算法的时间复杂度。5设A和B是两个单链表，表中元素递增有序。试编写一个算法，将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，C表的头结点可另辟空间。请分析算法的时间复杂度。,22,6已知一单链表中的数据元素含有三个字符(即字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。7已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(顺序结构和链式结构)编写实现上述运算的算法。8假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。,23,栈和队列 一、名词解释栈，顺序栈，链栈，队列，顺序队列，循环列队，链队二、填空题1栈修改的原则是_，因此，栈又称为_线性表。在栈顶进行插入运算，被称为_，在栈顶进行删除运算，被称为_。2对于顺序栈而言，top=0表示_，此时作退栈运算，则产生“_”；top=stack_maxsize-1表示_，此时作进栈运算，则产生“_”。,24,3以下运算实现在顺序栈上的进栈，请在_处用适当的语句予以填充。,25,5以下运算实现循环队列的初始化，请在_处用适当句子予以填充。void InitCycQueue(Cycqueue*6链队在一定范围内不会出现_的情况。当lq-front=lq-rear时，称为_。,26,7以下运算实现在链队上取队头元素，请在_处用适当句子予以填充。int GetFront(LinkQ*lq,DataType*x)LinkQ*p;if(lq-rear=lq-front)return(0);else_;_=p-data;return(1);,27,三、选择题1设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是()。A.2 B.3 C.5 D.62一个栈的入栈序列是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 e3一个栈的入栈序列是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,28,29,5向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为()。A.Top-next=s B.s-next=Top-next;Top-next=sC.s-next=Top;Top=s D.s-next=Top;Top=Top-next6从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为()。A.x=Top-data;Top=Top-next B.Top=Top-next;x=Top-dataC.x=Top;Top=Top-next D.x=Top-data,30,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,四、算法设计1回文是指从左向右读和从右向左读均相同的字符序列，如“level”是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈，然后出栈与另一半字符进行比较。)2借助栈(可用栈的基本运算)来实现单链表的逆置运算。3利用栈的基本运算将栈S中值为m的元素全部删除。,32,4假设一个算术表达式中包含三种括号：圆括号“(”和“)”，方括号“”和“”以及花括号“”和“”，且这三种括号可按任意的次序嵌套使用，如(.(.)。试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法int correct(exp)；其中exp为字符串类型的变量。如果括号正确配对，则返回值1；否则返回值0。(提示：对表达式进行扫描，凡遇到“(”、“”或“”就入栈，当遇到“)”、“”或“”时，检查当前栈顶元素是否是对应的左括号，若是就退掉栈顶的“(”、“”或“”，否则不配对。表达式扫描完毕，栈应为空。),33,34,串和数组 一、名词解释串，顺序串，链串二、填空题1含零个字符的串称为_串，用_表示。其他串称为_串。任何串中所含_的个数称为该串的长度。2当且仅当两个串的_相等并且各个对应位置上的字符都_时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的_串，该串称为它所有子串的_串。,35,3通常将链串中每个存储结点所存储的字符个数称为_。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上_。4一般地，一个n维数组可视为其数据元素为_维数组的线性表。数组通常只有_和_两种基本运算。5通常采用_存储结构来存放数组。对二维数组可有两种存储方法：一种是以_为主序的存储方式，另一种是以_为主序的存储方式。C语言数组用的是以_序为主序的存储方法。,36,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,8需要压缩存储的矩阵可分为_矩阵和_矩阵两种。9对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元素压缩存储到_个元素的存储空间中。10假设以一维数组M(1.n(n+1)/2)作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角(包括对角线)中的元素，数组M和矩阵A间对应的关系为_。,38,11上三角矩阵中，主对角线上的第t行(1tn)有_个元素，按行优先顺序在一维数组M中存放上三角矩阵中的元素aij时，aij之前的前i-1行共有_个元素，在第i行上，aij是该行的第_个元素，Mk和aij的对应关系是_。当ij时，aij=c(c表示常量)，c存放在M_中。,39,三、选择题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,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,4对于C语言的二维数组DataType Amn,每个数据元素占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.aij D.i,j,42,6基于三元组表的稀疏矩阵，对每个非零元素aij,可以用一个()唯一确定。A.非零元素 B.三元组(i,j,aij)C.aij D.i,j7二维数组Mi,j的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。若M按行存储，元素M3,5的起始地址与M按列存储时，元素()的起始地址相同。A.M 2,4 B.M3,4 C.M3,5 D.M4,48常对数组进行的两种基本操作是()。A.建立与删除 B.建立与修改 C.查找与修改 D.查找与索引,43,四、问答及算法设计1简述下列各对术语的区别。空串和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值,44,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,3分别在顺序串和链串上实现串的判相等运算EQUAL(S,T)。4若S和T是用结点大小为1的单链表存储的两个串(S、T为头指针)，设计一个算法将串S中首次与串T匹配的子串逆置。5用串的其他运算构造串的子串定位运算index。6利用C的库函数strlen、strcpy和strcat写一算法void StrInsert(char*S,char*T)，将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。,46,7利用C的库函数strlen、strcpy和strncpy写一算法void StrDelete(char*S,int i,int m)，删去串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,树和二叉树 一、名词解释树，结点的度，叶子，树的度，父结点，子结点，兄弟，结点的层数，树的高度，二叉树，左孩子，右孩子，满二叉树，完全二叉树二、填空题1假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为。2假定一棵二叉树的结点数为18个，则它的最小高度是，最大高度是。,第3章 算法与数据结构(三),48,3在一棵二叉树中第4层上的结点数最多为。4如果结点A有三个兄弟，而且B是A的双亲，则B的出度是。5在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点，否则没有左兄弟。6对于一棵具有n个结点的树，该树中所有结点的度之和为。7在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为；若它存在左孩子，则左孩子结点的下标为；若它存在右孩子，则右孩子结点的下标为。8在一棵二叉排序树中，按 遍历得到的结点序列是一个有序序列。,49,三、选择题1以下说法错误的是()。A.树形结构的特点是一个结点可以有多个直接前趋B.树形结构可以表达(组织)更复杂的数据C.树(及一切树形结构)是一种“分支层次”结构D.任何只含一个结点的集合是一棵树 2深度为6的二叉树最多有()个结点。A.64 B.63 C.32 D.31 3任何一棵二叉树的叶结点在其先序、中序、后序遍历序列中的相对位置()。A.肯定发生变化 B.有时发生变化C.肯定不发生变化 D.无法确定,50,4设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为()个。A.k+1 B.2k C.2k-1 D.2k+1 5一棵二叉树满足下列条件：对于任意结点，其值都大于它的左子树上所有结点的值，而小于右子树上所有结点的值。现采用()遍历方式就可以得到这棵二叉树所有结点的递增序列。A.先序 B.中序 C.后序 D.层次6已知某二叉树的后序遍历序列是dabec，中序遍历序列是deabc，它的先序遍历序列是()。A.acbed B.deabc C.decab D.cedba,51,四、简答及算法设计1画出由3个结点所构成的所有形态的树(假设是无序树)。2一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次自顶向下，同一层自左向右从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？(2)编号为i的结点的双亲结点(若存在)的编号是多少？(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4)编号为i的结点有右兄弟的条件是什么？右兄弟结点的编号是多少？,52,3分别描述满足下面条件的二叉树的特征：(1)先序序列和中序序列相同。(2)先序序列和后序序列相同。(3)中序序列和后序序列相同。4已知某二叉树的先序遍历序列为ABC，试画出能得到这一结果的所有二叉树。5已知二叉树的后序序列DECBGIHFA和中序序列DCEBAFHGI，画出这棵二叉树。6分别设计出先序和后序遍历二叉树的非递归算法。,53,7已知二叉树采用二叉链表存储结构，编写一个算法，交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。8采用二叉链表结构存储一棵二叉树，编写一个算法，删除该二叉树中数据值为x的结点及其子树，并且输出被删除的子树。9试以三种遍历为基础，分别写出在二叉树上查找指定结点的直接前趋或直接后继的算法。10已知树(森林)的高度为4，所对应的二叉树的先序序列为ABCDE，请构造出所有满足这一条件的树或森林。,软件技术基础电子教案,54,11将深度为4的满二叉树转换为对应的树或森林。12已知结点序列21，18，37，42，65，24，19，26，45，25，画出相应的二叉排序树，并画出删除结点37后的二叉排序树。13试编写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。,软件技术基础电子教案,55,图 一、名词解释图，无向完全图，有向完全图，子图，连通分量，图的遍历，拓扑排序二、填空题1一个具有n个顶点的完全无向图的边数为。一个具有n个顶点的完全有向图的弧度数为。2设x,yV，若E,则表示有向图G中从x到y的一条，x称为 点，y称为 点。若(x,y)E，则在无向图G中x和y间有一条。,第3章 算法与数据结构(四),56,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,7图的深度优先搜索遍历类似于树的 遍历，它所用到的数据结构是；图的广度优先搜索遍历类似于树的 遍历，它所用到的数据结构是。8一个图的 表示法是唯一的，而 表示法是不唯一的。9在有向图的邻接矩阵上，由第i行可得到第 个结点的出度，而由第j列可得到第 个结点的入度。10在无向图中，所有顶点的度数之和是所有边数的 倍，在有向图中，所有顶点的入度之和是所有顶点出度之和的 倍。,软件技术基础电子教案,58,软件技术基础电子教案,59,三、选择题 1在无向图中，所有顶点的度数之和是所有边数的()倍。A.0.5 B.1 C.2 D.4 2在有向图中，所有顶点的入度之和是所有顶点出度之和的()倍。A.0.5 B.1 C.2 D.4 3设有6个结点的无向图，该图至少应有()条边能确保是一个连通图。A.5 B.6 C.7 D.8,60,4以下说法中错误的是()。A.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间的大小只与图中结点个数有关，而与图的边数无关 B.邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下(或上)三角部分就可以了D.用相邻矩阵A表示图，判定任意两个结点vi和vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可,软件技术基础电子教案,61,四、简答及算法设计1写出将一个无向图的邻接矩阵转换成邻接表的算法。2写出将一个无向图的邻接表转换成邻接矩阵的算法。3写出建立一个有向图的逆邻接表的算法。4给定的无向图如图3.1所示，写出其邻接表，并以顶点1为出发点，写出其深度优先搜索和广度优先搜索所经过的顶点和边序列。,62,图3.1,软件技术基础电子教案,63,5设有一无向图G=(V,E)，其中V=1,2,3,4,5,6,E=(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)，按上述顺序输入后，画出其相应的邻接表。6在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。7已给有向图如图3.2所示，利用Dijkstra算法求v0到各顶点的最短路径，并写出算法执行时每次循环的状态。,软件技术基础电子教案,64,图3.2,软件技术基础电子教案,65,8对图3.3所示AOE网，求出：(1)各活动的最早开始时间和最迟开始时间；(2)所有的关键路径；(3)完成该网络所代表的工程工期；(4)提高哪些关键活动的速度可缩短工期？,66,图3.3,软件技术基础电子教案,67,查找 一、名词解释查找表，查找长度，有序表，散列表，散列函数，同义词，冲突二、填空题1查找表中主关键字指的是，次关键字指的是。2二分查找在查找成功时的查找长度不超过，其平均查找长度为，当n较大时约等于。3在散列存储中，装填因子的值越大，则。,第3章 算法与数据结构(五),68,4二分查找法仅适用于这样的表：表中的记录必须，其存储结构必须是。5静态查找表的三种不同实现各有优缺点。其中，查找效率最低但限制最少，查找效率最高但限制最强，而 查找则介于上述二者之间。6设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需比较 次，至多需比较 次。7在采用开放地址法解决冲突的散列表中删除一个记录，则对该元素所在存储单元的操作是。,软件技术基础电子教案,69,8以下算法在散列表HP中查找键值等于K的结点，成功时返回指向该结点的指针，不成功时返回空指针。请分析程序，并在 上填充合适的语句。pointer research_openhash(keytype K,openhash HP)i=H(K);/计算K的散列地址p=HPi;/i的同义词子表表头指针传给pwhile()p=p-next;/未达表尾且未找到时，继续扫描_;,软件技术基础电子教案,70,9以下算法假定以线性探测法解决冲突，在散列表HL中查找键值为K的结点，成功时回送该位置，不成功时回送标志-1。请分析程序，并在 上填充合适的语句。int search_cloxehash(keytype K,closehash HL)d=H(K);/计算散列地址i=d;while(HLi.key!=K/查找失败,软件技术基础电子教案,71,三、选择题1顺序查找法适合于()存储结构的查找表。A.压缩 B.散列 C.索引 D.顺序或链式2对采用折半查找法进行查找运算的查找表，要求按()方式进行存储。A.顺序存储 B.链式存储C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序,72,3设顺序表的长为n，则其每个元素的平均查找长度是()。A.n B.(n-1)/2 C.n/2 D.(n+1)/24分块查找的时间性能()。A.低于二分查找 B.高于顺序查找而低于二分查找 C.高于顺序查找 D.低于顺序查找而高于二分查找5设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用折半查找法查找键值为84的结点时，经()次比较后查找成功。A.2 B.3 C.4 D.12,73,6用二分查找法对具有n个结点的线性表查找的时间复杂性量级为()。A.O(n2)B.O(nlbn)C.O(n)D.O(lbn)7与其他查找方法相比，散列查找法的特点是()。A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字比较或通过关键字计算记录存储地址进行查找D.通过关键字计算记录存储地址，并进行一定的比较进行查找,软件技术基础电子教案,74,8在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值()。A.一定都是同义词 B.一定都不是同义词C.都相同 D.不一定是有序的顺序表,软件技术基础电子教案,75,9以下说法中错误的是()。A.散列法存储的基本思想是由关键码的值决定数据的存储地址B.散列表的结点中只包含数据元素自身的信息，不包含任何指针C.装填因子是散列法的一个重要参数，它反映散列表的装填程度D.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法,软件技术基础电子教案,76,四、简答及算法设计1假设线性表中结点是按键值递增的顺序存放的。试写一顺序查找法，将岗哨设在高下标端，然后分别求出等概率情况下查找成功和不成功时的平均查找长度。2若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的结点，则将该结点和其前趋(若存在)结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法(注意，查找时必须从表头开始向后扫描)。3试写出折半查找的递归算法。,软件技术基础电子教案,77,4给定有序表：D=006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908用折半查找法在D中查找586，试用图示法表示出查找过程。5已知散列函数为H(K)=K mod 13，关键字序列为25，37，52，43，84，99，120，15，26，11，70，82，试分别画出采用线性探查法和拉链法处理冲突时的散列表，并计算查找成功的平均查找长度。6顺序查找时间为O(n),二分查找时间为O(lbn),散列查找时间为O(1)，为什么在已有高效率的查找方法时仍不放弃低效率的方法？,软件技术基础电子教案,78,查找 一、名词解释排序，稳定的排序，不稳定的排序，内部排序，外部排序 二、填空题1按照排序过程涉及的存储设备的不同，排序可分为 排序和 排序。2在排序算法中，分析算法的时间复杂性时，通常以 和 为标准操作。评价排序的另一个主要标准是执行算法所需要的。3直接插入排序是稳定的，它的时间复杂性为，空间复杂度为。,软件技术基础电子教案,79,4对于n个记录的集合进行起泡排序，其最坏情况下所需的时间复杂度为。5对于n个记录的集合进行归并排序，所需的附加空间消耗是。6以下为起泡排序的算法。请分析算法，并在 上填充适当的语句。,软件技术基础电子教案,80,7对快速排序来讲，其最好情况下的时间复杂度是，其最坏情况下的时间复杂度是。8归并排序要求待排序列由若干个 的子序列组成。三、选择题1以下不稳定的排序方法是()。A.直接插入排序 B.起泡排序D.直接选择排序 D.二路归并排序,81,2以下时间复杂性不是O(n2)的排序方法是()。A.直接插入排序 B.二路归并排序 C.起泡排序 D.直接选择排序3排序的目的是为了以后对已排序的数据元数进行()操作。A.打印输出 B.分类 C.合并 D.查找4具有24个记录的序列，采用起泡排序至少的比较次数是()。A.1 B.23 C.24 D.529,软件技术基础电子教案,82,软件技术基础电子教案,83,6()方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。A.归并排序 B.插入排序 C.快速排序 D.选择排序7()方法是对序列中的元素通过适当的位置交换，将有关元素一次性地放置在其最终位置上。A.归并排序 B.插入排序 C.快速排序 D.选择排序8将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用()方法能够最快地找出其中最大的正整数。A.快速排序 B.插入排序 C.选择排序 D.归并排序,软件技术基础电子教案,84,四、简答及算法设计1给定关键字序列：105，50，30，25，85，40，100，12，10，28，分别写出直接插入排序、希尔排序、起泡排序、直接选择排序、快速排序和归并排序的每一趟运行结果。2试给出上题中直接插入排序、希尔排序、起泡排序、直接选择排序、快速排序和归并排序在最好和最坏时的关键字序列，指出比较和移动次数，以及相应的时间复杂度。3举例说明本章介绍的各排序方法中哪些是不稳定的。,85,4已知数组An中的元素为整型，设计算法将其中所有的奇数调整到数组的左边，而将所有的偶数调整到数组的右边，并要求时间复杂度为O(n)。5试在单链表上实现起泡排序。6试在单链表上实现直接插入排序。7试在单链表上实现直接选择排序。8一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。,软件技术基础电子教案,86,9设计算法以实现以下功能：不用完整排序，找出按增序关系为第k位的元素。10设计算法以实现以下功能：不用完整排序，要求找出其中最大的10个数，并回答选用何种排序算法最节省时间？11试写出递归形式的归并排序算法。12采用希尔排序方法对顺序表中的整型数据进行排序，设计希尔排序算法并显示每趟排序的结果。13编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。,软件技术基础电子教案,87,14下面是一个自下往上扫描的改进的起泡排序算法，按照给定的关键字序列：49，31，63，85，75，15，26，49。试分析共排序了几趟，并写出各趟排序的结果。,软件技术基础电子教案,88,目录,第1章 导论第2章 程序设计语言 第3章 算法与数据结构第4章 操作系统第5章 关系数据库系统第6章 软件工程,软件技术基础电子教案,89,操作系统概述一、选择题1操作系统是一种系统软件，它的职能是()。A.只管理软件B.只管理硬件C.既不管理硬件，也不管理软件D.既管理硬件，也管理软件 2设计批处理操作系统时，首先应考虑的是()。A.交互性和响应时间B.吞吐量和周转时间 C.灵活性和可适应性D.可靠性和完整性,第4章 操作系统,软件技术基础电子教案,90,3设计分时操作系统的主要目标是()。A吞吐量和周转时间B交互性和响应时间C灵活性和可适应性D可靠性和完整性4对计算机系统起着控制和管理作用的是()。A硬件 B操作系统 C编译系统 D应用程序5在()操作系统的控制下，计算机能及时处理过程控制装置反馈的信息，并作出响应。A网络 B分时 C实时 D批处理,91,二、填空题1如果操作系统具有很强的交互性，可同时供多个用户使用，但时间响应不太及时，则属于_类型；如果操作系统可靠，时间响应及时但仅有简单的交互能力，则属于_类型；如果操作系统在用户提交作业后，不提供交互能力，它所追求的是计算机资源的高利用率，大吞吐量和作业流程的自动化，则属于_类型。2设计实时操作系统时，必须先考虑系统的实时性和_，其次才考虑_等。3某