计算机专业基础数据结构

1、2.下面是一个求最小生成树的算法,其中 G是连通无向图,T 是所求的生成树. T:G: While T 中存在回路 do begin在 T中找一条权值最大的边 e; T:T 一e; T 中去掉 e边 EnD 试问该算法是哪一种求最小生成树的。

2、l 和 s 的降序链表,若将它们合并为一个长度为 ls 的升序链表,则最坏情况下的时间复杂度是 .AOlB OlsC Ominl,sDOmaxl,s3 线性表中存放的主要是 .A整型常量B字符C数据元素D信息元素4 下面的叙述中正确的是 。

3、删除和查找2.在线性表中的每一个表元素都是数据对象,它们是不可再分的.分数:2.00A.数据项B.数据记录C.数据元素D.数据字段3.对于顺序存储的线性表,其算法的时间复杂度为 O1的运算应是.分数:2.00A.将 n 个元素从小到大排序B。

4、则此二叉树中所包含的结点个数至少有;已知二叉树有 50个叶结点,有 30个度为 1的结点,则该二叉树的总结点数为.分数:5.00A.2d1B.2d1C.2d1D.2d1A.129B.130C.131D.1321.设森林中有三棵树,第一第二和。

5、一算术表达式的中缀形式为 ABCDE,后缀形式为 ABCDE一,其前缀形式为 .A一 ABCDEB一 ABCDEC ABCDEDABC DE3 算术表达式 abcd e转为后缀表达式后为 .AabcdeB abcdeC abcdeDabcd。

6、堆排序快速排序归并排序的关系是 .A堆排序快速排序归并排序B堆排序归并排序快速排序C堆排序归并排序快速排序D堆排序快速排序归并排序3 一组记录的关键码为25,48,16,35,79,82,23,40,36,72,其中,含有5 个长度为 2。

7、2.从顺序表中删除第 i个元素并由函数返回被删元素的值.如果 i不合理或顺序表为空则显示出错信息并退出运行.分数:4.003.向顺序表中第 i个位置插入一个新的元素 x.如果 i不合理则显示出错信息并退出运行.分数:4.004.从顺序表中删。

8、2.编号为 i 的结点的父结点若存在的编号是多少分数:4.003.编号为 i 的结点的第 k 个子女结点若存在的编号是多少分数:4.004.编号为 i 的结点有右兄弟的条件是什么其右兄弟结点的编号是多少分数:4.005.若结点个数为 n。

9、2.采用简单选择排序,比较次数与移动次数分别为 .分数:2.00A.On,Olog 2 nB.Olog 2 n,On 2 C.On 2 ,OnD.Onlog 2 n,On3.就排序算法所用的辅助空间而言,堆排序快速排序归并排序的关系是 .分。

10、存储或链式存储的线性表,平均比较次数为 1 ,二分法查找只适用于查找顺序存储的有序表,平均比较次数为 2 .在此假定N 为线性表中结点数,且每次查找都是成功的.2 1AN1B 2log2NC log2NDN23 2AN1B 2log2NC 。

11、问该算法是哪一种求最小生成树的算法 APrim普里姆算法B Kruskal克鲁斯卡尔算法C罗巴赫算法D其他算法2 邻接表是图的一种 .A顺序存储结构B链接存储结构C索引存储结构D散列存储结构3 下面试图对图中路径进行定义,说法正确的是 .A。

12、简单无向图,在其邻接矩阵中共有个零元素,该邻接矩阵是一个.而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的.分数:8.00A.权值B.顶点C边D.边与顶点均AeB.2eC.n2eD.n22eA.上三角矩阵B.稀疏矩阵C.对角矩阵D。

13、2.下面给出的 4 种排序方法中, 排序法是不稳定性排序法.分数:2.00A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中,其比较次数或交换次数与序列初态无关的算法是 .分数:2.00A.快速排序B.直接插入排序C.二路归并排序D。

14、2.若查找每个记录的概率均等,则在具有 n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度 ASL为 .分数:2.00A.n12B.n2C.n12D.n顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为 1 ,二。

15、2.栈和队列的主要区别在于 .分数:2.00A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样3.若循环队列以数组 Q0m1作为其存储结构,变量 rear.表示循环队列中的队尾元素的实际位置。

16、2.下面给出的 4种排序方法中, 排序法是不稳定性排序法.分数:2.00A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中,其比较次数或交换次数与序列初态无关的算法是 .分数:2.00A.快速排序B.直接插入排序C.二路归并排序D.冒。

17、2.设树 T的度为 4,其中度为 123 和 4的结点个数分别为 41,1,1,则 T中的叶子数为 .分数:2.00A.10B.11C.9D.73.用下列元素序列22,8,62,35,48构造平衡二又树,当插入 时,会出现不平衡的现象.分数。

18、2.在下面关于树的相关概念的叙述中,正确的是 .分数:2.00A.只有一个结点的二叉树的度为 1B.二叉树的度一定为 2C.二叉树的左右子树可任意交换D.深度为 K的完全二叉树的结点个数小于或等于深度相同的满二叉树3.已知一算术表达式的中缀。

19、2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则下面最节省运算时间的存储方式是 .分数:2.00A.单链表B.带有头指针的单循环链表C.双链表D.带有尾指针的单循环链表3.已知两个长度分别为 l和 s的降序链。

20、2.下面是一个求最小生成树的算法,其中 G是连通无向图,T 是所求的生成树. T;G; While T 中存在回路 do begin在 T中找一条权值最大的边 e; T:T 一e; T 中去掉 e边 End 试问该算法是哪一种求最小生成树的。