1 《算法与数据结构》第1-6 章课堂测验（双号） 一、选择题 1、已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。（ c ） (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 ） A.6 B.11 C.15 D.不确定 4、在下述结论中，正确的是（ d ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 5、一棵树高为K 的完全二叉树至少有（）个结点。（ a ） A.2k –1 B.2k-1 +1 C.2k-1 D.2k 二、简答题 1 简述下列术语：线性表，顺序表，链表。 2 线性表：最常用且最简单的一种数据结构。一个线性表是n 个数据元素的有限序列。 3 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。 4 链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。 2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表； 相反需要经常大量的修改表，但不是频繁 的随机存取的情况下可选用链式表。 3 链表所 表示 的元素是否 有序?如 有序，则有序性体 现 于何处 ?链表所 表示 的元素是否 一定要在物理上是相邻的?有序表的有序性又 如 何理解 ? 答：有序。有序性体 现 在通 过 指针数据元素有序的相连。物理上不一定要相邻。 4 设A 和 B 是两 个按 元素值递 增 有序的单链表，写 一算法将 A 和 B 归 并 为按 按 元素值递 减 有序的单链表 C，试 分 析 算法的时间 复 杂 度。 2 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!=N...
VIP
