数据结构与算法 复习题.doc

1. 设栈s和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈s，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈s的容量至少应该是( )。2. 数组Q0n1用来表示一个环形队列，f为当前队头元素的前一个位置，r为队尾元素的位置，假定队列中元素的个数总小于n，则计算队列中元素个数的公式为( )。3. 在一个单链表中删除p所指结点时，应执行以下操作： q=pnext； pdata=pnextdata； pnext=( )； frec (q)；4. 数据元素之间的关系，在计算机中有两种不同的表示方法，顺序映像和非顺序映像， 并由此得到两种不同的存储结构：( )和( )。5. 一个栈的人栈序列是a，b，c，d，e，则栈的不可能输出序列是( )。 A)edcba B)decba C)dceab D)abcde6. 判断一个栈ST(最多元素为mo)为空的条件是（ ）。A)STtop0 B)STtop=0 C)STtopmo D)STtop=mo7. 不带头结点的单链表head为空的判定条件是( )。 A)head=NULL B)headnext=NULLC)head-next=head D)head!=NULl。8设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_； _;9在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动_个元素。10 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_、_、_、_。11 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。12设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。13线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 14. 一个递归算法必须包括（ ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分15. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 16. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front17. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点18表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是_。19. 设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_。20. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。21. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（ ）。 A)snext=pnext；pnext=s B)pnext=snext;snext=p; C)qnext=s;snext=p; D)pnext=s;snext=q;22. 回答问题（每题2分）（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。23设字符串S=aabaabaabaac，P=aabaac（1）给出S和P的next值和nextval值； （2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。阅读下列说明和流程图，回答问题（1）和问题（2）。说明：流程图是用来实现中序遍历，二叉树存放在数组tree中，每个数组元素存放树中一个结点，每个结点的形式为（值，左指针，右指针），分别用treei.v，treei.l，treei.r来表示第i个结点的值，左指针，右指针，其中左，右指针的值为所指结点在数组中的下标，若指针的值为0，表示它指向空树，图中指针root用以指向二叉树的根结点。问题： （1）填充流程图中的、，使其按中序遍历二叉树。（2）把流程图中的（A）框移至哪个位置（图中）使流程图的算法从中序遍历变成后序遍历。24设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。2已知一个无向图G=（V，E），其中V= V1，V2，V3，V4，V5，V6，其邻接矩阵如下所示：（1） 请还原图G，并写出图G的邻接表；（2） 根据写出的邻接表，求出从V1开始的BFS和DFS遍历序列及生成树；（3） 根据写出的邻接表，画出图G的最小生成树。3什么叫冲突？解决冲突的方法有哪些？68当增量d为1时，该趟希尔排序与