在职研究生全国联考数据结构模拟试题.docx

一、选择题（20分，每题2分）1、学习数据结构主要目的是(　C　)。　　A、处理数值计算问题　　B、研究程序设计技巧　　C、选取合适数据结构，写出更有效的算法　　D、是计算机硬件课程的基础2、分块查找中确定块的查找采用的查找方法是（　D　）。　　A、顺序查找　　B、折半查找　　C、顺序查找、折半查找都可以　　D、顺序查找、折半查找都不可以3、在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找30需要进行（　D　）次比较。　　A、1　　　　　B、2　　　　　　C、3　　　　　D、44、当先后插入的关键字有序时，构成的二叉排序树蜕变成单支树。如果树的深度为n，其平均查找长度为（　D　）。　　A、n　　　　　B、n+1　　　　　C、n/2　　　　　D、(n+1)/25、已知序列{a,b,c,d}依次进入空栈，然后执行了2次出栈操作，则当前的栈顶元素是（　B　）。　　A、a　　　　　B、b　　　　　C、c　　　　　D、d6、已知长度为10的线性表采用顺序存储的方法，则插入或删除一个元素平均需要移动的元素个数为（　B　）。　　A、11　　　　　B、5　　　　　C、4　　　　　D、107、在下列选项中，使用顺序表比链表好的运算是（　C　）。　　A、插入　　B、删除　　C、根据序号查找　　D、根据元素值查找8、适合作为经常在首尾两端进行操作的线性表的存储结构的是（　C　）。　　A、顺序表　　　　　B、单链表　　　　　C、循环链表　　　　　D、双向链表9、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（　D　）。　　A、front=front+1　　　　　　　　　　B、front=(front+1)%(m-1)　　C、front=(front-1)%m　　　　　　　　D、front=(front+1)%m10、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(　D　)。　　A、e　　　　　B、2e　　　　　C、n2－e　　　　　D、n2－2e?二、填空题（10分，每空1分）1、讨论算法时间复杂度往往分析（最坏）情况下的时间复杂度。2、队列又称为（先进先出）线性表。3、顺序查找查找成功时的最坏比较次数为（n-1）和查找失败时的比较次数为（n）。4、设有64个元素，用折半查找方法进行查找时，最大比较次数是（7），最小比较次数是（1）。5、对不同的关键字可能得到同一哈希地址，即key1!=key2，而f(key1)=f(key2)，这种现象称为（冲突）。具有相同函数值的关键字对该哈希函数来说称作（同义词）。6、一棵深度为K且有2k-1个结点的二叉树称为（满二叉树）。7、在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在（元素的移动上）。?三、简答题（30分，每题5分）1、在AOE网中提高关键活动的速度应该注意什么？答：关键活动的速度提高是有限的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。　　若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。2、简述二叉排序树的定义。答：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：　　1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；　　2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；　　3、它的左、右子树也分别为二叉排序树。3、直接插入排序算法最坏的情况是哪种情况，并说明为什么该算法的时间复杂度为O(n2)。答：最坏的情况是记录按照关键字非递增有序排列。因为第i趟时第i个记录必须与前面i-1个记录都做关键字比较，并且每做1次比较就要做1次数据移动。则总的关键字比较次数KCN和记录移动次数RMN分别为：　　该算法的两个基本操作的频度都和n2有关。4、请比较快速排序和堆排序。答：可以得出的结论有：当待排序的结点个数 n较大时，则应该采用快速排序或堆排序。从平均排序速度来看，快速排序的速度最快，但在最坏情况下（待排序的结点序列已经几乎排好序），他的时间性能却很差。这时不如采用堆排序。但要注意快速排序和堆排序都是不稳定的。5、链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。6、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。　　链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以