本文共 911 字，大约阅读时间需要 3 分钟。

一、选择题

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（O(n)）。2．设一棵二叉树的深度为k，则该二叉树中最多有（2k-1）个结点。3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（n）。4．在二叉排序树中插入一个结点的时间复杂度为（O(log2n)）。5．设某有向图的邻接表中有n个表头结点和m个表结节点，则该图中有（m）条有向边。

二、填空题

1．直接插入排序的时间复杂度为O(n²)，快速排序的平均时间复杂度为O(nlog₂n)。2．删除结点X需要执行的语句序列为p→rlink=p→rlink p→rlink→llink=p→rlink。3．建立的二叉排序树的高度为3。4．深度为k的完全二叉树中最少有2k-1个结点。5．用筛选法思想建立堆必须从第1个元素开始进行筛选。6．哈夫曼树中有50个叶子结点；若采用二叉链表作为存储结构，则该树中有100个空指针域。7．顺序循环队列中最多能够存储m-1个队列元素；当前实际存储(R-F+M)%M个队列元素。8．插入第i个位置上的数据元素需要移动n-i+1个数据元素；删除第i个位置上的数据元素需要移动n-i个元素。9．以20为中轴的一趟快速排序结果为(16, 18, 19, 22, 30, 32)。10．初始堆为(16, 18, 19, 20, 22, 32)。

三、计算题

1．画出广义表LS=(( ), (e), (a, (b, (c, d))))的头尾链表存储结构。2．(1) 求树(a)的先根序列和后根序列；(2) 求森林先序序列和中序序列；(3) 将此森林转换为相应的二叉树。3．设散列表的地址范围是[0..9]，散列函数为H(key)=（key×2）MOD 9，并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

四、算法设计题

1．设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2．设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3．在链式存储结构上建立一棵二叉排序树。