(2011级数据结构试卷A.docVIP

一、单选题：（每题1.5分，共30分） 以下函数增长率最大的是 (3/2)n B、n C 、log2n D、 n! 2、设某算法与问题规模的函数关系为f(n)=5000n3.5+nlogn，则使用大O表示法，其时间复杂度可表示为： A、O(n) B、O(5000) C、O(nlogn) D、O(n3.5) 3、在具有n个单元的顺序储存的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为__( ) A、 rear%n=front B、 (front+1)%n=rear C、 rear%n-1=front D、 (rear+1)%n=front 4、 下列陈述中正确的是（ ） A、二叉树是度为2的有序树 B、二叉树中结点只有一个孩子时无左右之分 C、 二叉树中必有度为2的结点 D、 二叉树中最多只有两棵子树，并且有左右之分 5、 一个顺序表第一个元素存储的地址是100，每个元素的长度为2，则第五个元素的地址是：( ) A、110 B、108 C、100 D、120 6、在单向循环链表中，若头指针为first，那么p所指结点为尾结点的条件是（ ） A、p=NULL B、p.next=NULL C、p=first D、p.next=first 7、若要在O（1）的时间复杂度上实现两个单向循环链表头尾相接，则应对两个单向循环链表各设置一个指针，分别指向（ b ） A、各自的头结点 B、各自的尾结点 C、各自的第一个元素结点 D、一个表的头结点，另一个表的尾结点 8、与线性表的链接存储不相符合的特性是（ ） A、便于插入、删除操作 B、存贮空间动态分配 C、需要连续的存贮空间 D、只能顺序查找 9、 在待排序的元素序列基本有序的前提下，以下排序方法中效率最高的是( ) A、起泡排序 B、堆排序 C、快速排序 D、归并排序 10、线性表L =（a, a, ．．．, a）,下列说法正确的是：__________ A、每个元素都有一个直接前驱和直接后继 B、线性表中至少要有一个元素 C、表中诸元素的排列顺序必须是由小到大或由大到小的 D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 11、若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种出栈序列不可能得到？（ ） A、ABCDE B、EDCBA C、BAEDC D、ECDBA 12、以下说法错误的是 ( ) A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点 C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 13、设二叉树的根为第1层，则高度为k的二叉树最大结点数有（ ） A、2k B、2k－1 C、2k-1 D、2k-1－1 14、在以下排序方法中，关键字比较的次数与记录的初始排列次序无关系的是（） A、希尔排序 B、起泡排序 C、直接插入排序 D、归并排序 15、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 （ ） A、 4 B、 5 C、 6 D、 7 16、 按照二叉树的定义，具有3个结点的二叉树有( ) 种形态 A、3 B、4 C、5 D、6 17、一棵二叉树的顺序存储结构如下，空值表示不存在该结点： 2 3 7 12 10 11 17 5 30 21 则值为7的结点的右孩子的值为____________。 A、11 B、17 C、 不存在 D、 5 18、 折半查找要求静态查找表的存储形式为( ) A、有序、链接存储 B、有序、顺序存储 C、无序、链接存储 D、无序、顺序存储 19、以下排序方法中，（ ）是一种不稳定的排序方法 。 A、 直接选择排序 B、冒泡排序 C、 快速排序 D、直接插入排序 20、在一个单链表中，结点结构为(data , link)，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。 A、q一link=p一link；p=q； B、p一 link =q一 link；q=p； C、q一 link =p一 link；p一 link =q； D、 p一 link =q一