搜索
第10章综合测试[能力要求]（1）计算机基础知识：掌握图的概念以及图的基本操作。（2）分析问题：针对具体的问题，要能够运用图去进行分析，逐步找到解决问题的方法。（3）具有概念化和抽象化能力：针对具体的应用和实际的问题，能够运用图对问题进行抽象，提取它的逻辑结构和存储结构。（4）发现问题和表述问题：在具体的工程中，能够发现工程中涉及到图的问题，并能够明确表述。（5）建模：在具体的工程中，能够使用图进行建模，设计合理的数据结构和相应的算法。（6）解决方法和建议：在具体工程应用中，发现了关于图的问题，要能够解决问题，并提出合理的建议。（7）定义功能，概念和结构：使用图这种逻辑结构处理一些具体问题，实现系统的功能。（8）设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的图的应用项目。（9）软件实现过程：了解系统中各个模块中的关于图的设计；讨论算法（数据结构、控制流程、数据流程）；使用编程语言实施底层设计（编程）。10.1综合测试题1一、判断题说明：共10题，每题1分，满分10分（）1①有一批数据，经常用来进行插入和删除处理，这样的数据用顺序表存储最合适。（）2①栈用于实现子程序调用。（）3①队列可用于表达式的求值。（）4①队列在队头插入，队尾删除。（）5②若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（）6②完全二叉树的某结点若无左孩子，则它必是叶结点。（）7②将一棵树转换成二叉树后，根结点没有左子树。（）8②任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。（）9②中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）10③如果待排序的数据是有一定顺序的，那么冒泡和简单选择排序法中，简单选择最好。二、填空题说明：共10空，每空1分，满分10分。1①栈的特点是，队列的特点是。2③深度为k的完全二叉树的至少有个节点，至多有节点。3②一棵二叉树的前序遍历结点的访问顺序为：abdgcefh，中序遍历为：dgbaechf，则其后序遍历结果为。4②一组记录元素的关键码为{75，84，26，33，92，15}，则利用快速排序的方法，以第一个记录为枢纽值得到的一次划分结果是：5②n个顶点的无向连通图中最多边数为，最少边数为。6②利用冒泡排序处理n个数据，最快比较次完成排序，最慢比较次完成排序。三、选择题说明：共20小题，每小题1分，满分20分；请将答案填入题后括号中。在本选择题中出现的front代表队列的队头指针，rear代表队列的队尾指针，top代表栈顶指针。其中，涉及到单链表的节点定义如下：structlist{intdata;structlist*next;};1②循环队列用数组A[maxsize]表示，下面哪个选项表示该循环队列队满（）Arear==maxsize-1Bfront==（rear+1）%maxsizeCrear-t==maxsizeDrear-ft==maxsize-12②元素的入栈序列是a，b，c，d，则栈的不可能的输出序列是（）AdcbaBabcdCdcabDcbad3②高度为3的完全二叉树最多有个节点，最少有个节点（）A7，8B4，7C7，4D8，74①堆的形状是一颗（）A二叉排序树B满二叉树C完全二叉树D平衡二叉树5③从n个未排序的数中，找出处在中间位置的元素的计算时间复杂度为（）AO（1）BO（n）CO（2lognn）DO（2n）6①线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续不连续都可以7①线性表是具有n个（）的有限序列（n≠0）A表元素B.字符C数据元素D数据项8②设有一个二维数A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[4][5]在（）位置，（10）表明用10进数表示。A692（10）B626（10）C709（10）D724（10）9①不带头结点的单链表head为空的判定条件是（）Ahead==NULLBhead-next==NULLChead-next==headDhead!=NULL10②在循环双链表的p所指结点之后插入s所指结点的操作是（）。Ap-right=s;s-left=p;p-right-left=s;s-right=p-right;Bp-right=s;p-right-left=s;s-left=p;s-right=p-right;Cs-left=p;s-right=p-right;p-right=s;p-right-left=s;Ds-left=p;s-right=p-right;p-right-left=s;p-right=s;11①若在线性表中采用折半查找法查找元素，该线性表应该：（）A元素按值有序B采用顺序存储结构C元素按值有序，且采用顺序存储结构D元素按值有序，且采用链式存储结构12②下列哪一个程序片断是删除链表中间点。（假设欲删除结点为Pointer结点，Back为前一个结点）（）Afree（Pointer）;Bfree（Back）;CBack=Pointer-next;DBack-next=Pointer-next;free（Pointer）;free（Pointer）;13②用邻接表存储的图的深度优先遍历（DFS）算法类似于二叉树的（）A先序遍历B中序遍历C后序遍历D按层次遍历14②若已知一个栈的入栈序列是1，2，3，4….，n，其输出序列为p1，p2，p3，p4，….，pn，若p1=n，则pi为（）。AiBn=iCn-i+1D不确定15②（）排序的比较次数与记录的初始排列状态无关。A插入B冒泡C选择D快速16②用链表仿真队列时，队空的条件是（）Afront==rearBrear0C没有Dfront==NULL17③有一子函数如下：intX（intn）{if（n=2）return1;elsereturnX（n-1）+X（n-2）+2;}问X（X（3））执行（）次X子函数。A5B6C7D818②以下说法错误的是（）A对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表B对单链表来说，只有从头结点开始才能扫描表中全部结点C双链表的特点是找结点的前驱和后继都很容易D对双链表来说，结点*p的存储位置既存放在其前驱结点的后继指针域中，也存放在其后继结点的前驱指针域中19③已知广义表L=（（x，y，z），a，（u，t，w）），从L表中取出原子项t的运算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail（head（tail（tail（L）））））20③若串S1=‘ABCDEFG’，S2=‘9898’，S3=‘###’，S4=‘012345’，执行concat（replace（S1，substr（S1，length（S2），length（S3）），S3），substr（S4，index（S2，‘8’），length（S2）））其结果为（）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###01234（）四、简答题说明：共5小题，每小题8分，满分40分1③利用普利姆算法（Prim）构造出如图所示的一个最小生成树。图10.11题图2③一棵二叉树的结点数据采用顺序存储结构，存储于数组T中，如图所示，则将该二叉树的链接表示形式画出来。eafdgcjihb123456789101112131415161718192021图10.22题图3③已知一组关键字为{19，14，23，68，84，27，55，79}，请画出堆排序法进行从小到大的排序过程。V2V4V1V3V5V665253566414③假设通信电文使用的字符集为{a，b，c，d，e，f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符’0’，右分支表示字符’1’），然后分别写出每个字符对应的编码。5③设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝KMOD13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字30，需要依次与哪些关键字进行比较？（3）若查找关键字14，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。五、算法题说明：共2小题，每小题10分，满分20分。以下题目的算法可以用C语言函数表达，也可以用伪代码描述。1④对于一棵二叉查找树，试设计递归算法InsertNode（Root，Value），以实现插入结点Value。二叉树的结点数据结构定义如下：structtree{structtree*left;intdata;structtree*right;};typedefstructtreetreenode;typedeftreenode*b_tree;voidInsertNode（b_treeRoot，b_treeValue）{……}2④假设单链表中节点的定义如下：structstudent{charname[20];/*学生姓名*/intbDelelted;/*删除标记，1表示该节点被做了删除标记，0表示该节点未被作删除标记*/structstudent*next;};typedefstructstudentnode;typedefnode*link;要求打印出单链表（已经创建）中所有未作删除标记的节点的学生姓名。注：可以用程序语句完成以下子函数，也可以用伪代码描述算法。voidprint_list（linkhead）/*head指向已创建的单链表的头节点*/{}10.2综合测试题2一、判断题说明：共10题，每题1分，满分10分（）1②哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）2②堆可以看作是一个完全二叉树。（）3②队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）4②Ｈａｓｈ表的平均查找长度与处理冲突的方法无关。（）5②算法的优劣与算法描述语言无关，但与所用计算机有关。（）6②快速排序算法在每一趟排序中都能找到一个元素放置在其最终位置上。（）7②若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n个非空指针域。（）8②在一个大根堆中，最小元素一定在最后。（）9②二维数组在内存中存储也是连续的。（）10②对于有N个结点的二叉树，其高度为2logN。二、填空题说明：共10空，每空1分，满分10分。1①数据结构类型可分成四大类，包括集合结构、结构、结构和结构。2③设一棵完全二叉树具有500个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个只有左孩子的结点，有个只有右孩子的结点。3③用元素“2、3、1、7、5、11、6、9”建立二叉排序树，则将该二叉树以后序遍历方式输出节点为。4②下表为一个具有5个顶点（0、1、2、3、4）有向图形的邻接数组表示（数组内容以1表示弧存在，以0表示弧不存在），则顶点3的入度为，出度为。01100101110000011101110100123401234图10.34题图三、选择题说明：共20小题，每小题1分，满分20分；请将答案填入题后括号中。在本选择题中出现的front代表队列的队头指针，rear代表队列的队尾指针，top代表栈顶指针。其中，涉及到单链表的节点定义如下：structlist{intdata;s