计算机软件技术基础题库

1第1章数据结构一、选择题1算法指的是（D）。A计算机程序B解决问题的计算方法C排序方法D解决问题的有限运算序列2在数据的树形结构中，数据元素之间为（C）的关系。A00B11C1NDMN3数据的存储结构包括顺序、链接、散列和（A）4种基本类型。A索引B数组C集合D向量4一个数组元素AI与（B）的表示等价。ABPNEXTPHPHPCPNEXTPHPPHDPNEXTPHNEXTPHNEXTP21在一个表头指针为PH的单链表中，若要在指针Q所指结点的后面插入一个由指针P所指向的结点，则执行（D）操作。AQNEXTPNEXTPNEXTQBPNEXTQNEXTQPCQNEXTPNEXTPNEXTQDPNEXTQNEXTQNEXTP22在一个单链表HL中，若要删除由指针Q所指向结点的后继结点（若存在的话），则执行（C）操作。APQNEXTPNEXTQNEXTBPQNEXTQNEXTPCPQNEXTQNEXTPNEXTDQNEXTQNEXTNEXTQNEXTQ23在一个带头结点的循环双向链表中，若要在指针P所指向的结点之后插入一个Q指针所指向的结点，则需要对QNEXT赋值为（B）。APPRIORBPNEXTCPNEXTNEXTDPPRIORPRIOR24在一个带头结点的循环双向链表中，若要在指针P所指向的结点之前插入一个Q指针所指向的结点，则需要对PPRIORNEXT赋值为（A）。AQBPCPNEXTDPPRIOR25在一个带头结点的循环双向链表中，若要删除指针P所指向的结点则执行（A）操作。APPRIORNEXTPNEXTPNEXTPRIORPPRIORBPNEXTPRIORPPNEXTPNEXTNEXTCPPRIORNEXTPPNEXTPNEXTPRIORDPPNEXTPPRIORNEXTPPRIOR26栈的插入和删除操作在（A）进行。A栈顶B栈底C任意位置D指定位置27当利用大小为N的数组顺序存储一个栈时，假定用TOPN表示栈空，则向3这个栈插入一个元素时，首先应执行（B）语句修改TOP指针。ATOPBTOPCTOP0DTOPN128假定利用数组AN顺序存储一个栈，用TOP表示栈顶指针，用TOPN1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（A）。ATOP1BTOP1CTOP0DTOPN129假定利用数组AN顺序存储一个栈，用TOP表示栈顶指针，用TOP1表示栈空，并已知栈未满，当元素X进栈时所执行的操作为（C）。AATOPXBATOPXCATOPXDATOPX30假定利用数组AN顺序存储一个栈，用TOP表示栈顶指针，用TOP1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（B）。ARETURNATOPBRETURNATOPCRETURNATOPDRETURNATOP31假定一个链式栈的栈顶指针用TOP表示，该链式栈为空的条件（C）。ATOPNULLBTOPTOPNEXTCTOPNULLDTOPTOPNEXT32假定一个链式栈的栈顶指针用TOP表示，每个结点结构为,当P所DATANEXT指向的结点进栈时，执行的操作为（D）。APNEXTTOPTOPTOPNEXTBTOPPPNEXTTOPCPNEXTTOPNEXTTOPNEXTPDPNEXTTOPTOPP33假定一个链式栈的栈顶指针用TOP表示，每个结点结构为,退栈时DATANEXT所执行的操作为（C）。ATOPNEXTTOP；BTOPTOPDATACTOPTOPNEXTDTOPNEXTTOPNEXTNEXT34若让元素1，2，3，4依次进栈，则出栈次序不可能出现（D）的情况。A3，2，1，4B2，1，4，3C4，3，2，1D1，4，2，335在一个顺序循环队列中，队首指针指向队首元素的（A）位置。A前一个B后一个C当前D最后36当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（B）。AN2BN1CNDN137从一个顺序循环队列中删除元素时，首先需要（B）。A前移队首指针B后移队首指针C取出队首指针所指位置上的元素D取出队尾指针所指位置上的元素38假定一个顺序循环队列的队首和队尾指针分别用F和R表示，则判断队空的条件为（D）。AF1RBR1FCF0DFR39假定一个顺序循环队列存储于数组AN，其队首和队尾指针分别用F和R表示，则判断队满的条件为（B）。A（R1）NFB（R1）NFC（F1）NRD（F1）NR40假定利用数组AN循环顺序存储一个队列，其队首和队尾指针分别用F和R表示，并已知队列未满，当元素X入列时所执行的操作为（A）。AARNXBARNXCARNXDARNX41假定利用数组AN循环顺序存储一个队列，其队首和队尾指针分别用F和R表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（C）。4ARETURNARNBRETURNARNCRETURNAFNDRETURNAFN42假定一个链式队列的队首和队尾指针分别为FRONT和REAR，则判断队空的条件为（D）。AFRONTREARBFRONTNULLCREARNULLDFRONTNULL43假定一个链式队列的队首和队尾指针分别为FRONT和REAR，每个结点结构为,当出列时所进行的操作为（A）。DATANEXTAFRONTFRONTNEXTBREARREARNEXTCFRONTNEXTREAR；REARREARNEXTDFRONTFRONTNEXT；FRONTNEXTREAR；44假定一个带头结点的循环链式队列的队首和队尾指针分别用FRONT和REAR表示，则判断对空的条件为（D）。AFRONTREARNEXTBREARNULLCFRONTNULLDFRONTREAR45假定一个链式队列的队首和队尾指针分别为FRONT和REAR，每个结点结构为包含值域DATA和指针域NEXT,则使P所指结点入列所执行的操作为（B）。APNEXTNULL；REARREARNEXTP；BPNEXTREARNEXT；REARREARNEXTP；CPNEXTFRONT；FRONTP；DPNEXTFRONTNEXT；FRONTNEXTP；46在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分别用FRONT和REAR表示，则该队列中数组元素个数为（B）。A（REARFRONT）NB（REARFRONTN）NC（REARN）ND（FRONTN）N47二维数组A12,10采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A0，0的地址）为1200，则A6，5的地址为（D）。A1400B1404C1372D146048有一个MN的矩阵A，若采用行优先进行顺序存储，每个元素占用8个字节，则AIJ1IM,1JN元素的相对字节地址（相对首元素地址而言）为（B）。A（I1）NJ）8B（I1）NJ1）8C（INJ1）8D（I1）NJ1）849有一个NN的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用K个字节，则AIJ1IN,1JI元素的相对字节地址（相对首元素地址而言）为（C）。A（I（I1）/2J1）4B（II/2J）4C（I（I1）/2J1）4D（I（I1）/2J）450树中所有结点的度等于所有结点数加（C）。A0B1C1D251在一棵树中，（C）没有前驱结点。A树枝结点B叶子结点C树根结点D空结点52在一棵树中，每个结点最多有（B）个前驱结点。A0B1C2D任意多个53在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（A）。5A2B1C0D154在一棵具有N个结点的二叉树中，所有结点的空子树个数等于（C）。ANBN1CN1D2N55在一棵具有N个结点的二叉树的第I层上，最多具有（C）个结点。A2IB2I1C2I1D2N56在一棵深度为H的完全二叉树中，所含结点个数不小于（D）。A2HB2H1C2H1D2H157在一棵深度为H的完全二叉树中，所含结点个数不大于（C）。A2HB2H1C2H1D2H158在一棵具有35个结点的完全二叉树中，该树的深度为（A）。A6B7C5D859在一棵完全二叉树中，若编号为I的结点存在左孩子，则左孩子结点编号为（A）。A2IB2I1C2I1D2I260在一棵完全二叉树中，若编号为I的结点存在右孩子，则右孩子结点编号为（C）。A2IB2I1C2I1D2I261在一棵完全二叉树中，对于编号为I（I1）的结点其双亲结点的编号为（D）。A（I1）/2B（I1）/2CI2DI/262有如图11所示的一棵二叉树，则该二叉树所含单支结点数为（B）。A2B3C4D563有如图12所示的一棵二叉树，则该二叉树的中序遍历序列为（C）。AABCDEFGBCDBGFEACCBDAEGFDABECDFG64有如图12所示的一棵二叉树，则该二叉树的先序遍历序列为（A）。AABCDEFGBCDBGFEACCBDAEGFDABECDFG65有如图12所示的一棵二叉树，则该二叉树的后序便利序列为（B）。AABCDEFGBCDBGFEACCBDAEGFDABECDFG66利用N个值生成的哈夫曼树中共有（D）个结点。ANBN1C2ND2N167利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（A）。A55B29C58D3868在一个具有N个顶点的有向图中，若所有顶点的出度数之和为S，则所有的入度数之和为（A）。ASBS1CS1DNABCE图11DGHFABC图12EGDF669在一个具有N个顶点的有向图中，若所有顶点的出度数之和为S，则所有的度数之和为（D）。ASBS1CS1D2S70在一个具有N个顶点的无向图中，若具有E条边，则所有顶点的度数为（D）。ANBECNED2E71在一个具有N个顶点的无向完全图中，所含的边数为（C）。ANBN（N1）CN（N1）/2DN（N1）/272在一个具有N个顶点的有向完全图中，所含的边数为（B）。ANBN（N1）CN（N1）/2DN（N1）/273在一个具有N个顶点的无向连通图中，它包含的连通分量的个数为（C）。A0B1CNDN174若有一个图中包含K个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（A）次深度优先搜索遍历的算法。AKB1CK1DK175若要把N个顶点连接为一个连通图，则至少需要（C）条边。ANBN1CN1D2N76在一个具有N个顶点和E条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（D）。ANBNECED2E77在一个具有N个顶点和E条边的有向图的邻接矩阵中，表示边存在的元素的个数为（C）。ANBNECED2E78在一个具有N个顶点和E条边的无向图的邻接矩阵中，边结点的个数为（D）。ANBNECED2E79对于一个有向图，若一个顶点的度为K1，出度为K2，则对应邻接表中该顶点单链表的边数结点为（B）。AK1BK2CK1K2DK1K280对于一个有向图，若一个顶点的度为K1，出度为K2，则对应逆邻接表中该顶点单链表的边数结点为（C）。AK1BK2CK1K2DK1K281对于一个无向图，下面（A）的说法是正确的。A每个顶点的入度等于出度B每个顶点的度等于入度和出度之和C每个顶点的入度为0D每个顶点的出度为082在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（A）。A出边数B入边数C度数D度数减一83若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（B）。AABCFDEBACFDEBCABDCFEDABDFEC84若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（D）。AABCDEFBABCFDECABDCEFDACBFDE785若一个图的边集（1，2）（1，4）（2，5）（3，1）（3，5）（4，3），则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（A）。A1，2，5，4，3B1，2，3，4，5C1，2，5，3，4D1，4，3，2，588若查找每一个元素的概率相等，则在长度为N的顺序表上查找任一元素的平均查找长度为（D）。ANBN1CN1/2DN1/289对长度为N的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找长度为（B）。AN/2B（N1）/2CN1/2DN/490对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（C）的值除以9。A20B18C25D2291对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（B）。A2B3C4D692对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（C）。A2B3C4D593在分块查找中，若用于保存数据元素的主表长度为N，它被分为K个子表，每个子表的长度均为N/K，若用顺序查找确定块，则分块查找的平均查找长度为（D）。ANKBKN/KC（KN/K）/2D（KN/K）/2194在分块查找中，若用于保存数据元素的主表长度为144，它被分为12个子表，每个子表的长度均为12，若用顺序查找确定块，则分块查找的平均查找长度为（A）。A13B24C12D7995在一棵深度为H的具有N个元素的二叉排序树中，查找所有元素的最长查找长度为（D）。ANBLBNC（H1）/2DH96在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（B）。A11B22C12D0197若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用H（K）K13计算哈希地址，则元素64的哈希地址为（C）。A4B8C12D1398若根据查找表（23，44，36，48，52，73，64，58）建立线形哈希表，采用H（K）K13计算哈希地址，则哈希地址为3的元素个数为（B）。A1B2C3D499若根据查找表建立长度为M的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为D，则下一次的哈希地址为（D）。ADBD1C（D1）/MD（D1）M100在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子A的值为05，则查找任一个元素的平均查找长度为（B）。A1B15C2D258102若对N个元素进行直接插入排序，则进行第I趟排序过程前，有序表中元素的个数为（A）。AIBI1CI1D1103若对N个元素进行直接插入排序，在进行第I趟排序时，为寻找插入位子最多需要进行（C）次元素的比较，假定第0号元素放有待查的键值。AIBI1CI1D1104若对N个元素进行直接插入排序，在进行第I趟排序时,假定元素RI1的插入位置为RJ，则需要移动元素的次数为（D）。AJIBIJ1CIJDIJ1105若对N个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（B）。AO（1）BO（N）CO（N2）DO（LBN）106在对N个元素进行直接插入排序的过程中，共需要进行（C）趟。ANBN1CN1D2N107对N个元素进行直接插入排序的时间复杂度为（C）。AO（1）BO（N）CO（N2）DO（LBN）108在对N个元素进行冒泡排序的过程中，第一趟排序至多进行（B）对相邻元素之间的交换。ANBN1CN1DN/2109在对N个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（D）。AO（1）BO（LBN）CO（N2）DO（N）110在对N个元素进行冒泡排序的过程中，至多需要（A）趟完成。A1BNCN1DN/2111在对N个元素进行快速排序的过程中，最好情况下需要进行（C）趟。ANBN/2CLBND2N112在对N个元素进行快速排序的过程中，最坏情况下需要进行（B）趟。ANBN1CN/2DLBN113对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（D）。A1，3，5，7，9B9，7，5，3，1C5，3，1，7，9D5，7，9，1，3114假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（B）。A2B3C4D5115在对N个元素进行简单选择排序的过程中，在第I趟需要从（A）个元素中选择出最小值元素。ANI1BNICIDI1116若对N个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（D）。AO（1）BO（LBN）CO（N2）DO（N）117假定一个初始堆为（1，5，3，9，12，7，15，10），则进行第一趟堆排序后得到的结果为（A）。A3，5，7，9，12，10，15，1B3，5，9，7，12，10，15，1C3，7，5，9，12，10，15，1D3，5，7，12，9，10，15，1118若一个元素序列基本有序，则选用（A）方法较快。9A直接插入排序B简单选择排序C堆排序D快速排序119若要从1000个元素中得到10个最小元素，最好采用（B）方法。A直接插入排序B简单选择排序C堆排序D快速排序120在平均情况下速度最快的排序方法为（D）。A简单选择排序B冒泡排序C堆排序D快速排序二填空题1数据的逻辑结构可分为_和_两大类。2数据的存储结构被分为_，_，_和_4种。5线性表的两种存储结构分别为_顺序_和链式_。6线性表的顺序存储结构称为顺序表_，链式存储结构称为_链式表_。7若经常需要对线性表进行插入和删除运算，则最好采用_链式_存储结构，若经常需要对线性表进行查找运算，则最好采用_顺序_存储结构。8对于一个长度为N的顺序存储的线性表，在表头插入元素的时间复杂度为_。9对于一个单链表存储的线性表，在表头插入结点的时间复杂度为_，在表尾插入结点的时间复杂度为_。10在线性表的单链表存储中，若一个元素所在结点的地址为P，则其后的断结点的地址为_。12在_循环_链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。13在一个单链表中删除指针P所指向结点的后继结点时，需要把_的值赋给PNEXT指针域。14在一个单链表中指针P所指向结点的后面插入一个指针Q所指向的节点时，首先把_的值赋给PNEXT，然后把_的值赋给PNEXT。15假定指向单链表中第一个结点的头指针为HEAD，则像该单链表的表头插入指针P所指向的新结点时，首先执行_赋值操作，然后执行_赋值操作。16访问一个顺序表和一个单链表中第I个元素的时间复杂度分别为_和_。17在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作过程是否相同_。18在双向链表中每个结点包含有两个指针域，一个指向其_结点，另一个指向其_结点。19在一个双向链表中指针P所指向的结点之后插入一个指针Q所指向的结点时，需要对PNEXTPRIOR指针域赋值为_。20在一个双向链表中删除指针P所指向的结点时，需要对PNEXTPRIOR指针域赋值为_。21栈又称为_表，队列又称为_表。22在一个用一维数组AN表示的顺序栈中，该栈所含元素的个数最少为_个，最多为_个。23像一个顺序栈插入一个元素时，首先使_后移一个位置，然后把新元素_到这个位子。24从一个栈删除元素时，首先取出_，然后再使_减一。25一个顺序栈存储一个一维数组AM中，栈顶指针用TOP表示，当栈顶指针等10于_时为空栈，栈顶指针为_时为满栈。26假定一个链栈的栈顶指针为TOP，每个结点包含值域DATA和指针域NEXT，当P所指向的结点入栈时，则首先执行_操作，然后执行_操作。27假定一个链栈的栈顶指针为TOP，每个结点包含值域DATA和指针域NEXT，当进行出栈运算时（假定栈非空），需要把栈顶指针修改为_的值。28设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为PUSHS,1,PUSHS,2,_,POPS,PUSHS,4,POPS,_,_,POPS,POPS。29设元素A，B，C，D依次进栈，若要在输出端得到序列CBDA，则应进行的操作序列为PUSHS,A,PUSHS,B,PUSHS,C,_,_，_POPS,POPS。30队列的插入操作在_进行，删除操作在_进行。31一个顺序循环队列存在于AM中,假定队首和队尾指针分别为FRONT和REAR，则判断对空的条件为_，判断对满的条件为_。32一个顺序循环队列存在于AM中,假定队首和队尾指针分别为FRONT和REAR，则求出队首和队尾指针的下一个位置的计算公式分别为_和_。33在一个用一维数组AN存储的顺序循环队列中，该队列中的元素个数最少为_个，最多为_个。34向一个顺序循环队列中插入元素时，需要首先移动_，然后再向它所指位置_新元素。35在一个空链队列中，假定队首和队尾指针分别为F和R，当向他插入一个新结点P时，则首先执行_操作，然后执行_操作。36在一个带头结点的循环链队列中，假定队首和队尾指针分别为F和R，当向它插入一个新结点P时，则首先执行_操作，然后执行_操作。37假定FRONT和REAR分别为一个链队列的对首和队尾指针，则该链队列中只有一个结点的条件为_。38在一个链栈中，若栈顶指针等于NULL则为_；在一个链队列中，若对首和队尾的指针相同，则表示该队列为_或该队列_。39一个二维数组A15，10采用行优先方式存储，每个数据元素占用4个存储单元，以该数组第3列第0行的地址（即A3，0的地址）1000为首地址，则A12，9的地址为_。40在二维数组A10,20中，每个元素占8个存储单元，假定该数组的首地址为2000，则数组元素A6,15的字节地址为_。41有一个88的下三角矩阵A，若将其进行顺序存储于一维数组AN中，则N的值为_。42有一个1010的下三角矩阵A，若将其进行顺序存储于一维数组AN中，则AIJ（1I10,1JI）存储于A中的下标位置为_。43有一个88的下三角矩阵A，若将其进行顺序存储，每个元素占用4个字节，则A5，4元素的相对字节地址为（相对首元素地址而言）_。44一种数据结构的元素集合K和它的二元ABICDGJKEFHXY图1311关系R为KA,B,C,D,E,F,G,HR，则该数据结构具有_结构。45对于一棵具有N个结点的树，则该树中所有结点的度数之和为_。46在一棵树中，_结点没有前驱结点，其余每个结点有并且只有一个_，可以有人以多个_结点。47如图13所示为一棵树，该树的叶子结点数为_个，单支结点数为_个，双分支结点数为_个，三分支结点数为_个。48如图13所示的一棵树，结点K的所有祖先的结点数为_个，结点B的所有子孙结点数为_个。49如图13所示的一棵树，结点D和X的层数分别为_和_。50如图14所示的一棵树，则树中所含的结点数为_个，树的深度为_，树的度为_。51如图14所示的一棵树，则度为3，2，1，0的结点数分别为_，_，_。52如图14所示一棵树，则结点H的双亲为_，孩子结点为_。53在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_。54对于一棵二叉树，若一个结点的编号I，若它的左孩子结点存在，则其编号为_，若右孩子结点存在，则其编号为_，若双亲结点存在，则其编号为_。55在一棵二叉树中，第5层上的结点数最多为_。56假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。57如图15所示为一棵二叉树，则E结点的双亲结点数为_，左孩子结点为_，右孩子结点为_。58如图15所示为一棵二叉树，它含有双支结点_个，单分支结点_个，叶子结点_个。59假定一棵二叉树顺序存储在一维数组A中，若A5元素的左孩子存在则对应的元素为_，若右孩子存在则对应的元素为_，双亲元素为_。60若对一棵二叉树从0开始进行结点编号，并按此编号把它存储到一维数组A中，即编号为0的结点存储到A0中，依次类推，则AI元素的左孩子为_，右孩子为_，双亲元素（I0）为_。61对于一棵具有N个结点的二叉树，对应_二叉链表中指针总数为_个，其中_个用于指向孩子结ABCDHEGI图14FJABCDEF图15GABCFDE图1612点，_个指针空闲。62在一棵深度为H的完全平衡二叉树中，最少含有_个结点，最多含有_个结点。63一棵深度为5的完全二叉树中的结点数最少为_个，最多为_个。64如图16所示为一棵二叉树，对它进行先序遍历结果为_。65若将如图17所示为一棵树转换为二叉树，该二叉树中双支结点的个数为_个，单支结点的个数为_个，叶子结点个数为_。66一棵树转换为二叉树后如图18所示，则原树中分支结点数为_，叶子结点数为_。67一个树林转换成二叉树后如图19所示，则该素林中包含_棵树。68若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的深度为_，带权路径长度为_。69一种数据结构的元素集合K和它的二元关系R为K1，2，3，4，5，6R（1，2）（2，3）（2，4）（3，4）（3，5）（3，6）（4，5）（4，6）则该数据结构具有_数据结构。70在一个图中，所有顶点的度数之和等于所有边数的_倍。71在一个具有N个顶点的无向完全图中，包含有_条边，在一个具有N个顶点的有向完全图中，包含有_条边。72已知一个连通图的边集为（1，2），（1，3），（1，4），（2，3），（2，5），（3，5），（4，5），则度为3的顶点的个数有个。73假定一个有向图的顶点的集为A,B,C,D,E,F,边集，,则出度为0的顶点个数为，入度为1的顶点个数为。74在一个具有N个顶点的无向图中，要连通所有顶点则至少需要条边。75表示图的两种存储结构为和。76在一个连通图中存在着个连通分量。77若一个图的顶点集为A,B,C,D,E,F,边集为（A,B），（A,C），（B,C），（D,E），则该图含有个连通分量。78若一个图的边集为，ABCIFG图17DEHABCG图18DFEHIABCE图19DGIHF13则从顶点V0到顶点V4共有条简单路径。79如图110所示为一个带权有向图，从顶点V0到顶点V4的最短路径长度为。80对于一个具有N个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为。81对于一个具有N个顶点和E条边的有向图和无向图，在其对应的邻接表中，所含边结点的个数分别为和。82在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有和。83有一个图的边集为（A,C），（A,E），（B,E），（C,D），（D,E），从顶点A出发进行深度优先搜索遍历得到的顶点序列为，从顶点A出发进行广度优先搜索遍历得到的顶点序列为。84一个图的边集为（A,C），（A,E），（C,F），（D,C），（E,B），（E,D）,从顶点A出发出发进行深度优先搜索遍历得到的顶点序列为，从顶点A出发进行广度优先搜索遍历得到的顶点序列为。85图的优先搜索遍历算法是一种递归算法，图的优先搜索遍历算法需要使用队列。86若一个连通图中每个边上的权值均不同，则得到的最小生成树是（唯一/不唯一）。87以顺序查找方法从长度为N的顺序表或单链表中查找一个元素时，平均查找长度为。88对长度为N的查找表进行查找时，假定查找第I个元素的概率为P，查找长度（即在查找过程中依次同有关元素比较的总次数）为C，则在查找成功的情况下的平均查找长度的计算公式为。89假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功的情况下的平均查找长度，则在查找不成功的情况下的平均查找长度。90以折半查找方法从长度为N的有序表中查找一个元素时，平均查找长度约等于减一。91以折半查找方法从长度为50的有序表中查找一个元素时，其查找长度不超过。92从有序表（12，18，30，43，56，78，82，95）中分别折半查找43和56元素时，其查找长度分别为和。93假定对长度N50的有序表进行折半查找，则对应的判定树深度为，最后一层的结点数为。94在分块查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行分块查找的平均查找长度为。95假定对长度为N的有序表进行分块查找，并假定每个子表的长度为，则N进行分块查找的平均查找长度为。96在一棵二叉树排序中，每个分支结点的左子树上所有结点的值一定该结432A16241055图11014点的值，右子树上所有结点的值一定该结点的值。97从一棵二叉排序树中查找某个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向查找，若元素的值大于根结点的值，则继续向查找。98向一棵二叉排序树种插入一个元素时，若元素的值小于根结点的值，则接着向根结点的插入，若元素的值大于根结点的值，则接着向根结点的插入。99在一棵平衡二叉排序树中，每个结点的左子树深度与右子树深度之差的绝对值不超过。100假定对线性表（38，25，74，52，48），进行散列存储，采用H（K）K7作为哈希函数，采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到次冲突。101假定对线性表（38，25，74，52，48）进行散列存储，采用H（K）K7作为哈希函数，采用线性探测再散列法处理冲突，则平均查找长度为。102在线性表的散列存储中，装填因子A又称装填系数，若用M表示散列表的长度，N表示散列存储的元素个数，则A等于。103对线性表（18，25，63，50，42，32，90）进行散列存储时，若选用H（K）K9作为哈希函数，则散列地址为0的元素有个，则散列地址为5的元素有个。104每次从无序子表中取出一个元素，把它插入到有序子表的适当位置，此种排序方法叫做排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一段，此种排序方法叫做排序。105若对一组记录（46，79，56，38，40，80，35，50，74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较次。106排序方法能够每次使无序表中的第一个记录插入到有序表中。107对N个记录进行冒泡排序时，最少的比较次数为，最少的趟数为。108假定一组记录为（46，79，56，38，40，84），在冒泡排序过程中进行第一趟排序后的结果为。109假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序过程中进行第一趟排序时，元素97将最终下沉到其后第位置。110排序方法使键值达的记录逐渐下沉，使键值小的记录逐渐上浮。111假定一组记录为（46，79，56，38，40，80）对其进行快速排序的过程中，共需要趟。112假定一组记录为（46，79，56，25，76，38，40，80）对其进行快速排序的第一次划分后，右区间内元素个数为。113假定一组记录为（46，79，56，38，40，80），对其进行快速排序的第一次划分后的结果为。114在所有排序方法中，排序方法采用的是折半查找法的思想。115在简单选择排序中，记录比较次数的时间复杂度为，记录移动次数的时间复杂度为。116若对一组记录（46，79，56，38，40，80，35，50，74）进行简单选择排15序，用K表示最小值元素的下标，进行第一趟是可得初值为1，则在第一趟选择最小值的过程中，K的值被修改次。117在时间复杂度为O（N2）的所有排序方法中，排序方法使不稳定的。118假定一个堆为（38，40，56，79，46，84），则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为。119在所有排序方法中，方法使数据的组织采用的是完全二叉树的结构。120排序方法能够每次从无序表中查找出一个最小值。三、名词解释1数据2数据元素3数据对象4数据结构5逻辑结构6时间复杂度7空间复杂度8栈9队列10压缩存储11树形结构12结点的度13树的度14树的深度15有序树16遍历17哈夫曼树18邻接关系19路径20连通图21强连通图22完全无向图23完全有向图24主关键字四、简答题1简述线性结构，树形结构，网状结构的不同。2简述算法复杂度的评价方法。3设有两个算法在同一台机器上运行，其执行时间分别为100N2和2N,要使前者快于后者，N至少为多大4在顺序表中插入和删除一个结点需平均移动多少个结点，具体移动的次数取决于哪些因素5简述定义线性表、单链表、线性表的存储方式、循环链表、双向链表。6在单链表，双向链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将P从相应的链表中删去若可以，其时间复杂度分别为多少7有哪些链表可仅有一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点8何时选用顺序表，何时选用链表作为线性表的存储结构9简述栈与队列的不同之处。10设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序压入其中，请回答下述问题（1）若入、出栈次序为PUSH1,POP,PUSH2,PUSH3,POP,POP,PUSH4,POP,则出栈的数字序列如何（2）能否得到出栈序列1423和1432，并说明为什么不能得到或者如何得到。（3）请分析1，2，3，4的各种排列中，哪些序列是可以通过相应的入,出栈操作得到的。11举例说明栈的“上溢”和“下溢”现象。12循环队列的优点是什么如何判别它的空和满13假定用一维数组A7顺序存储一个循环队列，队首和队尾指针分别用FRONT和REAR表示，当前队列中有5个元素23，45，67，80，34，其中23为队首元素，FRONT的值为3，请画出对应的存储状态，当ABD图111CFE16连续进行4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。14空串和空格串有何区别字符串中空格符有何意义空串在串的处理中有何作用15两个字符串相等的充要条件是什么16二叉树和树之间有何区别一棵度为2的树与二叉树有何区别17在一棵二叉树如图111所示。写出对此树进行先序，中序，后序遍历时得到的结点序列。18已知一棵二叉树的中序遍历序列为CDBAEGF,先序遍历序列为ABCDEFG,试问能不能唯一确定一棵二叉树若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一确定19将图112所示的树转换成二叉树。20一棵度为2的有序树与一棵二叉树有何区别21试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。22高度为H的完全二叉树至少有多少个结点至多有多少个结点23试采用顺序存储方法和链式存储方法分别画出如图113所示各二叉树的存储结构。24假定用于通信的电文由8个字母组成，分别是A，B，C，D，E，F，G，和H，各字母在电文中出现的概率为5，25，4，7，9，12，30，8，试为8个字母设计哈夫曼编码。25根据如图114所示的带权有向图G，试回答下面问题（1）给出从结点V1出发按深度优先搜索遍历G所得的结点序列，并给出按广度优先搜索遍历G所得的结点序列。（2）给出从结点V1到结点V8的最短路径。26对于如图115所示的有向图，请给出ABE图112DCFGHLM12图113133424231A5431464图114678650112242083812ADEFBC图11517（1）对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度。（2）邻接表表示和逆邻接表表示。（3）强连通分量。27假设图的顶点是A，B，C，D，请根据下述邻接矩阵画出相应的有向图和无向图。（1）0111（2）0110010110001011011000111100101028对N个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题（1）图中有多少条边（2）任意两个顶点I和J是否有边相连（3）任意一个顶点的度是多少29试述顺序查找法，折半查找法和分块查找法对查找表中元素的要求。30若有一个长度为N的表，其查找该表中每个元素的概率相同，采用顺序查找、折半查找和分块查找3种查找方法进行查找时的其平均查找长度各为多少31设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答下列问题（1）设计一个适合该散列表的哈希函数。（2）用设计的哈希函数将上述关键字插入到散列表中，画出其结构，并指出用线性探测再散列法解决冲突时构造散列表的装填因子为多少32选择排序算法是否稳定为什么33给出一组关键字（19，01，26，92，87，11，43，87，21），进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次数。34直接插入排序算法是否稳定为什么35堆排序为什么是不稳定的排序试举例说明。五、应用题1指出下列每个算法的功能并求出其时间复杂性。（1）INTSUM1（INTN）INTP1,S0FORINTI1；INEXT11HLNEXTNULLHLNEXTHL12循环13PNEXTNEXT14PNEXT15PNEXTHEADHEADP16O1ON17相同18前趋；后续19Q20PPRIOR21先进后出；先进先出220123栈顶指针；插入（写入）24栈顶元素栈顶指针251；M126PNEXTTOPTOPP27TOPNEXT28PUSHS,3POPSPUSHS,529POPSPOPSPUSHS,D30队尾；队首31FRONTREARR1MFRONT32FRONT1MR1M330N134队尾指针；插入（写入）35PNEXTNULLRFP36PNEXTRNEXTRRNEXTP37（FRONTREAR）I和J536542I；2I1；I/25516565；857A；F；空582；2；359A10A11A260A2I1A2I2AI1/2612N,N1,N1622H12H163163164ABCDEFCBAEDFCBEFDA6524366456736848769图状70271NN1/2NN1724732474N175邻接矩阵；邻接表76177378479780NN81E2E82出边；入边83ACDEBACEDB答案不唯一84ACFEBDACEFBD答案不唯一85深度；广度86唯一87（N1）/288N1IICP8920541901BN1916239213936199411951N96小于；大于97查找成功；左子树；右子树98左子树；右子树99110051012102N/M10332104插入；选择1054106直接插入107N1110846,56,38,40,79,841094110冒泡11131124113403846567980114快速115ON2ON1162117快速118（40，46，56，79，84，38）119堆排序120简单排序三名词解释1数据是指反映客观事物的信息的集合，它是数据结构所要描述的东西。22数据元素是数据的一个个体，它是数据的基本单位。3数据对象是指在数据这个集体中人们感兴趣的一个子集，通常，数据对象中的元素具有某些相同的特性。4数据结构是指相互之间有关联的数据元素的集合。5逻辑结构是指数据之间的逻辑关系。6算发在计算机执行时在时间资源方面消耗的多少。7算发在计算机执行时在空间资源方面消耗的多少。8栈是被限定为仅能在表尾进行插入和删除运算的线性表。9列对是一种只允许在表的一端进行插入，而在另一端进行删除的受限的线性表。10压缩存储是指给多个值相同的元素只分配一个空间，对零元素不分配空间。2411树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。12一个结点的子树的个数称为该结点的度。13树的所有结点中最大的度称为树的度。14树的深度是指树的所有结点中最大的层次，又称树的高度。15有序树是指如果一棵树所有结点的子结点的左右顺序不可颠倒的树。16遍历是指循某条线路，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。17哈夫曼树是指以文本中出现的字符为叶子结点的最优二叉树，其中叶子结点的全值为该字符在文本中出现的几率。18邻接关系是指在无向图中若存在边（VI，VJ），则称结点VI邻接于VJ或结点VJ邻接于VI；在有向图中若存在边（VI，VJ），则称结点VJ邻接于结点VI。19路径是连接两个结点的边的集合。20如果无向图中的任意两个结点都是通的，则称无向图是连通图。21在有向图中，任意一对结点VI和VJ之间都存在路径，则称有向图为强连通图。22若一个有向图中每一对结点之间都存在一条边，则称无向图为完全无向图。23若一个有向图中每一对结点之间都存在两条不同的边，则称有向图为完全有向图。24主关键字是指能用来唯一标识该记录的数据项。四简答题1线性结构是指数据元素之间存在一对一的关系。树型结构是指元素之间存在一对多的关系。图或网状结构是指数据元素之间存在多对多的关系。2算法的复杂度分析可分为时间复杂度和空间复杂度。时间复杂度以基本操作重复执行的次数为算法的时间量度。空间复杂度指算发所存储空间的量度。3要使100N2快于2N时,必须满足100N22N,可以算出N的值为15时,2N恰好大于100N2,所以至少应该是154插入一个结点要平均移动N/2结点；删除一个结点要平均移动（N1）/2结点；具体的移动次数取决于N的大小和插入或删除的位置这两个因素。5线性表是指由N（N0）个数据元素A0,A1A2AN2,AN1组成的有限序列。该序列要么为空或仅有一个元素，要么除了第一个元素没有前趋以及最后一个元素没有后续之外，其他元素都有且仅有一个前趋，也有且仅有一个后续。线性表可以表示为AI|I属于0，N1单链表是指必须是有一个称为表头的指针向连接，N个结点形成一个链，且每个结点只有一个指针域的线性表。线性表的存储方式是指线性表的存储方式分为线性存储和链式存储两种，其中顺序存储是指线性表的顺序存储，链式存储是指线性表中的每一个结点其物理位置可连续，也可不连续，但是各结点间通过指针相连。循环链表是指把单链表的末尾结点种的指针域指向头结点，形成环型的链表。双向链表是指必须具有一个头指针，每个结点有两个指针域，一个指向该结点的前趋，一个指向该结点的后继的线性表。256在单链表中不能删除，而在双链表和单循环莲表中可以删除P结点。双向链表的删除P结点的时间复杂度为O1，单循链表删除P结点的时间复杂度为O（1）。7在循环链表中可以由尾指针表示。8因为