数据结构期末复习题.ppt

《数据结构期末复习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、此答案仅供参考第一篇1、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A、110B、108C、100D、120解答：因为：第一个元素的存储地址是100，且每个元素的长度是2，所以第五个元素的地址为：100+2×（5﹣1）=108。答案为：B2、若已知一个栈的入栈序列是1，2，3，…..，n，其输出序列为p1，p2，p3，…..，pn，若p1=n，则pi为（）A、iB、n=iC、n-i+1D、不确定解答：因为p1=n假设：i=1，则pi=n-1+1；若i=2，则pi=n-2+1以此类推，则pi

2、=n-i+1。答案为：C3、栈结构通常采用的两种存储结构是（）A、线性存储结构和链表存储结构B、散列方式和索引方式C、量表存储结构和数组D、线性存储结构和非线性存储结构解答：这个书上有，记下就行。答案选：A4、栈的特点是（），队列的特点是（）A、先进先出B、先进后出解答：假设栈S=（a1,a2,…,an），则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的（如下图所示），因此，栈又称为后进先出，所以栈的特点为：后进先出。ana2

3、a1栈顶栈底出栈进栈……而队列和栈相反，是一种先进先出的线性表。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。所以答案为：B，A5、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）A、（rear-front+m）%mB、rear-front+1C、rear-front-1D、rear-front解答：….…..Q.frontQ.rearMaxsize-1队列如图所示：粉色标注的是队列元素所占的空间，Q.front指向第一个

4、元素，Q.rear指向最后一个元素的下一位，因为该循环队列用数组Ａ【０，ｍ-１】存放其元素值，所以该循环队列共有ｍ个元素空间，再者，因为不知道头尾指针所指向的具体位置（该数组的具体位置）若rear所指向的位置的数字大于front所指向的位置的数字。则，该队列中元素个数为：rear-front。反之得到的结果就是负数了，显然负数不可能是元素个数，此时，用得到的这个负数加上该数组的元素空间，即可得到一个正数，这个正数是元素个数的补数，然后用他除以元素空间个数取余就可以了。例如：如果元素空间个数m为10，头指针指向的位置是2，为指针

5、指向的位置是6，用（2-6+10）/10取余则为4，即元素个数为4，再来验证下，该数组的第2、3、4、5有元素，很显然有四个元素。。。答案选：A8、在具有n个单元的循环队列中，队满时共有_______个元素。解答：队列满的约定条件：队列头指针在队列尾指针的下一位置（指环状的下一位置）上。也就是说，队尾的指针永远指向最后一个元素的下一个结点，当队尾指针的下下个元素是对头指针指向的元素的时候，即可断定该队列是满了…所以该题答案为：n-115、在循环双链表的p所指结点之后插入s所指结点的操作是________abx①②③④p…..…

6、…s解答：如图：将s结点插入p所指结点之后，可分为四部…..①：s->prior=p;②:s->next=p->next;③:p->next->prior=s->next;④:p->next=s;答案即为上面的四部…16、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行ps……①②解答：解答如图所示，可分为两部….①：s->next=p->next；②：p->next=s；18、在栈顶指针为HS的链栈中，判定栈空的条件是_____topbase解答：栈的初始化操作为..按设定的厨师分配量进行第一次存储分

7、配，base的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记…所以答案为：HS=base19、在一个单链表中删除p所指结点时，应执行以下操作：q=p->next；p->data=p->next->data；p->next=______；free(q)；pq解答：因为是单链表，所以如果删除①所在的那个箭头的话，整个链表就断了，就不能找到下一个位置了。所以可以采用另一种方法来实现删除p所指结点，就是将p的下一个结点（这里给他赋值为q）所指的数字放在p所指的结点那里。然后再将

8、q结点删除就可以了。所以答案为：q->next①//定义一个指针q令他指向p的下一个结点//将p的下一个结点的数值放在p所指的结点之上//删除q所指结点//释放q20、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：s->next=_______；p->n