数据结构试题3.doc

数据结构试题3一、单项选择题（每小题3分，共30分） 1、假设有 n个关键字，它们具有相同的Hash 函数值，用线性探测法把这 n个关键字存入到Hash地址空间中要做（ ）次探测。 A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2 2、若有一个栈的输入序列是 1，2，3，n 输出序列的第一个元素是 n，则第 i 个输出元素是（ ）。 A、n-i B、n-i-1 C、n-i+1 D、不确定 3、在一棵度为3的树中，度为 3的结点数为 2 个，度为2的结点数为 1个，度为1 的结点树为2个，那么度为 0的结点数为（ ）。 A、4 B、5 C、6 D、7 4、在一个具有 n个结点的无向完全图中，包含有（ ）条边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2 5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需（ ）次比较可检索成功。 A、 1 B、2 C、3 D、4 6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（ ）。 A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序 7、已知 8 个元素（34，76，45，18，36，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（ ）。 A、4 B、5 C、6 D、7 8、设有一个10阶的对称矩阵 A，采用压缩存储方式以行序为主存储，a00为第一个元素， 其存储地址为0，每个元素占有 1个存储地址空间，则a85的地址为 （ ）。A、13 B、33 C、17 D、32 9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为（ ）。A、6 B、7 C、8 D、20 10、给定权的集合15，3，14，2，6，9，16，17，所构造出的哈夫曼树的带权路径长度为（ ）。 A、129 B、219 C、189 D、229 二、判断题 （认为对的，在题后的括号内打“”，错的打“”，每小题分， 共分） 1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 （ ） 2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。 （ ） 3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。 （ ） 4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法两个方面。 （ ） 5、因为算法和程序没有区别，所以在数据结构中二者是通用的。 （ ） 6、进栈操作 push(x,s)作用于链接栈时，无须判满。 （ ） 7、稳定排序算法是最好的。 （ ） 8、二叉搜索树的左、右子树都是二叉搜索树。 （ ） 9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 （ ） 10、表中的每一个元素都有一个前驱和后继元素。 （ ） 三、填空题（每小题2分，共20分） 1、在散列表(Hash)查找中，评判一个散列函数优劣的两个主要条件是_和_。 2、设根结点处在第一层，那么具有 n 个结点的完全二叉树，其高度为_。 3、快速排序方法的最坏时间复杂度为_，平均时间复杂度为_。 4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为_。5、设图 G 的顶点数为 n，边数为 e，各顶点的度数为 D(Vi)，则e=_。 6、将5个不同的数据进行排序，至少需要比较_次，至多需要比较_次。7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二分折半查找时，最大比较次数是_，最小比较次数是_。 8、由 a，b，c3 个结点构成的二叉树，共有_种不同的结构。 9、在一棵高度为 h 的平衡二叉树中，至少含有_个结点，最多含有 2 h -1 个结点。10、在一个单链表中删除*p 结点，应执行如下操作 ：q=pnext;pdata=pnextdata; pnext=_; free(q); 四、简答题（每题10分，共60分） 1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？ 2、假设用于通讯的电文仅有 8 个字母组成，字母在电文中出现的频率分别为：7， 19，2，6，32，3，21，10。试用这8个频率值构造哈夫曼树，并画出该哈夫曼所对应的森林。3、已知一个长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec）： （1）构造最价二叉排序树； (2)试求在等概率情况下对此二叉排序树进行折半检索时检索成功的平均长度。 4、对于下图，试给出：（1）每个顶点的入度和出度； （2）邻接矩阵； （3）逆邻接表； （4）强连通分量；5、快速排序、插入排序、自然两路归并排序、堆排序，哪一种排序方法所需的辅助空间最大？请简单说明。 6、分析以下程序段中语句x=x+y的执行次数。 x=0; y=0; for(int i=1;i=n;i+) for(int j=1;j=i;j+) for(int k=1;k=j;k+)x=x+y; 五、算法设计题（每题15分，共30分） 说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、 假设以二叉链表作为二叉树存储结构，其类型定义如下： typedef struct node char data; struct node *lchild,*rchild; /左右孩子指针 BinTNode,*BinTree; 写一函数，完成以下功能： 对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子设置 为左孩子。 2、 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写 一个删除表中所有值大于 min且小于 max的元素 （若表中存在这样的元素） 的算法。 数据结构试题3答案一、15：CCCAB 610：DCBAD 二、15： 610： 三、1、 值均匀分布于表空间以减少冲突 函数尽可能简单以方便计算 2、logn的最小整数+1 3、O(n 2 ) O(nlogn) 4、(31 38 44 56 75 80 55 63) 或(80 75 55 56 63 44 31 38) 5、0.5*D(Vi)之和(in) 6、4 10 7、7 1 8、5 9、h 10、pnextnext 四、1、答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。 2、答案： （哈夫曼树有多种形态，不是唯一的。 ） （1）哈夫曼树为：（2）哈夫曼树所对应的森林为：3、答案：（1）（2）在等概率情况下检索成功的平均检索长度： ASL=（1*1+2*2+3*4+4*4+5*1）/12=38/12=19/63、 答案：（1）各个顶点的入度和出度如下：顶点：1 2 3 4 5 6 入度：2 2 1 3 2 1 出度：1 2 3 0 3 2（2）邻接矩阵为： （3）逆邻接表为： （4）、强连通分量有如下3个：5、答案：快速排序需要的辅助空间与辅助栈的深度有关，平均情况下为O(logn),最坏情况下需要 O(n)；插入排序和堆排序只需要一个元素大小的辅助空间在元素交换时用,为O(1)；而自然两路归并排序需和待排序数组同样大小的辅助空间，为O(n)，所以自然两路归并排序所需的辅助空间最大，快速排序次之，插入排序和堆排序最小。 6、答案：五、1、答案： void exchange(Bin Tree T) if(T) if(!Tlchild&Trchild) Tlchild= Trchild; Trchild=NULL; exchange(Tlchild); exchange(Trchild); 2、答