数据结构以前的试题.doc

一、选择题（共10题，2分/题，共20分） （下列各题四个项,请选项 2 3 4 5 6 7 8 9 10 1．以下数据结构中哪一个是非线性结构？( ) A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树 2．对于二维数组A采用以行序为主序的结构进行存储，每个元素需要1个字节的存储空间，且A在内存中的存储基地址为1000，则A[3][4]在内存的存储地址为：( ) A. 1019 B. 1020 C. 1027 D. 1028 ．在一棵度为3的树中为3的结点个数为2度为2 的结点个数为1无度为1的结点，则度为0的结点个数为( ) A．4 B．5 C．6 D．7 有64个结点的完全二叉树的深度为( )(根的层次为1)。 A. 8 B. 7 C. 6 D. 5 ．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 .下列编码中属前缀码的是(????? )。 A.{1,01,000,001}???????? B.{1,01,011,010} C.{0,10,110,11}? ? D.{0,1,00,11} ．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为（ ）。 A. 1,2,3 B. 9,5,2,3 C.9,5,3 D.9,4,2,3 ．任何一个无向连通图的最小生成树（ ）。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 ．设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 ．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4 的长度是所占用的存储空间的大小的操作遵循的原则在采用线性探测法处理冲突所有同词在表中相邻根据数据元素之间关系的不同特征，通常有和 4种基本结构。 一个无向图完全图中，共有 条边。 假定一组记录的排序码为（），对其进行归并排序的过程中，第三趟归并后的结果为__________________________________。 取出广义表A=（（x，y，z），（a，b，c））中原子b的函数是 。 二分查找法要求查找表中的数据元素应满足的条件是 。 单链表中指针P所指结点不为尾结点的条件是___________。 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度与和 有关。 如右图所示的二叉树，按中序遍历所得到的结点序列为 。 在下面的程序段中，对x的赋值语句的频度为_________________。 for（i=1;i=n;i++） for（j=i;j=n;j++） x=x+1; 10．在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是 。 四、应用题（共5题，共30分） 1．画出和下列已知序列对应的树T：（5分） 树的先根次序访问序列为：GFKDAIEBCHJ 树的后根次序访问序列为：DIAEKFCJHBG 2. 已知一个哈希表如下图所示：（5分） 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其哈希函数为h(key)=key%13, 处理冲突的方法为再哈希法，探查序列为： hi=(h(key)+*