《数据结构》模拟自测题2

《数据结构》模拟自测题2

一、单选题（每小题2分，共30分）

1.从逻辑上可以把数据结构分为（）两大类。

A.动态结构、静态结构B.顺序结构、链式结构

C.线性结构、非线性结构D.初等结构、构造型结构

2.在n个结点的顺序表中，算法的时间复杂度是0（1）的操作是：（）

A.访问第i个结点（IWiWn）和求第i个结点的直接前驱（2WiWn）

B.在第i个结点后插入一个新结点（lWiWn）

C.删除第i个结点（IWiWn）

D.将n个结点从小到大排序

3.链接存储的存储结构所占存储空间：（）

A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B只有一部分，存放结点值

C只有一部分，存储表示结点间关系的指针

D分两部分，一部分存放结点值，另一部分存放结点所占单元数

4.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：()。

A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;

C.p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;

5.设栈的输入序列是1,2,3,4,则()不可能是其出栈序列。

A.1,2,4,3,B.2,1,3,4,C.1,4,3,2,

D.4,3,1,2,E.3,2,1,4,

6.循环队列存储在数组中，则入队时的操作为()。

A.rear=rear+lB.rear=(rear+l)mod(m-1)

C.rear=(rear+l)modmD.rear=(rear+1)mod(m+1)

7.若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3,•••,pn,

若pl=n,则pi为()

A.iB.n=iC.n-i+1D.不确定

8.串^ababaaababaa,的next的函数值为（）。

A.B.

C.D.5

9.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A.9B.11C.15D.不确定

10.高度为k的二叉树最大的结点数为（）。

A.2kB.2k-1C.2-1D.2kl-l

11.边远山区的N个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以

归结为什么问题()

A最短路径B关键路径C拓扑排序D最小生成树

12.当一个有n个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是()。

£/![/,；]£A[Z,J]J；A[j,i]

A.i=iB.j=1C.i=iD.<=14>,

13.设广义表L=((a,b,c)),则L的长度和深度分别为()o

A.1和2B.1和3C.1和1D.2和3

14.折半查找法查找一个长为10的，排好序的线性表，当查找不成功时，最多需要比较多少

次()

A5B2C4D1

15.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法，以第一个

记录为基准得到的一次划分结果为().

A.(40,38,46,56,79,84)B.(40,38,46,79,56,84)

C.(38,40,46,56,79,84)D.(40,38,46,84,56,79)

二、填空(每空1分，共16分)

1.对于给定的n个元素,可以构造出的逻辑结构有,___,_____,_____四种。

2.顺序存储结构是通过表示元素之间的关系的;链式存储结构是通过

表示元素之间的关系的。

3.具有n个结点的二叉树，采用二叉链表存储，共有个空指针域。

4.完全二叉树中，结点个数为n,则编号最大的非终端结点的编号为,

5.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为,邻

接表的边结点个数为。

6.设一棵完全二叉树具有1000个结点，则此完全二叉树有一个叶子结点，有

一个度为2的结点，有一个结点只有非空左子树，有一个结点只有非空右子树。

7.在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记

录基本无序，则最好选用

三、判断题：对打；错打“X”，并说明理由。(每小题1分，共10分)

L顺序存储结构的主要缺点是不利于插入或删除操作。()

2.线性表的长度是线性表所占用的存储空间的大小。()

3.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

()

4.完全二叉树中，若一个结点没有左孩子，则它必是树叶。()

5.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()

6.折半查找与二叉排序树的时间性能有时不相同。()

十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。()

8.在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列，则需要

采用“大根堆”。()

9.图G的拓扑序列唯一，则其弧数必为n-1(其中n为顶点数)。()

10.散列表的装填因子a越小，发生冲突的可能性就越小。()

四、算法设计题：(共20分)

已知Q是一个非空队列，S是一个空栈。仅用如下给定的队列和栈的ADT函数和尽量少

的工作变量，使用C或C++语言编写一个算法，将队列Q中的所有元素逆置。

•栈的ADT函数有：

voidMakeEmpty(Stack&S)置空栈

boolPush(Stack&S,DataTypee)新元素e进栈，入栈成功返回TRUE,否则返回FALSE

DataTypePop(Stack&S)出栈，返回栈顶值,否则返回空值

boolisSEmpty(StackS)判栈空否，若空返回TRUE,否则返回FALSE

•队列的ADT函数有：

boolEnQueue(Queue&Q,DataTypee)元素e进队，入队成功返回TRUE,否则返回FALSE

DataTypeDeQueue(Queue&Q)出队列，若队列非空返回队头值，否则返回空值

boolisQEmpty(QueueQ).判队列空否。若空返回TRUE,否则返回

五、设散列表的长度皿=13；散列函数为II(Key)=KeyMODm,给定的关键码序列为19,

14,23,01,68,20,84,27,55,1b试画出用线性探查法(Hi=(H(Key)+di)MODm,

i=l,2,……k(k<m-l))解决冲突时所构造的散列表。并求出在等概率的情况下，这种方

法的搜索成功时的平均搜索长度。

(构造出散列表15分，求出其搜索成功时的平均搜索长度15分，共计30分)

以下是本试卷的参考答案：

一、单选题(每小题2分，共30分)

1.C2.A3.A4.B5.D6.D7.C8.D9.B10.C

11.B12.B13.A14.A15.A

二、填空题(每空1分，共16分)

1.线性结构，树型结构，图状结构，集合

2.物理位置上相邻，结点的指针

3.n+1

4.Ln/2j

5.n,2e

6.500,499,1,0

7.堆排序快速排序

三、岁断题(其题］?，共10分)

1.VI2.XI3.XI4.VI5.VI6.VI7.XI8.VI9.XI10.V

四、算法设计题：(共20分)

参考算法：voidInvert(Queue&Q)

{MakeEmpty(S);//IIwhile(!isSEmpty(S))

while(!isQEmpty(Q))II{e=Pop(S)

{e=DeQueue(Q);IIEnQueue(Q,e);

Push(S,e);II}//

}//return;

五、(构造出散列表15分，求出其搜索成功时的平均搜索长度15分，共计30分)

设散列表的长度皿=13；散列函数为H(K)=Kmodm,给定的关键码序列为19,14,

23,01,68,20,84,27,55,11,则有

11(19)=6,成功；