数据结构(计算机科学与技术).pdf

数据结构(计算机科学与技术) . 《数据结构》（计算机科学与技术本科） 第一部分 客观题 一、单项选择（每题 2 分，共 20 分） 1、设 n 为正整数。则下面程序段的时间复杂度为________ 。 k=0; for(i=1;i=n;i++) for(j=i;j=n;j++) k++; A.O(1) B. O(n) C. O(nlogn) D. O(n2) 2、若在线性表的任何位置上插入元素的概率是相等的，那么在长度为 n 的顺 序表中插入一个元素时需平均移动________个元素。 A. n B. (n-1)/2 C.n/2 D. (n+1)/2 3、栈的入栈序列是 1，2，…，n，输出序列为 p1,p2,…pn,若 p1=n, 则 pi 为_____ 。 A. i B. n-i C. n-i+1 D. 不确定 4 、已知串 s=ABCDEFGH’,则 s 的所有不同子串的个数为________ 。 A. 8 B. 9 C. 36 D. 37 5、下列关于二叉树的说法中，正确的是_______ 。 A. 二叉树的度为 2 B. 二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2 D. 二叉树中任一个结点的度都为 2 6、图的深度优先遍历算法类似于二叉树的_____ 。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 7、用链地址法处理冲突构造的散列表中，每个地址单元所的同义词表中结点的 _____相同。 . 数据结构(计算机科学与技术) . A. 关键字 B. 元素值 C. 散列地址 D. 含义 8、有序表（1，32，41 ，45 ，62，75，77，82，95，100），使用折半查找关键 字为 95 的元素时，需要经过____次比较后才能查找成功。 A. 2 B. 3 C. 4 D.5 9、下列方法中，________是稳定的排序方法。 A ．堆排序 B. 希尔排序 C. 快速排序 D. 直接插入排序 10、对 n 个记录的序列进行堆排序，最坏情况下的时间复杂度为______ 。 A. O(logn) B. O(nlogn) C. O(n) D.O(n2) 二、是非题：（每题 1 分，共 10 分）（说明：正确的选“A”,错误选“B” ） 11、在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。 （B） 12、在不带头结点的非空单链表中，首元结点的存储位置由头指针指示。（ B ） 13、队列是限定在队尾插入元素，在队头删除元素的线性表。（ A ） 14、空串和空格串是相同的。（A ） 15、在哈夫曼树中，通常权值较大的结点离根较远。（ B ） 16、若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该 图一定是连通图。（A ） 17、有 n 个顶点和 n-1 条边的无向图一定是生成树。（ B） 18、折半查找时，要求线性表必须是有序的且以顺序结构存储。（ A ） 19、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。 （B ） 20、对一个堆按层次遍历，不一定能得到一个有序序列。（ A ） . 数据结构(计算机科学与技术) . 第二部分 主观题 一、简答题（每题 10 分，共 50 分） 1、在快速排序过程中，通常取序列中的第 1 个记录作为枢轴，以它为“分界线” 重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕 化为起泡排序，为改进之，应如何选取枢轴记录？ 答有序或者基本有序时，每次划分只能完成 1 个（左右），时