权路径长度为（B）A24B71C48D5314．下列哪一种图的邻接矩阵是对称矩阵（B）A．有向图B．无向图C．AOV网D．AOE网15采用顺序查找方法查找长度为
的顺序表时，搜索成功的平均搜索长度为（D）。A
B
2C
12D
12
二、判断题每题1分，共10分
1数据元素是数据的最小单位。×2线性表就是顺序存储的表。×
得分
评阅人
3为了很方便的插入和删除数据，可以使用双向链表存放数据。5一个广义表的表头为空表，则此广义表亦为空表。（6．连通分量指的是有向图中的极大连通子图。（7深度为K的二叉树中结点总数≤2k1。（√×）√）））×）
√
）
4栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√
8二叉树的遍历只是为了在应用中找到一种线性次序。（10关键路径是AOE网中从源点到终点的最长路径。（√
9任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（×
）
第2页共
页
f三、填空题每题2分，共20分
得分
评阅人
1数据结构中评价算法的两个重要指标是
算法的时间复杂度和空间复杂度
。
2一个长度为
的顺序表中第i个元素（1i
）之前插入一个元素时，需向后移动__
i1____个元素。3链接存储的特点是利用__指针___来表示数据元素之间的逻辑关系。4INDEX（‘DATASTRUCTURE’，‘STR’）____5____。5两个字符串相等的充分必要条件是_两串中对应位置的字符相等且长度也相等_。6一棵具有257个结点的完全二叉树，它的深度为9。7一棵完全二叉树有900个结点，则共有450个叶子结点。8由一棵二叉树的前序序列和中序序列唯一确定这棵二叉树。9已知一无向图G（V，E），其中VabcdeEabadacdcbe现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是___深度优先遍历方法。10对于一个具有
个顶点和e条边的连通图，其生成树的边数为
1。
四、应用题（共３０分）
１请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（共6分）voiddemo2Li
kListheadListNodephead是带头结点的单链表，删除P指向的结点ListNodeqheadwhileqifqq
extp
得分
评阅人
qq
ext（2分）
Error“p
oti
head”（2分）（2分）
q
extp
extfreep
第3页共
页
f2已知一棵二叉树的前序遍历的结果是ABECDFGHIJ中序遍历的结果是EBCDAFHIGJ试画出与其对应的二叉树4分，并给出这棵二叉树的后序遍历序列2分。参考答案：根据r