《2017年南京工业大学数据结构(同等学力加试)复试实战预测五套卷.doc》由会员分享，可在线阅读，更多相关《2017年南京工业大学数据结构(同等学力加试)复试实战预测五套卷.doc（3页珍藏版）》请在金锄头文库上搜索。
1、2017年南京工业大学数据结构(同等学力加试)复试实战预测五套卷一、应用题1 设散列表为数分别为：注：是求余数运算中，函数码序列为（2）计算搜索成功的平均搜索长度表示颠倒十进制数x 的各位，如 即表的大小为 其等。若插入的关键，现采用双散列法解决冲突。散列函数和再哈希函（1）试画出插入这8个关键码后的哈希表；【答案】（1）插入这8个关键码后的哈希表如表所示：表 插入关键字后的哈希表 （2） 个最小元素，你所学过的排序方法中哪个最小元素，应使用快速排序方法。其基本 2 如果只要找出一个具有n 个元素的集合的第种最适合? 给出实现的思想。【答案】在具有n 个元素的集合中找第思想如下：设n 个元素的
2、集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若则在1至i-1间继续进行快速排序的划分；若则在i+1至n 间继续进个最小元行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第素。3 （1）判定起泡排序的结束条件是什么？（2）请简单叙述希尔排序的基本思想。 （3）将下列序列调整成堆（堆顶为最小值）。 （4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。【答案】（1）至多进
3、行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。（3）13，24，33，65，70，56，48，92，80，112（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最大值，均与兄弟比较，共4次
4、选出亚军）。 4 设二叉树BT 的存储结构如表：表 二叉树BT 的存储结构 其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：（1）画出二叉树BT 逻辑结构；（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。【答案】（1）二叉树的逻辑结构如图1所示： 图1（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA（3）:二叉树的后续线索树如图2所示： 图2 5 给出一组关键字：29，18，25，47，58，12，51，10，
5、分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58; 第三趟：10，12，18，25，29，47，51，58（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序建大堆：58，47，51，29，18，12，25，10; 51，47，25，29，18，12，10，58; 47，29，25，10，18，12，51，58; 29，18，25，10，12，47，51，58; 25，18，12，10，29，47，51，58; 18，10，12，25，29， 47，51，58; 12，10，18，25，29，47，51，58; 10，12，18，25，29， 47，51，58一、应用题考研试题
