www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档
2．在一个单链表中，在指针P所指向的结点之后插入指针s所指向的结点时，应执行“s一>next=______：”和 “P一>next=_______：”的操作。
3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取 线性表中的元素时，应采用_________存储结构。 4．_______可以作为实现递归函数调用的一种数据结构。
5．对带头结点的链队列lq，判定队列中只有一个数据元素的条件是lq→______→ __==lq→_____。
7．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为______和_____。 8．用于描述分类过程的二叉树称为______。
9．在具有n个顶点的图的生成树中，含有________条边。
10．对n个顶点，e条边的无向图，其邻接表表示中，需要_______ 个结点。 11．在散列存储中，装填因子a的值越大，存取元素时发生冲突的可能性_____，a的值 越小，存取元素时发生冲突的可能性就_____。
12．一个索引顺序表由两部分组成：一个______和一个_____。 13．文件的基本运算有两类：_____和______。
14．对n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是______。 15．按照排序过程涉及的存储设备的不同，排序可分为_____和______。 四、应用题(每小题6分，共24分)
1．已知一棵二叉树的前根遍历结果为ABCDEFGHIJ，中根遍历的结果为CBEDAHGUF，试 画出该二叉树。 2．无向图G如图所示
第 21 页
www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档
试给出(1)该图的邻接矩阵 (2)从A出发的“深度优先”遍历序列 3．如图所示的二叉排序树中
(1)删除关键码15；(2)插入关键码20，分别画出得到的=叉排序树
4．设有一个栈，元素进栈的次序为A，B，C，D，E，写出下列出栈序列的操作序列。 (1)C，B，A，D，E (2)A，C，B，E，D
其中1为进栈操作，0为出栈操作。 五、设计题(每小题6分，共12分)
1．一个带头指针的单链表，写出在其值为X的结点之后插入m个结点的算法。 2．以二叉链表为存储结构，写出求二叉树中叶子数的算法。
第 22 页