二叉树的查找和折半查找的时间复杂度_二叉搜索树的查找和折半查找的时间复杂度

数据结构|FZU2008期末试卷·分类与解析 　　时间复杂度·递归 　　以下函数的时间复杂度为（ ）。 int Rsum ( int a[], int n ) { if ( n>0 ) return Rsum ( a, n-1 ) + a[n-1]; return 0; } A、O(1) B、O(n2) C、O(n) D、O(nlog2n) 　　答案：C 　　解析：每次递归调用n就-1，直到n小于0停止，操作n次，所以时间复杂度为O(n); 　　线性表·顺序存储 　　下列不属于顺序存储结构特点的是（ ）。A、可对素进行随机访问 B、非表尾的插入和删除操作需要移动表中大量素C、相邻素在内存中的物理位置也是相邻的D、采用该存储结构的线性表空间可动态扩充 　　答案：D 　　解释：顺序表可以随机存储，但是不能动态扩容； 　　顺序表·插入节点 　　若在含n个素的顺序表中执行删除操作，设删除每个素的概率相同，则该删除操作需移动素的平均次数为 　　答案：(n-1)/2 　　链表·插入节点(前插、后插） 　　设在带哨兵结点的单链表中，链结点的指针域为next，在指针p所指结点后插入由指针y所指的新结点，应使用的语句为（ ）。A、p->next=y->next; y->next=p;B、y->next=p->next; p->next=y;C、p->next=y->next; p->next=y;D、y->next=p->next; y->next=p; 　　答案：B 　　解析：后插时，先连接前面的，再让后面指针链接。 　　①y->next=p->next; ②p->next=y; 　　静态链表 　　下列关于静态链表的说法错误的是（ ）。A、多条静态链表可共用一个数组空间 B、在数组空间中，静态链表中的素可以随机存放C、静态链表可以无限扩充D、静态链表的指针域也称为游标，存放下一素在数组中的下标 　　答案：C 　　解释：静态链表，由数组构成；存储两个东西：数据＋游标； 　　栈·插入在栈顶进行/先进后出 　　下列关于栈的说法错误的是（ ）。A、栈的插入和删除操作均在栈底方向进行 B、若用数组实现栈，为避免栈发生溢出，通常需要预置一个较大栈空间C、若用数组实现栈，为提高存储空间利用率，可以让多栈共享数组空间D、链栈空间可以动态扩充 　　答案：A（略） 　　循环队列·顺序存储中的实现 　　若用循环数组实现队列，队首游标front指向队首素前一单，队尾游标rear指向队尾素所在单，设循环数组的单个数为MaxSize。若使用总剩一个单不利用的方法区分满空状态，则front和rear满足关系（ ）时队列为满。A、front==(rear+1)%MaxSizeB、rear==(front+1)%MaxSizeC、front==(rear+2)%MaxSizeD、front==rear 　　答案：A 　　解释：front==(rear+1)%MaxSize，最后一个指针和第一个指针差一个位置，所以最后一个指针＋1，除余最大长度，得到逻辑上的循环队列；若用循环数组实现队列，队首游标front指向队首素前一单，队尾游标rear指向队尾素所在单，设循环数组的单个数为MaxSize，循环数组名为queue。则将素x入队应执行的语句为 ； 。 　　答案： rear=(rear+1)%MaxSize; queue[rear]=x; 　　循环链表·指针实现 　　在带哨兵结点的双循环链表中，设链结点的后继指针域为next，前驱指针域为prior，指针header指向哨兵结点，则判断该链表是否为空的表达式为 。 　　答案：header->next==header 或 header->prior==header 　　树的存储结构·三种表示方法 　　下列关于树的表示法说法错误的是（ ）。A、父结点数组表示法可以快速找到某结点的父结点，但查询儿子结点和兄弟结点可能要遍历整个数组 B、儿子链表表示法适合于查找子结点，但不适合于查找父结点和兄弟结点C、左儿子右兄弟表示法方便查找父结点和兄弟结点，但不方便查找子结点D、若采用儿子表示法，并使用定长结点的多重链表结构，则表示一棵有n个结点度为d的树必存在nd-(n-1)个空链域 　　答案：C表示法方式寻找特点双亲/父节点表示法（向上）顺序存储（数组存上一个根节点）往上查容易孩子/儿子表示法（向下）顺序＋链式存储（数组存单链表）往下查容易孩子兄弟表示法（相互）链式存储（左指针—子，右指针——兄弟）都容易 　　※孩子表示法造成空链域 　　若采用儿子表示法，并使用定长结点的多重链表结构，则表示一棵有n个结点度为d的树必存在nd-(n-1)个空链域； 　　二叉树的存储结构·顺序与链式 　　若采用二叉链表作为二叉树的存储结构，在含有n个结点的二叉树对应的二叉链表中，空链域总数为 。 　　答案：n+1 　　顺序存储：
空缺空间 　　链式存储：n+1个空链域（n个结点，共2n个链域） 　　二叉树·5种形态 　　不考虑树结点所存放的素值，由3个结点可组成 种不同形态的二叉树。

　　完全二叉树 　　具有50个结点的完全二叉树，高度为 ，叶结点有 个。（设仅含一个结点的二叉树的高度为1） 　　答案：6；25； 　　完全二叉树的3条性质：高度：
度数:度=1度=0（叶子结点）度=2（分支结点）2k个结点1kk-12k-1个结点0kk-1结点编号i：
为分支结点，
为叶子结点； 　　二叉树遍历·遍历序列求二叉树 　　已知一棵二叉树的先序遍历序列为A B D G C E H I F，中序遍历序列为D G B A E I H C F，画出这棵二叉树并写出它的后序遍历序列。 　　先序遍历：A B D G C E H I F 　　中序遍历：D G B A E I H C F

　　二叉树遍历·线索二叉树 　　利用后序线索链表进行二叉树的后序遍历时，若当前遍历结点存在右子树，则（ ）。A、由当前结点的后继线索可找到后继结点B、若当前结点是父结点的左子结点且父结点有右子树，则后继结点为父结点C、若当前结点是根结点，则后继结点是其右子树中最左下结点D、若当前结点是父结点的右子结点，则后继结点为父结点 　　答案：D※ 　　解析：先序遍历（第一次访问）、中序遍历（第二次访问）、后序遍历（第三次访问的结点） 　　图的概念·连通分量＆生成树 　　下列说法正确的是（ ）。A、连通分量是无向图的极小连通子图 B、生成树是无向图的极大连通子图C、具有n个顶点，少于n-1条边的无向图可能是连通图D、具有n个顶点，多于n-1条边的无向图必存在环 　　答案：D连通分量：极大连通子图；生成树：包含所有结点的极小连通子图；（极大/极小：结点数）若含有n个顶点的无向图是一个环，则它有 棵生成树。 　　答案：n棵，因为任意删去一条边就是一个生成树，有n条边。 　　图的4种表示法 　　下列说法错误的是（ ）。A、有向图的邻接矩阵第i列非零素的个数是第i个顶点的入度B、邻接矩阵适用于表示稀疏图C、通过邻接矩阵可以方便快速地判定两个顶点间是否有边或弧相连D、有向图的逆邻接表第i条链表的长度是第i个顶点的入度 　　答案：B 　　四种表示方法图的表示方法适用范围求度空间复杂度邻接矩阵（唯一）适用于“稠密图”，空间冗余大求度容易（行=出度，列=入度）O(V2）邻接表（不唯一）存储无向图时，空间冗余大正邻接表：求出度易逆邻接表：求入度易O(V+E)十字链表（不唯一）只存有向图求度容易O(V+E)邻接多重表（不唯一)只存无向图——O(V+E) 　　图的遍历 　　进行图的广度优先搜索时，需要用到下列哪种数据结构（ ）。A、栈 B、队列 C、数组 D、串 　　答案：B图的遍历实现结构求序列/求生成树、森林广度优先遍历（BFS）辅助队列深度优先遍历（DFS）函数调用栈 　　※非连通图：调用BFS/DFS函数次数=连通分量（无向图）；如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。A、连通图 B、完全图 C、有回路 D、一棵树 　　答案:A写出以顶点4为源点遍历以下所示的无向连通图得到的深度优先序列和广度优先序列，并画出相应的深度优先生成树和广度优先生成树。（考虑顶点的邻接点时，序号小的邻接点优先考虑）

　　深度优先生成树为：

　　广度优先生成树为：



　　排序·算法评价 　　堆排序的时间复杂度为（ ）。A、O (n) B、O (n2) C、O (nlog2n) D、O (log2n) 　　答案:C排序方式操作时间复杂度空间复杂度稳定性插入排序遍历已排序序列（逐一对比），插入当前素最坏：O(n2)最好：O(n)遍历+移动素O(1）稳定折半插入排序折半查找位置，插入当前素；O(n2）折半查找+移动素，仍然是n2数量级O(1)稳定希尔排序先部分有序，逐渐减小各组间距d值，直到d=1排序完成无确切值≤O(n2)O(n)，存储局部子表造成不稳定冒泡排序从后往前/从前往后，两两对比，较小值向前冒泡（谁小谁往前）最坏：O(n2)最好：O(n)比较次数＋交换次数O(1)稳定快速排序枢轴/基准，分为两部分，左小右大，依次遍历调整位置最好：O(logn)最坏：O(n)相当于二叉树的递归层数最好：O(nlogn)最坏：O(n2)不稳定简单选择排序扫描待排序队列的最小值，放到队首O(n2）O(1)不稳定堆排序①建立堆：根＞左右；②下坠：堆顶素与最后一个素互换位置，逐层对比，再次调整为堆（下坠），重复O(nlogn）逐层对比次数=层数O(1)不稳定归类排序多路的有序子序列，逐步合并成有序序列。（每次合并，对比大小排序一次）O(nlogn)倒立的二叉树=层数O(n)稳定基数排序可由基数r拆为d组，数据很大的情况O(d×(n+r))d:趟数（个十百千n:素个数r:基数个数（0-9)O(r)存基数即可稳定对序列28 19 33 30 26 31使用冒泡排序法进行升序排序，进行第一趟冒泡排序后得到的序列为 　　答案：19 28 30 26 31 33；希尔排序是一种不稳定的排序方法。（填稳定或不稳定） 　　答案：不稳定对下列序列35 44 67 23 15 48 39 32 进行快速排序，每次划分以被划分区域内第一个素作为基准素，写出每次划分后得到的序列。 　　答案：{ 35, 44, 67, 23, 15, 48, 39, 32 } 　　→{ 32, 15, 23 } 35 { 67, 48, 39, 44 } 　　{ 32, 15, 23 } à { 23, 15 } 32 　　{ 67, 48, 39, 44 } à { 44, 48, 39 } 67 　　{ 44, 48, 39 } à { 39 } 44 { 48 } 　　{ 23, 15 }à { 15 } 23 　　树形查找·平衡二叉树(AVL) 　　平衡二叉树中结点的平衡因子不可能是（ ）。A、0 B、-1 C、1 D、2 　　答案：D在含有n个结点的平衡二叉树上执行插入操作的时间复杂度为插入删除查找ASL二叉排序树（BST）————递归：O(h)非递归：O(1)平衡二叉树（AVL）O(log2n)O(log2n)最好情况：O(log2n)最坏情况：O(n)红黑树（RBT）O(log2n)O(log2n)O(log2n) 　　树型查找·二叉排序树（BST） 　　下列有关二叉搜索树上的运算说法正确的是（ ）。A、从根结点起在二叉搜索树上查找某素，若当前结点存放的素比被查找素大，则在当前结点的右子树中继续查找 B、在二叉搜索树中删除一个素时，若被删素所在结点存在左右子树，可用其左子树中最右下结点中的素替代被删素，并将该最右下结点的左子树挂接为其父结点的右子树。调整结构后的二叉树仍为一棵二叉搜索树。 C、从根结点起在二叉搜索树中查找某素y的直接前驱素，若当前结点存放的素x小于y，则以x作为y直接前驱的候选者，并继续在当前结点的左子树中进行查找D、从根结点起在二叉搜索树中查找某素y的直接后继素，若当前结点存放的素x等于y，则在当前结点的左子树中继续查找 　　答案：B