《数据结构》-数据结构修正

一选择题1向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A8B635C63D72设有一个二维数组AMN，假设A00存放位置在644（10），A22存放位置在676（10），每个元素占一个空间，则A33在（）位置，（10）表明用10进数表示。A692（10）B626（10）C709（10）D724（10）3一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（）。A128B127C126D2554含5个结点（元素值均不相同）的二叉树搜索树有（）种。A54B42C36D655N个顶点的连通图至少有（）条边。AN1BNCN1D06对于两个函数，若函数名相同，但只是（）不同则不是重载函数。A参数类型B参数个数C函数类型D函数个数7若需7要利用形参直接访问实参，则应把形参变量表明为（）参数。A指针B引用C值D地址8下面程序的时间复杂度为（）。FORINTI0ILINKPLINKPLINKSBQLINKSSLINKPCPLINKSLINKSLINKQDPLINKSSLINKQ11设单链表中结点的结构为DATA,LINK。若想摘除结点P的直接后继，则应执行下列哪一个操作（）。APLINKPLINKLINKBPPLINKPLINKPLINKLINKCPLINKPLINKDPPLINKLINK12栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置13若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（）。A3，2，1B2，1，3C3，1，2D1，3，214广义表AA,则表尾为（）。AABC空表D（A）15下列广义表是线性表的有（）。AEA,B,CBEA,ECEA,BDEA,L16折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。A相同B完全不同C有时不相同D不确定17采用折半搜索算法搜索长度为N的有序表时，元素的平均搜索长度为（）。AONLOG2NBONCOLOG2NDON18采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A中序遍历B前序遍历C后序遍历D按层次遍历19每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。A插入B选择C交换D外排序20采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。A中序遍历B前序遍历C后序遍历D按层次遍历二填空题1算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应具有输入、输出、_确定性_、有穷性和可执行性等特性。2在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是_2_。3队列的插入操作在_队尾_进行，删除操作在_队头_进行。4当用长度为N的数组顺序存储一个栈时，若用TOPN表示栈空，则表示栈满的条件为_TOP0_。5对序列49,38,65,97,76,27,13,50采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是_1327384550657697_。6对于一棵具有N个结点的树，该树中所有结点的度数之和为_N1_。7在一个堆的顺序存储中，若一个结点的下标为I，则它的左子女结点的下标为_2I1_，右子女结点的下标为_2I2_。8请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用折半查找关键码12需做_4_次关键码比较。9若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是_144_。10在一个长度为N的顺序表中，向第I个元素（1IN）之前插入一个新元素时，需要向后移动_NI1_个元素。11设有两个串P和Q，求Q在P中首次出现的位置的运算称作_。12以折半搜索方法搜索一个线性表时，此线性表必须是_顺序_存储的_有序_表。13在一个无向图中，所有顶点的度数之和等于所有边数的_2_倍。14判定一个循环队列QU最多元素为M为满队列的条件是_。15设有广义表DA,B,D，其长度为_，深度为_。16在一个具有N个顶点的无向完全图中，要连通所有顶点则至少需要_N1_条边，在一个具有N个顶点的有向完全图中，包含有_NN1_条边。17对于一个具有N个顶点的图，若采用邻接矩阵表示，则矩阵大小为_NN_。18对于一个具有N个顶点和E条边的连通图，其生成树中顶点数和边数分别为_N_和_N1_。19在直接选择排序中，记录比较次数的时间复杂度为_ONN_，记录移动次数的时间复杂度为_ON_。20快速排序在平均情况下的空间复杂度为_OLOGN_，在最坏情况下的空间复杂度为_ON_。21当问题的规模N趋向无穷大时，算法执行时间TN的数量级被称为算法的_时间复杂度_。22若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是_144_。23在一个长度为N的顺序表中，向第I个元素（1IN）之前插入一个新元素时，需要向后移动_个元素。24设有两个串P和Q，求Q在P中首次出现的位置的运算称作_。25在一个无向图的邻接表中，若表结点的个数是M，则图中边的条数是_M/2_条。26对于一个具有N个顶点的图，若采用邻接矩阵表示，则矩阵大小为_。三、判断题（Y）1直接选择排序是一种不稳定的排序方法。（N）2折半搜索只适用于有序表，包括有序的顺序表和有序的链表。（Y）3数据的逻辑结构与数据元素本身的内容和形式无关。（N）4数据结构是指相互之间存在一种或多种关系的数据元素的全体。（N）5线性表的逻辑顺序与物理顺序总是一致的。（Y）6线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。（Y）7二叉树是数的特殊情形。（Y）8若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（N）9若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。（N）10任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（N）11对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（Y）12最优二叉搜索树的任何子树都是最优二叉搜索树。（Y）13在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。（Y）14有N（N1）个顶点的有向强连通图最少有N条边。（N）15连通分量是无向图中的极小连通子图。（N）16二叉树中任何一个结点的度都是2。（N）17单链表从任何一个结点出发，都能访问到所有结点。四、程序阅读填空1在顺序表中第I个位置插入新元素XTEMPLATEINTSEQLISTINSERTTYPE/插入不成功ELSELASTFOR_JIJ_DATAIXRETURN1/插入成功2删去链表中除表头结点外的所有其他结点TEMPLATEVOIDLISTMAKEEMPTYLISTNODEQWHILEFIRSTLINKNULL_/将表头结点后第一个结点从链中摘下DELETEQ/释放它LASTFIRST/修改表尾指针3删去链式队头结点（队头指针为QUEUENODEFRONT），并返回队头元素的值TEMPLATETYPEQUEUEDEQUEUEASSERTISEMPTY/判队空的断言QUEUENODEP_TYPERETVALUEPDATA/保存队头的值_/新队头DELETEPRETURNRETVALUE4最小堆的向下调整算法TEMPLATEVOIDMINHEAPFILTERDOWNINTSTART,INTENDOFHEAPINTISTART,J2I1/J是I的左子女TYPETEMPHEAPIWHILEJHEAPJ1KEYJ/两子女中选小者IFTEMPKEYINTORDEREDLISTBINARYSEARCHCONSTTYPEIFLOWXMIDBINARYSEARCHX,LOW,MID1RETURNMID6直接插入排序的算法（按关键码KEY非递减顺序对数据表LIST进行排序）TEMPLATEVOIDINSERTIONSORTDATALISTIVIODINSERTDATALISTINTJI/从后向前顺序比较WHILEJ0IVIODSELECTEXCHANGEDATALISTFORINTJI1JRLINK,QDLLLINKWHILEPQ_ELSESYM0RETURNSYM五、简答题1给定权值集合15,03,14,02,06,09,16,17,构造相应的霍夫曼树,并计算它的带权外部路径长度。P1342线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点P503设有一个输入数据的序列是46,25,78,62,12,37,70,29，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。4对于如右图所示的有向图，试写出1从顶点出发进行深度优先搜索所得到的深度优先生成树；2从顶点出发进行广度优先搜索所得到的广度优先生成树；P1785用广义表的带表头结点的存储表示法表示下列集合。AB6,2CA,5,3,XDB,C,AEB,D6右图所示为一有向图，请给出该图的下述要求（1）给出每个顶点的入度和出度；130222312431521614（2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；（3）给出该图的邻接矩阵；（4）给出该图的邻接表；（5）给出该图的逆邻接表；7已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A8已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边