《2017年军事医学科学院实验仪器厂836计算机应用之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年军事医学科学院实验仪器厂836计算机应用之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年军事医学科学院实验仪器厂836计算机应用之数据结构考研强化模拟题一、填空题1 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 【答案】 【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。 2 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_。【答案】【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。3 在单链表L 中，指针P 所指结点有后继结点的条件是_【答案】 【解析】指针所指节点的指针域
2、所指向的元素非空，说明该指针所指节点有后继结点。4 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】视哨。 5 假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表第 2 页，共 33 页 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监中每个元素的概率相等，则进行折半查找时的平均查找长度为_ 平均查找次数为6 文件由_组成；记录由_组成。【答案】记录；数据项 7 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3
3、在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 8 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 第 3 页，共 33 页 9 一个算法具有5个特性：_、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性10二进制地址为011011110000，大小为【答案】011011110100；01
4、1011100000011011110000是块的起始地址，【解析】大小分别为式如下： 当大小为4时，起始地址为当大小为16时，起始地址为： 11根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。12在
5、一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。【答案】 【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以13已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）【答案】 中，其下标值最大的分支结点为_。 14设有个结点的完全二叉树顺序存放在向量【答案】 和其伙伴块的起始地址计算公和块的伙伴地址分别为：_【解析】最大的分支结点是最后一个叶子结点的父结点。15如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。【答案】69【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。第 4 页，共 33 页一、填空题考研试题
