《2017年南昌航空大学软件学院817数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南昌航空大学软件学院817数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌航空大学软件学院817数据结构考研强化模拟题一、填空题1 数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算）2 在有n 个顶点的有向图中，每个顶点的度最大可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。3 有向图G=（V ，E ）, 其中V （G ）=0, 1，2，3，4, 5, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= , , ， ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50; 4 4 高度
2、为h 的堆中，最多有_元素，最少有_个元素。【答案】 当最后一层只有 则后缀式的【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为5 中缀式对应的前缀式为_，若运算结果为_。【答案】 【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。 6 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：32, 311，221，2111, 11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 执行程序，f （6，4）=_
3、。 【答案】1; 1; f （m ，n 1）; n 9 7 n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所
4、有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。8 已知 求REPLACE （S ，V , m ）=_。【答案】 ；（“图有回路”） 9设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_;【答案】 10起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起
5、始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。二、选择题11图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图D.G 所有顶点的度的总和为n （n-1） 【答案】A【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。 12下列关于虚拟存储的叙述中，正确的是
6、（ ）。A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 【答案】D 。【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。 一、填空题考研试题
