文档库 最新最全的文档下载
当前位置:文档库 › 数据结构各章复习题

数据结构各章复习题

数据结构各章复习题
数据结构各章复习题

第一章概述

一、选择题

1.以下哪种数据结构中任何两个结点之间都没有逻辑关系()。

A.树形结构 B.集合 C.图形结构 D.线性结构

2.要求同一逻辑结构的所有数据元素具有相同的性质,这意味着()。

A.数据元素具有同一的特点

B.不仅数据元素包含的数据项的个数相同,而且对应数据项的类型要一致

C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等

3.以下说法正确的是()。

A.数据元素是数据的最小单位 B.数据项是数据的基本单位

C.数据结构是带有结构(或称关系)的数据项的集合 D.数据结构是带有结构(或称关系)的数据元素的集合

4.下面的叙述不是算法的特性的是()。

A.有穷性 B.输入性 C.可行性 D.可读性

5.下面的叙述中()不是设计一个好的算法应达到的目标。

A.健壮性 B.可读性 C.高存储量 D.正确性

6.下面运算中()不是数据结构所具备的基本运算。

A.插入 B.排序 C.退出 D.删除

7.数据结构是一门研究非数值计算的程序设计问题中计算机的( 1 )以及它们之间的( 2 )和运算等的学科。

(1)A.数据元素 B.计算方法C.逻辑存储 D.数据映像

(2)A.结构 B.关系 C.运算 D.算法

8.数据结构被形式地定义为(K,R),其中K是( 1 )的有限集,R是K上的( 2 )的有限集。

(1)A.算法 B.数据元素 C.数据操作 D.逻辑结构

(2)A.操作 B.映像 C.存储 D.关系

9.在数据结构中,从逻辑上可以把数据结构分成()。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构

C.线性结构和非线性结构 D.内部结构和外部结构

10.数据结构在计算机内存中的表示是指()。

A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系

11.在数据结构中,与所使用的计算机无关的是数据的()结构。

A.逻辑 B.存储 C.逻辑和存储 D.物理

12.算法分析的目的是( 1 ),算法分析的两个主要方面是( 2 )。

(1)A.找出数据结构的合理性 B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性

(2)A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性

13.计算机算法指的是( 1 ),它必须具备输入、输出和( 2 )等5个特性。

(1)A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法

(2)A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性

14.在以下的叙述中,正确的是()。

A.线性表的线性存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出 D.队列的操作方式是先进后出

15.在决定选取何种存储结构时,一般不考虑()。

A.各结点的值如何 B.结点个数的多少

C.对数据有哪些运算 D.所用编程语言实现这种结构是否方便

16.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储()。

A.数据的处理方法 B.数据元素的类型

C.数据元素之间的关系 D.数据的存储方法

17.下面说法错误的是()。

(1)算法原地工作的含义是指不需要任何额外的辅助空间。

(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。

(3)所谓时间复杂度是指最坏情况下,估计算法执行的一个上界。

(4)同一个算法,实现语句的级别越高,执行效率越低。

A.(1) B.(1)(2) C.(1)(4) D.(3)

二、填空题

1.一种数据结构在计算机内存中的()称为存储结构。

2.数据的逻辑结构包括()()和()三种结构,树形结构和图形结构合称为(非线性结构)。

3.在线性结构中,第一个结点()前驱结点,其余每个结点有且只有()个前驱结点;最后一个结点()后继结点,其余每个结点有且只有()个后继结点。

4.在树形结构中,根结点没有()结点,其余每个结点有且只有()个前驱结点,叶子结点没有()结点,其余每个结点的后继结点可以()。

5.在图形结构中,每个结点的前驱结点数和后继结点数可以()。

6.线性结构中元素之间存在()关系,树形结构中元素之间存在()关系,图形结构中元素之间存在()关系。

7.算法的5个重要特性是()、()、()输入和输出。

8.算法可以用不同的语言描述,如果用C语言或PASCAL语言等高级语言来描述,则算法实现上就是程序了。这种说法是()的。

9.算法效率分析可分为()分析和()分析。

10.数据结构的存储方式有()、()、()和()4种。

11.数据结构包括()、()、()三个组成部分。

12.数据对象是性质相同的()的集合。

三、判断题

1.顺序存储方式只能用于存储线性结构。()

2.数据元素是数据的最小单位。()

3.数据结构、数据元素、数据项在计算机中的映像(或表示)分别称为存储结构、结点、数据域。()4.数据的物理结构是指数据在计算机内实际的存储形式。()

5.数据的逻辑结构是对数据元素之间关系的描述,它与数据元素的存储形式无关。()

四、问答题

1.指出下列程序段的时间复杂度

(1)i=1 (2) i=n

while(i<=n) while(i>=0 && a[i]!=k)

i=i*3; i--;

(3) for(i=0;i

for(j=0;j

a[i][j]=i*j; return (1);

else

return(n*fact(n-1)); }

2.画出下列二元组表示的数据结构对应的逻辑图形,并指出分别属于何种结构。

(1)B=(K,R)

K={a,b,c,d,e,f,g,h}

R={,,,,,,}

(2) C=(K,R)

K={1,2,3,4,5,6}

R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

第二章线性表

一、选择题

1.链表不具备的特点是()。

A.可随机访问任一结点 B.插入删除不需要移动元素

C.不必事先估计存储空间 D.所需空间与其长度成正比

2.不带头结点的单链表head为空的判定条件是()。

A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL

3.带头结点的单链表head为空的判定条件是( )。

A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL

4.带头结点的双循环链表L为空表的条件是()。

A.L==NULL B.L->next==NULL C.L->prior==NULL D.L->next==L

5.非空的循环单链表head的尾结点(由P所指向)满足()。

A.p->next==NULL B.p==NULL C.p->next==head D.p==head

6. 在循环双链表的p所指结点之前插入s所指结点的操作是()。

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

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

C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;

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

7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间。

A.单链表B.给出表头指针的单循环链表 C.双链表D.带头结点的双循环链表

8.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,故采用()存储方式最节省运算时间。

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

9.如果最常用的操作是取第i个结点及其前驱,则采用()存储方式最节省时间。

A.单链表 B.双链表 C.单循环链表 D.顺序表

10.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()。

A.O(1) B.O(n) C.O(n2) D.O(nlog2n)

11.在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行()操作与链表的长度有关。

A.删除单链表中的第一个元素B.删除单链表中的最后一个元素

C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素

12.设线性表有n个元素,以下算法中,()在顺序表上实现比在链表上实现效率更高。

A.输出第i(0≤i≤n-1)个元素值 B.交换第0个元素与第1个元素的值

C.顺序输出这n个元素的值D.输出与给定值x相等的元素在线性表中的序号

13.设线性表中有2n个元素,算法(),在单链表上实现比在顺序表上实现效率更高。

A.删除所有值为x的元素 B.在最后一个元素的后面插入一个新元素

C.顺序输出前k个元素D.交换第i个元素和第2n-i-1个元素的值(i=0,1,..,n-1) 14.与单链表相比,双链表的优点之一是()。

A.插入、删除操作更简单 B.可以进行随机访问

C.可以省略表头指针或表尾指针 D.顺序访问相邻结点更灵活

15.如果对线性表的运算只有4种,即删除第一个元素,删除最后一个元素,在第一个元素前面插入新元

素,在最后一个元素的后面插入新元素,则最好使用()。

A.只有表尾指针没有表头指针的循环单链表 B.只有表尾指针没有表头指针的非循环双链表

C.只有表头指针没有表尾指针的循环双链表 D.既有表头指针也有表尾指针的循环单链表

16.如果对线性表的运算只有2种,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用()。

A.只有表头指针没有表尾指针的循环单链表 B.只有表尾指针没有表头指针的循环单链表

C.非循环双链表 D.循环双链表

17.设有两个长度为n的单链表,结点类型相同,若以h1为表头指针的链表是非循环的,以h2为表头指针的链表是循环的,则()。

A.对于两个链表来说,删除第一个结点的操作,其时间复杂度都是O(1)

B.对于两个链表来说,删除最后一个结点的操作,其时间复杂度都是O(n)

C.循环链表要比非循环链表占用更多的内存空间

D.h1和h2是不同类型的变量

18.在长度为n的()上,删除第一个元素,其算法的时间复杂度为O(n)。

A.只有表头指针的不带表头结点的循环单链表 B.只有表尾指针的不带表头结点的循环单链表

C.只有表尾指针的带表头结点的循环单链表 D.只有表头指针的带表头结点的循环单链表

19.线性表是()。

A.一个有限序列,可以为空 B.一个有限序列,不能为空

C.一个无限序列,可以为空 D.一个无限序列,不能为空

20.设单链表中指针p指向结点M,指针f指向将要插入的新结点X:

(1)当X插在链表中两个数据元素M和N之间时,只要先修改()后修改()即可。

(2)当X插在链表中最后一个结点M之后时,只要先修改()后修改()即可。

A.p->next=f B.p->next=p->next->next C.p->next=f->next D.f->next=p->next E.f->next=NULL F.f->next=p

21.在单循环链表中指针p指向结点A,若要删除A之后的结点,则指针的操作方式为()。

A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p

22.给定有n个元素的向量,建立一个有序单链表的时间复杂度为()。

A.O(1) B.O(n) C.O(n2) D.O(nlog2n)

23.线性表采用链式存储时,其地址()。

A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可以

24.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较()个元素。

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

二、填空题

1.在单链表中,要删除某一指定的结点,必须找到该结点的()结点。

2.访问单链表中的结点,必须沿着()依次进行。

3.在双链表中,每个结点都有两个指针域,一个指向(),另一个指向()。

4.在()链表上,删除最后一个结点,其算法的时间复杂长为O(1)。

5.在非循环的()链表中,可以用表尾指针代替表头指针。

6.在一个单链表中的p所指结点之前插入一个s所指结点时,可执行如下操作:

(1)s->next=( ); (2)p->next=s; (3)t=p->data;

(4)p->data=( ); (5)s->data=( );

7.在一个单链表中删除p所指结点时,应执行以下操作:

q=p->next; p->data=p->next->data; p->next=( ) free(q);

8.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=( )和p->next=( )的操作。

9.对于一个具有n个结点的单链表,在*p结点后插入一个新的结点的时间复杂度是(),在给定值为x的结点后插入一个新结点的时间复杂度是()。

10.在一个长度为n的顺序表的第i(1<=i<=n)个元素之前插入一个元素需向后移动()个元素。11.在长度为n的顺序表中,删除第i(1<=i<=n)个元素,需向前移动()个元素。

12.线性表常用的存储结构有()和()。

13.线性表的逻辑结构是(),其所含结点的个数称为线性表的()。

14.当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用()存储结构为宜,当经常进行的是插入删除操作时,则采用()存储结构为宜。

三、判断题

1.顺序存储的线性表可以随机存取。()

2.线性表中的元素可以是各种类型的,但同一线性表中的数据元素具有相同的性质,因此属于同一数据对象。()

3.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定是相邻的。()

4.线性表的链式存储结构优于顺序存储结构。()

5.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。()

6.顺序存储方式只能用于存储线性结构。()

7.链表的每个结点中都恰好包含一个指针。()

四、简答题

1.头指针、头结点和首结点的区别是什么?

2.线性表的两种存储结构各有哪些优缺点?

3.对链表设置头结点的作用是什么?

五、算法题

1.建立一个由n个结点构成的单链表L=(1,2,3,…n)。

2.求单链表中数据域为x的结点个数。

3.求某一循环单链表的表长。

4.在头指针为head的单链表中查找值为x的元素。

5.复制一个单链表(依次查找头指针为head1的单链表中的每个结点,对每个结点复制一个新结点并链接到头指针为head2的单链表中)。

6.将单链表中所有值为x的元素替换成y。

7.编写函数,通过一次遍历确定单链表中值最大的结点,返回其地址。

8.编写函数将一个不带头结点的单链表中的所有结点逆置。

9.编写函数删除单链表中第i个结点。

10.在长度大于1的循环单链表中,既无头结点也无头指针,p指向链表中某一结点,编写算法删除该结点的前驱结点。

11.在单链表中删除值为x的所有元素。

12.已知带头结点的单链表中的元素按递增顺序排列,编写函数删除表中所有值大于min且小于max的元素。(max>min)

13.已知带头结点的单链表中的元素是无序的,编写函数删除表中所有值大于min且小于max的元素。

(max>min)

14.编写函数,对一单链表反复找出表中最小元素,并在输出该元素后删除它,直到表为空时结束。15.有一个单链表,其结点的元素值以递增有序排列,编写函数删除该单链表中多余的元素值相同的结点。16.试写出一个在不带头结点的单链表的第i个元素之前插入一个新元素x 的算法。

17.有一个有序单链表,表头指针为head,编写函数向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。

18.设A,B是两个线性表,其表中元素递增有序,长度分别为m和n,试写算法分别以顺序存储和链式存储将A 和B归并成一个仍按元素值递增有序的线性表C。

19.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa 和pb,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序。

20.有一个循环双链表,每个结点由两个指针(prior和next)以及data三个域构成,p指向其中某一结点,编写一函数删除p所指结点。

21.设有一个循环双链表,其中有一结点的指针为p,编写一个算法将p与其后继结点进行交换。

第三章栈和队列

一、选择题

1.栈和队列的共同点是()。

A.都是先进后出B.都是先进先出 C.只允许在端点处插入和删除元素D.没有共同点

2.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。

A.edcba B.decba C.dceab D.abcde

3.若已知一个栈的进栈序列是1,2,3,..,n,其输出序列为p1,p2,p3,..,p n,若p1=n则p i(1≤i

A.i B.n-i C.n-i+1 D.不确定

4.若已知一个栈的进栈序列是1,2,3,..,n,其输出序列为p1,p2,p3,..,p n,若p n=n则p i(1≤i

A.i B.n-i C.n-i+1 D.不确定

5.若已知一个栈的进栈序列是1,2,3,..,n,其输出序列为p1,p2,p3,..,p n,若p1=3则p2为()。

A.可能是2 B.一定是2 C.可能是1 D.一定是1

6.若已知一个栈的进栈序列是p1,p2,p3,..,p n,其输出序列为1,2,3,..,n,若p3=1则p1为()。

A.可能是2 B.一定是2 C.不可能是2 D.不可能是3

7.判定一个栈ST(最多元素为MaxSize)为空的条件是()。

A.ST->top!=-1 B.ST->top==-1 C.ST->top!=MaxSize-1 D.ST->top==MaxSize-1

8.判定一个栈ST(最多元素为MaxSize)为栈满的条件是()。

A.ST->top!=-1 B.ST->top==-1 C.ST->top!=MaxSize-1 D.ST->top==MaxSize-1

9.最不适合用作链栈的链表是()。

A.只有表头指针没有表尾指针的循环双链表 B.只有表尾指针没有表头指针的循环双链表

C.只有表尾指针没有表头指针的循环单链表 D.只有表头指针没有表尾指针的循环单链表

10.向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行( )。

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

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

11.从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删除结点的值,则执行()。

A.x=HS;HS=HS->next; B.x=HS->data;

C.HS=HS->next;x=HS->data; D.x=HS->data;HS=HS->next;

12.一个队列的入队序列是1,2,3,4,则队列的输出序列是()。

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

13.判定一个队列QU(最多元素为MaxSize)为空的条件是( )。

A.QU->rear-QU->front==MaxSize B.QU->rear-QU->front-1==MaxSize

C.QU->front==QU->rear D.QU->front==QU->rear+1

14.循环顺序队列中是否可以插入下一个元素,()。

A.与队头指针和队尾指针的值有关B.只与队尾指针的值有关,与队头指针的值无关

C.只与数组大小有关,与队首指针和队尾指针的值无关

D.与曾经进行过多少次插入操作有关

15.判定一个循环队列QU(最多元素为MaxSize)为空的条件是()。

A.QU->front==QU->rear B.QU->front!=QU->rear

C.QU->front==(QU->rear+1)%MaxSize D.QU->front!=(QU->rear+1)%MaxSize

16.判定一个循环队列QU(最多元素为MaxSize)为满队列的条件是()。

A.QU->front==QU->rear B.QU->front!=QU->rear

C.QU->front==(QU->rear+1)%MaxSize D.QU->front!=(QU->rear+1)%MaxSize

17.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front 和rear,则当前队列中的元素个数是()。

A.(rear-front+m)%m B.rear-front+1 C.rear-front-1 D.rear-front

18.若用一个大小为6的一维数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是()。

A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1

19.最不适合用作链队列的链表是()。

A.只带队头指针的非循环双链表B.只带队头指针的循环双链表

C.只带队尾指针的循环双链表 D.只带队尾指针的循环单链表

20.在一个链队列中,假设f和r 分别为队头和队尾指针,则插入s所指结点的运算是()。

A.f->next=s;f=s; B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;

21.在一个链队列中,假设f和r 分别为队头和队尾指针,则删除一个结点的运算是()。

A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next;

22.设有一个顺序栈S,元素的入栈顺序是S1,S2,S3,S4,S5,S6,如果6个元素出栈的顺序是S2,S4,S3,S6,S5,S1,则栈的容量至少应该是()。

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

23.和顺序栈相比,链栈比较明显的优势是()。

A.通常不会出现栈满的情况 B.通常不会出现栈空的情况

C.插入操作更容易实现 D.删除操作更容易实现

24.如果以链表作为栈的存储结构,则退栈操作时()。

A.必须判别栈是否满 B.判别栈元素类型 C.必须判别栈是否空 D.对栈不作任何判别

25.设C语言定义数组data[m+1]作为循环队列的存储空间,front,rear分别为队头,队尾指针,则执行出队操作的语句是()。

A.front=front+1 B.front=(front+1)%m C.front=(front+1)%(m+1) D.rear=(rear+1)%m

26. 输入序列为ABC,可以变为CBA时,经过的栈操作为()。

A. push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop

D. push,pop,push,push,pop,pop

27. 若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是( )。

A.top=top+1; V [top]=x B. V [top]=x; top=top+1

C. top=top-1; V [top]=x

D. V [top]=x; top=top-1

28. 栈在()中应用。

A. 递归调用

B. 子程序调用

C. 表达式求值

D. A,B,C

29. 表达式a*(b+c)-d的后缀表达式是( )。

A.abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

二、填空题

1.栈的特点是(),队列的特点是()。

2.设栈采用顺序存储结构,若已知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为()。

3.若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作是()。

4.在具有n个单元的循环队列中,队满时共有()个元素。

5.循环队列的引进目的是为了解决()问题。

6.在队列中,新插入的结点只能添加到()。

7.()可以作为实现递归函数调用的一种数据结构。

8.通常元素进栈的操作方式是()。

9.通常元素退栈的操作方式是()。

10.一个栈的输入序列是12345,则栈的输出序列43512是()。

11.在作进栈运算时应先判别栈是否(满);在作退栈运算时应先判别栈是否(),当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。

三、简答题

1. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式,画出栈的变化过程图。

2.栈和队列的共同点和区别是什么?

3. 怎样判定循环队列的空和满?

4. 画出后缀表达式ABC*D/-E-,求值时操作数栈和运算符栈的变化过程。

5. 在一个循环链.队中只有尾指针(记为rear,结点结构为数据域data,指针域next),请给出这种队列的入队和出队操作的实现过程。

四、算法题

1.分别写出顺序栈、链栈,顺序队列、链队列的进栈,出栈,入队列、出队列的算法。

2.利用栈和队列的特点。编写算法判断一个字符串是否为回文。

3.编写算法将一个十进制数转换成二进制。

第四章串

一、选择题

1.空串与空格串是相同的,这种说法()。

A.正确 B.不正确

2.串是一种特殊的线性表,其特殊性体现在()。

A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符

3.设有两个串p和q,求q在p中首次出现的位置的运算称作()。

A.连接 B.模式匹配 C.求子串 D.求串长

4.有串s1=“ABCDEFG”,s2=“PQRST”,假设函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s 从序号i字符开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果是()。

A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG

5.已知t=“abcaabbcabcaabdab”,该模式串的next数组值为()。

A.-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1 B. 0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1

C.-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1 D.-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1

6.若串s=”software”,其子串的个数是()。

A.8 B.37 C.36 D.9

7.KMP算法的特点是在模式匹配时指示主串的指针不会变小,这种说法()。

A.正确 B.错误

二、填空题

1.串的两种最基本的存储方式是()。

2.两个串相等的充分必要条件是()。

3.空串的长度等于(),空格串的长度等于()。

4.设s=“I AM A TEACHER”其长度是()。

5.设s1=”GOOD”,s2=””,s3=”BYE!”则s1,s2,s3连接后的结果是()。

6.BF算法的时间复杂度为(),KMP算法的时间复杂度为()

第五章数组和广义表

一、选择题

1.一维数组和线性表的区别是()。

A.前者长度固定,后者长度可变 B.后者长度固定,前者长度可变

C.两者长度均固定 D.两者长度均可变

2.二维数组M的成员是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要(①)个字节,M的第8列和第5行共占(②)个字节,若M按行优先方式存储,元素M[8][5]的起始地址与当M按列优先方式存储时元素(③)的起始地址一致。

①A.90 B.180 C.240 D.540

②A.108 B.114 C.54 D.60

③A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]

3.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i范围从0到4,列下标j的范围从0到5,M按行优先存储时元素M[3][5]的起始地址与M按列优先存储时元素()的起始地址相同。

A.M[2][4] B.M[3][4] C.M[3][5] D.M[4][4]

4.数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是()。

A.80 B.100 C. 240 D.270

5.数组A中每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为()。

A.SA+141 B.SA+144 C.SA+222 D.SA+225

6.数组A中每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按列存放时,A[5][8]的起始地址为()。

A.SA+141 B.SA+180 C.SA+222 D.SA+225

7.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a1.1为第一个元素,其存储地址为1,每个元素占1个地址空间,则a8.5的地址为()。

A.13 B.33 C.18 D.40

8.一个n*n的对称矩阵,如果以行或列为主序放入内存,则容量为()。

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

9.稀疏矩阵一般的压缩存储方法有两种,即()。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表

10.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点()。

A.正确B.错误

11.数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。

A.1175

B. 180

C.1205

D.1210

12. 将一个A[1..100,1..100]的对角矩阵,按行优先存入一维数组B[1‥298]中,A中元素A6665(即该元素下标i=66,j=65),在B数组中的位置K为()。

A. 198

B. 195

C. 197

D.201

13. 有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数据占2个字节,则用三元组表示该矩阵时,所需的字节数是()。

A. 60

B. 66

C. 18000

D. 33

14. 数组A[0..4,-1..-3,5..7]中含有元素的个数()。

A. 55

B. 45

C. 36

D. 16

15.对数组经常进行的操作有()。

A.建立与删除 B.索引与修改 C.查找与修改 D.查找与索引

16.下面说法不正确的是( )。

A. 广义表的表头总是一个广义表

B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构

D. 广义表可以是一个多层次的结构

17.广义表((a),a)的表头是( C ),表尾是( C )。

A.a B.b C.(a) D.((a))

18.广义表((a))的表头是( B ),表尾是( C )。

A.a B.(a) C.( ) D.((a))

19.广义表((a,b),c,d)的表头是( C ),表尾是( D )。

A.a B.b C.(a,b) D.(c,d)

20.广义表(a,b,c,d)的表头是( A ),表尾是( D )。

A.a B.b C.(a,b) D.(b,c,d)

21.一个广义表的表头总是一个广义表,这个断言是()。

A.正确的B.错误的

22.一个广义表的表尾总是一个广义表,这个断言是()。

A.正确的B.错误的

23.已知广义表L=((x,y,z), (u,t,w)),从L表中取出原子t的运算是()。

A.head(tail(tail(L))) B.tail(head(head(tail(L))))

C.head(tail(head(tail(L)))) D.head(head(tail(tail(L))))

24.若广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为()。

Head(tail(head(tail(tail(A)))))

A.(g) B.(d) C.(c) D.d

25.若广义表A满足Head(A)=Tail(A),则A为()。

A.() B.(()) C.((),()) D.((),(),())

二、填空题

1.当广义表中的每个元素都是原子()时,广义表便成了()。

2. 广义表(a,(a,b),d,e,((i,j),k))的长度是(),深度是()。

3.一维数组的存储结构是(),逻辑结构是(),对二维数组来说分()和()两种不同的存储方式。

4.已知二维数组A[m][n]采用行为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是()。

5.二维数组A[10][20]采用以列为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是()。

6.二维数组A[10..20][5..10]采用行为主方式存储,每个元素占四个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是()

7.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主存储且A[0][0]=1),则A[8][5]的地址是()8.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2+1]中,若按行序为主存储,当i>=j时,A[i][j]对应的S中的存储位置是()。

9.一个对称矩阵,采用压缩存储方式存储其容量为(),若不采用压缩存储则容量为()

三角矩阵压缩存储时其容量为()。

三、判断题

1.若一个广义表的表头为空表,则此广义表也为空表。( )

2.广义表是线性表的推广,是一类线性结构。()

3.一个稀疏矩阵采用三元组形式表示,若把三元组中行下标和列下标的值互换,则完成了矩阵的转置运算。()

4.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树型的。()

5.线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表。()6.广义表中原子的个数即为广义表的长度。()

7. 稀疏矩阵压缩存储后,必会失去随机存取功能。()

四、应用题

1.已知广义表L=((((a))),((b)),(c),d),试利用head和tail运算把原子项c从L中分离出来。

2.画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。

3.知广义表A=(((b,c),d),(a),((a),((b,c),d)),e,())

(1)画出其一种存储结构图;(2)写出表的长度与深度,表头与表尾。

4.稀疏矩阵A如图所示,画出以下各种表示法:(1)行优先三元组表示法;(2)列优先三元组表示法;(3)伪地址表示法;(4)十字链表示法。

15 0 0 22 0 -15

0 13 3 0 0 0

0 0 0 -6 0 0

0 0 0 0 0 0

91 0 0 0 0 0

0 2 8 0 0 0

第六章树

一、选择题

1.树最适合用来表示()。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

2.在线索化二叉树中,t所指结点没有左子树的充要条件是()。

A.t->left==NULL B.t->ltag==1 C. t->ltag==1且t->left==NULL D.以上都不对

3.二叉树按某种顺序线索化后,任一结点均有指向其前驱和后续的线索,这种说法()。

A.正确B.错误

4.二叉树的先序遍历序列中,任意一个结点均处在其孩子结点的前面,这种说法()。

A.正确B.错误

5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中包含的结点数至少是()。

A.2h B.2h-1 C.2h+1 D.h+1

6.如果T2是由有序树T1转换而来的二叉树,那么T1中结点的先序就是T2中结点的()。

A.先序 B.中序C.后序D.层次序

7.如果T2是由有序树T1转换而来的二叉树,那么T1中结点的后序就是T2中结点的()。

A.先序 B.中序 C.后序 D.层次序

8.某二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树一定是()。

A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数

9.树的基本遍历策略可分为先根遍历和后根遍历,二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历,这里,把由树转化得到的二叉树叫做这棵树对应的二叉树,结论()是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上都不对

10.按照二叉树的定义,具有3个结点的二叉树有()种。

A.3 B.4 C.5 D.6

11.深度为5的二叉树至多有()个结点。

A.16 B.32 C.31 D.10

12.在一棵非空二叉树的中序遍历序列中,根结点的右边()。

A.只有右子树上的所有结点B.只有右子树上的部分结点

C.只有左子树上的部分结点D.只有左子树上的所有结点

13.任何一棵二叉树的叶子结点在先序,中序和后序遍历序列中的相对次序()。

A.不发生改变B.发生改变C.不能确定D.以上都不对

14.对一个满二叉树,m个树叶,n个结点,深度为h,则()。

A .n=h+m

B .h+m=2n

C .m=h-1

D .n=2h

-1

15.设n,m 为一棵二叉树上的两个结点,在中序遍历时,n 在m 前的条件是( )。

A .n 在m 右方

B .n 是m 祖先

C .n 在m 左方

D .n 是m 子孙

16.线索二叉树是一种( )结构。

A .逻辑

B .逻辑和存储

C .物理

D .线性结构

17.根据使用频率,为5个字符设计的哈夫曼编码不可能的是( )。

A .111,110,10,01,00

B .000,001,010,011,1

C .100,11, 10, 1, 0

D .001,000,01, 11, 10

18.根据使用频率,为5个字符设计的哈夫曼编码不可能的是( )。

A .000,001,010,011,1

B .0000,0001,001,01,1

C .000,001,01,10,11

D .00,100,101,110,111

19.已知一算术表达式的中缀形式为 A+B*C-D/E ,后缀形式为ABC*+DE/-,其前缀形式为( )

A .-A+B*C/DE B. -A+B*CD/E C .-+*ABC/DE D. -+A*BC/DE

20. 设有一表示算术表达式的二叉树(见下图), 它所表示的算术表达式是( )。 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+(F-G )) D. A*B+C/D*E+F-G

21. 在下述结论中,正确的是( )。

①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;

④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A .①②③

B .②③④

C .②④

D .①④

22. 设森林F 对应的二叉树为B ,它有m 个结点,B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树

的结点个数是( )

A .m-n

B .m-n-1

C .n+1

D .条件不足,无法确定

23.对于有n 个结点的二叉树, 其高度为( )。

A .nlog 2n

B .log 2n

C .?log 2n ?|+1

D .不确定

24.深度为h 的满m 叉树的第k 层有( )个结点。(1=

A .m k-1

B .m k -1

C .m h-1

D .m h -1

25.在下列存储形式中,哪一个不是树的存储形式?( )。

A .双亲表示法

B .孩子链表表示法

C .孩子兄弟表示法

D .顺序存储表示法

26. 引入二叉线索树的目的是( )。

A .加快查找结点的前驱或后继的速度

B .为了能在二叉树中方便的进行插入与删除

C .为了能方便的找到双亲

D .使二叉树的遍历结果唯一

27.在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树,该说法( )。

A .正确

B .错误

二、填空题

1.二叉树由( ),( ),( )三个基本单元组成。

2.树在计算机内的表示方式有( ),( ),( )。

3.在二叉树中,指针p 所指结点为叶子结点的条件是( )。

4.中缀式a+b*3+4*(c-d )对应的前缀式为( ),若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的

运算结果为( )。

5.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的( )。

6.具有256个结点的完全二叉树的深度为( )。

7.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树有( )

个叶子结点。

8.深度为k的完全二叉树至少有()个结点,至多有()个结点。

9.在完全二叉树中,编号为i和j的两个结点处于同一层的条件是()。

10.假设根结点的层数为1,具有n个结点的二叉树的最大高度是()。

11.在一棵二叉树中,度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =()。

12.设有N个结点的完全二叉树顺序存放在向量A[1:N]中,其下标值最大的分支结点为()。13.高度为K的完全二叉树至少有()个叶子结点。

14.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是()。

15.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是()。

16.对于一个具有n个结点的二元树,当它为一棵()二叉树时具有最小高度,当它为一棵()时,具有最大高度。

17.具有N个结点的二叉树,采用二叉链表存储,共有()个空链域。

18.含4个度为2的结点和5个叶子结点的二叉树,可有______个度为1的结点。

19.二叉树结点的中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(),则该二叉树对应的树林包括()棵树。

20.现有按中序遍历二叉树的结果为abc,问有()种不同的二叉树可以得到这一遍历结果,这些二叉树分别是()。

21.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点,则它必是该子树的()序列中的最后一个结点。

22.先根次序周游树林正好等同于按()周游对应的二叉树;后根次序周游树林正好等同于()周游对应的二叉树。

23.具有n个结点的满二叉树,其叶子结点的个数是(),分支结点数是()。

24.线索二叉树的左线索指向其(),右线索指向其()。

25.哈夫曼树是()。

26.若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是()。

27.设n0为哈夫曼树的叶子结点数目,则该哈夫曼树共有()个结点。

三、应用题

1.①试找出满足下列条件的二叉树

1)先序序列与后序序列相同 2)中序序列与后序序列相同

3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同

5)先序序列与中序序列相反

②已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA,画出这棵二叉树,并求该二叉树的先序序列。

2.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果)

3

先序遍历序列: A B D F C E G H 中序遍历序列: B F D A G E H C

(1)画出这棵二叉树。

(2)画出这棵二叉树的后序线索树。

(3)将这棵二叉树转换成对应的树(或森林)。

4.一棵二叉树的先序、中序、后序序列如下,其中一部分未标出,请构造出该二叉树。

先序序列:_ _ C D E _ G H I _ K

中序序列:C B _ _ F A _ J K I G

后序序列:_ E F D B _ J I H _ A

5.设二叉树的存储结构如下:

其中BT为树根结点的指针,其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:

(l)画出二叉树BT的逻辑结构;

(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列;

(3)画出二叉树的中序线索树。

6.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码,使得上述正文的编码最短。7.试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。

8.以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树,并计算其带权路径长度。(请按左子树根结点的权小于等于右子树根结点的权的次序构造)

9.树和二叉树之间有什么样的区别与联系?

四、算法题

1.二叉树用链式方式存储,编写对二叉树进行先序,中序,后序遍历算法。

2.二叉树用链式方式存储,设计一个按层次顺序遍历二叉树的算法。

3.设计一个算法,判断一棵二叉树是否为完全二叉树。

4.计算一棵二叉树中的叶子结点数。

5.计算一棵二叉树中的单分支结点数。

6.求一棵二叉树的高度。

7.编写一个将二叉树中每个结点的左右孩子互换的算法。

8.写出在二叉树中查找值为x的结点的算法。

9.求给定二叉树中的所有结点数。

第七章图

一、选择题

1.在一个图中,所有顶点的度数之和等于所有边数的()倍。

A.1/2 B.1 C.2 D.4

2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。

A.1/2 B.1 C.2 D.4

3.一个有n个顶点的无向图最多有()条边。

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

4.具有4个顶点的无向完全图有()条边。

A.6 B.12 C.16 D.20

5.具有6个顶点的无向图至少应有()条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要()条边。

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

7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是()。

A.n B.(n-1)*(n-1) C.n-1 D.n2

8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为(①),邻接表中的结点总数是(②)。

① A.n B.n+1 C.n-1 D.n+e

② A.e/2 B.e C.2e D.n+e

9.对某个无向图的邻接矩阵来说,()。

A.第i行上的非零元素个数和第i 列上的非零元素个数一定相等

B.矩阵中的非零元素个数等于图中的边数

C.在第i行,第i列上非零元素总数等于顶点vi的度数

D.矩阵中非全零行的行数等于图中的顶点数

10.任何一个无向连通图的最小生成树()。

A.有一棵或多棵 B.只有一棵C.一定有多棵D.可能不存在

11.以下说法中不正确的是()。

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

B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.有向图的遍历不可采用广度优先搜索方法

12.判定一个有向图是否存在回路除了可以利用拓扑排序法外,还可以用()。

A.求关键路径的方法B.求最短路径的方法C.广度优先遍历法 D.深度优先遍历法13.关键路径是事件结点网络中()。

A.从源点到汇点的最长路径 B.从源点到汇点的最短路径

C.最长的回路 D.最短的回路

14.下面不正确的说法是()。

(1)在AOE网中,减小任一关键活动上的权值后,整个工期也就相应减小

(2)AOE网工程工期为关键活动上的权之和

(3)在关键路径上的活动都是关键活动,而关键活动也必须在关键路径上

A.(1) B.(2)C.(3)D.(1)(2)

15.下面不正确的说法是()。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成,将使整个工程提前完成

C.所有关键活动都提前完成,则整个工程提前完成

D.某些关键活动若提前完成,将可能使整个工程提前完成

16.图中有关路径的定义是()。

A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列

C.由不同边所形成的序列 D.上述定义都不是

17.一个有n个结点的图,最少有()个连通分量,最多有()个连通分量。

A.0 B.1 C.n-1 D.n

18.下面结构中最适于表示稀疏无向图的是(),适于表示稀疏有向图的是()。

A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表 E.邻接表

19.下列哪一种图的邻接矩阵是对称矩阵?()

A.有向图 B.无向图 C.AOV网 D.AOE网

20. 下列说法不正确的是()。

A.图的遍历是从给定的源点出发每一个顶点仅被访问一次

C.图的深度遍历不适用于有向图

B.遍历的基本算法有两种:深度遍历和广度遍历

D.图的深度遍历是一个递归过程

21.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},

E={,,,,,,,,},G的拓扑序列是()。

A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7

C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7

22.一个有向无环图的拓扑排序序列()是唯一的。

A.一定 B.不一定

23. 在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。

A.G中有弧 B.G中有一条从Vi到Vj的路径

C.G中没有弧 D.G中有一条从Vj到Vi的路径

二、填空题

1.在n个顶点的无向图中,若边数>n-1,则该图必是连通图,此断言是()的。

2.n个顶点的连通图至少()条边。

3.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于()。

4.一个图的()表示法是惟一的,而()表示法是不惟一的。

5.G是一个非连通无向图,共有28条边,则该图至少有()个顶点。

6.具有10个顶点的无向图,边的总数最多为()。

7.在有n个顶点的有向图中,每个顶点的度最大可达()。

8.已知一个图用邻接矩阵表示,计算第i个结点的入度的方法是()。

9.已知一个图用邻接矩阵表示,删除所有从第i个结点出发的边的方法是()。

10.图的深度优先搜索序列和广度优先搜索序列不是惟一的,此断言是()的。

11.如果含n个顶点的图形成一个环,则它有()棵生成树。

12.对n个顶点的连通图来说,它的生成树一定有()条边。

13.设图G有n个顶点和e条边,采用邻接矩阵存储,则拓扑排序算法的时间复杂度为()。14.若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑有序序列必定存在,此断言是()的。

15.图的存储方法主要有()和(),图的遍历方法主要有()和()。16.有向图G的强连通分量是指()。

17.一个连通图的()是一个极小连通子图。

18. 在有n)条弧。

19.右图中的强连通分量的个数为()个。

20. Prim(普里姆)算法适用于求((克鲁斯卡尔)算法适用于求()的网的最小生成树。

21.AOV网中,结点表示(),边表示()。AOE网中,结点表示(),边表示()。

22.在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为()。

三、应用题

1.解答问题。设有数据逻辑结构为:

B = (K, R), K = {k1, k2, …, k9}

R={, , ,, , ,, , , , }

(1)画出这个逻辑结构的图示。

(2)画出其邻接矩阵存储结构

(3)分别画出该逻辑结构的正向邻接表和逆向邻接表。

2.将如下图所示的无向图给出其存储结构的邻接矩阵和邻接表表示,并写出对其分别进行深度,广度优先遍历的结果。

第2题图 第3题图

3.以顶点①为出发点,画出如图所示的图的深度优先生成树和广度优先生成树。

4.已知一个无向图如下图所示,要求分别用Prim 和Kruskal 算法生成最小生成树,试画出构造过程。

第4题图

5.试写出用克鲁斯卡尔(Kruskal )算法构造下图的一棵最小支撑(或生成)树的过程。

第5题图

6.已知一图如下图所示:

(1)写出该图的邻接矩阵;(2)写出全部拓扑排序序列;

(3)以v1为源点,以v8为终点,给出所有事件允许发生的最早时间和最晚时间,并给出关键路径;

(4).求V1结点到各点的最短距离。

7.对于稠密图和稀疏图,采用邻接矩阵和邻接表哪个更好些?

8.请回答下列关于图的一些问题:

(1)有n 个顶点的有向强连通图最多有多少条边?最少有多少条边?

(2)表示一个有1000个顶点,1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?

(3)对于一个有向图,不用拓扑排序,如何判断图中是否存在环?

第八章 查找

一、选择题

1.分块查找的时间效率( )。

A .高于二分查找

B .高于顺序查找而低于二分查找

第6题图

C.低于顺序查找 D.高于顺序查找且高于二分查找

2.设有一个按元素的值排好序的线性表且长度大于2,对给定的值K,分别用顺序查找法和二分查找法查找一个与K相等的元素,比较次数分别是s和b;在查找不成功的情况下,正确的数量关系是()。A.总有s=b B.总有s>b C.总有s

3.有数据(53,30,37,12,45,24,96)从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应该选择下面哪个序列插入()。

A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96 C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,53

4.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素35要进行()次元素间的比较。

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

5.顺序查找法适合于存储结构为()的线性表。

A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储

6.对线性表进行折半查找时,要求线性表必须()。

A.以顺序方式存储 B.以链式方式存储

C.以顺序方式存储,且结点按关键字有序 D.以链式方式存储,且结点按关键字有序

7.采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为()。

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

8.采用折半查找法查找长度为n的线性表时,查找元素的时间复杂度为()。

A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)

9.有一个长度为12的有序表,按折半查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为()。

A.35/12 B.37/12 C.39/12 D.43/12

10.有一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100)当折半查找值为82的结点时,()次比较后查找成功。

A.1 B.2 C.4 D.8

11.对有18个元素的有序表作折半查找,则查找A[3]的比较序列的下标为()。

A.1、2、3 B.9、5、2、3 C.9、5、3 D.9、4、2、3

12.如图所示的二叉排序树,其查找失败时的平均查找长度是()。

A.21/7 B.28/7 C.15/6 D.21/6

13.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用()查找方法。

A.分块 B.顺序 C.折半 D.散列

14.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分()个结点最佳。

A.10 B.25 C.6 D.625

15.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值,这种说法()。

A.正确 B.错误

16.在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与()量级相当。

A.顺序查找 B.折半查找 C.前两者均不正确

17.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行()

次探测。

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

18.以下说法错误的是()。

A.散列法存储的基本思想是由关键码值决定数据的存储地址

B.散列表的结点中只包含数据元素自身的信息,不包含任何指针

C.装填因子是散列法的一个重要参数,它反映了散列表的装填程度

D.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法

19.散列表的平均查找长度()。

A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关

C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关

20.设散列表长m=14,散列函数H(key)=key%11,表中已有4个结点:addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点的地址是()。

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

二、填空题

1.在各种查找方法中,平均查找长度与结点个数n无关的查找方法是()。

2.若一个待哈希存储的线性表长度为n ,哈希表的长度为m,则m应()n,装填因子为()。3.在哈希存储中,装填因子的值越大,存取元素时发生冲突的可能性(),装填因子的值越小,存取

元素时发生冲突的可能性()。

4.对于二叉排序树的查找,若根结点的值大于被查元素的值,则应该在二叉排序树的()上继续

查找。

5.二叉排序树的查找效率与树的形态有关,当二叉排序树为单支树时,查找算法变为(),其平均

查找长度为()。

6.顺序查找n个元素的线性表,若查找成功,则比较关键字的次数最多为()次。

7.在n个记录的有序顺序表中进行折半查找,最大的比较次数是()。

8.折半查找的存储结构仅限于(),且是();而分块查找要求将待查找的表均匀地分成

若干块且块中诸记录的顺序可以是任意的,但块与块之间必须()。

9.分块查找中,若索引表各块内均用顺序查找,则有900个元素的线性表分成()块最好,若分成25块,其平均查找长度为()。

10.在分块查找方法中,首先查找(),然后再查找相应的()。

11.在散列函数H(key)=key%m中,m应取()。

12.已知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用折半法查找90时,需进行()次查找可确定成功;查找100时,需进行()次查找才能确定不成功。

13.对一棵二叉排序树进行()遍历,可得到一个递增有序序列。

14.用二叉排序树查找,在最坏情况下,平均查找长度(时间复杂度)为(),在最好情况下,平均

查找长度(时间复杂度)为(),

三、判断题

1.采用线性探测法处理冲突,当从哈希表中删除一个记录时,不应将这个记录的所在位置置空,因为这

会影响以后的查找。()

2.散列函数越复杂越好,因为这样随机性好,冲突概率小。()

3.Hash表的平均查找长度与处理冲突的方法无关。()

4.负载因子 (装填因子)是散列表的一个重要参数,它反映散列表的装满程度。()

5. 散列法的平均检索长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大。()

6.查找相同结点的效率折半查找总比顺序查找高。()

7.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。()

8. 在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,

而且与每块中元素个数有关。()

9.对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的。()

10.在查找树(二叉树排序树)中插入一个新结点,总是插入到叶结点下面。()

11.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。()

12. N个结点的二叉排序树有多种,其中树高最小的二叉排序树是最佳的。()

13. 在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二叉排序树与原二叉排序树相同。()

四、应用题

1.设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7,表长为10,用开放地址法的二次探测再散列方法解决冲突。要求:对该关键字序列构造哈希表,并计算查找成功时的平均查找长度。

2.对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8,采用线性探测再散列法解决冲突,

(1)设计哈希函数;(2)画出哈希表;(3)计算查找成功和查找失败的平均查找长度。

3.采用哈希函数H(k)=3*k mod 13并用线性探测法处理冲突,在散列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51

(1)构造哈希表;(2)计算查找成功和不成功的平均查找长度。

4.设哈希(Hash)表的地址范围为0~17,哈希函数为:H (K)=K MOD 16, K为关键字,用线性探测再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表,试回答下列问题:

(1) 画出哈希表示意图;

(2) 若查找关键字63,需要依次与哪些关键字比较?

(3) 若查找关键字60,需要依次与哪些关键字比较?

(4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

5.已知长度为11的表(xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon),按表中元素顺序依次插入一棵初始为空的二叉排序树中,画出插入完成后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

6.用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画出该树,并求在等概率情况下查找成功的平均查找长度。

7.一棵二叉排序树结构如下1-9,请标出各结点的值。

8.假定对有序表:进行折半查找,试回答下列问题:

(1)画出描述折半查找过程的判定树;

(2)若查找元素54,需依次与那些元素比较?

(3)若查找元素90,需依次与那些元素比较?

(4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。

第九章排序

一、选择题

1.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法称为()。

A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序

2.在待排序的元素序列基本有序的前提下,效率最高的排序方法是()。

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

3.在下列算法中,()算法可能出现下列情况,在最后一趟开始之前,所有的元素都不在其最终的位置上。

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

4.对记录的关键字为(50,26,38,80,70,90,8,30,40,20)进行排序,各趟排序结束时的结果为:其使用的排序方法是()。

50,26,38,80,70,90,8,30,40,20

数据结构第二章试题

第2章线性表 一、选择题 1. 链表不具备的特点是()。 A.可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是()。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是()。 ==NULL B. head->next==NULL >next==head !=NULL 4.带头结点的双循环链表L为空表的条件是()。 A.L==NULL B.L->next->==NULL C.L->prior==NULL >next==L 5.非空的循环链表head的尾结点(由P所指向)满足()。 A.p->next==NULL B.p==NULL C.p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是()。 A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间。 A.单链表 B.给出表头指针的单循环链表 C.双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点,故采用()存储方式最节省运算时间。 A.单链表 B.仅有头结点的单循环链表 C.双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是()。 A.单链表 B.静态链表 C.线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱,则采用()存储方式最节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()。 A.O(1) B.O(n) C.O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行()操作与链表的长度有关。A.删除单链表中的第一个元素 B.删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素,以下算法中,()在顺序表上实现比在链表上实现效率更高。A.输出第i(0<=i<=n-1)个元素值 B.交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素,算法(),在单链表上实现比在顺序表上实现效率更高。 A.删除所有值为x的元素 B.在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (2)算法指得就是()。 A)计算机程序???B)解决问题得计算方法 C)排序算法???D)解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得()。 A) 存储结构B) 逻辑结构C)算法D)操作 (4)从逻辑上可以把数据结构分为( )两大类。 A)动态结构、静态结构??B) 顺序结构、链式结构 C)线性结构、非线性结构???D)初等结构、构造型结构 (5)下列叙述中正确得就是()。 A)一个逻辑数据结构只能有一种存储结构 B)数据得逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是() ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为() i=0;s=0; while(s

数据结构试题及答案(免费)

一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度()。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的()。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为()。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。

数据结构第二章线性表测试题

第二章线性表 1、描述一下三个概念的区别:头指针,头结点,首元结点。并给予图示。 2、对于有头结点的单链表,分别写出定位成功时,实现下列定位语句序列。(1)定位到第i 个结点a i ; (2)定位到第i 个结点的前驱a i-1; (3)定位到尾结点; (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表,且P 结点既不是首元结点,也不是尾结点,试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点;(2)在P 结点前插入S 结点;(3)在表首插入S 结点;(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && jnext; j++;} p=head; while ( p ->next ) p=p->next; while ( p->next->next ) p=p->next; (1)s->next=p->next; p->next=s; (2)q =L ; whil e ( q ->next !=p ) q =q ->next;s->next=p 或 q ->next ; q ->next=s; (3 ) s->next=L ->next; L ->next=s; (4)q =L ; whil e ( q ->next !=NULL) q =q ->next;s->next= q ->next ; q ->next=s;

4、设计算法:在顺序表中删除值为e 的元素,删除成功,返回1;否则,返回0。 5、设计一个算法,将一个带头节点的数据域依次为a 1,a 2,…,a n (n ≥3)的单链表的所有节点逆置,即第一个节点的数据域变为a n ,…,最后一个节点的数据域为a 1。(注意:先用自然语言描述算法基本思想,然后用类C++语言描述) int Sqlist::DeleteElem( T e ) { for (i=1; i<=len g t h ; i ++) // 按值顺序查找 * i 可从0开始 if (elem[i-1]= =e) // 找到,进行删除操作 { for ( j=i; jnext; 4 LinkList* pri = NULL; //之前的节点 5 while(p){ 6 LinkList* q = new LinkList; 7 q->data = p->data; //把当前节点记录下来 8 q->next = pri; 9 pri = q; 10 head->next = q; 11 LinkList* t = p; //当前节点没用了删除掉 12 p=p->next; 13 delete(t); 14 } 15 }

《数据结构》题库及答案

《数据结构》题库及答案 一、选择题 1.线性表的顺序存储结构是一种 的存储结构,线性表的链式存储结构是一种 的存储结构。 a. 随机存储; b.顺序存储; c. 索引存取; d. HASH 存取 2.一个栈的入栈序列是a,b,c,d,e ,则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3.一个队列的入队序列是1,2,3,4,则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4.在一个单链表中,已知p 结点是q 结点的直接前驱结点,若在p 和q 之间插入结点s ,则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5.设有两个串p,q ,求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6.二维数组M 的成员是6个字符(每个字符占一个存储单元)组成的串,行下标i 的范围从0到8,列下标j 的范围从1到10,则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7.在线索二叉树中,结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8.在栈操作中,输入序列为(A ,B ,C ,D ),不可能得到的输出序列为:______ A 、(A , B , C , D ) B 、(D ,C ,B ,A ) C 、(A ,C ,D ,B ) D 、(C ,A ,B ,D ) 9.已知某二叉树的后序序列是dabec ,中序序列是debac ,则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10.设矩阵A 是一个对称矩阵,为了节省存储空间,将其下三角部分(见下图)按行序存放在一维数组B[1..n(n-1)/2]中,对任一上三角部分元素)(j i a ij ,在一维数组B 的存放位置是 。

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 1 ?在数据结构中,从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时,一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

数据结构试题及答案(10套最新)

单选题(每题2分,共20分) 1. 1. 对一个算法的评价,不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中,要向表头插入一个由指针 p 指向 的结点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分,共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时,称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行,删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时,假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表,在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3, 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时,其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时,应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构试题及答案

数据结构试题? 一、?单选题(每题 2 分,共20分) 1.1.???? 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2.???? 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时,其平均查找长度( B )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7.???? 若需要利用形参直接访问实参时,应将形参变量说明为( D )参数。 A.值 B.函数 C.指针 D.引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有 相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N(M: N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为

数据结构试题及答案

一、单选题(每题2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种( D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的(A)。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为(D )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为____O(1)_____,在表尾插入元素的时间复杂度为____O n________。

算法与数据结构题库与答案

一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ,表明该算法()。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述,不正确的是()。 A数据结构相同,对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来,起泡排序属于()。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是()。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4,则该队列可能的输出序列是()。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按()方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n( n≥ 0)个字符的有限()。其中,n是字符串的长度,表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中,每个数组元素占用 3 个存储单元,从首地址SA 开始按行连续存放。在这种情况下,元素A[8][5]的起始地址为()。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),则它的长度是()。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图,其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为()。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时,在等概率情况下,搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点(由p 所指向)满足()。 A p->link==NULL; B P==NULL;

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) 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) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为()、()、()和()。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。

数据结构第二章练习题 - 副本

《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是() A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是() A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是() A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是() A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点(由P所指向)满足() A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是() A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点,故采用()存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表

2017数据结构期末考试试题及答案

2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.

数据结构》期末考试试题及答案 1 单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列,在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构? ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io ), A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放A[1]中, 现进行二分查找,则查找 A [3]的比较序列的下标依次为( A. 1 , 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 8. 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O (1) B. O (n ) C. O ( 1 og 2n ) D. O (n2) 9. 对于线性表( 7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选 用 H (K )=K %9 作为散列函数,则散列地址为 1 的元素有( )个, 位置在 676(10),每个元素占一个空间, 表示用 10 进制表示。 问 A[3][3] (10)存放在什么位置?脚注 (10) 5. A .688 B .678 C . 692 D . 696 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 ( ). A .2-1 B.2K+1 C.2K-1 D. 2k-1 7.

数据结构试题及答案修2

试卷一 一、单选题(每题 2 分,共20分) 1. 对一个算法的评价,不包括如下()方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 7. 若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的()。 A.行号B.列号C.元素值D.非零元素个数 二、填空题(每空1分,共28分) 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N(M:N)的联系时,称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行,删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树,其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为_____________个,其中_______________个用于指向孩子,_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维数组A中,即编号为0的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为________,右孩子元素为

数据结构期末考试试题及答案

贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为()。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为()。 for(i=n-1;i>=0;i--) for(j=0;jnext; p->next= Q.rear->next; (D)、p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于() (A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和 (C)、各叶子结点的带权路径长度之和(D)、根结点的值 10.线索二叉链表是利用()域存储后继结点的地址。 (A)、lchild (B)、data (C)、rchild (D)、root 二、填空题

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i

相关文档 最新文档