资源描述：
《《数据结构》期末(A卷)_2011》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、命题方式：独立命题佛山科学技术学院2011—2012学年第一学期《数据结构》（A卷）课程期末考试试题专业、班级：10计算机①②姓名：学号：题号一二三四五六七八九十十一十二总成绩得分一、填空（20分，每空2分）1.数据结构的存储结构包括顺序、、索引和散列等四种。2.存储结构是逻辑结构的实现。3.在程序运行过程中可以扩充的数组是分配的数组。这种数组在声明它时需要使用数组指针。4.在链表中进行插入和操作的效率比在顺序存储结构中进行相同操作的效率高。5.栈是一种特殊的线性表，允许插入和删除运算的一端称为。6.若一个算法中的
2、语句频度之和为T(n)=n+2nlogn，则算法的时间复杂度为。7.一棵具有10个结点的完全二叉树，它的深度为。8.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2、e3、e5、e4、e6、e1，则栈S的容量至少应该是。9.在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素22，需进行次元素之间的比较。10.在对一组记录（18，6，27，12，52，15，47，29）进行直接插入排序时，当把
3、第5个记录52插入到有序表时，为寻找插入位置需比较次。二、选择题（20分，每选2分）1.数据的四种基本逻辑结构是指（）A．数组、链表、树、图形结构B．线性表、链表、栈队列、数组广义表C．线性结构、链表、树、图形结构D．集合、线性结构、树、图形结构共6页第6页1.线性表采用链式地址时，其地址（）A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（）A．n–i+1B．n–iC．iD．i-13.一个栈的入栈序列是
4、a、b、c、d、e，则栈的不可能的输出序列是（）A．edcbaB．decbaC．dceabD．abcde4.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.(rear-l)MODn=frontC．rear+1=frontD.rear=front5.在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）A．O(n)B．O(1)C．O(n2)D．O(log2n)6.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．nB．n-
5、1C．n+1D．2*n7.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba8.n个顶点的有向图中含有向边的数目最多为（）A．n-1B．nC．n(n-1)/2D．n(n-1)9.一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为（）。A．12,38,25,35,50,74,63,90B．12,38,35,25,74,50,63,90C．12,25,35,38,50
6、,74,63,90D．12,35,38,25,63,50,74,90共6页第6页三、解答题：（共40分）1．（5分）将下列树转换成为二叉树（只要求给出转换结果）2．(7分)设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均查找长度。3．(8分)以数据集（9，19，2，6，32，3，21，10）为叶结点的权值，构造一棵哈夫曼树，并计算其带权路径长度。共6页第6页（14分）已知一组关键字为（39,23,54,25,31,28,55,12,19,51,64），用链地址法解决冲突。
7、假设装填因子α=0.75，散列函数的形式为H（K）=KMODP，回答下列问题：（1）构造出散列函数；（3分）（2）画出插入全部关键字后的链地址散列表（5分）（3）计算出等概率情况下查找成功的平均查找长度（3分）（4）计算出等概率情况下查找失败的平均查找长度（3分）共6页第6页（6分）对关键字序列(56，20，23，75，29，61，36，87)进行堆排序，使之按关键字递增次序排列，请写出排序过程中建初始堆的过程。四、证明与问答题（共20分）1．(10分)写出求一棵二叉树的叶子结点个数的算法。二叉树的存储结构为二叉链
8、表，要求写出二叉链表的类型定义。共6页第6页(10分)试设计出对n个记录进行直接插入排序的算法，要求写出Sqlist的定义。共6页第6页
