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

学而不思则惘，思而不学则殆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) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页学而不思则惘，思而不学则殆37 在最坏情况下，堆排序的时间性能是O(nlogn), 比快速排序好 (t) 38 快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O（n 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=null B. L-next=null C. L-next=L D. L!=null 4 若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。顺序表的存储结构为：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.elemi ST.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是单链表中某一结点的指针，P 既不是首元结点也不是尾元结点，Q 是 P 的 前驱结点指针。当删除P 结点时，链表的链接可用语句（q-netx = p-next ）实现。5 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。若将该树转换为二叉树,其后序遍历次序为（） 。层次遍历次序为（） 。6 已知某二叉树的先序遍历次序为afbcdeg 后序遍历次序为cedbgfa。其后序遍历次序为（） 。层次遍历次序为（） 。7 在二叉树的第i 层上至少有 _1_个结点 , 至多有 _2_i-1_个结点, 深度为 k 的二叉树至多有_2_i_-1_个结点 . 8 对树的遍历有先序遍历树和后序遍历树。若以二叉链表作树的存储结构, 则树的先序遍历可借用二叉树的遍历算法来实现, 而树的后序遍历可借用二叉树的中序遍历遍历算法来实现。9 设高度为h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点数至少是2*h - 1 ，至多是满树。10 对任何一棵二叉树T,若其终端结点数为n0.度为 2 的结点为n2,则 n0 与 n2 的关系为( n0 = n2 +1 )。11 如果对完全二叉树中结点从1 开始按层进行编号，设最大编号为n；那么，可以断定编精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 14 页学而不思则惘，思而不学则殆号为 i (i1) 的结点的父结点编号为( i/2 向下取整)；所有编号（in/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函数为H（K）=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 14 52 36 92 56 34 23 24 75 12 49 21 一棵阶的-树，第一层至少有一个结点；第二层至少有2 个结点，除根之外的所有非终端结点至少有（）棵子树，树中每个结点至多有（）棵子树。22 在哈希表中， 处理冲突的方法有开放定址法，, 。23 哈希表的查找效率取决于（ 哈希函数 是否均匀； 处理冲突的方法； 哈希表 的装填因子） 。24 高度为4 (包含不带关键字的叶子结点层)的7?阶?B?阶阶阶阶阶阶阶阶阶阶阶阶_阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶2阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶25阶n阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶n1阶阶阶阶阶阶阶阶阶nn12阶25阶阶阶阶SausPeodeaveseBeeTSaus*VsTeemypee阶阶阶阶阶阶阶阶阶阶阶nsackSPushSTWhesackempySWhegeopSp&_p_精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 14 页学而不思则惘，思而不学则殆 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 BinarySearch 27 (算法填空 ) 下列函数为堆排序中的堆调整过程（调整 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 ( rc H.rj ) break; H.rs=H.rj; s=j; H.Rs = rc ; /heapadjust 图示结构题1 已知在电文中只出现频率为( 5,26,7,23,20,19 )的个字符，画出你建的哈夫曼树，并给出其哈夫曼编码。2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA 和 BDACFEG 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 14 页学而不思则惘，思而不学则殆请画出该二叉树，并为之建立先序线索没有左子树， 则建立该节点的前驱，若没有右子树，这指向该节点的后继。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 将图示森林转换为二叉树，并对该二叉树先序全序线索化。8 将图示森林转换为二叉树，并对该二叉树中序全序线索化。9 某二叉树的结点数据采用顺序存储表示如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A B C D E F G H I （1）试画出此二叉树的图形表示。（2）将此二叉树看作森林的二叉树表示，试将它还原为森林。10 已知某有向图如图所示：1）给出其十字链表存储结构2）给出其深度优先遍历次序。3）给出其广度优先遍历次序。4）给出各强连通分量。a b d j c e h f g m l k i 1 2 4 3 5 9 6 7 8 b d e c a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页学而不思则惘，思而不学则殆11 设输入序列为 20,45,30,89,70,38,62,19 ，依次插入到一棵2-3 树中 (初始状态为空)，请画出该 B-树。12阶阶阶阶阶3阶B阶阶阶阶20阶25阶1阶阶阶阶阶阶阶阶阶阶15阶=阶阶阶B阶阶阶10阶14阶21阶阶35阶2阶阶阶阶阶阶阶阶35阶阶阶阶阶阶阶B阶阶阶13阶阶Hash阶阶阶H阶K阶=Kmod13阶阶阶阶阶阶014阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶56阶34阶68阶23阶16阶70阶48阶35阶83阶12阶14阶57阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶?0123456789101112131414阶阶阶阶阶阶阶20阶30阶70阶60阶10阶100阶110阶90阶80阶阶阶阶阶阶阶阶阶阶阶阶阶15阶阶阶阶阶阶16阶阶阶阶阶阶Hkey=keymod13阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶d=12阶12阶22阶22阶32阶32阶阶阶阶阶阶12阶阶阶阶56阶82阶17243621839613345750阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶16阶阶阶阶阶阶阶阶阶251292073124351710阶阶阶阶阶1阶阶阶阶阶阶阶阶阶阶阶阶阶阶2阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶3阶阶阶阶阶阶阶阶阶阶5阶阶阶阶阶阶阶阶阶1阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶ypedesucLNodendaasucLNode*nexLNode*LnkLs阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶2阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶X阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶?阶阶阶阶阶阶阶阶阶3阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶X阶阶阶NSERT阶阶阶阶阶阶4阶阶阶阶阶Delete(linklist&L阶X),阶阶阶阶阶阶阶阶阶阶X阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶阶ypedesucLNodendaasucLNode*nex精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页学而不思则惘，思而不学则殆 LNode, *Linklist; 5 写一算法， Contrary(linklist &L) ,对一带头结点且仅设尾指针L 的循环单链表就地逆置。 （即表头变表尾，表尾变表头。）6 已知线性表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。试写一高效的算法， 删除表中所有值大于mink 且小于 maxk的元素 （若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度。单链表结点的类型定义如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist; 7 写一算法，将带头结点的有序单链表A 和 B 合并成一新的有序表C。(注:不破坏 A 和 B 的原有结构 .)Merge(Linklist A, Linklist B, Linklist &C ) 8 写一算法 Oplinklist(linklist L,int i;int j ) 删除单链表中第i 个元素 ,并将之插入至原表中的第j 个元素之前 .9 写出求单链表长度算法int length(linklist L) 10 若将循环队列Q 的结构定义为：#define m 100 /最大队列长度typedef struct QElemType *base; /存储空间基址int rear; /尾指针，若队列不空，指向队尾元素int length;/当前队列的长度，即元素个数 SqQueue; 试写出相应初始化、入队列和出队列的三个函数。11 二叉树用二叉链表存储表示。typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 试编写销毁二叉树T 的算法 DestroyBiTree ( BiTree &T) 。12 二叉树用二叉链表存储表示。typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 试编写算法，求元素值为x 的结点的左孩子（返回x 的左孩子的指针） 。13 设计一算法，计算给定二叉树T 中度为 2 的结点个数。14 编一算法：按层序遍历二叉树T。15 试编写先序遍历二叉树T 的递归算法PreorderBiTree ( BiTree &T) 。16 写出一个将树中每个结点的左右孩子对换的算法SWAPTREE(T) 即如 : 原二叉树转换后T SWAPTREE(T) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 14 页学而不思则惘，思而不学则殆 (A) (A) / / (B) (C) (C) (B) / / / (D) (E) (F) (F) (E) (D) / / (G) (H) (H) (G) 17 二叉树用二叉链表存储表示。试编写后序遍历二叉树T 的递归算法PostorderBiTree ( BiTree T) 。18 写一个计算二叉树中叶子结点个数的递归算法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页