《公共基础知识分类整理二零一六年-二零一六年（改）》.doc

软件基础真题 选择题 一.数据结构与算法 1、算法 （1）算法的时间复杂是指(?? )A.算法的执行时间??????????????? B.算法所处理的数据量C.算法程序中的语句或指令条数??? D算法在执行过程中所需要的基本运算次数算法的空间复杂度是指（??）。 A.算法在执行过程中所需要的计算机存储空间??? B.算法所处理的数据量 C.算法程序中的语句或指令条数???????D.算法在执行过程中所需要的临时工作单元数 解析:算法的空间复杂度是指执行算法所需要的内存空间,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间. 下列叙述中正确的是()A.算法的效率只与问题的规模有关，而与数据的存储结构无关 B.算法的时间复杂度是指执行算法所需要的计算工作量 C.数据的逻辑结构与存储结构是一一对应的 D.算法的时间复杂度与空间复杂度一定相关 下列叙述中正确的是 （　　） 。A.一个算法的复杂度大，则其复杂度也必定大B.一个算法的空间复杂度大，则其时间复杂度必定小 C.一个算法的时间复杂度大，则其空间复杂度必定小 D.上述三种说法都不对 下列数据结构中，属于非线性结构的是（???? ）。 A.??循环队列 B.带链队列 C.二叉树? D.带链栈 解析 树均是非线性结构（）下列关于栈叙述正确的是　　A 栈顶元素最先能被删除 　　B栈顶元素最后才能被删除 　　C栈底元素永远不能被删除 　　D以上三种说法都不对 下列数据结构中,能够按照先进后出原则存取数据的是（???? ）。 A..循环队列 B.栈? C.队列 D.二叉树（1）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A.12345ABCDE B.EDCBA54321 C .ABCDE12345 D.54321EDCBA 解析:栈是先进后出或后进先出的线性表下列叙述中正确的是 A.栈是先进先出的线性表 B队列是先进后出的线性表 C循环队列是非线性结构 D有序线性表即可以采用顺序存储结构也可以采用链式存储结构?下列对队列的叙述正确的是() A.队列属于非线性表 B.队列按先进后出原则组织数据 C.队列在队尾删除数据 D.队列按先进先出原则组织数据 对于循环队列下列叙述中正确的是（??? ）。 A.队头指针是固定不变的 B.队头指针一定大于队尾指针 C.队头指针一定小于队尾指针 D.队头指针可以大于队尾指针，也可以小于队尾指针 解析:如果队头指针大于队尾指针说明队列已经循环存放数据了,如果队头指针小于队尾指针说明没有进行循环存放（）下列叙述中正确的是A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反应队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反应队列中元素的动态变化情况D.循环队列中元素的个数是由队头和队尾指针共同决定（）下列叙述中正确的是()A.对长度为n的有序链表进行查找，最坏情况下需要比较次数为nB.对长度为n的有序链表进行对分查找，最坏情况下需要比较次数为（n/2）C.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数（log2n）D.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数（nlog2n）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）。　　A63 　　B64 　　C6 　　D7 （19）下列排序方法中最坏情况下比较次数最少的是A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是A. O(N) B. O(n2) C. O(log2n) D. O(n log2n) （）下列叙述中正确的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间A.顺序存储的有序线性表 B.线性链表 C.二叉链表 D.有序线性链表 （33）下列关于栈的描述正确的是（2005年秋） A.在栈中只能插入元素而不能删除元素 B.在栈中只能删除元素而不能插入元素 C.栈是特殊的线性表，只能在一端插入或删除元素 D.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 （34）下列叙述中正确的是（2005年秋） A.一个逻辑数据结构只能有一种存储结构 B.数据的逻辑结构属于线性结构，存储结构属于非线性结构 C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D.一个逻辑数据结构可以有多种存储结构，