文档介绍：数据结构部分
(1)算法的复杂度主要包括时间复杂度和_____复杂度。
答案:空间
知识点:算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)
评析:一个程序在计算机上运行时所耗费的时间由下列因素所决定:程序运行时所需输入的数据总量。对源程序进行编译所需时间,计算机执行每条指令所需时间,程序中的指令重复执行的次数。前一条取决于实现算法的计算机软、硬件系统,。算法在运行过程中需要的辅助存储空间的大小称为算法的空间复杂度。
(2)在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、_______遍历和后序遍历。
答案:中序
知识点:二叉树的前序、中序和后序遍历
评析:在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、中序遍历和后序遍历。
前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,首先访问根结点,然后遍历左子树,最后遍历右子树;并且遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中,首先遍历左子树,然后访问根结点,最后遍历右子树;并且遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。
后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中,首先遍历右子树,然后访问根结点,最后遍历左子树:并且遍历左、右子树时,仍然先遍历右子树,然后访问根结点,最后遍历左子树。
(3)设一棵完全二叉树共有500个结点,则在该二叉树中有____个叶子结点。
答案: 250
知识点:二叉树的概念
评析:所谓完全二叉树是指除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
具有n个结点的完全二叉树,其父结点数为(int)(n/2),而叶子结点数等于总结点数减去父结点数。本题n=500,故父结点数等于(int)(500/2)=250,叶子结点数等于500-250=250。
(4)栈的基本运算有三种:入栈、退栈和____。
答案:读栈顶元素
知识点:对栈的操作。
评析:栈的基本运算有三种:入栈、退栈和读栈顶元素。
入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作:首先将栈顶指针进一(即top加1),然后将新元素插入到栈顶指针指向的位置。
退栈运算是指取出栈项元素并赋给一个指定的变量。这个运算有两个基本操作:首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针退一(即top减1)。
读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是将它的值赋给一个变量。
(5)在最坏情况下,冒泡排序的时间复杂度为_____。
答案:n(n-1)/2 或(n(n-1)/2)
知识点:算法的概念
评析:冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据元素的交换