(完整word版)数据结构习题

1、、选择题第 1章 概论1. 要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（A、数据元素具有同一的特点。B、不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致。C、每个数据元素都一样。D、数据元素所包含的数据项的个数要相等。2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ 的（ B ） 和运算的学科。（1） A、操作对象B、计算方法C、逻辑存储（2） A、结构B、关系C、运算3. 数据结构被形式的定义为 （D , R），其中D是（B） 的有限集合。（ 1 ） A 、算法（2）A、操作4. 在数据结构中，c） ）以及它们之间数据映象 算法）的有限集合， R 是

2、D 上（ （ D ） ）D、D、A、动态结构和静态结构C、线性结构和非线性结构5.A、6.B、数据元素C、数据操作B、映象C、存储从逻辑上可以把数据结构分为（ CB、紧凑结构和非紧凑结构D、内部结构和外部结构A ）的存储结构。C、索引存取D、D、A、线性 -表的顺序存储结构是一种（ 随机存取B、顺序存取算法分析的目的是（ C ） 找出数据结构的合理性D、逻辑结构 关系Hash 存取C、分析算法的效率以求改进 7. 计算机算法指的是（C）（1） A、C、（ 2） A、B、C、D、计算方法 解决某一问题的有限运算序列 可行性、 可行性、 确定性、 易读性、B、研究算法中的输入和输出的关系D、分析算

3、法的易懂性和文档性 ）。它必需具备输入、输出和（ （B） ）等五个特征。B、排序方法D、调度方法可移植性和可扩充性确定性和有穷性有穷性和稳定性 稳定性和安全性8.A、 C、 9.A、线性表若采用链表存储结构时，必须是连续的B、一定是不连续的D、在以下的叙述中，正确的是（要求内存中可用存储单元的地址（ 部分地址必须是连续的 连续不连续都可以B ）D）线性表的线性存储结构优于链式存储结构 二维数组是它的每个数据元素为一个线性表的线性表 栈的操作方式是先进先出D、队列的操作方式是先进后出B、C、10. 根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的21数据组织形式。以下解释错

4、误的是(A )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、 线性结构中结点按逻辑关系依次排列形成一条”锁链”C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11. 以下说法正确的是(D )A、数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D数据结构是带有结构的数据元素的集合二、判断题1. 数据元素是数据的最小单位。02. 数据结构是带有结构的数据元素的集合。13. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。14. 数据项是数据的基本单位。0

5、5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。16. 数据的物理结构是数据在计算机中实际的存储形式。17. 算法和程序没有区别，所以在数据结构中二者是通用的。08. 顺序存储结构属于静态结构，链式存储结构属于动态结构。0三、填空题1. 所谓数据的逻辑结构指的是数据元素之间的逻辑关系。2. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容数据的逻辑结构、数据的存储结构、对数据施加的操作。3. 数据的逻辑结构包括集合|、线性结构1、树形结构I和图状构图四种类型。4. 在线性结构中，开始结点 没有前驱结点，其余每个结点有且只有_1个结点。5.

6、在树形结构中，树根结点只有_1，其余每个结点有且只有 _1前驱结点；叶子结点没有后继结点，其余每个结点的后继结点可以_任意个 。6. 在图形结构中，每个结点的前驱结点和后继结点可以有任意个。7. 算法的五个重要特性是_有穷性、_确定性、_可行性 、一输入、输出。8. 下列程序段的时间复杂度是 。for (i=1;i=n ;i+)Aij=0；9. 下列程序段的时间复杂度是 。s=0;for(i=1;i=n ;i+)for(j=1;j=n ;j+) s=s+Bij;sum=s;10. 存储结构是逻辑结构的物理 实现。11. 从数据结构的观点看，通常所说的”数据应分成三个不同的层次，即数据、_数据元

7、素_和_数据项_。12根据需要，数据元素又被称为结点、 记录、 元素或_顶点_。13. 通常，存储结点之间可以有_顺序存储、链式存储、索引存储、散列存储 、四种关联方式，称为四种基本存储方式。14. 通常从_正确性、可读性、健壮性、高效性 、等几方面评价算法的(包括程序)的质量。15. 一个算法的时空性能是指该算法的_时间复杂度 和空间复杂度，前者是算法包含的 _计算量 ，后者是算法需要的_存储量。16. 在一般情况下，一个算法的时间复杂性是_问题规模的函数。17. 常见时间复杂性的量级有：常数阶 0)、对数阶0(_ log 2 n)、线性阶0(n)、平方阶0(n2)、和指数阶0(2n)。通常

8、认为，具有指数阶量级的算法是_不可行的。18. 数据结构的基本任务是数据结构的设计和 实现。19. 数据对象是性质相同的数据元素的集合。20. 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。四、应用题1. 分析下列程序段的时间复杂度。i=1 ；WHILE （ i=n ）i=i*2 ；2. 叙述算法定义及其重要特性。3. 简述下列术语：数据，数据元素，数据结构，数据对象。4. 逻辑结构与存储结构是什么关系？5. 将数量级 210，n, n2, n3, nlog2n，log2n，2n， n , n!，2 3 n，n23,按增长率进行排列。6. 设有数据逻辑结构为：D=k1,k2,k3,

9、 ,k9R=,画出这个逻辑结构的图示，并确定相对于关系 R,哪些结点是开始结点，哪些结点是终端结点？7. 设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。8. 分析下列程序的时间复杂度(设 n 为正整数)(1) int rec(int n)if(n=1) return(1);else return(n*rec(n-1);(2) x=91;y=100;while(y0)if(x10) y-;(3) i=1;j=0;while(i+jj) j+; else i+;(4) x=n;y=0; while(x=(y+1)*(y+1) y+;9. 设 n 为正数。试确定下列

10、各程序段中前置以记号的语句的频度：( 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;jnext=NULLC、head-next=headD 、 head!=NULL10.非空循环单链表head的尾结点*p满足（C）A、p-next=NULLB 、 p=NULLC、p-next=headD、 p=head11.在循环双链表的*p 结点之后插入 *s 结点的操作是（D ）A 、 p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B 、 p-next=s; p-

11、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; snext=pnext; pnext-prior =s;p-next=s;12. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则 执行（ C ）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. 在

12、一个单链表中，若*p结点不是最后结点，在*p之后插入结点*s，则执行（B ）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 ）存储方式最节省时间。A、顺序表B、单链表C、双链表D、单循环链表15. 设 rear 是指向非空带头结点的循环单链表的尾指针，则删除表中第一元素的操作可表 示为( D )A 、 p=rear; rear=rear-next; free(p)B

13、、 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 )A、 q=pf next; pnext=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 指向双链表

14、的某一结点，则双链表结构的对称性可用( C )式来刻画A 、 p-prior-next=p-next-nextB、p-prior-prior=p-next-priorC、p-prior-next=p-next-priorD、p-next-next=p-prior-prior18. 在循环链表中，将头指针改设为尾指针 rear 后，其头结点和尾结点的存储位置分别是 ( B )A 、 rear 和 rear-next-nextB、rear-next 和 rearC、rear-next-next 和 rearD、rear 和 rear-next19. 循环链表主要优点是( D )A、不再需要头指针了

15、B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表20. 在线性表的下列存储结构中，读取元素花费时间最少的是( D )A、单链表B、双链表C、循环链表D、顺序表二、判断题1. 顺序存储的线性表可以随机存取。 A2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。 B3. 线性表中的元素可以是各种各样的， 但同一线性表中的数据元素具有相同的特性， 因此 是属于同一数据对象。 A4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。B5.

16、 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。A6. 在单链表中，可以从头结点进行查找任何一个元素。 A7. 线性表的链式存储结构优于顺序存储结构。 B8. 在线性表的顺序存储结构中， 插入和删除元素时， 移动元素的个数与该元素的位置有关。A9. 在单链表中，要取得某个元素， 只要知道该元素的指针即可， 因此，单链表是随机存取10.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.1.的存储结构。B顺序存储方式只能用于存储线性结构。B填空题为了便于讨论，有时将含 n(n0)个结点的线性结构表示成(a1, a2,an)，其中每个

17、 ai 代表一个_结点 。a1称为_第一个 结点，an称为_最后一个 结点，i称为 ai在线性表中的 位置。对任意一对相邻结点 ai、a十1(K in),ai称为ai十1的直接前驱, a十1称为 ai的直接_后继。线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_前驱外，其他结点有且仅有一个直接 _前驱_;除终端结点没有直接_后继外，其它结点有且仅有一个直接后继.所有结点按1对1的邻接关系构成的整体就是线性_结构。线性表的逻辑结构是_线性结构。其所含结点的个数称为线性表的_长度。在单链表中，删除 p所指结点的直接后继的操作是_ q=ptnext; p宀next=q宀next;fr

18、ee(q);。非空的循环单链表 head的尾结点(由指针 p所指)满足 _ p next=head。rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为_p=rearT n ext; q=p t n ext;p t n ext=q t n ext; free(q)。对于一个具有 n个结点的单链表，在p所指结点后插入一个结点的是时间复杂度为，在给定值为x的结点后插入新结点的时间复杂度为 。单链表表示法的基本思想是用指针表示结点间的逻辑关系。在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与_兀素位置有天。向一个长度为n的向量的第i个元素(1 i n+

19、1)之前插入一个元素时，需向后移动n - i+1个元素。向一个长度为n的向量中删除第i个元素(1 inext=head后，该单 链表构成单循环链表 。在单链表中，若 p和s是两个指针，且满足p-next与s相同，则语句p-next=s-next作用是一删除s指向的结点。设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 _ st next=r-next; r-next=s; r=s;。在单链表中，指针 p所指结点为最后一个结点的条件是_ pt next=NULL。在双循环链表中，若要在指针p所指节点前插入s所指的节点，则需执行下列语句：s_next=p

20、;s_prior=p_prior ;_ pt prior t next=s ;p-prior=s ;20. 在单链表中的 p 所指结点之前插入一个 s 所指结点时，可进行下列操作： s-next= ；p-next=s;temp=p-data； p-data=；s-data=；四、应用题1. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点) 。2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？3. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两 个因素？4. 为什么在单循环链表中设置尾指针比设置头指针更好？5. 双链表和单循环链表中， 若仅

21、知道指针 p 指向某个结点， 不知道头指针， 能否将结点 *p 从相应的链表中删除？若可以，其时间复杂度各为多少？6. 下列算法的功能是什么？ LinkedList test1(LinkedList L) /L 是无头结点的单链表 ListNode *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;7. 如果有 n 个线性表同时共存， 并且在处理过程中各表的长度会发生动态变化， 线性表的 总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？8

22、. 若线性表的总数基本稳定， 且很少进行插入删除操作， 但要求以最快的方式存取线性表 的元素，应该用哪种存储结构。为什么？9. 设有多项式 a(x)=9+8x+9x 4+5x10 b(x)=-2x+22x 7-5x 10 ( 1) 用单链表给出 a(x)、b(x) 的存储表示；(2) 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。第 3章 栈和队列、选择题1. 设有一顺序栈S,元素 s1,s2,s3,s4,s5,s6依次进栈，如果 6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是(b )A 、 2B 、 3C、 5D、 62. 若一个栈的输

23、入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为0maxsize-1a1a2a3(b )A、4B、5C、63.设有一顺序栈已经含有3个兀素，如图的出栈序列是(a)A、a3,a1,a4,a2B、a3,a2,a4,a1D、73.1所示元素a4正等待进栈。下列不可能出现C、a3,a4,a2,a1D、a4,a3,a2,a1Top图3.14. 链栈和顺序栈相比，有一个比较明显的优势是(a )A、通常不会出现栈满的情况B、通常不会出现栈空的情况C、插入操作更容易实现D、删除操作更加容易实现5. 若一个栈的输入序列是1,2,3,4,n，输出序列的第一个元素是n,则第i个输出元素是(c

24、 )A、不确定B、 n-iC、n-i+1D、n-i-16. 以下说法正确的是(a )A、 因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况B、 因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言，在栈满状态下，如果此时再作进栈运算，则会发生“上溢”D、 对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。7. 顺序队列的入队操作应为( a )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)

25、% maxsize; sq.datasq.rear=x;D、sq.datasqrear=x; sq.rear=(sq.rear+1)% maxsize;8. 循环队列的入队操作应为( c )A、sq.rear=sq.rear+1; sq.datasq.rear=xB、sq.datasq.rear=x;sq.rear=sq.rear+1;C、sq.rear=(sq.rear+1)% maxsiae; sq.datasq.rear=x;D、sq.datasq.rear=x; sq.rear=(sq.rear+1)% maxsize;9. 顺序队列的出队操作为(b )A、sq.front=(sq.f

26、ront+1)% maxsize ;B 、sq.front=sq.front+1 ;C、sq.rear=(sq.rear+1)% maxsize ;D、sq.rear=sq.rear+1 ;10. 循环队列的出队操作为(a )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;11. 循环队列的队满条件为(c )A、(sq.rear+1) % maxsize = =(sq.fr on t+1) % maxsize;B、(sq.r

27、ear+1) % maxsize = =sq.front+1C 、 (sq.rear+1) % maxsize = =sq.frontD 、 sq.rear = =sq.front12. 循环队列的队空条件为( d )A 、 (sq.rear+1) % maxsize = =(sq.front+1) % maxsize ；B 、 (sq.rear+1) % maxsize = =sq.front+1 ；C 、 (sq.rear+1) % maxsize = =sq.front ；,则退栈操作时（ c ） B 、判别栈元素的类型 D、 对栈不做任何判别D 、 sq.rear = = sq.fro

28、nt ；13. 如果以链表作为栈的存储结构 A 、必须判别栈是否满C、必须判别栈是否空14. 向一个栈顶指针为 Top 的链栈中插入一个 s 所指结点时，其操作步骤为（ c ）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 ）A 、 x=Top-data;Top=Top-next;B 、 Top=Top-next;x=Top-data;C 、 x=

29、Top;Top=Top-next;D 、 x=Top-data;16. 在一个链队中，若 f,r 分别为队首、队尾指针，则插入s 所指结点的操作为（b ）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则栈的不可能的输出序列是( c )A 、 e d c b aB、 d e c b aC、 d c e a bD、 a b c d eD 、 3，2，4，1 ）数据结构最佳。18. 一个队列的入队序列是1，2，3，4，则队列的可能的输出系列是（b ）A、4，3，2，

30、1B、 1，2，3，4C、 1，4，3，219. 设计一个判别表达式中左、 右括号是否配对出现的算法， 采用（ bA、线性表的顺序存储结构B、栈C 、队列D、线性表的链式存储结构20. 若以 1234 作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输 出受限双端队列得到的输出序列是（ c ）A、 1234B、 4132 C、 4231 D、 4213二、判断题1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢” 。 a2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。b3. 若一个栈的输入序列为1,2, 3,，n,其输出序列的第一个元素为n,则其输出序列的

31、每个元素 ai 一定满足 ai=i+1（i=1,2,n）。b4. 在链队列中,即使不设置尾指针也能进行入队操作。a5. 在对链队列（带头指针）做出队操作时,不会改变front 指针的值。 a6. 循环队列中元素个数为 rear- front 。 b7. 一个栈的输入序列是 1,2,3,4,则在栈的输出序列中可以得到4,3,1,2。 b8. 一个栈的输入序列是 1,2,3,4,则在栈的输出序列中可以得到1,2,3,4。 a9. 若以链表作为栈的存储结构,则进栈需要判断栈是否满。b10. 若以链表作为栈的存储结构,则出栈需要判断栈是否空。a填空题1. 向一个栈顶指针为Top的链栈中插入一个s所指的

32、结点时，其进行的操作是_s-n ext=Top; Top=s。2. 从栈顶指针为 Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_x=Top-data;。在具有n个单元的循环队列中，队满时共有_ n-1个元素。3. 假设以S和X分别表示进栈和退栈操作，则对输入序列 a,b,c,d,e进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为b c e d a。4. 设有数组A0.m作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素 x 执行入队操作的 语句是_if(rear+1)%(m+1)!=front)rear=(rear+1) % (m+1);Are

33、ar=x; 。5. 在一个链队列中，如f,r分别为队首，队尾指针，贝U插入s所指结点的操作是 _ r-next=s;r=s;。6. 栈的逻辑特点是后进先出 ,队列的逻辑特点是_先进先出 ,二者共同特点是操作受限。a) _栈可以作为实现递归函数调用的一种数据结构。b) 在队列中，新插入的结点只能添加到队尾7.链队在一定范围内不会出现队满的情况。当lq.front= =lq.rear时，队中无兀素，此时队空。8. 设一个链栈的栈顶指针为ls，栈中结点的格式为| data next ，栈空的条件是;如果栈不为空，则退栈操作为p=ls;free(p)。9. 对带有头结点的链队列lq,判定队列中只有一个

34、数据元素的条件是 。10. 设有一个空栈，现在输入序列为1, 2, 3, 4, 5,经过push, push, pop, push, pop,push，后栈顶指针所指元素是 411. 设用一维数组 A1.n来表示一个栈，令An为栈底。用整型变量t来指示当前栈顶的位置，At为栈顶元素。往栈中压入一个新元素时，变量t的值减1，从栈中弹出一个元素时，变量t的值加1。设空栈时，有输入序列a,b,c经过push,pop, push, push, pop操作后，从栈中弹出的元素是 c四、应用题1. 试证明：若借助栈由输入序列 1, 2, 3,n得到输出序列p1, p2,pn(它 是输入序列的一个排列)，则

35、在输出序列中不可能出现这样的情形： 存在着ijk,使pipj1) printf(i-);10. 试将下列递归过程改写为非递归过程void digui(int *sum)scanf(x);if(x=0) sum=0;else digui(sum);sum+=x; printf(sum);第 4章 串一、 选择题1. 串是一种特殊的线性表,其特殊性表现在（ b ）A、可以顺序存储B、数据元素是一个字符C可以链接存储B、数据元素可以是多个字符2. 设有两个串P和Q求Q在P中首次出现的位置的运算称为（b ）A、连接 B、模式匹配C 、求子串D、求串长3. 设串 S仁ABCDEFG，S2= PQRST，

36、函数StringConeat（X，Y）返回 X和 Y 串的连接串，SubString （ S，I，J）返回串S的从序号I的字符开始的J个字符组成的子串，StringLength （ S）返回串 S 的长度，贝U StringConeat （ SubString （ S1，2, StringLength( S2)， SubString ( S1， StringLength (S2)， 2)的结果串是( d )。 A、 BCDEFB 、 BCDEFG C 、BCDQRST D 、BCDEFEF、判断题1 子串定位函数的时间复杂度在最坏的情况下为O（n*m ），因此子串定位函数没有实际利用价值。 b

37、2. 设有两个串p和q,其中q是p的子串，把q在p中首次出现的位置作为子串 q在p中 的位置的算法称为匹配。 a3. KMP 算法的最大特点是指示主串的指针不需要回朔。 a三、填空题1. 两个串相等的充分必要条件是_两个串长度相等且各个对应位置的字符也相等。2. 空串是_零个字符的串 ,其长度等于 _0。3. 空格串是 _有一个或多个空格组成的串 ,其长度等于 _串中空格字符的个数4.设 S= 1 T AMT AT TEACHER，其长度是_14_。5.设 S1= GOOD， S2=T， S3= BYE！,则S1, S2 和S3连接后的结果是_ GOODT BYE 。6.设有两个串q和p,求q

38、在p中首次出现的算法叫_匹配 _。7.串的连接运算不满足 _交换律 ,满足 _结合律 _。8.模式串 t= abcaabbcabcabcaabdab的next 函数值为 _0111223112345。四、应用题1. 空串和空格串有何区别？字符串中的空格符有什么意义？空串在串处理中有何作用？2. 字符串 s1=abcdefghijklmnopqrstuvw ,由如下运算分别得到 s2 和 s3 ,请给出 s2 和 s3 的值。s2=StringConcat(SubString(s1,19,3),SubString(s1,4,2),SubString(s1,14,1),SubString(s1,2

39、0,1) , s3=SubString(s1, StringLength(s2), StringLength(s2)3. 设 a,b,c,d 都是串，a= this is a book ,b= ese are ,c= s。求d=StringConcat(SubString(a,1,2),b,SubString(a,10,5),c)的值。4. 知 s= (xyz)* , t= (x+y)*z 。试用连接,求子串和置换等基本运算,将 s 转化为 t ,将 t 转化为 s 。5.令 s= aaab ,t= abcabaa ,u= abcaabbabca baacbacba。分另U求出 s,t,u 的

40、 next 函数值和 nextval 函数值。6. 设 s= 11 AMTLSTUDENT,t= GOOD, q= WORKED。求 ： StringLength(s), StringLength(t),SubString(s,8,7),SubString(t,2,1),Index(s, A ), Index(s,t),StringConcat(SubString(s,6,2),StringConcat(t,SubString(s,7,8)7. 已知下列字符串a= THIS，f= ATSAMPLE，c= GOOD，d= NE，b=T，g= ISs=StringConcat(a,StringCo

41、ncat(SubString(f,2,7),StringConcat(b,SubString(a,3,2) ， t=Replace(f,SubString(f,3,6),c)， u=StringConcat(SubString(c,3,1),d)v=StringConcat(s,StringConcat(b,StringConcat(t,StringConcat(b,u)试问： s，t ， v ， StringLength(s) ， Index(v,g) ， Index(u,g) 各是什么？8. 已知模式串 pat= ADABBADADA, 写出模式串的 nextval 函数值。9. 计算下列

42、串的 next 值：( 1) aaabcaaba( 2) abcabcacb( 3) babbabab第 5章 数组和广义表一、 选择题1. 数组通常具有的两种基本操作是（ c ）A、建立和删除B、索引和修改C、查找和修改D、查找和索引2. 二维数组 A10.20,5.10 采用行序为主序方式存储，每个数据元素占4 个存储单元，且A10 ， 5的存储地址是 1000，则 A18,9 的存储地址是（ a ）A、 1208 B、 1212C、 1368 D、 13643. 三维数组 A0.4,0.5,0.6 ，采用行序为主序方式存储，每个数据元素占2 个存储单元，且第一个元素的存储地址是 120，

43、则 A3,4,5 的存储地址是（ a ）A、 438 B、 358 C、 360 D、 3624. 二维数组 A 中，每个元素的长度为 4个字节，行下标从 0到 4，列下标从 0到 5，A 按 行优先存储时元素 A3,5 的地址与 A 按列优先存储时元素（ b ）的地址相同。A、 A2,4B、 A3,4 C、 A3,5D、 A4,45.对矩阵压缩存储是为了（ bA、方便运算B、节省空间）C、方便存储D、提高运算速度6.稀疏矩阵一般的压缩存储方法有两种，即（c）A 、二元数组和三元数组B、三元组和散列C、二兀组和十字链表D 、散列和十字链表7.广义表（a）,a）的表头是（b）A、 aB、 (a)

44、C、 ( )D、 (a)8.广义表（a）的表尾是（c ）A、 aB、 (a)C、 ( )D、 (a)9.已知广义表 LS = (a,b,c),(d,e,f)，运用GetHead和GetTail函数取出LS中的兀素e的运算是（ c）A、 GetHead(GetTail(LS)B 、 GetTail(GetHead(LS)C、 GetHead(GetTail(GetHead(GetTail(LS)D 、 GetHead(GetTail(GetTail(GetHead(LS)10. 若广义表 A 满足 GetHead(A)=GetTail(A) ，则 A 为( b )A、 ( ) B、 ( )C、

45、( ),( ) D、 ( ),( ),( )、判断题1 数组是同类型值的集合。 b2 数组的存储结构是一组连续的内存单元。 a3. 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。b4. 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使 用。b5. 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。a6. 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。a7. 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。a& 广义表中原子个数即为广义表的长度。b9. 广义表中元素的个数即为广义表的深度。b三、填空题1. 二维数组 A1.1O, 1.20采用列序为主序方式存储，每个元素占一个存储单元，并且A1,1的存储地址是 200,则A6,12的地址是 315。2. 有一个10阶对称矩阵A采用压缩存储方式(以行序为主序方式存储)存储其下三角元素，且第一个元素A1,1的存储地址为1,则A4,5的地址是_14, A8,3的地址是 31。3.下三角矩阵 A1.N,1.N的下三角元素已压缩到一维数组S1.N* ( N+1 ) /2+1中，若按行序为主序存储，则 Ai,j对应的 S 中的存储位置是i(i 1).cJ J当i jk2kN(N 1)1,当ij2002030004.已知一个