数据结构习题及答案.doc

此文档收集于网络，如有侵权，请联系网站删除数据结构习题及答案第1章 数据结构一、选择题1.算法指的是（）。A计算机程序 B解决问题的计算方法C排序方法 D解决问题的有限运算序列2.在数据的树形结构中，数据元素之间为（ ）的关系。A 0:0 B 1:1 C 1:n D m:n3.数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。A索引 B数组 C集合 D向量4.一个数组元素ai与（ ）的表示等价。A &a+i B *(a+i) C *a+i D a+i5.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为（ ）参数。A指针 B引用 C值 D指针引用6.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为（ ）参数。A指针 B引用 C值 D指针引用7.下面程序的时间复杂性的量级为（）。int i=0，s1=，s2=0；while（i+n） if (i%2) s1+=i;else s2+=i;A.O(1) B.O(1bn) C.O（n） D.O(2n)8.下面程序段的时间复杂度为（ ）。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j;A.O(m2) B.O(n2) C.O(m+n) D.O(m*n)9.执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i=n;i+) for(int j=1,jnext=ph; B. p-next=ph; ph=p;C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p;21.在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. q-next=p-next; p-next=q; D. p-next=q-next; q-next=p;22.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。A. p=q-next; p-next=q-next; B. p=q-next; q-next=p;C. p=q-next; q-next=p-next; D. q-next=q-next-next; q-next=q;23.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）。A. P-prior B. p-nextC. p-next-next D.p-prior-prior24.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p-prior-next赋值为（）。A. q B. p C. p-next D. p-prior25. 在一个带头结点的循环双向链表中，若要删除指针p所指向的结点则执行（）操作。A. p-prior-next=p-next; p-next-prior=p-prior;B. p-next-prior=p; p-next=p-next-next;C. p-prior-next=p; p-next=p-next-prior;D. p=p-next; p-prior-next=p-prior;26.栈的插入和删除操作在（）进行。A. 栈顶 B. 栈底C. 任意位置D. 指定位置27.当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top+ B.top- C.top=0 D.top=N-128.假定利用数组aN顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（）。A.top=1 B.top=-1 C.top=0 D.top=N-129. 假定利用数组aN顺序存储一个栈，用top表示栈顶指针，用top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A.a-top=x B.atop-=x C.a+top=x D.atop+=x30. 假定利用数组aN顺序存储一个栈，用top表示栈顶指针，用top=-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（）。A return a-top B return atop- C return a+top D return atop+31.假定一个链式栈的栈顶指针用top表示，该链式栈为空的条件（）。A.top！=NULL; B. top=top-next; C. top= NULL; D. top！= top-next;32.假定一个链式栈的栈顶指针用top表示，每个结点结构为,当p所指向的结点进栈时，执行的操作为（）。A. p-next=top; top=top-next; B. top=p; p-next=top;C. p-next=top-next; top-next=p; D. p-next=top; top=p;33.假定一个链式栈的栈顶指针用top表示，每个结点结构为,退栈时所执行的操作为（）。A.top-next=top；B.top=top-data;C.top=top-next; D. top-next=top-next-next;34.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（ ）的情况。A.3，2，1，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3.35.在一个顺序循环队列中，队首指针指向队首元素的（）位置。A前一个 B后一个 C当前 D最后36.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（）。A.N-2 B.N-1 C.N D.N+137.从一个顺序循环队列中删除元素时，首先需要（）。A.前移队首指针 B.后移队首指针C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素38.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。A.f+1=r B.r+1=f C.f=0 D.f=r39.假定一个顺序循环队列存储于数组aN，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。A.（r-1）%N=f B.（r+1）%N=f C.（f-1）%N=r D.（f+1）%N=r40.假定利用数组aN循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未满，当元素x入列时所执行的操作为（）。A.a+r%N=x B.ar+%N=x C.a-r%N=x D.ar-%N=x41.假定利用数组aN循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（）。A.return a+r%N B.return a-r%N C.return a+f%N D.return af+%N42.假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为（）。A.front=rear B.front！=NULL C.rear！=NULL D.front=NULL43.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为,当出列时所进行的操作为（）。A.front=front-next B.rear=rear-nextC.front-next =rear；rear=rear-nextD.front=front-next；front-next =rear；44.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为（）。A.front=rear-next B.rear=NULL C. front=NULL D. front =rear45.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为包含值域data和指针域next,则使p所指结点入列所执行的操作为（）。A.p-next=NULL；rear=rear-next=p；B.p-next=rear-next；rear=rear-next=p；C.p-next=front；front=p；D.p-next=front-next；front-next=p；46.在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中数组元素个数为（）。A.（rear-front）%N B.（rear-front+N）%NC.（rear+N）%N D.（front+N）%N47.二维数组A12,10采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A0，0的地址）为1200，则A6，5的地址为（）。A.1400 B.1404 C.1372 D.146048.有一个MN的矩阵A，若采用行优先进行顺序存储，每个元素占用8个字节，则Aij(1iM,1jN)元素的相对字节地址（相对首元素地址而言）为（）。A.（i-1）N+j）8 B.（i-1）N+j-1）8C.（iN+j-1）8 D.（i-1）N+j+1）849.有一个NN的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1iN,1ji)元素的相对字节地址（相对首元素地址而言）为（）。A.（i（i+1）/2+j-1）4 B.（ii/2+j）4C.（i（i-1）/2+j-1）4 D.（i（i-1）/2+j）450.树中所有结点的度等于所有结点数加（）。A.0 B.1 C.-1 D.251.在一棵树中，（）没有前驱结点。A.树枝结点 B.叶子结点 C.树根结点 D.空结点52.在一棵树中，每个结点最多有（）个前驱结点。A.0 B.1 C.2 D.任意多个53.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2 B.1 C.0 D.-154.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.n B.n-1 C.n+1 D.2n55.在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。A.2i B.2i+1 C.2i-1 D.2n56.在一棵深度为h的完全二叉树中，所含结点个数不小于（）。A.2h B.2h+1 C.2h-1 D.2h-157.在一棵深度为h的完全二叉树中，所含结点个数不大于（）。A.2h B.2h+1 C.2h-1 D.2h-158.在一棵具有35个结点的完全二叉树中，该树的深度为（）。A.6 B.7 C.5 D.859.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点编号为（）。A.2i B.2i-1 C.2i+1 D.2i+260.在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点编号为（）。A.2i B.2i-1 C.2i+1 D.2i+261.在一棵完全二叉树中，对于编号为i（i1）的结点其双亲结点的编号为（）。A.（i+1）/2 B.（i-1）/2 C.i%2 D.i/262.有如图1.1所示的一棵二叉树，则该二叉树所含单支结点数为（）。A.2 B.3 C.4 D.563.有如图1.2所示的一棵二叉树，则该二叉树的中序遍历序列为（）。A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG64.有如图1.2所示的一棵二叉树，则该二叉树的先序遍历序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG65.有如图1.2所示的一棵二叉树，则该二叉树的后序便利序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG66.利用n个值生成的哈夫曼树中共有（）个结点。A.n B.n+1 C.2n D.2n-167.利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。A.55 B.29 C.58 D.3868.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的入度数之和为（）。A.s B.s-1 C.s+1 D.n69.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的度数之和为（）。A. s B. s -1 C. s +1 D.2s70.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数为（）。A.n B.e C.n+e D.2e71.在一个具有n个顶点的无向完全图中，所含的边数为（）。A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2 72.在一个具有n个顶点的有向完全图中，所含的边数为（）。A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/273.在一个具有n个顶点的无向连通图中，它包含的连通分量的个数为（）。A.0 B.1 C.n D.n+174.若有一个图中包含k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。A.k B.1 C.k-1 D.k+175.若要把n个顶点连接为一个连通图，则至少需要（）条边。A.n B.n+1 C.n-1 D.2n76.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。A.n B.ne C.e D.2e77.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。A.n B.ne C.e D.2e78.在一个具有n个顶点和e条边的无向图的邻接矩阵中，边结点的个数为（）。A.n B.ne C.e D.2e79.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表的边数结点为（）。A.k1 B.k2 C.k1-k2 D.k1+k280.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表的边数结点为（）。A.k1 B.k2 C.k1-k2 D.k1+k281.对于一个无向图，下面（）的说法是正确的。A.每个顶点的入度等于出度 B.每个顶点的度等于入度和出度之和C.每个顶点的入度为0 D.每个顶点的出度为082.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。A.出边数 B.入边数 C.度数 D.度数减一83.若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（）。A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC84.若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE85.若一个图的边集（1，2）（1，4）（2，5）（3，1）（3，5）（4，3），则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（）。A.1，2，5，4，3 B.1，2，3，4，5 C.1，2，5，3，4 D.1，4，3，2，586.若一个图的边集（1，2）（1，4）（2，5）（3，1）（3，5）（4，3），则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A. 1，2，3，4，5 B. 1，2，4，3，5 C. 1，2，4，5，3 D. 1，4，2，5，387.由一个具有n个顶点的连通图生成的最小树中有（）条边。A.n B.n-1 C.n+1 D.2n88.若查找每一个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）。A. n B. n+1 C. (n-1)/2 D. (n+1)/289.对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找长度为（）。A. n/2 B.（n+1）/2 C. (n-1)/2 D.n/490.对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（）的值除以9。A.20 B.18 C.25 D.2291.对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（）。A.2 B.3 C.4 D.692.对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（）。A.2 B.3 C.4 D.593.在分块查找中，若用于保存数据元素的主表长度为n，它被分为k个子表，每个子表的长度均为n/k，若用顺序查找确定块，则分块查找的平均查找长度为（）。A.n+k B.k+n/k C.（k+n/k）/2 D.（k+n/k）/2+194.在分块查找中，若用于保存数据元素的主表长度为144，它被分为12个子表，每个子表的长度均为12，若用顺序查找确定块，则分块查找的平均查找长度为（）。A.13 B.24 C.12 D.7995.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。A.n B.lbn C.（h+1）/2 D.h96.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（）。A.-11 B.-22 C.12 D.0197.若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用H（K）=K%13计算哈希地址，则元素64的哈希地址为（）。A.4 B.8 C.12 D.1398.若根据查找表（23，44，36，48，52，73，64，58）建立线形哈希表，采用H（K）=K%13计算哈希地址，则哈希地址为3的元素个数为（）。A.1 B.2 C.3 D.499.若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。A.d B.d+1 C.（d+1）/m D.（d+1）%m100.在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子a的值为0.5，则查找任一个元素的平均查找长度为（）。A.1 B.1.5 C.2 D.2.5101.在哈希查找中，平均查找长度主要与（）有关。A.哈希表长度 B.哈希元素个数 C.装填因子 D.处理冲突方法102.若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中元素的个数为（）。A.i B.i+1 C.i-1 D.1103.若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位子最多需要进行（）次元素的比较，假定第0号元素放有待查的键值。A. i B.i-1 C.i+1 D.1104.若对n个元素进行直接插入排序，在进行第i趟排序时,假定元素ri+1的插入位置为rj，则需要移动元素的次数为（）。A.j-i B.i-j-1 C.i-j D.i-j+1105.若对n个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。A.O（1） B.O（n） C.O（n2） D. O（lbn）106.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A.n B.n+1 C.n-1 D.2n107.对n个元素进行直接插入排序的时间复杂度为（）。A.O（1） B.O（n） C.O（n2） D. O（lbn）108.在对n个元素进行冒泡排序的过程中，第一趟排序至多进行（）对相邻元素之间的交换。A .n B.n-1 C.n+1 D.n/2109.在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。A.O（1） B.O（lbn） C.O（n2） D.O（n）110.在对n个元素进行冒泡排序的过程中，至多需要（）趟完成。A .1 B.n C.n-1 D.n/2111.在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟。A.n B.n/2 C.lbn D.2n112.在对n个元素进行快速排序的过程中，最坏情况下需要进行（）趟。A.n B.n-1 C.n/2 D.lbn113.对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。A.1，3，5，7，9 B.9，7，5，3，1 C.5，3，1，7，9 D.5，7，9，1，3114.假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。A.2 B.3 C.4 D.5115.在对n个元素进行简单选择排序的过程中，在第i趟需要从（）个元素中选择出最小值元素。A.n-i+1 B.n-i C.i D.i+1116.若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）。A.O（1） B.O（lbn） C.O（n2） D. O（n）117.假定一个初始堆为（1，5，3，9，12，7，15，10），则进行第一趟堆排序后得到的结果为（）。A.3，5，7，9，12，10，15，1 B.3，5，9，7，12，10，15，1C.3，7，5，9，12，10，15，1 D.3，5，7，12，9，10，15，1118.若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序119.若要从1000个元素中得到10个最小元素，最好采用（）方法。A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序120.在平均情况下速度最快的排序方法为（）。A.简单选择排序 B.冒泡排序 C.堆排序 D.快速排序二填空题1.数据的逻辑结构可分为_和_两大类。2.数据的存储结构被分为_，_，_和_4种。3.在下面的程序段中，s=s+p语句被执行次数为_，p*=j语句的执行次数为_,该程序的复杂度为_。int i=0，s=0；while（+i=n） int p=1;for(int j=1;j=i;j+)p*=j;s=s+p;4.一种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,f,g,h R=，则该数据结构具有_结构。5.线性表的两种存储结构分别为_和_。6.线性表的顺序存储结构称为_，链式存储结构称为_。7.若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行查找运算，则最好采用_存储结构。8.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_。9.对于一个单链表存储的线性表，在表头插入结点的时间复杂度为_，在表尾插入结点的时间复杂度为_。10.在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后的断结点的地址为_。11.在以HL为头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为_和_。12.在_链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。13.在一个单链表中删除指针p所指向结点的后继结点时，需要把_的值赋给p-next指针域。14.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的节点时，首先把_的值赋给p-next，然后把_的值赋给p-next。15.假定指向单链表中第一个结点的头指针为head，则像该单链表的表头插入指针p所指向的新结点时，首先执行_赋值操作，然后执行_赋值操作。16.访问一个顺序表和一个单链表中第i个元素的时间复杂度分别为_和_。17.在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作过程是否相同？_。18.在双向链表中每个结点包含有两个指针域，一个指向其_结点，另一个指向其_结点。19.在一个双向链表中指针p所指向的结点之后插入一个指针q所指向的结点时，需要对p-next-prior指针域赋值为_。20.在一个双向链表中删除指针p所指向的结点时，需要对p-next-prior指针域赋值为_。21.栈又称为_表，队列又称为_表。22.在一个用一维数组aN表示的顺序栈中，该栈所含元素的个数最少为_个，最多为_个。23.像一个顺序栈插入一个元素时，首先使_后移一个位置，然后把新元素_到这个位子。24.从一个栈删除元素时，首先取出_，然后再使_减一。25.一个顺序栈存储一个一维数组aM中，栈顶指针用top表示，当栈顶指针等于_时为空栈，栈顶指针为_时为满栈。26.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行_操作，然后执行_操作。27. 假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（假定栈非空），需要把栈顶指针修改为_的值。28.设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为Push(s,1),Push(s,2),_,Pop(s),Push(s,4),Pop(s),_,_,Pop(s),Pop(s)。29.设元素a，b，c，d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(s,a),push(s,b),push(s,c),_,_，_pop(s),pop(s)。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和它的二元关系R为：K=a,b,c,d,e,f,g,hR=，则该数据结构具有_结构。45.对于一棵具有n个结点的树，则该树中所有结点的度数之和为_。46.在一棵树中，_结点没有前驱结点，其余每个结点有并且只有一个_，可以有人以多个_结点。47.如图1.3所示为一棵树，该树的叶子结点数为_个，单支结点数为_个，双分支结点数为_个，三分支结点数为_个。48.如图1.3所示的一棵树，结点K的所有祖先的结点数为_个，结点B的所有子孙结点数为_个。49.如图1.3所示的一棵树，结点D和X的层数分别为_和_。50.如图1.4所示的一棵树，则树中所含的结点数为_个，树的深度为_，树的度为_。51.如图1.4所示的一棵树，则度为3，2，1，0的结点数分别为_，_，_。52.如图1.4所示一棵树，则结点H的双亲为_，孩子结点为_。53.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_。54.对于一棵二叉树，若一个结点的编号i，若它的左孩子结点存在，则其编号为_，若右孩子结点存在，则其编号为_，若双亲结点存在，则其编号为_。55.在一棵二叉树中，第5层上的结点数最多为_。56.假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。57.如图1.5所示为一棵二叉树，则E结点的双亲结点数为_，左孩子结点为_，右孩子结点为_。58.如图1.5所示为一棵二叉树，它含有双支结点_个，单分支结点_个，叶子结点_个。59.假定一棵二叉树顺序存储在一维数组a中，若a5元素的左孩子存在则对应的元素为_，若右孩子存在则对应的元素为_，双亲元素为_。60.若对一棵二叉树从0开始进行结点编号，并按此编号把它存储到一维数组a中，即编号为0的结点存储到a0中，依次类推，则ai元素的左孩子为_，右孩子为_，双亲元素（i0）为_。61.对于一棵具有n个结点的二叉树，对应_二叉链表中指针总数为_个，其中_个用于指向孩子结点，_个指针空闲。62.在一棵深度为h的完全平衡二叉树中，最少含有_个结点，最多含有_个结点。63.一棵深度为5的完全二叉树中的结点数最少为_个，最多为_个。64.如图1.6所示为一棵二叉树，对它进行先序遍历结果为_。65.若将如图1.7所示为一棵树转换为二叉树，该二叉树中双支结点的个数为_个，单支结点的个数为_个，叶子结点个数为_。66.一棵树转换为二叉树后如图1.8所示，则原树中分支结点数为_，叶子结点数为_。67.一个树林转换成二叉树后如图1.9所示，则该素林中包含_棵树。68.若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的深度为_，带权路径长度为_。69.一种数据结构的元素集合K和它的二元关系R为：K=1，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.若一个图的边集为，则从顶点V0到顶点V4共有条简单路径。79.如图1.10所示为一个带权有向图，从顶点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.假定对长度n=50的有序表进行折半查找，则对应的判定树深度为，最后一层的结点数为。94.在分块查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行分块查找的平均查找长度为。95.假定对长度为n的有序表进行分块查找，并假定每个子表的长度为，则进行分块查找的平均查找长度为。96.在一棵二叉树排序中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。97.从一棵二叉排序树中查找某个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向查找，若元素的值大于根结点的值，则继续向查找。98.向一棵二叉排序树种插入一个元素时，若元素的值小于根结点的值，则接着向根结点的插入，若元素的值大于根结点的值，则接着向根结点的插入。99.在一棵平衡二叉排序树中，每个结点的左子树深度与右子树深度之差的绝对值不超过。100.假定对线性表（38，25，74，52，48），进行散列存储，采用H（K）=K%7作为哈希函数，采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到次冲突。101.假定对线性表（38，25，74，52，48）进行散列存储，采用H（K）=K%7作为哈希函数，采用线性探测再散列法处理冲突，则平均查找长度为。102.在线性表的散列存储中，装填因子a又称装填系数，若用m表示散列表的长度，n表示散列存储的元素个数，则a等于。103.对线性表（18，25，63，50，42，32，90）进行散列存储时，若选用H（K）=K%9作为哈希函数，则散列地址为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）进行简单选择排序，用k表示最小值元素的下标，进行第一趟是可得初值为1，则在第一趟选择最小值的过程中，k的值被修改次。117.在时间复杂度为O（n2）的所有排序方法中，排序方法使不稳定的。118.假定一个堆为（38