数据结构与算法 复习题

《数据结构与算法 复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.设栈s和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈s，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，，则栈s的容量至少应该是()。2.数组Q[0．．n—1]用来表示一个环形队列，f为当前队头元素的前一个位置，r为队尾元素的位置，假定队列中元素的个数总小于n，则计算队列中元素个数的公式为()。3.在一个单链表中删除p所指结点时，应执行以下操作：q=p→next；p→data=p→next→data；p→next=()；frec(q)；4.数据

2、元素之间的关系，在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：()和()。5.一个栈的人栈序列是a，b，c，d，e，则栈的不可能输出序列是()。A)edcbaB)decbaC)dceabD)abcde6.判断一个栈ST(最多元素为mo)为空的条件是（）。A)ST→top<>0B)ST→top=0C)ST→top<>moD)ST→top=mo7.不带头结点的单链表head为空的判定条件是()。A)head==NULLB)head→next==NULLC)head->next=

3、=headD)head!=NULl。8．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:_______；______;9．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。10．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。11．假设有

4、两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。12．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p所指结点之前插入一s结点的C语言描述语句。13．线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性

5、表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？14.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分15.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)16.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）

6、。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front17.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点18．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。19.设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针

7、sq.rear）,则队满的条件为_______。20.用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。21.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）。A)s→next=p→next；p→next=sB)p→next=s→next;s→next=p;C)q→next=s;s→next=p;D)p→next=s;s→next=q;22.回答问题（每题2分）（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存

8、在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。23．设字符串S=‘aabaabaabaac'，P=‘aabaac'（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的