数据结构C++考试题及答案

1、 数据结构试题一一、单项选择题（每小题3分，共30分） 1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2n C、2n+1 D、2n-1 2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。 A、da，ax，eb，de，bbffha，gc B、cd，eb，ax，daffha，gc，bb C、gc，ax，eb，cd，bbffda，ha D、ax，bb，cd，daffeb，gc，ha 3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表 4、下列排序算

2、法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序 5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任意结点无左孩子 D、任意结点无右孩子6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的 是（ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序 7、快速排序算法在最好情况下的时间复杂度为（ ）。 A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)8、已知数据表 A中每个元素距其最终位

3、置不远，则采用（ ）排序算法最 省时间。 A、堆排序 B、插入排序 C、直接选择排序 D、快序排序9、带权有向图G用邻接矩阵 A存储，则顶点 i的入度为 A中（ ）。 A、第 i行非的元素之和 B、第 i列非的元素之和 C、第 i行非且非 0的元素之和 D、第 i列非且非 0的元素之和10、在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比 较次数的数量级为（ ）。 A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn) 二、判断题 （认为对的在题后的括号内打“”，错的打“”，每小题分，共10分） 1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先

4、搜索遍历可访问该图的每个顶点。 ( )2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。 ( )3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 ( )4、图G的最小生成树的代价一定小于其他生成树的代价。 ( )5、已知一棵树的先序序列和后序序列，一定能构造出该树。 ( )6、对一个堆按层次遍历，不一定能得到一个有序序列。 ( )7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。 ( ) 8、不管 ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Pu

5、sh(x,S) 的耗时均为 O(n)。 ( ) 9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入 上去，一定能得到原来的二叉排序树。 ( )10、快速排序是排序算法中最快的一种。 ( )三、填空题（每小题2分，共20分） 1、在双向循环表中，在 p所指的结点之后插入指针 f所指的结点，其操作为 ：_ _=p;fnext=pnext;_=f; pnext=f。 2、在有序表 A120中，采用二分查找算法查找元素值等于 A12的元素，所比较过的元素的下标依次为_。 3、若某串的长度小于一个常数，则采用_存储方式最节省空间。 4、在有 n个顶点的有向图中，每个顶点的度最大可达_。

6、 5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 _。 6、设键值序列为K1，K2，Kn,用筛选法建堆则必须从第_个元 素开始筛选。 7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_。 8、直接选择排序算法在最好情况下所作的交换元素的次数为_ _。 9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_比赛。 10、下列排序算法中， 占用辅助空间最多的是_( 堆排序， 希尔排序， 快速排序，归并排序)。四、简答题（每题10分，共60分） 1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间

7、复杂度各为多少？2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答以下问题：（1）设计一个适合该散列表的散列函数。（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多少？3、对 n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问（1）图中有多少条边？ （2）任意两个顶点 i和 j是否有边相连？ （3）任意一个顶点的度是多少？4、已知下面二叉排序树的各结点的值依次为19，请标出各结点的值。5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同

8、形态有哪些？ 6、分析以下程序段中语句x=x+y的执行次数。 x=0; y=0; for(int i=1;i=n;i+) for(int j=1;j=i;j+)for(int k=1;k=j;k+) x=x+y; 五、算法设计题（每题15分，共30分） 说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、 假设以二叉链表作为二叉树存储结构，其类型定义如下： typedef struct node char data; struct node *lchild,*rchild;/左右孩子指针 BinTNode,*BinTree; 写一函数，完成以下功能：对二叉树中每个结点，如果其左孩子

9、为空（右孩子不为空），则将其右孩子设置为左孩子。 2、 试设计将数组 A0n-1中所有奇数移到所有偶数之前的算法。要求不另增加存储空间且时间复杂度为O(n)。数据结构试题1参考答案一、15：DADAB 610：CCBDD二、15： 610： 三、 1、fprior， pnextprior 2、10 15 12 3、顺序压缩 4、2(n-1) 5、129 6、n/2的最小整数 7、(plchild=NULL)&(prchild=NULL)8、0 9、n(n-1) 10、归并排序 四、1、 答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链表 的删除时间复杂度为O(1)，单循

10、环链表删除p 结点的时间复杂度为O(n)。2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余 数法的模，则可得其散列函数为h(k)=k%11。 （2）若用线性探测法解决冲突，则可构造出散列表如下：1314 35 17 29 1530 1 2 3 4 5 6 7 8 9 1011 此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为： 3、 答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行 数值之和为总边数。邻接表表示无向图内部顶点个数除以 2，有向图内部顶 点个数。 （2）无向图中 I 行和 J 列的交叉点的值是否为 1。

11、有向图 I 行 J 列交叉点或 I列和 J行交叉点的值为1。 （3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数 值之和。 4答案：5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。具有3个结点的二叉树的形态为：5种形态，有左右之分。6：答案： 五、1、 答案： void exchange(Bin Tree T) if(T) if(!Tlchild&Trchild) Tlchild= Trchild; Trchild=NULL; exchange(Tlchild); exchange(Trchild); 2、 答案： int oddbefore(A,n)/将

12、数组 A0n-1中所有奇数移到所有偶数之前 int A ; int c,i,j; i=0;j=n-1;/初始化 i、j while(ij) while(Ai%2=1)&(ij) /Ai为奇数时，i向右扫描 i+; while(Ai%2=0)&(ij) / Ai为偶数时，j向右扫描 j-; if(in/2时，任何一个序列（k1，k2，kn）一定是堆。 （ ） 5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。 （ ） 6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。 （ ） 7、双循环链表中，任一结点的前驱指针均为不空。 （ ）

13、 8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复 杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 （ ） 9、如果有向图 G=(V，E)的拓扑序列不唯一，则图中必有两条弧和 存在。（ ）10、矩阵压缩存储的方法是用三元组表存储矩阵元素。 （ ）三、填空题（每小题2分，共20分） 1、设 sq1maxsize为一个顺序存储的栈，变量 top 指示栈顶元素的位置。作进栈操作时，必须判别_。如要把栈顶元素取到 x中，需执行语句_ _。 2、设一个二叉树共有50个叶结点（终端结点），则共有_个度为2的结点。 3、在单链表中，若要在指针p所指结点(data

14、，next)后插入指针s所指结点，则需要执行下列两条语句：snext=pnext;_。 4、3个结点可构成_棵不同形状的树。 5、利用直接选择排序算法对 n个记录进行排序，最坏情况下，记录交换的次数为 _6、如果含 n个顶点的图是一个环，则它有_棵生成树。 7、如果要将序列50，16，23，68，94，70，73建成堆，则只需把 16 与_ 相互交换即可。 8、在一棵高度为 h 的平衡二叉树中，最少含有_个结点，最多含有 2 h -1 个结点。9、假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中，其中 B0存储矩阵中第1个元素a11，则B31中存放的元素是_。 10、在

15、单链表上难以实现的排序方法有_和堆排序。 四、简答题（每题10分，共60分） 1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指 针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？2、 一项工程由P1、 P2、 、 P6六项子工程组成， 这些工程之间有下列关系： P1P2， P3P6，P4P3，P2P6，P4P5，P1P3，P5P6，符号“”表示“优于”关系，例如 P2P6，表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。3、设散列表长度为 14，散列函数 H(x)= 2 / i，其中 i为键值中第一个字母在字母表中的序号，若键值的输入顺序为

16、Jan，Feb，Mar，Apr，May，Jun，Jul，Aug， Sep，Oct，Nov，Dec，用拉链法处理冲突，要求： （1）构造散列表。 （2）求出在等概率情况下，查找成功的平均查找长度。 4、设下图所示的二叉树是由森林转化而成的，试将它还原为森林。 5、何为队列的“假溢出”现象？如何解决？ 6、分析以下程序段中语句x=x+y的执行次数。 x=0; y=0; for(int i=1;i=n;i+) for(int j=1;j=i;j+) for(int k=1;k=j;k+) x=x+y; 五、算法设计题（每题15分，共30分）说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。

17、1、设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。 2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min且小于 max的元素（若表中存在这样的元素）的算法。 数据结构试题2答案一、15：CDDBB 610：CBDAA 二、15： 610： 三、1、 栈是否满（或top=maxsize） x=sqtop 2、49 3、pnext=s; 4、2 5、n-1 6、n 7、50 8、h 9、A82 10、快速排序 四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表的删除时间复杂度为O(1)，单循环链表删除

18、p结点的时间复杂度为O(n)。2、答案：可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则，访问各个结点即可。 找出3个可能的施工顺序如下： P1，P2，P3，P4，P5，P6P1，P4，P2，P3，P5，P6P4，P5，P1，P2，P3，P6 3、答案：（1）：（2）ASL=（1*7+2*4+3*1）/12=5。 4、答案： 5、答案：队列的“假溢出”现象是指用数组实现的顺序队列中，对尾指针已达到数组的下标上界产生上溢而对头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间首尾相连。6、答案： 五、1、答案： int level(t,p)； bitree

19、*t,*p; int count; count=0; if(t=NULL) return(0); else count=count+1; while(tdata!=pdata) if(tdatapdata) t= trchild; else t= tlchild; count=count+1; return(count); 2、答案：delete(head,max,min) /删除有序单链表中所有值大于min且小于max 的元素 linklist *head; int max,min; linklist *p,*q; if(head!=NULL) q=head; p=headnext; whi

20、le(p!=NULL)&(pdatamax) p=pnext; qnext=p; 数据结构试题3一、单项选择题（每小题3分，共30分） 1、假设有 n个关键字，它们具有相同的Hash 函数值，用线性探测法把这 n个关键字存入到Hash地址空间中要做（ ）次探测。 A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2 2、若有一个栈的输入序列是 1，2，3，n 输出序列的第一个元素是 n，则第 i 个输出元素是（ ）。 A、n-i B、n-i-1 C、n-i+1 D、不确定 3、在一棵度为3的树中，度为 3的结点数为 2 个，度为2的结点数为 1个，度为1 的结点树为2个，那么

21、度为 0的结点数为（ ）。 A、4 B、5 C、6 D、7 4、在一个具有 n个结点的无向完全图中，包含有（ ）条边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2 5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需（ ）次比较可检索成功。 A、 1 B、2 C、3 D、4 6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（ ）。 A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序 7、已知 8 个元素（34，76，45，18，36，54，92，65），按照依次插

22、入结点的方法生成一棵二叉排序树，该树的深度为（ ）。 A、4 B、5 C、6 D、7 8、设有一个10阶的对称矩阵 A，采用压缩存储方式以行序为主存储，a00为第一个元素， 其存储地址为0，每个元素占有 1个存储地址空间，则a85的地址为 （ ）。A、13 B、33 C、17 D、32 9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为（ ）。A、6 B、7 C、8 D、20 10、给定权的集合15，3，14，2，6，9，16，17，所构造出的哈夫曼树的带权路径长度为（ ）。 A、129 B、219 C、189 D、229 二、判断题 （认为对的，在题后的括号内打

23、“”，错的打“”，每小题分， 共分） 1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 （ ） 2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。 （ ） 3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。 （ ） 4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法两个方面。 （ ） 5、因为算法和程序没有区别，所以在数据结构中二者是通用的。 （ ） 6、进栈操作 push(x,s)作用于链接栈时，无须判满。 （

24、） 7、稳定排序算法是最好的。 （ ） 8、二叉搜索树的左、右子树都是二叉搜索树。 （ ） 9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 （ ） 10、表中的每一个元素都有一个前驱和后继元素。 （ ） 三、填空题（每小题2分，共20分） 1、在散列表(Hash)查找中，评判一个散列函数优劣的两个主要条件是_和_。 2、设根结点处在第一层，那么具有 n 个结点的完全二叉树，其高度为_。 3、快速排序方法的最坏时间复杂度为_，平均时间复杂度为_。 4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为_。5、设图 G 的顶点数为 n，边

25、数为 e，各顶点的度数为 D(Vi)，则e=_。 6、将5个不同的数据进行排序，至少需要比较_次，至多需要比较_次。7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二分折半查找时，最大比较次数是_，最小比较次数是_。 8、由 a，b，c3 个结点构成的二叉树，共有_种不同的结构。 9、在一棵高度为 h 的平衡二叉树中，至少含有_个结点，最多含有 2 h -1 个结点。10、在一个单链表中删除*p 结点，应执行如下操作 ：q=pnext;pdata=pnextdata; pnext=_; free(q); 四、简答题（每题10分，共60分） 1、在单链表、双链表和单循环链表

26、中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？ 2、假设用于通讯的电文仅有 8 个字母组成，字母在电文中出现的频率分别为：7， 19，2，6，32，3，21，10。试用这8个频率值构造哈夫曼树，并画出该哈夫曼所对应的森林。3、已知一个长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec）： （1）构造最价二叉排序树； (2)试求在等概率情况下对此二叉排序树进行折半检索时检索成功的平均长度。 4、对于下图，试给出：（1）每个顶点的入度和出度； （2）邻接矩阵； （3）逆邻接

27、表； （4）强连通分量；5、快速排序、插入排序、自然两路归并排序、堆排序，哪一种排序方法所需的辅助空间最大？请简单说明。 6、分析以下程序段中语句x=x+y的执行次数。 x=0; y=0; for(int i=1;i=n;i+) for(int j=1;j=i;j+) for(int k=1;k=j;k+)x=x+y; 五、算法设计题（每题15分，共30分） 说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、 假设以二叉链表作为二叉树存储结构，其类型定义如下： typedef struct node char data; struct node *lchild,*rchild;

28、/左右孩子指针 BinTNode,*BinTree; 写一函数，完成以下功能： 对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子设置 为左孩子。 2、 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写 一个删除表中所有值大于 min且小于 max的元素 （若表中存在这样的元素） 的算法。 数据结构试题3答案一、15：CCCAB 610：DCBAD 二、15： 610： 三、1、 值均匀分布于表空间以减少冲突 函数尽可能简单以方便计算 2、logn的最小整数+1 3、O(n 2 ) O(nlogn) 4、(31 38 44 56 75 80 55 63)

29、或(80 75 55 56 63 44 31 38) 5、0.5*D(Vi)之和(in) 6、4 10 7、7 1 8、5 9、h 10、pnextnext 四、1、答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。 2、答案： （哈夫曼树有多种形态，不是唯一的。 ） （1）哈夫曼树为：（2）哈夫曼树所对应的森林为：3、答案：（1）（2）在等概率情况下检索成功的平均检索长度： ASL=（1*1+2*2+3*4+4*4+5*1）/12=38/12=19/63、 答案：（1）各个顶点的入度和出度如

30、下：顶点：1 2 3 4 5 6 入度：2 2 1 3 2 1 出度：1 2 3 0 3 2（2）邻接矩阵为： （3）逆邻接表为： （4）、强连通分量有如下3个：5、答案：快速排序需要的辅助空间与辅助栈的深度有关，平均情况下为O(logn),最坏情况下需要 O(n)；插入排序和堆排序只需要一个元素大小的辅助空间在元素交换时用,为O(1)；而自然两路归并排序需和待排序数组同样大小的辅助空间，为O(n)，所以自然两路归并排序所需的辅助空间最大，快速排序次之，插入排序和堆排序最小。 6、答案：五、1、答案： void exchange(Bin Tree T) if(T) if(!Tlchild&Tr

31、child) Tlchild= Trchild; Trchild=NULL; exchange(Tlchild); exchange(Trchild); 2、答案： delete(head,max,min) /删除有序单链表中所有值大于min且小于max 的元素 linklist *head; int max,min; linklist *p,*q; if(head!=NULL) q=head; p=headnext; while(p!=NULL)&(pdata1)的递归出口是_. ( ) AF(0)=0 BF(1)=1 CF(0)=1 DF(n)=n8在下列算法中，_算法可能出现以下情况：在

32、最后一趟开始之前，所有的元素都不在其最终的位置上。 ( )A 堆排序 B 冒泡排序 C 插入排序 D 快速排序 9在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为_。 ( )A O(1) B O(log2n) C O(n2) D O(n) 10具有四层结点AVL树至少有_个结点。 ( ) A 10 B 9 C 8 D 7 二、填空题（每小题2分，共20分） 1.在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着的_、_和_的联系。 2在线性表的单链接存储中，指向下一结点的指针为next。若一个元素所在结点的地址为p，则其后继结点的地址为_，若假定p为一个数组a中的下标，则其后

33、继结点的下标为_。 3. 栈又称为_表，队列又称为_表。 4. 后缀表达式“4 5 + 3 * 2 4 + * ”的值为_。 5. 一棵深度为5的满二叉树中的结点数为_个,一棵深度为3的满四叉树中的结点数为_个。 6. 对于一棵含有40个结点的理想平衡树,它的高度为_。 7. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做_排序。 8. 当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。 9. 对于一个具有n个顶点的图,若采用邻接矩阵表示，则矩阵大小为_。

34、 10. 向一棵 B树插入元素的过程中，若最终引起树根结点的分裂，则新树的高度比原树增_；从一棵 B树删除元素的过程中，若最终引起树根结点的合并，则新树的高度比原树减_。三、判断题 （认为对的，在题后的括号内打“”，错的打“”，每小题 分,共分）1.给出不同输入序列建造二叉排序树，一定得到不同二叉排序树 。 ( ) 2.有向图的邻接表和逆邻接表中的结点数一定相同。 ( ) 3.图G的拓扑序列唯一，则其弧数必为 n-1(其中n为G的顶点数)。 ( ) 4.在索引顺序文件中插入新的记录时，必须复制整个文件。 ( ) 5.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 ( ) 6.对n个记

35、录进行冒泡排序，在最坏情况下所需要的时间是O(n2)。 ( ) 7. 在线性结构中，每个结点都有一个直接前驱和一个直接后继。 ( ) 8.AVL树的任何子树都是AVL树。 ( ) 9. B树既适于随机检索，也适于顺序检索。 ( ) 10.两个字符串相等的充要条件是两个串包含的字符相同。 ( ) 四、简答题（每题10分，共60分） 1. 说明数组和链表的区别，各有何优缺点？ 2. 已知序列（17，18，60，40，7，32，73，65，85），请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。 3邻接矩阵表示图时，若图中有1000个顶点，500条边，则形成的邻接矩阵有多少个元素？有多少个非

36、零元素？是否为稀疏矩阵？ 4简述二叉排序树的概念，并按给定的输入序列： 25、13、15、31、7、20、37 构造一棵二叉排序树。 5一棵二叉树的前序、对称序和和后序序列分别如下，其中有一部分未显示出来，试求空格处内容，并画出该二叉树对应的森林。 前 序：_B_F_ICEH_G 对称序：D_KFIA_EJC_ 后 序: _K_FBHJ_G_A6有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的huffman编码。 五、算法设计题（每题15分，共30分） 说明：可以使用任

37、何高级程序设计语言或伪（类）程序设计语言。 1已知长度为n的线性表A采用顺序存储结构，写一算法，删除该线性表中所有值为 item的数据元素，并给出算法的时间复杂度。 2设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所有顶点的度。 数据结构试题4答案一、1. A 2.A 3. B 4. B 5. B 6.A 7. B 8. C 9. D 10.D 二、1. 1:1 1:N M:N （或者 一对一 1对多 多对多） 2. p-next ap.next 3. 后进先出 先进先出 4. 162 5. 31 21 6. 6 7. 交换 二路归并（或归并） 8. 堆尾 堆顶 向下 9. n2 10. 1 1 三、1X 2. 3. 4. X 5. X 6. 7.X 8. 9.X 10.X 四、答案：区别：数组占用连续的内存空间，链表不要求结点的空间连续。各有何优缺点：（1） 插入和删除操作。数组插入和删除需移动数据元素，链表插入和删除不移动数据元素，链表比数组易于实现插入和删除操作； （2） 在空间占用方面，数组优于链表； （3） 在数据存取方面，数组是随机存取方式，而链表是顺序存取方式。 2.答案：采用起泡排序法排序的各趟结果如下： 初 始：17，18，60，40，07，32，73，65，85 第一趟：17，18