数据结构自考查找

1、 0 到 8，列号从 0 到 10，数组中每个元素所占的存储空间为 3 个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。
A240 B297 C270 D300（分数：2.00）A.B.C.D.4.顺序存储结构 ( ) A仅适合于静态查找表的存储 B仅适合干动态查找表的存储 C既适合静态又适合动态查找表的存储 D既不适合静态又不适合动态查找表的存储（分数：2.00）A.B.C.D.5.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)（分数：2.00）A.B.C.D.6.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( ) A3 B5 C6 D7（分数：2.00）A.B.C.D.7.在一棵具有 5 层的满二叉树中，结点总数为( )。

2、B）紧凑结构和非紧凑结构（C）动态结构和静态结构（D）内部结构和外部结构4 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。
（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以5 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_。
（A）每个数据元素都一样（B）数据元素具有同一特点（C）数据元素所包含的数据项的个数要相等（D）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致6 算法是指_。
（A）程序（B）计算方法（C）操作的描述（D）问题求解步骤的描述7 以下有关抽象数据类型的描述中，正确的是_。
（A）抽象数据类型是一个值的集合（B）抽象数据类型是数据的逻辑结构及操作的组合（C）抽象数据类型的操作可以没有操作结果（D）抽象数据类型只能用 C 语言来描述8 分析下列程序段的时间复杂度是_。
i=1：while(i，画出这个逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点?25 设有如下图所示的逻辑结构，。

3、 n 个顶点的完全图具有 n(n 一 1)条边（C）完全图是无向图（D）完全图是有向图4 以下有关连通分量的说法中，正确的是_。
（A）连通分量是有向图中的极小连通子图（B）连通分量是无向图中的极小连通子图（C）连通分量是有向图中的极大连通子图（D）连通分量是无向图中的极大连通子图5 以下哪个路径不是简单路径_。
（A）v1，v2，v4，v2（B） v1，v2，v4，v5（C） v1，v2，v5，v4（D）v1，v2，v3，v56 在一个含 n 个顶点的连通图中，任意一条简单路径的长度都不可能超过（A）n2（B） n 一 1（C） n（D）n+17 十字链表适用于_。
（A）完全图（B）连通分量（C）无向图（D）有向图8 具有 n 个顶点的连通图，其最小生成树具有_条边。
（A）n2（B） n-1（C） n（D）n+19 任何一个带权的无向连通图，其最小生成树一定有_。
（A）1 棵（B） n 棵（C） 1 棵或 n 棵（D）0 棵10 如下图所示的有向图，其深度优先搜索遍历序列为_。
（A）ABEFDC（B） 。

4、 2004 年】（A）(n 1)2（B） n2（C） (n+1)2（D）n3 当采用分块查找时，数据的组织方式为_。
【太原科技大学 2007 年】（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同4 对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。
【华中科技大学 2007 年】（A）50（B） 125（C） 500（D）log 225005 下面关于二分查找的叙述正确的是_。
【南京理工大学 1996 年】（A）表必须有序，表可以顺序方式存储，也可以链表方式存储（B）表必须有序且表中数据必须是整型、实型或字符型（C）表必须有序，而且只能从小到大排列（D）表必须有序，且表只能以顺序方式存储6 当 n 足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是_。
【北京航空航天大学 200。

5、rior=p； pnextprior=s； pnextprior=s； sprior=p； snext=pnext； s next=pnext（C） sprior=p ；（D）sprior=p； snext=p next； snext=pnext； pnext=s； p nextprior=s； pnextprior=s； pnext=s；3 在下面的程序中，语句 S 的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （A） else return(0); 32 以下算法在有序表 R 中用二分查找法查找键值等于 K 的元素，请分析程序，并在_上填充合适的语句。
int binsearch(sqtable R,keytype K) low=l;hig=R.n;/*置查找区间初值。
low，hig 分别标记查找区间的下、上界 */while(low=hig) mid=(low+h。

6、b c d e3 带头结点的单链表 head 为空的判断条件是( )（A）head=NULL（B） headnext=NULL（C） headnext=head（D）head!=NULL4 非空的单循环链表 L 的尾结点 P，满足( )（A）P.next=NULL;（B） P=NULL;（C） P.next=L;（D）P=L5 在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )（A）箱排序（B）快速排序（C）插入排序（D）希尔排序6 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )（A）数据元素具有同一特点（B）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致（C）每个数据元素都一样（D）数据元素所包含的数据项的个数要相等7 从具有 n 个结点的单链表中查找值等于 x 的结点时，在查找成功的情况下，平均需比较( ) 个结点。
（A）n（B） n/2（C） (n-1)/2（D）(n+1)/28 在一个链队列中，若 f，r 分别为队首、队尾指针，则插入 s 所指结点的操作为( )（A）fnext=c;f=s;（B）。

7、ar=(rear+1)%m（D）front=(front+1)%(m+1)3 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是bgbaechf，则其后序遍历的结点访问顺序是( )（A）bdgcefha（B） gdbecfha（C） bdgechfa（D）gdbehfca4 如果以链表作为栈的存储结构，则退栈操作时( )（A）必须判别栈是否满（B）判别栈元素的类型（C）必须判别栈是否空（D）对栈不作任何判别5 在一个具有 n 个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以 top作为栈顶指针，则作退栈操作时，top 的变化是( )（A）top=top-1（B） top=top+1（C） top 不变（D）top 不确定6 对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。
（A）顺序存储（B）链式存储（C）顺序存储且结点按关键字有序（D）链式存储且结点按关键字有序7 在一棵完全二叉树的顺序存储方式中，若编号为 t 的结点有右孩子，则此结点右孩子的编号为( )（A）2t（B） 2t-1（C） 2t+1（D）t/28 对于一个具有 。

8、操作是 ( )（A）pnext=pnextnext;（B） p=pnext;p next=pnextnext;（C） pnext=p next;（D）p=pnext next;4 深度为 6(根的层次为 1)的二叉树至多有( ) 个结点。
（A）31（B） 32（C） 63（D）645 设二叉树有 n 个结点，则其深度为 ( )（A）n-1（B） n（C）（D）不确定6 在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )（A）先根遍历（B）中根遍历（C）后根遍历（D）按层次遍历7 一个栈的入栈序列为 a1,a2,a3,a4,a5，则此栈不可能的输出序列是 ( )（A）a5,a4,a3,a2,a1（B） a4,a5,a3,a2,a1（C） a4,a3,a5,a1,a2（D）a1,a2,a3,a4,a58 设 rear 是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )（A）s=rear;（B） rear=rearnext; rear=rearnext; free(r。

9、 04,13,27,38,49,49,55,65,76,97（C） 13,04,49,38,27,49,55,65,97,76（D）13,27,49,55,04,49,38,65,97,763 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。
（A）快速排序（B）插入排序（C）选择排序（D）归并排序4 长度为 12 的按关键字有序的查找表采用顺序组织方式。
若采用二分查找方法，则在等概率情况下，查找失败时的 ASL 值是( )（A）13850（B） 62/13（C） 14580（D）49/135 一个具有 N 个顶点的有向图最多有( )条边。
（A）N(N-1)/2（B） N(N-1)（C） N(N+1)（D）N(N+1)/26 Aarr 和 Barr 两个数组的说明如下： VAR Aarr:ArrayO7of char; Barr:Array-52,3,8of char; 这两个数组分别能存放的字符的最大个数是( )（A）7 和 3。

10、针，rear 为队尾指针，则执行出队操作的语句为( )（A）front:=front+1（B） front:=(front+1)mod m（C） rear:=(rear+1)mod m（D）front:=(front+1)mod(m+1)4 在一个长度为 n 的顺序表(顺序存储的线性表)中，向第 i 个元素(1in+1) 之前插入一个新元素时，需向后移动( )个元素。
（A）n-i（B） n-i+1（C） n-i-1（D）i5 线性表 L=(a1，a 2，a 1，a n)，下列说法正确的是 ( )（A）每个元素都有一个直接前趋和直接后继（B）线性表中至少要有一个元素（C）表中诸元素的排列顺序必须是由小到大或由大到小的（D）除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继6 在下图中，从顶点 V1 出发，按广度优选遍历图的顶点序列是 ( )（A）V 1 V5 V3 V4 V2 V6 V7（B） V1 V5 V3 V4 V2 V7 V6 （C） V1 V7 V2 V6 V4 V5 V3 （D）V 1 V2 V4 V7 V6 V5 V3 7 在 Has。

11、各元素等概率情况下查找成功所需的平均比较次数为( )（A）35/12 （B） 37/12 （C） 39/12 （D）43/12 3 采用分治法进行排序的方法是( )（A）快速排序（B）插入排序（C）堆排序（D）希尔排序4 下面四种内排序方法中，要求内存容量最大的是( )（A）插入排序（B）选择排序（C）快速排序（D）归并排序5 设深度为 k 的二叉树上只有度为 0 和度为 2 的结点，则这类二叉树上所含结点总数量少( ) 个。
（A）k+1（B） 2k（C） 2k-1（D）2k+16 串是一种特殊的线性表，其特殊性体现在( )（A）可顺序存储（B）数据元素是一个字符（C）可链接存储（D）数据元素可以是多个字符7 一个长度为 10 的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为( )（A）25/10 （B） 27/10 （C） 29/10 （D）31/108 从一个包含 2000 个结点的散列表 A12000中查找结点的平均比较次数 ( )从一个包含 200 个结点的散列表 B1200中查找结点的平均比较次数。
（A。

12、件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为_。
【北京航空航天大学 2004 年】（分数：2.00）A.(n1)2B.n2C.(n+1)2D.n3.当采用分块查找时，数据的组织方式为_。
【太原科技大学 2007 年】（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同4.对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。
【华中科技大学 2007 年】（分数：2.00）A.50B.125C.500D.log 2 25005.下面关于二分查找的叙述正确的是_。
【南京理工大学 1996 年】（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储6.当 n 足够大时，在。

13、ac，则它的前序遍历序列是 ( )（A）a c b e d（B） d e c a b（C） d e a b c（D）c e d b a4 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )（A）求关键路径的方法（B）求最短路径的 Dijkstra 方法（C）广度优先遍历方法（D）深度优先遍历方法5 将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为( )（A）42（B） 40（C） 21（D）206 设数组 A0,m作为循环队列 sq 的存储空间，front 为队头指针，rear 为队尾指针，则执行入队操作的语句是( )（A）sq.front=(sq.front+1)%m（B） sq.front=(sq.front+1)%(m+1)（C） sq.rear=(sq.rear+1)%m（D）sq.rear=(sq.rear+1)%(m+1)7 如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的后序就是 T2 中结点的( )（A）前序（B）中序（C）后。

14、C）后根（D）层次3 对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
（A）O（B） 1（C） 2（D）不存在这样的二叉树4 含 N 个顶点的连通图中的任意一条简单路径，其长度不可能超过 ( )（A）1（B） N/2（C） N-1（D）N5 顺序存储结构 ( )（A）仅适合于静态查找表的存储（B）仅适合干动态查找表的存储（C）既适合静态又适合动态查找表的存储（D）既不适合静态又不适合动态查找表的存储6 已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法是( )（A）将该元素所在的存储单元清空（B）将该元素用一个特殊的元素替代（C）将与该元素有相同 Hash 地址的后继元素顺次前移一个位置（D）用与该无素有相同 Hash 地址的最后插入表中的元素替代7 邻接表存储结构下图的广度优先遍历算法结构类似于树的( )（A）先根遍历（B）后根遍历（C）按层遍历（D）先序遍历8 下列说法中正确的是( )（A）二叉树中任何一个结点的度都为 2（B）二叉树的度为 2（C）任何一棵二叉树中至少有一个结点的度为 2（D）一棵二。

15、的是( )（A）顺序查找（B）二分查找（C）二叉排序树（D）B-树上的查找4 ( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。
（A）归并排序（B）插入排序（C）快速排序（D）选择排序5 在一个具有 N 个顶点的无向完全图中，包含的边的总数是 ( )（A）N(N-1)/2（B） N(N-1)（C） N(N+1)（D）N(N+1)/26 在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。
（A）snext=pnext;pnext=s;（B） qnext=s;snext=p;（C） pnext=s next;s next=p;（D）pnext=s;s next=q;7 如果一个队列的入队顺序是 1,2,3,4,5，则此队列的出队顺序是( )（A）5,4,3,2,1（B） 4,5,1,2,3（C） 1,2,3,4,5（D）不确定8 静态查找表与动态查找表二者的根本差别在于( )（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元。

16、找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。
在此假定为线性表中结点数，且每次查找都是成功的。
2 (1)（A）N+1（B） 2log2N（C） log2N（D）N23 (2)（A）N+1（B） 2log2N（C） log2N（D）N24 适用于折半查找的表的存储方式及元素排列要求为( )。
（A）链接方式存储，元素无序（B）链接方式存储，元素有序（C）顺序方式存储，元素无序（D）顺序方式存储，元素有序5 具有 12 个关键字的有序表，折半查找的平均查找长度为( )。
（A）31（B） 4（C） 25（D）56 折半查找的时间复杂性为( )。
（A）O(n 2)（B） O(n)（C） O(nlog2n)（D）O(log 2n)7 当采用分块查找时，数据的组织方式为( )。
（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干。

17、次数为( 2 )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( 3 )。
在此假定 N为线性表中结点数，且每次查找都是成功的。
A.N+1 B.2log2N C.log2N D.N/2 E.Nlog2N F.N2（分数：2.00）A.B.C.D.E.F.A.B.C.D.E.F.2.适用于折半查找的表的存储方式及元素排列要求为_。
（分数：1.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序3.具有 12个关键字的有序表，折半查找的平均查找长度为_。
（分数：1.00）A.3.1B.4C.2.5D.54.折半查找的时间复杂性为_。
A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n)（分数：1.00）A.B.C.D.5.当采用分块查找时，数据的组织方式为_。
（分数：1.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每。

18、对线性表进行折半查找时，要求线性表必须_。
A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C.D.3.采用折半查找方式查找一个长度为 n的有序顺序表时，其平均查找长度为_。
A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n)（分数：1.00）A.B.C.D.4.在对长度为 n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为_。
An BC D （分数：1.00）A.B.C.D.5.采用折半查找法查找长度为 n的有序顺序表，查找每个元素的数据比较次数_对应二叉判定树的高度(设高度2)。
A.小于 B.大于 C.等于 D.小于等于（分数：1.00）A.B.C.D.6.已知有序顺序表(13，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找值为 18的元素时，查找成功的数据比较次数为_。
A.1 B.2 。

19、2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。
（分数：2.00）A.(n 一 1)2B.n2C.(n+1)2D.n顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。
在此假定为线性表中结点数，且每次查找都是成功的。
（分数：4.00）(1).(1)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N2(2).(2)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N23.适用于折半查找的表的存储方式及元素排列要求为( )。
（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序4.具有 12 个关键字的有序表，折半查找的平均查找长度为( )。
（分数：2.00）A.31B.4C.25D.55.折半查找的时间复杂性为( )。
（分数：2.00）A.O(n 2 )B.O(n)C.O(。

20、 18，则查找任一个元素的平均查找长度为_。
（A）238（B） 208（C） 178（D）1483 下面有关折半查找的叙述中，正确的是_。
（A）数据元素必须有序排列，可以采用顺序存储，也可以采用链式存储（B）数据元素必须有序排列，且必须采用顺序存储（C）数据元素必须有序排列，而且只能从大到小排列（D）数据元素可以有序排列，也可以无序排列4 对有 14 个数据元素的有序表 a14进行折半查找，搜索到 a5的关键字等于给定值，此时元素比较顺序依次为_。
（A）a8，a5，a6，a7（B） a1，a8，a7，a6（C） a6，a4，a8，a5（D）a6，a2，a4，a55 有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功时所需平均比较次数为_。
（A）3512（B） 3712（C） 3912（D）十二月-436 当采用分块查找时，数据的组织方式为_。
（A）数据必须有序（B）数据不必有序（C）数据分成若干块，每。