2017年南京邮电大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？ （2）试证明
。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
2． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的
是否总有a ≤b ≤c? 为什么？
【答案】该结论不成立。例如，本题中对于任一f 的左子树上。对于从a 到根结点路径上的所有
，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
的右子树上，这时a>b，因此a 3． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？ 【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元） 元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小 且分布没有规律。用十字链表作存储结构自然失去了随机 最差情况下是 因此也失去 存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。 4． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。 要求： （1）写出图G 的邻接矩阵A 。 （2）画出有向带权图G 。 （3）求图G 的关键路径，并计算该关键路径的长度。 【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）： 可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示： 将各元素填入各行即得邻接矩阵： （2）根据第一步所得矩阵A 容易做出有向带权图G , 如下： （3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。 由上图容易求得图的关键路径长度为：4+5+4+3 = 16。 5． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？ 【答案】不一定相邻。哈希地址为同义词，都争夺哈希地址i 。 6． 设散列表为即表的大小为数分别为 ： 注：％是求余数运算中，函数码序列为 （2）计算搜索成功的平均搜索长度 表示颠倒十进制数x 的各位，如 其 等。若插入的关键 的关键字，和为解决冲突形成的探测序列f 的 ，现采用双散列法解决冲突。散列函数和再哈希函 （1）试画出插入这8个关键码后的哈希表； 【答案】（1）插入这8个关键码后的哈希表如表所示： 表 插入关键字后的哈希表 （2） 7． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：列法，要求装填（载）因子为0.7。 （1）请画出所构造的散列表。 （2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。 【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表： 采用线性探测法再散列法处理冲突，所构造的散列表为： （2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示： 故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。 在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需 处理冲突采用线性探测再散