A．n-iB．n-i+lC．n-i-1D．i
17.在等概率情况下，顺序表的插入操作要移动_____B_____表项。
A．全部B．一半
C．三分之一 D．四分之一
18.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_____B_______。
A．O
（1）B．O（n）
C．O（n2）D．O（log2n）
19.非空的循环单链表first的尾结点〔由p所指向〕满足：
___C____
A.p->link==NULL；
B.p==NULL；
C.p->link==first；
D.p==first；
20.对于顺序存储的线性表，其算法的时间复杂度为O
（1）的运算应是〔C〕。
A.将n个元素从小到大排序
B.从线性表中删除第i个元素〔1≤i≤n〕
C.查找第i个元素〔1≤i≤n〕
D.在第i个元素〔1≤i≤n〕后插入一个新元素
三、
21.在一个具有n个单元的顺序栈中，假定用top==n表示栈空，如此向这个栈插入一个元素时，首先应执行〔B〕语句修改top指针。
A．top++B．top--C．top=0D．top
22.向一个栈顶指针为top的链式栈中插入一个s结点时，应执行_B___。
A．top->link=s;
B．s->link=top;top=s;
C．s->link=top->link;top->link=s;
D．s->link=top;top=top->link;
23.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，如此判断队满的条件为__D____。
A．rear％n==frontB．〔front+l〕％n==rear
C．rear％n-1==frontD．（rear+l）％n==front
24.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，如此判断队空的条件为___C___。
A．rear％n==frontB．front+l==rear
C．rear==frontD．（rear+l）％n==front
25.在一个链式队列中，假定front和rear分别为队头和队尾指针，如此删除一个结点的操作为___A___。
A．front=front->nextB．rear=rear->next
C．rear=front->next D．front=rear->next
26.栈的插入和删除操作在〔A〕进展。
A．栈顶B．栈底Ｃ．任意位置Ｄ．指定位置
27.在一个链式队列中，假定front和rear分别为队头和队尾指针，如此判断队空的条件为__D___。
A．front==rearB．front!
=NULL
C．rear!
=NULL D．front==NULL
28.设链式栈中结点的结构为（data,link）且top是指向栈顶的指针。
假如想摘除链式栈的栈顶结点，并将被摘除的值保存到x中，如此应执行〔A〕操作。
A．x＝top->data;top=top->link；B．top=top->link;x=top->data;
C．x=top;top=top->link;D．x=top->data;
29.由两个栈共享一个向量空间的好处是：
〔B〕
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
30.设有一个递归算法如图，试问计算X〔X〔8〕〕时，需要计算〔D〕次X函数。
A．8次B．9次C．16次D．18次
四
单：
31.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，如此元素aij的地址为〔A〕。
A.p+[i*n+j]*kB.p+[（i-1）*n+j-1]*k
C.p+[（j-1）*n+i-1]*kD.p+[j*n+i-1]*k
32.稀疏矩阵可以采用〔B〕的压缩存储方法。
A.二维数组B.组
C.跳表D.散列
33.数组就是矩阵，矩阵就是数组，这种说法〔B〕。
A.正确B.错误
C.前句对，后句错D.后句对
34.设有广义表D=（a,b,D），其深度为〔A〕。
A.无穷大B.3C.2D.5
35.广义表A=（（x,（a,B））,（x,（a,B）,y）），如此运算head（head（tail（A）））的结果为〔A〕。
A.xB.（a,B）C.（x,（a,B））D.A
36.如下广义表用链表来表示时，分支结点最多的是〔A〕。
A.L=（（x,（a,B））,（x,（a,B）,y））B.A=（s,（a,B））
C.B=（（x,（a,B）,y））D.D=（（a,B）,（c,（a,B）,D）
37.一个广义表的表尾总是一个〔A〕。
A.广义表B.元素C.空表D.元素或广义表
38.空串与空白串组成的区别在于〔B〕。
A.没有区别B.两串的长度不相等
C.两串的长度相等D.两串包含的字符不一样
39.一个子串在包含它的主串中的位置是指〔D〕。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
40.下面的说法中，只有〔C〕是正确的。
A.字符串的长度是指串中包含的字母的个数
B.字符串的长度是指串中包含的不同字符的个数
C.假如T包含在S中，如此T一定是S的一个子串
D.一个字符串不能说是其自身的一个子串
五、
一、单
41.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，如此度为0的结点数为〔C〕个。
A.4B.5C.6D.7
42.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，如此叶子结点数为〔B〕个。
A.15B.16C.17D.47
43.假定一棵三叉树的结点数为50，如此它的最小高度为〔C〕。
A.3B.4C.5D.6
44.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]假如有左孩子，其左孩子的编号为结点〔B〕。
A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]
45.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为〔D〕。
A.24B.48
46.线索二叉树是一种〔C〕结构。
A.逻辑B.逻辑和存储C.物理D.线性
47.线索二叉树中，结点p没有左子树的充要条件是〔B〕。
A.p->LeftChild=NULLB.p->ltag=1
C.p->ltag=1且p->LeftChild=NULLD.以上都不对
48.如果F是由有序树T转换而来的二叉树，那么T中结点的先根遍历就是F中结点的〔B〕遍历。
A.中序B.前序C.后序D.层次序
二、多
49.如下说法正确的有：
〔ABDE〕
A.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。
B.二叉树的前序遍历中，任意结点均处在其子女结点之前。
C.线索二叉树是一种逻辑结构。
〔物理存储结构〕
D.哈夫曼树的总结点个数〔多于1时〕不能为偶数。
E.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到适宜位置为止。
50.如下说法错误的有：
〔ABDE〕并修改为正确的。
A.树的后根遍历与其对应的二叉树的后序遍历序列一样。
B.根据任意一种遍历序列即可唯一确定对应的二叉树。
C.满二叉树也是完全二叉树。
D.哈夫曼树一定是完全二叉树。
E.树的子树是无序的。
F.对于一棵具有n个结点，其高度为h的二叉树，进展任一种次序遍历的时间复杂度为O〔h〕。
六、
一、单：
51.为提高对有序链表的搜索效率，建议采用〔C〕数据结构。
A.集合B.字典C.跳表D.散列
52.假如根据关键码（23,44,36,48,52,73,64,58）建立散列表，采用h（K）=K%7计算散列地址，如此散列地址等于3的元素有（ B ）个。
A.1B.2C.3D.4
53.假如根据关键码建立长度为m的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，如此下一次的哈希地址为（ D ）。
A.dB.d+1C.（d+1）/mD.（d+1）%m
54.设散列空间为０到ｍ－１，ｋ为表项的关键码，散列函数采用除留余数法，即Hash〔k〕=k%p。
为了减少发生冲突的频率，一般取p为〔B〕。
A.mB.小于m的最大质数
C.大于m的最小质数D.小于m的最大合数
55.在闭散列表中，散列到同一个地址而引起的“堆积〞问题是由于〔C〕引起的。
A．同义词之间发生冲突。
B．非同义词之间发生冲突。
C．同义词或非同义词之间发生冲突。
D．散列表“溢出〞。
56.采用开散列法解决冲突时，每一个散列地址所的同义词表中各个表项的〔C〕一样。
A．关键码值B．元素值C．散列地址D．含义
57.解决散列法中出现的冲突问题常采用的方法是〔D〕。
A．数字分析法、除留余数法、平方取中法。
B．数字分析法、除留余数法、线性探查法。
C．数字分析法、线性探查法、双散列法。
D．线性探查法、双散列法、开散列法。
58.对包含n个元素的散列表进展搜索，搜索成功时的平均搜索长度〔C〕
A．为O〔log2n〕。
B．为O〔n〕。
C．不直接依赖于n。
D．上述三者都不是。
二、多
59.字典可以采用〔AＣ Ｄ〕组织方式。
A.线性表B.集合C.散列表D.跳表
60.如下说法正确的有：
〔AＤ〕
A.理想情况下，在散列表中搜索一个元素的时间复杂度为Ｏ〔１〕。
B.在散列法中，一个可用的散列函数必须保证绝对不产生冲突。
C.在散列法中，采取开散列法来解决冲突时，其装载因子的取值一定在〔０，１〕之间。
D.在散列法中，采取闭散列法来解决冲突时，一般不要立刻做物理删除，否如此在搜索时会发生错误。
七、
一、单：
61.对于长度为9的顺序存储的有序表，假如采用折半查找，在等概率情况下的平均查找长度为（ C ）的9分之一。
A.20B.18C.25D.22
62.对于顺序存储的有序表（5,12,20,26,37,42,46,50,64），假如采用折半查找，如此查找元素26的比拟次数为（ C ）。
A.2B.3C.4D.5
63.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（ A ）。
A.O（n）B.O
（1）C.O（log2n）D.O（n2）
64.在一棵高度平衡二叉搜索树中，每个结点的平衡因子的取值X围是（ A ）。
A.-1~1B.-2~2C.1~2D.0~1
65.对长度为n的顺序表进展查找时，假定查找第i个元素的概率为pi,查找长度〔即在查找过程中依次同有关元素比拟的总次数〕为ci，如此在查找成功情况下的平均查找长度的计算公式为〔D〕。
A.C1+C2+…+B.P1+P2+…+PnC.CiPiD.C1P1+C2P2+…+Pn
66.假定一个顺序表的长度为40，并假定查找每个元素的概率都一样，如此在查找不成功情况下的平均查找长度〔D〕。
A.39.5B.40C.40.5D.41
67.假定对长度n=50的有序表进展折半查找，如此对应的树高度为〔B〕。
A.5B.6C.7D.8
68.对一棵二叉搜索树进展〔B〕遍历时，得到的结点序列是一个有序序列。
A.前序B.中序C.后序D.层次
69.在一棵平衡二叉搜索树中，每个结点的左子树高度与右子树高度之差的绝对值不超过〔B〕。
A.0B.1C.2D.3
二、多
70.如下说法正确的有：
〔BC〕
A.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是一样的。
B.在二叉搜索树上插入新结点时，不必移动其它结点，仅需要改动某个结点的指针，使它由空变为非空即可。
C.对于两棵具有一样关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的。
D.在二叉搜索树上删除一个结点时，不必移动其它结点，只要将该结点的双亲结点的相应指针域置空即可。
八、
一、单：
71.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（B）。
A.0B.1C.nD.n+1
72.设无向图的邻接表如下列图，如此该图的边的数目是〔B〕
A.4B.5C.10D.20
73.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（A）。
A.nB.2nC.eD.2e
74.对于一个有向图，假如一个顶点的度为k1，出度为k2，如此对应逆邻接表中该顶点单链表中的边结点数为（C）。
A.k1B.k2C.k1-k2D.k1+k2
75.一个有向图的边集为{,,,,,}，如此由该图产生的一种可能的拓扑序列为（A）。
A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e
76.采用邻接表存储的图的深度优先遍历算法类似于二叉树的〔B〕。
A.中序遍历B.前序遍历C.后序遍历D.按层次遍历
77.设图中有n个顶点和e条边，采用邻接表存储，进展广度优先搜索，其时间复杂度至多为〔A〕。
A.O（n+e）B.O（n*e）C.O（n*logn/log2）D.O（e*loge/log2）
78.AOE网络如下列图，这个工程最早可能完毕的时间〔B〕。
A.35B.43C.31D.18
79.设有无向图G〔如下列图〕，用Prim算法构造的最小生成树时，顺序选出的各边为〔A〕。
A.（1,3）（2,3）（3,5）（5,6）（4,6）B.（1,3）（2,3）（2,5）（5,6）（4,6）
C.（5,6）（6,4）（4,1）（1,3）（3,2）D.（5,6）（4,6）（1,3）（1,2）（3,5）
80.
设有无向图G〔如下列图〕，用Kruskal算法构造最小生成树时，顺序选出的各边为〔D〕。
A.（1,3）（2,3）（3,5）（5,6）（4,6）
B.（1,3）（2,3）（2,5）（5,6）（4,6）
C.（5,6）（6,4）（4,1）（1,3）（3,2）
D.（5,6）（4,6）（1,3）（1,2）（3,5）
九、
一、单：
81.假定一个初始堆为（1,5,3,9,12,7,15,10），欲把这组数从大到小排序，采用最小堆，如此进展第一趟堆排序后得到的结果为〔A〕。
A.3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1
C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,1
82.假定一组记录为（46,74,53,14,26,38,86,65,27,34），对其进展希尔排序，第一趟间隔为3，得到的排序结果为〔C〕。
A.14,26,27,34,38,46,53,65,74,86B.14,26,27,38,34,46,53,65,74,86
C.14,26,27,34,65,38,46,74,53,86D.53,74,14,34,65,46,26,86,27,38
E.26,34,54,14,27,38,86,65,46,74F.14,34,46,86,26,65,74,53,38,27
83.假定一组记录为（46,74,53,14,26,38,86,65,27,34），对其进展基数排序，最低位优先，经过第一趟分配、收集后，得到的结果为〔D〕。
A.14,26,27,34,38,46,53,65,74,86B.14,26,27,38,34,46,53,65,74,86
C.14,26,27,34,65,38,46,74,53,86D.53,74,14,34,65,46,26,86,27,38
E.26,34,54,14,27,38,86,65,46,74F.14,34,46,86,26,65,74,53,38,27
84.〔D〕排序方法采用的是二分法的思想。
A.直接选择B.堆C.直接插入D.快速E.归并F.冒泡
85.〔E〕排序方法采用的是两两有序表合并的思想。
A.堆B.直接选择C.直接插入D.快速E.归并F.冒泡
86.〔F〕排序方法使排序码小的记录逐渐上浮，使排序码大的记录逐渐下沉。
A.堆B.直接选择C.直接插入D.快速E.归并F.冒泡
87.〔C〕排序方法能够每次使无序表中的第一个记录插入到有序表中。
A.堆B.直接选择C.直接插入D.快速E.归并F.冒泡
88.〔B〕排序方法能够每次从无序表中顺序查找出一个最小值。
A.堆B.直接选择C.直接插入D.快速E.归并F.冒泡
二、多
89.在所有的排序方法中，〔BCEF〕排序方法是稳定的。
A.堆B.归并C.折半插入D.快速E.直接插入F.起泡G.直接选择
90.适合元素个数n很大的排序方法是〔ABD〕。
A.堆B.归并C.折半插入D.快速E.直接插入F.起泡G.直接选择
十、
一、单：
91.在索引表中，假如一个索引项对应数据对象表中的一个表项，如此称此索引为〔D〕。
A.静态索引B.动态索引C.稀疏索引D.稠密索引
92.在索引表中，假如一个索引项对应数据对象表中的假如干表项，如此称此索引为〔C〕索引。
A.静态索引B.动态索引C.稀疏索引D.稠密索引
93.〔B〕仅是一种顺序存储设备。
A.磁盘B.磁带C.文件D.外存E.内存
94.基于磁盘进展的排序多使用〔B〕排序方法。
A.选择B.归并C.插入D.快速E.交换
95.索引非顺序文件是指〔A〕。
A.主文件中记录无序排列,索引表中索引项有序排列.
B.主文件中记录有序排列,索引表中索引项无序排列.
C.主文件中记录有序排列索引表中索引项有序排列.
D.主文件中记录无序排列,索引表中索引项无序排列.
二、多
96.索引文件由（AB）构成
A.索引表B.主文件C.关键码D.搜索表
97.磁带存储器是〔A〕设备。
A.顺序存取B.随机存取C.直接存取
98.文件采用〔ACD〕结构。
A.顺序B.链表C.索引D.直接存取
99.如下说法正确的有：
〔BC〕
A．对索引顺序文件进展搜索，可以按照给定值由索引表直接搜索要求的记录。
B．在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每个子表中的对象个数有关。
C．在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。
D．增大归并路数，可减少归并趟数，但不能减少总读写磁盘次数。
100.在索引表中，每个索引项至少含有〔AB〕域。
A．关键码
B．子表地址
C．元素值
D．索引项个数
升级会员 