《2017年北京语言大学语言智能与技术825数据结构与程序设计考研题库.doc》由会员分享，可在线阅读，更多相关《2017年北京语言大学语言智能与技术825数据结构与程序设计考研题库.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年北京语言大学语言智能与技术825数据结构与程序设计考研题库一、填空题1 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】视哨。2 假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表 平均查找次数为 3 棵有个结点的满二叉树有_个度为1的结点、有_个分支（非终端）结点和_个叶子，该满二叉树的深度为_。【答案】或 【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。4 在一棵m阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若
2、在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。【答案】 【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是最少 5 设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_。【答案】15 【解析】当 时，而，时， 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监中每个元素的概率相等，则进行折半查找时的平均查找长度为_6 数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算） 7 如果按关键码值递増的顺序依次将关键码值插入
3、到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_。【答案】 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为 8 遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。9 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索
4、和_检索。【答案】关键字；记录号；记录号；顺序；直接10二叉树的前序序列和中序序列相同的条件是_。【答案】空树或任何结点至多只有右子树的二叉树【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。 11属于不稳定排序的有_。【答案】希尔排序、简单选择排序、快速排序、堆排序等12二进制地址为011011110000，大小为【答案】011011110100；011011100000011011110000是块的起始地址，【解析】大小分别为式如下： 当大小为4时，起始地址为 13设有个结点的完全二叉树顺序存放在向量【答案】 和块的伙伴地址分
5、别为：_ 和其伙伴块的起始地址计算公当大小为16时，起始地址为：中，其下标值最大的分支结点为_。【解析】最大的分支结点是最后一个叶子结点的父结点。14对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2 15己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 二、判断题16对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找
6、成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）【答案】【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。 17二维以上的数组其实是一种特殊的广义表。（ ）【答案】【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。 18深度为k 的二叉树中结点总数小于等于【答案】【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为19排序算法中的比较次数与初始元素序列的排列无关。（ ）【答案】【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。 （ ） 一、填空题考研试题
