搜索
软件技术基础电子教案复习思考题2/125目录第1章导论第2章程序设计语言第3章算法与数据结构第4章操作系统第5章关系数据库系统第6章软件工程《软件技术基础》电子教案3/125一、名词解释数据，数据元素，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，算法，时间复杂度二、填空题1．从某种意义上说，数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干个________构成，数据元素可由若干个________构成。2．从逻辑关系上讲，数据结构主要分为两大类，它们是________和________。第3章算法与数据结构(一)4/1253．把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是________。4．通常从________、________、________等几方面评价算法的质量。5．常见时间复杂性的量级有：常数阶O(_____)、对数阶O(_____)、线性阶O(_____)、平方阶O(______)和指数阶O(_______)。6．在一般情况下，一个算法的时间复杂性是_________的函数。7．一个算法的时空性能是指该算法的________和_______，前者是算法包含的_______，后者是算法需要的________。5/125三、问答题分析下列程序段的时间复杂度。(1)i=1;k=0;while(in){k=k+10*i;i++;}(2)i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}6/125•线性表一、名词解释线性结构，非线性结构，顺序存储结构，链式存储结构，存储密度二、填空题1．为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,…，an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________。对于任意一对相邻结点ai、ai+1(1≤in),ai称为ai+1的直接______，ai+1称为ai的直接______。第3章算法与数据结构(二)7/1252．线性结构的基本特征是：若至少含有一个结点，则除开始结点没有直接______外，其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______。3．线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______。4．表长为0的线性表称为______。5．顺序表的特点是______。6．假定顺序表的每个datatype类型的结点占用k(k≥1)个内存单元，b是顺序表的第一个存储结点的第一个单元的内存地址，那么第i个结点ai的存储地址为______。8/1257．以下为顺序表的删除运算，分析算法，请在______处填上正确的语句。voiddelete_sqlist(sqlist*L,inti)//删除顺序表L中的第i-1个位置上的结点{if((i1)||(iL-last))error(“非法位置”)；for(j=i+1;j=L-last;j++)__________;L-last=L-last-1;}8．为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它结点称为________。9/1259．以下是求带头结点的单链表长度的运算，分析算法，请在______处填上正确的语句。intlength_linklist(linklist*head)//求表head的长度{________;j=0;while(p-next!=NULL){________________;j++;}return(j);//返回表长度}10/12510．以下为带头结点的单链表的定位运算，分析算法，请在_______处填上正确的语句。intlocate_lklist(lklisthead,datatypex)//求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0{p=head-next;j=0;while(________________________________){p=p-next;j++;}if(p-data==x)return(j);elsereturn(0);}11/12511．循环链表与单链表的区别仅仅在于其终端结点的指针域值不是______，而是一个指向_______的指针。12/125三、选择题1．线性结构中的一个结点代表一个()。A.数据元素B.数据项C.数据D.数据结构2．对于顺序表，以下说法错误的是()。A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是：逻辑上相邻的元素存储在物理位置也相邻的单元中13/1253．对顺序表上的插入、删除算法的时间复杂性分析来说，通常以()为标准操作。A.条件判断B.结点移动C.算术表达式D.赋值语句4．对于顺序表的优缺点，以下说法错误的是()。A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点C.插入和删除运算较为方便D.容易造成一部分空间长期闲置而得不到充分利用14/1255．在循环链表中，将头指针改设为尾指针(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-prior15/1257．循环链表的主要优点是()。A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表16/1258．设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/1259．双向链表结点结构如下：LLinkdataRLink其中：LLink是指向前驱结点的指针域；data是存放数据元素的数据域；Rlink是指向后继结点的指针域。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/12510．若某线性表中最常用的操作是取第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+1bj+1(jn=m)，则称AB；在其他情况下均称AB。试编写一个比较A和B的算法，当AB，A=B或AB时，分别输出 -1，0或1。2．分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,…,an)逆置为(an,…,a2,a1)。21/1253．已知单链表L中的结点是按值非递减有序排列的，试写一算法，将值为x的结点插入表L中，使得L仍然有序。4．已知单链表L是一个递增有序表，试编写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删除结点的空间，这里min和max是两个给定的参数。请分析算法的时间复杂度。5．设A和B是两个单链表，表中元素递增有序。试编写一个算法，将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，C表的头结点可另辟空间。请分析算法的时间复杂度。22/1256．已知一单链表中的数据元素含有三个字符 (即字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。7．已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(顺序结构和链式结构)编写实现上述运算的算法。8．假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点 *s的直接前趋结点。23/125•栈和队列一、名词解释栈，顺序栈，链栈，队列，顺序队列，循环列队，链队二、填空题1．栈修改的原则是_________，因此，栈又称为________线性表。在栈顶进行插入运算，被称为________，在栈顶进行删除运算，被称为________。2．对于顺序栈而言，top=0表示________，此时作退栈运算，则产生“________”；top=stack_maxsize-1表示________，此时作进栈运算，则产生“________”。24/1253．以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。intPush(SqStackTp*sq,DataTypex){if(sp-top==sqstack_maxsize-1}{printf(栈满);return(0);}else{________________;________________=x;return(1);}}4．顺序队列的出、入队操作会产生“_____________”。25/1255．以下运算实现循环队列的初始化，请在________处用适当句子予以填充。voidInitCycQueue(Cycqueue*&sq){________________;________________;sq-rear=0;}6．链队在一定范围内不会出现________________的情况。当lq-front==lq-rear时，称为________________。26/1257．以下运算实现在链队上取队头元素，请在_______处用适当句子予以填充。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