《数据结构与算法》(张晓莉)习题：选择题、判断题.docx

《《数据结构与算法》(张晓莉)习题：选择题、判断题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》(张晓莉)习题：选择题、判断题.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章绪论1 .从逻辑上可以把数据结构分为（C ）两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2 .在下面的程序段中，对x的赋值语句的频度为（C ）oFor （k=1 ；k=n； k+）For （j=1； jnext=s ；s-next=p-next；B . s-next=p-next； p-next=s；C . p-next=s ； p-next=s-next；D . p-next=s-next； p-next=s；9 .在双向链表存储结构中，删除p所指的结点时须修改指针(A )。A .(p- prior)- next = p-next

2、; (p-next) -prior =p- prior;B . p- prior= (p- prior) - prior; (p- prior) - next =p ;C .(p-next) -prior =p ; p-rlink= (p- next) - next;D . p-next = (p- prior) - prior; p- prior = (p- next) - next 10,完成在双向循环链表结点p之后插入s的操作是(D )oA . p-next =s; s- prior =p; p- next-prior =s; s- next =p- next;B . p-next- p

3、rior =s; p- next =s; s- prior =p; s- next =p- next;C . s- prior =p; s- next = p-next; p- next =s; p- next- prior =s; D . s prior =p; s- next = p-next; p- next- prior =s;p- next =s;11 .若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 （B ）存储方式最节省运算时间。A.单链表 B.顺序表 C.双向链表 D.单循环链表12 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个

4、元 素，则采用（D ）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双向链表D.仅有尾指针的单循环链表第三章栈和队列1 .向一个栈顶指针为top的链栈中插入一个p所指结点时，其操作步骤为（C ）oA. top-next=p；C. p-next=top； top=p；B . p-next=top-next； top-next=p；D . p-next=top； top=top-next；2 .对于栈操作数据的原则是（B ）oA.先进先出B.后进先出C.后进后出D.不分顺序3 .若已知一个栈的入栈序列是1 , 2, 3,，n,其输出序列为pP p2, P3,，Pn，若 Pn 是

5、n,则 P（ D ） oA . i B . n-i C . n-i + lD.不确定4 .表达式a* （bc）+d的后缀表达式是（B ）。A . abed*+B . abc*d+C . abc*d+D. +*abcd5 .采用顺序存储的两个栈的共享空间用topi代表第i个栈（i=1, 2）的栈顶, 栈1的底在S1,栈2的底在Sm,则栈满的条件是（B ）oA. top2top1=0 B . top1+1 = top2C. top1+top2 =m D . top1 = top26 . 一个栈的入栈序列是a, b, c, d, e,则栈的不可能的输出序列是（C ）。A edeba B . decb

6、a C . deeab D . abode7 .在一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（B ）。A . f-next=p ；f=pB . r-next=p； r=pC . p-next=r； r=pD . p-next=f； f=p8 .用不带头结点的单链表存储队列时，在进行删除运算时（D ）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改9 .递归过程或者函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。A.队列 B.静态链表C.栈 D.顺序表10,栈和队都是（C ）oA.顺序存储的线性结构C.限制存取点的线性结

7、构B.链式存储的非线性结构D.限制存取点的非线性结构第四章 字符串及线性结构的扩展1 .下面关于串的叙述，错误的是（C ）。A.串是字符的有限序列B.串既可以采用顺序存储，也可以采用链式存储C.空串是由空格构成的串D.模式匹配是串的一种重要运算2 .串的长度是指（B ）。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数 3.4.二维数组M的成员是6个字符(每一个字符占一个存储单元，即一个字节)组成的串, 行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要(1) ( D ) 个字节；M的第8列和第5行共占(2) ( A )个字

8、节；若M按行优先方式存储，元 素的起始地址与当M按列优先方式存储时的(3) ( C )元素的起始地址一 致。D. 540D. 60C. M58(1) A. 90 B. 180 C. 240(2)A.108 B. 114 C. 54(3) A. M85 B. M3105 .数组A中，每一个元素的存储占3个单元，行下标i从1至U 8,列下标j从1至U 10, 从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是(1) ( C )；若该数组按行存放，元素A85的起始地址为(2) ( D )；若该数组按列存放，元 素A85的起始地址为(3) ( B )o(1) A. 80 B. 100C

9、.240 D. 270(2) A. SA+141B. SA+144C. SA+222D. SA+225(3) A. SA+141B. SA+180C. SA+117D. SA+2256 .稀疏矩阵采用压缩存储，普通有(C )两种方法。A.二维数组和三维数组B,三元组和散列C.三元组表和十字链表D.散列和十字链表第五章树结构1 .下列说法正确的是(C )oA.二叉树中任何一个结点的度都为2 B.二叉树的度为2C. 一棵二叉树的度可小于2 D.任何一棵二叉树中至少有一个结点的度为22 .以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中(n0),空链域 的个数为(C )。A . 2n1B

10、- n1C . n+l D . 2n+l3 .线索化二叉树中，某结点*p没有孩子的充要条件是(B )。A. p-lchild=NULL B. p-ltag=1 且 p-rtag=1C. p-ltag=0D. p-lchild=NULL 且 p-ltag=14 .如果结点A有3个兄弟，而且B是A的双亲，则B的度是(B )。A. 3 B. 4 C. 5 D. 15 .某二叉树T有n个结点，设按某种顺序对T中的每一个结点进行编号，编号值为1, 2, n,且有如下性质：T中任意结点v,其编号等于左子树上的最小编号减1,而v的右子 树的结点中，其最小编号等于v左子树上结点的最大编号加1,这是按(B )编

11、号 的。A.中序遍历序列B.先序遍历序列C.后序遍历序列 D.层次顺序6 .设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针 域为空的结点有(C )个。A . n 1B. n C . n+l D . n+27 .一棵彻底二叉树上有1001个结点，其中叶子结点的个数是（C ）oA. 500 B. 501 C . 490 D . 4958 .设森林F中有3棵树，第1、第2和第3棵树的结点个数分别为N1，帅和N3o与森 林F对应的二叉树根结点的右子树上的结点个数是（D ）。A. MB . M + N,C. N9D . N9+NqII乙乙o9 .任何一棵二叉树的叶结点在先序、

12、中序和后序遍历序列中的相对次序（A ）oA.不发生改变B.发生改变C.不能确定 D.以上都不对10 .若一棵二叉树的后序遍历序列为dabec,中序遍历序列为debac,则先序遍历序列为（D ） oA. cbed B. decab C. deabc D.cedba11 .若一棵二叉树的先序遍历序列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍 历的结果为（D ）。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12 . 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（B ） oA.所有的结点均无左孩子B.所有的结点

13、均无右孩子C.惟独一个叶子结点D.是一棵满二叉树13,设高度为h的二叉树上惟独度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为（B ）。A. 2h B. 2h-1C. 2h + 1D. h + 114.一个具有567个结点的二叉树的高八为（D ）oA. 9 B. 10 C. 9566 之间D. 10567 之间第六章图结构1 .n条边的无向图的邻接表的存储中，边结点的个数有（A ）。A. nB. 2nC. n/2D. nxn2 . n条边的无向图的邻接多重表的存储中，边结点的个数有（A ）。A. nB. 2nC. n/2D. nxn3 .下列哪一种图的邻接矩阵是对称矩阵？（ B ）A

14、.有向图 B.无向图 C.AOV网 D.AOE网4 .最短路径的生成算法可用（C ）。A.普利姆算法 B.克鲁斯卡尔算法C.迪杰斯特拉算法D.哈夫曼算法5. 一个无向图的邻接表如下图所示。(2)从顶点V。出发进行广度优先搜索，经历的结点顺序为(D )。%，7 2, V3%，v3, v2A. v0, v3, v2, v1B. v0,C. vn, v9, V1, VqD. vn,U 乙IDU6.设有向图n个顶点和e条边,A. O(nlog2e) B. O(exn)进行拓扑排序时，总的计算时间为(D )。C. O(elog2n) D. O(n+e)7.含有n个顶点e条边的无向连通图，利用Kruska

15、l算法生成最小生成树，其时间复杂 度为(A )o8.关键路径是事件结点网络中(A.从源点到汇点的最长路径 C.最长的回路A )oB.从源点到汇点的最短路径D.最短的回路A. O(elog 2e) B. O(exn) C. O(elog2n) D. O(nlog2n)9 .下面关于求关键路径的说法，不正确的是(C )oA.求关键路径是以拓扑排序为基础的B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的 持续时间的差D.关键活动一定位于关键路径上10 .有10个结点的无向图至少有(B )条边才干确保其是连通

16、图。A. 8 B. 9 C. 10 D. 11第七章查找1 .静态查找表与动态查找表的根本区别在于(B )oA.它们的逻辑结构不一样B.施加在其上的操作不一样C.所包含的数据元素类型不一样D.存储实现不一样2 .在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为 (A ) oA. n B. 1 C. n+1 D. n-13 .顺序查找合用于存储结构为(C )的线性表。A.散列存储B.压缩存储C.顺序存储或者链式存储D.索引存储4 ,用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为(C )。A . O(log2n2)B. O(nlog2n) C. 0(n) D. O

17、(log2n)5 .合用于折半查找的表的存储方式及元素罗列要求为(D )。元素无序 元素有序 元素无序 元素有序A.链接方式存储, B.链接方式存储, C.顺序方式存储, D.顺序方式存储,6 .有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情B ）oD. 43/12况下查找成功所需的平均比较次数为(A. 35/12 B. 37/12 C. 39/127.在有序表1, 3, 9, 12, 32, 41, 62, 为82的数据元素需要比较（C ）次。A. 1 B. 2 C. 4 D. 575, 77, 82, 95, 100上进行折半查找关键字8 .设散列表长为14,散

18、列函数为H (key) = key % 11。当前表中已有4个结点：addr (15)=4, addr (38)=5, addr (61)=6, addr (84)=7o如用二次探测再散列处理冲突， 则关键字为49的结点的地址是(D )。A. 8 B. 3 C. 5 D. 99 .散列函数有一个共同的性质，即函数值应当以(D )取其值域的每一个值。A,最大概率B,最小概率C.平均概率D.同等概率10 .假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至 少要进行(D )次探测。A. k-1 次 B. k 次 C. k+1 次 D. k (k+1) /2 次11 .在散列函

19、数H (k) =k%m中，普通来讲，m应取(C )。A.奇数 B.偶数 C.素数 D.充分大的数12 .在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在 查找成功的情况下，所探测到的这些位置上的键值(B )。A. 一定是同义词B. 一定不是同义词C.都相同D.不一定都是同义词第八章排序1 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A ）oA.插入排序B.选择排序C.快速排序D,归并排序2 .设有1000个无序的元素，希翼用最快的速度挑选出其中前10个最大的元素，最好选 用（C ）排序法。A.冒泡排序B,快速排序C.堆排序D.基数排序3 .具有12个记录

20、的序列，采用冒泡排序至少的比较次数是（C ）0A. 1 B. 144 C. 11 D. 664 .下列四种排序方法中，要求内存容量最大的是（D ）。A,插入排序B.选择排序C.快速排序D,归并排序5 .初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（D ）0A . m2 B. nlog2n C. Iog2nD. n 16 .下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始罗列顺序无关的 是（C ） OA.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.直接插入排序和归并排序7 .一组记录的排序码为（46, 79, 56, 38, 40,

21、 84）,则利用堆排序的方法建立的初始 堆为（B ）oA.79, 46, 56, 38, 40, 84B.84, 79, 56, 38, 40, 46C.84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 388 . 一组记录的排序码为（46, 79, 56, 38, 40, 84）,则利用快速排序的方法，以第一 个记录为基准得到的一次划分结果为（C ）oA. 38, 40, 46, 56, 79, 84B. 40, 38 , 46, 79, 56, 84C. 40, 38, 46, 56, 79, 84D.40, 38, 46, 84, 56, 7927

22、, 68, 35 , 20)进行排序时,9 .用某种排序方法对线性表（25, 84, 21 , 47, 15, 元素序列的变化情况如下：(1) 25, 84, 21,20, 15, 21,15, 20, 21,15, 20, 21,)/ 7 )/2 3 4z/l /( /(47, 15, 27,25, 47, 27,25, 35, 27,25, 27, 35,则所采用的排序方法是（D ）oA.选择排序B.希尔排序68,68,47,47,C.35, 2035, 8468, 8468, 84归并排序D.快速排序10 .快速排序方法在（C ）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序

23、的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数第一章绪论1 .数据的逻辑结构是指数据的各个数据项之间的逻辑关系。2 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3 .数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。4 .算法优劣与描述算法的语言无关，但与所用计算机的性能有关。5 .算法必须有输出，但可以没有输入。第二章线性表1 .线性表的逻辑顺序与存储顺序总是一致的。2 .顺序存储的线性表可以按序号随机存取。3 .顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均惟独近一半的元素需要 挪移。4 .线性表中的元素可以是各种

24、各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同 一数据对象。5 .在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6 .在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7 .线性表的链式存储结构优于顺序存储结构。8 .在线性表的顺序存储结构中，插入和删除时挪移元素的个数与该元素的位置有关。9 .线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10 .在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储 结构。11 .静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i 无关。12 .线性表的特点是每一个元素都有一个前驱和一个后继。第三章栈和队列第四章 字符串及线性结构的扩展第五章树结构1 .二叉树是树的特殊形式。2 .由树转换成二叉树，其根结点的右子树总是空的。20 .满二叉树一定是彻底二叉树，反之未必。第六章图结构第七章查找3.对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉 排序树是相同的。