北京师范大学12-13-数据结构试卷-A+答案

1、北京师范大学20122013学年第 1 学期期末考试试卷（A卷）课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 120 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2011 姓 名： 学 号： 题号第一题第二题第三题第四题总分得分阅卷教师（签字）： 装 订 线一、 单项选择题（每题2分，共10题20分）题号12345678910答案CADDDABBAC1 从逻辑上可以把数据结构分为 两大类。A 动态结构、静态结构 B 顺序结构、链式结构C 线性结构、非线性结构 D 初等结构、构造型结构2 在双向链表中，删除p所指的结点时修改指针_。Ap-

2、next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;3 已知二维数组A46采用列序为主序方式存储，每个元素占用4个存储单元，并且A34的存储地址为1234，元素A00的存储地址是（ ）。 A1322B1146C1310D11584 设树T 的度为4，其中度为1，2，3 和4 的结点个数分别为4，2，1，1 ，则T 中的叶子数为_。A5

3、B6C7D85 由3 个结点可以构造出多少种不同的二叉树？_。A2B3C4D56 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为_。ACBEFDABFEDCBACCBEDFAD不定7 为便于判别有向图中是否存在回路，可借助于_。A广度优先搜索算法B拓扑排序算法C最短路径算法D最小生成树算法 8 具有n个顶点的无向连通图至少含有的边数为( )。AnBn-1Cn+1D2n9 具有12 个关键字的有序表，折半查找的平均查找长度_。A. 3.1B. 4C. 2.5D. 510 用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排

4、序，记录序列的变化情况如下，则采取的排序方法是_。（25，84，21，47，15，27，68，35，20）（15，20，21，25，47，27，68，35，84）（15，20，21，25，35，27，47，68，84）（15，20，21，25，27，35，47，68，84）A直接选择排序B冒泡排序C快速排序D二路归并排序二、 判断（每题1分，共10题10分）题号12345678910答案1 顺序存储方式只能用于存储线性结构。2 栈和队列都是限制存取点的线性结构。3 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。4 稀疏矩阵压缩存储后，必会失去随机存取功能。

5、5 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。6 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。7 采用二叉链表作存储结构，树的先根序遍历和其相应的二叉树的先根序遍历的结果是一样的。8 用一维数组存储二叉树时，总是以先根序遍历顺序存储结点。9 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素个数之和的一半。10 Hash 表的平均查找长度与处理冲突的方法无关。三、 填空题（每题2分，共10题20分）1 已知指针 p 指向单链表L 中的某结点，则删除其后继结点的语句是： p-next = p-next-next; f

6、ree(p); 。2 表达式 a+(b*c-d)/e+f*g/h)+i/j 的后缀表达式是： abc*d-e/fg*h/+ +ij/+ 。3 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列的元素个数是： (rear front + m) % m 。4 广义表 A =（a，b），（c，d，e），取出A 中的原子e 的操作是： Head(Tail(Tail(Head(Tail(Head(A) 。5 在一棵二叉树中，度为零的结点的个数为n0,度为2 的结点的个数为n2,则有： n0 = n2 + 1 。6 高度为8 的完全二叉树至少有 26 = 64

7、 个叶子结点。7 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)，当用二分法查找90 时，需比较 2 次查找成功。8 非叶子结点最大深度为3 的3 阶B-树中，最多有 2+2*3+2*9 = 26 个关键字。9 高度为5（除叶子层之外）的 3 阶B-树中，至少有 31 个结点。10 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1，写出第一趟结束后，数组中数据的排列次序： 10，7，-9，0，47，23，1，8， 98， 36 。四、 简答题（每题5分，共10题50分）1 画出广义表（

8、a，b），（），c，（d）的存储结构图（采用头尾指针的链表结构，标志1表示表结点，标志0表示原子结点）0a10b0c0d11111112 已知树的先根序列和后根序列分别为 ABCEFGD 和 BEGFCDA，请画出该树对应的二叉树，并画出这棵树。ABCDEFG ABCDEFG3 设用于通信的电文由6个字母A，B，C，D，E，F组成,各个字母在电文中出现的频率分别为0.10，0.34，0.08，0.16，0.20，0.12，试填写下表构造赫夫曼树，为这8个字母设计哈夫曼编码，(同一层的左子树根权值小于右子树根权值)0.100.200.340.120.160.080.180.280.380.621

9、.000000011111B 11F 100D 101C 000A 001E 01字符weightparentlchildrchild1A0.107002B0.3410003C0.087004D0.168005E0.209006F0.1280070.1893180.28106490.381175100.621182111.000910字符ABCDEF编码00111000101011004 对下面的3 阶B-树，依次执行下列操作，画出各步操作的结果，（1）插入26 （2） 插入853 12 451002461 7053 9030 37503 12 4510024 3061 7053 903750

10、26 45 7010061 535085903 12 24 3037265 对如图的邻接表，从项点v2开始进行深度优先搜索，写出深度优先遍历时访问顶点的顺序，并画出相应的深度优先生成树。v1v2v3v4v5v6v7v8从项点v2开始进行深度优先遍历时访问顶点的顺序：v2-v4-v1-v8-v3-v6-v5-v76 求出下面AOE网的所有关键活动（列出所有顶点的最早发生时间ve、最迟发生时间vl，和所有活动弧的最早发生时间ee、最迟发生时间el）拓扑序列：146235789顶点vevl活动eeelV100a100V266a202V346a303V458a466V577a546V6710a658V

11、71516a778V81414a877V91818a9710a101516a111414关键活动：a1, a4, a8, a117 使用普里姆算法构造，在如图所示的图G中，从结点A开始构造图G的一棵最小生成树（画出每一步生成的子树）。ABCDEF812951615247A AC1 ACE14ACDE514 ACDEF5124 ABCDEF516248 已知散列表的地址空间为A0.11，散列函数 H（k）= k mod 11，采用平方探测法处理冲突。请将下列数据26,25,23,33,21,24,45依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。关键字26252333212

12、445哈希值43101021哈希地址01234567891011关键字33232425264521比较次数1111141等概率情况下查找成功时的平均查找长度： (1+1+1+1+1+4+1)/7=10/79 根据序列 31、19、23、45、63、15、57、9，建立一个大顶堆。（画出画出主要过程）453157196323159 453123196357159453123631957159 31632345195715910 给出一组关键字 T = (12，2，16，30，8，28，4，10，20，6，18)，设内存工作区可容纳4 个记录，写出用置换-选择排序得到的全部初始归并段。12，2，16，30，8，28，4，10，20，6，188，28，4，10，20，6，1812，2，16，3028，4，10，20，6，1812，8，16，3024，10，20，6，1812，28，16，302，810，20，6，184，28，16，302，8，1220，6，184，28，10，302，8，12