中山大学考研真题

题目	题型
用一维数组来存储满二叉树，若数组下标从0开始，则元素下标为k（k>0）的父结点下标是（）	单选
对任意一棵二叉树T，H(T)表示树的高度。若树T含有n个结点，那么（）	单选
用邻接矩阵存储有n个结点(0,1,...,n)和e条边的有向图(0≤e≤n(n-1))。在邻接矩阵中删除结点i(0≤i≤n-1)的时间复杂度是（）	单选
用邻接矩阵存储有 n 个结点 (0,1,...,n) 和 e 条边的有向图 (0≤e≤n(n-1))。判断结点 i，j（0≤i，j≤n-1）有边的时间复杂度是（）	单选
下列排序算法中，平均时间复杂度为O(n 2 )的是（）	单选
对n个数进行排序时，基于比较的排序算法至少需要比较的次数为（）	单选
用基数（桶）排序算法对32位无符号数按字节进行排序时，即：先用最后一个字节（最低字节）进行排序，再依次用第二、第三和第四个字节进行排序。需要桶的个数是（）	单选
用基数（桶）排序算法对32位无符号数按字节进行排序时，即：先用最后一个字节（最低字节）进行排序，再依次用第二、第三和第四个字节进行排序。需要桶的个数是（）	单选
假设有n个待查找关键字，有关折半查找算法的不正确描述是（）	单选
在下列算法中，求图中两点之间最短路径的算法是（）	单选
已知一个无向图的顶点集为{a,b,c,d,e,f,g},其邻接矩阵如下所示（0-无边，1-有边）。	问答
简单描述求图最小生成树的Kruskal算法（克鲁斯科尔算法）的基本思想，并按步骤列出图2的最小生成树的求解过程。	问答
简单叙述堆排序算法（HeapSort）的基本思想。按“由小到大”排序所给的数值，并按排序步骤列出每次已堆化好的待排数值序列。可不列出“已排好”的数值和堆化过程中的堆形状或数值序列。如果给额外信息，将判断这些信息的正确性。	问答
在表中对关键字50和36进行查找时，所需进行的比较次数为多少？依次写出每次计算公式和值。	问答
在表中对关键字50和36进行查找时，所需进行的比较次数为多少？依次写出每次计算公式和值。	问答
阅读理解题，按空白编号填写相应的C/C++语言语句，以实现函数功能。	问答
阅读理解题，按空白编号填写相应的C/C++语言语句，以实现函数功能。	问答
假设二叉树T=<T L ,root,T R >中结点数的定义如下：	问答
用C/C++语言实现下面函数的功能。	问答
编写函数Find(BSNode *root,int key)，其功能是在以结点root为根的二叉搜索树中找“比参数key大的最小值”。若找不到，则返回NULL，否则，返回该结点地址。	问答

题目

题型

用一维数组来存储满二叉树，若数组下标从0开始，则元素下标为k（k>0）的父结点下标是（）

单选

对任意一棵二叉树T，H(T)表示树的高度。若树T含有n个结点，那么（）

单选

用邻接矩阵存储有n个结点(0,1,...,n)和e条边的有向图(0≤e≤n(n-1))。在邻接矩阵中删除结点i(0≤i≤n-1)的时间复杂度是（）

单选

用邻接矩阵存储有 n 个结点 (0,1,...,n) 和 e 条边的有向图 (0≤e≤n(n-1))。判断结点 i，j（0≤i，j≤n-1）有边的时间复杂度是（）

单选

下列排序算法中，平均时间复杂度为O(n 2 )的是（）

单选