2022年数据结构练习题及答案实用 .pdf

《2022年数据结构练习题及答案实用 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构练习题及答案实用 .pdf（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 第1章绪论一、 判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。（）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）3.数据元素是数据的最小单位。（）4.数据的逻辑结构和数据的存储结构是相同的。（）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）7.数据的存储结构是数据的逻辑结构的存储映象。（）8.数据的物理结构是指数据在计算机内实际的存储形式。（）9.数据的逻辑结构是依赖于计算机的。（）10.算法是对解题方法和步骤的描述。（）二、填空题1.数据有逻辑结构和存储结构两种

2、结构。2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。4.树形结构和图形结构合称为非线性结构。5.在树形结构中，除了树根结点以外，其余每个结点只有1 个前驱结点。6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。7.数据的存储结构又叫物理结构。8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。9.线性结构中的元素之间存在一对一的关系。10.树形结构中的元素之间存在一对多的关系。11.图形结构的元素之间存在多对多的关系。12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3

3、个方面的内容。13.数据结构被定义为（D， R） ，其中 D是数据的有限集合，R是 D上的关系有限集合。14.算法是一个有穷指令的集合。15.算法效率的度量可以分为事先估算法和事后统计法。16.一个算法的时间复杂度是算法输入规模的函数。17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n 的函数。18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n, 则算法的时间复杂度为O （ nlog2n）。19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2, 则算法的时间复杂度为O （n2）。20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，

4、以及它们之间的关系和运算的学科。三、选择题1.数据结构通常是研究数据的（A）及它们之间的相互关系。A存储结构和逻辑结构 B 存储和抽象 C联系和抽象 D联系与逻辑2.在逻辑上可以把数据结构分成（C） 。A动态结构和静态结构 B 紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构。3.数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C） 。A存储结构 B逻辑结构 C顺序存储结构 D链式存储结构4.非线性结构中的每个结点（D） 。A无直接前驱结点 B无直接后继结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

5、- - - - 名师精心整理 - - - - - - - 第 1 页，共 45 页 - - - - - - - - - 2 C只有一个直接前驱结点和一个直接后继结点D可能有多个直接前驱结点和多个直接后继结点5.链式存储结构所占存储空间（A） 。A分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。B只有一部分，存放结点的值。 C只有一部分，存储表示结点间关系的指针。D分两部分，一部分存放结点的值，另一部分存放结点所占单元素6.算法的计算量大小称为算法的（C） 。A现实性 B难度 C时间复杂性 D效率7.数据的基本单位（B） 。A数据结构 B数据元素 C数据项 D文件8.每个结点只

6、含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为（ A）结构。A顺序结构 B链式结构 C索引结构 D散列结构9.每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B） 。A顺序 B链式 C索引 D散列10.以下任何两个结点之间都没有逻辑关系的是（D） 。A图形结构 B线性结构 C树形结构 D集合11.在数据结构中，与所使用的计算机无关的是（C） 。A物理结构 B存储结构 C逻辑结构 D逻辑和存储结构12.下列 4 种基本逻辑结构中，数据元素之间关系最弱的是（A） 。A集合 B线性结构 C树形结构 D图形结构13.与数据元素本身的形式、内容、相对位置

7、、个数无关的是数据的（A ） 。A逻辑结构 B存储结构 C逻辑实现 D存储实现14.每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。A顺序 B链式 C索引 D散列15.算法能正确的实现预定功能的特性称为算法的（A ） 。A正确性 B易读性 C健壮性 D高效性16.算法在发生非法操作时可以作出相应处理的特性称为算法的（C） 。A正确性 B易读性 C健壮性 D高效性17.下列时间复杂度中最坏的是（D） 。A O （1） B.O（n） C.O( log2n) D.O(n2) 18.下列算法的时间复杂度是（D） 。for(i=

8、0;in;i+) for(j=o;iprior-next=p-next；p-next-prior=p-prior 20.在如图所示的链表中，若在指针P 所在的结点之后插入数据域值为a 和 b 的两个结点，则可用语句 S-next-next=p-next和 P- next=S ；来实现该操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 45 页 - - - - - - - - - 4 p a b s 三、 选择题1.在具有 n 个结点的单向链表中，实现（ A）的操作，其

9、算法的时间复杂度都是O(n). A.遍历链表或求链表的第i 个结点 B.在地址为 P的结点之后插入一个结点C.删除开始结点 D.删除地址为P的结点的后继结点2.设 a、b、c 为 3 个结点， p、10、20 分别代表它们的地址，则如下的存储结构称为（ B ） 。 p a 10 b 20 c A循环链表 B单向链表 C双向循环链表 D双向链表3.单向链表的存储密度（ C ） 。A.大于 1 B.等于 1 C.小于 1 D.不能确定4.已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第 i 个结点的地址为（ A ） 。A.B+(i-1)m B.B+im C.B-im

10、 D.B+(i+1) m 5.在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ） 。A O （1） B.O（n） C. O(n2) D.O( log2n) 6.设 front 、rear 分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L 的尾元素的条件是（ D ） 。A.P= =L B.P-front= =L C.P= =NULL D.P-rear= =L 7.两个指针P和 Q ，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（ B ） AP-next= =Q-next B.P-next= =Q C.Q-next= =P D.P=Q

11、8.用链表存储的线性表，其优点是（ C ） 。 A便于随机存取 B花费的存储空间比顺序表少C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同9.在单链表中，增加头结点的目的是（ C ） 。 A 使单链表至少有一个结点 B标志表中首结点的位置C方便运算的实现 D说明该单链表是线性表的链式存储结构10.下面关于线性表的叙述中，错误的是（ D ）关系。 A 顺序表必须占一片地址连续的存储单元B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元D链表可以随机存取任一元素11.L 是线性表，已知LengthList(L)的值是 5，经 DelList(L，2) 运算后， LengthLis

12、t(L)的值是（ C ） 。 A 2 B 3 C4 D5 12.单向链表的示意图如下： L A B C D P Q R 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 45 页 - - - - - - - - - 5 指向链表Q结点的前驱的指针是（ B ） 。A L BP CQ DR 13.设 p 为指向单循环链表上某结点的指针，则*p 的直接前驱（ C ） 。A找不到 B查找时间复杂度为O（1）C查找时间复杂度为O（n）D查找结点的次数约为n 14.等概率情况下，在有n

13、 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ 8 ） 。A n B.(n-1)/2 C.n/2 D.(n+1)/2 15.在下列链表中不能从当前结点出发访问到其余各结点的是（ C ） 。A. 双向链表 B.单循环链表 C.单向链表 D.双向循环链表16.在顺序表中，只要知道（ D ） ，就可以求出任一结点的存储地址。A. 基地址 B.结点大小 C.向量大小 D.基地址和结点大小17.在双向链表中做插入运算的时间复杂度为（ A ） 。A O （1） B.O（n） C. O(n2) D.O( log2n) 18.链表不具备的特点是（ A ） 。A随机访问 B.不必事先估计存储空间C.

14、 插入删除时不需要移动元素 D. 所需空间与线性表成正比19.以下关于线性表的论述，不正确的为（ C ） 。A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继D.存在这样的线性表，即表中没有任何结点20.在（ B ）的运算中，使用顺序表比链表好。A.插入 B.根据序号查找 C.删除 D.根据元素查找名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 45 页 - - - - -

15、- - - - 6 第 3 章 栈一、 判断题1.栈是运算受限制的线性表。（）2.在栈空的情况下，不能作出栈操作，否则产生下溢。（）3.栈一定是顺序存储的线性结构。（）4.栈的特点是“后进先出”。（）5.空栈就是所有元素都为0 的栈。（）6.在 C（或 C+ ）语言中设顺序栈的长度为MAXLEN ，则 top=MAXLEN 时表示栈满。（）7.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（）8.一个栈的输入序列为：A，B ，C，D，可以得到输出序列：C，A， B ，D。（）9.递归定义就是循环定义。（）10.将十进制数转换为二进制数是栈的典型应用之一。（）二、填空题1.在栈结构中，允

16、许插入、删除的一端称为栈顶。2.在顺序栈中，当栈顶指针top=-1时，表示栈空。3.在有 n 个元素的栈中，进栈操作时间复杂度为 O（1）。4.在栈中，出栈操作时间复杂度为 O（1）。5.已知表达式，求它的后缀表达式是栈的典型应用。6.在一个链栈中，若栈顶指针等于NULL ，则表示栈空。7.向一个栈顶指针为top 的链栈插入一个新结点*p 时，应执行p-next=top;top=p；操作。8.顺序栈 S存储在数组S-data0 ,MAXLEN-1中， 进栈操作时要执行的语句有：S-top+ 。 ( 或 S-top+1) S-dataS-top=x 9.链栈 LS，指向栈顶元素的指针是LS-ne

17、xt 。10.从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。11.由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。12.已知顺序栈S，在对 S进栈操作之前首先要判断栈是否满。13.已知顺序栈S，在对 S出栈操作之前首先要判断栈是否空。14.若内在空间充足，链栈可以不定义栈满运算。15.链栈 LS 为空的条件是 LS-next=NULL 。16.链栈 LS 的栈顶元素是链表的首元素。17.同一栈的各元素的类型相同。18.若进栈的次序是A、B、C、D、E，执行 3 次出栈操作以后，栈顶元素为 B 。19.A+B/C-D*E 的后缀表达式是 ABC/+DE*- 。20.4 个元

18、素 A、B、 C、D顺序进 S栈，执行两次Pop(S,x) 运算后， x 的值是 C 。三、选择题1.插入和删除操作只能在一端进行的线性表，称为（ C ） 。A队列 B循环队列 C栈 D循环栈2.设有编号为1，2。3，4 的 4 辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（ D） 。A1234 B1243 C1324 D1423 3.如果以链表作为栈的存储结构，则出栈操作时（ B ） 。A必须判别栈是否满 B 必须判别栈是否为空 C 必须判别栈元素类型 D 栈可不做任何判别4.元素 A、B 、 C、D依次进栈以后，栈顶元素是（ D ）AA BB CC DD 5.顺序栈存储空间的实

19、现使用（ B ）存储元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 45 页 - - - - - - - - - 7 A链表 B数组 C循环链表 D变量6.在 C（或 C+ ）语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ） 。A已固定 B不固定 C可以改变 D动态变化7.带头结点的链栈LS的示意图如下，栈顶元素是（ A ） 。LS H A B C D AA BB CC DD 8.链栈与顺序栈相比，有一个比较明显的优点是（ B ） 。A.插入操作更加方便 B

20、. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便9.从一个栈顶指针为top 的链栈中删除一个结点时，用x 保存被删除的结点，应执行下列（d ）命令。Ax=top;top-next; B.top=top-next;x=top-data C.x=top-data; D.x=top-data;top=top-next 10.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列（ B ）命令。A.HS-next=S B.S-next=HS-next;HS-next=S; C.S-next=HS-next;HS=S; D.S-next=HS=HS-next 1

21、1.4 元素按 A、B、 C、D顺序进 S栈，执行两次Pop(S，x) 运算后，栈顶元素的值是（ B ） 。AA BB CC DD 12.元素 A、B 、 C、D依次进栈以后，栈底元素是（ A ） 。AA BB CC DD 13.经过下列栈的运算后，再执行ReadTop(s) 的值是（ A ） 。InitStack(s);Push(s， a); Push(s，b);Pob(s); A.a B.b C.1 D.0 14.经过下列栈的运算后，x 的值是（ B ） 。InitStack(s)（初始化栈） ; Push(s，a); Push(s，b); ReadTop(s) ； Pob(s， x);

22、A.a B.b C.1 D.0 15.经过下列栈的运算后，x 的值是（ B ） 。InitStack(s)（初始化栈） ; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x); A.a B.b C.1 D.0 16.经过下列栈的运算后,SEmpty(s) 的值是（ C ） 。InitStack(s)（初始化栈） ; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x); A.a B.b C.1 D.0 17.向顺序栈中输入元素时（ B ） 。A先存入元素，后移动栈顶指针 B先移动栈顶指针，后存入元素C谁先谁后无关紧要 D同时进行18.初

23、始化一个空间大小为5 的顺序栈 S后， S-top 的值是（ B ） 。A0 B-1 C不再改变 D动态变化19.设有一个入栈的次序A、B、C、D、E，则栈不可能的输出序列是（ C ） 。AEDCBA BDECBA CDCEAB DABCDE 20.设有一个顺序栈S，元素 A、B、 C、D、E、F 依次进栈，如果6 个元素出栈的顺序是B、D、C、 F、E、A，则栈的容量至少应是（ A ） 。A3 B4 C5 D6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 45 页

24、- - - - - - - - - 8 第 4章 队列一、判断题1.队列是限制在两端进行操作的线性表。（）2.判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。（）3.在链队列上做出队操作时，会改变front指针的值。（）4.在循环队列中，若尾指针rear 大于头指针front ，其元素个数为rear-front。（）5.在单向循环链表中，若头指针为h，那么 p 所指结点为尾结点的条件是p=h。（）6.链队列在一定范围内不会出现队满的情况。（）7.在循环链队列中无溢出现象。（）8.栈和队列都是顺序存储的线性结构。（）9.在队列中允许删除的一端称为队尾。（）10.顺序队和循环队关于队满和队

25、空的判断条件是一样的。（）二、填空题1.在队列中存取数据应遵循的原则是先进先出。2.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。3.在队列中，允许插入的一端称为队尾。4.在队列中，允许删除的一端称为队首（或队头）。5.队列在进行出队操作时，首先要判断队列是否为空。6.顺序队列在进行入队操作时，首先在判断队列是否为满。7.顺序队列初始化后，初始化后，front=rear= -1 。8.解决顺序队列“假溢出”的方法是采用循环队列。9.循环队列的队指针为front ，队尾指针为rear ，则队空的条件为 front= =rear 。10.链队列 LQ为空时， LQ-fr

26、ont-next= NULL 。11.设长度为n 的链队列用单循环表表示，若只设头指针，则入队操作的时间复杂度为 O(n) 。12.设长度为n 的链队列用单循环表表示，若只设尾指针，则入队操作的时间复杂度为 O(1) 。13.在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。14.设循环队列的头指针front指向队首元素，尾指针rear 指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN ，则队满标志为 front= =(rear+1)%MAXLEN 。15.在一个链队列中，若队首指针为front ，队尾指针为rear ，则判断队列只有一个结点的条件为front= =re

27、ar或 front!。16.向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。17.读队首元素的操作不改变或不影响队列元素的个数。18.设循环队列的容量为40（序号 039） ，现经过一系列的入队和出队的运算后，front=11，rear=19 ，则循环队列中还有 8 个元素。19.队列 Q，经过下列运算： InitQueue(Q)(初始化队列 )；InQueue(Q,a) ；InQueue(Q,b) ；OutQueue(Q,x) ；ReadFront(Q,x)；QEmpty(Q)；后的值是 8 。20.队列 Q经过 InitQueue(Q)(初始化队列 )

28、；InQueue(Q,a) ；InQueue(Q,b) ；ReadFront(Q,x)后， x 的值是 a 。三、选择题1.队列是限定在（D）进行操作的线性表。A中间者 B.队首 C.队尾 D.端点2.队列中的元素个数是（B） 。A不变的 B.可变的 C.任意的 D.0 3.同一队列内的各元素的类型（A） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 45 页 - - - - - - - - - 9 A. 必须一致 B.不能一致 C.可以不一致 D.不限制4.队列是一

29、个（ C）线性表结构。A. 不加限制的 B.推广了的 C.加了限制的 D.非5.当利用大小为n 的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B） 。A.n-2 B.n-1 C.n D.n+1 6.一个循环队列一旦说明，其占用空间的大小（A） 。A. 已固定 B.可以变动 C.不能固定 D.动态变化7.循环队列占用的空间（A） 。A. 必须连续 B.不必连续 C.不能连续 D.可以不连续8.存放循环队列元素的数组data 有 10 个元素，则data 数组的下标范围是（B） 。A.0 10 B.09 C.19 D.1 10 9.若进队的序列为A、B、C、D，则出队的序列是（C） 。A

30、.B、C、D、A B.A、C、B 、 D C.A、B、C、D D.C、 B、D、A 10.4 个元素按 A、B、C 、D顺序连续进队Q，则队尾元素是（D）AA BB CC DD 11.4 个元素按 A、B、C 、D顺序连续进队Q，执行一次QutQueue(Q)操作后，队头元素是（B） 。A.A B.B C.C D.D 12.4 个元素按A、B、C、 D顺序连续进队Q ，执行 4 次 QutQueue(Q)操作后，再执行QEmpty(Q)；后的值是（ B） 。A.0 B.1 C.2 D.3 13.队列 Q，经过下列运算后，x 的值是 （B） 。InitQueue(Q)(初始化队列 ) ；InQu

31、eue(Q,a) ；InQueue(Q,b) ；OutQueue(Q,x) ；ReadFront(Q,x)；A.a B.b C.0 D.1 14.循环队列SQ队满的条件是（B） 。A.SQ-rear= =SQ-front B.(SQ-rear+1)%MAXLEN= =SQ-front C.SQ-rear= =0 D.SQ-front= =0 15.设链栈中结点的结构：data 为数据域， next 为指针域，且top 是栈顶指针，若想在链栈的栈顶插入一个由指针s 所指的结点，则应执行下列（A）操作。A.s-next=top-next;top-next=s; B.top-next=s; C.s-

32、next=top;top-next; D.s-next=top;top=s; 16.带头结点的链队LQ示意图如下，链队列的队头元素是（A） 。LQ-front H A B C D LQ-rear AA BB CC DD 17.带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C） 。LQ-front H A B C D 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 45 页 - - - - - - - - - 10 LQ-rear A.LQ-front B.LQ-

33、rear C.LQ-front-next D.LQ-rear-next 18.带头结点的链队列LQ示意图如下 , 在进行进队的运算时指针LQ-frnot(A). LQ-front H A B C D LQ-rear A. 始终不改变 B.有时改变 C.进队时改变 D.出队时改变19. 队列 Q ，经过下列运算后，再执行QEmpty(Q)的值是（ C） 。InitQueue(Q)(初始化队列 )；InQueue(Q,a) ；InQueue(Q,b) ；OutQueue(Q,x) ；ReadQueue(Q,x) ；A.a B.b C.0 D.1 20. 若用一个大小为6 数组来实现循环队列，且当前

34、front和 rear 的值分别为3 和 0，当从队列中删除一个元素，再加入两个元素后，front和 rear 的值分别为（B） 。A.5 和 1 B.4和 2 C.2和 4 D.1和 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 45 页 - - - - - - - - - 11 第 5 章 串一、判断题1.串是 n 个字母的有限序列。（）2.串的数据元素是一个字符。（）3.串的长度是指串中不同字符的个数。（）4.如果两个串含有相同的字符，则说明它们相等。（）5

35、.如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（）6.串的堆分配存储是一种动态存储结构。（）7.“ DT”是“ DATA ”的子串。（）8.串中任意个字符组成的子序列称为该串的子串。（）9.子串的定位运算称为模式匹配。（）10.在链串中为了提高存储密度，应该增大结点的大小。（）二、填空题1.由零个或多个字符组成的有限序列称为字符串（或串）。2.字符串按存储方式可以分为顺序存储、链接存储和堆分配存储。3.串的顺序存储结构简称为顺序串。4.串顺序存储非紧凑格式的缺点是空间利用率低。5.串顺序存储紧凑格式的缺点是对串的字符处理效率低。6.串链接存储的优点是插入、删除方便，缺点是

36、空间利用率。7.在 C或 C+ 语言中，以字符 0 表示串值的终结。8.空格串的长度等于空格的个数。9.在空串和空格串中，长度不为0 的是空格串。10.两个串相等是指两个串长度相等，且对应位置的字符都相同。11.设“ S=My Music” ，则 LenStr(s)= 8 。12.两个字符串分别为；S1=”Today is ”、S2=”30 July ，2005”，ConcatStr(S1，S2)的结果是 Today is 30 July,2005 。13.求子串函数SubStr( “Today is 30 July，2005”， 13，4) 的结果是 July 。14.在串的运算中，Equa

37、lStr(aaa,aab)的返回值 m ，则模式匹配算法最坏情况下的时间复杂度为 (n-m+1)*m 。三、选择题1.串是和种特殊的线性表，其特殊体现在（B） 。A可能顺序存储 B数据元素是一个字符C可以链接存储 D 数据元素可以是多个字符2.某串的长度小于一常数，则采用（B）存储方式最节省空间。A链式 B顺序 C堆结构 D无法确定3.以下论述正确的是（C） 。A空串与空格串是相同的B” tel ”是” Teleptone ”的子串C空串是零个字符的串 D 空串的长度等于1 4.以下论述正确的是（B） 。A空串与空格串是相同的B” ton ”是” Teleptone ”的子串名师资料总结 -

38、- -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 45 页 - - - - - - - - - 12 C空格串是有空格的串 D 空串的长度等于1 5.以下论断正确的是（A） 。A全部由空格组成的串是空格串 B” BEUIJING”是” BEI JING ”的子串C” something ”1) 个结点的完全二叉树中，结点i(2in)的左孩子结点是（D） 。A.2i B.2i+1 C.2i-1 D.不存在13.把一棵树转换为二叉树后，这棵二叉树的形态是（A） 。A. 唯一的 B.有多种 C.

39、有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子14.将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为 45 的结点的左孩子编号为（B） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 45 页 - - - - - - - - - 17 A.46 B.47 C.90 D.91 15.将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为 49 的结点的右孩子编号为（B

40、） 。A.98 B.99 C.50 D.100 16.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B） 。A. 正确 B.错误 C.不确定 D.都有可能17.下列陈述正确的是（D） 。A. 二叉树是度为为2 的有序树 B.二叉树中结点只有一个孩子时无左右之分C. 二叉树必有度为2 的结点 D.二叉树中最多只有两棵子树，且有左右子树之分18.用 5 个权值 3 ， 2，4，5，1构造的哈夫曼树的带权路径长度是（B） 。A.32 B.33 C.34 D.15 19.在树结构中，若结点B有 4 个兄弟， A是 B的父亲结点，则A的度为（ C） 。A.3 B.4 C.5 D

41、.6 20.二叉树的叶结点个数比度为2的结点的个数（C） 。A. 无关 B.相等 C.多一个 D.少一个名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 45 页 - - - - - - - - - 18 第 8 章 图一、判断题1.图可以没有边，但不能没有顶点。（）2.在无向图中， (v1，v2) 与（ v2，v1）是两条不同的边。（）3.邻接表只能用于有向图的存储。（）4.一个图的邻接矩阵表示是唯一的。（）5.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个

42、数无关，而只与图的边数有关。 （）6.有向图不能进行广度优先遍历。（）7.若一个无向图以顶点v1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（）8.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角） 部分就可以了。（）9.用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（）10.若从一个无向图中任一顶占出发，进行了一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。（）二、填空题1.图常用的存储方式有邻接矩阵和邻接表等。2.图的遍历有：深度优先搜和广度优先搜等方法。3.有 n 条边的无向图邻接矩阵中，1 的个数是

43、 2n 。4.有向图的边也称为弧。5.图的邻接矩阵表示法是表示顶点之间相邻关系的矩阵。6.有向图 G用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的出度。7.n 个顶占 e 条边的图若采用邻接矩阵存储，则空间复杂度为： On2。8.n 个顶占 e 条边的图若采用邻接表存储，则空间复杂度为： O(n+e) 。9.设有一稀疏图G ，则 G采用邻接表存储比较节省空间。10.设有一稠密图G ，则 G采用邻接矩阵存储比较节省空间。11.图的逆邻接表存储结构只适用于有向图。12.n 个顶点的完全无向图有 n(n-1)/2 条边。13.有向图的邻接矩阵表表示适于求顶点的出度。14.有向图的邻接矩阵表示

44、中，第i 列上非 0 元素的个数为顶点vi的入度。15.对于具有n 个顶点的图，其生成树有且仅有 n-1 条边。16.对有 n 个顶点， e 条弧的有向图，其邻接表表示中，需要 n+e 个结点。17.从图中某一顶点出发，访遍历图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。18.无向图的邻接矩阵一定是对称矩阵。19.一个连通网的最小生成树是该图所有生成树中权最小的生成树。20.若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。三、选择题1.在一个图中，所有顶点的度数之和等于图的边数的（C）倍。A.1/2 B.1 C.2 D.4 2.在一个有向图中，所有顶点的入度之和等

45、于所有顶点的出度之和的（B）倍。A.1/2 B.1 C.2 D.4 3.对于一个具有n 个顶点的有向图的边数最多有（B ） 。A.n B.n(n-1) C.n(n-1)/2 D.2n 4.在一个具有n 个顶点的无向图中，要连通全部顶点至少需要（C）条边。A.n B.n+1 C.n-1 D.n/2 5.有 8 个结点的有向完全图有（ C ）条边。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 45 页 - - - - - - - - - 19 A.14 B.28 C.56

46、 D.112 6.深度优先遍历类似于二叉树的（A） 。A. 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历7.广度优先遍历类似于二叉树的（D） 。A. 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历8.任何一个无向连通图的最小生成树（A） 。A. 只有一棵 B.一棵或多棵 C.一定有多棵 D.可以不存在9.无向图顶点v 的度是关联于该顶点B）的数目。A. 顶点 B.边 C.序号 D.下标10.有 n 个顶点的无向图的邻接矩阵是用（B）数组存储。A. 一维 B.n行 n 列 C.任意行 n 列 D.n行任意列11.对于一个具有n 个顶点和 e 条边的无向图，采用邻接表表示，则表头向量大小

47、为（C） 。A.n-1 B.n+1 C.n D.n+e 12.在图的表示法中，表示形式唯一的是（A） 。A. 邻接矩阵表示法 B. 邻接表表示法 C. 逆邻接表表示法 D. 邻接表和逆邻接表表示法13.在一个具有n 个顶点 e 条边的图中，所有顶点的度数之和等于（C） 。A.n B.e C.2n D.2e v1 1 a a v2 v3 2 3 b c b c e e v4 v5 4 5 d f d f 图 8-23 度为 3 的结点图 8-24（15）题图 8-25 从顶点 a 出发图 8-26 优先遍历14.图 8-23 中，度为 3 的结点是（ B） 。A.V1 B.V2 C.V3 D.V

48、415.图 8-24 是（A） 。A. 连通图 B.强连通图 C.生成树 D.无环图16.如图 8-25 所示，从顶点a 出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D） 。A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 17.如图 8-26 所示，从顶点a 出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A） 。A.a,b,e,c,d,f B.a,b,e,c,f,d C.a,e,b,c,f,d D.a,e,d,f,c,b 18.最小生成树的构造可使用（A）算法。A.Prim 算法 B.卡尔算法 C.哈夫曼算法 D

49、.迪杰斯特拉算法19.下面关于图的存储结构的叙述中正确的是（A） 。A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C.用邻接存储图，占用空间大小只与图中顶点数有关，而与边数无关D.用邻接存储图，占用空间大小只与图中边数有关，而与顶点数无关20.连通分量是（ C）的极大连通子图。A.树 B.图 C.无向图 D.有向图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 45 页 - - - -

50、 - - - - - 20 第 9 章 查找一、判断题1.二分查找法要求待查表的关键字值必须有序。（）2.对有序表而言采用二分查找总比采用顺序查找法速度快。（）3.在二叉排序树中，根结点的值都小于孩子的结点的值。（）4.散列存储法的基本思想是由关键字的值的决定数据的存储地址。（）5.哈希表是一种将关键字转换为存储地址的存储方法。（）6.选择好的哈希函数就可以避免冲突的发生。（）7.在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（）8.采用分块查找，既有实现线性表所希望的查找速度，又能适应动态变化的需要。（）9.哈希查找的效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法