数据结构习题612含答桉.docx

数据结构习题612含答桉.docx

《数据结构习题612含答桉.docx》由会员分享，可在线阅读，更多相关《数据结构习题612含答桉.docx（8页珍藏版）》请在冰点文库上搜索。

数据结构习题612含答桉

数据结构习题6~12（含答桉）

　　　　　　数据结构练习题第六章练习　　选择题　　1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为　　A．5　　B．6　　C．7　　D．8　　2.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是　　A．m-nB．m-n-1　　C．n+1D．条件不足，无法确定　　3．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是A．9　　B．11　　C．15　　D．不确定4．具有10个叶结点的二叉树中有个度为2的结点，　　A．8　　B．9　　C．10　　D．ll　　5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是A．250B．500　　C．254　　D．505　　E．以上答案都不对　　6.有n个叶子的哈夫曼树的结点总数为。

　　A．不确定　　B．2n　　C．2n+1　　D．2n-17.一棵具有n个结点的完全二叉树的树高度是　　A．?

logn?

+1　　B．logn+1　　C．?

logn?

　　D．logn-18．深度为h的满m叉树的第k层有个结点。

（1=　　A．mk-1　　B．mk-1　　C．mh-1　　D．mh-19．在一棵高度为k的满二叉树中，结点总数为　　A．2k-1　　B．2k　　C．2k-1　　D．?

log2k?

+1　　10．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C）次序的遍历实现编号。

　　A．先序　　B.中序　　C.后序　　D.从根开始按层次遍历11．树的后根遍历序列等同于该树对应的二叉树的（B）.　　A.先序序列　　　　B.中序序列　　C.后序序列　　12．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是。

　　A．acbed　　B．decab　　C．deabc　　D．cedba　　13．二叉树的先序遍历和中序遍历如下：

先序遍历：

EFHIGJK；中序遍历:

HFIEJKG。

该二叉树根的右子树的根是：

C　　A、E　　B、F　　C、G　　D、H14．对于前序遍历与中序遍历结果相同的二叉树为;　　对于前序遍历和后序遍历结果相同的二叉树为。

　　A．一般二叉树　　B．只有根结点的二叉树　　C．根结点无左孩子的二叉树　　D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树　　15．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足　　A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树　　16.引入二叉线索树的目的是　　A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除　　　　1　　C．为了能方便的找到双亲　　D．使二叉树的遍历结果唯一17．n个结点的线索二叉树上含有的线索数为A．2n　　B．n－l　　C．n＋l　　D．n18．的遍历仍需要栈的支持.　　A．前序线索树　　B．中序线索树　　C．后序线索树19．二叉树在线索后，仍不能有效求解的问题是。

　　A．前序线索二叉树中求前序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继20．3个结点可以构造出多少种不同的二叉树？

A．2　　B．3　　C．4　　D．5　　21．下述编码中哪一个不是前缀码。

A．B．C．D．　　22．从下列有关树的叙述中,选出5条正确的叙述（共5分）　　A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2k-1个结点。

C．用树的前序周游和中序周游可以导出树的后序周游。

　　D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。

E．将一棵树转换成二叉树后,根结点没有左子树。

　　F．一棵含有N个结点的完全二叉树,它的高度是?

LOG2N?

+1。

G．在二叉树中插入结点,该二叉树便不再是二叉树。

　　H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。

I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。

J．用一维数组存储二叉树时,总是以前序周游存储结点。

　　判断题　　1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。

√2.二叉树只能用二叉链表表示。

×　　3．在二叉树的第i层上至少有2i-1个结点（i>=1）×4．度为二的树就是二叉树。

×　　5.在中序线索二叉树中，每一非空的线索均指向其祖先结点。

√　　填空题：

　　1．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。

　　2．具有256个结点的完全二叉树的深度为__9____。

　　3．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。

4．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=__N2_+1___5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是__99____。

6．一个有2001个结点的完全二叉树的高度为__11____。

　　7．设F是T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__n1-1_个结点，右子树中有_n2+n3__个结点。

　　作业题　　1、给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，　　　　2　　试画出用Huffman算法建造的Huffman树；求平均编码长度考虑概率解：

　　23895143421923653417105235717313778411124532913＋6×5＋5×7＋4×＋3×）/238　　2、．设一棵二叉树的先序、中序遍历序列分别为　　先序遍历序列：

ABDFCEGH中序遍历序列：

BFDAGEHC画出这棵二叉树。

　　画出这棵二叉树的后序线索树。

解：

　　ABDF　　GEHC　　

（2）　　后序遍历为：

FDBGHECA　　　　3　　ABDFGEHC　　　　3．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。

　　intdepth（bitreebt）/*bt为根结点的指针*/{inthl,hr;　　if（bt==NULL）return（

（1）_0__）;　　hl=depth（bt->lchild）;hr=depth（bt->rchild）;if（

（2）hl>hr___）（3）_hr=hl_____；return（hr+1）;}　　4．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。

规定在储存线索二叉树时，完成下面中序线索化过程。

。

　　/*pre是同tree类型相同的指针，初值是null*/thread_inorder（tree）{if（tree!

=null）　　{thread_inorder（

（1）tree->lchild____）;　　if（tree->lchild==

（2）__NULL______）{tree->ltag=1;tree->lchild=pre;}　　if（（3）tree->rchild____==null）{（4）tree->rtag=1__;（5）tree->rchild=tree_______;}　　pre=p;thread-inorder（（6）_tree->rchild__）;　　}}　　5、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？

解：

16　　6、一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。

　　n（k?

1）?

1n0?

　　k7.假设一个二叉树的两种遍历如下：

　　　　4　　前序：

ABFGCHDEIJLK　　中序：

FGBHCDILJKEA画出这棵二叉树以及它的中序线索树；解：

　　A　　BFGHCDEIJLKFGBACHDEIJLK　　第七章练习　　选择题　　1．设无向图的顶点个数为n，则该图最多有条边。

　　A．n-1　　B．n（n-1）/2　　C．n（n+1）/2　　D．0　　E．n22．一个n个顶点的连通无向图，其边的个数至少为。

　　A．n-1　　B．n　　C．n+1　　D．nlogn；　　3．一个有n个结点的图，最少有个连通分量，最多有个连通分量。

　　A．0　　B．1　　C．n-1　　D．n　　4．在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。

　　A．1/2　　B．2　　C．1　　D．45．下列哪一种图的邻接矩阵是对称矩阵？

　　A．有向图　　B．无向图　　C．AOV网　　D．AOE网6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是。

　　A．　　?

A[i,j]i?

1n　　B．　　?

A?

i,j?

j?

1n　　C．i?

1?

A[j,i]n　　D．i?

1?

A[i,j]?

A?

j,i?

+　　j?

1nn　　7．无向图G=（V,E）,其中：

V={a,b,c,d,e,f},E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是。

　　A．a,b,e,c,d,f　　B．a,c,f,e,b,d　　C．a,e,b,c,f,d　　D．a,e,d,f,c,b8．下面哪一方法可以判断出一个有向图是否有环：

　　　　5

　　　　　　A．深度优先遍历B.拓扑排序C.求最短路径D.广度优先遍历　　9.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（B）。

　　A.O（n）　　B.O（n+e）　　C.O（n2）　　D.O（n3）10.求解最短路径的Floyd算法的时间复杂度为（D）。

　　A．O　　B.O　　C.O　　D.O11．已知有向图G=（V,E），其中V={V1,V2,V3,V4,V5,V6,V7}，　　E={,,,,,,,,},G的拓扑序列是。

　　A．V1,V3,V4,V6,V2,V5,V7　　B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7　　D．V1,V2,V5,V3,V4,V6,V7　　12．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列。

　　A．存在B．不存在　　13．一个有向无环图的拓扑排序序列是唯一的。

　　A．一定　　B．不一定　　14.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是。

　　A．G中有弧　　B．G中有一条从Vi到Vj的路径　　　　C．G中没有弧　　D．G中有一条从Vj到Vi的路径15.在用邻接表表示图时，拓扑排序算法时间复杂度为（B）。

A.O（n）　　B.O（n＋e）　　C.O（n*n）　　D.O（n*n*n）16.关键路径是事件结点网络中。

　　A．从源点到汇点的最长路径　　B．从源点到汇点的最短路径C．最长回路　　　　D．最短回路17．下列关于AOE网的叙述中，不正确的是。

　　A．关键活动不按期完成就会影响整个工程的完成时间　　B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成判断题　　1.有e条边的无向图，在邻接表中有e个结点。

2.有向图的邻接矩阵是对称的。

3．任何无向图都存在生成树。

　　4.不同的求最小生成树的方法最后得到的生成树是相同的.5.有环图也能进行拓扑排序。

　　6.关键路径是AOE网中从源点到终点的最长路径。

　　填空题　　1．具有10个顶点的无向图，边的总数最多为__45_____。

　　2.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要___n___条弧。

3．n个顶点的连通无向图，其边的条数至少为___n-1____。

　　4．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_2（n-1）______个非零元素。

5．构造连通网最小生成树的两个典型算法是_普里姆算法、克鲁斯卡尔算法_____。

6.有一个用于n个顶点连通带权无向图的算法描述如下：

　　　　6　　．设集合T1与T2，初始均为空；．在连通图上任选一点加入T1；．以下步骤重复n-1次：

　　a.在i属于T1，j不属于T1的边中选最小权的边；b.该边加入T2。

　　上述算法完成后，T2中共有__n-1__条边，该算法称_普里姆算法_算法，T2中的边构成图的_最小生成树_。

　　7．AOV网中,结点表示____活动____,边表示___联系__。

AOE网中,结点表示___事件__,边表示__活动__。

　　8.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

．查邻接表中入度为____零_____的顶点，并进栈；．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是__Vk的入度减1，如为0则入栈____；．若栈空时，输出顶点数小于图的顶点数，说明有___环路____，否则拓扑排序完成。

　　作业题　　1．n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。

注：

．图的顶点号从0开始计；．indegree是有n个分量的一维数组，放顶点的入度；　　．函数crein用于算顶点入度；．有三个函数push（data）,pop（）,check（）其含义为数据data进栈，退栈和测试栈是否空。

　　crein（array,indegree,n）　　　　　　　　{for（i=0;i　　for（i=0,i　　for（j=0;j　　topsort（array,indegree,n）　　　　　　　　{count=（（4）__0______）　　　　　　　　for（i=0;i　　{vex=pop（）;printf（vex）;count++;　　　　　　for（i=0;i　　{k=array（6）__[vex][i];______　　　　　　　　if（（7）__k!

=0__）{indegree[i]--;if（（8）__indegree[i]==0__）　　push（i）;}　　　　　　　　　　}　　　　　　　　}　　　　　　　　　　if（count　　}　　　　2．设G=（V,E）以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。

　　234?

15?

1342124?

31235?

4　　524?

7　　[‘[[　　解：

　　1231253445　　3．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

1621　　2151119436146335618　　1616解：

2211551111　　43436　　6　　56561818　　　　4、对下面的有向图，试利用DIJKSTRA算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。

　　　　8　　10　　v510v615　　v4410304　　v2　　220v1　　15v3　　　　　　9　　　　第十章　　选择题　　1．下面给出的四种排序法中（D）排序法是不稳定性排序法。

　　A.插入　　B.冒泡　　C.二路归并　　D.堆排序2．下列排序算法中，其中是稳定的。

　　A.堆排序，冒泡排序　　B.快速排序，堆排序　　C.直接选择排序，归并排序　　D.归并排序，冒泡排序3．下面的排序算法中，不稳定的是　　A.起泡排序B.折半插入排序C.简单选择排序　　D.希尔排序　　E.基数排序F.堆排序。

　　4．对一组数据排序，数据的排列次序在排序的过程中的变化为844725　　21154725842115212584471521254784则采用的排序是（A　　）。

　　　　A.选择　　B.冒泡　　C.快速　　D.插入5.在下面的排序方法中，辅助空间为O的是（D）。

　　A．希尔排序　　B.堆排序　　C.选择排序　　D.归并排序　　6.下列排序算法中，占用辅助空间最多的是：

（A　　）　　A.归并排序　　B.快速排序　　C.希尔排序　　D.堆排序7．用直接插入排序方法对下面四个序列进行排序，元素比较次数最少的是。

　　A．94,32,40,90,80,46,21,69　　B．32,40,21,46,69,94,90,80C．21,32,46,40,80,69,90,94　　D．90,69,80,46,21,32,94,40　　8．直接插入排序在最好情况下的时间复杂度为　　A．O（logn）　　B．O（n）　　C．O（n*logn）　　D．O（n2）9．对下列关键字序列用快速排序法进行排序时，速度最快的情形是。

　　A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}10．下列四个序列中，哪一个是堆。

　　A.75,65,30,15,25,45,20,10　　B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10　　D.75,45,65,10,25,30,20,15　　判断　　1．内排序要求数据一定要以顺序方式存储。

　　2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

3．直接选择排序算法在最好情况下的时间复杂度为O。

4．在待排数据基本有序的情况下，快速排序效果最好。

5．快速排序总比选择排序快。

填空　　1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较__和记录的_移动_。

　　2．关键码序列，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_QACSQDFXRHMY____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是__FHCDM　　　　10

　　　　　　AQSRQYX____。

　　　　作业题　　1．下面的排序算法的思想是：

第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?

依次下去，直到待排序列为递增序。

代表两个变量的数据交换）。

　　voidsort（SqList&r,intn）{　　i=1;　　while（

（1）i　　for（j=i+1;

（2）_j　　{if（（3）_r[j].keyr[max].key）　　max=j;}　　if（（4）_min!

=j_____）r[min]r[j];　　if（max!

=n-i+1）{if（（5）_max==j__）r[min]r[n-i+1];else（（6）r[max]r[m-i+1]___）;}i++;}　　}//sort　　2．快速排序是在所有情况下，排序速度最快吗？

为什么？

在何种情况下使用此排序法最好？

　　解：

不是，已经有序情况下不适用，适用于基本无序的情况。

　　3、以上所列的排序方法，哪些是稳定的？

哪些是不稳定的？

对不稳定的方法举出反例。

4、设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取负值关键字之前。

　　快速排序的一趟排序：

把关键字改成跟零比较　　5、以单链表为存储结构实现直接选择排序，写出它的算法。

6、判别以下序列是否为堆？

若不是，则把它调整为堆1）100，86，48，73，35，39，42，57，66，212）12，70，33，65，24，56，48，92，86，33　　3）103，97，56，38，66，23，42，12，30，52，06，204）05，56，20，23，40，38，29，61，35，76，28，100　　　　　　11　　第九章　　选择题　　1、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（A）　　A．/2　　B.N/2　　C.N　　D.[*N]/22.下面关于二分查找的叙述正确的是（D）　　A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列　　B.表必须有序且表中数据必须是整型，实型或字符型　　D.表必须有序，且表只能以顺序方式存储　　3.二叉查找树的查找效率与二叉树的（C）有关,在（C）时其查找效率最低　　

（1）:

A.高度　　B.结点的多少　　C.树型　　D.结点的位置　　

（2）:

A.结点太多　　B.完全二叉树　　C.呈单枝树D.结点太复杂。

4.若采用链地址法构造散列表，散列函数为H=keyMOD17，则需（A）个链表。

　　这些链的链首指针构成一个指针数组，数组的下标范围为（C）　　　　A．17　　B.13　　C.16　　D.任意A．0至17　　B.1至17　　C.0至16　　D.1至16判断题　　1．Hash表的平均查找长度与处理冲突的方法无关。

×2.若散列表的负载因子α　　3.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

×填空题　　1.在顺序表中，用二分法查找关键码值20，需做的关键码比较次数为__4____.作业题　　1.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：

H=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=（H（key）+di）mod10（di=12,22,32,?

）解决冲突。

要求：

对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

　　解：

14/8＝　　0　　1　　23　　4　　56　　7　　8　　914　　1　　923　　842755201　　1　　1　　2　　3　　3　　1　　2　　　　2.已知散列表的地址空间为A[0..11]，散列函数H=kmod11，采用线性探测法处理冲突。

请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等