数据结构及算法-考试范围题及答案解析like

1、.数据结构与算法考试参考题专业：计算机科学与技术 13年一、单选 30分1.在数据结构中,数据的逻辑结构可分 B.线性结构和非线性结构2.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用 C.指向后继元素的指针表示3.设p指向单链表中的一个结点。S指向待插入的结点,则下述程序段的功能是 D.在结点*p之前插入结点*ss-next=p-next; p-next=s!t=p-data; p-data=s-data; s-data=t; B.在p所指结点的元素之前插入元素 D.在结点*p之前插入结点*s4. 栈和队列都是 C:链式存储的线性结构A:限制存取位置的线性结构B:顺序存储的线性结构

2、C:链式存储的线性结构D:限制存取位置的非线性结构5.下列关于线性表的基本操作中,属于加工型的操作是 B初始化、插入、删除操作6.根据定义,树的叶子结点其度数 B.必等于07.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为 A.数组的元素处在行和列两个关系中8.从广义表LS= p,q,r,s中分解出原子q的运算是B. headtallhead 9.在具有n个叶子结点的满二叉树中,结点总数为 C. 2n-110.若是有向图的一条边,则称 D. Vi与Vj不相邻接11.二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有 B. 2n个指针域其中n+1个指针为NULL12.在一个无向

3、图中,所有顶点的度数之和等于边数的 B. 2倍13. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度的时间复杂度为 A.O14.散列法存储中出现的碰撞冲突现象指的是 B.不同关键码值对应到相同的存储地址15.循环链表适合的查找方式是 A. 顺序二、填空 20分1.若一棵完全二叉树中含有121个结点,则该树的深度为 72.若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的 。3.二叉树的遍历主要有先序遍历、后序遍历和 中序遍历三种。4.深度为3的完全二叉树至少有 4个结点。5.若图的邻接矩阵是一个对称矩阵,则该图一定是一个 无向图

4、6.若某无向图G的邻接表如下图所示,试给出以顶点V3为出发点,按广度优先搜索所产生的结点序列 V3-2V1-V4-V5 7.在无向图中,若从顶点a到顶点b存在 路径,则称a与b之间是连通的。8.我们通常把队列中允许删除的一端称为 队头9.表头和表尾均为 a,的广义表L= 10.假定对有序表： 进行折半查找,若查找元素24 程序设定为向下取整,需依次与 元素进行比较。三、解答 50分1.二维数组A10.20采用按行为主序的存储方式,每个元素占4个存储单元,若A1.1的存储地址为300,则请算A10,10的存储地址。答： 300+ 9*20+10*4=300+190*4=300+760=10602

5、.已知树如右图所示：1画出由该树转换得到的二叉树；.原图答图：.2写出该二叉树的后序序列：答： 后序序列为：E B K J I H G F D C A3.试给出如图所示的邻接矩阵和邻接表表示。.答： 邻接矩阵.4.已知某二叉排序树10个结点的值依次为1-10,其结构如图所示,试标出该二叉排序树各结点所对应的具体值。原图：答图： 5.试构造下图的最小生成树,要求分步给出构造过程。原图：答图： 1. 2. 3.4.6.从一个空的二叉排序树开始,依次插入关键字试画出插入关键字后的二叉排序树,并计算查找成功时的平均查找长度。average search length平均查找长度答： ASL=/7=18

6、/7主要思想是以第一个数为标准,将比此数小的放在左边,大的放在右边,再一一插入,通过比较,找到末端为止。如13比25小,便在左边,后15小于25,又在25左端,但是比13大,故放在了13的右边,每个数都是这样找到自己的位置的。7.为关键字 构造一个长度为7的散列表,设散列函数为h=key%7,用开放定址法解决冲突的探查序列是Hi=h+%7 0i6画出构造所得的散列表；求出在等概率情况下查找成功时的平均查找长度。答： ASL=/5=11/5H=17%7=3H=33%7=5H=31%7=3 冲突？%= 3+1 31%5+1%7=5%7=5 冲突Hi=3+2%7=%7=0H=40%7=5 冲突Hi=

7、5+1%7=6%7=6H=48%7=6 冲突Hi=6+1%7=%7=3 冲突Hi=6+2%7=%7=0 冲突Hi=6+3%7=%7=18%7=4 012345631174833408.顶点C出发进行深度优先遍历的序列。原图：答： CDABFE完1.已知一棵树边的集合为,请画出这棵树,并回答下列问题： 1哪个是根结点？ 2哪些是叶子结点？ 3哪个是结点g的双亲？ 4哪些是结点g的祖先？ 5哪些是结点g的孩子？ 6哪些是结点e的孩子？ 7哪些是结点e的兄弟？哪些是结点f的兄弟？ 8结点b和n的层次号分别是什么？ 9树的深度是多少？ 10以结点c为根的子树深度是多少？1.解答： 根据给定的边确定的树

8、如图5-15所示。其中根结点为a；叶子结点有：d、m、n、j、k、f、l；c是结点g的双亲；a、c是结点g的祖先；j、k是结点g的孩子；m、n是结点e的子孙；e是结点d的兄弟；g、h是结点f的兄弟；结点b和n的层次号分别是2和5；树的深度为5。4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。4.解答： 先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA数据结构：在一棵空的二叉查找树中依次插入关键字学列为54,18,66,87,36,12 请画出所得到的二叉排序树数据结构题：二维数组A1020采用列序为主方式存储,每个元素占一个存储单元并且A00的存储地址是200则A612的地址是326。还有这题：二维数组A10.205.10采用行序为主方式存储,每个元素占4个存储单元,并且A105的存储地址是1000,则A189的地址是1208。答案第一题:列序存储,则A