河海大学2014年计算机838初试试题
说明:阴影部分为试卷上的原题,还有几个题目的实在是没有回忆出来
一、 选择题(本题共15小题,每题2分,共30分) 1. 【知识点:数组压缩存储】
A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]
中,则对任一上三角元素a[i][j]对应T[k]的下标k 是 。 A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1 2. 【知识点:卡特兰函数有关】 问四个不同的结点可以组成多少种二叉树
3. 【知识点:双链表的插入】
4. 【知识点:入栈和出栈】dcba 5. 【知识点:数组和广义表】
已知广义表L=((x,y,z),a,(u,t,w)),从L 表中取出原子项t 的运算是 。
A. head(tail(tail(L)))
B. tail(head(head(tail(L)))) C. head(tail(head(tail(L))))
D. head(tail(head(tail(tail(L)))))
6. 【知识点:二叉树的前序和中序遍历相反,求二叉树的结构】
对于前序遍历与中序遍历结果相同的二叉树为 ;对于前序遍历和后序遍历结果相同的二叉树为 。 A 一般二叉树 B 只有根结点的二叉树 C 根结点无左孩子的二叉树 D 根结点无右孩子的二叉树
E 所有结点只有左子树的二叉树 F 所有结点只有右子树的二叉树 7. 【知识点:什么散列函数不冲突?】
8. 【知识点:哪一个排序,在最后一趟排序排好之前,所有的关键码都不在最终位置上】 下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell 排序 C. 堆排序 D.冒泡排序 9. 【知识点:前序表达式转换为后序表达式】 10. 【知识点:m阶B-树】 11. 【知识点:k叉树】
12. 【知识点:链表的插入删除】(原题是以下两个中的一道)
设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用 最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
如果某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。那么采用 存储方式最节省运算时间。 A.单链表 B.双链表 C.单循环链表 D.带头结点的双循环链表