---------------------考试---------------------------学资学习网---------------------押题------------------------------《算法与数据结构》第1-6章课堂测验（双号）一、选择题1、已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p,p,…,p,若p=n,则121np的值。（c）i(A)i(B)n-i(C)n-i+1(D)不确定2、设n个元素进栈序列是1,2,3,…,n,其输出序列是p,p,…,p,若p=3,则p2n112的值。（c）(A)一定是2(B)一定是1(C)不可能是1(D)以上都不对3、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（b）A.6B.11C.15D.不确定4、在下述结论中，正确的是（d）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.②③④C.②④D.①④5、一棵树高为K的完全二叉树至少有（）个结点。（a）kk-1k-1kD.21B.2+1C.2A.2–二、简答题1简述下列术语：线性表，顺序表，链表。2线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结3构都相邻。链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。42何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。3链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。4设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。voidListInsert(SqListA,SqListB,SqListC){ElemType*p,*q,*s;P=&A;q=&B;s=&C;while(p.next!=NULL||q.next!=NULL){if(p.next.data<=q.next.data){if(s.next!=NULL)p.next=s.next;s.next=p.next;p++;}else{if(s.next!=NULL)q.next=s.next;s.next=q.next;q++;}}while(p.next!=NULL){p.next=s.next;s.next=p.next;}while(q.next!=NULL){q.next=s.next;s.next=q.next;}4、例：什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？答：在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。解决队列上溢的方法有以下几种:1)建立一个足够大的存储空间,但这样做会造成①采用平移元素:当出现假溢出时可采用以下几种方法(2)空间的使用效率降低。．的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；②每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置；③采用环形队列方式:把队列看成一个首尾相接的环形队列,在环形队列上进行插入或删除运算时仍然遵循“先进先出”的原则。”5、例：对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。解:当已知队首元素的位置front和队列中元素个数count后:队空的条件为:count==0队满的条件为:count==MaxSize计算队尾位置rear:rear=(front+count)%MaxSize对应的算法如下:typedefstruct{ElemTypedata[MaxSize];intfront;/*队首指针*/intcount;/*队列中元素个数*/}QuType;/*队列类型*/voidInitQu(QuType*&q)/*队列q初始化*/{q=(QuType*)malloc(sizeof(QuType));q->front=0;q->count=0;}intEnQu(QuType*&q,ElemTypex)/*进队*/{intrear;if(q->count==MaxSize)return0;/*队满上溢出*/else{r...
