文档介绍：《算法与数据结构》习题1
第一部分
一、单项选择题
( )二叉排序树可以得到一个从小到大的有序序列。
A、先序遍历 B、中序遍历
C、后序遍历 D、层次遍历
设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为( )。
A、2i+1 B、2i
C、i/2 D、2i-1
设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为( )。
A、q=p->next;p->data=q->data;p->next=q->next;free(q);
B、q=p->next;q->data=p->data;p->next=q->next;free(q);
C、q=p->next;p->next=q->next;free(q);
D、q=p->next;p->data=q->data;free(q);
设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( )。
A、BADC B、BCDA
C、CDAB D、CBDA
设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有( )条有向边。
A、n B、n-1
C、m D、m-1
设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为( )。
A、O(1) B、O(log2n)
C、O(nlog2n) D、O(n2)
设有序表中有1000个元素,则用二分查找查找元素X最多需要比较( )次。
A、25 B、10
C、7 D、1
二、填空题
设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为______=p;s->right=p->right;______=s;p->right->left=s;(设结点中的两个指针域分别为left和right)。
一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为______。
设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该二叉树中度数为3的结点数有______个。
后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式(3+4X)-2Y/3对应的后缀算式为______。
设初始记录关键字序列为(K1,K2,„,Kn),则用筛选法思想建堆必须从第______个元素开始进行筛选。
对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有______个和______个。
______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。
完全二叉树中第5层上最少有______个结点,最多有______个结点。
三、计算题
设散列表的地址范围是[0..9],散列函数为H(key)=(key2+2) MOD 9,并采用链表处理冲突,请画出元素2、4、5、3、6、7、8、9依次插入散列表的存储结构。
请下图所示的森林:
求树(a)的先根序列和后根序列;
求森林先序序列和中序序列;
将此森林转换为相应的二叉树;
已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,画出此二叉树,并画出它的后序线索二叉树