数据结构期末复习总结计划思考题

《数据结构》复习思虑题一、基础题题目答案数据结构研究的主要内容是：非数值计算程序设计中数据的（①）和（②）以及它们之间（③）方法。①C①A.操作对象B.计算方法C.逻辑结构D.数据映像②D②A.计算方法B.数据映像C.分类方法D.储存结构③B③A.链接与关系B.关系与算法C.数据映像D.计算方法一棵含18个结点的二叉树的高度起码为()CA.3B.4C.5D.6算法剖析的主要目的是对（①）和（②）两个方面进行评论。①C①A.数据储存的合理性B.算法选择的简单性②AC.算法的空间复杂度D.算法过程的逻辑性②A.算法的时间复杂度B.算法选择的简单性C.算法的空间复杂度D.算法的正确性与简单性拥有屡次插入删除操作的线性表，应采纳（）储存结构效率较高。BA.矩阵B.链表C.数组D.结构无向图中一个极点的度是指图中()BA.经过该极点的简单路径数B.与该极点相毗邻的极点数C.经过该极点的回路数D.与该极点连通的极点数以下程序段的时间复杂度数目级为__________。O(log3nk=1;)while(k<=n){k=k*3;}从算法设计的简单性、时间复杂性和空间复杂性等多种角度考虑，你以为实现图深度优先遍历过程的控制，采纳（）作为算法协助储存结构最合B适。A.行列B.货仓C.单向环形链表D.双向循环链表一个栈的数据入栈次序为：ABCDE，指出不行能的出栈序列为（）。CA.EDCBAB.DECBAC.DCEABD.ABCDEhead为无头结点单向向后链表，判断head为空表的判断条件是（）AA．head==NULLB．head=0C．head-→data==0D．head→next==NULL循环行列定义为：intA[m];使用A[0]至A[m-1]A作为数据储存区，已知头尾指针分别为front和rear，表示行列中有效数据元素总数（一个正整数）的表达式是（）。A.（rear-front+m）%mB.rear–front+1C.rear–front-1D.(rear–front)%m带头结点的单链表head为空表的判断条件是（）。CA.head->next!=NULLB.head!=NULLC.head->next==NULLD.head==NULL一货仓数据进栈的序次为：1，2，3，4，5确立下述结果中错误的选项是（）。DA.5,4,3,2,1B.1,2,3,4,5C.2,3,1,5,4D.3,1,2,4,5依据数据元素的重点字能够直接确立记录素储存地点的方法称为（）。A．链接储存方法B．次序储存方法C．散列储存方法D．索引储存方法算法剖析的目的是（）。A．鉴识数据结构的合理性B．评论算法的效率C．研究算法中输入与输出的关系D．鉴识算法的可读性在线性表的以下运算中，不改变数据元素之间结构关系的运算是（）。A．插入B．删除C．排序D．定位在按层次遍历二叉树的算法中，借助（）协助数据结构比较适合。A．行列B．栈

CBDAC．线性表D．有序表在以下排序方法中，均匀时间性能为O(nlogn)且空间性能最好的是( )BA.迅速排序B.堆排序C.合并排序D.基数排序若用数组s[0..n-1]作为两个栈s1和s2的共用储存空间，且仅当s[0..n-1]全满时，各栈才不可以进前进栈操作。为这两个栈选择空间利用的最正确方案，问s1和s2栈顶指针的初值分别为（）能更好地利用供给的储存空间？A．1和n+1B．1和n/2C．－1和nD．－1和n+1假如求一个连通图中以某个极点为根的高度最小的生成树，应采纳（）。A．深度优先搜寻算法B．广度优先搜寻算法C．求最小生成树的prim算法D．拓扑排序算法栈和行列都是（）。A．限制存取地点的线性结构B．次序储存的线性结构C．链式储存的线性结构D．限制存取地点的非线性结构若用毗邻矩阵表示一个有向图，则此中每一列包含的″1″的个数为（）。A．图中每个极点的入度B．图中每个极点的出度C．图中弧的条数D．图中连通重量的数目在一个带权连通图G中，权值最小的边必定包含在G的（）中。A．最小生成树B．深度优先遍历树C．广度优先遍历树D．深度优先生成丛林假如在排序过程中，每次均将一个待排序的记录按重点字大小加入到前面已经有序的子表中的适合地点，则该排序方法称为（）。A．插入排序B．合并排序C．冒泡排序D．堆排序二、操作题题目答案对给定字符集和相应权重，结构Huffman树并确立每个字符的Huffman编码，给出huffman答案:树的带权路径长度。树的逻辑结构：节点ETADU权重1012794

CBABAA编码：U:000（3位）D:001（3位）e:01（2位）a:11（2位）t:10（2位）树的带权路径长度：97给定数据序列：6,3,9,5,7,8,2,1,4,12，按要求达成以下题目。答案：（1）结构排序二叉树，画出排序二叉树的逻辑结构；（1）二叉树的逻辑结构（2）给出该二叉树先序、中序和后序遍历的节点序列。（2）遍历结果先序：6-3-2-1-5-4-9-7-8-12中序：1-2-3-4-5-6-7-8-9-12后序：1-2-4-5-3-8-7-12-9-6（3）选作题参照答案使用左子树右下角节点替代使用右子树左下角节点替代对指定的二叉树，写出二叉树次序储存方式的节点次序（包含空位）、先根遍历的节点次序、中根答案:遍历的节点次序、后根遍历的节点次序。0123456789ABCDEFG10111213141516171819HIJ先序：ABDEGHCFIJ中序：DBGEHACIFJ后序：DGHEBIJFCA节点次序储存的节点次序012345678910111213141516171819先序：中序：后序：对给定的图，按要求达成以下题目。答案：（1）写出图的毗邻矩阵，毗邻表；（1）毗邻矩阵：（2）写出从节点V6出发深度优先与广度优先遍历的节点序列。结点12345611025223348456475毗邻表：出边结点1236233^4365^6145入边结点162131244656614（2）遍历结果：深度优先：v6—v1—v2—v3—v4—v5广度优先：v6—v1—v4—v5—v2—v3对以下无向连通图给出图最小生成树的逻辑结构；给出求解的操作过程，说明所依照的算法最小生成树：（结果的形式不独一）（克鲁斯卡尔，普利姆？）判断以下数据是不是堆？说明判断方法？数据以下：答案：5，23，16，68，94，72，71，73，是小根堆，按二叉树次序储存结构确立堆的逻辑结果，并判断：对以下无向连通图给出图最小生成树的逻辑结构，并写出从V1到其余各点最短路径的组成与路径答案：长度。（1）最小生成树：对给定的数据序列{19,01,23,14,55,20,84,27,68,11,10,77}，使用指定Hash函数和矛盾解决方法，写出数据序列的最后储存结果。Hash(key)=key%13使用线性探测再散列方法解决矛盾，在0-13地点空间内散列储存数据序列中数据012345678910111213对指定的图，写出全部可能的拓扑序列。

（2）最短路径v1-v2：3v1-v3：5v1-v4：4v1-v5：51-4-5v1-v6：4答案：01234567891111012311526128211745789043107答案：2—1—3—4—6—5已知带权图的毗邻表以下所示，按要求达成以下题目。答案：1）给出该图的逻辑结构；2）给出该图从V0出发深度优先遍历和广度优先遍历结果；3）写出从极点V0到其余各极点的最短路径。0123450∞1210∞301001∞∞∞∞∞∞2∞∞∞50∞∞3∞∞∞∞∞104∞∞∞20∞605∞∞∞∞∞∞深度优先遍历：V0—V1—V2—V3—V5—V4广度优先遍历：V0—V1—V2—V4—V5—V3单源最短路径：V0V1V0—V1：12V2V0—V2：10V3V0—V4—V3：50V4V0—V4：30V5V0—V4—V3—V5：60已知待散列的线性表为（36，15，40，63，22），散列用的一维地点空间为[0..6]，假设采纳的散答案：列函数是H（K）=Kmod7，若发生矛盾采纳线性探查法办理，按要求达成以下题目。（1）散列结果：（1）计算出每一个元素的散列地点并在以下图中填写出散列表；012340123456566336152240（2）求出在查找每一个元素概率相等状况下的均匀查找长度。（提示依据各个重点字的散列操作计算过程：次数计算均匀定位查找次数）。设一组记录重点字序列为（80，70，33，65，24，56，48），将数据序列调整为小根堆，写出获得数据序列，并给出小根堆二叉树的逻辑图。

H(36)=36mod7=1;H(15)=15mod7=1;矛盾H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;5)H(22)=22mod7=1;矛盾H１(22)=(1+1)mod7=2;矛盾H2(22)=(2+1)mod7=3;（2）ASL=121131.65答案：(24，65，33，80，70，56，48)原始二叉树：调整后的二叉树：已知二叉树的先序序列和中序序列分别为（1）画出该二叉树；

HDABCGFE

和ADCBHFEG

，按要求达成以下题目。

答案：（1）二叉树逻辑结构：2）给出二叉树后序遍历的结果；3）给出该二叉树次序储存的逻辑结构图。（2）后序遍历结果ACBDEFGH（3）次序储存结构图0123456789HDGABFC10111213141516E给出下述图所能组成的全部拓扑序列。答案：V0—V1—V2—V3—V4—V5V0—V2—V1—V3—V4—V5三、程序设计题目

答案达成知足下述要求的排序函数（填空或独立达成一个拥有同样方法功能的函数）

：

答案：intPartition（intr[],intlow,inthigh）{intkey;key=r[low];while(____(1)____)//从表的两头，向中间扫描{while(low<high&&r[high]>=key)high--;_____(2)______;//将小于key数据挪动到地区低段while(_________(3)_______)low++;_____(4)______;//将大于key数据挪动到地区高段}r[low]=key;returnlow;//返回定位key数据地点

IntPartition（intr[],intlow,inthigh）{intkey;key=r[low];while(low<high)//从表的两头，向中间扫描{while(low<high&&r[high]>=key)high