数据结构复习题及答案(12级).doc

一、选择题。(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为_A_。A.数据 B.数据元素 C.数据结构 D.数据类型(2) 数据结构通常是研究数据的_ A _及它们之间的联系。A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑(3) 不是数据的逻辑结构是_ A _。A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为,其中D是_ B _的有限集，R是_ C _的有限集。A.算法 B.数据元素 C.数据操作 D.逻辑结构(5) 组成数据的基本单位是_ A _。 A.数据项 B.数据类型C.数据元素 D.数据变量(6) 设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是_ A _。A.线性结构 B.树型结构 C.图型结构 D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_ C _。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为_ A _。A.内部结构与外部结构 B.静态结构与动态结构C.线性结构与非线性结构 D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下_ B _方面的内容。A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度(10) 算法分析的两个方面是_ A _。A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性(11) 线性表是具有n个_ C _的有限序列（n0)。A.表元素 B.字符 C.数据元素 D.数据项(12) 线性表的存储结构是一种_ B _的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.HASH存取(13) 在一个长度为n 的顺序表中，向第i个元素（1 i n）之前插入一个新元素时，需要向后移动_ B _个元素。A.n-i B.n-i+1 C.n-i-1 D.i(14) 链表是一种采用_ B _存储结构存储的线性表；A.顺序 B.链式 C.星式 D.网状(15) 下面关于线性表的叙述错误的是_ D _。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现(16) 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为_ B _。A. s-next=p-next；p-next=-s；B. q-next=s； s-next=p；C. p-next=s-next；s-next=p；D. p-next=s；s-next=q；(17) 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为_ A _。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p(18) 下列说法哪个正确？_ D _A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表(19) 栈和队列的共同点是_ C _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点(20) 栈与一般线性表的区别主要在_D_。A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置(21) 链栈与顺序栈相比，比较明显的优点是_D_。A、插入操作更加方便 B、删除操作更加方便C、不会出现下溢的情况 D、不会出现上溢的情况(22) 以下数据结构中哪一个是非线性结构_ D _。A.队列B.栈C.线性表D.二叉树(23) 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_ C _。A. iB. B. n=i C. n-i+1D.不确定(24) 当利用大小为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行_ B _语句修改top指针。A. top+ B. top- C. top=0D. top(25) 4个元素进S栈的顺序是A,B,C,D，经运算POP(S)后，栈顶元素是_ C _。A. AB. BC. CD. D(26) 一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_ C _。A. edcbaB. decbaC. dceabD. abcde(27) 设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是_ C _。A. n-iB. n-1-iC. n+1-iD.不能确定(28) 字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_ B _个不同的字符串？A. 15B. 14C. 16D. 21(29) 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为_ D _。A. top=top+1; B. top=top-1; C. top-next=top; D. top=top-next; (30) 设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是_ C _。A. 6B. 4C. 3D. 2(31) 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_ B _。A. 1和5B. 2和4C. 4和2D. 5和1(32) 设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为_ C _。A. R-FB. F-RC. (R-F+M)%MD. (F-R+M)%M(33) 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为_ C _。A. front-next=s；front=s；B. s-next=rear；rear=s；C. rear-next=s；rear=s；D. s-next=front；front=s；(34) 如下陈述中正确的是_ A _。A. 串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串(35) 下列关于串的叙述中，正确的是_ D _。A. 串长度是指串中不同字符的个数B. 串是n个字母的有限序列C. 如果两个串含有相同的字符，则它们相等D. 只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等(36) 字符串的长度是指_ C _。A. 串中不同字符的个数B. 串中不同字母的个数C. 串中所含字符的个数D. 串中不同数字的个数 (37) 两个字符串相等的充要条件是_ C _。A. 两个字符串的长度相等B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件 D. 以上答案都不对(38) 串是一种特殊的线性表，其特殊性体现在_ B _。A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符(39) 设有两个串p和q，求q在p中首次出现的位置的运算称作_ B _。A. 连接B. 模式匹配C. 求子串D. 求串长(40) 设串sI=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是_ D _。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF (41) 函数substr(“DATASTRUCTURE”，5，9)的返回值为_ A _。A. “STRUCTURE” B. “DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE”(42) 设串S=”I AM A TEACHER!”，其长度是_ D _。A. 16B. 11C. 14D. 15(43) 假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为_B_。 A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉树的结点数为18个，则它的最小高度_B_。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉树中第五层上的结点数最多为_C_。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五层的满二叉树中，结点总数为_A_。A. 31 B. 32 C. 33 D. 16(47) 已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_B_。A. 1 B. 2 C. D. 4(48) 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_C_。 A. 23 B. 37 C. 44 D. 46(49) 在树中除根结点外，其余结点分成m (m0)个_A _的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1im)。A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交(50) 如果结点A有三个兄弟，而且B是A的双亲，则B的出度是_B_。A. 3 B. 4 C. 5 D. 1(51) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A. 1/2 B. 1 C. 2 D. 4(52) 具有n个顶点的无向完全图，边的总数为_ D_条。A. n-1 B. n C. n+1 D. n*(n-1)/2(53) 在无向图G的邻接矩阵A中，若Ai,j等于1，则Aj,i等于_C _。A. i+j B. i-j C. 1 D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为_A_ 。(访问标志位数组空间)A. O(n) B. O(e) C. O(n-e) D. O(n+e)(55) 请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用折半法查找关键码12需做_ C _次关键码比较。A.2 B.3 C.4 D.5 (56) 对线性表进行折半查找时，必须要求线性表 _ C _。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排列D. 以链接方式存储，且结点按关键字有序排列(57) 设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为_ B _。A. O(1) B. O(log2n) C. O(n) D. O(n2)(58) 依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中，查找元素35要进行_ A _元素间的比较。A.4次B.5次C.7次D.10次(59) 设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择_ B _。A. 小于等于m的最大奇数B. 小于等于m的最大素数C. 小于等于m的最大偶数D. 小于等于m的最大合数(60) _ D _是HASH查找的冲突处理方法。A.求余法 B. 平方取中法 C. 二分法 D. 开放地址法(61) 当的值较小时，散列存储通常比其他存储方式具有_ B _的查找速度。A. 较慢B. 较快C. 相同 D. 不确定(62) 对线性表进行折半查找最方便的存储结构是_ B _。A顺序表 B有序的顺序表C链表 D有序的链表(63) 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用_ D _查找方法。A分块 B顺序 C折半 D散列(64) 散列函数有一个共同性质，即函数值应按_ C _取其值域的每一个值。A最大概率 B最小概率 C同等概率 D平均概率(65) 下述排序算法中，稳定的是_ B _。A.直接选择排序 B. 直接插入排序 C.快速排序 D.堆排序 (66) 下列排序算法中，_ A _需要的辅助存储空间最大。A.快速排序B.插入排序C.希尔排序D.基数排序(67) 下列各种排序算法中平均时间复杂度为O(n2)是_ D _。A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序(68) 在基于关键码比较的排序算法中，_ C _算法在最坏情况下，关键码比较次数不高于O(nlog2n)。A. 起泡排序B. 直接插入排序C. 二路归并排序D. 快速排序(69) 一组记录为46，79，56，38，84，40，则采用冒泡排序法按升序排列时第一趟排序结果是_ B _ 。A. 46,79,56,38,40,84 B.46,56,38,79,40,84C. 38,40,46,56,84,79 D.38,46,79,56,40,84(70) 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_ A _ 排序。A. 插入 B. 堆 C.快速 D.归并(71) 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_ B _排序。A. 插入 B. 堆 C.快速 D.归并(72) 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为_ C _。A. 2，3，5，8，6B. 3，2，5，8，6C. 3，2，5，6，8D. 2，3，6，5，8(73) 下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关_ D _。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接选择排序(74) 设有关键码初始序列Q，H，C，Y，P，A,M,S,R,D,F,X，新序列F，H，C，D，P，A，M，Q，R，S，Y,X是采用_ C _ 方法对初始序列进行第一趟扫描的结果。A. 直接插入排序 B二路归并排序C以第一元素为分界元素的快速排序 D基数排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_ C _。A. 直接插入排序 B. 直接选择排序C 快速排序 D 归并排序(76) 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是_ C _ 。A. 快速排序 B 堆排序C 归并排序 D 直接插入排序(77) 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_ B _。A n B 2n-1 C 2n D n-1(78) 下列排序算法中，_ C _ 算法可能会出现下面情况：初始数据有序时，花费的间反而最多。A. 堆排序 B冒泡排序 C快速排序 D SHELL排序二、填空题。(每空1分，共10分)(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据 以及它们之间的 关系 和运算等的学科。(2) 数据结构包括数据的逻辑结构结构和物理结构结构。(3) 数据结构从逻辑上划分为三种基本类型：_线性数据结构_、_树型结构_和_图结构_。(4) 数据的物理结构被分为_顺序存储_、_链式存储_、_索引存储_和_散列表（Hash）存储_四种。(5) 一种抽象数据类型包括_变量的取值范围_和 _操作的类别_两个部分。(6) 数据的逻辑结构是指 数据元素间的逻辑关系 ，数据的存储结构是指 数据元素存储方式或者数据元素的物理关系 。(7) 数据结构是指数据及其相互之间的_关系_。当结点之间存在M对N（M：N）的联系时，称这种结构为_网状结构_。当结点之间存在1对N（1：N）的联系时，称这种结构为_树结构_。(8) 对算法从时间和空间两方面进行度量，分别称为 空间复杂度和时间复杂度 分析。(9) 算法的效率可分为_空间_效率和_时间_效率。(10) for(i=1，t=1，s=0；i1)的各棵树中，高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?答：结点个数为n时，高度最小的树的高度为1，有两层，它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-l，有n层，它有1个叶结点，n-1个分支结点。24. 什么是内部排序?什么是排序方法的稳定性?答：假定给定含有n个记录的文件(r1，r2，rn)，其相应的关键字为(k1，k2，kn)，则排序就是确定文件的一个序列r1，r2，rn，使得k1k2kn，从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。五、分析题。(每小题4分，共8分