数据结构模拟题（开卷）.doc

中国地质大学（北京）继续教育学院 2012年09课程考试数据结构模拟题（开卷） 一、单项选择题1.分析下列算法suanfa1(n): void suanfa1(int n) int i,j,x=1； for(i=0；in；i+) for(j=0；jn；j+) x=x*2； printf(%d,x) 其中语句x=x*2；的执行次数是( D )。A.(n*2)2 B.(n-1)2 C.(n+1)2 D.n22.折半查找有序表(16,20,30,35,40,46,60,80),若查找元素80,需依次与表元素( D )进行比较。A.35,46,80 B.40,60 C.40,60,80 D.35,46,60,803.对长度为10的表作选择(简单选择)排序,共需比较( A )次关键字。A.45 B.90 C.10 D.1104.下列算法suanfa2(n)的时间复杂度为( A )。 int suanfa1(int n) int i,x=0； for (i=0；i5；i+) for (j=1；j0)个结点的完全二叉树的深度为log2(n+1)或 log2n+1或 log2n+1。5._ 线性表中元素的数目_称为线性表的长度。6._ 限定在表头作删除,在表尾作插入_的线性表称为队列。7.设n个元素的线性表顺序存储,若在它的第i个(1in)元素之后插入一个新元 素,共需移动_ n-i _个元素。8.构造Hash函数的方法有直接定址法、随机数法、_数字分析法、除留余数法、平方取中法、折叠法_等。9.对n个记录的表进行简单选择排序,共计需要进行_ n(n-1)/2 _次比较关键字, 在最坏情况下,共计交换_ n-1_对记录。10.字符串A中_连续字符组成子序列_称为串A的子串,_ 仅由空格字符组成的字符串称为空格串。 11.深度为k(k0)的满二叉树共有_2k-1-1_个非叶子。12.在有向图G中,以顶点i为_弧尾的弧_的数目称为i的出度。四、画图题1.试画出下列稀疏矩阵以行序为主序的三元组表。 稀疏矩阵参考答案：1.行序为主序的三元组表。 行号 列号 值 13182133424536612342.下列树的双亲表示法: 参考答案：2.下列树的双亲表示法: 3.试画出下列有向图G的逆邻接表。 有向图G 参考答案：3.有向图的逆邻接表:4.二叉树T的顺序存储结构:参考答案：4.二叉树T的顺序存储结构: 5.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F 试画出该二叉树。参考答案：5.前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F, 对应的二叉树如下: 五、求解下列问题1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树,(1)画出 生成之后的二叉排序树；(2)对该二叉排序树作中序、逆中序遍历，写出遍历序 列,(3)假定每个元素的查找概率相等,试计算查找成功时平均查找长度 。参考答案：1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树,(1)生成的二叉排序树是: (2)中序遍历序列: 3,6,7,8,10,25,27,30,42,60 逆中序遍历序列: 60,42,30,27,25,10,8,7,6,3(3)查找成功时平均查找长度: ASL=(1+2+2+3+3+3+3+4+4+5)/10=3.02.试按表(30,11,18,4,55,19,15,70,58)中元素的排列次序,将所有元素插入一棵 初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)画出插入完成之后的 二叉排序树；(2)假设每个元素的查找概率相等,计算该树的平均查找长度ASL。参考答案： 2.解:(1)构造二叉排序树: (2)平均查找长度: ASL=(1+2+2+3+3+3+4+4+4)/9=26/92.93.试对下列网,(1)从顶点A出发,求(画)出一棵宽度优先生成树；(2)从顶点D出发,用Prim(普里姆)算法求出一棵最小生成树，写出求解过程。 参考答案：3.(1)从顶点A出发,宽度优先生成树之一； (1) 从顶点D出发,用Prim(普里姆)算法求出最小生成树之一:(2) 六、设计题1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言 类型定义分别写出结点类型和指针类型的定义。参考答案：1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言 类型定义分别写出结点类型和指针类型的定义。typedef struct node int data; struct node *mext; node,*linklist;七、简答题 1.二叉树有哪几种基本形态? 试举例说明。参考答案：1.答:二叉树有5种基本形态,举例如下： 其中：B1:为空二叉树；B2:有根结点,左右子树均为空二叉树；B3:有根结点,左子树为非空二叉树,右子树为空二叉树；B4:有根结点,左子树为空二叉树,右子树为非空二叉树； B5:有根结点,左右子树均为非空二叉树。2.线性表的顺序存储结构和链式存储结构各有哪些优点和缺点?参考答案：2.答:对于顺序存储结构: (1)优点:是一种随机存取结构,存取任何元素的时间是一个常数,速度快；结构简单,逻辑上相邻的元素在物理上也是相邻的；不使用指针,节省存储空间。 (2)缺点:插入和删除元素,平均需要移动约半个表的元素,消耗大量时间；需要提供一个连续的存储空间；插入元素可能发生“溢出”；表尾之后的自由存储空间不能被其它表的数据占用(共享)。对于链式存储结构:(1)优点:插入和删除元素,不必移动元素,只需修改相关结点的指针；不需要一个连续的存储空间。 (2)缺点:不是随机存取结构,查找元素的时间与元素在表中位置有关,不是一个常数；使用指针,指针需占用一定的存储空间；系统需提供动态存储管理功能。八、算法说明:输入一列整数,以0为结束标志,生成带头结点的递增有序单链表。结点类型定义和算法： struct Lnode int data； struct Lnode *next； ； struct Lnode *creat( ) struct Lnode *head,*f,*q,*p；int e； head=(struct Lnode *)malloc(struct Lnode)； head-next=NULL； do f=_； scanf(%d,&e)；f-data=e； q=head；p=_； while (p & ep-data) q=_； p=_； f-next=_； q-next=_； while(e)； return head；参考答案：八、算法填空 struct Lnode int data； struct Lnode *next； ； struct Lnode *creat( ) struct Lnode *head,*f,*q,*p；int e； head=(struct Lnode *)malloc(struct Lnode)； head-next=NULL； do f=(struct Lnode *)malloc(structLnode)； scanf(%d,&e)；f-data=e； q=head；p=p-next； while(p & ep-data) q=p； p=p-next ； (* 或 q=q-next； p=q-next；*) f-next=p； q-next=f； while(e)； return head； 第8页（共8页）