《数据结构》期末(A卷)_2011.doc

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