《算法与数据结构》第1-6章课堂测验（双号）
一、选择题
1、已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。（ B ）
(A) i (B) n-i (C) n-i+1 (D) 不确定
2、设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。（ c ）
(A) 一定是2 (B) 一定是1
(C) 不可能是1 (D) 以上都不对
3、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）[n0=n2+1]
A.6 B.11 C.15 D.不确定 4、在下述结论中，正确的是（d ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 5、一棵树高为K的完全二叉树至少有（）个结点。（ c ）
kk-1k-1
A.2 –1 B.2 +1 C.2 D.2k
二、简答题
1 简述下列术语：线性表，顺序表，链表。
答：线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之
外，其它数据元素都是首尾相接的
顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。
链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。
2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优
1
缺点是什么?
不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表； 相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。
3链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? ，
有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻
4设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。 答：
void ListInsert(SqList A,SqList B,SqList C) {
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; }
2
while(q.next!=NULL) {
q.next=s.next; s.next=q.next; }
4、例：什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？
答：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组
的低端还有空闲空间，这种现象叫做假溢出 解决假溢的方法：
将存储队列的数组头尾相接，形成循环队列。队头、队尾指针加1时用语言的取模(余数)运算实现。 队头指针进1: Q.front = (Q.front+1) % MAXQSIZE; 队尾指针进1: Q.rear = (Q.rear+1) %MAXQSIZE;
队列的“上溢”：队列空间已满，而继续往队列中插入元素，就会使数组越界而导致程序代码被破坏，称为“上溢”
为了克服\假上溢\现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种： ·一种是另设一个布尔变量来判断； ·第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空； ·第三种就是用一个计数器记录队列中的元素的总数。
5、例：对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法 。
1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？
答：abc,acb,bac,bca,cba
2循环队列的优点是什么?如何判断它的空和满?
优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分 利用。
3
判断循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法： 一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元素的总数，不仅可判别空或满，还可以得到队列中元素的个数
3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队
列满的条件是什么？
队列为空：front=rear。队满：rear=MAX -1或front=rear (队首指针front ，一个队尾指针rear)
4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队
列满的条件是什么？
循环队列为空：front=rear 。 循环队列满：(rear+1)%MAX=front。 (队首指针front ，一个队尾指针rear)
5设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。
a, b, c, d入队 a, b, c出队
i , j , k , l , m入队 d, i出队
n, o, p, q, r入队 答
6假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操
4
作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。
d, e, b, g, h入队 d, e出队
i , j , k , l , m入队 b出队
n, o, p, q, r入队
⑴假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题：
① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟?
② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?
⑵一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ①各层的结点数是多少?
②编号为i的结点的双亲结点(若存在)的编号是多少?
③编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
三、算法理解
1、已知P结点是某双向链表的中间节点，画图并写出下列操作的语句序列。 （1）在P结点后插入S结点。 （2）删除P结点的后继结点Q。 结点结构如下： Prior Data Next （其中Prior、Data、Next分别为前驱节点指针、数据域、后继节点指针。）
5