浙江师范大学2008年计算机考研数据结构范例.doc

浙江师范大学2008年计算机考研数据结构试题数据结构一、判断题 用√和×表示对和错（每小题1.5分，共15分） ??? 1. 数据元素是数据的最小单位。? （× ） ??? 2. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。? （ ×） ??? 3. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。? （× ） ??? 4. 在树中，如果从结点K出发，存在两条分别到达K’，K”的长度相等的路径，则结点K’和k”互为兄弟。? （ √） ??? 5. 最佳两叉排序树的任何子树都是最佳的。? （ √） ??? 6. 算法和程序没有区别，所以在数据结构中两者是通用的。? （× ） ??? 7. 顺序存储方式只能用于存储线性结构。? （ ×） ??? 8. 在线性表链式存储结构中，? 逻辑上相邻的元素在物理位置上不一定相邻。? （√ ） ??? 9. 如果某种排序算法是不稳定的，则该算法没有实际意义。? （ ×） ??? 10. 当两个字符出现的频率相同时，则其哈夫曼编码也相同。? （× ） 二、单项选择题（每小题3分，共60分） ??? 1. 某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是______。 ??? A.110??? B.108??? C.100??? D.120 ??? 2. 栈和队列的共同特点是______。 ??? A.都是先进后出??? B.都是先进先出?? C.只允许在端点处插入和删除元素??? D.没有共同点 ??? 3. 对线性表进行二分查找时，要求线性表必须______。 ??? A.以顺序方式存储??? B.以链接方式存储??? C.以顺序方式存储，且结点按关键字有序排序??? D.以链接方式存储，且结点按关键字有序排序 ??? 4. 一组记录的排序码为（47、78、61、33、39、80），则利用堆排序的方法建立的初始堆为______。 A.78、47、61、33、39、80??? B.80、78、61、33、39、47??? C.80、78、61、47、39、33??? D.80、61、78、39、47、33 ??? 5. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点______。 ??? A.无左、右孩子??? B.有左孩子，无右孩子??? C.有右孩子，无左孩子??? D.有左、右孩子 ??? 6. 用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下的时间复杂度为______。 ??? A.O（n）??? B.O（log2n）??? C.O（nlog2n）??? D.O（n2） 7. 在最坏的情况下，查找成功时二叉排序树的平均查找长度______。 ??? A.小于顺序表的平均查找长度??? B.大于顺序表的平均查找长度??? C.与顺序表的平均查找长度相同??? D.无法与顺序表的平均查找长度比较 ??? 8. 对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下： （18，12，19，22，49，30，65，35，86） ，则可以认为使用的排序方法是______。 ??? A.选择排序??? B.冒泡排序??? C.快速排序??? D.插入排序 ??? 9. 在线性表的下列存储结构中，读取元素花费时间最少的是______。 ??? A.顺序表??? B.双链表??? C.循环链表??? D.单链表 ??? 10. 具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余______个指针域为空。 ??? A.50??? B.99??? C.100??? D.101二叉树指针??? 11. 从逻辑上可以把数据结构划分为______。 ??? A.动态结构和静态结构??? B.紧凑结构和非紧凑结构??? C.线性结构和非线性结构??? D.内部结构和外部结构 ??? 12. 以下数据结构中属于非线性结构的是______。 ??? A.树??? B.字符串??? C.队列??? D.栈 13. 在单链表中，若*P节点不是最后节点，在*P之后插入节点*S，则其操作是______。 ??? A.s-next=p;p-next=s;??? B.s-next=p-next;p-next=s;??? C.s-next=p-next;p=s;??? D.p-next=s;s-next=p; ??? 14. 栈是一种操作受限的数据结构，其插入和删除必须在______进行。 ??? A.栈顶??? B.栈底??? C.任意位置??? D.指定位置 ??? 15. 设T为一颗深度为6的二叉树，则T拥有的最多结点数是_