数据结构导论真题分类整理详细

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。 1.从逻辑上可以把数据结构分为（ ）

A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确的是（ ） A.算法最终必须由计算机程序实现

B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为_____。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、_____和散列存储方式。 1.在数据结构中，数据的基本单位是( ) A.数据项 B.数据元素 C.数据对象 D.数据文件

1

2. k=1;

for（i=0；i

for（j=0；j

A［i］［j］=k++；

上述程序段的时间复杂度为( ) A.O（n2） B.O（n） C.O（2n） D.O（1） 16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。 1.在数据结构中，从逻辑上可以把数据结构分成( )

A.线性结构和非线性结构 B.紧凑结构和非紧凑结构C.动态结构和静态结构 D.内部结构和外部结构 2.for（i=0；i

for（j=0；j

A［i］［j］=i*j；

上面算法的时间复杂度为( ) A.O(m2) B.O(n2) C.O(m×n) D.O(m+n）

16.如果操作不改变原逻辑结构的―值‖，而只是从中提取某些信息作为运算结果，则称该类运算为_ _型运算。

3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构

16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_______。 17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。 1.数据的基本单位是（ ）A.数据项 B.数据类型 C.数据元素 D.数据变量 2.下列程序的时间复杂度为（ ） i=0；s=0；

while（s

A.O（n） B.O（2n） C.O（n） D.O（n2）

16.在数据结构中，数据的逻辑结构分为集合、_____、树形结构和图状结构等四类。 17.通常从正确性、易读性、_____和高效率等4个方面评价算法（包括程序）的质量。 1.数据结构中所定义的数据元素，是用于表示数据的（ ） A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2.数据的四种基本存储结构是指（ ）

A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构 C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构

16.数据表示和________________是程序设计者所要考虑的两项基本任务。

17.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。 1.若要描述数据处理的变化过程，其正确的次序应为( )

A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算

2

2.从运算类型角度考虑，属于引用型的运算是( )

A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 16.算法通常可分为程序、伪语言算法和__________三种类型。

17.时间复杂性描述量级中，若某算法达到__________量级，则该算法通常是不可计算的。 1.数据的四种基本逻辑结构是指( )

A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性 C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性

16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和_______两种基本 类型。 17.数据结构中的算法，通常采用最坏时间复杂度和______两种方法衡量其效率。

1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（ ） A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构

2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（ ） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较

16.从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和___________。

17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为___________算法。 1．下列数据组织形式中，（ ）的各个结点可以任意邻接。 A．集合 B．树形结构 C．线性结构 D．图状结构 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 16．下列程序段的时间复杂性量级是_____________。 for (i=1;i

3

第二章 线性表 第三章 栈、队列、数组 真题

5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( )

A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确的是( )

A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储

15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+I C.i(j-i)／2+1 D.j(i-1)／2+l

18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点___的。 19.在栈结构中，允许插入的一端称为____________。

20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动____________个元素。 21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为____________。 22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是____________。

29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈)

1.在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ） A.n/4 B.n/3 C.n/2 D.n

2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ ）

A.212 B.213 C.214 D.215

4.元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（ ） ．．．

A.A，B，C，D，E B.B，C，D，E，A C.E，A，B，C，D D.E，D，C，B，A

6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为( )

2

A.O（1） B.O（log2n） C.O（n） D.O(n)

10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ ） A.单链表 B.双链表 C.顺序表 D.单循环链表 11.在栈中进行插入和删除操作的一端称为（ ）

A.栈顶 B.栈底 C.任意位置 D.指定位置

15.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ） A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL

4

18.线性表中所含结点的个数称为______。

19.向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行______和top=p操作。

20.设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为______。 35.设顺序表va中的数据元素递增有序。试编写算法实现将x插入到顺序表的适当位置上，以保持该

表的有序性。 3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（ ） A.单链表 B.双链表 C.单循环链表 D.顺序表

4.设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为（ ） A.p—>next=p—>next—>next B.p=p—>next C.p=p—>next—>next D.p—>next=p 5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ ） A.hs—>next=s; B.s—>next=hs;hs=s;

C.s—>next=hs—>next;hs—>next=s; D.s—>next=hs;hs=hs—>next;

6.设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ ） A.Q[4] B.Q[5] C.Q[14] D.Q[15]

7.定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ ）

A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L

18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向____和_____。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为______和______。 20.在栈结构中，允许插入的一端称为______;在队列结构中，允许插入的一端称为______。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为______。

3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（） A.直接前趋 B.直接后继 C.开始结点 D.终端结点

4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（） A.n B.2n-1 C.2n D.n2 5.栈和队列共同具有的特点是（ ）

A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（） A.1和5 B.2和4 C.4和2 D.5和1 7.数组A[0..5][0..5]的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（ ） A.1175 B.1180 C.1205 D.1210

18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动______个元素。 24.两个串是相等的，当且仅当两个串的长度相等且________的字符都相同。

34.设两个数据元素均为整型数据的线性表A=(a1，a2，…，an)和B=(b1，b2，…，bm)。若n=m且ai=bi（i=1，2,…，n）则认为A=B；若ai=bi（i=1，2,…，j）且aj+1

5

3.线性表采用链式存储结构时，要求内存中可用存储单元的地址( )

A.必须是连续的 B.必须是部分连续的 C.一定是不连续的 D.连续和不连续都可以 4.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段 p=h;

while (p->next->next!=h) p=p->next; p->next=h;

后（其中，p->next为p指向结点的指针域），则( )

A.p->next指针指向链尾结点 B.h指向链尾结点 C.删除链尾前面的结点 D.删除链尾结点

5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245

6.一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是( )A.dceab B.decba C.edcba D.abcde 7.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为―s->tl->r1=s->r1；‖和―_______‖。 32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。

35.某带头结点的单链表的结点结构说明如下： typedef struct node1 { int data;

struct node1 *next }node；

试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。

3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9

4.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( )

A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink

5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( ) A. 110 B. 108 C. 100 D. 120

6.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB

6

7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )

A.top++ B.top-- C.top不变 D.top=0

17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为―p→next=head；‖和―________‖。

18.单链表中逻辑上相邻的两个元素在物理位置上______相邻。

19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是________。 31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。

34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示：

struct node{ int info; struct node *link; }

int Delete (struct node *head, int x)

{ struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/

if (! head ) return (0); if (head→link ==head) { if (head→info==x)

{ free (head); head=NULL； return (x) } return (0); }

p=head; q=head;

while (q→link!=head) q=(1) ; while (p→link!=head)

7

{ if (p→info==x)

{ (2) ;

if (p==head) head=(3) ; free (p);return (x); }

else { q=p ;（4） ;} } return (0);

}

1．关于栈和队列的说法中正确的是（ ）

A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 2．关于存储相同数据元素的说法中正确的是（ ）

A顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构

4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ） A．q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ） A．O(n) B.O(1) C.O(log2n) D.O(n2) 6．设一个栈的输入序列是a,b,c,d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ） A．a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 7．关于串的叙述中，正确的是（ ）

A．空串是只含有零个字符的串 B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列

8．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front

9．设有二维数组A［n］［n］表示如下： ， 则A［i］［i］（0≤i≤n-1）的值为（ ）

A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 18．在顺序表上读表元算法的时间复杂度为_______。

19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;_______; 20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］的存储位置为_______。

29．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入

8

栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。 34．设单链表的结点结构如下： struct node{datatype data; struct node*next; }

试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。

3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）

A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（ ） A.n-i B.n-i+1 C.n-i-1 D.i

5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ ）

A.s.elem［top］=e；s.top=s.top+1；

B.s.elem［top+1］=e；s.top=s.top+1；

C.s.top=s.top+1；s.elem［top+1］=e； D.s.top=s.top+1； s.elem［top］=e； 6.循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ） A.8 B.16 C.17 D.18

7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ ） A.13 B.35 C.17 D.36

18.顺序表的存储密度为________，而链表的存储密度为______。 19.对于栈只能在________插入和删除元素。

20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。 3.对于长度为n的顺序表执行删除操作，则其结点的移动次数（ ）

A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是 （ A. p->next=q B. p->next=q->next C. p=q->next D. p->next=q->next->next 5.有关栈的描述，正确的是（ ） A.栈是一种先进先出的特殊的线性表 B.只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作 6.二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ） A.700 B.1120 C.1180 D.1140

18.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为________________。 19.串是一种特殊的线性表，串常见的存储结构有顺序存储和________________两种方式。

9

20.我们通常把队列中允许插入的一端称为________________。

21.二维数组在机器级的具体实现，通常均采用________________存储结构。 34.试编写一个函数，以读取单链表的第i个元素。

3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( )

A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( )

A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构

18.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。

19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为_____。 20.我们通常把队列中允许删除的一端称为_______。

21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是__________。

34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。 3.下列关于线性表的叙述中，不正确的是( )

A.线性表是n个结点的有穷序列 B.线性表可以为空表

C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系 4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( ) A.p=p->next B.p->next=p->next C.p->next=p->next->next D.p->next=p 5.栈和队列( )

A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表

C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处

6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )A.127 B.142 C.150 D.157 18.判断带头结点head的单链表为空的条件是___________。

19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为____。 20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是_______。

21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。 34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。 3.下列关于线性表的基本操作中，属于加工型的操作是（ ）

10

A.初始化、求表长度、插入操作 B.初始化、插入、删除操作 C.求表长度、读元素、定位操作 D.定位、插入、删除操作

4.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（ ）

A.s–>next=p–>next; p–>next=s; B.p–>next=s–>next; s–>next=p; C.s–>next=p; p–>next=s; D.s–>next=p–>next; p=s;

5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（ ） A.3种 B.4种 C.5种 D.6种

6.C语言对数组元素的存放方式通常采用（ ） A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.具体存储结构无法确定

18.对顺序表执行插入操作，其插入算法的平均时间复杂性为___________。

19.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。

20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是___________。

21.二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则[A][10][10]的地址为___________。

34.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2)

3．在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A．单链表 B．双链表 C．循环链表 D．顺序表

4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为（） q=NULL;

while (p!=NULL) { （ ） } p=q;

A．r=q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r; D．q=p; p=p -> next; r=q; q -> next=r; 5．数组通常具有两种基本运算，即（ ）

A．创建和删除 B．索引和修改 C．读和写 D．排序和查找

17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动___个元素。

18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： ______； sq -> data[sq -> top]=x；

19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的______。

11

29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）

34．设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 { int data;

struct node1*next }node;

试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。

35．编写一个算法 void DisplayQueue ()，产生50个300～600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分） （1）队列用链表实现；

（2）每产生一个数显示一次相应操作后的队列当前状态； （3）无需定义函数int MyRand()；

（4）显示队列可调用函数 void DisOne (QueptrTp lq)，也无需定义； （5）设链队列定义为： typedef struct linked_queue { int data;

struct linked_queue*next; }LqueueTp;

typedef struct queueptr { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq;

12

第四章 树 真题

2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ ） A.acbed B.becab C.deabc D.cedba

3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 12.有关树的叙述正确的是( )

A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点

C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____________。

30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。 34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ） A.23 B.37 C.44 D.46 12.用n个值构造一棵二叉排序树，它的最大高度为（ ） A.n/2 B. n C. n+1 D.log2n 21.若满二叉树的结点数为n，则其高度为________。

22.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点，那么其父结点的编号为_____。 23.深度为k的二叉树，结点数最多有________个。

24.某二叉树的后根遍历为ABKCBPM，则该二叉树的根为______。

29.某通讯电文由A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是6，

5，9，10，20，1，试画出这六个字符编码所用的哈夫曼树。

30.已知一棵二叉树的顺序存储结构如题30图所示，其中∧表示虚结点，试构造该二叉树。

A B G C D ∧ H ∧ ∧ E F 题30图

34.若两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。

8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ ） A.n-1 B.n C.n+1 D.2n

9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ） A.99 B.98 C.97 D.50 10.有m个叶子结点的哈夫曼树，其结点总数是（ ）

A.2m-1 B.2m C.2m+1 D.2(m+1) 22.深度为k的二叉树至多有______个结点，最少有______个结点。

29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。

30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。

13

8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（ ） A.n-1 B.n C.n+1 D.n+2

9.在一棵深度为H的完全二叉树中，所含结点的个数不少于（ ） A.2H-1-1 B.2H-1 C.2H-1 D.2H

19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为_______。 21.具有n个叶子结点的哈夫曼树，其结点总数为________。

22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。 30.画出题30图所示的二叉树的二叉链表存储结构。

35.设二叉树的结点类型定义如下： typedef struct node{ datatype data;

struct node*lchild,*rchild; }Bitree; Bitree*t;

试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t))。

8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )

A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点 9.在完全二叉树中，若一个结点是叶结点，则它没有( )

A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点 12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____。 20.深度为15的满二叉树上，第11层有_______个结点。

21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为________。 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。

8.除根结点外，树上每个结点( )

A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( )

14

A.2 B.3 C.5 D.8

20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。

21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。

29.分别写出题29图中二叉树的先根、中根、后根遍历序列。

10．高度为h的完全二叉树中，结点数最多为（ ）A．2h-1 B.2h+1 C.2h-1 D.2h 11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（ ）A．mn B.mn-1 C.n(m-1) D.m(n-1) 21．有4个结点且深度为4的二叉树的形态共有_______种。

22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。

30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。

8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ） A.3 B.4 C.5 D.6

9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ） A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。

22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。

29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。 7.关于二叉树性质的描述，正确的是（ ）

A.二叉树结点的个数可以为0 B.二叉树至少含有一个根结点 C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子

15

D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 8.具有4个结点的二叉树可有（ ）

A.4种形态 B.7种形态 C.10种形态 D.11种形态 22.深度为k的满二叉树其叶子结点个数共有________________个。 23.二叉树通常采用________________两种存储结构表示。 29.试采用类C语言，给出二叉树的二叉链表结构描述。

35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述 7.树是n个结点的有穷集合，( )

A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子C.2k-1个叶子 D.2k-1-1个叶子 22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。

23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。 29．对于如题29图所示二叉树，分别写出其先根遍历，中根遍历，后根遍历的结点访问序列。

35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。 7．深度为k的二叉树最多有（）个结点

22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为______。 23.具有n个结点的完全二叉树，其深度为___________。 29．已知某二叉树的顺序存储结构如图所示，试画出该二叉树。

35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左 右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。 7.根据定义，树的叶子结点其度数（ ）

A.必大于 0 B.必等于0 C.必等于1 D.必等于2

8.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（ ） A.2n个指针域其中n个指针为NULL B.2n个指针域其中n+1个指针为NULL C.2n-1个指针域其中n个指针为NULL D.2n-1个指针域其中n+1个指针为NULL 22.树的遍历主要有先根遍历、后根遍历和___________三种。 23.深度为k的完全二叉树至少有___________个结点。

29.已知某二叉树如下图所示，试给出其二叉链表及顺序存储结构表示。

16

35.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数 6．除根结点外，树上每个结点（ ）

A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲

7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。

A．50 B．99 C．100 D．101

20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为__________。 21．在下列树中，结点H的祖先为__________。

30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）

17

第五章 图 真题

4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1

25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。 32.下述题32图矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。

3.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为（ ）

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

14.设无向图的邻接表如题14图所示，则该图的边数为（ ）

题14图

A.4 B.5 C.10 D.20

25.在一个具有n个顶点的无向图中，顶点的度最大可达_____。

26.有向图G的邻接矩阵为A，如果图中存在弧，则A［i］［j］的值为____。

题32图

32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。

11.有n个结点的无向图的边数最多为（ ）

A.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1)

12.设图的邻接矩阵为，则该图为（ ）

A.有向图 B.无向图 C.强连通图 D.完全图

18

23.设有一稠密图G，则G采用__存储结构较省空间。设有一稀疏图G，则G采用__存储结构较省空间。

31.已知某图的邻接表存储结构如题31图所示： (1)画出该图。

(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（ ） A.0 B.1 C.n D.不确定 11.下列说法中不正确的是（ ）

A.无向图的极大连通子图称为连通分量

B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法

23.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于________。

27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。 31.对于题31图，试给出： 1）邻接矩阵； 2）邻接表。

10.邻接矩阵为对称矩阵的图是( ) A.有向图 B.带权有向图 C.有向图或无向图 D.无向图 11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D.n/2 22.一个具有4个顶点的无向完全图有_________条边。

23.一个有向图G中若有孤、和，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为_________。

33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。

19

10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20

11.设图的邻接矩阵为，则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图

22.具有n个顶点的连通图至少需有__________条边。

23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。

32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。

12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ ）A．n B.n-1 C.n+1 D.2(n-1) 13．关于无向图的邻接矩阵的说法中正确的是（ ） A．矩阵中非全零元素的行数等于图中的顶点数

B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等

23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。

24．一个具有10个顶点的完全无向图中有_______条边。 33．已知连通网的邻接矩阵A如33题图 ， 试画出它所表示的连通网并画出该连通网的最小生成树。

11.有n个结点的有向完全图的弧数是（ ） A.n2 B.2n C.n(n-1) D.2n(n+1)

20

12.设图的邻接链表如题12图所示，则该图的边的数目是（ ）

题12图

A.4 B.5 C.10 D.20 23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的______。 30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。

35.下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。 Void deledge（ALGraph *G，int i，int j） { EdgeNode *p，*q；

p=G→adjlist［i］.firstedge；

if（p→adjvex==j）{ G→adjlist［i］.firstedge=p→next；free（p）；} else

{ while（p→next→adjvex != j && p→next）

（1）________；

if（p→next!=NULL）{q=p→next；（2）________；free（q）；} }

p=G→adjlist［j］.firstedge；

if（p→adjvex==i）{ G→adlist［j］.firstedge=p→next；free（q）；} else

{ while（p→next→adjvex!=i&&p→next）

（3）________；

if（p→next!=NULL）{q=p→next；（4）________；free（q）；} } }

9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历

10.具有n个顶点的无向图，若要连通全部顶点，至少需要（ ）

21

A.（n-1）条边 B. n条边 C. n(n-1)条边 D. n(n-1)/2条边 24.若一个完全无向图具有n条边，则该图的顶点个数为________________。 30.试用Prim算法构造题30图的最小生成树，要求分步给出构造过程。

9.具有10个顶点的有向完全图应具有( ) A.20条弧 B.50条弧C.90条弧 D.100条弧 10.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为( ) A.V1V2V3V5V4V6 B.V1V2V3V5V6V4 C.V1V5V2V3V6V4 D.V1V3V6V4V5V2 24.对于n个顶点的生成树，其边的个数为__________ 。 31．试给出题31图的邻接矩阵和邻接表表示。

8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )

题8图 题10图 9.下面关于生成树的描述中，不正确的是( )

A.生成树是树的一种表现形式 B.生成树一定是连通的 C.生成树一定不含有环 D.若生成树顶点个数为n，则其边数一定为n-1

10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是( A v1v2v3v4v5 B v1v2v3v5v4 C v1v4v3v5v2 D v1v3v4v5v2 24.图主要采用___________两种存储结构存放。

30．试用prim算法构造下图的最小生成树，要求分步给出构造过程。

) 22

题31图

9.在一个无向图中，所有顶点的度数之和等于边数的（ ） A.1倍 B.2倍 C.3倍 D.4倍

10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历

24.若图的邻接矩阵是一个对称矩阵，则该图一定是一个___________。

30．若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按广度优先搜索所产生的一棵生成树。

8．邻接表是图的一种（ ）

A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ） A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 B．n C．(n+1)/2 D．n+1

22．顶点数为n、边数为n(n-1)/2的无向图称为__________。

31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）

23

第六章 查找 真题

8.对线性表进行二分查找时，要求线性表必须( )

A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列

27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为____________。

7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ ）A.1 B.2 C.3 D.4 12.用n个值构造一棵二叉排序树，它的最大高度为（ ） A.n/2 B. n C. n+1 D.log2n 27.顺序查找算法的平均查找长度为______。

31.题31图中二叉排序树的各结点的值为1～9，标出各结点的值。

13.二分查找算法的时间复杂度是（ ）A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n) 14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） A.4 B.5 C.6 D.7

25.假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。 12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ） A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列

13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（ ）A.1 B.2 C.4 D.8

32.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 13.闭散列表中由于散列到同一个地址而引起的―堆积‖现象，是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表―溢出‖引起的 24.在一棵二叉排序树上按_________遍历得到的结点序列是一个有序序列。

25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。 31.设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。

24

12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表

13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( ) A.线性探测法 B.除留余数法 C.平方取中法 D.折叠法 24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。

25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。

33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。

14．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（ ）A．1 B.2 Ｃ．3 D.4 25．一棵平衡二叉树中任一结点的平衡因子只可能是_______。 26．二分查找的时间复杂度为_______。

32．题32图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。

13.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（ ） A.1 B.2 C.3 D.4

24.对二叉排序树进行________遍历，可得到排好序的递增结点序列。 25.采用折半查找方法进行查找的数据序列应为________且________。

31.设散列函数H（key）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。

32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。

12.闭散列表中由于散列到同一个地址而引起的―堆积‖现象，是由（ ） A.同义词之间发生冲突引起的 B.非同义词之间发生冲突引起的 C.同义词与非同义词之间发生冲突引起的 D.散列地址―溢出‖引起的 25.查找表的逻辑组织结构实际上是________________结构。

26.对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为________________。 31.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。 11.适用于静态的查找方法为( )

A.二分查找、二叉排序树查找 B.二分查找、索引顺序表查找 C.二叉排序树查找、索引顺序表查找 D.二叉排序树查找、散列法查找

25

12.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )

A.从MID/2位置开始 B.从MID位置开始 C.从MID-1位置开始 D.从MID+1位置开始 25.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为__________。 26.解决散列所引起冲突的方案中，__________法是介于开散列表与闭散列表之间的一种方法。 30．设散列函数H(key)=key，散列表长度为11（散列地址空间为0…10），在给定表（SUN， MON，TUE，WED，THU，FRI，SAT）中，取单词的第一个字母在英语字母表中的序号为键值K，构造一散列表，并利用线性探测法解决有关的地址冲突。 11.下列查找方法中，不属于动态的查找方法是( )

A.二叉排序树法 B.平衡树法 C.散列法 D.斐波那契查找法 12.要解决散列引起的冲突问题，常采用的方法有( ) A.数字分析法、平方取中法 B.数字分析法、线性探测法 C.二次探测法、平方取中法 D.二次探测法、链地址法

25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用______法在块中找到具体的元素值。

26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用______法遍历。

31.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：

(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2)若要用该散列表查找元素68，给出所需的比较次数。

11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为（ ） A.从第0个元素开始往后查找该数据元素 B.从第1个元素开始往后查找该数据元素 C.从第n个元素开始往前查找该数据元素 D.从第n+1个元素开始往前查找该数据元素 12.下列查找中，效率最高的查找方法是（ ）

A.顺序查找 B.折半查找 C.索引顺序查找 D.分块查找

25.对于具有n个元素的数据序列，采用二叉排序树查找，其平均查找长度为___________。 26.要完全避免散列所产生的―堆积‖现象，通常采用___________法。

31．已知某二叉排序树10个结点值依次为1~10，其结构如图所示，试标出该二叉树各结点所对应得具体值。

10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 B．n C．(n+1)/2 D．n+1

11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次

26

的查找区间为从原开始位置至（ ）

A．该中间位置 B．该中间位置－1 C．该中间位置＋1 D．该中间位置／2 12．散列文件不能（ ）

A．随机存取 B．索引存取 C．按关键字存取 D．直接存取

24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。

25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。

32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分） （1）构造散列表； （2）求查找数34需要的比较次数。

27

第七章 文件 真题

1.下述文件中适合于磁带存储的是（ ）

A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件

26.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中_________特别适应磁带存储器，也适应磁盘存储器。

15.关于VSAM文件存取操作的说法，正确的是（ ）

A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取 C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取 26.文件的检索有三种方式，它们是顺序存取、直接存取和____________存取。

26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是__________存取、直接存取和按关键字存取。

28．文件的基本存取单位是_______。

26.索引文件只能是________，因为索引文件的组织方式是为随机存取而设计的。 13.ISAM文件组织方式是一种（ ）

A.专门适用于磁带的存取方法 B.专门适用于磁盘的存取方法

C.专门适用于光盘的存取方法 D.可适用于磁带、磁盘、光盘等多用途的存取方法 27.若构成索引文件的索引表有序而主文件无序，则该索引文件称为________________文件。 13.磁盘是一种广泛使用的外部存储设备，对磁盘的存取操作( ) A.只能用顺序方式 B.只能用随机方式

C.既能用顺序方式也能用随机方式 D.方式取决于具体的机器

27.多关键字文件是指同时对__________两部分都建立索引的文件组织形式。 13.用于外存储器的数据组织结构散列文件，主要适用于( )

A.顺序存取 B.随机存取 C.索引存取 D.以上三种都可以 27.文件常见的存储结构有顺序文件、链接文件、 索引文件和____四种。 13.索引文件通常由索引表和主文件两部分构成，其中（ ）

A.索引表和主文件均必须是有序文件 B.索引表和主文件均可以是无序文件 C.索引表必须是有序文件 D.主文件必须是有序文件

27.ISAM其中文含义为___________方法。 12．散列文件不能（ ）

A．随机存取 B．索引存取 C．按关键字存取 D．直接存取

13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（

A．n/2 B．n C．n/4 D．log n

26．文件的基本运算包括______________和修改两类。

28

第八章 排序 真题

6.下述几种排序方法中，要求内存量最大的是( )

A.插入排序 B.快速排序 C.归并排序 D.选择排序

7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 28.堆排序需____________个记录大小的辅助存储空间。

33.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。 35.试写出直接插入排序算法。

9.下列各项键值序列中不是堆的为（ ）

A.{5，23，16，68，94，72，71，73} B.{5，16，23，68，94，72，71，73} C.{5，23，16，73，94，72，71，68} D.{5，23，16，68，73，71，72，94} 10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ ） A.单链表 B.双链表 C.顺序表 D.单循环链表

28.二路归并排序的平均时间复杂度为_____。

33.写出键值（83，40，63，13，84，35，96，57，39，79，61，15）应用二路归并排序算法从小到

大排序后各趟的结果。

35.设顺序表va中的数据元素递增有序。试编写算法实现将x插入到顺序表的适当位置上，以保持该

表的有序性。 15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ） A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡

27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是______。 28.冒泡排序最好的时间复杂度为_______，平均时间复杂度为_______，是一种稳定的排序算法。 33.用快速排序法对数据序列(49，38，65，97，16，53，134，27，39)进行排序，写出其第一趟排序的全过程。

34.完善下列折半插入排序算法。

Voidbinasort(structnoder[MAXSIZE]，int n) {for(i=2;i<=n;i++){ r[0]=r[i];low=1;high=i-1; while(low<=high){ mid=(1)_________;

if(r［0］.key

for(j=i-1;j>=low;j--) (4)_________; r[low]=r[0]; }

}

4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（）

29

A.n B.2n-1 C.2n D.n2

14.一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（ ） A.80，45，55，40，42，85 B.85，80，55，40，42，45 C.85，80，55，45，42，40 D.85，55，80，42，45，40

26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为________。 28.对n个元素进行冒泡排序时，最少的比较次数为________。

33.用插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行排序，写出整个插入排序的每一趟过程。

14.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是( ) A.快速排序 B.堆排序 C.插入排序 D.二路归并排序

15.在排序方法中,从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )A.希尔排序B.插入排序C.冒泡排序D.快速排序 27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用____________。 28.对n个元素的序列进行冒泡排序时，最多需进行___________趟。

29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的结果。

34.编写一个函数void insert(int *p,int size,int a)，其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是：首先采用折半查找的方法，找出要插入数据的位置；然后按升序将数据插入该数组中。

14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( ) A.选择排序 B.插入排序 C.冒泡排序 D.快速排序

15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( ) A.希尔排序 B.归并排序 C.插入排序 D.选择排序

27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行__________趟才能够完成。

28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为__________。

30.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 15．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（ ）

A．36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81 27．二路归并排序算法的时间复杂度为_______。

31．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出整个冒泡排序的每一趟过程。

35．试写出直接插入排序算法。

14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ） A.选择排序 B.快速排序 C.冒泡排序 D.插入排序

30

15.排序算法中，不稳定的排序是（ ）

A.直接插入排序 B.冒泡排序 C.堆排序 D.归并排序 27.在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用____。 28.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。 33.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。 34.在下面冒泡排序算法中（1）～（4）处填入适当内容，以使该算法在发现有序时能及时停止。 bubble（R） Rectype R［n］；

{ int i，j，exchang；

Rectype temp； i=1； do

{ exchang=False；

for（j=n；j>= （1）________；j--）

if（R［j］

{ temp=R［j-1］；

R［j-1］=R［j］； R［j］=temp；

exchang= （2）________；

}

（3）________；

}

while（exchang= （4）________）； }

14.当待排序序列中记录数较多时，速度最快的排序方法是（ ） A.冒泡排序法 B.快速排序法 C.堆排序法 D.归并排序法

15.若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（ ）

A.15，22，26，30，50，53，69，87 B.15，30，22，26，50，69，53，87 C.15，26，30，22，50，69，53，87 D.15，26，22，30，50，53，69，87

28.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行________________趟起泡。 32.已知一组键值序列（33，37，26，43，55，67，42，38），试采用堆排序法对该组序列作升序排序，给出建立的初始堆，以及第一次输出堆元素后筛选调整的堆。

33.已知一组键值序列（22，24，26，25，27，29，21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。

14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为( ) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法

15.若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是( ) A.插入排序 B.冒泡排序 C.快速排序 D.选择排序

31

28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的__________中

32.已知一组键值序列（32，44，38，65，53，42，29，57），试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。

33.已知一组键值序列（13，12，16，17，15，14，11），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。

14.堆排序属于一种选择排序，其时间复杂性为( )A.O(1) B.O(nlog2n) C.O(n) D.O(n2) 15.下列排序方法中，属于不稳定的排序方法是( )

A.直接插入排序法 B.冒泡排序法 C.基数排序法 D.归并排序法 28.在各种内部排序中，占用存储空间较大的排序通常是___________排序。

32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列 作升序排序，并给出每一趟的排序结果。

33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列 作升序排序，并给出每一趟的排序结果。

14.直接插入排序算法，其时间复杂性为（ ） A.O(1) B.O(n) C.O(nlog2n) D.O(n2)

15.下列排序方法中，属于稳定的排序方法是（ ）

A.直接插入排序法 B.快速排序法 C.冒泡排序法 D.堆排序法

28.在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为____次。 32.已知一组键值序列（28，47，35，42，53，60，34，22），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。

33.已知一组键值序列（3，6，8，9，2，7，4，3），试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。

14．下列关键码序列中，属于堆的是（ ）

A．（15，30，22，93，52，71） B．（15，71，30，22，93，52） C．（15，52，22，93，30，71） D．（93，30，52，22，15，71）

15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（ ） A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95

27．在排序方法中，依次将每个记录插入到一个有序的子序列中去，即在第i(i≥1)遍整理时，r1,r2,…,ri-1已经是排好顺序的子序列，取出第i个元素ri，在已排好序的子序列里为ri找到一个合适的位置，并把它插到该位置上。这种排序方法被称为___________。

28．快速排序法在待排序数据_____________的情况下最不利于发挥其长处

33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）

32

本文来源：https://www.bwwdw.com/article/9a4r.html