数据结构模拟题.doc

一、选择题（每题2分，共40分）1若进栈序列为A，B，C，D，进栈过程中可以出栈，则下面（ ）不可能出栈顺序。 A. BADCB. ABCDC. CBADD. DCAB2判断一个有向图是否有环（回路）的方法是（ ）。A. 求结点的度B. 拓扑排序C. 求关键路径D. 求最短路径3设单链表中结点的结构为（data,next）。已知指针p所指结点不是尾结点，若在指针p所指结点之后插入结点s，则应执行下列（ ）操作。As-next=p;p-next=s；Bs-next=p-next; p-next=s；Cs-next=p-next;p=s;Dp-next=s; s-next=p;4一棵二叉排序树，经过（ ）遍历可以得到一个有序序列。A. DLRB. LDRC. DLRD. RDL5以下是平衡二叉树的是（ ）。ABCD6一棵具有782个结点的完全二叉树的叶子结点数为（ ）。A. 390B. 391C. 392D. 3937在数据结构中，逻辑上数据结构可分为（ ）。 A 动态结构和静态结构 B.线性结构和非线性结构C.紧凑结构和非紧凑结构 D.内部结构和外部结构8. 具有1048个结点的完全二叉树的深度为( ).A. 12B.10C.11D. 139. 有一个有序表为8,15,20,22,32,41,45,62,75,77,82,85,97，当二分查找值为32的数据时要进行（ ）次比较。A. 1B.2C.3D. 410. 若用起泡排序对序列1,14,8,29,12,52,5,20,8,10从大到小排序,需要( )次比较。A. 28B.36C.45D. 411二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是（ ）。A. HGFEDACBB. GHEDFCBAC. CEFDBHGAD. HGAFDEBC12已知关键字的集合20，30，10，15，12，依次构造平衡二叉树，当插入15时，引起二叉树不平衡，则采用的旋转类型（ ）。A. LRB. LLC. RLD. RR13队列操作的原则是（ ）。A. 先进先出B. 后进先出C. 只能进行插入D. 只能进行删除14设哈希表长为16，哈希函数是H(key)=key%13,表中已有数据的关键字为15,29,43,57共四个，现要将关键字为55的结点加到表中，用二次线性哈希表解决冲突，则放入的位置是（ ）。A. 6B. 7C. 8D. 915已知一组数为 3, 5, 6, 7,8,用这组数构成的哈夫曼树的带权路径长度（ ）。 A. 66B. 56C.68D. 7616. 有关二叉树的说法正确的是:A. 二叉树的度为2 B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度为217. 在一棵二叉树中，度为0的结点有30个，度为1的结点有40个，则二叉树总的结点数有( )。A. 39B. 99C.101D. 7618. 计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、（ ）。A 输出、可行性、可移植性和可扩充性B 输出、易读性、可行性和稳定性C输出、确定性、有穷性和稳定性D 输出、可行性、有穷性和确定性19. 下面程序段的时间复杂度为（ ）。void func(int n)int s = 1, t = 100;while (s 1，则其双亲结点的编号是 。5. 在一棵10阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是 。6. 假定对数据序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后,在 7的左边数据依次是 ，7的右边数据依次是 。7.求最小生成树的算法常见的算法有prim算法和 算法三、问答题（共26分）1假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。（1）画出该树；（2分）（2）写出后序序列；（2分）（3）写出对应该二叉树的森林；（2分）2根据下图所示的AOE网，顶点V1,V2,V3,V4,V5,V6, V7,V8,V9表示事件，弧a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12表示活动，请回答以下问题： (1) 去掉边的方向后，画出最小生成树。（2分）(2) 求出所有事件的最早发生时间与最迟发生时间。（4分）(3) 列出所有关键活动。（2分）3设关键字输入序列为21，30，12，40，69，55，26，53 （1）（2分）试构造平衡二叉树；（2）（2分）构造3阶B-树，并分别写出删除21和40后的B-树。（3）（2分）HASH表表长为10，HASH函数为H（key）=key%9，试用二次探测再散列解决冲突的方法构造哈希表。4（6分）写出3个结点的树；3个结点的二叉树；二叉树的五种形式。四、算法设计（每题7分，共14分）1试写出计算二叉树结点数的递归算法。已知二叉树结点定义如下：typedef struct bitnode int data; bitnode *left,*right;bitnode;2已知一带表头结点的单链表，结