《2017年中国传媒大学计算机学院821数据结构与计算机网络考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年中国传媒大学计算机学院821数据结构与计算机网络考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年中国传媒大学计算机学院821数据结构与计算机网络考研导师圈点必考题汇编一、填空题1 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定 2 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元
2、素的编号，动态链表的指针指向下一个元素的物理位置。3 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串）4 从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。5 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 6 VSAM （虚拟存储存取方法）文件的优点是：动态地_，不需要文件进行_，并能较快地_进行查找。【
3、答案】分配和释放存储空间；重组；对插入的记录7 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度【答案】完全；只有一个叶结点的二叉树 8 当广义表中的每个元素都是原子时，广义表便成了_。【答案】线性表【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。 9 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量；10线性表【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为11起始地址为480，大小为8的块，其伙伴块的起始地
4、址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。 12设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为 将代入得33。则的地址为若，）则 的地址为_。二、选择题13在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）A.5 B.7 C.8 D.14【答案】A【解析】根据B 树的定义可知，跟结点最少含有个关键
5、字，高度为2的阶B树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。14y 的机器数分别为某字长为8位的计算机中，已知整型变量x 、若整型变量A.11000000 B.00100100 C.10101010 D. 溢出【答案】Ay 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。 15下列介质访问控制方法中，可能发生冲突的是（ ）A.CDMA B.CSMA C.TDM AC D.FDMA 【答案】B 【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。16下列选项中，描述浮点数操作速度指标的是（ ）。A.MIPS B.CPI C.IPCD.MFLOPS则z 的机器数为（ ）一、填空题考研试题
