《数据结构》复习题.docx

《数据结构》复习题.docx

《《数据结构》复习题.docx》由会员分享，可在线阅读，更多相关《《数据结构》复习题.docx（62页珍藏版）》请在冰点文库上搜索。

《数据结构》复习题

一、选择题（每题2分，共20分）

1．单链表的一个存储结点包含（　D　）。

A．数据域或指针域

B．指针域或链域

C．指针域和链域

D．数据域和指针域

2.线性表是具有n个（C）的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项

3．对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B）为标准操作来考虑。

A．条件判断B．结点移动C．算术表达式D．赋值语句

4．循环链表主要优点是（D）

A．不再需要头指针了

B．已知某个结点的位置后，能够容易找到它的直接前趋

C．在进行插入、删除运算时，能更好地保证链表不断开

D．从表中任一结点出发都能扫描到整个链表

5．栈和队都是（C）

A．顺序存储的线性结构B.链式存储的非线性结构

C．限制存取点的线性结构D．限制存取点的非线性结构

6．下列哪一种图的邻接矩阵是对称矩阵（B）

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

7.二维数组A[6][8]采用行优先的存储方法，若每个元素各占10个存储单元，且第1个元素的A[0][0]地址为1000，则元素A[4][7]的地址为（B）

A.1282B.1390C.1270D.1276

8.在深度为6的完全二叉树中（D）

A.最少有31个结点，最多有64个结点

B.最少有32个结点，最多有64个结点

C.最少有31个结点，最多有63个结点

D.最少有32个结点，最多有63个结点

9．具有n个顶点的连通图至少有（A）条边。

A.n-1B.nC.n+1D.2n

10．具有3个结点的二叉树的有（B）种不同形态。

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

二、填空题（每空2分，共30分）

1.通常从__正确性_、_可读性_、__健壮性_、__高效性__等几方面评价算法的（包括程序）的质量。

2.程序段“for（i=l;i<=n;i++）{k++;for（j=1;j<=n;j++）L+=k;}”的时间复杂度T（n）=__O（n2）__。

3.在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（rear-front+m）%m。

4.在有n个结点的二叉链表中，值为非空的链域的个数为n-1。

5.组成串的数据元素只能是字符，则INDEX（‘DATASTRUCTURE’，‘STR’）的值为5。

6.一个n*n的对称矩阵，如果以行或列为主主序存入内存，则其存储容

为n*（n+1）/2。

7.由权值分别为7，19，2，6，32,3,21,10的叶子结点生成一棵哈夫曼树，它的树高是6，带权路径长度为261。

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

9.n个顶点的无向完全图中含边的数目为n*（n-1）/2。

10.含有n个记录的表在等概率情况下顺序查找成功的平均查找长度为（n+1）/2。

三、问答题（共30分）

3.（4分）写出有向图的所有拓扑排序序列。

解：

（1）ABCDEG

（2）ABCEDG

4.（4分）请画出与下列森林对应的二叉树。

5.（8分）已知一个无向图的邻接表如下图所示。

（1）画出该图的图形；（2分）

（2）求出每个顶点的度；（2分）

（3）根据邻接表从顶点V1出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

（4分）

6.（4分）连通网络如图所示。

试按（顶点1，顶点2，权值）的格式，应用克鲁斯卡尔算法给出在构造最小生成树过程中顺序选出的各条边。

（顶点1，顶点2，权值）

（1,3,1）

（4,6,2）

（2,5,3）

（3,6,4）

（2,3,5）

四、算法填空题（每空2分，共10分）

１.请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。

voiddemo2（LinkListhead,ListNode*p）

{//head是带头结点的单链表，删除P指向的结点

ListNode*q=head；

while（q&&

（1）q->next!

=p）q=q->next；

if（!

q）Error（“*pnotinhead”）;

（2）q->next=p->next；

（3）free（p）；}

2.假设称正读和反读相同的字符序列为“回文”，例如，‘abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。

下面算法是判别读入一个以‘@’为结束符的字符序列是否是“回文”。

intPalindrome_Test（）

{

InitStack（S）;InitQueue（Q）;

while（（c=getchar（））!

='@'）

{

（4）Push（S,c）;EnQueue（Q,c）;

}

while（!

StackEmpty（S））

{

Pop（S,a）;（5）DeQueue（Q,b）;

if（a!

=b）returnERROR;

}

returnOK;

}

承诺：

我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。

专业班级学号学生签名：

华东交通大学2010—2011学年第一学期考试卷

得分

评阅人

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

1.计算机算法指的是（）。

A．计算方法B.排序方法

C.解决问题的步骤序列D.调度方法

2．算法的计算量的大小称为计算的（）。

A．效率B.复杂性C.现实性D.难度

3.在下面的程序段中，对x的赋值语句的频度为（）

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）

4.线性表是具有n个（）的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项E．信息项

5.在单链表指针为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;

6.在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。

A．（front-rear+1）%mB.（rear-front+1）%m

C．（front-rear+m）%mD.（rear-front+m）%m

7.栈和队都是（）

A．顺序存储的线性结构B.链式存储的非线性结构

C.限制存取点的线性结构D.限制存取点的非线性结构

8.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。

A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b

9.广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（）。

Head（Tail（Head（Tail（Tail（A）））））

A.（g）B.（d）C.cD.d

10．在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。

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

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

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

12.在有n个结点的二叉链表中，值为非空的链域的个数为（）

A．n-1B．2n-1C．n+1D．2n+1

13.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

A.24B.71C.48D.53

14．下列哪一种图的邻接矩阵是对称矩阵（）

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

15.采用顺序查找方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。

A.nB.n/2C.（n-1）/2D.（n+1）/2

得分

评阅人

二、填空题（每题2分，共20分）

1.数据结构中评价算法的两个重要指标是空间复杂度和时间复杂度。

2.一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_n-i+1_____个元素。

3.链接存储的特点是利用指针来表示数据元素之间的逻辑关系。

4.INDEX（‘DATASTRUCTURE’，‘STR’）=5

5.两个字符串相等的充分必要条件是每个位子对应字符相同。

6.一棵具有257个结点的完全二叉树，它的深度为8+1=9。

7.一棵完全二叉树有900个结点，则共有450　个叶子结点。

8.由一棵二叉树的前序序列和　中序遍历　唯一确定这棵二叉树。

9.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={（a,b）,（a,d）,（a,c）,（d,c）,（b,e）}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度遍历方法。

10.对于一个具有n个顶点和e条边的连通图，其生成树的边数为n-1。

得分

评阅人

四、应用题（每题8分，共4０分）

１.请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。

（8分）

　　　　voiddemo2（LinkListhead,ListNode*p）

{//head是带头结点的单链表，删除P指向的结点

ListNode*q=head;

while（q&&）q=q->next;（2分）

if（!

q）Error（“*pnotinhead”）;

；（3分）

；（3分）

}

2.已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出与其对应的二叉树并中序线索化（6分），并给出这棵二叉树的后序遍历序列（2分）。

3．将下面的森林变换成二叉树（8分）。

4．已知带权无向图，求解下列问题：

1）写出它的邻接矩阵。

（2分）

2）用普里姆算法求出最小生成树，要求从顶点1出发，并给出在构造最小生成树过程。

（6分）

解：

邻接矩阵为：

最小生成树为：

5.下图所示的AOE网络

（1）给出全部的拓扑排序。

（2分）

（2）这个工程最早可能在什么时间结束和关键路径。

（3分）

（3）求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。

（3分）

解：

（1）拓扑排序：

（2）

此工程最早完成时间为　　　　　　，

关键路径为　　　　　　　　　　　　　　　　　　　　　　　　。

事件代号

①

②

③

④

⑤

⑥

Ve

Vl

（3）填写下图

得分

评阅人

四、算法设计题（共1０分）

1.编写递归算法，计算二叉树中叶子结点的数目。

已知二叉树抽象数据类型为：

TypedefStructBiTNode{

intdata;structnode*lchild,*rchild;}BiTNode,*BiTree;

《数据结构与算法》复习题

一、选择题。

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．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系

C．分析算法的效率以求改进C．分析算法的易读性和文档性

（2）A．空间复杂度和时间复杂度B．正确性和简明性

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

8．下面程序段的时间复杂度是O（n2）。

s=0;

for（I=0;i

for（j=0;j

s+=B[i][j];

sum=s;

9．下面程序段的时间复杂度是O（n*m）。

for（i=0;i

for（j=0;j

A[i][j]＝0;

10．下面程序段的时间复杂度是O（log3n）。

i＝0；

while（i<=n）

i=i*3；

11．在以下的叙述中，正确的是B。

A．线性表的顺序存储结构优于链表存储结构

B．二维数组是其数据元素为线性表的线性表

C．栈的操作方式是先进先出

D．队列的操作方式是先进后出

12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B。

A．数据元素具有同一特点

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

C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等

13．链表不具备的特点是A。

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

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

14．不带头结点的单链表head为空的判定条件是A。

A．head==NULLBhead->next==NULL

C．head->next==headDhead!

=NULL

15．带头结点的单链表head为空的判定条件是B。

A．head==NULLBhead->next==NULL

C．head->next==headDhead!

=NULL

16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用

D存储方式最节省运算时间。

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

17．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是B。

A．单链表B．静态链表C．线性链表D．顺序存储结构

18．非空的循环单链表head的尾结点（由p所指向）满足C。

A．p->next==NULLB．p==NULL

C．p->next==headD．p==head

19．在循环双链表的p所指的结点之前插入s所指结点的操作是D。

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->prior->next=s

D．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s

20．如果最常用的操作是取第i个结点及其前驱，则采用D存储方式最节省时间。

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

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

A．O

（1）B．O（n）C．O（n2）D．O（nlog2n）

22．在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行B操作与链表的长度有关。

A．删除单链表中的第一个元素

B．删除单链表中的最后一个元素

C．在单链表第一个元素前插入一个新元素

D．在单链表最后一个元素后插入一个新元素

23．与单链表相比，双链表的优点之一是D。

A．插入、删除操作更简单

B．可以进行随机访问

C．可以省略表头指针或表尾指针

D．顺序访问相邻结点更灵活

24．如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用B。

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

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

C．非循环双链表

D．循环双链表

25．在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：

A。

A．n–i+1B．n–iC．iD．i–1

26．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为C。

A．顺序表B．用头指针表示的循环单链表

C．用尾指针表示的循环单链表D．单链表

27．下述哪一条是顺序存储结构的优点？

C。

A插入运算方便B可方便地用于各种逻辑结构的存储表示

C存储密度大D删除运算方便

28．下面关于线性表的叙述中，错误的是哪一个？

B。

A线性表采用顺序存储，必须占用一片连续的存储单元

B线性表采用顺序存储，便于进行插入和删除操作。

C线性表采用链式存储，不必占用一片连续的存储单元

D线性表采用链式存储，便于进行插入和删除操作。

29．线性表是具有n个B的有限序列。

A．字符B．数据元素C．数据项D．表元素

30．在n个结点的线性表的数组实现中，算法的时间复杂度是O

（1）的操作是A。

A．访问第i（1<=i<=n）个结点和求第i个结点的直接前驱（1

B．在第i（1<=i<=n）个结点后插入一个新结点

C．删除第i（1<=i<=n）个结点

D．以上都不对

31．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为C。

A．O（0）B．O

（1）C．O（n）D．O（n2）

32．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为C。

A．O（n）O（n）B．O（n）O

（1）C．O

（1）O（n）D．O

（1）O

（1）

33．线性表（a1,a2,…,an）以链式方式存储，访问第i位置元素的时间复杂度为C。

A．O（0）B．O

（1）C．O（n）D．O（n2）

34．单链表中，增加一个头结点的目的是为了C。

A．使单链表至少有一个结点B．标识表结点中首结点的位置

C．方面运算的实现D．说明单链表是线性表的链式存储

35．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是B。

A．p->next=s；s->next=p->nextB．s->next=p->next；p->next=s;

C．p->next=s；p->next=s->nextD．p->next=s->next；p->next=s

36．线性表的顺序存储结构是一种A。

A．随机存取的存储结构B．顺序存取的存储结构

C．索引存取的存储结构D．Hash存取的存储结构

37．栈的特点是B，队列的特点是A。

A．先进先出B．先进后出

38．栈和队列的共同点是C。

A．都是先进后出B．都是先进先出

C．只允许在端点处插入和删除元素D．没有共同点

39．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是C。

A．edcbaB．decbaC．dceabD．abcde

40．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。

下列C是不可能的出栈序列。

A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A

41．以下B不是队列的基本运算？

A．从队尾插入一个新元素B．从队列中删除第i个元素

C．判断一个队列是否为空D．读取队头元素的值

42．若已知一个栈的进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为C。

A．iB．n－iC．n－i＋1D．不确定

43．判定一个顺序栈st（最多元素为MaxSize）为空的条件是B。

A．st->top!

=-1B．st->top==-1

C．st->top!

=MaxSizeD．st->top==MaxSize

44．判定一个顺序栈st（最多元素为MaxSize）为满的条件是D。

A．st->top!

=-1B．st->top==-1

C．st->top!

=MaxSizeD．st->top==MaxSize

45．一个队列的入队序列是1，2，3，4，则队列的输出序列是B。

A．4，3，2，1B．1，2，3，4

C．1，4，3，2D．3，2，4，1

46．判定一个循环队列qu（最多元素为MaxSize）为空的条件是C。

A．qu->rear–qu->front==MaxSizeB．qu->rear–qu->front-1==MaxSize

C．qu->rear==qu->frontD．qu->rear=qu->front-1

47．在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是C。

A．front==rear+1B．rear==front+1C．front==rearD．front==0

48．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行D操作。

A．h->next=s ;B．s->next=h ;

C．s->next=h ;h=s ;D．s->next=h->next ;h->next=s ;