文档介绍：习题3
一、单项选择题
L将一棵有1皿个结点的完全二叉树从根开始，每层从左到右依次 对结点进行编号，根结点编号为1,则编号最大的非叶子结点的编号 为（）。
A 48
B 49
C 50
D 51
2在待排序的元素序列基本有序的前提下，效率最高的排序算法是 （）。
A选择排序
B插入排序
G快速排序
D归并排序
a 一个具有n个顶点的连通无向图的生成树中有（）条边。
A n—1
B n
G n/2
D n-Fl
二、填空题
L在树形结构中，树根结点没有前驱结点，其余每个结点有且只有
前驱结点；叶子结点没有 ^点。
2若按层次顺序将一棵有n个结点的完全二叉树的所有结点编号为
1到n那么，当i为 不等于1时，结点i的左兄弟是结点
i—1,否则结点i没有左兄弟；当iW（n-l） /2时，结点i的右子女
是 L否则结点i没有右子女。
a在单链表中，除了首元结点外，任一结点的存储位置由 指
/Ji O
4将下列表达式的复杂度由小到大重新排序后的正确顺序
为 O
A 21 Bn!
G n D 10000
E nMog?n
三、判断题
L二叉树中所有结点个数是 旷一1,其中k是树的深度。（）
2顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）
3链表的物理存储结构具有同链表一样的顺序。（）
4对于不同的使用者，一个表结构既可以是栈，也可以是队列，也
可以是线性表。（）
四、简答题
L编写一个算法，对于输入的十进制非负整数，将它的二进制表示 打印的算法写出来。
2写一个递归算法来计算并返回链表的长度，并在程序中做出相应 的文字说明。
a给出栈的最常用的5种操作，并说明它们的功能。
4什么是内排序？什么样的排序算法是稳定的？快速排序稳定吗？ 为什么？
5什么是二叉树的高度？什么是完全二叉树？什么是满二叉树？
习题答案
一、单项选择题
题号
1
2
3
答案
c
B
A
二、填空题
题号
答案
1
1;后续
2
奇数；2i+l
3
其直接前驱结点的链
域的值
4
三、判断题
题号
1
2
3
4
答案
X
X
X
V
四、简答题
L Void print bin (int dec_jiunber) {
/川各十进制非负整数转化为二进制数打印出来灯
PSeqStack pastack
Int tarp =dec nunbei；
If (tQTpO) {
Printf (“ Error! W )；
Return
}
PastacA creatHiptyStack 0_ eq 0； /健立一个空栈*/
If (pastack = = NJLQ return
While (torp>0) {
Push_seq (pastack ters^)；
Tarp/^
}
Whiled i sBTptyStacl^_seq (pastack)) {
Prin, top_seq (pastack))；
Pop seq (pastack)；
}
Free (pastack)；
}
2 答：int length (L