模拟题答案.docx
《模拟题答案.docx》由会员分享，可在线阅读，更多相关《模拟题答案.docx（21页珍藏版）》请在冰点文库上搜索。
模拟题答案
一、选择题
1.以下数据结构中哪一个是线性结构？
（B）
A.有向图 B.队列C.线索二叉树 D.B树
2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（D）语句序列。
A.p=q;p->next=q;B.p->next=q;q->next=p;
C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;
3.以下哪一个不是队列的基本运算？
（A）
A.在队列第i个元素之后插入一个元素B.从队头删除一个元素
C.判断一个队列是否为空D.读取队头元素的值
4.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（B）。
A．11B.35C.19D.53
5.该二叉树结点的前序遍历的序列为（C）。
A.E、G、F、A、C、D、BB.E、A、G、C、F、B、D
C.E、A、C、B、D、G、FD.E、G、A、C、D、F、B
6.下面关于图的存储的叙述中正确的是（B）。
A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
7.设有关键码序列（q，g，m，z，a，n，p，x，h），下面哪一个序列是从上述序列出发建堆的结果?
（B）
A.a，g，h，m，n，p，q，x，z B.a，g，m，h，q，n，p，x，z
C.g，m，q，a，n，p，x，h，zD.h，g，m，p，a，n，q，x，z
8.一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（B）。
A.HL=p;p->next=HL;B.p->next=HL->next;HL->next=p;
C.p->next=HL;p=HL;D.p->next=HL;HL=p;
9.顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素.
A.n B.n-1
C.n+1D.不确定
10.下述哪一条是顺序存储方式的优点？
（A）
A．存储密度大B.插入和删除运算方便
C.获取符合某种条件的元素方便D.查找运算速度快
11.下列关于二叉树遍历的叙述中，正确的是（A）。
A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
12.k层二叉树（K>=1）的结点总数最多为（A）.
A．2k-1B.2K+1C.2K-1 D.2k-1
13.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个。
A．1B．2C．3D．4
14.对一个算法的评价，不包括如下（B）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度
15.对线性表，在下列哪种情况下应当采用链表表示？
（B）
A.经常需要随机地存取元素B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变
16.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（C）
A.231B.321
C.312D.123
17.快速排序在最坏情况下的时间复杂度为（D）。
A．O（log2n）B．O（nlog2n）C．0（n）D．0（n2）
18.从二叉排序树中查找一个元素时，其时间复杂度大致为（C）。
A.O（n）B.O
（1）C.O（log2n）D.O（n2）
19.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采
用（C）存储方式最节省时间。
A.单链表B.双链表
C.带头结点的双循环链表D.单循环链表
20.
下面的二叉树中，（C）不是完全二叉树。
21.栈和队列的共同特点是（A）。
A.只允许在端点处插入和删除元素B.都是先进后出
C.都是先进先出D.没有共同点
22.用链接方式存储的队列，在进行插入运算时（D）。
A.仅修改头指针 B.头、尾指针都要修改
C.仅修改尾指针D.头、尾指针可能都要修改
23.树最适合用来表示（C）。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
24.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（D）。
A.1，2，3B.9，5，2，3
C.9，5，3D.9，4，2，3
25.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9
作为散列函数，则散列地址为1的元素有（D）个，
A．1B．2C．3D．4
26.设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图。
A.5B.6C.7D.8
27.某算法的时间代价为T（n）=100n+10nlog2n+n2+10，其时间复杂度为（ C）。
A:
O（n） B:
O（nlog2n）
C:
O（n2） D:
O
（1）
28.从一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的平均比较次数为（C）。
A:
n B:
n/2
C:
（n+1）/2 D:
（n-1）/2
29.在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ C）个元素。
A:
n-i B:
n-i+1
C:
n-i-1 D:
I
30.树中所有结点的度之和等于所有结点数加（ C ）。
A:
0 B:
1
C:
－1 D:
2
31.一棵具有35个结点的完全二叉树的高度为（A）,假定空树的高度为 -1。
A:
5 B:
6
C:
7 D:
8
32.对于具有e条边的无向图，它的邻接表中有 （ D） 个边结点。
A:
e-1 B:
e
C:
2（e-1） D:
2e
33.图的深度优先搜索类似于树的（ A ）次序遍历。
A:
先序 B:
中序
C:
后序 D:
层次
34.设单链表中结点的结构为（data,next）。
已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（B）。
A:
s->next=p->next;p->next=s;B:
q->next=s;s->next=p;
C:
p->next=s->next;s->next=p;D:
p->next=s;s->next=q;
35.递归调用时系统需要利用一个（D）来实现数据的传递和控制的转移。
A:
队列B:
优先级队列
C:
双端队列D:
栈
36.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。
这样的排序方法是（C）。
A:
直接选择排序B:
直接插入排序
C:
快速排序D:
起泡排序
37.设无向图的顶点个数为n，则该图最多有（B）条边。
A:
n-1B:
n（n-1）/2
C:
n（n+1）/2D:
n（n-1）
38.设循环队列的结构是
constintMaxSize=100;
typedefintDataType;
structQueue{
DataTypedata[MaxSize];
intfront,rear;
};
若有一个Queue类型的队列Q，试问判断队列满的条件应为（D）。
A:
Q.front==Q.rear;B:
Q.front-Q.rear==MaxSize;
C:
Q.front+Q.rear==MaxSize;D:
Q.front==（Q.rear+1）%MaxSize;
39.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（D）。
A:
front==rearB:
front!
=NULL
C:
rear!
=NULLD:
front==NULL
40.对于有向图，其邻接矩阵表示比邻接表表示更易于（A）。
A:
求一个顶点的度B:
求一个顶点的邻接点
C:
进行图的深度优先遍历D:
进行图的广度优先遍历
41.与邻接矩阵相比，邻接表更适合于存储（C）。
A无向图B连通图
C稀疏图D稠密图
42.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）
A．3，2，6，1，4，5B．3，4，2，1，6，5
C．1，2，5，3，4，6D．5，6，4，2，3，1
43.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ）
A．队列B．栈
C．线性表D．有序表
44.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（A）
A．图中每个顶点的入度B．图中每个顶点的出度
C．图中弧的条数D．图中连通分量的数目
45.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i（i>=1）趟排序之前，无序区中关键字元素的个数为（ D）
A．iB．i+1
C．n-iD．n-i+1
46.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ A ）
A．f,c,bB．f,d,b
C．g,c,bD．g,d,b
47.在下面的程序段中，对x的赋值语句的频度为（C）
For（i=1;i<=n;i++）
For（j=1;j<=n;j++）
x=x+1;
A．O（2n）B．O（n）C．O（n2）D．O（log2n）
48.下面关于线性表的叙述中，错误的是哪一个？
（B）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
49.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
50.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双链表D．仅有尾指针的单循环链表
51.链表不具有的特点是（B）
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
52.下面的叙述不正确的是（B,C）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
53.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。
A．O（n）O（n）B.O（n）O
（1）C.O
（1）O（n）D.O
（1）O
（1）
54.在一个以h为头的单循环链中，p指针指向链尾的条件是（A）。
A.p->next=hB.p->next=NULLC.p->next->next=hD.p->data=-1
55.完成在双循环链表结点p之后插入s的操作是（D）；
A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
B．p->next->prior:
=s;p->next=s;s->prior=p;s->next:
=p->next;
C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
56.双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D）
A.p->llink=q;q->rlink:
=p;p->llink->rlink:
=q;q->llink:
=p->llink;
B.q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink:
=q->rlink;
C.q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;
D.p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;
57.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）
A．head==NULLB．head→next==NULLC．head→next==headD．head!
=NULL
58.在双向链表存储结构中，删除p所指的结点时须修改指针（A）。
A．（p->prior）->next=p->next（p->next）->prior=p->prior;
B．p->prior=（p->prior）->prior（p->prior）->next=p;
C．（p->next）->prior=pp->next=（p->next）->next
D．p->next=（p->prior）->priorp->prior=（p->next）->next;
59.输入序列为ABC，可以变为CBA时，经过的栈操作为（B）
A.push,pop,push,pop,push,popB.push,push,push,pop,pop,pop
C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop
60.设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。
A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈
61.用链接方式存储的队列，在进行删除运算时（D）。
A.仅修改头指针B.仅修改尾指针
C.头、尾指针都要修改D.头、尾指针可能都要修改
62.假设以数组A[0..m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。
A．（rear-front+m）%mB．rear-front+1
C．（front-rear+m）%mD．（rear-front）%m
63.循环队列存储在数组A[0..m]中，则入队时的操作为（D）。
A.rear=rear+1B.rear=（rear+1）mod（m-1）
C.rear=（rear+1）modmD.rear=（rear+1）mod（m+1）
64.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（B）
A.1和5B.2和4C.4和2D.5和1
65.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（B）。
A.（rear+1）%n==frontB.rear==front
C．rear+1==frontD.（rear-l）%n==front
66.栈和队列都是（C）
A．顺序存储的线性结构B.链式存储的非线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
67.用单链表表示的链式队列的队头在链表的（A）位置。
A．链头B．链尾C．链中
68.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）
A．9B．11C．15D．不确定
69.具有10个叶结点的二叉树中有（B）个度为2的结点
A．8B．9C．10D．ll
70.设给定权值总数有n个，其哈夫曼树的结点总数为（D）
A．不确定B．2nC．2n+1D．2n-1
71.对于有n个结点的二叉树,其高度为（D）
A．nlog2nB．log2nC．log2n|+1D．不确定
72.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（D）次序的遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
73.二叉树的先序遍历和中序遍历如下：
先序遍历：
EFHIGJK；中序遍历:
HFIEJKG。
该二叉树根的右子树的根是（G）
A、EB、F C、G D、H
74.在完全二叉树中，若一个结点是叶结点，则它没（C）。
A．左子结点B．右子结点
C．左子结点和右子结点D．左子结点，右子结点和兄弟结点
75.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（C）
A.X的双亲B.X的右子树中最左的结点
C.X的左子树中最右结点D.X的左子树中最右叶结点
76.引入二叉线索树的目的是（A）
A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲D．使二叉树的遍历结果唯一
77.n个结点的线索二叉树上含有的线索数为（C）
A．2nB．n－lC．n＋lD．n
78.由3个结点可以构造出多少种不同的二叉树？
（D）
A．2B．3C．4D．5
79.设无向图的顶点个数为n，则该图最多有（B）条边。
A．n-1B．n（n-1）/2C．n（n+1）/2D．0E．n2
80.一个n个顶点的连通无向图，其边的个数至少为（A）。
A．n-1B．nC．n+1D．nlogn；
81.n个结点的完全有向图含有边的数目（ A ）。
A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）
82.在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。
A．1/2B．2C．1D．4
83.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（B）。
A.O（n）B.O（n+e）C.O（n2）D.O（n3）
84.下面关于二分查找的叙述正确的是（D）
A.表必须有序，表可以顺序方式存储，也可以链表方式存储
B.表必须有序，而且只能从小到大排列
C.表必须有序且表中数据必须是整型，实型或字符型
D.表必须有序，且表只能以顺序方式存储
85.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（C）
A．（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，120，110，130）
D.（100，80，60，90，120，130，110）
86.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用开散列表构造散列表，散列函数为H（key）=key%13,散列地址为1的链中有（D）个记录。
A．1B.2C.3D.4
87.闭散列表的地址区间为0-17,散列函数为H（K）=K%17。
采用线性重散列技术处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中,元素59存放在散列表中的地址是（D）。
A．8B.9C.10D.11
88.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D）。
A．直接插入排序B.气泡排序C.快速排序D.直接选择排序
89.119．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1）8447251521
（2）1547258421（3）1521258447（4）1521254784,则采用的排序是（A）。
A.选择B.冒泡C.快速D.插入
90.对序列{15，9，7，8，20，-1，4}进行排序，经一趟排序后的排列为{9，15，7，8，
20，-1，4}，则采用的是（C）排序。
A．选择B.堆C.直接插入D.冒泡
91.下列排序算法中（C）排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择B.冒泡C.合并D.堆
92.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。
A．（38,40,46,56,79,84）B.（40,38,46,79,56,84）
C．（40,38,46,56,79,84）D.（40,
升级会员 