数据结构与算法-考试范围题与答案like

《数据结构与算法-考试范围题与答案like》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、结点*s4.栈和队列都是（C:链式存储的线性结构）A:限制存取位置的线性结构B:顺序存储的线性结构C:链式存储的线性结构D:限制存取位置的非线性结构5.下列关于线性表的基本操作中，属于加工型的操作是（B初始化、插入、删除操作）6.根据定义，树的叶子结点其度数（B.必等于0）7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（A.数组的元素处在行和列两个关系中）8.从广义表LS=（（p,q）,r,s）中分解出原子q的运算是(B.head(tall(head(LS)))9.在具有n个叶子结点的满二叉

3、树中，结点总数为（C.2n-1）10.若是有向图的一条边，则称（D.Vi与Vj不相邻接）11.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（B.2n个指针域其中n+1个指针为NULL）12.在一个无向图中，所有顶点的度数之和等于边数的（B.2倍）13.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（A.O(n)）14.散列法存储中出现的碰撞（冲突）现象指的是（B.不同关键码值对应到相同的存储地址）15.循环链表适合的查找方式

4、是（A.顺序）二、填空（20分）1.若一棵完全二叉树中含有121个结点，则该树的深度为（7）2.若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的。3.二叉树的遍历主要有先序遍历、后序遍历和（中序遍历）三种。4.深度为3的完全二叉树至少有（4）个结点。5.若图的邻接矩阵是一个对称矩阵，则该图一定是一个（无向图）6.若某无向图G的邻接表如下图所示，试给出以顶点V3为出发点，按广度优先搜索所产生的结点序列（V3-2V1-V4-V5）7.在无向图中，若从顶点a到顶点b存在（路径），则称

5、a与b之间是连通的。8.我们通常把队列中允许删除的一端称为（队头）9.表头和表尾均为（a,(b,c)）的广义表L=（）10.假定对有序表：（3.4.5.7.24.30.42.54.63.72.87.95）进行折半查找，若查找元素24（程序设定为向下取整），需依次与（30.5.7.24）元素进行比较。三、解答（50分）1.二维数组A[10.20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[1.1]的存储地址为300，则请算A[10,10]的存储地址。答：300+（9*20+10）*4=300+1

6、90*4=300+760=10602.已知树如右图所示：（1）画出由该树转换得到的二叉树；原图答图：（2）写出该二叉树的后序序列：答：后序序列为：EBKJIHGFDCA3.试给出如图所示的邻接矩阵和邻接表表示。答：邻接矩阵4.已知某二叉排序树10个结点的值依次为1-10，其结构如图所示，试标出该二叉排序树各结点所对应的具体值。原图：答图：5.试构造下图的最小生成树，要求分步给出构造过程。原图：答图：1.2.3.4.6.从一个空的二叉排序树开始，依次插入关键字25.13.15.14.7.20.37试画出插入

7、关键字后的二叉排序树，并计算查找成功时的平均查找长度。averagesearchlength平均查找长度答：ASL=(1*1+2*2+3*3+4*1)/7=18/7主要思想是以第一个数为标准，将比此数小的放在左边，大的放在右边，再一一插入，通过比较，找到末端为止。如13比25小，便在左边，后15小于25，又在25左端，但是比13大，故放在了13的右边，每个数都是这样找到自己的位置的。7.为关键字（17.33.31.40.48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决

8、冲突的探查序列是Hi=(h(key)+(key%5+1))%70≤i≤6(1)画出构造所得的散列表；(2)求出在等概率情况下查找成功时的平均查找长度。答：ASL=(1+1+3+2+4)/5=11/5H(17)=17%7=3H(33)=33%7=5H(31)=31%7=3冲突？%=（3+1（31%5+1））%7=5%7=5冲突Hi=(3+2(31%5+1))%7=(3+4)%7=0H(40)=40%7=5冲突Hi=(5+1(40