公共基本知识练习.docVIP

公共基础知识练习 第一章 数据结构与算法（占10分） 1、下列叙述正确的是 A)算法就是程序?? B)算法强调的是利用技巧提高程序执行效率? C)设计算法时只需考虑结果的可靠性 D)以上三种说法都不对 算法不同于程序，算法优先于程序。算法强调的是程序的易读性。设计算法时需要考虑算法的时间复杂度和空间复杂度。 2、下列叙述中正确的是 A)在栈中，栈顶指针和栈底指针同时动态反映了栈中元素的变化情况? B)在队列中，队尾指针动态反映了队列中元素的变化情况 C)在栈中，栈顶指针动态反映了栈中元素的变化情况??????????????? D)在队列中，排头指针动态反映了队列中元素的变化情况 在栈中，只需要用栈顶指针来反应栈中元素的变化（栈只在在栈顶进行插入和删除元素，栈类似于垃圾桶）；在队列中，需要队头和队尾指针发应队列中元素的变化（队列在队头进行删除元素，在队尾插入元素） 3、下列叙述正确的是 A)顺序表是线性表的顺序存储结构???????????? B)在顺序表中，各元素的存储位置是连续的 C)在顺序表中插入一个元素，平时需要移动表中一半的元素??????? D)以上三种说法都对 4、下列数据结构中不属于存储结构的是 A)循环队列?????????????? B)二叉链表???????????????? C)循环链表?????????????? D)二叉树 5、具有记忆作用的数据结构是 A)队列 ????????????? B)栈????????? C)双向链表???????????????? D)二叉树 6、在最坏情况下，比较次数不是n(n-1)/2的排序方法是 A)快速排列 ?????????????? B)冒泡排序????????? C)直接插入排序 ???? D)堆排序 堆排序需要比较的次数为nlog2n 7、设有右图所示二叉树：对该二叉树进行中序遍历的结果为 A)ABCDEFXYZ???????? ? B)YDEBAFCXZ??? C)DYBEAFCZX ?????? ??D)BDYEACFXZ 8、算法的时间复杂度是指 A)执行算法程序所需要的时间???????????????????? B)算法执行过程中所需要的所有运算的次数 C)算法执行过程中所需要的基本运算次数??????????? D)算法程序中的指令条数 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。度量一个算法的工作量，可以用算法在执行过程中所需要基本运算的执行次数来度量。特别要注意：算法的时间复杂度不是算法程序所需要的执行时间。 另外，注意：评价一个算法的效率时与所用的计算机硬件配置、程序设计语言、程序设计者等等都无关。 9、深度为5的完全二叉树可能具有的结点数为 A)33 ??????? ?B)32???????? ? C)16 ????????????? ?D)15 对于这类的题目，画出这种满足条件二叉树即可。深度为5的完全二叉树具有的结点数为24～25－1 ――――――――――――――――――――――――――――――――――――――― 10、按“先进先出”原则组织数据的数据结构称为???? 队列??????? 。 11、若一棵完全二叉树共有950个结点，则该二叉树有?? 1??? 个度为1的结点。 12、设有下列二叉树：与上图一样 对该二叉树进行前序遍历的结果为?? ABDEYCFXZ??? 。 13、数据结构分为线性结构和非线性结构，循环链表属于? 线性结构???? 。 14、在一个长度为32的有序线性表中进行顺序查找，在最坏情况下需要比较 ?32 ?次。 ――――――――――――――――――――――――――――――――――――――― 1、算法的空间复杂度是指 A)算法程序中变量的个数? B)算法程序中的指令条数 C)算法程序中各控制变量所占的额外空间?? D)算法执行过程中所需要的存储空间 2、下列叙述中正确的是 A)线性链表是线性表的链式存储结构??? B)栈与队列是非线性结构? C)双向链表是非线性结构 D)只有根结点的二叉树是线性结构 3、数据的存储结构是指 A)数据所占的存储空间量?????????? B)数据的逻辑结构在计算机中的存放形式?? C)数据在计算机中的顺序存储方式???? D)存储在外存中的数据 4、下列关于队列的叙述中正确的是 A)只能在排头插入数据???????????????? B)只能在队尾删除数据???? C)队列按先进先出组织数据?????????? D)队列按先进后出组织数据 5、下列关于栈的叙述中正确的是 A)在栈定只能插入数据? B)在栈底只能删除数据???? C)栈按“先进先出”组织数据??? D)栈按“先进后出”组织数据 6、设有下列二叉树：对此二叉