算法与数据结构习题3

《算法与数据结构习题3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题3一、单项选择题1.将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为（）。A．48B．49C．50D．512.在待排序的元素序列基本有序的前提下，效率最高的排序算法是（）。A、选择排序B、插入排序C、快速排序D、归并排序3.一个具有n个顶点的连通无向图的生成树中有（）条边。A、n-1B、nC、n/2D、n+1第6页共6页二、填空题1.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______个前驱结点；叶子结点没有_______结点。2.若按层次顺

2、序将一棵有n个结点的完全二叉树的所有结点编号为1到n，那么，当i为_______且不等于1时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟；当i<=（n-1）/2时，结点i的右子女是_______，否则结点i没有右子女。3.在单链表中，除了首元结点外，任一结点的存储位置由指示。4.将下列表达式的复杂度由小到大重新排序后的正确顺序为。A、2nB、n！C、n5D、10000E、n*log2n三、判断题1.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（）2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）3.链表的

3、物理存储结构具有同链表一样的顺序。（）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）四、简答题第6页共6页1.编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印的算法写出来。2.写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。3.给出栈的最常用的5种操作，并说明它们的功能。4.什么是内排序？什么样的排序算法是稳定的？快速排序稳定吗？为什么？5.什么是二叉树的高度？什么是完全二叉树？什么是满二叉树？习题答案第6页共6页一、单项选择题题号123答案CBA二、填空题题号答案11；

4、后续2奇数；2i+13其直接前驱结点的链域的值4D0){P

5、ush_seq(pastack,temp%2);Temp/=2;}While(!isEmptyStack_seq(pastack)){Printf(“%d”,top_seq(pastack));Pop_seq(pastack);}Free(pastack);}2.答：intlength(LinkListllist){/*计算单链表list的长度*/If(llist==NULL)return();return1+length(llist->link);}3.答：第6页共6页(1)voidpush（ST,x）将元素x插入栈ST的顶端(2)

6、voidpop（ST）从栈ST顶端删除一个元素(3)DataTypetop（ST）读栈ST顶端的元素(4)intisEmpty（ST）判断栈ST是否为空栈(5)pStackcreatEmptyStack()创建一个空栈4.答：（1）排序过程中，数据全放在内存中处理的排序方法称为“内排序”。（2）若经过排序后，文件中排序码相等的记录之间的相对次序保持不变，则此排序算法是稳定的，否则为不稳定。（3）快速排序是不稳定的，因为在每次分区交换时，可能已经破坏了其他排序码相同的记录的顺序。5.答：（1）规定根的层数为0，其余结点的层数等于其父结点

7、的层数加1.二叉树中结点的最大层数称为二叉树的高度。（2）如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。（3）如果一棵二叉树的任何结点或者是树叶，或有两棵非空子树，则此二叉树称为满二叉树。第6页共6页