一、填空题
1．评价算法的五个标准是、、、、和。2．链表最后一个结点的指针指向链表的头节点，这样的链表称为_____链表；链表的每个结点都有两个指针域，一个指针指向前一结点，另一个指针指向后一结点，这样的链表称为_____链表。3．在稀疏矩阵所对应的三元组线形表中，每个三元组元素按_________为主序、________为辅序的次序排列。
4．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为和。5．Hanoi塔、求一个数的阶乘、二叉树遍历等类似问题的解决一般通过使用_____来解决。。
6．在进行直接插入排序时，其数据比较次数与数据的初始排列_____关；而在进行直接选择排序时，其数据比较次数与数据的初始排列____关。
7．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_________ _；r=s; r->next=null;。
8.栈中存取数据的原则，队列中存取数据的原则。
二、选择题
1．在数据结构的讨论中把数据结构从逻辑上分为（）
A．内部结构与外部结构B．静态结构与动态结构
C．线性结构与非线性结构D．紧凑结构与非紧凑结构
2．算法分析的两个主要方面是（）
A．空间复杂性和时间复杂性B．正确性和简明性
C．可读性和文档性D．数据复杂性和程序复杂性
3．一个非空广义表的表头（）
A．不可能是子表B．只能是子表C．只能是原子 D．可以是子表或原子4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( ) A．s->next=p；p->next=s B．s->next=p->next；p->next=s
7．深度为5的二叉树其结点数最多为（）
A．16 B．30 C．31 D．32
8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（）
A．s=rear；rear=rear->next；delete s；B．rear=rear->next；delete rear；
C．rear=rear->next->next；delete rear；D．s=rear->next->next；rear->next->next=s->next；delete s；9．线性表采用链式存储时，结点的存储地址（）
A．必须是不连续的B．连续与否均可
C．必须是连续的D．和头结点的存储地址相连续
三、判断题
1、单链表从任何一个结点出发，都能访问到所有结点。( )
2、将一棵树转换成二叉树后，根结点没有左子树。( )
3、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )
4、在树结构里，有且仅有一个结点没有前驱；非根结点有且仅有一个双亲，且存在一条从根到该
结点的路径（）。
5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）
6、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。( )
7、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。()
四、算法填空题：将折半查找的非递归算法中的空白处进行正确填写。
int Search_Bin(SSTable ST,KeyType key)
{ int low=_______；high=ST.length；（1）
While (low<=high) { (2)
mid=_________________；(3)
if (EQ(key,ST.elem[mid].key ) return __________；
else if (LT(key,ST. elem[mid].key)) __________________；(4)
else __________________；(5)
}
return 0；
}// Search_Bin
五、 综合应用题 （（共 4 小题，每题10分，共计 40 分））
１．下图为某无向图的邻接表，分别写出从A 出发深度优先搜索和广度优先搜索的结果，并画出该无向图的逻辑结构图。 A 5 ^ B
3 7 ^ C 2 6 7 ^ D ^ E 1 ^ F 3 ^ G 2 3 ^ H 9 10 ^
I 8 ^ J
8
^
2．已知指针ha 和hb 分别指向两个单链表的头结点．并且已知两个链表的长度分别为m 和n 。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
1 2 3 4 5 6 7 8 9 10
