数据结构复习题答案修订.docx

《数据结构复习题答案修订.docx》由会员分享，可在线阅读，更多相关《数据结构复习题答案修订.docx（19页珍藏版）》请在三一办公上搜索。

1、数据结构复习题答案修订一、填空题 1、根据需要，数据元素又被称为_ 元素 _、_ 结点 _、_ 顶点 _或 记录 。 2、在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 小于 该结点的值，右子树上所有结点的值一定 大于 该结点的值。 3、通常从 正确性 、 可读性 、 健壮性 、 高效性 等几方面评价算法的(包括程序)质量。 4、假定一棵二叉树的结点数为18，则它的最小深度为 5 ，最大深度为 18 。 5、顺序存储结构是通过 物理上相邻 表示元素之间的关系的;链式存储结构是通过 指针 表示元素之间的关系的。 6、在线性结构中,第一个结点 无 前驱结点,其余每个结点有且只有 1 个

2、前驱结点；最后一个结点 无 后续结点,其余每个结点有且只有 1 个后续结点。 7、在树形结构中，树根结点没有 前驱 结点，每一个结点只有一个 前驱 结点，称为 根结点 。 8、栈是 操作受限 的线性表，其运算遵循 后进先出 的原则。 9、哈夫曼树是带权路径度 长度最短 的树，通常权值较大的结点离根 较近 。 10、从数据结构的观点看，通常所说的数据应分成三个不同的层次，即数据 、 数据元素和 数据项。 11、一个运算的实现是指一个完成该运算功能的 程序 。运算实现的核心是处理步骤的规定，即 算法设计 。 12、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接 前驱 外，其他结点有

3、且仅有一个直接 前驱 ;除终端结点没有直接 后续 外，其它结点有且仅有一个直接 后续 。 13、顺序表的特点是 表中相邻的数据元素在内存中存储位置也相邻 。 14、栈的基本运算至少应包括 初始化 、进栈 、出栈、与 读栈 、判栈空五种。 15、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 1 和 3 。 16、对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“ 上溢 ”。 17、深度为k(k=1)的二叉树至多有 2k-1 个结点。 18、结点最少的树为 只有一个结点 ，结点最少的二叉树为 空二叉树 。 19、常见时间复杂

4、性的量级有：常数阶O( 1 )、对数阶O( log2n )、线性阶O ( n )、平方阶O( n2 )、和指数阶O( 2n )。 20、数据结构的三要素是指 数据元素、 逻辑结构 和 存储结构 。 21、二叉树由 根结点， 左子树 ， 右子树 三个基本单元组成。 22、向栈中压入元素的操作是先 存入元素 ，后 移动栈顶指针 。 23、一棵有n个结点的满二叉树有 0 个度为1的结点、有/2 个分支 结点和 /2 个叶子，该满二叉树的深度为 log2(n) +1。 24、通常从四个方面评价算法的质量：正确性、易读性、强壮性和高效性。 25、一个算法的时间复杂度为(n3+n2log2n+14n)/n

5、2，其数量级表示为o。 26、假定一棵树的广义表表示为A，H），则树中所含的结点数为9个，树的深度为3，树的度为3。 27、后缀算式9 2 3 +- 10 2 / -的值为-1。中缀算式-2Y/3对应的后缀算式为3 4 X * + 2 Y * 3 / -。 28、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有n-1个指针域是存放了地址，有n+1个指针是空指针。 29、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有e个和2e个。 30、AOV网是一种有向无回路的图。 3

6、1、在一个具有n个顶点的无向完全图中，包含有n*/2条边，在一个具有n个顶点的有向完全图中，包含有n* A.数据域用于存储线性表的一个数据元素 B.指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C.所有数据通过指针的链接而组织成单链表 D.NULL称为空指针，它不指向任何结点，只起标志作用 3、单链表中，增加头结点的目的是为了 ( C ) A.使单链表至少有一个结点 B.标示表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储实现 4、线性表若采用链表存储结构时，要求内存中可用存储单元的地址 ( D ) A.必需是联系的 B.部分地址必须是连续的

7、 C.一定是不连续的 D.连续不连续都可以 5、如果以链表作为栈的存储结构,则退栈操作时 ( C ) A.必须判别栈是否满 B.判别栈元素的类型 C.必须判别栈是否空 D. 队栈不做任何判别 6、深度为6的二叉树最多有( B )个结点 A.64 B.63 C.32 D.31 7、 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是 D。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 8、循环链表主要优点是 A.不再需要头指针了 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能

8、更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 9、下面关于线性表的叙述正确的是 ( A ) A.线性表采用顺序存储，必须占用一片连续的存储单元 B.线性表采用顺序存储，便于进行插人和删除操作 C.线性表采用链接存储，不必占用一片连续的存储单元 D.线性表采用链接存储，不便于插人和删除操作 10、带头结点的单链表Head为空的判定条件是 ( B ) A.Head=Null B.Head-next=NULL C.Head-next=Head 11、以下说法错误的是 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.

9、在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 12、以下说法错误的是 ( B ) A.用数字式计算机解决问题的实质是对数据的加工处理 B.程序设计的实质是数据处理 C.数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式 D.运算实现是完成运算功能的算法，或这些算法的设计 13、对于数据结构课程的主要内容，以下解释正确的是 A.数据结构的定义，包括逻辑结构、存储结构和基本运算集 B.数据结构的实现，包括存储实现、运算实现和基本运算集 C.数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择 14、一般地，一个存储结构包括以

10、下三个主要部分。以下说法错误的是 ( A ) A存储结点每个存储结点可以存放一个或一个以上的数据元素 B.数据元素之间关联方式的表示 也就是逻辑结构的机内表示 C.附加设施，如为便于运算实现而设置的“哑结点”等等 15、顺序存储结构 A.仅适合于静态查找表的存储 B.仅适合于动态查找表的存储 C.既适合静态又适合动态查找表的存储 D.既不适合静态又不适合动态查找表的存储 16、线性结构中的一个结点代表一个 A. 数据元素 B. 数据项 C. 数据 D. 数据结构 17、与数据元素本身的形式、内容、相对位置、个数无关的是数据的 A存储结构 B.存储实现 C.逻辑结构 D.运算实现 18、以下说法

11、错误的是 A.所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体 B.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的 C.数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域 D.数据项是数据的基本单位 19、对顺序表上的插入算法的时间复杂性分析来说，通常以为标准操作 A.条件判断 B.结点移动 C.算术表达式 D.赋值语句 20、单链表的一个存储结点包含 A.数据域或指针域 B.指针域或链域 C.指针域和链域 D.数据域和链域 21、在一棵高度为k的满二叉树中，结点总数为 C A2k-1 B2k C2k-1 Dlog2k+1 22、在完全二叉树中，

12、若一个结点是叶结点，则它没 C 。 A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点 23、下面哪一方法可以判断出一个有向图是否有环回路. B A广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 24、判定一个栈ST为空的条件是 B AST-top0 BST-top=0 CST-topm0 DST-top=m0 25、具有n(n0)个结点的完全二叉树的深度为 C 。 A. log2(n) B. log2(n) C. log2(n) +1 D. log2(n)+1 26、任何一个无向连通图的最小生成树 B A只有一棵 B. 一棵或多棵 C. 一定有多棵

13、 D. 可能不存在 27、在数据结构中，从逻辑上可以把数据结构分成 C A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 28、线性表采用链式存储结构时，其地址 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 29、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是： B Ap-next=s；s-next=p-next; B s-next=p-next；p-next=s; Cp-next=s；p-next=s-next; D p-next=s-next；p-next=s; 30

14、、如果以链表作为栈的存储结构，则退栈操作是 A.必须判别栈是否满 B.必须判别栈是否空 C.判别栈元素的类型 D.对栈不做任何操作 31、栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 32、用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 33、以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 34、设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676

15、(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 C A688 B678 C692 D696 35、树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 36、二叉树的第k层的结点数最多为( 2(k-1) ). A2k-1 B.2K+1 C.2K-1 D. 2k-1 37、若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3

16、38、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 C A. O B. O C. O D. O 39、对于线性表进行散列存储时，若选用H=K %9作为散列函数，则散列地址为1的元素有个， A1 B2 C3 D4 三、判断题 1、双链表中至多只有一个结点的后继指针为空。 2、对链表进行插入和删除操作时，不必移动结点。 3、栈可以作为实现程序设计语言过程调用时的一种数据结构。 4、线性表只能用顺序存储结构实现。( ) 5、“顺序查找法”是指在顺序表上进行查找的方法。 6、二叉树的遍历只是为了在应用中找到一种线性次序。( ) 7、二叉树中每个结点的两棵子树是有序的。( ) 8、向二叉排序

17、树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 9、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。( ) 10、在栈满情况下不能作进栈运算，否则产生“上溢”。 ( ） 11、栈和链表是两种不同的数据结构。 12、具有12个结点的完全二叉树有5个度为2的结点。 13、数据元素是数据的最小单位。 14、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 15、链表中的头结点仅起到标识的作用。 16、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。( ) 17、栈和队列的存储方式既可是顺序方式，也可是链接方式。( ) 18、一个有向图的邻接表和逆邻接表中

18、表结点的个数一定相等。 19、二叉树是度为2的有序树。( ) 20、程序一定是算法。( ) 21、在顺序表中取出第i个元素所花费的时间与i成正比。 22、在中序线索二叉树中，每一非空的线索均指向其祖先结点。( ) 23、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。( ) 24、线性表在物理存储空间中也一定是连续的。( ) 25、数据元素是数据的最小单位。( ) 26、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 27、由一棵二叉树的前序序列和后序序列可以唯一确定它。 28、二叉树是一般树的特殊情形。 29、顺序存储方式插入和删除时效率太低，因此它不如链式存

19、储方式好。 30、集合与线性表的区别在于是否按关键字排序。 四、简答题 1、假定一棵普通树的广义表表示为a(b(e)，c(f(h，i)，g)，d)，分别写出先根、后根、按层遍历的结果。 先根遍历：a b e c f h i g d 后根遍历：e b h i f g c d a 按层次遍历：a b c d e f g h i 2、设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 至少有14种 4321 3421 3241 3214 2431 2341 2134 2143 2314 1432 1324 1342 1234 1243 3、试

20、比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 顺序存储时，相邻数据元素的存放地址也相邻;内存中可用存储单元的地址必须是连续的。优点：存储密度 大 ，存储空间利用率高。缺点：插入或删除元素时不方便。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点 间关系的指针. 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小 ，存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入，删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除

21、操作，则采用链表。 4、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15， 画出用直接插入排序各趟的结果。 这个自己查 5、现有按中序遍历二叉树的结果为ABC，问有多少种不同形态的二叉树可以得到这一遍历结果，并分别画出这些二叉树？ 这个自己查 6、如何衡量hash函数的优劣？ 答：评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。 7、一棵树的形状如下图所示，分别求出它的根结点、叶子结点、结点H的度、这棵树的度、这棵树的深度、结点F的儿子结点、结点G的父结点？ 答：它的根结点是 A 叶子结点是

22、 EJKGLOPQRNI 结点H的度是 3 这棵树的度是 4 这棵树的深度是 5 结点F的儿子结点是 JK 结点G的父结点是 C 。 8、给定排序码(41，30，75，27，56，13，27，91，48)写出建立堆排序的过程。 这个自己查 9、假定一棵普通树的广义表表示为a(b(e,f)，c(g),d(h(m)，i,j)，分别写出先根、后根、按层遍历的结果。 这个自己查 10、已知数据序列为，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 这个自己查 11、画出以数据集4，5，6，7，10，12，18为叶结点的权值所构造的哈夫曼树？并求出其带权路径长度？ 问题一： 带权路径长度：6

23、3+73+122+44+54+103+182=18+21+24+16+20+30+36=165 12、一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(这题我自己写的，不一定正确，你们自己做) (1)第k层结点数(1kh)。M (2)整棵树结点数。/(m-1) (3)编号为i的结点的双亲结点的编号。 (i-1)/m +1 (4)编号为i的结点的第j个孩子结点(若有)的编号 *m+j 13、对如下图所示的二叉树进行遍历，分别画出先序、中序、后序线索二叉树的逻辑表示图。(自己做的)

24、 先序：ABDGECFHI 中序：DGBEACHFI 后序：GDEBHIFCA 14、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 它们出现的频度为： A - 9 B - 1 C - 5 D - 3 它们的最优编码为： A - 1 B - 000 C - 01 D - 001 15、 树和二叉树之间有什么样的区别与联系？ 答：树和二叉树逻辑上都是树形结构,树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为

25、空，树一般不允许为空.二叉树不是树的特例。 16、已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 答：用克鲁斯卡尔算法得到最小生成树为： 3，4，5，8，10，20 五、算法分析题 1、以下为求单链表表长的运算，分析算法，请在 _处填上正确的语句。 int length_lklist(lklist head) /*求

26、表head的长度*/ p=head ; j=0; while(p-next!=NULL) p=p_next; j+; return(j); /*回传表长*/ 2、阅读下列算法，写出其完整的功能。 Void reverse_list( LinkedListTP *head) LstackTP ls,p; 该算法的功能是：把一个LinkList倒序输出 DataType x; InitStack(&ls); p=head-next; While(p!=NULL) Push(&lsdata); p=p-next; p=head-next; While(! EmptyStack(&ls) Pop(&l

27、,&x); p-data=x; p=p-next; 3、以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ p=find_lklist(head,i-1); if(p=NULL)error(“不存在第i个位置”)； else s=malloc(size);s-data=x; s-next= p_next ; p-next=s; 4、阅读下列程序，写出程序的运行结果。 # define sqstack_maxsize 40 type

28、def struct sqstack char datasqstack_maxsize; int top; SqStackTp; main SqStackTp sq; int i; char ch; InitStack(&sq); For(ch=A;chtop=sqstack_maxsize-1error(“栈满”);return(0); elsesq-top+ : Sq-datasq-top =x; return(1); 6、分析下列算法段，并写出它的语句频度及时间复杂度 for 语句频度为： for (j=1;j=i;j+) for ( k=1;knext=NULL ; return(t)

29、; 8、以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(lklist head,int i) p=find_lklist(head,i-1); if(p!=NULL)&(p-next!=NLUU) q= p-next ; p-next=p-next; free(q); else error(“不存在第i个结点”) 9、以下运算实现在顺序栈上取栈顶元素，请在_处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) if( sq-top=0 ) return(0); else*x= sq-datasq-t

30、op ; return(1); 10、分析下面程序段中循环语句的执行次数 i:=0;s:=0;n:=100; 执行次数为：5次 while i:=i+1; s:=s+10*i; UNTIL (in) AND (sNEXT=S； (2) P-NEXT=S -NEXT； (3) S-NEXT= P-NEXT； (4) Q=P； (5) WHILE (P-NEXT!=Q) P= P-NEXT； (6) P=Q； (7) P=L； 答：(4),(7),(5),(3),(1) 12、LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L

31、；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： 说明语句S1的功能； 答：查询链表的尾结点 说明语句组S2的功能；答：将第一个结点链接到链表的尾部，作为新的尾结点 设链表表示的线性表为,写出算法执行后的返回值所表示的线性表。 答：返回的线性表为 13、void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatanext while(p!=NULL) if(s-datadata) break else q=

32、p p=p-next s-next=p; q-next=s; 2、编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。 答： void Insert1(List& L, int i, ElemType x) for(int j=L.size-1; j=i-1; j-) L.listj+1=L.listj; L.listi-1=x; L.size+; 3、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况给出相应的信息。 答； #define maxsize 栈空间容量 Void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和出栈的操作。 int top=0; /top为栈顶指针，定义top=0时栈为空。 for(i=1; idata=x)i+; P=p-next; /while,出循环时i中的值即为x结点个数 Return i; /CountX