必看数据结构期末复习题及部分答案解析.doc

0一是非题1. 数据构造(应该是抽象数据类型)可用三元式表示D，S，P。其中：D是数据对象，S是D上的关系，P是对D的根本操作集。(f)2 简单地说,数据构造是带有构造的数据元素的集合。(t)3 判断带头结点的非空循环单链表头指针为L中指针p所指结点是最后一个元素结点 的条件是：p->next=L。(t)4 线性表的链式存储构造具有可直接存取"表中任一元素的优点。(f)5 线性表的顺序存储构造优于链式存储构造。(f)6. 在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next;。(顺序弄反了)(f)7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t)8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f)9. 栈和队列是操作上受限制的线性表。(t)10. 队列是与线性表完全不同的一种数据构造。栈和队列是操作上受限制的线性表(f)11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进展。对列不是(f)12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进展操作。(f)13. 栈是限定仅在表头进展插入和表尾进展删除运算的线性表。(f)14. 二叉树中每个结点有两个子结点，而对一般的树，那么无此限制，所以，二叉树是树的 特殊情形。(f)15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f)16 赫夫曼树中结点个数一定是奇数。(t)17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t)18 假设B是一棵树，B是对应的二叉树。那么B的后根遍历相当于B的后序遍历后根遍历相当于中序遍历。(f)19. 通常，二叉树的第i层上有2i-1个结点。应该为12i-1个(f)20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t)21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t)22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t)23 邻接多重表可以用以表示无向图，也可用以表示有向图。只能表示无向图，有向图用十字链表(f)24 可从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(f)25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)26 关键路径是AOE网中源点到汇点的最短路径。(f)27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f)28 一个无向图的连通分量是其极大的连通子图。(t)29 十字链表可以表示无向图，也可用以表示有向图。(f)30 邻接表可以表示有向图，也可以表示无向图。 t 31. 二叉排序树的平均查找长度为O(log)。(t)32. 二叉排序树的最大查找长度与LOG2N同阶。(f)33 选用好的HASH函数可防止冲突。哈希函数有几种处理冲突的方法(f)34 折半查找不适用于有序链表的查找。(t)35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f)37 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好(t)38 快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是On log n。(f)39. 字符串是数据对象特定的线性表。(t)40. 空串与空格串是一样的。(f)41. 对于一棵m阶的B-树.树中每个结点至多有m 个关键字.除根之外的所有非终端结点至少有m/2个关键字。(f)42. 当二叉排序树是一棵平衡二叉树时，其平均查找长度为O(log2n)。(t)43. 广义表的表头和表尾都是广义表。(f)44 二维数组是其数据元素为线性表的线性表。(t)选择题。1 从逻辑上可以把数据构造分成( c )。 A.动态构造和静态构造B.顺序组织和组织 C.线性构造和非线性构造D.根本类型和组合类型2 线性表L在( b )情况下适于使用链表构造实现。A. 不需修改L的构造 B. 需不断对L进展删除、插入C. 需经常修改L中结点值 D. L中含有大量结点3 带头结点的单链表L为空的判断条件是 b 。 带头结点的循环链表L为空的判断条件是 c 。A. L=nullB. L->next=nullC. L->next=L D. L!=null4 假设顺序表中各结点的查找概率不等，那么可用如下策略提高顺序查找的效率：假设找到指定 的结点，将该结点与其后继假设存在结点交换位置，使得经常被查找的结点逐渐移至 表尾。以下为据此策略编写的算法，请选择适当的容，完成此功能。 顺序表的存储构造为：typedef struct ElemType *elem; /数据元素存储空间，0号单元作监视哨 int length; /表长度 SSTable;int search_seq(SSTable ST,KeyType key) /在顺序表ST中顺序查找关键字等于key的数据元素。/假设找到，那么将该元素与其后继交换位置，并返回其在表中的位置，否那么为0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key)f;if( G ) ST.elemiST.elemi+1；e； return i;A. i>0 B. i>=0 C. i<ST.length D. i<=ST.lengthE. i+ F. i- G. A和C同时满足 H. B和D同时满足5 假设入栈顺序为A、B、C、D、E，那么以下( d )出栈序列是不可能的。AA、B、C、D、E BB、C、D、A、ECC、D、B、E、A DD、E、C、A、B6 递归程序可借助于( c )转化为非递归程序。 a.线性表 b.队列 c: 栈 d.数组 7 在以下数据构造中( c )具有先进先出FIFO特性，( b)具有先进后出(FILO特性。a线性表 b栈 c队列 d广义表8 假设对编号为1，2，3的列车车厢依次通过扳道栈进展调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,19 在计算递归函数时，如不用递归过程，应借助于( b ) 这种数据构造。 A.线性表B.栈C.队列D.双向队列10 假设带头结点的链表只设尾结点指针。以下选择中c最适用于队列。A单链表 B双向链表 C循环单链表 D双向循环链表11 栈和队列的一个共同点是( c )。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点12 循环队列用数组A0.m-1存放其元素值，设头尾指针分别为front和rear，那么当前队列中 的元素个数是( c )。 A. rear-front-1B. Rear-front+1 C.(rear-front+m)%mD. Rear-front13 如下关于串的述中，正确的选项是( a, c )。A. 串是数据元素类型特殊的线性表 B. 串中的元素是字母C. 串中假设干个元素构成的子序列称为子串 D. 空串即为空格串14 对字符串s=data-structure 执行操作replace(s,substring(s,6,8),bas)的结果是 ( b ) 。a: database b: data-base c: bas d: data-basucture 1 5 设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址.A的起始地址为100。那么按行存储时，元素A06的第一个字节的地址是d 按列存储时，元素A06的第一个字节的地址是 a a: 220 b: 200 c: 140 d: 12416对广义表 A=a,(b),(c,(),d执行操作gettail(gethead(gettail(A)的结果是： b 。a: b: c: d d: (d)17 假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32,14。 假设为这6个字母设计哈夫曼编码设生成新的二叉树的规那么是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右，那么频率为7的字符编码是 g ，频率为32的字符编码是 c 。a: 00 b: 01 c: 10 d: 11e: 011 f: 110 g: 1110 h:111118 对二叉排序树 c 可得到有序序列。a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历19 设一棵二叉树BT的存储构造如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B C D E F G Hrchild 0 5 4 0 87 0 0 其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。那么 该二叉树的高度为( d )； 第3层有( a )个结点根结点为第1层。 A2 B. 3 C. 4 D. 520 先序遍历图示二叉树可得到 a 的序列。 (A) (B) (C) (H) (D) (G) (E) (F) (I) a)A B H D E F I C G b)H B E D F I A C G c) H E I F D B G C A21 在有n个结点的二叉树的二叉链表表示中，空指针数为 n+1;非空指针树为 n-1; b 。 a.不定 b.n+1 c.n d.n-122 假设某二叉树有20个叶子结点，有20个结点仅有一个孩子，那么该二叉树的总结点数是( c )。度为2的节点n2 = n0 1;其中no表示度为0的节点 A40 B. 55 C. 59 D. 6123 某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，那么该二叉树的后序遍历次序为 c 。层次遍历次序为 a 。a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba.24 图示的三棵二叉树中( c)为最优二叉树。 A) B) C) ca 2 7abcddb 7 5 2 4 4 5 a bcd 7 5 2 425 某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。那么其先序遍历次序为 b ，层次遍历次序为 a 。a: abcdefg b: abdcefg c: abcdfeg d: abcdegf26 某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。假设将该树转换为二叉树,其后序遍历次序为 d 。a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba27 设x和y是二叉树中的任意两个结点，假设在先根序列中x在y之前，而在后根序列中x在y之后，那么x和y的关系是( c )。A. x是y的左兄弟 B. x是y的右兄弟C. x是y的祖先D. x是y的子28 用三叉链表作二叉树的存储构造，当二叉树中有n个结点时，有( d )个空指针。A. n-1 B. n C. n+1 D. n+229 对一棵完全二叉树进展层序编号。那么编号为n的结点假设存在右孩子,其位序是( d )。 编号为n的结点假设存在双亲,其位置是( a )。a:n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)30 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，那么与 森林F对应的二叉树根结点的右子树上的结点个数是( d )。A. m1B. m1+m2 C. m3 D. m2+m331 以下二叉树中，( a )可用于实现符号不等长高效编码。a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树32 邻接表存储构造以下图的深度优先遍历算法类似于二叉树的(a )遍历。A. 先根 B. 中根C. 后根 D. 层次33 设无向图G = (V,E)和G= (V,E)，假设G是G的生成树，那么下面不正确的说法是( b )。 A. G是G的子图B. G是G的连通分量极通子图称为连通分量 C. G是G的无环子图 D. G是G的极小连通子图且V= V34 任何一个连通图的最小生成树( b )。最小生成树其实是最小权重生成树的简称 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 e f e f35 深度优先遍历图使用了数据构造b ，而广度优先遍历图使用了数据构造 c 。A数组 B栈 C队列 D线性表36 某有向图的邻接表存储构造如下图。0 E 2 1 1 D 0 3 4 2 C 43 B 1 2 0 4 A 2 根据存储构造依教材中的算法其深度优先遍历次序为 d 。广度优先遍历此序为 c 。各强连通分量的顶点集为 h 。有向图的极大强连通子图，称为强连通分量a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc及ed f: bc及aed g: ab及ced h: ac及bed37 以下查找方法中 a 适用于查找单链表。 A顺序查找 B折半查找 C分块查找 Dhash查找38 以下算法中c普利姆算法适用于求图的最小代价生成树。b能对图作广度优先遍历。ADFS算法 BBFS算法 CPrim算法 DDijkstra算法39 关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点 c 的路径。a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小40 希表的查找效率取决于 d 。a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是41 在Hash函数H(k)=k MOD m中，一般来说，m应取( c )。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数42 在顺序表查找中，为防止查找过程中每一步都检测整个表是否查找完毕， 可采用a方法。A.设置监视哨 B.链表存贮 C.二分查找 D.快速查找43 静态查找表和动态查找表的区别在于( b )。A. 前者是顺序存储，而后者是链式存储B. 前者只能进展查找操作，而后者可进展查找、插入和删除操作C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序44 在一个含有n个元素的有序表上进展折半查找，找到一个元素最多要进展( b )次元素 比拟。 Aëlog2(n)ûB. ëlog2(n)û+1 C. ëlog2(n+1)û D. ëlog2(n+1)û+145 设输入序列为20,45,30,89,70,38,62，19依次插入到一棵2-3树中(初始状态为空)，该B-树为 b 。再删除38，该B-树为 f 。 30 62 45 19，20 38 45 70，89 30 70 19 20 38 62 89 a: b: 45 70 45 20 62 89 20 70 19 30 19 ( 30,38 62 89 c: d: 30 70 45 19，20 45 62 89 20 70 19 30 62 89 e: f:46根据插入次序80，90，100，110，85，70，75，60，72建立二叉排序树。 图a是最终变化的结果。假设仍以该插入次序建立平衡二叉树。图c是最 终变化的结果。80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b:90 90 75100 80 100 7080 110 75 70 85 110 60 72 85 60 72 c: d:47 假设有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。画出二叉判定树计算，关键字在第几层，就经过几次比拟对其进展 折半查找，那么在等概率情况下，查找成功时的平均查找长度是( c )。查找32时需进 行( c )次比拟。A.1B.2C.3D.448 哈希表地址空间为A9，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突指加数为1。 假设依次将数据序列：76,45,88,21,94,77,17存入该散列表中，那么元素17存储的下标为( h )； 在等概率情况下查找成功的平均查找长度为( c )。 A.0B.1 C.2 D.3 E. 4 F. 5 G. 6 H. 749 假设从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序， 那么该二叉树是( c )。 A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树50 当待排序序列的关键字次序为倒序时，假设需为之进展正序排序，以下方案中( d )为佳。 A.起泡排序B.快速排序 C.直接插入排序D.简单项选择择排序51 以下排序算法中，( d)算法可能会出现：初始数据有序时，花费的时间反而最多。 A. 堆排序 B. 起泡排序 C. 归并排序 D. 快速排序52 在以下排序方法中， c快速排序方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)； d 方法所有情况下时间复杂度均为0(nlogn)。a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 53 一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42以下选择中 d 是快速排序一趟排序的结果。 c 是希尔排序初始步长为3一趟排序的结果。 a 是初始堆大堆顶。 A86,75,77,58,42,19,56,35,48,26. B26,56,35,75,19,77,58,48,42,86. C35,26,19,42,58,48,56,75,86,77. D42,26,48,35,19,56,77,58,75,86.三填空题1 数据构造通常有以下4类根本构造：集合、线性构造 、树型构造、图型构造。2 设单链表中结点形式为 data next ，假设单链表长度大于等于2，指针p指向表中某个结点且p->next非空，此时假设要删除指针p所指的结点，可以通过如下方法进展：将p所指结点的后继的元素值复制到该结点，然后删除其后继结点。相应的语句序列为：p->data = p->next->data; p->next = p->next->next; free(p ->next)换指针的同时还要交换数据3 线性表的顺序存储构造是以数组下标来表示数据元素之间的逻辑关系的。4 P是单链表中某一结点的指针，P既不是首元结点也不是尾元结点，Q是P 的 前驱 结点指针。当删除P结点时，链表的可用语句 q->netx = p->next 实现。5 某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。假设将该树转换为二叉树,其后序遍历次序为 。层次遍历次序为 。6 某二叉树的先序遍历次序为afbcdeg后序遍历次序为cedbgfa。其后序遍历次序为 。层次遍历次序为 。7 在二叉树的第i层上至少有_1_个结点, 至多有_2_个结点 ,深度为k的二叉树至多有_2_-1_个结点.8 对树的遍历有先序遍历树和后序遍历树。假设以二叉链表作树的存储构造, 那么树的先序遍历可借用二叉树的遍历算法来实现, 而树的后序遍历可借用二叉树的中序遍历遍历算法来实现。9 设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少 是2*h - 1，至多是满树。10 对任何一棵二叉树T,假设其终端结点数为n0.度为2的结点为n2,那么n0与n2的关系为 ( n0 = n2 +1 )。11 如果对完全二叉树中结点从1开场按层进展编号，设最大编号为n；那么，可以断定编 号为i (i>1)的结点的父结点编号为( i/2向下取整 )；所有编号 i>n/2的结点为叶子结点。 12 n个顶点的连通图至少有条边，至多有n*(n-1)/2条边，此时即是完全图条边。13 对于图的存储构造有 数组表示法 、 邻接表法 ( 十字链表法 ) ( 邻接多重表法 )等方法。14 在一个无向图的邻接表中，假设表结点的个数是m，那么图中边的条数是_m/2_条。15 假设有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进展折半查找，那么在等概率情况下，查找成功时的平均查找长度是 。查找99时需进展 次比 较。16 在哈希表中，处理冲突的方法有开放定址法， 再哈希表法 ，链地址法等。17 在二叉树的第i层上至少有_个结点, 至多有_个结点 ,深度为k的二叉树至多有个结点.18 对于一棵高度为K的二叉排序树，结点数最少可有个，最多可有个。19 用中序遍历遍历对二叉排序树进展访问可得到有序序列。20 Hash函数为 HK=K mod 13 ，散列地址为0 -14，用二次探测再散列 处理冲突，关键字23，34，56，24，75，12，49,52，36，92 的分布如图，那么平均成功的查找长度为 、平均失败的查找长度为 。0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634232475124921 一棵阶的-树，第一层至少有一个结点；第二层至少有2个结点， 除根之外的所有非终端结点至少有 棵子树， 树中每个结点至多有 棵子树。22 在哈希表中，处理冲突的方法有开放定址法， ， , 。23 哈希表的查找效率取决于 哈希函数是否均匀； 处理冲突的方法； 哈希表的装填因子 。24高度为4 (包含不带关键字的叶子结点层)的7阶B树最少有个关键字，最多有_个关键字；如果其中的某结点正好有2个儿子，那么，该结点必定是结点。25 对n个元素的序列进展部排序，假设用起泡排序法，最少的比拟次数是n-1，最多的比拟次数是n(n-1)/2。25 (算法填空)Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)/先序非递归遍历二叉树。Initstack ( S ); Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )&& _p_ ) if (!Visit (p->data ) ) return ERROR;_push(s,p->lchild)_ ;Pop ( S , p );if (_(!stackempty(s) _ ) _ pop(S, p); push( S, p->rchild );return ok;26 (算法填空)以下算法试图完成在数组A中搜索有无关键字key，假设有，返回数组下标,假设无，返回-1。在"处填上适宜的容,完成该算法。int BinarySearch (keytype A , int low,int high, keytype key )while (low <= high) middle = (low+high) /2;if (Amiddle = key) return middle;if (key < Amiddle)high = middle -1;else low = middle + 1;return -1; /end of BinarySearch27 (算法填空)以下函数为堆排序中的堆调整过程调整H.rs的关键字，使H.rs.m成为一小顶堆。请在"处填上适宜的容,完成该算法。Void heapadjust( heaptype H , int s , int m ) rc=H.rs;for (j=2*s;j<=m;j*=2) if (j<m && rj+1>rj ) +j;if ( rc > H.rj ) break;H.rs=H.rj; s=j;H.Rs = rc ;/heapadjust图示构造题1 在电文中只出现频率为 ( 5,26,7,23,20,19 )的个字符， 画出你建的哈夫曼树，并给出其哈夫曼编码。2.某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG请画出该二叉树，并为之建立先序线索没有左子树，那么建立该节点的前驱，假设没有右子树，这指向该节点的后继。3 某二叉树的先序遍历次序为：a,b,c,d,e,f,g.中序遍历次序为：b,a,d,f,e,g,c 画出该二叉树，并在该二叉树上建立中序线索。4 某二叉树的中序遍历次序为BEGFDAC， 先序遍历次序为ABDEFGC。 试画出该二叉树，并为之建立中序线索图示之。5 某二叉树的后序遍历和中序遍历次序分别为FBEDGCA和FBADECG，请构造并画出该二叉树。6 设某一电文只出现a,b,c,d,e,f,g 7个字母；出现频率分别为30%,10%,05%,04%,13%,18%及20%，请给出各字母的哈夫曼编码。7 将图示森林转换为二叉树，并对该二叉树先序全序线索化。hdajibfecmlkg8 将图示森林转换为二叉树，并对该二叉树中序全序线索化。5619783249 某二叉树的结点数据采用顺序存储表示如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1819ABC D E  F   GH    I1试画出此二叉树的图形表示。2将此二叉树看作森林的二叉树表示，试将它复原为森林。10 某有向图如下图：a1给出其十字链表存储构造2给出其深度优先遍历次序。3给出其广度优先遍历次序。cb4给出各强连通分量。ed11 设输入序列为20,45,30,89,70,38,62,19，依次插入到一棵2-3树中(初始状态为空)，请画出该B-树。12 右图为一棵3阶B树。 20，251)画出在该树上插入元素15