电子科大820 计算机专业基础 (2016)真题.pdf

所需积分/C币:20 2019-11-15 348KB PDF
评分

电子科大820 计算机专业基础 (2016)真题 一、填空题(10 分,每空 2 分) 1. 若信号量S的初值为4,当前有6个进程在等待信号量S,则当前信号量S的值为 。 2. 某系统中共有 11 台打印机,X 个进程共享此打印机,每个进程最多请求使用 3 台打印 机,则该系统中不会发生死锁的最大 X 值是 。 3. 虚拟存储管理系统的基础是程序的 理论。 4. 为满足 264地址空间的作业运行,采用多级分页存储管理方式,假设页面大小为 4KB,
《数据结构》 、填空题共空,每空分,共分 顺序表采用的是 存取方式,线性链表采用的是 存取方式 深度为的完全二叉树至少含有 个节点,至多含有 个节点。 个节点构成的二叉树有种不同形状。个元素依次入栈可能的出栈序列有种。 无向连通图含有个节点条边。求的最小生成树,采用算法的时间复杂度 是 ,采用 算法的时间复杂度是 快速排序算法平均情况下的时间复杂度是 空间复杂度是 二、单选题共题,每题分,共分 循环队列为了防止假上溢采用取模运算折叠空间,解决队头队尾指针同指一个单元时候 空满判定门题,下列选项不是常见的方案。 牺牲一个存储空间改置一个计数器改置一个布尔变量再配置一个指针 列选项中不属」规则矩阵的是 三角矩阵 对称矩阵 对角矩阵 稀疏矩阵 下列选项中符合前缀码要求的是 下列关于哈大曼树的论述不正确的是 哈大曼树又被称为最优叉树 哈夫曼树是带权路径最短的二叉树 棵哈夫曼树仟意交换左右子树仍然是一棵哈弗曼树 对给定的输入数值集合所生成的哈夫曼树深度是确定的 无向图做深度优先搜索和广度优先搜索共有的特点是 都是递归类算法都必狈用到栈都是遍历类算法搜索结耒都是唯一的 对」网络,若它的关键路径存在,那么该路径一定是 最长路径 最短路径拓扑排序序列唯一的一条咯径 拓扑排序解决的问题是 对一个有向图进行遍历操作计算一个有向图的回路个数 判断一个有向图是否有回路 对一个有向图进行线索化 已知广义表 定义取表头函数为,取表尾函数为,那么 从中取出数据元素的操作是 对序列 进行折半查找元素,需要依次比较 第页共页 下列哪种排序算法在一趟过后不能保证至少有一个元素落在最终位置上的是 冒泡排序 希尔排序 快速排序 简单选择排序 简答题共题,每题分,共分 设计一种尽可能高效的策略使得单循环链表成为队列,给出入队和出队的时间复杂度。 输入数据序列为 ,请按输入序构造排序二叉树,并绞制出它的中序线索。 输入数据序列为 ,请按输入序构造平衡二叉树。给出每添加一个节 点后平衡二叉树的调整结果 L知输入关键字序列为 根据哈希函数建立哈希表,采用公 共溢出区法解决冲突。凵知哈希函数为 ,哈希表长为,溢出表长 为。请画岀哈希表和溢岀表,并计算査找成功时等枇率情况下的平均査找长度。 已知项数据记录为 。将它调整成为小顶堆,给出筛选过程 全源最短路径问题采用算法进行求解。下面给出了一个由个顶点构成的有向图 邻接矩阵Dist[4][4J和路径矩阵Path[4][4]。约定中用∞表示不能到达 用表示没有前驱的情况。请计算并给出每一次迭代的结果。请将答案誊写在答题纸上 四、算法题共题,共分 设规模 ≥的顺序表存储在维数组 int array[n]中,它含有的元素为 请编写算法将上述顺序表改造成为 ,要求时间复杂度和空间复杂度尽可能低。程序 设计语言可以选用 分 叉树用二叉链表结构进行存储。请编写算法求二叉树根节点左仁子树相隔最远的叶子 节点之间距离。程序设计语言可以选用 分 第页共页

...展开详情
立即下载 最低0.43元/次 身份认证VIP会员低至7折
举报 举报 收藏 收藏
分享
img
木子川

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐