《算法与数据结构》第1-6章课堂测验

1、算法与数据结构第 1-6 章课堂测验1-6 章课堂测验（双号1、已知一个栈的进栈序列是 1,2,3,?,n,其输出序列是 p1,p2,?,pn,p1=n,pi （ C ）(A) i (B) n-i (C) n-i+1 (D) 不确定2n 1,2,3,?,n,p1,p2,?,pn,若p1=3,p2 （ C ）(A) 一定是 2 (B) 一定是 1(C) 不可能是 1 (D) 以上都不对310 2 的结点，5 1 0 的结点个数是（ B ）A.6 B.11 C.15 、在下述结论中，正确的是（D ） 只有一个结点的二叉树的度为 0; 二叉树的度为 2；二叉树的左右子树可任意交换;K 的完全二叉树的

2、结点个数小于或等于深度相同的满二叉树。 A. B. C. D. 5、一棵树高为K 的完全二叉树至少有（）（ A ） A.2k C1 B.2k-1 +1 C.2k-1 D.2k二、 简答题简述下列术语：线性表，顺序表，链表。n 据元素的有限序列。 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。的形式连接起来。何时选用顺序表，何时选用链表作为线性表的存储结构合适?不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；选用链式表。顺序表的主要优点: 没用使用指针，不用花费附加开销 ;元素的读访问非常简洁便利 链表的主要优点：无需事先了解线性表的长度; 允

3、许线性表的长度有很大变化1?表所表示的元素是否一定要在物理上是相邻的?顺序表的有序性又如何理解?A B A 和B 归并为按按元素值递减有序的单链表度。void ListInsert(SqList A,SqList B,SqList C) ElemType *p,*q,*s; P= q= s= 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+;elseif(s.next!=NULL)q.next=s.next;s.next=q.nex

4、t;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; 时间复杂度：length（A）+length（B）. 2法？答：在队列的顺序存储结构中,设头指针为 front,队尾指针 rear,队的容量(存储空间的大小 )为 MaxSize。当有元素加入到队列时 ,若rear=MaxSize(rear=0),该元素不能加元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所:建立一个足够大的存储空间,降低。: 每当队列中加入一个元素时,队列中已有的

5、元素向队头移动一个位置 (,则依次,front 采用环形队列方式:把队列看成一个首尾相接的环形队列,在环形队列上”例：对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,: front count 后:队空的条件为:count=0队满的条件为:count=MaxSize rear: rear=(front+count)%MaxSize : typedef struct ElemType dataMaxSize; int front; /*队首指针*/int count; /*队列中元素个数*/ QuType; /*队列类型*/ void In

6、itQu(QuType *q) /*队列 q 初始化*/ q=(QuType *)malloc(sizeof(QuType)q-front=0q-count=0EnQu(QuType *q,ElemType x/*进队*/int rear;if (q-count=MaxSize) return 0; /*队满上溢出*/ elserear=(q-front+q-count+MaxSize)%MaxSize/*/ 3rear=(rear+1)%MaxSize; /*队尾位置进 1*/ q-datarear=x; q- count+; return 1; int DeQu(QuType *q,Ele

7、mType x) /*出队*/ if (q-count=0) /*队空下溢出*/ return 0; else q-front=(q-front+1)%MaxSize; x=q-dataq-front; q-count-; return 1; int QuEmpty(QuType *q) /*判空*/ return(q-count=0); a, b, 得到哪些输出序列？cba； abc； acb；bac； bca；?”量空间得到充分利用。 判断循环队列的空或满不能以头尾指针是否1 后是设有一个静态顺序队列，向量大小为 MAX条件是什么？队列满的条件是什么？队列为空：front=rear。队满：rear=MAX-1front=rear队首front rear)设有一个静态循环队列，向量大小为MAX条件是什么？队列满的条件是什么？ 。循环队列满：。4(队首指针 front ，一个队尾指针 rear)Q0,6front=rear=0， 请指出其元素，并说明理由。a, b, c, d 入队 a, b, c 出队i , j , k , l , m 入队 d, i 出队n, o, p, q, r 入队其中 l,m,