(算法与数据结构习题.docVIP

《算法与数据结构》习题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，画出此二叉树，并画出它的后序线索二叉树。 四、算法填空 下列算法实现在顺序散列表中查找值为k的关键字，请在下划线处填上正确的语句: struct record { int key; int others; }; int hashsqsearch(struct record hashtable[ ],int k) { int i,j; j=i=k % p; while(hashtable[j].key!=khashtable[j].flag!=0) { j=(______)%m; if(i==j) return(-1); } if(______) return(j); else return(-1); } 五、编写算法 设计计算二叉树中所有结点值之和的算法。 设计将所有奇数移到所有偶数之前的算法。 第一部分参考答案 一、单项选择题 题号 1 2 3 4 5 6 7 答案 B B A A C B B 二、填空题 s-left=p，p-right O(n) 14 -1 34X*+2Y*3/- n/2 e 2e 中序 1 16 三、计算题 H(4)=H