数据结构与算法 复习题

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

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==headD)head!=NULl。8．设单链表的结点结构为(d

3、ata,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）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？14.一个递归算法

5、必须包括（）。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，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front17.栈和队列的共同点是（

6、）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点18．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。19.设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。20.用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。21.在一个单链表中，已知q所指结点是p所指结点的

7、前驱结点，若在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）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。23．设字符串

8、S=‘aabaabaabaac'，P=‘aabaac'（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的