信科2010级数据结构试卷

1、。装。订。线。2011 年2012 年第 2 学期 信科 10 级数据结构时间共 120 分钟试卷 B 卷一、填空题（每题 1 分，共 15 分）1. 数据结构的结构包括、索引和散列等四种。2、栈是一种限定在表的一端进行和删除的线性表，又被称为表。3、算法的五个重要特性是 、 、和输出。4、对于二维数组 floata54计算：若数组 a 的起始地址为 2000，且每个数组元素长度为 32 位，数组元素 a32的内存地址为。5、一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点 f 的层数为。假定树根结点的层数为 0。6. 一棵树按照孩子-兄弟表示法转换成对应的二

2、叉树，则该二叉树中树根结点肯定没有。7. 向一棵二叉排序树中一个元素时，若元素的值小于根结点的值，则应把它到根结点的上。8、在哈希表中的查找中，评判一个哈希函数优劣的两个主要条件是和。9、完全有向图中弧的个数为。10、在一棵 AVL 树（高度平衡的二叉排序树）中，每个结点的。树高度与右子树高度之差的绝对值不超过二、单向选择题（每题 1 分，共 15 分）1、线性表是一个具有 n 个的有限序列。A表元素B字符C数据元素D数据项2、设无向图的顶点个数为 n，则该图最多有条边。An-1Bn(n-1)/2+1)/2C0结构最节省时间。结点的循环链表3、设线性表最常用的操作是存取指定序号的元素，则采用A

3、、顺序表4、线性表采用链式A、必须是连续的B、单链表C、双链表D、时，其地址。B、一定是不连续的C、部分地址必须是连续的 D、连续与否均可以5、对于循环队列，A、R-F空间大小为 n，头指针为 F，尾指针为 R，则队列中元素的个数为。B、n+R-FC、（R-F+1）mod nD、（n+R-F）mod n6、栈与一般的线性表的区别在于。A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同7、设有三个元素 X、Y、Z 顺序进栈，在进栈过程中可以出栈，下列出栈顺序中错误的排列是。A、XYZB、YZXC、ZXYD、ZYX8、“假上溢”现象会出现在中。A、循环队列B、队列C、链

4、队列D、顺序队列9、串是一种特殊的线性表，其特殊性体现在。A、可以顺序B、数据元素是一个字符C、可以D、数据元素可以是多个字符得分阅卷人得分阅卷人题号12345678910总分得分阅卷人10、当输入错误时，一个好的算进行适当处理，而不会产生难以理解的输出结果，这称为算法的A、可读性B、健壮性C、正确性D、有穷性11、对广义表 A=（x,(a,b),c,d)），运算 head(head(tail(A)的结果是。A、xB、(a,b)C、(a,b)D、c12、在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是。A、树的最右下结点B、右子树的最右下结点C、树的最左下结点D、右子树的最左下结点1

5、3、Huffman 树的形态是。A、唯一的B、不定的C、不唯一D、以上说法都不对14、当执行函数调用时，其局部变量的一般采用进行。A、树型结构B、静态链表C、栈结构D、队列结构15、线性表必须是,才能进行折半查找。A、用向量的线性表 B、用链表的有序表 C、用链表的线性表 D、用向量的有序表三、判断题（每题 1 分，共 10 分）1、静态链表既有顺序的优点，又有动态链表的优点，所以它存取表中第 i 个元素的时间与 i 无关。（ ）2、由前序序列和中序序列可以唯一确定一棵二叉树。 （）3、稀疏矩阵压缩后，必会失去随机功能。（）4、若一个广义表的表头为空表，则此广义表亦为空表。 （5、完全二叉树的

6、某个结点若无左孩子，则它必是叶子结点。（6、数组可以看成是线性结构的一种推广，因此可以对它进行7、如果从无向图的任一顶点出发进行一次深度优先搜索即可）、删除等运算。（）所有顶点，则该图一定是连通的。（）8、在求网的最小生成树时，9、先删除二叉排序树中一个姆算法适用于稀疏网，而算法使用于稠密网。（），再重新该，一定能得到原来的二叉排序树。（）10、循环队列是链式结构。（）四、简答题（每题 5 分，共 15 分）1、已学过的顺序表的检索方法有哪些？答：2、在一棵二叉树的先序序列、中序序列和后序序列中，任意两种序列的组合可以唯一地确定这棵二叉树吗？若可以，有哪些组合？若不可以，有那些组合？答：3、顺

7、序、链式和静态链表各自特点？答：五、应用题（共 35 分）1、已知一棵二叉树的中序序列和后序序列分别为：BDCEAFHG 和 DECBHGFA，请写出其先序序列。（7 分）得分阅卷人得分阅卷人得分阅卷人先序序列为：2、假设用于通讯的电文由 a,b,c,d,e,f,g，h 等 8 个字母组成，字母在电文中出现的频率分别为 0.03，0.12，0.07，0.04，0.02，0.08，0.11 和 0.10。求：（）画出树；（）为这些字母设计蔓编码；（）求出带权路径长度。（6 分）3、设有 12 个数据25，40，33，47，12，66，72，87，94，22，5，58，将它们在哈希表中，哈希函数为：H（key）=key mod 11，利用开放定址法中的二次探测再散列解决，并求出在等概率下的平均查找长度。（8）4、给出下图所示的有向图 G 的全部可能的拓扑排序序列。（8 分）123456答：5下图中给出由 7 个顶点组成的无向图。（6 分）从顶点 1 出发， 对它进行遍历，则：深度优先遍历得到的顶点序列是：广度优先遍历得到的顶点序列是：。六、算法题（共 10 分）1、假