《2018年华东交通大学信息工程学院829数据结构考研基础五套测试题.doc》由会员分享，可在线阅读，更多相关《2018年华东交通大学信息工程学院829数据结构考研基础五套测试题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年华东交通大学信息工程学院829数据结构考研基础五套测试题一、填空题1 实现字符串拷贝的函数strcpv 为: (_) 【答案】s+*t+或(*s+*t+)!0?2 棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。3 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11l) ， 则a 85的地址为_。【答案】33【解析】设存储的元素的行标为i ，列标为j 。若i j ，则的地址为l 2. i l ji(il)/2j 。若i j 。
2、则的地址为j(jl)/2i 。将i 8，j 5代入得33。 4 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32, 则其伙伴块的起始地址为_; 。【答案】480+8=488，48032=448【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下: 根据上述公式起始地址就为488。5 在基于关键字比较且时间为【答案】归并；堆 6 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储_ 的排序中，若要求排序是稳
3、定的，则可选用_排序；若要求就地排序(及辅助空间为O(1)，则可选用_排序。7 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_个结点。【答案】 【解析】哈夫曼树只有度为0和2的节点。8 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 a 中存放待排序的关键字 【答案】 【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 9 堆是一种有用的数据结构。堆排序是一种_排序，堆实质上是一棵_结点的层次序列。对含有N 个元素的序列进行排序时
4、，堆排序的时间复杂度是_，所需的附加存储结点是_。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_ 。【答案】选择；完全二叉树；10在哈希函数；O(1)；满足堆的性质中，p 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 二、单项选择题11某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是为, 读取一个4KB 的扇区所需平均时间约为（ ）A.9ms B. C.
5、12ms D. 【答案】B【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB扇区信息的时间为。 12次总线事物中, 主设备只需给出一个首地址, 从设备就能从首地址开始的若干连续单元格读出或写入的个数, 这种总线事务方式称为（ ）A. 并行传输 B. 串行传输 C. 突发 D. 同步 【答案】C【解析】猝发数据传输方式:在一个总线周期内传输存储地址连续的多个数据字的总线传输方式 13已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。A.1 B.2 C.4 D.5【答案】B【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。 (1)为原堆, (2)为插入18后, (3)比较10与18, 交换后,(4)比较25与18, 不交换, 即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。, 信息延迟的时间为0.2ms ,总时间为, 磁盘控制器延迟一、填空题考研试题
