数据结构+算法分析与设计［15-18真题版］
2015年考试试题
一、给出数组A[3..8,2..6]0F integer,当它在内存中按行存放和按列存放时，分别写出元素A[i,j]的地址计算公式(设每个元素占两个存储单元)。(10分)
二、已知一棵二叉树的中序序列的结果是BDCEAFHG,后序序列的结果是DECBHGFA,试画出这棵二叉树。(10分)
三、对下图所示的二叉树分别求出其先序、中序、后序序列。(10分)
四、己知图G如下，给出从顶点V1出发的一个深度优先生成树；给出从顶点V1出发产生的一个广度优先生成树。(10分)
五、使用克鲁斯卡尔算法构造出如下图所示的图G的一棵最小生成树。(10分)
六、试证明有n0个叶子的哈夫曼树共有2n0-1个结点。(10分)
七、给出一组关键字(12,2,16,30,28,10,16,20,6,18),分别写出按下列各种排序方法进行排序时的变化过程： (15分)
(1)直接排序，每排序一次书写一个次序。
(2)快速排序，每划分一次书写一个次序。
(3)堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
八、设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数：H(Key)=Key MOD 13采用开放地址法的二次探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。(15分)
九、有一份电文中共使用5个字符：A、B、C、D、E,它们出现的频率依次为4、7、5、2、9。
试画出对应的哈夫曼树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。并求出每个字符的哈夫曼编码和带权路径长度。(15分)
十、编一函数，使输入的一个字符串按反序存放，在主函数中输入和输出字符串。(15分)
十一、编写一个程序，用“起泡法”对输入的20个字符按由小到大顺序排序。(15分)
十二、有数组A[4][4],把1到16个整数分别按顺序放入A[0][0],…,A[0][3],A[1][0],…,
A[1][3],A[2][0],…,A[2][3]A[3][0],…,A[3][3]中，编写一个函数获取数据并求出两对角线元素的乘积。(15分)
2016年考试试题
一、设有二维数组A[6][8],每个元素占6个字节存储，实现存放，A[0][0]的起始地址为1000,计算： (10分)
(1)数组最后一个元素A[5][7]的起始地址；
(2)按行优先存放时，元素A[1][4]的起始地址；
(3)按列优先存放时，元素A[4][7]的起始地址。
二、若有一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 (10分)
三、首先将下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度优先遍历，广度优先遍历的结果。(10分)
四、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。(10分)
五、使用普里姆算法构造出如下图所示的图G的一棵最小生成树。(10分)
六、任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有(m-1)个度数为2,其余度数为1。(10分)
七、给出一组关键字(29,18,25,47,58,12,51,10),分别写出按下列各种排序方法进行排序时的变化过程：(15分)
(1)归并排序，每归并一次书写一个次序。
(2)快速排序，每划分一次书写一个次序。
(3)堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
八、对关键字序列7,4,1,14,100,30,5,9,20,134,设哈希函数为H(X)=X MOD 13。试给出表长为13的哈希表(用线性探测开放定址法处理冲突)。(15分)
九、假定用于通信的电文仅由8个字母cl,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数。(15分)
十、试写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。(15分)
十一、编写程序求1!+2!+3!+4!+…+30!之和。(15分)
十二、定义一个通讯录结构，成员包括：姓名(字符串)、电话(字符串)、生日(日期结构：年、月、日)。编写函数实现数据的输入、输出和按姓名查找。(15分)
2017年考试试题
一、设有一个10阶的对称矩阵A,采用以行优先的方式压缩存储。a11为第1个元素，其存储地址为1,每个元素占3个存储单元。问元素a85和a58的地址是多少?(10分)
二、已知二叉树的前序序列是A-B-D-G-C-E-F,中序序列是D-G-B-A-E-C-F,试画出这该棵二叉树。(10分)
三、己知图G如下，给出从顶点V1出发的一个深度优先生成树；给出从顶点V1出发产生的一个广度优先生成树。(10分)
四、已知一棵二叉树的中序序列为C-B-E-D-A-H-G-I-J-F,后序序列为C-E-D-B-H-J-I-G-F-A,试画出这棵二叉树的先序线索二叉树。(10分)
五、使用克鲁斯卡尔算法构造出如下图所示的图G的一棵最小生成树。(10分)
六、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该树中有多少个叶子结点。(10分)
七、设待排序的排序列为(12,2,16,30,28,10,16*,20,6,18),试分别写出按下列排序方法进行排序时的变化过程(即每趟排序后的结果)。(1)直接插入排序；(2)快速排序；(3)希尔排序。(15分)
八、设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数：H(Key)=Key MOD 13采，用开放地址法的线性探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。(15分)
九、有一份电文中共使用5个字符：A、B、C、D、E,它们出现的频率依次为4、7、5、2、9。试画出对应的哈夫曼树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。并求出每个字符的哈夫曼编码和带权路径长度。(15分)
十、试编写将用二叉链表表示的完全二叉树转换为二叉树的顺序(数组)表示的算法。(15分)
十一、有n个人围成一圈，顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子，问最后留下的是原来第几号的那个人。(15分)
十二、编写几个函数。(1)输入20个员工的姓名和员工号；(2)按员工号由小到大排序，姓名顺序也随之调整；(3)要求输入一个员工号，用折半查找法找出该员工的姓名。从主函数输入要查找的员工号，输入该项员工姓名。(15分)
2018年考试试题
一、设有一个二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间，问A[3][3]存放在什么位置。(10分)
二、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。(10分)
三、己知图G的邻接表如下所示，顶点V1为出发点，完成下列要求，请画出：(1)由深度优先搜索得到的一棵生成树；(2)由广度优先搜索得到的一棵生成树。(10分)
四、首先将下图G所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度优先遍历，广度优先遍历的结果。(10分)
五、使用普里姆算法构造出如下图所示的图G的一棵最小生成树。(10分)
六、如果一棵树有n1个度为1的结点，有n2个度为2的结点，…,nm个度为m的结点，试问,有多少个度为0的结点?试推导之。(10分)
七、分别写出按下列各种排序方法对已知序列进行排序时的每一趟结果：(15分)
(1)冒泡排序，已知序列{17,18,60,40,7,32,73,65,85}。
(2)希尔排序，已知序列{10,18,4,3,6,12,1,9,15,8}。
(3)归并排序，已知序列{10,18,4,3,6,12,1,9,15,8}。
八、将序列13,15,22,8,34,19,21插入到一个初始时是空的散列表中，散列函数采用H(X)=1+(X MOD 7)。使用步长为3的线性探测法解决冲突。(15分)
九、已知A、B、C、D、E、F等字符的出现概率分别为0.26、0.1、0.12、0.16、0.28、0.08,求其不等长Huffman编码和平均码长。(15分)
十、编写一个函数，利用二分查找算法在一个有序表中插入一个元素X,并保持表的有序性。(15分)
十一、已知有函数的定义如下：(15分)
{n+1 if m=0
akm(m,n)={akm(m-1,1) if m<>0 n=0
{akm(m-1,akm(m,n-1) if m<>0 n<>0
(1)写出递归算法程序。
(2)写出非递归算法程序。
十二、将100名员工的个人信息从键盘输入、然后送到磁盘文件worker.rec中保存。设员工信息包括员工号、姓名、工资，再从磁盘读入这些数据，并依次显示在屏幕上(要用fread()函数和fwrite()函数),试编写程序。(15分)