数据结构试题及答案(20201222151306)

1、第一章 概论一、选择题1、研究数据结构就是研究（ D ）。A. 数据的逻辑结构 B. 数据的存储结构C. 数据的逻辑结谈判存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作）2、算法分析的两个主要方面是（ A）。A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D）。（ 线性结构就是：在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素, 有除了第一个元素, 集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继 ）（链表、

2、栈、队列、数组、串）A. 图 B. 树 C. 广义表（线性表的推广） D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、 （B）等5 个特性。A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。for(i=0;im;i+)for(j=0;jn;j+)aij=i*j;A. O(m2) B. O(n 2) C. O(m*n) D. O(m+n)6、算法是（ D ）。 为了解决某一问题而规定的一个有限长的操作序列A. 计算机程序 B. 解决问题的计算方法

3、C. 排序算法 D. 解 决问题的 有限运算序列7、某算法的语句执行频度为（ 3n+nlog 2n+n2+8 ）, 其时间复杂度表示（ C ）。A. O(n) B. O(nlog 2n) C. O(n2 ) D. O(log 2n)8、下面程序段的时间复杂度为（ C）。i=1;while(i=n)i=i*3;A. O(n) B. O(3n) C. O(log 3n) D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。 （关系和操作）A. 结构 B. 关系 C. 运算 D. 算法10 、下面程序段的时间复杂度是（ A）。i=s=

4、0;while(s=(y+1)*(y+1)y=y+1;A.O(n) B. O( n) C. O(1) D. O(n2)二、填空题1、程序段“ i=1;while(i=n) i=i*2; ”的时间复杂度为 log2n 。2、数据结构的四种基本类型中, 树形结构 的元素是一对多关系。三、综合题1、将数量级 O(1),O(N),O(N2),O(N 3),O(NLOG 2N),O(LOG 2N),O(2 N) 按增长率由小到大排序。参考答案： O(1) O(log 2N) O(N) O(Nlog 2N) O(N2) O(N 3) O(2N )一、填空题1. 数据结构被形式地定义为 （D, R ）,其中

5、 D 是数据元素 的有限集合, R 是 D 上的 关系有限集合。2. 数据结构包括数据的 逻辑结构、数据的 存储结谈判数据的 运算这三个方面的内容。3. 数据结构按逻辑结构可分为两大类,它们分别是 线性结谈判非线性结构 。4. 线性结构中元素之间存在 一对一关系,树形结构中元素之间存在 一对多关系,图形结构中元素之间存在多对多关系。5在线性结构中,第一个结点 没有前驱结点,其余每个结点有且只有 1 个前驱结点；最后一个结点 没有后续结点,其余每个结点有且只有 1 个后续结点。6. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续结点,其余每个结点的后

6、续结点数可以 任意多个。7. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个 。8数据的存储结构可用四种基本的存储方法表示,它们分别是 顺序、链式、索引、散列。9. 数据的运算最常用的有 5 种,它们分别是 插入、删除、修改、查找、排序 。10. 一个算法的效率可分为 时间效率和 空间效率。11.任何一个 C 程序都由 一个主函数 和若干个被调用的其它函数组成。二、单项选择题（B）1. 非线性结构是数据元素之间存在一种：A ）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系（C）2. 数据结构中,与所使用的计算机无关的是数据的结构；A) 存储 B)物理 C)逻辑 D)物

7、理和存储（C）3. 算法分析的目的是：A) 找出数据结构的合理性 B)研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D)分析算法的易懂性和文档性（A）4. 算法分析的两个主要方面 5 是：A) 空间复杂性和时间复杂性 B)正确性和简明性C)可读性和文档性 D)数据复杂性和程序复杂性（C）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C)解决问题的有限运算序列 D)调度方法（B）6. 计算机算法必须具备输入、输出和等 5 个特性。A) 可行性、可移植性和可扩充性 B)可行性、确定性和有穷性C)确定性、有穷性和稳定性 D) 易读性、稳定性和安全性三、简答题1.数据结谈判数据类

8、型两个概念之间有区别吗？答：简单地说, 数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素, 而且还在其上定义了一组操作。2. 简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的, 非线性结构反映结点间的逻辑关系是多对多的。四、分析下面各程序段的时间复杂度2. s=0;1. for (i=0; in; i+) for (j=0; jm; j+) Aij=0;for (i=0; in; i+)for(j=0; jn; j+)s+=Bij;sum=s;3. x=0;for(i=1; in; i+)for (j=1; j=n-i; j+

9、)x+;4. i=1;while(inext=head B. p-next=NULLC. p=NULL D. p=head6、链表不具有的特点是（） 。A. 可随机访问任一元素 B. 插入删除不需要移动元素C. 不必事先预计存储空间 D. 所需空间与线性表长度成正比7、在双向循环链表中,在 p指针所指的结点后插入一个指针 q所指向的新结点,修改指针的操作是（）。A. p-next=q;q-prior=p;p-next-prior=q;q-next=q;B. p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C. q-prior=p;q-next=p

10、-next;p-next-prior=q;p-next=q;D. q-next=p-next;q-prior=p;p-next=q;p-next=q;8、线性表采用链式存储时,结点的存储地址（） 。A. 必须是连续的 B. 必须是不连续的C. 连续与否均可 D. 和头结点的存储地址相连续9、在一个长度为 n 的顺序表中删除第 i 个元素,需要向前移动（）个元素。A. n-i B. n-i+1 C. n-i-1 D. i+110 、线性表是 n 个（）的有限序列。A. 表元素 B. 字符 C. 数据元素 D. 数据项11 、从表中任一结点出发,都能扫描整个表的是（） 。A.单链表 B.顺序表 C

11、. 循环链表 D. 静态链表12 、在具有 n个结点的单链表上查找值为 x的元素时,其时间复杂度为（） 。A. O(n) B. O(1) C. O(n2 ) D. O(n-1)13 、线性表 L=(a1,a2, ,an) ,下列说法正确的是（） 。A. 每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大到小D. 除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继14 、一个顺序表的第一个元素的存储地址是 90 ,每个元素的长度为2,则第 6 个元素的存储地址是（） 。A. 98 B. 100 C. 102 D

12、. 10615 、在线性表的下列存储结构中,读取元素花费的时间最少的是（） 。A.单链表 B. 双链表 C. 循环链表 D.顺序表16 、在一个单链表中,若删除 p所指向结点的后续结点,则执行（） 。A. p-next=p-next-next;B. p=p-next;p-next=p-next-next;C. p =p-next;D. p=p-next-next;17 、将长度为n 的单链表连接在长度为m的单链表之后的算法的时间复杂度为（） 。A. O(1) B. O(n) C. O(m) D. O(m+n)18 、线性表的顺序存储结构是一种（）存储结构。A. 随机存取 B.顺序存取 C. 索

13、引存取 D. 散列存取19 、顺序表中,插入一个元素所需移动的元素平均数是（） 。A. (n-1)/2 B. n C. n+1 D. (n+1)/210 、循环链表的主要优点是（） 。A. 不再需要头指针B. 已知某结点位置后能容易找到其直接前驱C. 在进行插入、删除运算时能保证链表不断开D. 在表中任一结点出发都能扫描整个链表11 、不带头结点的单链表 head为空的判定条件是（） 。A. head=NULL B. head-next=NULLC. head-next=head D. head!=NULL12 、在下列对顺序表进行的操作中,算法时间复杂度为O(1) 的是（）。A.访问第 i个

14、元素的前驱（ 1next=s-next ；s-next=p ；B. s-next=p ；q-next=s-next ；C. p-next=s-next ；s-next=q ；D. s-next=q ；p-next=s-next ；14、在以下的叙述中,正确的是（） 。A.线性表的顺序存储结构优于链表存储结构B. 线性表的顺序存储结构适用于频繁插入 /删除数据元素的情况C. 线性表的链表存储结构适用于频繁插入 /删除数据元素的情况D. 线性表的链表存储结构优于顺序存储结构15、在表长为 n 的顺序表中, 当在任何位置删除一个元素的概率相同时, 删除一个元素所需移动的平均个数为（） 。A. (n-

15、1)/2 B. n/2 C. (n+1)/2 D. n16、在一个单链表中, 已知 q 所指结点是 p 所指结点的前驱结点, 若在 q 和 p 之间插入一个结点 s,则执行（） 。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;17、在单链表中,指针 p指向元素为 x 的结点,实现删除 x的后继的语句是（） 。A. p=p-next; B. p-next=p-next-next;C. p-next=p; D.p=p-next-next;18 、在头指针为

16、 head 且表长大于 1 的单循环链表中,指针 p 指向表中某个结点,若p-next-next=head ,则（）。A. p指向头结点 B. p 指向尾结点 C. p的直接后继是头结点D. p的直接后继是尾结点二、填空题1、设单链表的结点结构为 （data,next ）。已知指针 p 指向单链表中的结点, q指向新结点,欲将q插入到 p结点之后,则需要执行的语句： q-next=p-next,p-next=q 。参考答案： q-next=p-next p-next=q2、线性表的逻辑结构是线性结构,其所含元素的个数称为线性表的长度。参考答案： 线性结构 长度3、写出带头结点的双向循环链表 L

17、 为空表的条件 L-prior=L-next=L 。参考答案： L-prior=L-next=L4、带头结点的单链表 head 为空的条件是 head-next=null 。参考答案： head-next=NULL5、在一个单链表中删除 p所指结点的后继结点时,应执行以下操作：q= p-next;p-next=_q-next _;参考答案： q-next三、判断题1、单链表不是一种随机存储结构。2、在具有头结点的单链表中,头指针指向链表的第一个数据结点（的存储位置） 。3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针。4、顺序存储方式只能用于存储线性结构。5、在线性表的顺

18、序存储结构中, 逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。6、链式存储的线性表可以随机存取。四、程序分析填空题1、函数 GetElem 实现返回单链表的第 i 个元素,请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p ；int j ；p=L-next;j=1;while(p&ji) return ERROR;*e= p-data (2) ;return OK;参考答案： (1) p=p-next (2)p-data2、函数实现单链表的插入算法,请在空格处将算法补充完整。int ListInsert(Lin

19、kList L,int i,ElemType e)LNode *p,*s;int j;p=L;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL|ji-1) return ERROR;s=(LNode *)malloc(sizeof(LNode);s-data=e;(1) s-next=p-next ;(2) p-next=s ;return OK;/*ListInsert*/参考答案： (1) s-next=p-next (2)p-next=s3、函数 ListDelete_sq 实现顺序表删除算法,请在空格处将算法补充完整。int ListDelete_sq(Sq

20、list *L,int i)int k;if(iL-length) return ERROR;for(k=i-1;klength-1;k+)L-slistk=L-slistk+1 （1）;（2）-L-Length;return OK;参考答案：（1）L-slistk+1 （2） -L-Length4、函数实现单链表的删除算法,请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s)LNode *p,*q;int j;p=L;j=0;while( p-next!=null （1）)&(jnext;j+;if(p-next=NULL|ji-

21、1) return ERROR;q=p-next;p-next=q-next （2 ）;*s=q-data;free(q);return OK;/*listDelete*/参考答案： (1)p-next!=NULL (2)p-next=q-next5、写出算法的效用。int L(head)node * head;int n=0;node *p;p=head;while(p!=NULL) p=p-next;n+;return(n);参考答案：求单链表 head的长度五、综合题1、编写算法,实现带头结点单链表的逆置算法。参考答案： void invent(Lnode *head)Lnode *p,

22、*q;if(!head-next) return ERROR;p=head-next; q=p-next; p-next =NULL;while(q)p=q; q=q-next; p-next=head-next; head-next=p;2、有两个循环链表,链头指针分别为 L1 和 L2 ,要求写出算法将 L2 链表链到 L1 链表之后,且连接后仍保持循环链表形式。参考答案： void merge(Lnode *L1, Lnode *L2)Lnode *p,*q ;while(p-next!=L1)p=p-next;while(q-next!=L2)q=q-next;q-next=L1; p

23、-next =L2;3、设一个带头结点的单向链表的头指针为 head,设计算法,将链表的记录,按照 data 域的值递增排序。参考答案： void assending(Lnode *head)Lnode *p,*q , *r, *s;p=head-next; q=p-next; p-next=NULL;while(q)r=q; q=q-next;if(r-datadata)r-next=p; head-next=r; p=r; elsewhile(!p & r-datap-data)s=p; p=p-next; r-next=p; s-next=r;p=head-next; 4、编写算法 ,将

24、一个头指针为 head 不带头结点的单链表改造为一个单向循环链表,并分析算法的时间复杂度。参考答案：void linklist_c(Lnode *head)Lnode *p; p=head;if(!p) return ERROR;while(p-next!=NULL)p=p-next;p-next=head;设单链表的长度（数据结点数）为 N,则该算法的时间主要花费在查找链表最后一个结点上（算法中的 while 循环）,所以该算法的时间复杂度为 O（N）。5 、已知 head 为带头结点的单循环链表的头指针,链表中的数据元素依次为（ a1 ,a2,a3,a4, , ,an ）,A 为指向空的顺

25、序表的指针。阅读以下程序段,并回答问题：（1 ）写出执行下列程序段后的顺序表 A中的数据元素；（2 ）简要叙述该程序段的效用。if(head-next!=head)p=head-next;A-length=0;while(p-next!=head)p=p-next;A-dataA-length +=p-data;if(p-next!=head)p=p-next;参考答案：(1) (a2, a4, , , ) (2) 将循环单链表中偶数结点位置的元素值写入顺序表 A6、设顺序表 va 中的数据元数递增有序。试写一算法,将 x 插入到顺序表的适当位置上,以保持该表的有序性。参考答案：void In

26、sert_sq(Sqlist va, ElemType x)int i, j, n;n=length(va);if(x=vai)van=x;elsei=0;while(xvai) i+;for(j=n-1;j=I;j-)vaj+1=vaj;vai=x; n+;7 、假 设线性 表采用 顺序存储 结构, 表中元 素值为 整型。阅 读算法 f2 , 设顺序 表L=(3,7,3,2,1,1,8,7,3), 写出执行算法 f2 后的线性表 L的数据元素, 并描述该算法的功能。void f2(SeqList *L)int i,j,k;k=0;for(i=0;ilength;i+)for(j=0;jdat

27、ai!=L-dataj;j+);if(j=k)if(k!=i)L-datak=L-datai;k+;L-length=k;参考答案：(3,7,2,1,8) 删除顺序表中重复的元素8、已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一算法,删除表中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同时释放被删除结点空间。参考答案：void Delete_list(Lnode *head, ElemType x, ElemType y)Lnode *p, *q;if(!head) return ERROR;p=head; q=p;while(!p)if(p-datax) & (

28、p-datanext; free(p);p=head; q=p; elseq-next=p-next; free(p);p=q-next; elseq=p; p=p-next; 9、在带头结点的循环链表 L 中,结点的数据元素为整型,且按值递增有序存放。给定两个整数 a 和 b,且 arear=Q-front B. Q-rear=Q-front+1C. Q-front=(Q-rear+1)%n D. Q-front=(Q-rear-1)%n3、设计一个判别表达式中括号是否配对的算法,采用（）数据结构最佳。A. 顺序表 B. 链表 C. 队列 D. 栈4、带头结点的单链表 head 为空的判定条

29、件是（） 。A. head=NULL B. head-next=NULLC. head-next!=NULL D. head!=NULL5、一个栈的输入序列为： 1,2,3,4 ,则栈的不可能输出的序列是（） 。A. 1243 B. 2134 C. 1432 D. 4312 E. 32146、若用一个大小为 6 的数组来实现循环队列,且当 rear 和front 的值分别为 0,3。当从队列中删除一个元素,再加入两个元素后, rear 和front 的值分别为（） 。A. 1 和5 B. 2 和4 C. 4 和2 D. 5 和17、队列的插入操作是在（） 。A. 队尾 B. 队头 C. 队列任

30、意位置 D. 队头元素后8、循环队列的队头和队尾指针分别为 front 和rear ,则判断循环队列为空的条件是（） 。A. front=rear B. front=0C. rear=0 D. front=rear+19、一个顺序栈 S,其栈顶指针为 top ,则将元素 e 入栈的操作是（） 。A. *S-top=e;S-top+; B. S-top+;*S-top=e;C. *S-top=e D. S-top=e;10 、表达式 a*(b+c)-d 的后缀表达式是（） 。A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd11 、将递归算法转换成对应的非递归算

31、法时,通常需要使用（）来保存中间结果。A. 队列 B. 栈 C. 链表 D. 树12 、栈的插入和删除操作在（） 。A. 栈底 B. 栈顶 C. 任意位置 D. 指定位置13 、五节车厢以编号 1,2,3,4 ,5 顺序进入铁路调度站（栈） ,可以得到（）的编组。A. 3 ,4,5,1 ,2 B. 2 ,4,1 ,3,5C. 3 ,5,4,2 ,1 D. 1 ,3,5 ,2,414 、判定一个顺序栈 S（栈空间大小为 n）为空的条件是（） 。A. S-top=0 B. S-top!=0C. S-top=n D. S-top!=n15 、在一个链队列中, front 和rear 分别为头指针和尾

32、指针,则插入一个结点 s的操作为（）。A. front=front-next B. s-next=rear;rear=sC. rear-next=s;rear=s; D. s-next=front;front=s;16 、一个队列的入队序列是 1,2 ,3 ,4,则队列的出队序列是（） 。A. 1 ,2,3,4 B. 4 ,3 ,2 ,1C. 1 ,4,3,2 D. 3 ,4 ,1 ,217 、依次在初始为空的队列中插入元素 a,b,c,d 以后,紧接着做了两次删除操作,此时的队头元素是（） 。A. a B. b C. c D. d18 、正常情况下, 删除非空的顺序存储结构的堆栈的栈顶元素,

33、 栈顶指针 top 的变化是 （）。A. top 不变 B. top=0 C. top=top+1 D. top=top-119 、判断一个循环队列 Q（空间大小为 M）为空的条件是（） 。A. Q-front=Q-rear B. Q-rear-Q-front-1=MC. Q-front+1=Q-rear D. Q-rear+1=Q-front20、设计一个判别表达式中左右括号是否配对出现的算法,采用（）数据结构最佳。A. 线性表的顺序存储结构 B. 队列 C. 栈 D. 线性表的链式存储结构21、当用大小为 N的数组存储顺序循环队列时,该队列的最大长度为（） 。A. N B. N+1 C.

34、N-1 D. N-222、队列的删除操作是在（） 。A. 队首 B. 队尾 C. 队前 D. 队后23、若让元素 1,2,3依次进栈,则出栈次序不可能是（） 。A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,224 、循环队列用数组 A0 ,m-1 存放其元素值,已知其头尾指针分别是 front 和rear ,则当前队列中的元素个数是（） 。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front25 、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入

35、该缓冲区, 而打印机则从该缓冲区中取走数据打印。 该缓冲区应该是一个（）结构。A. 堆栈 B. 队列 C. 数组 D. 线性表26 、栈和队列都是（） 。A. 链式存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构27 、在一个链队列中,假定 front 和rear分别为队头指针和队尾指针,删除一个结点的操作是（）。A. front=front-next B. rear= rear-nextC. rear-next=front D. front-next=rear28、队和栈的主要区别是（） 。A. 逻辑结构不同 B. 存储结构不同C. 所包含的

36、运算个数不同 D. 限定插入和删除的位置不同二、填空题1、设栈 S和队列 Q的初始状态为空,元素 e1,e2,e3,e4,e5,e6 依次通过栈 S,一个元素出栈后即进入队列 Q,若6个元素出队的序列是 e2,e4,e3,e6,e5,e1 ,则栈的容量至少应该是。参考答案： 32、一个循环队列 Q的存储空间大小为 M, 其队头和队尾指针分别为 front 和rear ,则循环队列中元素的个数为： 。参考答案： (rear-front+M)%M3、在具有 n个元素的循环队列中,队满时具有个元素。参考答案： n-14、设循环队列的容量为 70 ,现经过一系列的入队和出队操作后, front 为20

37、 ,rear 为11 ,则队列中元素的个数为。参考答案： 615、已知循环队列的存储空间大小为 20,且当前队列的头指针和尾指针的值分别为 8和3,且该队列的当前的长度为 _。三、判断题1、栈和队列都是受限的线性结构。2、在单链表中,要访问某个结点,只要知道该结点的地址即可；因此,单链表是一种随机存取结构。3、以链表作为栈的存储结构,出栈操作必须判别栈空的情况。四、程序分析填空题1、已知栈的基本操作函数：int InitStack(SqStack *S); / 构造空栈int StackEmpty(SqStack *S);/ 判断栈空int Push(SqStack *S,ElemType e

38、);/ 入栈int Pop(SqStack *S,ElemType *e);/ 出栈函数conversion 实现十进制数转换为八进制数,请将函数补充完整。void conversion()InitStack(S);scanf( “%d”,&N);while(N)（1）;N=N/8;while( （2 ）)Pop(S,&e);printf( “%d”,e);/conversion参考答案：（1）Push(S,N%8) （2）!StackEmpty(S)2、写出算法的效用。int function(SqQueue *Q,ElemType *e)if(Q-front=Q-rear)return E

39、RROR;*e=Q-baseQ-front;Q-front=(Q-front+1)%MAXSIZE;return OK;3、阅读算法 f2, 并回答下列问题：（1）设队列 Q=（1,3 ,5 ,2,4,6）。写出执行算法 f2 后的队列 Q;（2）简述算法 f2 的效用。void f2(Queue *Q)DataType e;if (!QueueEmpty(Q)e=DeQueue(Q);f2(Q);EnQueue(Q,e);参考答案：（1）6,4,2,5,3,1 （2）将队列倒置五、综合题1、假设以带头结点的循环链表表示队列, 并且只设一个指针指向队尾结点, 但不设头指针,请写出相应的入队列算

40、法（用函数实现） 。rear参考答案： void EnQueue(Lnode *rear, ElemType e) Lnode *new;New=(Lnode *)malloc(sizeof(Lnode);If(!new) return ERROR;new-data=e; new-next=rear-next;rear-next=new; rear =new;2、已知 Q是一个非空队列, S 是一个空栈。编写算法,仅用队列和栈的 ADT 函数和少量工作变量,将队列 Q的所有元素逆置。栈的 ADT 函数有：void makeEmpty(SqStack s); 置空栈void push(SqSta

41、ck s,ElemType e); 元素 e 入栈ElemType pop(SqStack s); 出栈,返回栈顶元素int isEmpty(SqStack s); 判断栈空队列的 ADT 函数有：void enQueue(Queue q,ElemType e); 元素 e 入队ElemType deQueue(Queue q); 出队,返回队头元素int isEmpty(Queue q); 判断队空参考答案： void QueueInvent(Queue q) ElemType x;makeEmpty(SqStack s);while(!isEmpty(Queue q)x=deQueue(Q

42、ueue q);push(SqStack s, ElemTypex);while(!isEmpty(SqStack s)x=pop(SqStack s);enQueue(Queue q, ElemType x);3、对于一个栈,给出输入项 A,B,C,D ,如果输入项序列为 A,B,C,D ,试给出全部可能的输出序列。参考答案：出栈的可能序列：ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDACBDA CBAD CDBA DCBA第四章 串一、选择题1、设有两个串 S1和S2 ,求串 S2在S1中首次出现位置的运算称作（ C ）。A. 连接 B. 求子串

43、C. 模式匹配 D. 判断子串2、已知串 S=aaab ,则 next 数组值为（ A ）。A. 0123 B. 1123 C. 1231 D. 12113、串与普通的线性表相比较,它的特殊性体现在（ C）。A. 顺序的存储结构 B. 链式存储结构 C. 数 据元素 是一个字符 D. 数据元素任意4、设串长为 n,模式串长为 m,则 KMP算法所需的附加空间为（ A ）。A. O(m) B. O(n) C. O(m*n) D. O(nlog 2m)5、空串和空格串（ B）。A. 相同 B. 不相同 C. 可能相同 D. 无法确定6、与线性表相比,串的插入和删除操作的特点是（） 。A. 通常以串

44、整体作为操作对象 B. 需要更多的辅助空间C. 算法的时间复杂度较高 D. 涉及移动的元素更多7、设SUBSTR(S,i,k) 是求 S中从第 i 个字符开始的连续 k个字符组成的子串的操作,则对于S=Beijing&Nanjing ,SUBSTR(S,4,5)= （ B ）。A. ijing B. jing& C. ingNa D. ing&N 二、判断题（）1、造成简单模式匹配算法 BF算法执行效率低的原因是有回溯存在。（ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。（ ）3、完全二叉树某结点有右子树,则必然有左子树。三、填空题1、求子串在主串中首次出现的位置的运算称为 模式匹配

45、 。2、设s=I AM ATEACHER , 其长度是 _。3、两个串相等的充分必要条件是两个串的长度相等且 对应位置字符相同 。四、程序填空题1、函数 kmp 实现串的模式匹配,请在空格处将算法补充完整。intkmp(sqstring *s,sqstring *t,int start,int next)int i=start-1,j=0;while(ilen&jlen)if(j=-1|s-datai=t-dataj)i+;j+;else j=;if(j=t-len)return();elsereturn(-1);2、函数实现串的模式匹配算法,请在空格处将算法补充完整。intindex_bf(

46、sqstring*s,sqstring *t,int start)int i=start-1,j=0;while(ilen&jlen)if(s-datai=t-dataj)i+;j+;elsei= i-j+1 ;j=0;if(j=t-len)return i-t-len+1 ;elsereturn -1;/*listDelete*/3、写出下面算法的效用。int function(SqString *s1,SqString *s2)int i;for(i=0;ilength&ilength;i+)if(s-datai!=s2-datai)return s1-datai-s2-datai;ret

47、urn s1-length-s2-length;参考答案： .串比较算法4、写出算法的效用。int fun(sqstring*s,sqstring *t,int start)int i=start-1,j=0;while(ilen&jlen)if(s-datai=t-dataj)i+;j+;elsei=i-j+1;j=0;if(j=t-len)return i-t-len+1;elsereturn -1;参考答案：串的模式匹配算法第五章 数组和广义表一、选择题1、设广义表 L=(a ,b,c) ,则 L的长度和深度分别为（ C ）。A. 1 和1 B. 1 和3 C. 1 和2 D. 2 和3

48、2、广义表 (a),a) 的表尾是（ B ）。A. a B. (a) C. () D. (a)3、稀疏矩阵的常见压缩存储方法有（ C ）两种。A. 二维数组和三维数组 B. 三元组和散列表 C. 三元组和十字链表D. 散列表和十字链表4、一个非空广义表的表头（ D）。A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可 以是子表或原子5、数组A0.5,0.6 的每个元素占 5 个字节, 将其按列优先次序存储在起始地址为 1000的内存单元中,则元素 A55 的地址是（ A）。A. 1175 B. 1180 C. 1205 D. 12106、广义表 G=(a,b(c,d,(e,f),g) 的长度是（ A ）。A. 3 B. 4 C. 7 D. 87、采用稀疏矩阵的三元组表形式进行压缩存储,若要完成对三元组表进行转置,只要将行和列对换,这种说法（ B ）。A. 正确 B. 错误 C. 无法确定 D. 以上均不对8、广义表 (a,b,c) 的表尾是（ B ）。A. b,c B. (b,c) C. c D. (c)9、常对数