《数据结构与算法-考试范围题与答案like》由会员分享，可在线阅读，更多相关《数据结构与算法-考试范围题与答案like（6页珍藏版）》请在金锄头文库上搜索。
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 之前插入结点*s 4. 栈和队列都是（C:链式存储的线性结构）A:限制存取位置的
2、线性结构B:顺序存储的线性结构C:链式存储的线性结构D:限制存取位置的非线性结构5.下列关于线性表的基本操作中，属于加工型的操作是（B初始化、插入、删除操作）6.根据定义，树的叶子结点其度数（B.必等于 0）7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（A.数组的元素处在行和列两个关系中）8.从广义表LS= （ （ p,q）,r,s）中分解出原子q 的运算是 (B. head(tall(head (LS) 9.在具有 n 个叶子结点的满二叉树中，结点总数为（C. 2n-1）10.若是有向图的一条边，则称（D. Vi 与 Vj 不相邻接）11.二叉树若采用二叉链表结构表示，则对于
3、n 个结点的二叉树一定有（B. 2n 个指针域其中n+1 个指针为NULL）12.在一个无向图中，所有顶点的度数之和等于边数的（B. 2倍）13. 一个含 n 个顶点和e 条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（A.O(n)）14.散列法存储中出现的碰撞（冲突）现象指的是（B.不同关键码值对应到相同的存储地址）15.循环链表适合的查找方式是（A. 顺序）二、填空（ 20 分）1.若一棵完全二叉树中含有121 个结点，则该树的深度为（7）2.若以邻接矩阵表示有向图，则邻接矩阵上第i 行中非零元素的个数之和即为顶点Vi 的。3.二叉树的遍历主要有先序遍历
4、、后序遍历和（中序遍历）三种。4.深度为 3 的完全二叉树至少有（ 4）个结点。5.若图的邻接矩阵是一个对称矩阵，则该图一定是一个（无向图）6.若某无向图G的邻接表如下图所示， 试给出以顶点V3为出发点，按广度优先搜索所产生的结点序列（ V3-2V1-V4-V5 ）V1 V2V3 V4V5V2 V1V1V1 V1V3V3 V3V4V4V4V5V5V57.在无向图中，若从顶点a 到顶点 b 存在 （路径），则称 a 与 b 之间是连通的。8.我们通常把队列中允许删除的一端称为（队头）9.表头和表尾均为（ a,(b,c)）的广义表L=（）10.假定对有序表： （ 3.4.5.7.24.30.42.
5、54.63.72.87.95 ）进行折半查找，若查找元素24（程序设定为向下取整），需依次与（30.5.7.24）元素进行比较。三、解答（ 50 分）1.二维数组A10.20 采用按行为主序的存储方式，每个元素占4 个存储单元， 若 A1.1的存储地址为300， 则请算 A10,10的存储地址。答： 300+（9*20+10 ） * 4=300+190*4=300 +760=1060 2.已知树如右图所示：（1）画出由该树转换得到的二叉树；原图ADBEFGHIJKC答图：ABCDEFJGKHI（2）写出该二叉树的后序序列：答： 后序序列为：E B K J I H G F D C A 3. 试给
6、出如图所示的邻接矩阵和邻接表表示。V1V2V5V4V32 13784116答：邻接矩阵000130001170000000080006420AV1V2V3V4V5223 82 72 13 123453 44 6311邻接表4.已知某二叉排序树10 个结点的值依次为1-10，其结构如图所示，试标出该二叉排序树各 结点所对应的具体值。原图：答图：654732911085.试构造下图的最小生成树，要求分步给出构造过程。原图：V1V2V5V4V32784 6 55答图：1.V1V2V5V4V322.V1V2V5V4V3253.V1V2V5V4V32554.V1V2V5V4V326556.从一个空的二叉
7、排序树开始，依次插入关键字25.13.15.14.7.20.37 试画出插入关键字后的二叉排序树，并计算查找成功时的平均查找长度。average search length平均查找长度答： ASL=(1*1+2*2+3*3+4*1)/7=18/7 2534720153713主要思想是以第一个数为标准，将比此数小的放在左边，大的放在右边， 再一一插入， 通过比较， 找到末端为止。如 13 比 25 小，便在左边，后15 小于 25，又在 25 左端，但是比13 大，故放在了13 的右边，每个数都是这样找到自己的位置的。7. 为关键字（ 17.33.31.40.48）构造一个长度为7 的散列表，设
8、散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是Hi=(h(key)+(key%5+1)%7 0i 6 (1) 画出构造所得的散列表；(2) 求出在等概率情况下查找成功时的平均查找长度。答：ASL=(1+1+3+2+4)/5=11/5 H(17)=17%7=3 H(33)=33%7=5 H(31)=31%7=3 冲突？%= （ 3+1 （ 31%5+1 ） ）%7 =5%7=5 冲突Hi=(3+2(31%5+1)%7 =(3+4)%7=0 H(40)=40%7=5 冲突Hi=(5+1(40%5+0)%7 =6%7=6 H(48)=48%7=6 冲突Hi=(6+1(48%5+
9、1)%7 =(6+4)%7=3 冲突Hi=(6+2(48%5+1)%7 =(6+8)%7=0 冲突Hi=(6+3(48%5+1)%7 =(6+12)%7 =18%7 =4 0 1 2 3 4 5 6 31 17 48 33 40 8. 顶点C出发进行深度优先遍历的序列。原图：ABCDE2 070 111 205 14123454 150F3 081 091 115 092 081 150 074 143 20 邻接点权值链域答：CDABFE ACDEFB87119 151420完1. 已知一棵树边的集合为 ， ， ， ， ， ， ，请画出这棵树，并回答下列问题：（ 1 ）哪个是根结点？（ 2
10、）哪些是叶子结点？（ 3 ）哪个是结点g 的双亲？（ 4 ）哪些是结点g 的祖先？（ 5 ）哪些是结点g 的孩子？（ 6 ）哪些是结点e 的孩子？（ 7 ）哪些是结点e 的兄弟？哪些是结点f 的兄弟？（ 8 ）结点 b 和 n 的层次号分别是什么？（ 9 ）树的深度是多少？（ 10 ）以结点 c 为根的子树深度是多少？ 1. 解答：根据给定的边确定的树如图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
11、的兄弟；结点 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 。答案第一题 :列序存储 ,则 A612 的地址的 A00 的地址加上 “12*10+6“=200+126=326 (行序是6*20+12) 第二题 :行序存储 ,A189=A105+(8*6+4)*4=1000+208=1208; A10.205.10等同于 A116 然后已知A00 的地址为1000 ，求 A84 的地址，注意每个元素占4 个存储单元了需要乘上4
