《2017年北方民族大学计算机系统结构832C语言程序设计与数据结构之数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北方民族大学计算机系统结构832C语言程序设计与数据结构之数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北方民族大学计算机系统结构832C语言程序设计与数据结构之数据结构考研仿真模拟题一、填空题1 高度为h 的堆中，最多有_元素，最少有_个元素。【答案】 当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为 2 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：32, 311，221，2111, 11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 执行程序，f （6，4）=_。 【答案】1; 1; f （m
2、 ，n 1）; n 9 3 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储4 已知二维数组为1000的连续存储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为：5 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_; 对于有向图来说等于该顶点的_。【答案】度；出度第 2 页，共 42 页中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_。 6 在下面的程序段中，
3、对X 的赋值语句的时间复杂度为_（表示为n 的函数）。 【答案】1（12）（123）?（l 2. n ）=n（n 1）（n 2）/6，即 【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了12次。当i=3时，赋值语句被执行了123次。可以推出赋值语句总共被执行了1（12）（123）（l 2. n ）=n（n 1）（n 2）/6次。7 空格串是指_，其长度等于_。【答案】由空格字符（值32）所组成的字符串；空格个数 8 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。9 对于双向链表，在两个结点之
4、间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2 10n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） .； （“图有回路”）第 3 页，共 42 页 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegreei=0【解析
5、】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 二、判断题11拓扑排序的有向图中，最多存在一条环路。（ ）【答案】【解析】要进行拓扑排序，需要满足一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在 顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件, 所以拓扑排序的有向图中不能存在环路。 12对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到
6、的序列的顺序却是一致的。（ ）【答案】，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，所以顺序是一致的。 13循环队列也存在空间溢出问题。（ ）【答案】 【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。 14倒排文件的目的是为了多关键字查找。（ ）【答案】【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。 15串是一种数据对象和操作都特殊的线性表。（ ）【答案】【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。 16若一个有向图无环，则它一定有唯一的拓扑序列。（ ）【答案】【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序第 4 页，共 42 页 一、填空题考研试题
