注：1、除第九题外，其他各题每题10分，第九题20分。

　　2、所有试题的答案写在答题纸上。

　　一、判断下列叙述的对错。

　　（1） 线性表的逻辑顺序与物理顺序总是一致的。

　　（2） 线性表的顺序存储表示优于链式存储表示。

　　（3） 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

　　（4） 二维数组是其数组元素为线性表的线性表。

　　（5） 每种数据结构都应具备三种基本运算：插入、删除和搜索。

　　二、设单链表中结点的结构为

　　typedef struct node { //链表结点定义

　　ElemType data； //数据

　　struct node * Link； //结点后继指针

　　} ListNode；

　　（1） 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？

　　A. s->link = p； p->link = s；

　　B. s->link = p->link； p->link = s；

　　C. s->link = p->link； p = s；

　　D. p->link = s； s->link = p；

　　（2） 非空的循环单链表first的尾结点（由p所指向）满足：

　　A. p->link == NULL；

　　B. p == NULL；

　　C. p->link == first；

　　D. p == first；

　　三、设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？

　　四、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？

　　五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。

　　（1） 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。

　　（2） 采用邻接表存储的图的深度优先遍历算法类似于树的（ C ）。

　　（3） 采用邻接表存储的图的广度优先遍历算法类似于树的（ D ）。

　　（4） 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。

　　供选择的答案

　　A：① n ② n+1 ③ n-1 ④ n+e

　　B：① e/2 ② e ③ 2e ④ n+e

　　C~D：① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历

　　E：① 求关键路径的方法 ② 求最短路径的Dijkstra方法

　　 ③ 深度优先遍历算法 ④ 广度优先遍历算法