《《软件技术基础》复习思考题.ppt》由会员分享，可在线阅读，更多相关《《软件技术基础》复习思考题.ppt（126页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、软件技术基础复习思软件技术基础复习思考题考题目录目录第第1章章 导论导论第第2章章 程序设计语言程序设计语言 第第3章章 算法与数据结构算法与数据结构第第4章章 操作系统操作系统第第5章章 关系数据库系统关系数据库系统第第6章章 软件工程软件工程软件技术基础电子教案2 一、名词解释一、名词解释一、名词解释一、名词解释数据，数据元素，逻辑结构，存储结构，线性结构，非线数据，数据元素，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，算法，时间复杂度存储结构，算法，时间复杂度二、填空题二、填空题二
2、、填空题二、填空题1 1从某种意义上说，数据、数据元素和数据项反映了数从某种意义上说，数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干个据组织的三个层次，数据可由若干个_构成，数据元素构成，数据元素可由若干个可由若干个_构成。构成。2 2从逻辑关系上讲，数据结构主要分为两大类，它们是从逻辑关系上讲，数据结构主要分为两大类，它们是_和和_。第第3章章 算法与数据结构算法与数据结构(一一)33 3把逻辑上相邻的数据元素存储在物理上相邻的存储单把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是元中的存储结构是_。4 4通常从通常从_、_、_等几方面评价等几方面评价算法的质量。
3、算法的质量。5 5常见时间复杂性的量级有：常数阶常见时间复杂性的量级有：常数阶O(_)O(_)、对数阶、对数阶O(_)O(_)、线性阶、线性阶O(_)O(_)、平方阶、平方阶O(_)O(_)和指数阶和指数阶O(_)O(_)。6 6在一般情况下，一个算法的时间复杂性是在一般情况下，一个算法的时间复杂性是_的的函数。函数。7 7一个算法的时空性能是指该算法的一个算法的时空性能是指该算法的_和和_，前者是算法包含的，前者是算法包含的_，后者是算法需要的，后者是算法需要的_。4 三、问答题三、问答题三、问答题三、问答题分析下列程序段的时间复杂度。分析下列程序段的时间复杂度。(1)i=1;k=0;(1)
4、i=1;k=0;while(in)while(in)k=k+10*i;i+;k=k+10*i;i+;(2)i=1;j=0;(2)i=1;j=0;while(i+j=n)while(i+jj)j+;if(ij)j+;else i+;else i+;5线性表线性表 一、名词解释一、名词解释一、名词解释一、名词解释线性结构，非线性结构，顺序存储结构，链式存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，存储密度存储密度二、填空题二、填空题二、填空题二、填空题1 1为了便于讨论，有时将含为了便于讨论，有时将含n(n0)n(n0)个结点的线性结构表示个结点的线性结构表示成成(a(a1 1，a
5、a2 2,，a an n)，其中每个，其中每个a ai i代表一个代表一个_。a a1 1称为称为_结点，结点，a an n称为称为_结点，结点，i i称为称为ai ai在线性表中的在线性表中的_。对。对于任意一对相邻结点于任意一对相邻结点a ai i、a ai+1i+1(1in),(1in),a ai i称为称为a ai+1i+1的直接的直接_，a ai+1i+1称为称为a ai i的直接的直接_。第第3章章 算法与数据结构算法与数据结构(二二)6 2 2线性结构的基本特征是：若至少含有一个结点，则除线性结构的基本特征是：若至少含有一个结点，则除开始结点没有直接开始结点没有直接_外，其他结点
6、有且仅有一个直接外，其他结点有且仅有一个直接_；除终端结点没有直接；除终端结点没有直接_外，其它结点有且仅有一外，其它结点有且仅有一个直接个直接_。3 3线性表的逻辑结构是线性表的逻辑结构是_结构。其所含结点的个数结构。其所含结点的个数称为线性表的称为线性表的_，简称，简称_。4 4表长为表长为0 0的线性表称为的线性表称为_。5 5顺序表的特点是顺序表的特点是_。6 6假定顺序表的每个假定顺序表的每个datatypedatatype类型的结点占用类型的结点占用k(k1)k(k1)个内个内存单元，存单元，b b是顺序表的第一个存储结点的第一个单元的内存地是顺序表的第一个存储结点的第一个单元的内
7、存地址，那么第址，那么第i i个结点个结点a ai i的存储地址为的存储地址为_。7 7 7以下为顺序表的删除运算，分析算法，请在以下为顺序表的删除运算，分析算法，请在_处填处填上正确的语句。上正确的语句。void delete_sqlist(sqlist*L,int i)/void delete_sqlist(sqlist*L,int i)/删除顺序表删除顺序表L L中的第中的第i-1i-1个个位置上的结点位置上的结点 if(iL-last)error(“if(iL-last)error(“非法位置非法位置”)”)；for(j=i+1;j=L-last;j+)_;for(j=i+1;j=L-
8、last;j+)_;L-last=L-last-1;L-last=L-last-1;8 8为了便于实现各种运算，通常在单链表的第一个结点为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为之前增设一个类型相同的结点，称为_，其它结点称为，其它结点称为_。8 9 9以下是求带头结点的单链表长度的运算，分析算法，请以下是求带头结点的单链表长度的运算，分析算法，请在在_处填上正确的语句。处填上正确的语句。int length_linklist(linklist*head)/int length_linklist(linklist*head)/求表求表headhead的长度的
9、长度 _;_;j=0;j=0;while(p-next!=NULL)while(p-next!=NULL)_;_;j+;j+;return(j);/return(j);/返回表长度返回表长度 91010以下为带头结点的单链表的定位运算，分析算法，请以下为带头结点的单链表的定位运算，分析算法，请在在_处填上正确的语句。处填上正确的语句。int locate_lklist(lklist head,datatype x)int locate_lklist(lklist head,datatype x)/求表求表headhead中第一个值等于中第一个值等于x x的结点的序号。不存在这种结的结点的序号。
10、不存在这种结点时结果为点时结果为0 0 p=head-next;j=0;p=head-next;j=0;while(_)p=p-while(_)p=p-next;j+;next;j+;if(p-data=x)return(j);if(p-data=x)return(j);else return(0);else return(0);101111循环链表与单链表的区别仅仅在于其终端结点的指针循环链表与单链表的区别仅仅在于其终端结点的指针域值不是域值不是_，而是一个指向，而是一个指向_的指针。的指针。11三、选择题三、选择题三、选择题三、选择题1 1线性结构中的一个结点代表一个线性结构中的一个结点代
11、表一个()()。A.A.数据元素数据元素 B.B.数据项数据项 C.C.数据数据 D.D.数据结构数据结构2 2对于顺序表，以下说法错误的是对于顺序表，以下说法错误的是()()。A.A.顺序表是用一维数组实现的线性表，数组的下标可以顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址看成是元素的绝对地址 B.B.顺序表的所有存储结点按相应数据元素间的逻辑关系顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列决定的次序依次排列C.C.顺序表的特点是：逻辑结构中相邻的结点在存储结构顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻中仍相邻D.D.顺序表的特点是：逻辑
12、上相邻的元素存储在物理位置顺序表的特点是：逻辑上相邻的元素存储在物理位置也相邻的单元中也相邻的单元中123 3对顺序表上的插入、删除算法的时间复杂性分析来说，对顺序表上的插入、删除算法的时间复杂性分析来说，通常以通常以()()为标准操作。为标准操作。A.A.条件判断条件判断 B.B.结点移动结点移动 C.C.算术表达式算术表达式 D.D.赋值语句赋值语句4 4对于顺序表的优缺点，以下说法错误的是对于顺序表的优缺点，以下说法错误的是()()。A.A.无需为表示结点间的逻辑关系而增加额外的存储空间无需为表示结点间的逻辑关系而增加额外的存储空间B.B.可以方便地随机存取表中的任一结点可以方便地随机存
13、取表中的任一结点C.C.插入和删除运算较为方便插入和删除运算较为方便D.D.容易造成一部分空间长期闲置而得不到充分利用容易造成一部分空间长期闲置而得不到充分利用135 5在循环链表中，将头指针改设为尾指针在循环链表中，将头指针改设为尾指针(rear)(rear)后，其头后，其头结点和尾结点的存储位置分别是结点和尾结点的存储位置分别是()()。A.realA.real和和rear-next-next rear-next-next B.rear-next B.rear-next 和和realrealC.rear-next-nextC.rear-next-next和和rear rear D.rear
14、D.rear和和rear-nextrear-next6 6设指针设指针P P指向双向链表的某一结点，则双向链表结构指向双向链表的某一结点，则双向链表结构的对称性可用的对称性可用()()来描述。来描述。A.p-prior-next-=p-next-next A.p-prior-next-=p-next-next B.p-prior-prior-=p-next-priorB.p-prior-prior-=p-next-priorC.p-prior-next-=p-next-prior C.p-prior-next-=p-next-prior D.p-next-next=p-prior-priorD
15、.p-next-next=p-prior-prior147 7循环链表的主要优点是循环链表的主要优点是()()。A.A.不再需要头指针不再需要头指针B.B.已知某个结点的位置后，能够容易找到它的直接前趋已知某个结点的位置后，能够容易找到它的直接前趋C.C.在进行插入、删除运算时，能更好地保证链表不断开在进行插入、删除运算时，能更好地保证链表不断开D.D.从表中任一结点出发都能扫描到整个链表从表中任一结点出发都能扫描到整个链表158 8设设rearrear是指向非空带头结点的循环单链表的尾指针，则是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为删除表首结点的操作可表示为()(
16、)。A.p=rear;B.rear=rear-next;A.p=rear;B.rear=rear-next;rear=rear-next;free(rear);rear=rear-next;free(rear);free(p)free(p)C.rear=rear-next-next;D.p=rear-next-next;C.rear=rear-next-next;D.p=rear-next-next;free(rear);rear-next-next=p-next;free(rear);rear-next-next=p-next;free(p);free(p);1617下面给出的算法段是要把一
17、个新结点下面给出的算法段是要把一个新结点*q*q作为非空双向链作为非空双向链表中的结点表中的结点*p*p的前驱，插入到此双向链表中。不能正确完成的前驱，插入到此双向链表中。不能正确完成要求的算法段是要求的算法段是()()。A.q-LLink=p-LLink;A.q-LLink=p-LLink;B.p-LLink=q;B.p-LLink=q;q-Rlink=p;q-Rlink=p;q-Rlink=p;q-Rlink=p;p-LLink=q;p-LLink=q;p-LLink-Rlink=q;p-LLink-Rlink=q;p-LLink-Rlink=q;q-LLink=p-LLink;p-LLi
18、nk-Rlink=q;q-LLink=p-LLink;C.q-LLink=p-LLink;C.q-LLink=p-LLink;q-Rlink=p;q-Rlink=p;p-LLink-Rlink=q;p-LLink-Rlink=q;p-LLink=q;p-LLink=q;181010若某线性表中最常用的操作是取第若某线性表中最常用的操作是取第i i个元素和找第个元素和找第i i个个元素的前趋元素，则采用元素的前趋元素，则采用()()存储方式最节省时间。存储方式最节省时间。A.A.顺序表顺序表 B.B.单链表单链表 C.C.双链表双链表 D.D.单循环链表单循环链表19四、算法设计四、算法设计四、
19、算法设计四、算法设计1 1设设A=(aA=(a1 1,a,a2 2,a,a3 3,a,an n)和和B=(bB=(b1 1,b,b2 2,b,bmm)是两个线性表是两个线性表(假假定所含数据元素均为整数定所含数据元素均为整数)。若。若n=mn=m且且a ai i=b=bi i(i=1,n)(i=1,n)，则称，则称A=BA=B；若；若a ai i=b=bi i(i=1,j)(i=1,j)且且a aj+1j+1bbj+1j+1(jn=m)(jn=m)，则称，则称ABABAB。试编写一个比较。试编写一个比较A A和和B B的算法，当的算法，当ABABAB时，分别输出时，分别输出-1-1，0 0或或
20、1 1。2 2分别以顺序表和单链表作存储结构，各写一个实现线分别以顺序表和单链表作存储结构，各写一个实现线性表的就地性表的就地(即使用尽可能少的附加空间即使用尽可能少的附加空间)逆置的算法，在原表逆置的算法，在原表的存储空间内将线性表的存储空间内将线性表(a(a1 1，a a2 2,a,an n)逆置为逆置为(a(an n,a,a2 2,a,a1 1)。203 3已知单链表已知单链表L L中的结点是按值非递减有序排列的，试中的结点是按值非递减有序排列的，试写一算法，将值为写一算法，将值为x x的结点插入表的结点插入表L L中，使得中，使得L L仍然有序。仍然有序。4 4已知单链表已知单链表L
21、L是一个递增有序表，试编写一高效算法，是一个递增有序表，试编写一高效算法，删除表中值大于删除表中值大于minmin且小于且小于maxmax的结点的结点(若表中有这样的结点若表中有这样的结点)，同时释放被删除结点的空间，这里同时释放被删除结点的空间，这里minmin和和maxmax是两个给定的参是两个给定的参数。请分析算法的时间复杂度。数。请分析算法的时间复杂度。5 5设设A A和和B B是两个单链表，表中元素递增有序。试编写一是两个单链表，表中元素递增有序。试编写一个算法，将个算法，将A A和和B B归并成一个按元素值递减有序的单链表归并成一个按元素值递减有序的单链表C C，并要求辅助空间为并
22、要求辅助空间为O(1)O(1)，C C表的头结点可另辟空间。请分析算表的头结点可另辟空间。请分析算法的时间复杂度。法的时间复杂度。216 6已知一单链表中的数据元素含有三个字符已知一单链表中的数据元素含有三个字符(即字母字即字母字符、数字字符和其它字符符、数字字符和其它字符)。试编写算法，构造三个循环链表，。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间间作为这三个表的结点空间(头结点可另辟空间头结点可另辟空间)。7 7已知已知A A、B B和和C C为三个元素值递增有序的线性表
23、，现要为三个元素值递增有序的线性表，现要求对表求对表A A作如下运算：作如下运算：删去那些既在表删去那些既在表B B中出现又在表中出现又在表C C中出中出现的元素。试分别以两种存储结构现的元素。试分别以两种存储结构(顺序结构和链式结构顺序结构和链式结构)编写编写实现上述运算的算法。实现上述运算的算法。8 8假设在长度大于假设在长度大于1 1的循环链表中，既无头结点也无头指的循环链表中，既无头结点也无头指针，针，s s为指向链表中某个结点的指针，试编写算法删除结点为指向链表中某个结点的指针，试编写算法删除结点*s*s的直接前趋结点。的直接前趋结点。22栈和队列栈和队列 一、名词解释一、名词解释一
24、、名词解释一、名词解释栈，顺序栈，链栈，队列，顺序队列，循环列队，链队栈，顺序栈，链栈，队列，顺序队列，循环列队，链队二、填空题二、填空题二、填空题二、填空题1 1栈修改的原则是栈修改的原则是_，因此，栈又称为，因此，栈又称为_线性表。在栈顶进行插入运算，被称为线性表。在栈顶进行插入运算，被称为_，在栈顶进行，在栈顶进行删除运算，被称为删除运算，被称为_。2 2对于顺序栈而言，对于顺序栈而言，top=0top=0表示表示_，此时作退栈运，此时作退栈运算，则产生算，则产生“_”_”；top=stack_maxsize-1top=stack_maxsize-1表示表示_，此时作进栈运算，则产生此时
25、作进栈运算，则产生“_”_”。233 3以下运算实现在顺序栈上的进栈，请在以下运算实现在顺序栈上的进栈，请在_处用适处用适当的语句予以填充。当的语句予以填充。245 5以下运算实现循环队列的初始化，请在以下运算实现循环队列的初始化，请在_处用处用适当句子予以填充。适当句子予以填充。void InitCycQueue(Cycqueue*&sq)void InitCycQueue(Cycqueue*&sq)_;_;_;sq-rear=0;_;sq-rear=0;6 6链队在一定范围内不会出现链队在一定范围内不会出现_的情况。的情况。当当lq-front=lq-rearlq-front=lq-rea
26、r时，称为时，称为_。257 7以下运算实现在链队上取队头元素，请在以下运算实现在链队上取队头元素，请在_处用处用适当句子予以填充。适当句子予以填充。int GetFront(LinkQ*lq,DataType*x)int GetFront(LinkQ*lq,DataType*x)LinkQ*p;LinkQ*p;if(lq-rear=lq-front)return(0);if(lq-rear=lq-front)return(0);else_;else_;_=p-data;_=p-data;return(1);return(1);26 三、选择题三、选择题三、选择题三、选择题1 1设有一顺序栈设
27、有一顺序栈S S，元素，元素s s1 1,s,s2 2,s,s3 3,s,s4 4,s,s5 5,s,s6 6依次进栈，如果依次进栈，如果6 6个元素出栈的顺序是个元素出栈的顺序是s s2 2,s,s3 3,s,s4 4,s,s6 6,s,s5 5,s,s1 1，则栈的容量至少应该，则栈的容量至少应该是是()()。A.2 A.2 B.3 B.3 C.5 C.5 D.6D.62 2一个栈的入栈序列是一个栈的入栈序列是a,b,c,d,e,a,b,c,d,e,则栈的不可能的输出则栈的不可能的输出序列是序列是()()。A.e d c b a A.e d c b a B.B.d e c b a d e
28、c b a C.d c e a b C.d c e a b D.a b c d eD.a b c d e3 3一个栈的入栈序列是一个栈的入栈序列是a,b,c,d,e,a,b,c,d,e,则栈的不可能的输出则栈的不可能的输出序列是序列是()()。A.e d c b a A.e d c b a B.B.d e c b a C.d c e a b D.a b c d ed e c b a C.d c e a b D.a b c d e27285 5向一个栈顶指针为向一个栈顶指针为TopTop的链中插入一个的链中插入一个s s所指结点时，所指结点时，其操作步骤为其操作步骤为()()。A.Top-nex
29、t=s A.Top-next=s B.s-next=Top-next;Top-next=sB.s-next=Top-next;Top-next=sC.s-next=Top;Top=s C.s-next=Top;Top=s D.s-next=Top;Top=Top-nextD.s-next=Top;Top=Top-next6 6从栈顶指针为从栈顶指针为TopTop的链栈中删除一个结点，并将被删节的链栈中删除一个结点，并将被删节点的值保存到点的值保存到x x中，其操作步骤为中，其操作步骤为()()。A.x=Top-data;Top=Top-nextA.x=Top-data;Top=Top-next
30、 B.Top=Top-next;x=Top-data B.Top=Top-next;x=Top-dataC.x=Top;Top=Top-next C.x=Top;Top=Top-next D.x=Top-data D.x=Top-data 297 7循环队列的入队操作应为循环队列的入队操作应为()()。A.sq.rear=sq.rear+1;sq.datasq.rear=x;A.sq.rear=sq.rear+1;sq.datasq.rear=x;B.sq.datasq.rear=x;sq.rear=sq.rear+1;B.sq.datasq.rear=x;sq.rear=sq.rear+1;
31、C.sq.rear=(sq.rear+1)%maxsize;sq.datasq.rear=x;C.sq.rear=(sq.rear+1)%maxsize;sq.datasq.rear=x;D.sq.datasq.rear=x;sq.rear=(sq.rear+1)%maxsize;D.sq.datasq.rear=x;sq.rear=(sq.rear+1)%maxsize;8 8循环队列的队空条件为循环队列的队空条件为()()。A.(sq.rear+1)%maxsize=(sq.front+1)%maxsizeA.(sq.rear+1)%maxsize=(sq.front+1)%maxsize
32、B.(sq.rear+1)%maxsize=sq.front+1B.(sq.rear+1)%maxsize=sq.front+1C.(sp.rear+1)%maxsize=sq.frontC.(sp.rear+1)%maxsize=sq.frontD.sq.rear=sq.frontD.sq.rear=sq.front 30四、算法设计四、算法设计四、算法设计四、算法设计1 1回文是指从左向右读和从右向左读均相同的字符序列，回文是指从左向右读和从右向左读均相同的字符序列，如如“level”“level”是回文，但是回文，但“good”“good”不是回文。试写一个算法判定给定不是回文。试写一个
33、算法判定给定的字符向量是否为回文。的字符向量是否为回文。(提示：将一半字符入栈，然后出栈提示：将一半字符入栈，然后出栈与另一半字符进行比较。与另一半字符进行比较。)2 2借助栈借助栈(可用栈的基本运算可用栈的基本运算)来实现单链表的逆置运算。来实现单链表的逆置运算。3 3利用栈的基本运算将栈利用栈的基本运算将栈S S中值为中值为mm的元素全部删除。的元素全部删除。314 4假设一个算术表达式中包含三种括号：圆括号假设一个算术表达式中包含三种括号：圆括号“(”“(”和和“)”“)”，方括号，方括号“”“”和和“”“”以及花括号以及花括号“”“”和和“”“”，且这三种括号可按，且这三种括号可按任意
34、的次序嵌套使用，如任意的次序嵌套使用，如(.(.(.)(.)。试利用栈的运算编写判断给定表达式中所含括号。试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法是否正确配对出现的算法int correct(exp)int correct(exp)；其中；其中expexp为字符串类为字符串类型的变量。如果括号正确配对，则返回值型的变量。如果括号正确配对，则返回值1 1；否则返回值；否则返回值0 0。(提示：对表达式进行扫描，凡遇到提示：对表达式进行扫描，凡遇到“(”“(”、“”“”或或“”“”就入栈，当就入栈，当遇到遇到“)”“)”、“”“”或或“”“”时，检查当前栈顶元素是否是对应的
35、左括号，时，检查当前栈顶元素是否是对应的左括号，若是就退掉栈顶的若是就退掉栈顶的“(”“(”、“”“”或或“”“”，否则不配对。表达式扫描完，否则不配对。表达式扫描完毕，栈应为空。毕，栈应为空。)3233串和数组串和数组 一、名词解释一、名词解释一、名词解释一、名词解释串，顺序串，链串串，顺序串，链串二、填空题二、填空题二、填空题二、填空题1 1含零个字符的串称为含零个字符的串称为_串，用串，用_表示。其他表示。其他串称为串称为_串。任何串中所含串。任何串中所含_的个数称为该串的长度。的个数称为该串的长度。2 2当且仅当两个串的当且仅当两个串的_相等并且各个对应位置上的相等并且各个对应位置上的
36、字符都字符都_时，这两个串相等。一个串中任意个连续字符组时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的成的序列称为该串的_串，该串称为它所有子串的串，该串称为它所有子串的_串。串。343 3通常将链串中每个存储结点所存储的字符个数称为通常将链串中每个存储结点所存储的字符个数称为_。当结点大小大于。当结点大小大于1 1时，链串的最后一个结点的各个数时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上里补上_。4 4一般地，一个一般地，一个n n维数组可视为其数据元素为维数组可视为其数据元素为
37、_维数维数组的线性表。数组通常只有组的线性表。数组通常只有_和和_两种基本运算。两种基本运算。5 5通常采用通常采用_存储结构来存放数组。对二维数组可存储结构来存放数组。对二维数组可有两种存储方法：一种是以有两种存储方法：一种是以_为主序的存储方式，另一种为主序的存储方式，另一种是以是以_为主序的存储方式。为主序的存储方式。C C语言数组用的是以语言数组用的是以_序序为主序的存储方法。为主序的存储方法。356 6数组数组MM中每个元素的长度是中每个元素的长度是3 3个字节，行下标个字节，行下标i i从从1 1到到8 8，列下标，列下标j j从从1 1到到1010，从首地址，从首地址EAEA开始
38、连续存放在存储器中。开始连续存放在存储器中。若按行方式存放，则元素若按行方式存放，则元素M85M85的起始地址为的起始地址为_；若按；若按列优先方式存放，则元素列优先方式存放，则元素M85M85的地址为的地址为_。7 7二维数组二维数组MM的成员是的成员是6 6个字符个字符(每个字符占一个存储单每个字符占一个存储单元元)组成的串，行下标组成的串，行下标i i的范围从的范围从0 0到到8 8，列下标，列下标j j的范围从的范围从1 1到到1010，则存放，则存放MM至少需要至少需要_个字节；个字节；MM的第的第8 8列和第列和第5 5行共占行共占_个字节；若个字节；若MM按行方式存储，元素按行方
39、式存储，元素M85M85的起始地址的起始地址与当与当MM按列优先方式存储时的按列优先方式存储时的_元素的起始地址一致。元素的起始地址一致。368 8需要压缩存储的矩阵可分为需要压缩存储的矩阵可分为_矩阵和矩阵和_矩矩阵两种。阵两种。9 9对称方阵中有近半的元素重复，若为每一对元素只分对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将配一个存储空间，则可将n2n2个元素压缩存储到个元素压缩存储到_个元素个元素的存储空间中。的存储空间中。1010假设以一维数组假设以一维数组M(1.n(n+1)/2)M(1.n(n+1)/2)作为作为n n阶对称矩阵阶对称矩阵A A的的存储结构，以
40、行序为主序存储其下三角存储结构，以行序为主序存储其下三角(包括对角线包括对角线)中的元素，中的元素，数组数组MM和矩阵和矩阵A A间对应的关系为间对应的关系为_。371111上三角矩阵中，主对角线上的第上三角矩阵中，主对角线上的第t t行行(1tn)(1tn)有有_个元素，按行优先顺序在一维数组个元素，按行优先顺序在一维数组MM中存放上三角矩阵中的元中存放上三角矩阵中的元素素a aij ij时，时，a aij ij之前的前之前的前i-1i-1行共有行共有_个元素，在第个元素，在第i i行上，行上，a aij ij是该行的第是该行的第_个元素，个元素，MkMk和和a aij ij的对应关系是的对
41、应关系是_。当当ijij时，时，a aij ij=c(c=c(c表示常量表示常量)，c c存放在存放在M_M_中。中。38三、选择题三、选择题三、选择题三、选择题1 1在串的基本运算中，能够改变串值的运算有在串的基本运算中，能够改变串值的运算有()()。A.EQAL(S,T)A.EQAL(S,T)B.LENGTH(S)B.LENGTH(S)C.CONCAT(S,T)C.CONCAT(S,T)D.REPLACE(S,T,R)D.REPLACE(S,T,R)E.INDEX(S,T)E.INDEX(S,T)2 2在串的基本运算中，不能够改变串值的运算有在串的基本运算中，不能够改变串值的运算有()()
42、。A.ASSIGN(S,T)B.INSERT(S1,i,S2)A.ASSIGN(S,T)B.INSERT(S1,i,S2)C.DELETE(S,i,j)C.DELETE(S,i,j)D.SUBSTR(S,i,j)D.SUBSTR(S,i,j)E.REPLACE(S,T,R)E.REPLACE(S,T,R)393 3对于以行序为主序的存储结构来说，在数组对于以行序为主序的存储结构来说，在数组Ac1.d1Ac1.d1，c2.d2c2.d2中，中，c1c1和和d1d1分别为数组分别为数组A A的第一个下标的下界和上界，的第一个下标的下界和上界，c2c2和和d2d2分别为第二个下标的下界和上界，每个数
43、据元素占分别为第二个下标的下界和上界，每个数据元素占K K个存储个存储单元，二维数组中任一元素单元，二维数组中任一元素ai,jai,j的存储位置可由的存储位置可由()()式确定。式确定。A.Loc(i,j)=Loc(c1,c2)+(i-c1)*(d2-c2)+(j-c2)*kA.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)*kB.Loc(i,j)=Loc(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*kC.Loc(i,j)=Loc(c1,c2)+(
44、j-c2)*(d1-c1+1)+(i-c1)*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)*kD.Loc(i,j)=Loc(c1,c2)+(j-c2)*(d1-c1)+(i-c1)*k404 4对于对于C C语言的二维数组语言的二维数组DataType Amn,DataType Amn,每个数据元素每个数据元素占占K K个存储单元，二维数组中任意元素个存储单元，二维数组中任意元素ai,j ai,j 的存储位置可由的存储位置可由()式确定。式确定。A.Loc(
45、i,j)=Loc(0,0)+i*(n+1)+j*kA.Loc(i,j)=Loc(0,0)+i*(n+1)+j*kB.Loc(i,j)=Loc(0,0)+j*(m+1)+i*kB.Loc(i,j)=Loc(0,0)+j*(m+1)+i*kC.Loc(i,j)=Loc(0,0)+(i*n+j)*kC.Loc(i,j)=Loc(0,0)+(i*n+j)*kD.Loc(i,j)=Loc(0,0)+(j*m+i)*kD.Loc(i,j)=Loc(0,0)+(j*m+i)*k5 5稀疏矩阵的压缩存储方法是只存储稀疏矩阵的压缩存储方法是只存储()()。A.A.非零元素非零元素 B.B.三元组三元组(i,j,
46、a(i,j,aij ij)C.aC.aij ij D.i,jD.i,j416 6基于三元组表的稀疏矩阵，对每个非零元素基于三元组表的稀疏矩阵，对每个非零元素aij,aij,可以用可以用一个一个()()唯一确定。唯一确定。A.A.非零元素非零元素 B.B.三元组三元组(i,j,a(i,j,aij ij)C.aC.aij ij D.i,j D.i,j7 7二维数组二维数组Mi,jMi,j的元素是的元素是4 4个字符个字符(每个字符占一个存储每个字符占一个存储单元单元)组成的串，行下标组成的串，行下标i i的范围从的范围从0 0到到4 4，列下标，列下标j j的范围从的范围从0 0到到5 5。若若M
47、M按行存储，元素按行存储，元素M3,5M3,5的起始地址与的起始地址与MM按列存储时，元素按列存储时，元素()的起始地址相同。的起始地址相同。A.M 2,4 A.M 2,4 B.M3,4 B.M3,4 C.M3,5 C.M3,5 D.M4,4D.M4,48 8常对数组进行的两种基本操作是常对数组进行的两种基本操作是()()。A.A.建立与删除建立与删除 B.B.建立与修改建立与修改 C.C.查找与修改查找与修改 D.D.查找与索引查找与索引42四、问答及算法设计四、问答及算法设计四、问答及算法设计四、问答及算法设计1 1简述下列各对术语的区别。简述下列各对术语的区别。空串和空格串；串变量和串常
48、量；主串和子串；串变量的空串和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值名字与串变量的值432 2设有设有A=“”,B=“mule”A=“”,B=“mule”，C=“old”C=“old”，D=“my”,D=“my”,试计算下试计算下列运算的结果列运算的结果(注：注：A+BA+B是是CONCAT(A,B)CONCAT(A,B)的简写的简写,A=“”,A=“”表示含表示含有两个空格的字符串有两个空格的字符串)。(a)A+B (a)A+B (b)B+A (b)B+A (c)D+C+B(c)D+C+B (d)SUBSTR(B,3,2)(d)SUBSTR(B,3,2)(e)SUBST
49、R(C,1,0)(e)SUBSTR(C,1,0)(f)LENGTH(A)(f)LENGTH(A)(g)LENGTH(D)(g)LENGTH(D)(h)INDEX(B,D)(h)INDEX(B,D)(i)INDEX(C,“d”)(i)INDEX(C,“d”)(j)INSERT(D,2,C)(j)INSERT(D,2,C)(k)INSERT(B,1,A)(k)INSERT(B,1,A)(l)DELETE(B,2,2)(l)DELETE(B,2,2)(m)DELETE(B,2,0)(m)DELETE(B,2,0)443 3分别在顺序串和链串上实现串的判相等运算分别在顺序串和链串上实现串的判相等运算E
50、QUAL(S,T)EQUAL(S,T)。4 4若若S S和和T T是用结点大小为是用结点大小为1 1的单链表存储的两个串的单链表存储的两个串(S(S、T T为头指针为头指针)，设计一个算法将串，设计一个算法将串S S中首次与串中首次与串T T匹配的子串逆置。匹配的子串逆置。5 5用串的其他运算构造串的子串定位运算用串的其他运算构造串的子串定位运算indexindex。6 6利用利用C C的库函数的库函数strlenstrlen、strcpystrcpy和和strcatstrcat写一算法写一算法void void StrInsert(char*S,char*T)StrInsert(char*S