《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研强化模拟题一、填空题1 在有n 个顶点的有向图中，每个顶点的度最大可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。2 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）【答案】 3 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。4 空格串是指_，其长度等于_。【答案】由空格字符（值32）所组成的字符串；空格个数 5 对于双向链表，在两
2、个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2 6 中缀式运算结果为_。【答案】 【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。7 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为8 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为若对应的前缀式为_
3、，若则后缀式的，）则 的地址为_。则的地址为9 在一棵m 阶的个数是_。【答案】将代入得33。树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字 最少 【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是10阅读下列程序说明和裎序，填充程序中的_。本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）存放还没有转换过的结点，它的栈顶指针为。（2）当堆栈不空时，取出栈顶元素，交换
4、它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 11执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储12设数组储，则元素为_。【答案】9174；8788的基地址
5、为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_；若以列序为主序顺序存储，则元素的存储地址【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 二、选择题13对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。 A.4B.3 C.2 D.1【答案】B【解析】拓扑排序的步骤为：（1）在有向图中选一个没有前驱的顶点并且输出它；（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。 14下列网络设备中，能够抑制广播风暴的是（ ）。 中继器集线器网桥路由器 A. 仅和 B. 仅D. 仅 C. 仅和【答案】D【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。 一、填空题考研试题
