习题3一、单项选择题。
1. 将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为（ ）
a．48b．49
c．50d．51
2.在待排序的元素序列基本有序的前提下，效率最高的排序算法是（ ）
a、选择排序。
b、插入排序。
c、快速排序。
d、归并排序。
3. 一个具有n个顶点的连通无向图的生成树中有（ ）条边。
a、n-1b、n
c、n/2d、n+1
二、填空题。
1. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有___个前驱结点；叶子结点没有___结点。
2. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点编号为1到n，那么，当i为___且不等于1时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟；当i<=（n-1）/2时，结点i的右子女是___否则结点i没有右子女。
3. 在单链表中，除了首元结点外，任一结点的存储位置由指示。
4. 将下列表达式的复杂度由小到大重新排序后的正确顺序为。
a、2nb、n
c、n5d、10000
e、n*log2n
三、判断题。
1.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（
2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（
3. 链表的物理存储结构具有同链表一样的顺序。（
4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（
四、简答题。
1. 编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印的算法写出来。
2.写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。
3.给出栈的最常用的5种操作，并说明它们的功能。
4. 什么是内排序？什么样的排序算法是稳定的？快速排序稳定吗？为什么？
5. 什么是二叉树的高度？什么是完全二叉树？什么是满二叉树？
习题答案 一、单项选择题。
二、填空题。
三、判断题。
四、简答题。
1. void print_bin(int dec_number){
*将十进制非负整数转化为二进制数打印出来*/
pseqstack pastack;
int temp =dec_number;
if (temp<0){
printf(“error!”);
return;
pastack= createmptystack()_seq();建立一个空栈*/
if(pastack = null)return;
while(temp>0){
push_seq(pastack,temp%2);
temp/=2;
while(!isemptystack_seq(pastack)){
printf(“%d”,top_seq(pastack));
pop_seq(pastack);
free(pastack);
2. 答： int length(linklist llist){ 计算单链表list的长度*/
if(llist = null)
return();
return1+length(llist->link);
3. 答：1) void push（st,x） 将元素x插入栈st的顶端。
2) void pop（st） 从栈st顶端删除一个元素。
3) datatype top（st） 读栈st顶端的元素。
4) int isempty（st） 判断栈st是否为空栈。
5) pstack createmptystack() 创建一个空栈。
4. 答：1）排序过程中，数据全放在内存中处理的排序方法称为“内排序”。
2）若经过排序后，文件中排序码相等的记录之间的相对次序保持不变，则此排序算法是稳定的，否则为不稳定。
3）快速排序是不稳定的，因为在每次分区交换时，可能已经破坏了其他排序码相同的记录的顺序。
5. 答：1）规定根的层数为0，其余结点的层数等于其父结点的层数加1.二叉树中结点的最大层数称为二叉树的高度。
2）如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
3）如果一棵二叉树的任何结点或者是树叶，或有两棵非空子树，则此二叉树称为满二叉树。
算法与数据结构习题
一 单项选择题。1 算法的时间复杂度的表示方法是 a 实现算法的程序在指定机器上执行的时间。b 标准程序在机器上的执行时间。c 基本操作重复次数，即问题规模n的某个函数。d 与刻画基本操作重复次数的函数同阶无穷大的函数f n 2 在一个双向链表中，假设结点的域分别为left,right,以及data...
算法与数据结构习题
6 页共 8 页。一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是 a 6 页共 8 页。算法与数据结构 习题2 一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数...
算法与数据结构习题
一 单项选择题。1.在数组a8 10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是 a 240b 100 c 80d 270 2.如果把由树转换得到的二叉树叫做这棵树所对应的二叉树，则下面结论正确的是 a 等同于该...