二叉树查找元素的时间复杂度_二叉树查找一个元素的时间复杂度

数据结构习题及解析三 　　来源：我是码农，转载请保留出处和链接！ 　　本文链接：数据结构习题及解析三 　　一、选择题 　　1.二叉树中第5层上的结点个数最多为______ A. 8 B. 15 C. 16 D. 32

　　解析：本题考点是二叉树中各层结点个数的计算方法。二叉树中第i层上的结点个数最多为2i-1。因此，本题参考答案是C。 2.一个无向连通图的生成树是含有该连通图的全部顶点的_____。 A. 极小连通子图 B. 极小子图 C. 极大连通子图 D. 极大子图 　　解析：本题考点是极小连通子图的概念。一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。因此，本题参考答案是A。 3.堆的形状是一棵______。 A. 二叉排序树 B. 满二叉树 C. 完全二叉树 D. 平衡二叉树 　　解析：本题考点是堆与完全二叉树的关系。完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。堆是一种完全二叉树或者近似完全二叉树，所以效率极高。因此，本题参考答案是C。 4.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_____。 A. n B. n-1 C. n+1 D. 2*n 　　解析：本题考点是二叉树的性质。结点有n个，于是子树总数为2n，所以的边数为n-1，因此结点的空子树数量为2n-(n-1)= n+1因此，本题参考答案是C。 5.有向图的一个顶点的度为该顶点的___ ___。 A. 入度 B. 出度 C. 入度与出度之和 D. (入度＋出度)/2 　　解析：本题考点是有向图中顶点度的概念。有向图的某个顶点v，把以v为终点的边的数目，称为v的入度；以v为始点的边的数目，称为v的出度；v的度则定义为该顶点的入度和出度之和。因此，本题参考答案是C。 6.对线性表进行折半查找时，要求线性表必须___ ___。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且素按关键字有序排序 D. 以链接方式存储，且素按关键字有序排序 　　解析：本题考点是线性表折半查找的条件。折半查找的前提条件是线性表以顺序方式存储，且素按关键字有序排序，因此，本题参考答案是C。 7.在一个有向图中，所有顶点的度数之和等于所有弧数的______倍。 A. 3 B. 2 C. 1 D. 1/2 　　解析：本题考点是有向图顶点度数与弧数的关系。有向图的某个顶点v，把以v为终点的边的数目，称为v的入度；以v为始点的边的数目，称为v的出度；v的度则定义为该顶点的入度和出度之和。显然，在一个有向图中，所有顶点的度数之和等于所有弧数的2倍。因此，本题参考答案是B。 8.一棵树的广义表表示为a(b(c), d(e(g(h)), f))，则该二叉树中度为1的结点数为______。 A. 2 B. 3 C. 4 D. 5 　　解析：本题考点是广义表与二叉树的转换。二叉树中的度就是分支的数目。没有分叉的二叉树节点的度就是0度。如果一个节点只有一个分叉就是1度。两个分叉就是2度。该广义表转换为二叉树后，度为1的结点是b，e，g。因此，本题参考答案是B。 9.在一棵深度为h的完全二叉树中，所含结点个数不大于______。 A. 2h B. 2h+1 C. 2h -1 D. 2h-1 　　解析：本题考点是完全二叉树中结点的个数。在一棵深度为h的完全二叉树中，所含结点个数不大于2h -1。回答此题可以用实例来验证，例如当h=2时，完全二叉树最多有3个结点。因此，本题参考答案是C。 10.对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，为查找素26，若采用折半查找，需要比较______次才能查找成功。 A. 3 B. 4 C. 5 D. 6 　　解析：本题考点是折半查找的基本思想。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。因此，本题参考答案是B。 11.以下哪一个术语与数据的存储结构无关_____ A. 顺序表 B. 静态数组 C. 二叉树 D. 链表 　　解析：本题考点是数据结构的基本概念。二叉树是每个节点最多有两个子树的树结构，不是数据的存储结构。因此，本题参考答案是C。 12.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为______ A. 顺序表 B. 用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 　　解析：本题考点是循环链表的优点。插入和删除方便的存储结构是链表，这是因为链表插入和删除时不需要移动素就能实现。只在表的首、尾进行插入操作的线性表用尾指针表示的单循环链表最适宜，减少了移动指针的次数。因此，本题参考答案是C。 13.100个素的排序数组分别进行二分查找和顺序查找，在查找失败的情况下，______的比较次数较多。 A. 二分查找 B. 顺序查找 C. 一样多 D. 不一定 　　解析：本题考点是二分查找的性能。100个素的排序数组分别进行二分查找和顺序查找，在查找失败的情况下，顺序查找最多比较100次，二分查找最多比较7次。因此，本题参考答案是B。 14.有6个素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列____ A. 5,4,3,6,1,2 B. 4,5,3,1,2,6 C. 3,4,6,5,2,1 D. 2,3,4,1,5,6 　　解析：本题考点是栈的应用。栈是一种后进先出的数据结构，5在6之后进栈，肯定要在6之前出栈。因此，本题参考答案是C。 15.会引起循环队列队头位置发生变化的操作是____。 A. 出队列 B. 入队列 C. 取队首素 D. 取队尾素 　　解析：本题考点是循环队列的基本操作。循环队列的出队列操作是在队头进行的，会使队头位置发生变化。因此，本题参考答案是A。 16. 链表的结点类型定义如下: typedef struct node *link; struct node { ListItem element; link left; link right; }*p,*q,*r;删除双链表中结点p(由p指向的结点)的操作是______ A. q=p->left;r=p->right;q->right=r;r->left=q; B. q=p->right;r=p->left;q->right=r;r->left=q; C. q=p->left;r=p->right;q->left=r;r->right=q; D. q=p->left;r=p->right;q->right=r->left; 　　解析：本题考点是链表的操作。根据链表结点类型的定义可以看出，该链表是一个双向链表。删除双链表中结点p(由p指向的结点)的操作是： q=p->left; r=p->right; q->right=r; r->left=q; 因此，本题参考答案是A。 17.在下列排序算法中，时间复杂度为O(nlogn)的是____ A. 冒泡排序 B. 简单选择排序 C. 直接插入排序 D. 堆排序 　　解析：本题考点是堆排序的时间复杂度。在上述算法中，堆排序的时间复杂度是O(nlogn)，其他算法的时间复杂度都是O(n2)。因此，本题参考答案是D。 18.在一棵三树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为____个。 A. 4 B. 5 C. 6 D. 7 　　解析：本题考点是三树中结点数的计算。树中结点数等于所有结点度数的和加1。所以：2+1+2+X=2*3+1*2+2*1+X*0+1，所以X=6。因此，本题参考答案是C。 19.具有10个叶结点的二叉树中有____个度为2的结点. A. 8 B. 9 C. 10 D. 11 　　解析：本题考点是二叉树的性质。叶子结点个数=度为2的结点个数+1。因此，本题参考答案是B。 20.在一个图中，所有顶点的度数之和等于所有边的____倍。 A. 1/2 B. 1 C. 2 D. 4 　　解析：本题考点是图的基本性质。在一个图中，所有顶点的度数之和等于所有边的2倍，这是因为一条边一定是连接两个顶点。因此，本题参考答案是C。 21.下列数据结构具有记忆功能的是____ A. 队列 B. 循环队列 C. 栈 D. 顺序表 　　解析：本题考点是具有记忆功能的数据结构。由栈的定义可知，栈是一种后进先出的线性表，所以栈具有记忆功能。因此，本题参考答案是C。 22.下列数据结构中，按先进后出原则组织数据的是____ A. 线性链表 B. 栈 C. 循环链表 D. 顺序表 　　解析：本题考点是栈的定义。栈是一种后进先出（先进后出）的线性表。因此，本题参考答案是B。 23.下列关于栈的叙述中正确的是____ A. 在栈中只能插入数据 B. 在栈中只能删除数 C. 栈是先进先出的线性表 D. 栈是先进后出的线性表 　　解析：本题考点是栈的定义。栈是一种后进先出（先进后出）的线性表，可以进行插入和删除数据。因此，本题参考答案是D。 24.下列关于队列的叙述中正确的是____ A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 　　解析：本题考点是队列的定义。队列是一种先进先出的线性表，可以进行插入和删除数据。因此，本题参考答案是C。 25.下列叙述中，正确的是____ A. 线性链表中的各素在存储空间中的位置必须是连续的 B. 线性链表中的表头素一定存储在其他素的前面 C. 线性链表中的各素在存储空间中的位置不一定是连续的，但表头素一定存储在其他素的前面 D. 线性链表中的各素在存储空间中的位置不一定是连续的，且各素的存储顺序也是任意的 　　解析：本题考点是线性链表的特点。线性链表中的各素在存储空间中的位置不一定是连续的，且各素的存储顺序也是任意的。因此，本题参考答案是D。 26.下列叙述中正确的是____ A. 线性表是线性结构 B. 栈与队列是非线性结构 C. 线性链表是非线性结构 D. 二叉树是线性结构 　　解析：本题考点是线性表的性质。线性表是一种线性结构。栈、队列和线性链表都是线性结构。二叉树是一种非线性结构。因此，本题参考答案是A。 27.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是____ A. 每个素都有一个直接前件和直接后件 B. 线性表中至少要有一个素 C. 表中诸素的排列顺序必须是由小到大或由大到小 D. 除第一个素和最后一个素外，其余每个素都有一个且只有一个直接前件和直接后件 　　解析：本题考点是线性表的性质。线性表的特点是：除第一个素和最后一个素外，其余每个素都有一个且只有一个直接前件和直接后件。因此，本题参考答案是D。 28.链表不具有的特点是____ A. 不必事先估计存储空间 B. 可随机访问任一素 C. 插入删除不需要移动素 D. 所需空间与线性表长度成正比 　　解析：本题考点是链表的特点。可随机访问任一素是顺序表（例如数组）的特点，不是链表的特点。因此，本题参考答案是B。 29.在____中，只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。 A. 线性单链表 B. 双向链表 C. 线性链表 D. 循环链表 　　解析：本题考点是循环链表的特点。循环链表最大的特点是只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。因此，本题参考答案是D。 30.以下数据结构属于非线性数据结构的是____ A. 队列 B. 线性表 C. 二叉树 D. 栈 　　解析：本题考点是非线性数据结构的特点。二叉树属于非线性结构，其他选项都属于线性结构。因此，本题参考答案是C。 31.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置素的时间复杂性为____ A. O（i） B. O（1） C. O（n） D. O（i-1） 　　解析：本题考点是单链表的基本操作。线性表（a1,a2,…,an）以链接方式存储时，该线性表就是一个单链表。单链表访问第i位置素的时间复杂性为O（n），因为需要从首素开始逐个向后访问。因此，本题参考答案是C。 32.在双向链表指针p的结点前插入一个指针q的结点操作是____。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; 　　解析：本题考点是双向链表的插入操作。在双向链表指针p的结点前插入一个指针q的结点操作是： q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q; 因此，本题参考答案是C。 33.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：____。 A. p->next=s;s->next=p->next; B. s->next=p->next;p->next=s; C. p->next=s;p->next=s->next; D. p->next=s->next;p->next=s; 　　解析：本题考点是单链表的基本操作。在单链表指针为p的结点之后插入指针为s的结点的操作是： s->next=p->next; p->next=s; 因此，本题参考答案是B。 34.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是____ A. head==NULL B. head→next==NULL C. head→next==head D. head!=NULL 　　解析：本题考点是单链表的基本操作。由于单链表带有头结点，因此从头结点的下一个结点开始存储素，所以判定该表为空表的条件是看头结点的下一个结点是否为空。因此，本题参考答案是B。 35.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为____。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 　　解析：本题考点是线性表操作的性能分析。对于顺序存储的线性表，例如数组，访问结点时是随机访问方式，直接利用下标就可以定位要访问哪个素，时间复杂度为O(1)。增加、删除结点时需要移动大量其他素，时间复杂度为O(n)。因此，本题参考答案是C。 36.执行完下列语句段后，i值为：____ int f(int x) { return ((x>0) ? x* f(x-1):2); } int i; i =f(f(1)); A. 2 B. 4 C. 8 D. 无限递归 　　解析：本题考点是递归的使用。首先计算f(1)的值，当x=1时，函数返回值是x* f(x-1)；即1*f(0)，而f(0)=2，因此，f(1)的值为2。再计算f(f(1))=f(2)，当x=2时，函数返回值是2*f(1)=2*2=4。因此，本题参考答案是B。 37.设计一个判别表达式中左，右括号是否配对出现的算法，采用____数据结构最佳。 A. 线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 　　解析：本题考点是栈的应用。栈的一个重要应用就是判别表达式中括号是否匹配，基本思想是遇到左括号进栈，遇到右括号时不进栈，并弹出栈顶的左括号，如果最终无素进栈，并且栈中也无左括号，则匹配成功。因此，本题参考答案是D。 38.用链接方式存储的队列，在进行删除运算时____。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 　　解析：本题考点是队列的基本操作。链接方式存储的队列，一般都是在队头进行删除运算，头指针需要修改，但当删除队列中最后一个素时，头、尾指针都需要修改。因此，本题参考答案是D。 39.关二叉树下列说法正确的是____ A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 　　解析：本题考点是二叉树的基本性质。当一个二叉树为空树时，此时，它的度小于2。因此，本题参考答案是B。 40.对于有n 个结点的二叉树, 其高度为____ A. nlog2n B. log2n C. log2n+1 D. 不确定 　　解析：本题考点是二叉树高度的计算方法。对于有n个结点的二叉树，其高度是不确定的，与结点的排列方式有关，最大为n（每个节点就只有一棵子树的时候），最小是完全二叉树的时候，当然也有其他情况可以满足，最小为log2n，其他情况的都是在这两种之间，不大于最大不小于最小。因此，本题参考答案是D。 二、填空题 　　1、二叉树的遍历方式有_______、_________和________ 　　解析：本题考点是二叉树遍历方式的种类。二叉树的遍历有三种方式，如下：1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 2、图的遍历方式有_______和________ 　　解析：本题考点是图的遍历。从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS（Depth First Search）和广度优先搜索BFS（Broad First Search）。这两种方法都适用于有向图和无向图。 3、_______可以作为算法所需存储空间的度量。 　　解析：本题考点是算法运行所需存储空间的度量。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做(n)=O(f(n))。 4、某二叉树的前序和后序正好相反，则该二叉树一定是__________二叉树。 　　解析：本题考点是二叉树的特性。由于二叉树的前序序列是先访问根结点再访问左右子树得到的，二叉树的后序序列是先访问左右子树最后访问根结点得到的，因此，高度等于其结点数的二叉树的前序和后序正好相反。 5、栈的存储方式有_______和_________两种。 　　解析：本题考点是栈的存储方式。栈既然是一种线性表，所以线性表的顺序存储和链式存储结构同样适用于栈。 6、开放定址法中，增量序列的取法有_______、___________和_________三种。 　　解析：本题考点是开放定址法中增量序列的取法。开放定址法就是从发生冲突的那个单开始，按照一定的次序，从散列表中查找出一个空闲的存储单，把发生冲突的待插入素存入到该单中的一类处理冲突的方法。增量序列的取法主要有线性探测再散列，二次探测再散列，伪随机数序列三种。 三、解答题 　　1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？ 　　解析：本题考点是单链表的基本操作。队列的特点是：先进先出；单链的特点是：迭代的时候只能向前，不能回头；在只知道头指针的情况下： 入队：首先要遍历单链，找到尾指针，时间复杂度O(n); 出队：直接访问头指针即可，时间复杂度O(1); 只知道尾指针的情况下，出入队时间均为O(1)，因为是循环链表，尾指针所指的下一个素就是头指针所指素，所以出队时不需要遍历整个队列。 2、无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。 　　解析：本题考点是无向图的遍历方法。回答此题前，应首先根据9条边画出该无向图，然后根据无向图深度优先和广度优先搜索法的定义进行遍历，得到结点序列。 深度优先搜索法:0–>2–>3–>4–>5–>1 广度优先搜索法:0–>1–>2–>4–>5–>3 3、简单描述栈的特点。 　　解析：本题考点是栈的基本特性。后进先出是栈的最主要特点。 四、算法题 　　1、设栈S=(1,2,3,4,5,6,7) ，其中7为栈顶素。 1）简述函数f31中第一个循环语句的功能； 2）写出调用f31(&s)后的s。

　　解析：本题考点是栈的基本操作。!就是逻辑非，当i=0，!i就是1，当i!=0，!i就是0了，i=!i就是给i赋值了(i=!i)!=0)的意思就很明显了，当i=0，i=!i代表的就是1，当i!=0，那么表达式if((i=!i)!=0)为真成立的条件就是i=0。函数f31中第一个循环语句的功能是将栈S中的素依次出栈，同时将第奇数次出栈的素入栈T，第偶数次出栈的素入队列Q。调用f31(&s)后，s = (1,3,5,7,6,4,2),其中2为栈顶素；