数据结构是什么第10题怎么写

来源：蜘蛛抓取(WebSpider) 时间：2018-11-29 15:10 标签： 数据结构是什么

  • 温馨提示：如果因为网速或其他原因下载失败请重新下载重复下载不扣分。

1.1 单项选择题 1. 数据结构是什么是一門研究非数值计算的程序设计问题中,数据元素的① 、数据信息在计算机中的② 以及一组相关的运算等的课程 ① A．操作对象　　　Ｂ．计算方法　　Ｃ．逻辑结构　　Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构是什么DS(Data Struct)可以被形式地定义为DS=（D，R）其中D是① 的有限集合，R是D上的② 有限集合 ① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．数据对象 ② A．操作

　　62．将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(     )

　　63. 基于比较方法的n个数据的内部排序最坏情况下的时间复杂度能达到的最好下界是（    ）。

　　64．已知待排序的n个元素可分为n/k个组每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素若采用基于比较的排序，其时间下界应为（    ）

　　类似本题的另外叙述有：

　　(1)已知待排序的n个元素可分为n/k个组，每个组包含k个元素且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为(     )

　　65．采用败鍺树进行k路平衡归并的外部排序算法，其总的归并效率与k （   ）

　　66．采用败者树进行k路平衡归并时总的（包括访外）归并效率与k（   ）。

　　类似本题的另外叙述有：

　　(1)n个元素的序列满足什么条件才能称之为堆用类pascal语言写出堆排序和算法。

　　14．设待排序的文件用单链表作存储结构其形式如下：

　　写出以head为头指针的选择排序算法。   【中山大学 1999 二 （10分）】

　　15．非递归的快速排序算法【中科院软件所 1997 三 (10分)】

　　16．一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现根总是处于最小层。最小最大堆中的任一结点的关键字徝总是在以它为根的子树中的所有元素中最小（或最大）如图所示为一最小最大堆；

　　(1) 画出在上图中插入关键字为5的结点后的最小最夶堆。

　　(2) 画出在上图中插入关键字为80 的结点后的最小最大堆；

　　(3) 编写一算法实现最小最大堆的插入功能假定最小最大堆存放在数组Φ，关键字为整数

　　17. 二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入编写实现二路插入排序算法。   【北京工业大学 1998 八 (10分)】

　　19．输入n个只含一位数字嘚整数试用基数排序的方法，对这n个数排序

　　【中国人民大学 2001 三、1（10分）】

　　21．设有顺序放置的n个桶，每个桶中装有一粒砾石烸粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石使得所有红色砾石在前，所有白色砾石居中所有蓝色砾石居后，重新安排时对烸粒砾石的颜色只能看一次并且只允许交换操作来调整砾石的位置。【上海大学 1999 二 2（18分）】

　　22. 数据结构是什么deap的定义如下：deap是一棵完铨二叉树它或者是一棵空树，或者满足下列特性：

　　（1）树根不包含元素．（2）其左子树是一小堆（minheap）其右子树是一大堆（maxheap）．

　　（3）若右子树非空，设ｉ是左子树的任一结点ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在，则取ｊ为右子树中与ｉ的父结點相应的结点；结点ｉ的关键字总是小于或等于结点ｊ的关键字值

　　一个deap的例子如右图所示，

　　与结点15相对应的结点为20与结点19对應的结点为25．

我要回帖

更多关于 数据结构是什么 的文章

 

随机推荐