数据结构考研题北京邮电大学2017.pdfVIP

2017年北京邮电大学数据结构考研题 一、选择 1、 在数据结构中，与计算机无关的数据称为___________ ；单链表是一种______存储结构 的线性表，适合于______查找。 2、 二叉树最常用的__________是二叉链表。 3、 一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是_________ 。 4 、 设树的度为5，其中度为1~5 的结点数分别为6、5、4 、3、2 个，则该树共有_______ 个叶子。 5、 11 个顶点的无向图，最多能有_______条边。 6、 某索引顺序表共有元素275 个，平均分成5 块。若先对索引表采用顺序查找，再对块 中元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是________ 。 7、 交换排序适用于________存储结构的表。 8、 由A~F 六个字母构成的堆序列是______ (1) 9 (2) 28 (3) 31 (4) 36 (5) 50 (6) 51 (7) 55 (8) 110 (9) 138 (10) 逻辑结构 (11) 存储结构 (12) 顺序 (13) 链式 (14) DBCAEF (15) ABCDEF (16) ABCEDF (17) BACDEF 二、判断 1、 抽象数据类型与计算机内部表示和实现无关； 2、 线性表的插入和删除总是伴随着大量数据的移动； 3、 队列在程序调用是必不可少，因此递归离不开队列； 4 、 字符串’aababaaaba’的改进函数nextval 数组值是0020200320 ； 5、 二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点； 6、 不用递归就不能实现二叉树的前序遍历； 7、 若有向图有n 个顶点，则其强连通分量最多有n 个； 8、 平衡二叉树一定是一棵完全二叉树； 9、 若某内部排序算法不稳定，则该算法没有使用价值； 10、 倒排文件的目的是为了多关键字查找； 三、已知一组关键字为(112，213，305，46 ，57，86，72，162，95)，用散列表函数H(k)=k%10 将它们散列到表HT(0..9)中，用线性探测法H(k)，H(k)+1，……，H(k)-1 解决冲突，画出最后 的散列表，并计算产生冲突的次数。 四、简述Prim 和Kruskal 算法求最小生成树的算法思想，分析他们的时间复杂度及分别适用 于什么样的网 五、算法 1、 阅读下面的程序，根据输入写出输出结果 #include “iostream.h” viod swap(int x, int y) { int z=x; x=y; y=z; } void change(int a[100], int I, int j) { if(ij) { if(a[i]%2) {swap(a[i],a[j]); j--;} else i++; if(a[j]%2)) j--; else {swap(a[i],a[j]); i++;} change(a,i,j); } } void main() { int a[100],n; cinn; for(int i=0;in;i++) cinm[i]; change(m,0,n-1); for(i=0;in;i++) coutm[i]’ ‘; coutendl; } 输入：10 1 2 3 4 5 6 7 8 9 10 输出： 2、 算法改错：判断一棵二叉树是否平衡，是返回1，否返回0 void Post(bitptr t, int isbbt) { if(t) return 0; int hl=Post(t-lc,isbbt); int hr=Post(t-rc,isbbt); if(hl-hr1) isbbt=0; if(hlhr) hl=hr; return hl;