《必看数据结构期末复习题及部分答案解析.doc》由会员分享，可在线阅读，更多相关《必看数据结构期末复习题及部分答案解析.doc（13页珍藏版）》请在三一办公上搜索。
1、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 对于插入、删除而言，线性表的链式存储优于顺序存储
2、。(t)8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f)9. 栈和队列是操作上受限制的线性表。(t)10. 队列是与线性表完全不同的一种数据构造。栈和队列是操作上受限制的线性表(f)11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进展。对列不是(f)12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进展操作。(f)13. 栈是限定仅在表头进展插入和表尾进展删除运算的线性表。(f)14. 二叉树中每个结点有两个子结点，而对一般的树，那么无此限制，所以，二叉树是树的 特殊情形。(f)15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f)16 赫夫
3、曼树中结点个数一定是奇数。(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 可
4、从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(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)
5、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)
6、。(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 假设顺序表中各结
7、点的查找概率不等，那么可用如下策略提高顺序查找的效率：假设找到指定 的结点，将该结点与其后继假设存在结点交换位置，使得经常被查找的结点逐渐移至 表尾。以下为据此策略编写的算法，请选择适当的容，完成此功能。 顺序表的存储构造为：typedef struct ElemType *elem; /数据元素存储空间，0号单元作监视哨 int length; /表长度 SSTable;int search_seq(SSTable ST,KeyType key) /在顺序表ST中顺序查找关键字等于key的数据元素。/假设找到，那么将该元素与其后继交换位置，并返回其在表中的位置，否那么为0。ST.elem0.
8、key=key;i=ST.length;while(ST.elemi.key!=key)f;if( G ) ST.elemiST.elemi+1；e； return i;A. i0 B. i=0 C. iST.length D. inext非空，此时假设要删除指针p所指的结点，可以通过如下方法进展：将p所指结点的后继的元素值复制到该结点，然后删除其后继结点。相应的语句序列为：p-data = p-next-data; p-next = p-next-next; free(p -next)换指针的同时还要交换数据3 线性表的顺序存储构造是以数组下标来表示数据元素之间的逻辑关系的。4 P是单链表中
9、某一结点的指针，P既不是首元结点也不是尾元结点，Q是P 的 前驱 结点指针。当删除P结点时，链表的可用语句 q-netx = p-next 实现。5 某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。假设将该树转换为二叉树,其后序遍历次序为 。层次遍历次序为 。6 某二叉树的先序遍历次序为afbcdeg后序遍历次序为cedbgfa。其后序遍历次序为 。层次遍历次序为 。7 在二叉树的第i层上至少有_1_个结点, 至多有_2_个结点 ,深度为k的二叉树至多有_2_-1_个结点.8 对树的遍历有先序遍历树和后序遍历树。假设以二叉链表作树的存储构造, 那么树的先序遍历可借用二叉树的遍历
10、算法来实现, 而树的后序遍历可借用二叉树的中序遍历遍历算法来实现。9 设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少 是2*h - 1，至多是满树。10 对任何一棵二叉树T,假设其终端结点数为n0.度为2的结点为n2,那么n0与n2的关系为 ( n0 = n2 +1 )。11 如果对完全二叉树中结点从1开场按层进展编号，设最大编号为n；那么，可以断定编 号为i (i1)的结点的父结点编号为( i/2向下取整 )；所有编号 in/2的结点为叶子结点。 12 n个顶点的连通图至少有条边，至多有n*(n-1)/2条边，此时即是完全图条边。13 对于图的存储构造有 数
11、组表示法 、 邻接表法 ( 十字链表法 ) ( 邻接多重表法 )等方法。14 在一个无向图的邻接表中，假设表结点的个数是m，那么图中边的条数是_m/2_条。15 假设有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进展折半查找，那么在等概率情况下，查找成功时的平均查找长度是 。查找99时需进展 次比 较。16 在哈希表中，处理冲突的方法有开放定址法， 再哈希表法 ，链地址法等。17 在二叉树的第i层上至少有_个结点, 至多有_个结点 ,深度为k的二叉树至多有个结点.18 对于一棵高度为K的二叉排序树，结点数最少可有个，最多可有个。19 用中序遍历遍历对二叉排序树进
12、展访问可得到有序序列。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 哈希表的查找效率取决于 哈希函数是否均匀
13、； 处理冲突的方法； 哈希表的装填因子 。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
14、( 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
15、) 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 (jrj ) +j;if
16、( 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，
17、 先序遍历次序为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 1819ABCDEFGHI1试画出此二叉树的图形表示。2将此二叉树看作森林的二叉树表示，试将它复原为森林。10 某有向图如下图：a1给出其十字链表存储构造2给出其深度优先遍历次序。3给出其广度优先遍历次序。cb4给出各强连通分量。ed11 设输入序列为20,45,30,89,70,38,62,19，依次插入到一棵2-3树中(初始状态为空)，请画出该B-树。12 右图为一棵3阶B树。 20，251)画出在该树上插入元素15
