数据结构练习题1.pdf

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

1、一、选择题1.下面说法错误的是一 c _。(1)算法原地工作的含义是指不需要任何额外的辅助空间。(2)在相同的规模n下，复杂度O(n)的撒在时间上总是优于复杂度0(2。)的算法。(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。(4)同一个算法，实现语言的级别越高，执行效率越低。A、(1)B、(1)(2)C、(1)(4)D、(3)2.一个递归算法必须包括_ _B _。A、递归部分 B、终止条件和递归部分C、迭代部分 D、终止条件和迭代部分3.数据的_ C _ 包括查找、插入、删除、更新、排序等操作类型。A、存储结构 B、逻辑结构C、基本运算 D、算法描述4.在数据结构中，从逻辑上

2、可以把数据结构分成_A、动态结构和静态结构 B、紧凑结构利非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5.与数据元素本身的形式、内容、相对位置、个数无关的是数据的_CA、存储结构 B、存储实现C、逻辑结构 D、运算实现6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着一 B_。A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7.以下说法正确的是_ _D _ A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同

3、的数据可以有相同的逻辑结构8.以下说法错误的是上_ oA、程序设计的实质是数据处理B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C、运算实现是完成运算功能的算法或这些算法的设计D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然9.下列程序段的时间复杂度为_Bx=n;y=o；while(x=(y+l)*(y+l)y=y+i;A、0(n)B、0(n1/2)C、0(1)D、0(n2)10.下列叙述中有关好的编程风格的正确描述是一C.。A、程序中的注释是可有可无的B、对递归定义的数据结构不要使用递归过程C、过程应是自封闭的，尽量少使用全程变量D、多采用一些技巧以提高程序

4、的运行效率二、填空题1.一个算法有5 个特性：有 穷 性、确 定 性、可行性、有零个或多个输入、有一个或多个输出。2.算法的时间复杂度是指该算法所求解问题_规 模(或 频 度)的函数。3.算法的可行性是指每一条_ 指令都应在有限的时间内完成4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有一旦仅有唯的个有接前趋和个仃接后继一。5 .数据的存储结构被分为一顺序、链 接、一 索 引 _ 和 _ 散 列 4 种。6.存储结构是逻辑结构的查僮实现，其基本目标是建立数据的一机 内 表 示 7.数据表示任务是逐步完成的，即数据表示形式的变化过程是：_机 外 表 示 f_ 逻辑结

5、构 f 存 储 结 构 o8.数据处理任务也是逐步完成的，即转化过程是：一处 理 要 求 一 基本运算_-_篁 返 9.从逻辑关系上讲数据结构主要分为两大类，它们是一线性结构 和一非 线 性 结 构。10.数据结构的基本任务是数据结构的一巡 L和一实现_。三、给出下列算法的时间复杂度。1、Sum(int n)int sum=0,i,j;for(i=l;i=n;i+)p=l;for(j=l;j=i;j+)P=P*j；sum=sum+p;return(sum);?T(n)=0(n2)2、j=l；while(jnext=p+l;pnext=s;B、(*p).next=s;(*s).next=(*p)

6、.next;C、snext=pnext;pnext=snext;D、snext=pnext;p-next=s;Ps图2-6插入结点示意6.在双向链表存储结构中，删 除 p 所指的结点时须修改指针 A _oA、pnextprior=p prior;ppriornext=pnext;B、pnext=pnextnext;pnextprior=p;C、pprioinext=p;pprior=ppriorprior;D、pprior=pnextnext;pnext=ppriorprior;7.在双向循环链表中，在 P 指针所指的结点后插入q 所指向的新结点，其修改指针的操作是 一 。A、pnext=q;

7、q prior=p;pnextprior=q;q next=q;B、pnext=q;pnextprior=q;q prior=p;q next=pnext;C、q prior=p;q next=pnext;pnextprior=q;pnext=q;D、q next=pnext;q prior=p;pnext=q;pnext=q;8.将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是 AA、n b.2n 1 c.2n d.n19.在一个长度为n 的顺序表中，在 第 i 个 元 素(l&i&n+l)之前插入一个新元素时须向后移动_ _B_ _ 个元素。A、ni B、ni+1 C、ni

8、 1 D、i10.线性表L=(ai，a2,an),下列说法正确的是A、每个元素有有一个直接前驱和一个直接后继B、线性表中至少有一个元素C、表中诸元素的排列必须是由小到大或由大到小。D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。11.对单链表表示法，以下说法错误的是_ _cA、数据域用于存储线性表的一个数据元素B、指针域(或链域)用于存放个指向本结点所含数据元素的直接后继所在结点的指针C、所有数据通过指针的链接而组织成单链表D、NULL称为空指针，它不指向任何结点只起标志作用12.若指定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是_ C_A、0(

9、1)B、0(n)A 0(n2)D、O(nlog2n)13.以 下 说 法 正 确 的 是_oA、顺序存储方式的优点是存储密度大且插入、删除运算率高B、链表的每个结点中都恰好包含一个指针C、线性表的顺序存储结构优于链式存储结构D、顺序存储结构属于静态结构而链式结构属于动态结构14.以下说法错误的是_ A_A、对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链中来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中15.以下说法错误的是_

10、DA、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B、序存储的线性表可以随机存取C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D、线性表的链式存储结构优于顺序存储结构二、判断题1.线性表采用链表存储时;结点和结点内部的存储空间可以是不连续的。（错）2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（错）3.顺序存储的线性表可以随机存取。（对）4.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（错）5.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（对

11、）6.顺序存储结构属于静态结构，链式结构属于动态结构。（对）3、简述以下算法的功能：status A（linkedist L）L 是无表头结点的单链表if（L&Lnext）Q=L;L=Lnext;P=L;while（Pnext）P=Pnext;Pnext=Q;Qnext=NULL;return ok;/A本程序实现的功能就是：如果L 的长度不小于2,则将首元结点删去并插入到末尾。4、写出下列程序段的输出结果。（假设此栈中元素的类型是char）void main()pop(s,x)stack s;push(s,H);char x,y;while(!stackEmpty(a)InitStack(a

12、)pop(s,y);x=,Lz y=O printf(y);push(s,x);)push(s,x);printf(x)push(s,y);)push(s,x);push(s,E);push(s,x);此题的输出结果是HELOLLL,5、以下为单链表删除运算，分析算法，请在_ _ _ _ _ _ _ 处填上正确的语句。void delete_lkist(lklist head,int i)p=find_lkist(head,i-l);if(p!=NULL)&(D-next!=NULL)q=Dnext;pnext=qnext;free(q);else error(不存在第i 个结点”)6、以下为

13、顺序表的定位运算，分析算法，请在_ _ _ _ 处用正确的语句予以填充。int locate_sqlist(sqlist L,data type X)0,；while(iLlast)&(Ldatai-l!=X)i+;if(iWL.Iast _)return(i);else return(O);7、以下为单链表的建表算法，分析算法，请在一处填上正确的语句Iklist create_lklist2()head=malloc(size);p=head;scanf(%f,%x);while(x!=$)q=malloc(size);qdata=x;pnext=q;p=q _；scanf(_ pnext=

14、NULL _;return(head);?此算法的量级为-0(n)习题三一、选择题1、若用单链表来表示队列，则应该选用一上A、带尾指针的非循环链表 B、带尾指针的循环链表C、带头指针的非循环链表 D、带头指针的循环链表2、若用一个大小为6 的数组来实现循环队列，且 当 rear和 front的值分别为。和 3。当从队列中删除个元素，再加入两个元素后，rear和 front的值分别是一上 一。A、1 和 5 B、2 和 4C、4 和 2 D、5 和 13、设栈的输入序列为1、2、3、4,则_ _ C _不可能是其出栈序列。A、1243B、2134C、1432D、4312E、32144、已知一算术

15、表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+D E/-,其前缀形式 为 _C _。A、-A+B*C/DE B、-A+B*CD/EC、-+*ABC/DE D、-4-A*BC/DE5、设栈的输入序列是1、2、n,若输出序列的第一个元素是n,则第i 个输出元素是一上一。A、不确定 B、n-i+1 C、i D、n-i6、假定一个顺序循环队列的队首和队尾指针分别用front和 rear表示，则判队空的条件是 _ 2 _。A、front+l=rear B、front=rear+lC、front=0 D、front=rear7、假定一个顺序循环队列存储于数组An中，其队首和队尾指针分别用fro

16、nt和 rear表示，则判断队满的条件是_ BA、(rear-l)%n=front B、(rear+l)%n=frontC、rear=(front-l)%n D、rear=(front+l)%n8、一个栈的的输入序列为12345,则下列序列中不可能是栈的输出序列的是_BA、23415 B、54132 C、23145 D、154329、若一个栈的输入序列是1、2、3、n,输出序列的第一个元素是i,则第i 个输出元素是_ _D _。A.i-j-1 B、i-j C、j-i+1 D、不确定10、用单链表表示的链式队列的队头在链表的_上一位置。A、链头 B、链尾 C、链中11、设计一个判别表达式中左、右

17、括号是否配对出现的算法，采用_ _D _ 数据结构最佳。A、线性表的顺序存储结构 B、队列C、线性表的链式存储结构 D、栈12、在下列算法描述中，涉及到队运算的算法是_ _D _oA、表达式求值算法 B、深度优先搜索C、二叉树遍历 D、广度优先搜索13、栈的插入和删除操作在一 A _ 进行。A、栈顶 B、栈底 C、任意位置 D、指定位置14、在一个顺序循环队列中，队首指针指向队首元素的 A _ 位置。A、前一个 B、后一个 C、当前 D、最后15、当利用大小为N 的数组存储顺序循环队列时，该队列的最大长度 为 卫A、N-2 B、N-l C、N D、N+116、如果以链表作为栈的存储结构，则退栈

18、操作时_ _C _oA、必须判别栈是否满 B、判别栈元素的类型C、必须判别栈是否空 D、对栈不作任何判别17、链栈与顺序栈相比有一个明显的优点，B P_ BA、插入操作更加方便 B、通常不会出现栈满的情况C、不会出现栈空的情况 D、删除操作更加方便二、填空题1、中绿式a+b*3+4*(c-d)对应的前缀式为+axb3x4-cd,若a=l,b=2,c=3,d=4,则后缀式 db/cc*a-b*+的运算结果为 _18_ _。2、用下标0 开始的N 元数组实现循环队列时，为实现下标变量m 加 1 后在数组有效下标范围内循环，可采用的表达式是m=(m+1)%n _ 3、表达式求值是_找一应用的一个典型

19、例子。4、队列是特殊的线性表，其特殊性在于_ 只允许在表的一端进行元素的插入而在另一端进行元素的删除_05、一个循环队列存于AM中，假定队首和队尾指针分别为front和 rear,则判断队空的条件为_ front=rear,判断队满的条件为(rear+1)%M=front _。6、向-一 个循环队列存入新元素时，需要首先移动 队 尾 指 针 然后再向它所指位置一在入一新元素。7、_又称为先进先出表。8、栈是特殊的线性表，其特殊性在于_ 只允许在栈顶加入或删除元素9、栈又称为 后进先出 表，队列又成为_先进先出 表。10、在一个用一维数组AN表示的顺序栈中，该栈所含元素的个数最少为_Q _个，最

20、多为_ _N_ 一 个。11、在一个用一维数组AN表示的循环队列中，该队列中的元素个数最少为0 个，最多为 N d.一个。习题四一、选择题1、设有两个串p 和 q，求 q 和 p 中首次出现的位置的运算称作一 C _A、连接 B、求子串 C、模式匹配 D、求串长2、若串S=good student,其子串的数目是_C _。A、12B、79C、78D、133、串是一种特殊的线性表，其特殊性体现在_B _。A、可以顺序存储C、可以链接存储4、串是任意有限个_ _DA、符号构成的集合C、字符构成的集合B、数据元素是个字符D、数据元素可以是多个字符B、符号构成的序列D、字符构成的序列5、已知模式串T=

21、abcdabcd,则其next数组值为_ _B_A,00123412 B、01111234C、01232412D、112134126、二维数组A 的每个元素是由6 个字符组成的串，其行下标i=0、1.8,列下标n个 X 110=9i-108n=9j-108kl,2.10。若 A 按行先存储，元素 A8,5的起始地址与当A 按列先存储时的元素的 B 的起始地址相同。设每个字符占一个字节。A、A8,5 B、A3,10 C、A5,8 D、A0,97、数组SZ-3.5O,0.10含有元素数目为 一 上 一 oA、88 B、99 C、80 D、908、稀疏矩阵般的压缩存储方法有_C _ 两 种。A、二维

22、数组和三维数组 B、三元组和散列表C、三元组和十字链表D、散列表和十字链表9、一个n x n 的对称矩阵，如果以行或列为主序放入内存，则其容量为_ CA、n x nn x n/2C、(n+1)x n/2D、(n+1)x(n+l)/2io、对数组经常进行的两种基本操作是_ cA、建立与删除 B、索引与修改C、查找与修改 D、查找与索引11、二维数组A1O.2O,5.10采用行序为主序方式存储，每个数据元素占4个存储单元，且A10,5的存储地址是1000,则A18,91的地址是 A。A、1208 B、1212 C、1368 D、1364二、填空题1、两个字符串相等的充分必要条件是_ 长度相等且对应

23、位置上字符相同,o2、字符在串中的位置，即是字符在该序列中的 序号。3、串是指_ 含n个字符的有限序列且n=0 4、设有串 S1=I an a student7,S2=,st,index(Sl,S2)=8 _5、含零个字符的串称为空一串，用 油 表示；其他串称为一韭空一串。任何串中所含的一包的个数称为该串的长度。6、一个串中任意个连续字符组成的子序列称为该串的一王串，该串称为它的所有子串的 一 串。7、设数组a1.50,L.80的基地址为2000,每个元素占2个存储单元，若一行序为主序顺序存储,则元素a45,68的存储地址为9174若以列序为主序存储,则元素a45,68的存储地址为_ 8788

24、 _ 8、数组结构是由固定数量的且由一个值和一组下标组成的数据元素构成，其元素间的下标关 系 具 有 上下界约束及下标有序。9、维数组的逻辑结构是线 性 结 构 存 储 结 构 是 顺序结构_；对二维或多维数组，分为按 以行为主序一 和 以列为主序_ 两种不同的存储方式。10、需要压缩存储的矩阵可分为_特 正 矩 阵 和 _场 置 矩 阵 两 种。11、数组元素间的关系由_ W 来限定。12、有一个8 x 8 的下三角矩阵A,若采用行序为主序顺序存储于一维数组a l.n,则 n的值为_ 3 6。三、判断题1、稀疏矩阵压缩存储后，必会失去随机存取的功能。（对）2、数组是同类型值的集合。（错）3、

25、数组是一种复杂的数据结构；数组元素之间的关系既不是线性的，也不是树形的。（对）习题五一、选择题1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_ _ C_ OA、所有的结点均无左孩子 B、所有的结点均无右孩子C、只有一个叶子结点 D、是任意一棵二叉树2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是一 E 一。A、250 B、500 C、254 D、505 E、以上答案都不对3、以下说法正确的是 CA、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子

26、树中序遍历序列中的最后一个结点C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点4、以下说法错误的是_ 。A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历并不能唯地确定这棵树，因为不知道树的根结点是哪一个D、在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的5、一棵有124个叶结点的完全二叉树，最多有_ A 一个

27、结点。A、247 B、248 C、249 D、250 E、2516、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序_ A _oA、不发生变化 B、发生变化 C、不能确定7、设 a、b 为一棵二叉树上的两个结点。在中序遍历时，a 在 b 前面的条件是 卫A、a 在 b 的右方 B、a 在 b 的左方C、a 是 b 的祖先 D、a 是 b 的子孙8、设深度为k 的二叉树上只有度为0 和度为2 的结点，则这类二叉树上所含的结点总数为 _,CA、k+1 B,2k C、2k-l D、2k+l9、设 有 13个值，用它们组成棵哈夫曼树，则该哈夫曼树共有_ D _ 个结点。A、13 B、

28、12 C、26 D、251 0,下面几个符号串编码集合中，不是前缀编码的是_ _BA、0,10,110,1111 B、11,10,001,101,0001C、00,010,0110,1000D、b,c,aa,ac,aba,abb,abc)11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用 _ 上 一存储结构。A、三叉链表 B、广义表 C、二叉链表 D、顺序表12、以下说法错误的是_ BA、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B、二叉树是树的特殊情形C、由树转换成二叉树，其根结点的右子树总是空的D、在二叉树只有一棵子树的情况下也要明确指出该子

29、树是左子树还是右子树13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面_ A 一是正确的。A、树的先根遍历序列与其对应的二叉树先序遍历序列相同B、树的后根遍历序列与其对应的二叉树后序遍历序列相同C、树的先根遍历序列与其对应的二叉树中序遍历序列相同D、以上都不对14、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。则该二叉树是_ _CA、二叉排序树 B、哈夫曼树 遍历树 c C、堆15、下列有关二叉树的说法正确的是_B_。A、二叉树的度为2 B、一棵二叉树度可以小于2C、二叉

30、树中至少有一个结点的度为2 D、二叉树中任一个结点的度都为216、某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是一旦A、EGFACDBB、EACBDGFC、EAGCFBD D、上面的都不对17对二叉排序树进行_ _B_ _ 遍历，可以得到该二叉树所有结点构成的排序序列。A、前序 B、中序 C、后序 D、按层次18、由二叉树的前序和后序遍历序列_ _B _ 唯一地确定这棵二叉树。A、能 B、不能19、在一棵度为3 的树中，度 为 3 的结点数为2 个，度 为 2 的结点数为1个，度 为 1 的结点数为2 个，则度为0 的结点数为一 个。A、4 B、5 C、6 D、720

31、、在一棵深度为h 的完全二叉树中，所含结点的个数不小于_D _ A、2h B、2h+1 C、2h-l D、2h-121、在一棵具有n 个结点的二叉树第i 层上，最多具有_ _ C _ 个结点。A、21 B、2i+1 C、2 4 D、2n22、在下列情况中，可称为二叉树的是一 BA、每个结点至多有两棵子树的树 B、哈夫曼树C、每个结点至多有两棵子树的有序树 D、每个结点只有一棵右子树E、以上答案都不对二、填空题1、8 层完全二叉树至少有_ .128 一个结点，拥 有 100个结点的完全二叉树的最大层数为一 7_ _2、树在计算机内的表示方式有_双 亲 表 示 法、一孩子表示法一、孩子兄弟表示法。

32、3、,棵有n 个结点的满二叉树有_ 0_ _ 个度为1 的结点，有_ n/2一 个 分 支（非终端）结点和 5/2+1 一个叶子，该满二叉树的深度为_ Hogzn+1 _。4、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是孩子树的一前 序 遍 历 序列中的最后个结点。5、一棵共有n个结点的树,其中所有分支结点的度均为k,则该树中的叶子结点个数为（nx（k-1）+1）/k。6、深度为k（设根的层数为1）的完全二叉树至少有2 k z l个结点，至多有_ 2 k-l个结点。7、设只包含根结点的二叉树高度为0,则高度为k的二叉树最大结点数为2 k+l-l,最小结点数为k+l。8

33、、棵完全二叉树有999个结点，它的深度为10 o9、对于一棵具有n个结点的树，该树中所有结点的度数之和为j v l o10、有n个结点并且其高度为n的二叉 树 有2 r v l个。11、一棵具有n个结点的二叉树，若它有n 0个叶子结点，则该二叉树上度为1的结点nl=_ n-2no+1 12、若一棵二叉树的叶子数为n 0,则该二叉树中左、右子树皆非空的结点个数为n Q z l。13、设n 0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2 n 0-l个结点。14、若以 4、5、6、7、8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是6 9。三、判断题1、完全二叉树的某结点若无左孩子，则它必是叶结

34、点。（对）2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。（对）3、二叉树就是结点度为2的树。（错）4、二叉树中不存在度大于2的结点，当某个结点只有棵子树时无所谓左、右子树。错）5、一知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一一 个。（错）6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（错）7、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（对）8、将一棵树转换成二叉树后，根结点没有左子树。（错）9、用树的前序遍历和中序遍历可以导出树的后序遍历。（对）10、哈夫曼树是带权路径长度最短的树，路径

35、上权值较大的结点离根较近。（对）11、不使用递归也能实现二叉树前序、中序和后序遍历。（对第二 部 分 判断题1、顺序存储方式的优点是存储密度大，且插入和删除运算效率高（错）2、循 环 队 列 中 无 上 溢 现 象（错）3、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置并不定紧邻。（错）4、栈和队列都是运算受限的线性表，只允许在表的两端进行运算。（错）5、数据元素是数据的最小单位。（错）6、顺序存储的线性表可以随机存储。（对）7、线性表采用顺序存储，必须占用一片连续的存储单元。（对）8、算法和程序没有区别，在数据结构中二者是通用的。（错）9、顺序存储结构方式只能用于存储线性结构。（错

36、）10、线性表的链式存储结构优于顺序存储结构。（错）11、线性表的链接存储，表中元素的逻辑顺序与物理顺序定相同。（错）12、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。（错）1 3、循环队列只有下溢，没有上溢。（错）1 4、如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。（对）1 5、在循环单链表中，任何一个结点的指针字段值都不可能为空。（时）1 6、空栈没有栈顶指针。（错）1 7、无论是顺序队列还是链接队列，插入、删除运算的时间复杂度都是0 （1）。（对）1 8、在表示稀疏矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关（错）1 9、线性表可以看成是广义

37、表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。（对）2 0、稀疏矩阵的特点是矩阵中元素较少。（错）第三部分填空题1、q l.m a xs i ze 为一个顺序存储的栈，变量t o p指示栈顶元素的位置。作进栈操作时必须判别 栈满 o如果要把栈顶元素取到x中，需执行下列语句：a+t o D l=x。2、带有表头结点的双链表L中，指 针P所指结点是第一个结点的条件是 L-n e xt=D o3、数据结构的三个要素是逻 辑 结 构、存储结构、操作。4、单链表中引入头结点的作用是 为了方便操作。5、算法的主要特性有：有穷性、确 定 性、可 行 性、输入和输出。6、设循环队列存放在向

38、量s q.d a t a 0 m中，队头指针s q.f r o n t在循环意义下的加1操作可用模运算表示为（s a.f r o n t+l）%（m+l）；若用牺牲个单元的办法来区分队满和队空的条件，则队满条件可以表示为（s a.r e a r+l）%（m +l）=s a.f r o n t8、可以仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点的链表有双向链及 和 循环链及。9、单链表中，指 针 p 所指结点为最后一个结点的条件是D-next=NULL。10、数据的逻辑结构包括线 性 结 构、树型结构 和图型结构 三种类型。11、对于长度为n 的线性表A L.n,插入和删除

39、一个元素的时间复杂度为 O（n）。12、用二 元 组（D,R）来表示数据结构，那么D 指 数据的集合,R 指这些数据之间的关系的第合 o13、一条语句重复执行的次数称为频度14、栈的运算主要有入栈、出栈、取栈顶元素、判断栈空、销毁栈 等儿种。15、在带头结点的单链表L 中，第一个元素结点的指针为L-next。16、为了最快的存取某元素，数据结构宜用顺序存储 结构；为了方便插入一个元素，宜 用 链 接 存 储 结构。17、带头结点的双链表为空的条件是head-next=NULL。18、在进栈运算时，应先判别栈是否为 满；作退栈运算时，应 先 判 别 栈 是 否 为 生。2.选择题线性表的顺序存储

40、结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A 随机存取B 顺序存取（：索引存取D 散列存取【解答】A,B【分析】参见2,2.1。线性表采用链接存储时，其 地 址（）。A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的D 连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。单循环链表的主要优点是（）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，能更好地保证链表不断

41、开。【解答】B（4）链表不具有的特点是（）。A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比【解答】A若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A顺 序 表B单 链 表C双 链 表D单循环链表【解答】A【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。（6）若链表中最常用的操作是在最后一个结点之后插入个结

42、点和删除第一个结点，则采用（）存储方法最节省时间。A单 链 表B带头指针的单循环链表C双 链 表D带尾指针的单循环链表【解答】D【分析】在链表中的最后个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是0（1），所以，答案是D。若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。A单 链 表B循环双链表C单循环链表 D带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表

43、都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。（8）在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A 0（1）B 0（n）C 0（n2）D O（nlog2n）【解答】B2.选择题线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A随机存取B顺序存取C索引存取D散列存取【解答】A,B【分析】参见2.2.1。线性表采用链接存储时，其 地 址（）。A必须是连续的 B部分地址必须是连续的C 一定是不连续的 D连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储

44、单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。单循环链表的主要优点是（）。A 不再需要头指针了B 从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。【解答】B（4）链表不具有的特点是（）。A可随机访问任一元素B 插入、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正比【解答】A若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A 顺 序 表 B 单 链 表 C 双 链 表 D 单循环链表【解答

45、】A【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。A单 链 表 B 带头指针的单循环链表C 双 链 表 D 带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第

46、个结点，其时间性能是。(1),所以，答案是D。若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用()存储方法最节省运算时间。A单 链 表B循环双链表C单循环链表 D带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。(8)在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。A 0(1)B 0(n)C 0(n2)D O(nlog2n)【解答】B习题六一、选择题1、

47、设无向图的顶点个数为n,则该无向图最多有_ _B 一 条边。A、n-1 B、n(n-1)/2 C、n(n+1)/2D、0 E、n22、在下列两种求图的最小生成树的算法中，一 _B 算法适合于求边稀疏的网的最小生成树。A、Prim B、Kruskal3、下面的叙述中不正确的是_ _B _ oA、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，将使整个工程提前完成C、所有关键活动都提前完成，则整个工程将提前完成D、某些关键活动若提前完成，将使整个工程提前完成4、采用邻接表存储的图，其深度优先遍历类似于二叉树的_ _B_A、中序遍历 B、先序遍历C、后序遍历 D、按层次遍历

48、5、采用邻接表存储的图，其广度优先遍历类似于二叉树的 A _。A、按层次遍历 B、中序遍历C、后序遍历 D、先序遍历6、具 有 n 个顶点的有向图最多有_ _B_ _ 条边。A、n B、n(n-1)C n(n+1)D、n27、个n 个顶点的连通无向图，其边的个数至少为 A。A、n-1 B、n C、n+1 D、nlog2n8、下列说法中，正确的有一工_。A、最小生成树也是哈夫曼树B、最小生成树唯一C、普里姆最小生成树算法时间复杂度为。(n2)D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。10、判定个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用一C _ oA、求关键路径

49、的方法 B、求最短路径的Dijkstra方法C、深度优先遍历算法 D、广度优先遍历算法11、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和 为 _A oA、s B、s-1 C、s+l D、n12、在一个无向图中，若两个顶点之间的路径长度为k,则该路径上的顶点数为_ BA、k B、k+1 C-.k+2 D、2k13、一个有n个顶点的无向连通图，它所包含的连通分量个数为_ BA 0 B、1 C n D、n+114、对于一个有向图，若一个顶点的入度为k l、出度k 2,则对应邻接表中该顶点单链表中的结点数为_ oA、k l B、k2 C、kl-k2 D、kl+k215、

50、对于一个有向图，若一个顶点的入度为k l、出度k 2,则对应逆邻接表中该顶点单链表中的结点数为一 A _oA、k l B、k2 C、kl-k2 D、kl+k216、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用_ B oA、顺序存储 B、链式存储C、索引存储 D、散列存储二、填空题1、具 有10个顶点的无向图，边的总数最多为 一 变o2、在 有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。3、克鲁斯卡尔算法的时间复杂度为-O(e,lo g 2 e)，它对撞显图较为适合。4、若一个连通图中每个边上的权值均不同，则得到的最小生成树是一唯二_ 的。5、深度优先搜索遍历类似于