数据结构复习题2013新版
数据结构各章复习资料
数据结构
复习参考题资料
计算机科学与技术专业
2013.7
数据结构各章复习资料
第一章 绪论
一、选择题:
1、在数据结构的讨论中把数据结构从逻辑上分为( C )。
A、 B、静态结构与动态结构
C、线性结构与非线性结构 D、紧凑结构与非紧凑结构
2、下面程序段的时间复杂度为( C )。
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
a[i][j]=i*j;
A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)
3、执行下面程序段时，执行S语句的次数为( D )。
for(int i=1;i<=n;i++)
for(int j=1; j<=i;j++)
S;
A、n2 B、n2/2 C、n(n+1) D、n(n+1)/2
,、某算法的时间代价为T(n)=100n+10nLog2n+n2+10，其时间复杂度为(C)。
A、O(n) B、O(nlog2n) C、 O(n2) D 、O(1)
二、填空题
,、数据结构的抽象数据类型ADT可用三元组表示(D，S，P)，其中D是(数据对象)，S是( 关系集 )，P是( 操作集 )。
,、数据的基本单位是( 数据元素 ),最小单位是( 数据项 )。
3、一个算法的时间复杂性通常用它的( T(n)=O(F(n)) )形式表示，当一个算法的时间复杂性与问题的规模n大小无关时，则表示为( O(1) );成正比时，则表示为( O(n) ) ;成对数
2关系时，则表示为(O(log2n) );成平方关系时，则表示为( O(n) )。
4、我们常常称数据的逻辑结构为数据结构，数据的逻辑结构有两类:(线性结构)， (非线性结构 )。
5、一个算法应该具有(有穷性)、(确定性)、(可行性 )、( 零个或多个输入 )、(一个或多个输出 )五个特征。
6、数据结构中的逻辑结构具体分为四种分别是(线性结构)(树型结构)(图或网型结构)(集合)。
7、数据结构中的存储结构具体分为二种分别是(顺序存储结构)(链式存储结
构)。
三、简答题
1、比较顺序存储结构和链式存储结构的优缺点,
参考答案:
1)顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。
它的优点是:
数据结构各章复习资料
(1)方法简单，各种高级语言中都有数组，容易实现。
(2)不用为表示节点间的逻辑关系而增加额外的存储开销。
(3)顺序表具有按元素序号随机访问的特点。
缺点:
(1)在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。
(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置;预先分配过小，又会造成溢出。
2)在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。
链表的最大特点是:
插入、删除运算方便。
缺点:
(1)要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。
(2)链表不是一种随机存储结构，不能随机存取元素。
3)顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢,通常有以下几点考虑:
(1)顺序表的存储空间是静态分配的，在程序执行之前必须明确
规定
关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定
它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要 但在链表中，除数据域外海需要在每个节点上附加指针。如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。当顺序表被填满时，则没有结构开销。在这种情况下，顺序表的空间效率更高。由于设置指针域额外地开销了一定的存储空间，从存储密度的角度来讲，链表的存储密度小于1.因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。
(2)基于运算的考虑(时间)
顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1).而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺表优于链表。
反之，在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的;在链表中作插入、删除，虽然要找插入位置，但操作是比较操作，从这个角度考虑显然后者优于前者。
(3)基于环境的考虑(语言)
顺序表容易实现，任何高级语言中都有数组类型;链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。
总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表，即主要操作是查找操作的线性表，适于选择顺序存储;而频繁做插入删除运算的(即动态性比较强)的线性表适宜选择链式存储。
数据结构各章复习资料
2、评价一个算法的好坏的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
是什么,
由于针对一个问题可能会有不同的算法去解决，不同的算法思路不同，有的执行速度很慢，效率低;有的执行速度很快，效率自然会很高。这样也就出现了算法的“好”与“坏”之分，如何衡量一个算法的好坏，通常要从以下几个方面来分析。
1)正确性
算法能满足具体问题的需求，即对任何合法的输入算法都会得出正确的结果。
2)可读性
算法创建后由人来阅读、理解、使用以及修改。所以可读性的好坏直接影响到算法的好坏。如果一个算法涉及的想法很多，就会给阅读的人造成困难，那么这个算法就不能得到更好的交流和推广，更不便于对算法进行修改、扩展和维护。所以要提高算法的可读性，就要做到简明易懂。
3)健壮性
一个程序完成后，运行该程序的用户对程序的理解各有不同，并不能保证每一个人都能按照要求进行输入，健壮性就是指对非法输入的抵抗能力，当输入的数据非法时，算法能识别并做出处理，而不会因为输入的错误产生错误动作或造成瘫痪。
4)时间复杂度与空间复杂度
时间复杂度简单地说就是算法运行所需要的时间。不同的算法具有不同的时间复杂度，当一个程序较小时感觉不到时间复杂度的重要性，当一个程序特别大时便会察觉到时间复杂度的重要性。所以如何写出更高速的算法一直是算法不断改进的目标。空间复杂度是指算法运行所需的存储空间，随着计算机硬件的发展，空间复杂度已经显得不再那么重要。
数据结构各章复习资料
第二章 线性表
一、选择题
1(线性表是( A ) 。
A、 一个有限序列，可以为空; B、一个有限序列，不能为空;
C、一个无限序列，可以为空; D、一个无序序列，不能为空。
2(对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的(A)个元素。
A、 n/2 B、(n+1)/2 C、(n -1)/2 D、 n
3(线性表采用链式存储时，其地址( D ) 。
A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续与否均可以
4(用链表表示线性表的优点是( C )。
A、便于随机存取 B、花费的存储空间较顺序存储少
C、便于插入和删除 D、数据元素的物理顺序与逻辑顺序相同
5、某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。
A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表
6、循环链表的主要优点是( D ) 。
A、不在需要头指针了
B、已知某个结点的位置后，能够容易找到他的直接前趋
C、在进行插入、删除运算时，能更好的保证链表不断开
D、从表中的任意结点出发都能扫描到整个链表
7、下面关于线性表的叙述错误的是( B )。
A、线性表采用顺序存储，必须占用一片地址连续的单元;
B、线性表采用顺序存储，便于进行插入和删除操作;
C、线性表采用链式存储，不必占用一片地址连续的单元;
D、线性表采用链式存储，便于进行插入和删除操作;
8、单链表中，增加一个头结点的目的是为了( C )。
A、使单链表至少有一个结点 B、标识表结点中首结点的位置
C、方便运算的实现 D、说明单链表是线性表的链式存储
9、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( D )存储方式最节省运算时间。
A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表
10、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用(B )存储方式最节省运算时间。
A、 单链表 B、顺序表 C、 双链表 D、单循环链表
11、链表不具有的特点是( A )。
,、可随机访问任一元素 ,、插入删除不需要移动元素
,、不必事先估计存储空间 ,、所需空间与线性表长度成正比
12、在一个有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为( B ) 。
A、O(1) B、O(n) C、O(n2) D、O(log2n)
13、在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行( D )。
数据结构各章复习资料
A、 HL=p;p->next=HL; B、 p->next=HL; HL=p;
C、 p->next=HL; p=HL; D、 p->next=HL->next;HL->next=p;
14、在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结 点，则执行( D )。
A 、q->next=p->next;p->next=q; B、 p->next=q->next;q=p;
C 、q->next=p->next;p->next=p D、 p->next=q->next;q->next=p;
15、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( D )。
A、 p=q->next;p->next=q->next; B、 p=q->next;q->next=p;
C、 p=q->next;p->next=q; D、 q->next=q->next->next;
16、给定有n个元素的向量，建立一个有序的单链表的时间复杂度为( C )。
2A、O(1) B、O(n) C、O(n) D、O(nlog2n)
17、不带头结点的单链表first为空的判定条件是( A )。
A、first==NULL B、first->next==NULL C、first->next==first D、first!=NULL
18、在非空的循环双链表中q所指的结点前插入一个由p所指结点的过程依次为:
p->next=q; p->prior=q->prior; q->prior=p;和( C )。
A、q->next=p ,、q->prior->next=p ,、p->prior->next=p ,、p->next->prior=p
19、线性表的链式存储结构与顺序存储结构相比优点是( D )。
A、所有的操作算法实现简单 B、便于随机存储
C、不便于插入与删除 D、便于利用零散的存储空间
20、在双向链表存储结构中,删除P所指向的结点时须修改指针( A )。
A、P->next->prior=P->prior P->prior->next=P->next
B、P->next=P->next->next P->next->prior=P
C、P->prior->next=P P->prior=P->prior->prior
D、P->prior=P->next->next P->next=P->prior->prior
21、向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动(B) 个元素。
A、8 B、63.5 C、63 D、7
22、在一个长度为n的顺序存储的线性表中，向第i个元素(1?i?n+1)之前插入一个新元素时，需要从年向前依次移(B )个元素。
A、n-i B、n-i+1 C、n-i-1 D、i
二、填空题
1、带头结点的单链表H为空的条件是( H->next==NULL )。
2、非空单循环链表L中*p是尾结点的条件是( p->next==L )。
3、在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=( p->next );和p->next=( f )的操作。
4、在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作:
s->next=( p->next );
p->next=s;
t=p->data;
p->data=( s->dada );
s->data=( t );
5(在顺序表中做插入操作时首先检查( 插入位置是否合理 )。
6、顺序表、链表分别通过( 存储的相对位置 )、( 指针)体现元素的逻辑关系。
数据结构各章复习资料
7、线性链表中指针的作用是(表示逻辑关系)。
8、在顺序表中，插入或者删除一个元素，需要平均移动(一半 )个元素，具体移动的元素个
数与(插入与删除的位置有关)有关。
9、顺序表中逻辑上相邻的元素的物理位置(一定)紧邻。单链表中逻辑上相邻的元素的物理
位置(不一定 )紧邻。
10、在单链表中，除了首元结点外，任一结点的存储位置由(前趋结点的指针域 )指示。
11、有一个单链表(不同结点的data域可能相等)，其头指针为head,编写一算法计算数据
域为x的结点的个数，请填空。
int count(LinkList head ,ElemType x)
{ Node *p;
int n=0;
( p=head->next );
While (p!=NULL)
{ if( (p->data==x) )
n++;
( p=p->next );}
return n;}
12、单链表的逆置，请填空
void insert(LikList L)
{Node *p,*q,*r;
p=head;
( q=p->next或q=head->next );
while(q!=NULL)
{r=q->next;
( q->next=p );
p=q;
q=r;
} head->next=NULL;head=p; }
三、判断题
1、双循环链表中，任一结点的后继指针均指向其逻辑后继。 (F)
2、线性表的逻辑顺序与存储顺序总是一致的。(F)
3、顺序存储的线性表可以按序号随机存取。(T)
4、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 (F)
5、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(T)
6、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(F)
7、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(T)
8、线性表的链式存储结构优于顺序存储结构。(F)
9、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(T)
10、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(T)
11、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(F)
数据结构各章复习资料
四、操作题
1、下面算法调用方式为unknown(rear);说明该算法的功能，若输入数据为ABCDE回车，
画出该算法所得到的存储结构。
void unknown(LinkList &rear ){
LinkList head，s;
DataType ch;
rear=head=(ListNode *)malloc(sizeof(ListNode));
head->next=head;
printf("输入数据以回车键结束～\n");
while((ch=getchar())!=„\n?){
s=(LNode *)malloc(sizeof(LNode));
s->data=ch;
s->next=rear->next;
rear->next=s;
rear=rear->next;
}
rear->next=head->next;
free(head); }
参考答案:
rear
2、下面算法调用方式为Unknown(root);说明该算法的功能，若输入数据为
AB#CD##EF####
回车，画出该算法所得到的存储结构。
void Unknown(BiTree &T){
char ch;
==„#?) T=NULL; if((ch=getchar())
else{T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;
Unknown(T->lchild); Unknown(T->rchild);}
}
参考答案:
数据结构各章复习资料
3、已知线性链表元素为字符(‘A’，‘B’，‘C’，‘D’，‘E’，’F’)，说明下面
算法的功能，并
画出该算法处理后所得到的存储结构。
void Unknown(LinkList &head)//head为链表的表头指针
{LinkList p，s;
p=head->next;
while(p->next){
s=p->next;
if(s->data%2==1)p=p->next;
else{
p->next=s->next;
free(s);
}
}//end of while }
参考答案:将单链表中ASCII码为偶数的结点删除。
4、设单链表的结点的结构为ListNode=(data,link)，阅读下面的函数，指出它所
实现的
功能是什么。
Int unknown(ListNode *Ha)
{
Int n=0;
ListNode *p=Ha->link;
While(p)
{
n++;
p=p->next;
}
Return (n);
}
参考答案:计算单链表的长度或计算单链表的结点的个数。
5、假定p1和p2是两个单链表的表头指针，用来表示两个集合，单键表中的结点包括值域 data和指向后继的结点的指针域link，试根据下面的算法指出算法的功能。
int SS(ListNode *p1,ListNode *p2)
{ ListNode r;
while(p2!=NULL)
{ r=p1;
while(r!=NULL)
{if(p2->data==r->data) break;
r=r->link;
}
if(r==NULL) return 0;
P2=p2->link;
}
return 1;}
参考答案:判断P2单链表所代表的集合是否为P1单链表所代表的集合的子集，若是则返
回1，否则返回0。
数据结构各章复习资料
五、算法题
,、已知两个单向链表A=(a，b，((((((，c);B=(d，e，((((((，f)，
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
算法
void MergeList(LinkList &A，LinkList B)，实现将两个链表合并为一个单向链表 A=(d，e，(((((，f，c，(((((，b，a)，其中A，B为两个链表的表头指针，小写字母为表中元素。
void merger(LinkList *A ,LinkList B){}
参考答案:
void MergrList(LIstList &A,LinkList B)
{ for (R=B;R->next;R=R->next);
P=A->next
while(P)
{ S=P;P=P->next;
S->next=R->next;
R->next=S;
}
A=B;
}
,、假定在一个带头结点的单链表L中所有结点的值按递增顺序排列，试写下
面的函数，功 能是删除表L跌所有的值大于等于min，同时小于等于max的结
点。
单链表的结构定义如下:
void rangeDelete(ListNode *L,ElemType min,ElemType max){}
参考答案:
void rangeDelete(ListNode *L,ElemType min,ElemType max)
{ listNode *q=L,*p=L->next;
while(p!=NULL)
{if(p->data>=min&&p->data<=max)
{ q->next=p->next;free(p);p=q->next;
}
else {q=p;p=p->next;}}}
3、线性顺序表及链表就地逆置算法.
int revSqList(SqList *L){} int revLinkList(LinkList L){}
参考答案:
int revSqList(SqList *L)
{ int i;
ElemType temp;
for(i=0;i<L->length/2;i++)
{ temp=L->elem[i];
-i]; L->elem[i]=L->elem[L->length-1
L->elem[L->length-1-i]=temp;}
return OK;}
int revLinkList(LinkList L)
{ LinkList P,Q;
P=L->next;
数据结构各章复习资料
if(L->next&&P->next)
{ Q=P->next;
P->next=NULL;
while (Q)
{ P=Q;
Q=Q->next;
P->next=L->next;
L->next=P;}
}return OK;}
4、设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归
并成一个按元素
值递增有序的单链表C，并要求辅助空间为O(1)。
LinkList MergeList_L(LinkList La,LinkList Lb) {}
参考答案:
LinkList MergeList_L(LinkList La,LinkList Lb)
{ LinkList Lc,pa,pb,pc;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while(pa&&pb)
{ if (pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else
{pc->next=pb;pc=pb;pb=pb->next;}}
pc->next=pa?pa:pb;
free(Lb);
return La;}
5、已知一个的链表A，表中元素为整数，设计算法把表中的所有的负整数排列在所有非负
整数之后。
void Divide(LinkList *A){}
参考答案:
void Divide(LinkList *A)
{ P=A->next;q=A;
while(p)
{ if(p->data>=0)
{ q->next=p->next;
p->next=A->next;
A->next=p;
P=q->next;
}
else{ q=p;p=p->next;}
}
}
数据结构各章复习资料
第三章 栈与队列
一、选择题
1、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列( C )。
A、 1，3，2，4 B、2，3，4，1 C、 4，3，1，2 D、3，4，2，1
2、将一个递归算法改为对应的非递归算法时，通常需要使用( A )。
A、 栈 B、 队列 C、 循环队列 D、优先队列
3、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
是( C )。
A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2
C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的
栈底位置为n/2
4、 在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以top 作为栈顶指针，则作退栈操作时，top的变化是( A )。
A、top =top -1 B、top = top +1 C、top 不变 D、top不确定
5、 链栈和顺序栈相比较，有一个明显的特点是( A )。
A、链栈通常不会出现栈满的情况 B、链栈通常不会出现栈空的情况
C、链栈的插入操作更加方便 D、链栈的删除操作更加方便。
6、 在一个链队中，假设f和r分别为队首和队尾指针，删除一个结点的运算是( C )。
A、r = f —>next B、r = r —>next C、f = f —>next D、f = r —>next
7、 向一个栈顶指针为top的链栈中插入一个s 所指结点时，其操作步骤是( B )。
A、top —>next = s B、s —>next = top ; top = s;
C、s —>next =top —>next; top —>next = s;
D、s —>next =top ; top = top —>next
8、栈的插入与删除操作在 ( A ) 进行。
A、 栈顶 B 、栈底 C、 任意位置 D、 指定位置
9、当利用大小为N的数组顺序存储一个队列时，该队列的最大长度为 ( B )。
A、 N-2 B 、N-1 C、 N D、 N+1
10、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空指针的条件为(D )。
A、f+1==r B、 r+1==f C、 f==0 D、 f==r
11、在系统实现递归调用时需利用递归工作记录保存( C )，当递归调用结束时通过它将控 制转到上层调用程序。
A、调用地址 B、递归入口 C、返回地址 D、递归出口
12、设栈的输入序列是1,2,3,4,,n若输出序列的第一个元素是n,则第i个输出元素( B)。
A、不确定 B、n-i+1 C、i D、n-i
二、填空题
1、已知顺序存储的循环队列中，front，rear分别为队头、队尾指针，MAX为队列中存储单 元的最大个数，若当队列中仅有一个空闲单元时视为队满，则队满条件为
((rear+1)%MAX==front );一般情况下，队列中元素个数可表示为
数据结构各章复习资料
( (rear-front+MAX)%MAX )。
2、已知元素入栈先后为ABCDE，若C为第一个出栈元素，则下一个出栈的元素可能是 ( B 、D 、 E )。
3、已知仅设尾指针的单循环链表rear(指针域为next)表示队列，链表前端为队头，则结 点*s入队的语句依次为( s->next=rear->next );( rear->next=s );rear=rear->next;
4、已知仅设尾指针rear的无头结点的单循环链表(指针域为next)表示栈，
链表前端为 栈顶，则结点*new进栈的语句依次为(new->next=rear->next );( rear->next=new ); (rear=new);
5、 在对栈的操作中，其插入和删除都是在栈的( 同一端 )进行的，所以导致后进栈的元 素必定先被删除，也就是说，栈的修改是按照( 后进先出 )的原则进行的，所以栈又称为 ( LIFO )表。
6、 在队列的操作中，其插入和删除工作是在表的两端进行的，它允许在表的一端进行插入， 一端进行删除，则允许插入的一端称为(队尾 )，允许删除的一端称为( 队首 )， 先进入队列的成员必定先离开队列，所以队列又称为( FIFO )表。
7、向一个栈顶找针为HS的链栈中插入一个S所指的结点时，则执行( S->next=HS;HS=S; )。
8、在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列 的初始化时均应该设置为( 0 )，当对队列进行插入和删除的操作后，如果头指 针和尾指针相等时，队列为( 空 )。
9、 向栈中压入元素的操作是(压栈 )。对栈进行出栈时的操作是( 出栈 )。
10、在具有n个存储单元的队列中，队满时队中共有( n-1 )个元素。
11、假设有一个顺序栈A，其中元素a1,a2,a3,a4,a5,a6依次进栈，如果已知六个元素出栈 的顺序是a2,a3,a4,a6,a5,a1,则此栈容量至少应该为( 3 )。
12、 线性表、栈和队列都是( 线性结构 )结构，可以在线性表的( 任意 )位置上插入和删除。
13、判断单链表是否对称，对称返回1，否则返回0，请填空。
int xyz(LinkList L)
{
Node *p,*q;
int n1,n,i,x;
Stack s;
P=L->next;
q=p;
n=0;
while(q!=NULL)
{
n++;
q=q->next;
}
n1=( n/2 );
for(i=1;i<=n1;i++)
{
push(s,p->data);
( p=p->next );
}
数据结构各章复习资料
if( (n%2!=0) )
p=p->next;
while(p!=NULL)
{
pop(s,x);
if (p->data!=x) break;
( p=p->next );
}
if ( p==NULL 或!p ) return 1;
else return 0;
}
三、判断题
1、栈与队列都是限制存取点的表，只是它们的存取特征不一样。(T)
2、在链队列中，即使不设置尾指针也能进行入队操作。(T)
3、递归调用算法与相同的功能的非递归算法相比，主要问题在于重复计算太
多，而且本 身需要分配额外的空间和传递数据和控制，所以时间与空间开销通
常都比较大。(T)
4、链式栈与顺序栈的相比，一个明显的优点是通常不会出现栈满的情况。(T)
四、操作题
1、写出下列程序的运行结果。
main()
{Stack S;
char x,y;
S.InitStack();
X=?c?;y=?k?;
S.Push(x);S.Push(,a?);S.Push(y);
S.Pop(S,x);S.Push(,t?);S.Push(,s?);
while(!S.IsEmpty())
{ S.Pop(S,x);
printf(“%c”,x);}
printf(“%c”,y);
}
参考答案:stack
2、请写出下列算法的功能。
Void unknown(Queue &Q)
{ Stack S;
int d;
S.InitStack();
while(!Q.IsEmpty())
{Q.DeQueue(d);S.Push(d);
}
while(!S.IsEmpty())
{S.Pop(d);Q.EnQueue(d);}}
数据结构各章复习资料
参考答案:利用栈，将队列中的元素逆置。
五、算法题
1、请分别写出在循环队列上进行插入与删除操作的算法。
循环队列的结构定义如下:
Struct CyclicQueue
{ElemType elem[M] //M为已定义过的整型常量，表示队列的长度
Int rear,front;//rear指向队尾元素的后一个位置，front指向队头元素
Int tag;//当front=rear且tag=0时，队列空。当front=rear且tag=1，队列满。
};
Bool EnCQueue(CyclicQueue *Q ,ElemType x){}
Bool DelCQueue(CyclicQueue *Q,ElemType x){}
参考答案:
Bool EnCQueue(CyclicQueue *Q ,ElemType x)
{if(Q->rear==Q->front&&Q->tag==1) return false;
Q->elem[Q->rear]=x;
Q->rear=(Q->reat+1)%M;
if(Q->rear==Q.front) Q.tag=1;
Return true;}
Bool DelCQueue(CyclicQueue *Q,ElemType x)
{if(Q->front==Q->rear&&Q->tag==0) return false;
x=Q->elem[Q->front];
Q->front=(Q->front+1)%M;
if(Q->front==Q->rear) Q.tag=0;
return true;}
2、 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是
回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。
参考答案:
int Ishuiwen(char *s)
{ SqStack T;
int i,l;
char c;
InitStack(T);
l=(int)strlen(s);
for(i=0;i<l/2;i++)
Push(T,s[i]);
while(!StackEmpty(T))
{ Pop(T,&c);
if(c!=s[l-i]) return ERROR;
i--;
}
return OK;
}
数据结构各章复习资料
第五章 数组与广义表
一、选择题
1、设一个广义表的A=(a)，其表尾为( C )。
a B、(( )) C、( ) D、(a) A、
2、设有一个N*N的对称矩阵A，将其下三角部分存入一个一维数组B中，A[0][0]存入B[0] 中，那么第i行的对角元素A[i][i]存入于B中的( )处。
A、(i+3)*i/2 B、(i+1)*i/2 C、(2N-i+1)*i/2 D、(2N-i-1)*i/2
3、广义表( (A , B, E, F , G))的表尾是( B )。
A、(B, E , F, G) B、( ) C、(A，B， E，F，G) D、不存在
4、 广义表((( ) ，( )), (a , b, c) , (e , d))的表头是( C )，表尾是( D )。
A、((e , d )) B、( ( ) ) C、( ( ) , ( ) ) D、((a , b , c ),( e , d))
5、 对广义表,,( (a),(b) )进行下面的操作head(head(,)后的结果是( A )。
a B、(a) C、( ) D、不确定 A、
6、 广义表(A,B,E,F,G)的表尾是( A )。
A、(B, E , F, G) B、( ) C、(A，B， E，F，G) D、(G)
44(10),A[2][2]存放位置 7、设有一个二维数A[m][n],假设A[0][0]存放位置在6
在676(10), 每个元素占一个空间，则A[4][5]在(C)位置，(10)表明用10进数表示。
A、692(10) B、626(10) C、709(10) D、724(10)
8. 二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范 围从0到8，列下标j的范围从1到10，则存放M至少需要(D)个字节;M的第8列和第5行共占(A)个字节;若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的( B)元素的起始地址一致。
(1) A、90 B、180 C、240 D、540
(2) A、108 B、114 C、54 D、60
(3) A、M[8][5] B、M[3][10] C、M[5][8] D、M[0][9]
9. 二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范 围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素(B)的起始地址相同。
A、m[2][4] B、M[3][4] C、M[3][5] D、M[4][4]
10. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器 B、100 C、240 D、270
(2) A、SA+141 B、SA+144 C、SA+222 D、SA+225
(3) A、SA+141 B、SA+180 C、SA+222 D、SA+225
二、填空题
1、设广义表A=((a,(b),c),((d)),(e,f))，则表长为( 3 );表头，表尾运算分别用H
(A)，T(A)表示，则表示原子e的表达式为( H(H(T(T(A)))) )。
2、一个向量的第一个元素存储地址是100，每个元素的长度为2，则第五个元素的地址(108)。
数据结构各章复习资料
3、广义表中元素既可以是单原子，也可以是(广义表)广义表两个基本操作是(取表头)、 (取表尾)。
4、若设一个N*N的矩阵A的开始存储地址LOC(0，0)及元素所占的存储单元数d已知 ，按行优先存储时任意一个矩阵元素a[i][j]的存储地址为( LOG(0,0)+(i*n+j)*d )。
5、广义表的深度定义为广义表的括号的( 重数 )。
6、一棵树的广义表的表示为a(b(c,d(e,f),g(h)),i(j,k(x,y))),结点的f的层次为 ( 3 )。设根结点的层次为0。
7、假定一棵树的广义表表示为A(B,C,D(E,F(H(I,J),G)))则树中所含的结点数为(10)，树的深度为( 4 )，树的度是(3)。设根结点的层次为0。
8、将一个N阶矩阵A的上三角部分按行优压缩存放于一个一维数组B中，A[0][0]存放 于B[0]中，则A[i][j]在i<=j时将存放于数组B的( (2n-i-1)i/2+j-i )位置。
三、判断题
1、一个广义表的((a),((b),c),(((d))))的长度为3，深度为4。(T)
= ( ( x , ( a , b ) ) , y )是一个长度为3的广义表。(F) 2、 C
3、tail ( tail (a , ( c , d ) )的结果是(d)。(F)
4、广义表( (a) )的表头是(a),表尾不存在。(F)
5、三元组表是稀疏矩阵的一种顺序存储结构。(T)
6、对非空的广义表的表头和表尾总是一个广义表。(F)
7、将一个对角阵按照行优先的顺序压缩到一个向量中时，对应的存储结构是一种随机的存取结构。(T)
8、若已知一个数组的起始存储地址和维数以及每维的上、下界，且已知每个数组元素所 占有的单元数，则不管按照行优先还是列优先，元素a[i,j]的存储地址是一样的。(F)
9、顺序存储的数组是一个随机存取结构。(T)
10、对一个空表作求表头和表尾的运算后得到的表头和表尾均是空表。(F)
四、操作题
1、n阶矩阵Aij(Aij(0?i，j?n-1)的上三角(不含对角线)为常数C，下三角无规律，
设计压缩存储方案。
参考答案:
1)、共需空间为n(n+1)/2+1个,地址从0至n(n+1)/2
2)、按照行优先顺序依次存储下三角的元素，将常数C存入n(n+)/2中
3)、关系为:
i(i+1)/2+j i>=j
K=
n(n+1)/2 i<j
数据结构各章复习资料
第六章 树与二叉树
一、选择题
，则该二叉树的度为0的结点个数 1、 若一棵二叉树具有10个度为2的结点
是(B)
A、 9 B、 11 C、 12 D、不确定
2、在有n个结点的二叉链表中，值为非空的链域的个数为(A)。
A、n-1 B、2n-1 C、n+1 D、2n+1
3、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个
结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用(C)遍历实现编号。
A、无序 B、中序 C、后序 D、从根开始的层次遍历
4、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是(C)的二叉树。
A、空或只有一个结点 B、高度等于其结点数
C、任一结点无左孩子 D、任一结点无右孩子
5、有64个结点的完全二叉树的深度为(B )(根的层次为1)。
A、8 B、7 C、6 D、5
、在有n个叶子结点的哈夫曼树中，其结点总数为(D)。 6
,、 不确定 ,、2n ,、2n+1 D、2n-1
7、设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为( B )
A、 2k B、 2k+1-1 C 、 2k -1 D、 2k-1-1
8、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行 编号，根结点的编号为1，则编号为49的结点的左孩子编号为( A )。
A、98 B、99 ,、50 ,、48
9、树中所有结点的度之和等于所有结点数加(C)
A、 0 B 、 1 C、 -1 D、 2
10、一棵具有35个结点的完全二叉树的高度为( B ) ，假定树根的高度为1。
A、 5 B、 6 C、 7 D、 8
11、在一个棵具有n个结点的完全二叉树中，树枝结点的最大编号是(A)设按层次编号，且树根的编号为0。
A、(n-1)」/2 B、n/2 」 C、「n/2 D、 n/2 」-1
12、利用n个权值作为叶子结点的生成的哈夫曼树中共包含( D)个结点
,、n B、n+1 ,、2*n ,、2*n-1
13、权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为(D)。
A、 24 B、 48 C、 72 D、 53
14、如果T2是由有序树T转换而来的二叉树,那么T中的结点的后序就是T2中的结点的(B )
A、先序 B、中序 C、后序 D、层次序列
15、设有13个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有( D)个结点.
A、13 B、12 C、26 D、25
二、填空题
( 二叉树的度小 1、树与二叉树的区别是(树是无序的，而二叉树是有序的 )、于等于2，而
树是任意的)。
数据结构各章复习资料
2、93个结点的完全二叉树高度为(7 )，叶子数为( 47)。
3、已知一棵度为5的树中，2度、3度、4度、5度结点的个数依次为1，2，3，4个，则叶 子个数为( 31 )。
4、8层完全二叉树至少有( 128 )个结点,拥有100个结点的完全二叉树的最大层数为(7)。
k-15、深度为K的完全二叉树,其前K-1层共有(2-1)个结点。
6、哈夫曼树是带权路径( 最短 )的树,通常权值较大的结点离根( 近 )。
三、判断题
1、将一棵树转换成一棵二叉树之后，二叉树的根结点的右子树必定为空。(T)
2、一棵树的度是指该树中所有结点的度的和。(F)
3、满二叉树一定是完全二叉树，并且完全二叉树也一定是满二叉树。(F)
4、从树的根结点到树中其余结点均存在一条惟一的路径。(T)
5、在完全二叉树中，一个结点若没有左孩子，则它一定没有右孩子。(T)
四、操作题
1、已知二叉树的先序、中序和后序序列分别如下，但其中有一些模糊不清，请将其补完整。 先序序列 ,BC,EF,,
中序序列 BDE,AG,H
后序序列 ,DC,GH,A
参考答案:先:ABCDEFGH中:BDECAGFH后:EDCBGHFA
2、 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27。
(1)画出这棵Huffman(哈夫曼)树,并计算WPL值。
(2)写出a,b,c,d,e,f的Huffman(哈夫曼)编码。
参考答案:
哈夫曼树 (略)
WPL=2.44
3、已知某二叉树的先序、中序遍历序列分别为ABCDEFG;BDCEAGF，画出它的逻辑结构，中
序线索树, 后序遍历序列。
) 参考答案:中序线索树(略
后序为:DECBGFA
4、请证明任意一棵二叉树中叶子结点数等于度为2的结点数加1。
参考答案:
设度为0，1，2的结点个数分别为n0,n1,n2,总的结点数为n，则有下面的关系: n=n0+n1+n2;n-1=n1+2*n2; 求得:n0=n2+1
数据结构各章复习资料
5、假定一棵二叉树的广义表表示为A(B(，D(G))，C(E，F))，请分别写出对它的前序，中序，层次的遍历序列。
参考答案:前序遍历序列:ABDGCEF。中序遍历序列:BGDAECF。层次遍历序列:ABCDEFG
6、已知二叉树的中的结点的类型BintreeNode定义为:
Struct BinTreeNode
{ ElemType data;
BinTreeNode *left ,*right;}
其中data为结点值域，left和right分别为指向左右子女结点的指针域。根据下面的函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。
Void BTC(BinTreeNode *BT)
{ BintreeNode *t
If(BT!=NULL)
{ if (BT->left!=NULL&&BT->right->right!=NULL)
If(BT->left->data>BT->right->data)
{
T=Bt->left;
BT->left=BT->right;
BT->right=t;
}
BTC(BT->left);
BTC(BT->right);
}
}
参考答案:当BT中的每个结点的左子女的值大于右子女的值则交换左右子树。
5、已知二叉树的中的结点的类型BintreeNode定义为:
Struct BinTreeNode
{ ElemType data;
BinTreeNode *left ,*right;
}
其中data为结点值域，left和right分别为指向左右子女结点的指针域。
参数bt指向一棵二叉棵，引用参数x一开始具有的值小于树中的所有的结点的值。试根据下面的函数定义指出此算法的功能。
Int JB(BinTreeNode *bt ,ElemType *x)
{ if(bt==NULL) return 1;
else
{ if(JB(bt->left,*x)==0) rturn 0;
if(bt->data<*x) return 0;
*x=bt->data;
if(JB(bt->right,*x)==0) return 0;
else return 1;
}
}
参考答案:判定一树二叉树是否为二叉排序树，是则返回1，否则返回0。
6.有一个二叉树中序序列为:ABCEFGHD 后序序列为:ABFHGEDC,请画出此二叉树。
数据结构各章复习资料
参考答案:
7、已知字符A，B，C，D，E，F，G的权值依次为(7，6，10，9，20，15，30)，设计它们的哈夫曼编码，并计算WPL值。
参考答案:A:1110 B:1111 C:010 D:011 E:00 F:110 G:10
WPL=254
五、算法题
1、编写计算二叉树的叶子个数算法，其中T为二叉树的根指针。
int CountLeaf(BinTree T){}
参考答案:
int countLeaf(BitTree T)
{ if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else return(countleaf(T->lchild)+countleaf(T->rchild));
}
2、二叉树的中序与先序遍历的非递归算法.
Status InOrderTraverse(BiTree T){}
Status PreOrdertraverse(BiTree T){}
参考答案:
//中序遍历的非递归算法
Status InOrderTraverse(BiTree T)
{BiTreeStack S;
BiTree p;
Initial(S);
p=T;
while(p||!StackEmpty(S))
{ if(p) {Push(S,p); p=p->lchild;}
else {Pop(S,p);
数据结构各章复习资料
printf("%c",p->data);
p=p->rchild;}
}
return OK
}
//先序遍历的非递归算法
Status PreOrdertraverse(BiTree T)
{BiTreeStack S;
BiTree p;
Initial(S); p=T;
while(p||!StackEmpty(S))
{ if(p) {printf("%c",p->data);
Push(S,p); p=p->lchild;}
else {Pop(S,p);p=p->rchild; }
}
return OK;
}
3、编写层次遍历二叉树的算法。 其中T为二叉树的根指针。 void Layer(BiTree T){}
参考答案:
void Layer(BiTree T)
{
InitQueue(Q); EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}
4、求二叉树高度的算法.
int BiTreeHigh(BiTree *b){ }
参考答案:
int BiTreeHigh(BiTree *b)
{ int lchilddep,rchilddep;
if (b==NULL) return 0;
else
{lchilddep=treedepth(b->lchild);
rchilddep=treedepth(b->rchild);}
return (lchilddep>rchilddep)?lchilddep+1:rchilddep+1;
}
数据结构各章复习资料
第七章 图
一、选择题
1、n 个顶点的连通图至少有(A)条边。
A、n-1 B 、n C、n+1 D、0
D )。 2、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中(
A、第i行非?的元素之和 B、第i列非?的元素之和
C、第i行非?的元素个数 D、第i列非?的元素个数
3、 在有向图中，所有顶点的入度之和是所有顶点的出度之和的( B)倍。
A、2 B、1 C、0.5 ,、不确定
4、任何一个无向连通图的最小生成树(B )
A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在
5、 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是(B )。
A、(N-1)×(N-1) B、N×N C、(N+1)×(N+1) D、不确定
6、对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则表头向量的大小是( A)。
A、 N B、N+1 C、N-E D、N-1
7、 判断一个有向图是否存在回路的方法中，除了可以利用拓扑排序方法外，还可以利用的方法是( C )。
A、求最短路径的方法 B、求关键路径的方法
C、深度优先遍历的方法 D、广度优先遍历的方法
8、一个具有N个顶点的有向图最多有(B )条边。
A、N(N-1)/2 B、N(N-1) C、N(N+1) D、N(N+1)/2
9、对于具有e条边的无向图，它的邻接表中有(D )边结点
A、 e-1 B、 e C、 2(e-1) D、 2e
10、图的深度优先搜索类似于树的( A )次序遍历。
A、 先根 B、中根 C、后根 D、 层次
11、设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑
排序时，总的计算时间为( B )。
e2A 、 O(nlog2e) B、 O(n+e) C、 O(n) D、 O(n)
12、在连通具有n个顶点的有向图，至少需要( B )条边。
A、n-1 B、 n C、n+1 D、2n
13、以知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,
<V3,V6>,<V4,V6>,<V3,V7>, < V6,V7>}则G的可能拓扑序列为:(A)
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
14、对于一个有向图,其邻接矩阵表示比邻接表表示更易于( A)
A、求一个顶点的入度 B、求一个顶点的出边邻接点
C、进行图的浓度优先遍历 D、进行图的广度优先遍历
15、在一个带权的连通图G中，权值最小的边一定包含在G的(A)中。
A、最小生成树中 B、生成树中 C、广度优先生成树中 D、深度优先生成树中
16、与邻接矩阵相比，邻接表更适合存储( C )
数据结构各章复习资料
A、无向图 B、连通图 C、稀疏图 D、稠密图
17、设无向图的顶点的个数为n，则该图的最多有( B )条边。
A、n-1 B、n(n-1)/2 C、n(n+1)/2 D、n(n-1)
18、N个顶点的强连通图至少有(A)条边，这样的有向图的形状是(C)。
(1)A、n B、n，1 C、n,1 D、n(n,1)
(2)A、无回路 B、有回路 C、环状 D、树状
19、最短路径的生成算法可用(C )。
A、普里姆算法 B、克鲁斯卡尔算法 C、迪杰斯特拉算法 D、哈夫曼算法
20、有拓扑排序的图一定是(D )。
A、有环图 B、无向图 C、强连通图 D、有向无环图
21、图的邻接表如下图所示:
vertex firstedge
(1)从顶点V0出发进行深度优先搜索，经历的结点顺序为(B )。
A、V0,V3,V2,V1 B、V0,V1,V2,V3 C、V0,V2,V1,V3 D、V0,V1,V3,V2
(2)从顶点V0出发进行广度优先搜索，经历的结点顺序为( D)。
A、V0,V3,V2,V1 B、V0,V1,V2,V3 C、V0,V2,V1,V3 D、V0,V1,V3,V2
22、对于含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为(A )。
A、O (elog2e) B、O (en ) C、O ( elog2n) D、O (nlog2n)
23、关键路径是事件结点网络中( A)。
A、从源点到汇点的最长路径 B、从源点到汇点的最短路径
C、最长的回路 D、最短的回路
二、填空题
1、在一个无向图中，所有的顶点的度数之和等于边数的( 2 )倍。
2、已知一个图的顶点集V和边的集合E分别如下:
V={0，1，2，3，4，5，6}
E={(0,1)8,(0,2)2,(0,3)6,(1,3)9,(1,4)5,(2,6)10,(3,6)12,(4,5)16,(5,6)15} 则按照克鲁斯卡尔算法写出得到的最小生成树的过程中依次求出的各边数
( (0,2)2 )((1,4)5)((0,3)6)((0,1)8)((2,6)10)((5,6)15)。
3、一般来说，深度优先生成树比广度优先生成树的高度要(高 )。
4、设无向图G中顶点数为n，则图G最少有(n-1)条边，最多有( n(n-1)/2 )条边。若G为有向图，有n个顶点，则图G最少有( n )条边;最多有(n(n-1) )条边。
5、具有n个顶点的无向完全图，边的总数为(n(n-1)/2)条;而在n个顶点的有向完全图中，边的总数为(n(n-1))条。
6、 图的邻接矩阵表示法是表示(边 )之间相邻关系的矩阵。
7、 一个图的生成树的顶点是图的(所有)顶点。
数据结构各章复习资料
8、写出下图所示的一组拓扑序列( V0-V1-V5-V2-V3-V6-V4)。
9、在如下图所示的网络
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
图中关键路径是( 11,13,16,17 )，
全部计划完成的时间是( 19 )。
10、深度优先遍历类似于树的(先根)遍历.它所用的数据结构是(栈)
11、一个连通图的生成树是一个( 极大 )连通子图，n个顶点的生成树有( n-1 )条边。
12、对于含有n个顶点e条边的无向连通图，利用prim算法生成最小代价生成树其时间复
2杂度为( O(n) )。
13、邻接表和十字链表适合于存储(有向)图，邻接多重表适合于存储( 无向 )图。
14、一个非连通无向图,共有28条边,则该图至少有( 9 )个顶点.
15、克鲁斯卡尔算法的时间复杂度是(O (elog2e)),它对(稀疏)图较适用.
16、从源点到汇点长度最大的路径称为关键路径,该路径上的活动称为(关键活动)
三、判断题
1、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该 图的每个顶点。(F)
2、一个有向图的邻接表和逆邻接表中的结点个数一定相等。(T)
3、任何有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一。(F)
4、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。(F)
5、若V(G)中有两个不同的顶点是连通的，则G就称为是连通图。(F)
6、任何图的连通分量只有一个。(F)
7、对于一个有向图进行拓扑排序，一定可以将图中所有的顶点按其关键码大小排序到一个拓扑有序的序列中。(F)
8、存储有向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下(上)三角部分。(F)
9、若连通图上各边权值均不相同,则该图的最小生成树是唯一的。(T)
10、有回路的有向图不能完成拓扑排序。(T)
数据结构各章复习资料
四、操作题
1、带权无向图,(顶点分别为,,，,,，,,，,,，,,，,,)的邻接矩阵是, v1 v2 v3 v4 v5 v6
? , ? ? , ,
, ? ,
? ? ,
? , ? , ? ?
,,
? ? , ? ? ,
, ? ? ? ? ,
, , ? , , ?
要求:(,)画出图,。
(,)分别画出一棵从,,出发的深度优先生成树和广度优先生成树。
(,)画出一棵最小生成树
参考答案:
(1)画出图,。
(略)) (2)生成树(参考答案
(3)画出一棵最小生成树
数据结构各章复习资料
2、已知某有向图的顶点集合为{A，B，C，D，E，F}，边集合为{〈A，B〉，〈A，C〉，〈A，E〉，〈C，F〉，〈E，D〉}，画出该图的邻接表,以它为基础写出深度优先、广度优先遍历序列和 拓扑排序序列(深度、广度遍历要求从结点A开始)。
参考答案:
邻接表
1 2 3 4 5 6
深度优先遍历序列:ABCFED3、广度优先遍历序列:ABCEFD 4、拓扑排序序列:AEDCFB
3、已知无向图的顶点集合为{A，B，C，D，E，F，G}，边集合为{(A，B，5)，(B，C，6)，
(A，E，8)，(B，D，4)，(C，F，5)，(D，E，3)，(D，F，9)，(F，G，7)，(E，G，3)，(D，G，3)}，其中边集合中的数字信息为边上的权值，画出该无向图的邻接表和最小生成树，并以邻接表为基础分别写出深度、广度优先遍历序列(要求从结点A开始)。 参考答案:
邻接表
最小生成树
数据结构各章复习资料
深度优先遍历序列:ABCFDEG 广度优先遍历序列:ABECDGF
4、已知一个图的顶点的集合V和边的集合分别为:
V={1，2，3，4，5，6}
E={(1，2)，(1，3)，(2，4)，(2，5)，(3，4)，(4，5)，(4，6)，(5，1)，(5，3)
(6，5)};
假定该图采用邻接表表示，并且每个顶点的邻接表中的边结点的都是按序号的从大到 小的次序链接的，试按照遍历的算法写出:
(1)从顶点1出发进行的深度优先遍历顶点序列。
序列。 (2)从顶点1出发进行的广义优先遍历顶点
参考答案:
(1)1 ，5 ，6 ，4， 3， 2
(2)1 ，5 ，3 ，2 ，6 ，4
5、已知一个带权图的顶点集V与边集E如下:
V={0，1，2，3，4，5}
E={(0，1)19，(0，2)10，(0，3)14，(1，2)6，(1，5)5，(2，3)26，(2，4)
15，(3，4)18，(4，5)6，(4，6)6，(5，6)12}
试根据Dijkstra算法求出从顶点0到其余的各顶点的最短路径。
参考答案:
顶 点: 0 1 2 3 4 5 6
路径长度: 0 16 10 14 25 21 31
6、已知一个AOV网络的顶点集V和边集G分别为:
V={0，1，2，3，4，5，6，7}
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,
7>,<4,7>,<5,7>,<6,7>};
假定该图采用邻接表表示，并且每个顶点的邻接表中的边结点的都是按序号的从小到
大的次序链接的。按照算法写出进行拓扑排序的序列。
参考答案: 1，3，6，0，2，5，4，7
7、已知一个AOE网络的顶点集V与边集E分别为:
V={0，1，2，3，4，5}
E={<0,1>5,<0,2>8,<1,2>7,<1,3>10,<1,4>6,<2,4>
;3,<3,4>9,<3,5>15,<4,5>12} 假定该图采用邻接表表示,依次写出所有的关键的活动，并求出关键路径的长度。
参考答案:
关键活动:<0,1>5,<1,3>10,<3,4>9,<4,5>12
关键路径长度:36
数据结构各章复习资料
第九章 查找
一、选择题
1、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为(D)。
A、 n B、 n/, C、 (n-1)/2 D、(n+1)/2
2、使用哈希表的目的是(C)。
,、插入 B、删除 C、快速查找 D、排序
3、向一棵AVL树插入元素，可能引起最小不平衡子树的调整过程，此调整分为(C)种。
A、2 B、3 C、4 D、5
4、对于长度为N的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大 的为(A)的值向上取整。
A、log2(N+1) B、log2N C、n/2 D、(n+1)/2
5、对于长度为18的有序顺序表进行折半搜索，则搜索第15个元素的搜索长度为( B)
A、3 B、4 C、5 D、6
6、对于长度为10的顺序表进行搜索,若搜索前5个元素的概率相同均为1/8,搜索后 5个元素的概率均为3/40,则搜索任一元素的平均搜长度为( C )
A、5.5 B、5 C、39/8 D、19/4
7、 下面的查找方式中，可以对无序表进行查找的是( A )。
A、顺序查找 B、二分查找 C、二叉排序树 D、哈希查找
8、 对于关键字值序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，必须从关键字值为( C )的结点开始。
,、100 ,、12 ,、60 ,、15
9、 用n个键值构造一棵二叉排序树，最低高度为( D )。
,、n/2 ,、n ,、2n ,、log2n
10、折半查找要求查找表中各元素的关键字值必须是( A )排列。
,、 递增或递减 ,、递增 ,、递减 ,、无序
11、一个有序顺序表有255个对象，采用顺序搜索法查表，成功平均搜索长度为(A)。
A、128 B、127 C、126 D、255
12、 用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为( B )。
2A、O(n) B、O(log2n) C、O(n) D、O(1)
13、有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排
序树,若希 望高度最小,则应选择下面的序列输入( B )。
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
14、从二叉搜索树中查找一个元素时，其时间复杂度大致为 (C) 。
2A、 O(n) B、 O(1) C、 O(log2n) D、 O(n)
15、向二叉搜索树中插入一个元素时，其时间复杂度大致为 ( B )。
A、 O(1) B、 O(log2n) C、 O(n) D、 O(nlog2n)
16、根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为(D)。
2 A、 O(n) B、 O(log2n) C、 O(n) D、 O(nlog2n)
17、从堆中删除一个元素的时间复杂度为 (C) 。
A 、O(1) B 、O(n) C、 O(log2n) D、 O(nlog2n)
数据结构各章复习资料
18、向堆中插入一个元素的时间复杂度为( A)。
A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)
19、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度(即x同元素的平均比较次数，假定查找每个元素的概率都相等)为 ( C )。
A、 n B、 n/2 C、 (n+1)/2 D、 (n-1)/2
D )。 20、 我们对记录进行排序的目的是(
A、分类 B、合并 C、存储 D、查找
二、填空题
1、从理论上讲，散列查找的算法效率为( O(1) )，但实际应用时，常常因为( 同义词 ) 使查找速度有所降低。
2、二分查找的存储结构仅限于( 有序顺序表 )。
3、对一棵二叉搜索树进行中序遍历时得到的结点的序列是一个( 有序序列 )。
三、判断题
1、能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序表上相同。(F)
2、折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想的平衡的二叉树。(T)
3、折半搜索只适用于有序顺序表。 (T)
4、在顺序表中取出第i个元素所花费的时间与i成正比。(F)
5、折半搜索只适用于有序表，包括有序的顺序表和有序的链表。(F)
6、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数 有关，而且与每一块中的元素个数有关。(T)
7、为度量一个搜索算法的好坏，需要在时间和空间两个方面进行分析。(T)
四、操作题
1、设哈希表的长度,,13;哈希函数为H(K)=K%m，给定的关键码序列为19，14，23，01，
68，20，84，27，55，11，试填出用线性探查法和链地址法解决冲突时所构造的哈希表。并求在每种哈希表上成功查找的ASL.
参考答案
ASL=(6+2*3+3)/10=1.5
数据结构各章复习资料
ASL=(1+1+1+2+1+1+3+4+3+1)/10=18/10=1.8
2、已知哈希函数为除余法(对7取余), 关键字序列(49，10，16，79，13，
76)， 分别画出利用线性探测法(表长为7)、链地址法处理冲突的哈希表。 20，
参考答案: 线性探测法:
3、已知13个有序元素采用折半查找，画出查找判定树，计算等概率成功查找的ASL值。
参考答案:ASL=41/13
4、设散列表的长度为M=11，散列函数为H(K)=K mod M,采用链地址解决冲突，待依次插入的关键码序列为{1，13，12，34，38，33，27，22}。根据构成的开散列表回答: (1)在等概率的情况下，搜索成功时的平均搜索长度。 (2)在等概率的情况下，搜索不成功时的平均搜索长度。 参考答案:(1)13/8 ，(2) 19/11
5、使用哈希函数hash(x)=x mod 11 把数据1,13,12,34,38,33,27,22插入到哈希表中. (1)用线性探测再散列法构造哈希表. (2)使用链地址法构造哈希表.
(3)针对上面的情况,确定其装填因子,并计算线性探测再散列法与链地址法的查找成功所需的平均查找次数以及查找不成功所需的探查次数.哈希表的长度为11, 地址空间为0-10。 参考答案:
数据结构各章复习资料
(1)
(3)装填因子:,,,, 线性探测法:
成功:,,,,,,,,(,，,，,，,，,，,，,，,),,,,, 不成功:u,,,,,,,*(1+1+1+9+8+7+6+5+4+3+2)=47/3 链地址法:
成功:,,,,,,,,(,,,，,,,，,),,,,, 不成功:u,,,,1/11*(3+4+2+1+1+3+1+1+1+1+1)=19/11
数据结构各章复习资料
第十章 B、起泡排序 C、 快速排序 D、 直接选择排序
2、下列序列中，(D)是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。 ,、[ax,bb,cd,da]ff[eb,gc,ha] ,、 [cd,eb,ax,da]ff[ha,gc,bb]
,、[gc,ax,eb,cd,bb]ff[da,ha] ,、 [da,ax,eb,de,bb]ff[ha,gc]
3、在已知待排序文件已基本有序的前提下，效率最高的排序方法是( A)
A、 直接插入排序 B、 直接选择排序 C、 快速排序 D、 归并排序
4、下列排序算法中，( C )排序在某趟结束后不一定选出一个元素放到其最终的位置上。
A、选择 B、冒泡 C、归并 D、堆
5、如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用( B )。
A、快速排序 B、直接插入排序 C、堆排序 D、归并排序
6、 在最坏的情况下，冒泡排序法的时间复杂度为( D )。
2A、O(logn) B、O(nlogn) C、O(n) D、O(n)
7、如果想在4092个数据中只需要选择其中的最小的10个，采用( B )方法
最好。
A、起泡法 B、堆排序 C、直接选择法 D、快速排序
8、对给出的一组关键字{14,5,19,20,11,19}若按关键字非递减排序,第一趟排序结果为 {14,5,19,20,11,19},问采用的排序方法是( C )。
A、简单选择排序 B、快速排序 C、希尔排序 D、二路归并排序
9、以下序列不是堆的是(D )
A、{100,85,98,77,80,60,82,40,20,10,66}
B、{100,98,85,82,80,77,66,60,40,20,10}
C、{10,20,40,60,66,77,80,82,85,98,100}
D、{100,85,40,77,80,60,66,98,82,10,20}
二、填空题
1、每次使两个相邻有序表合并成一个有序的排序方法叫做( 归并 )排序。
2、写出三种不稳定的排序方法的名称(快速排序)、(希尔排序)和(堆排序)。
3、在对于一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当 把第七个记录60插入到有序表时，为寻找插入位置需比较( 3 )次。
)次调整算法。 4、在堆排序中，对N个记录的建立初始堆时需要调用( N/2
25、快速排序在最坏情况下的时间复杂度为( O(n) )。
6、给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟
3 )。 快速排序处 理，得到的右子表中的数据个数为(
7、若关键字序列为正序，则直接插入排序，希尔排序，快速排序中哪个排序方法效率最高 (直接插入排序 )，此时时间复杂度为( O(n) )。
8、假定一个大顶堆为(64，38，55，20，15，44，18，12)则从中删除最大元素后得到 的堆序列为(55，38，44，20，15，12，18，64 )。
数据结构各章复习资料
三、判断题
1、 直接选择排序是一种不稳定的排序方法。(F)
2、二路归并排序的核心操作是将两个有序序列归并为一个有序序列。(T)
3、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法 是不稳定的。(F)
4、对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。(F)
5、堆排序适合记录数目较少的文件。(F)
6、基于关键字之间的比较来实现的排序算法需要的时间的下界是O(nlgn)。(T)
7、基数排序是一种就地排序，它是稳定的排序方法。(T)
8、直接插入排序是一种就地排序，它需要的辅助空间是O(n)。(F)
9、直接插入排序方法是稳定的。(T)
10、在冒泡排序法中，如果按照轻气泡向上的原则进行排序，则排序的终止条件是:待排 序的无序区中所有的气泡均满足轻者在上，重者在下。(T)
四、操作题
1、已知关键字序列为 (34,23,56,32,45,58,89,20,25,50)，分别用下列排序方法进行排序， 分别写出每趟排序结果，并指出算法的稳定性。1)快速排序 2)希尔
排序 3)堆排序
49 38 65 97 76 13 27 49
参考答案:
快速:(不稳定)
一趟:25 23 20 32 34 58 89 45 56 50
二趟:20 23 25 32 34 50 56 45 58 89
三趟:20 23 25 32 34 45 50 56 58 89
希尔:(不稳定)
一趟:34 23 20 25 45 58 89 56 32 50
二趟:25 23 20 34 45 32 50 56 58 89
三趟:20 23 25 32 34 45 50 56 58 89
堆排序:(不稳定)
初建堆序列:89,50,58,32,45,34,56,20,25,23
一趟: 58,50,56,32,45,34,23,20,25,89
二趟: 56,50,34,32,45,25,23,20,58,89
三趟: 50,45,34,32,20,25,23,56,58,89
2、给定序列 24,38,48,39,36,12,27 请写出将其调整成大顶堆后的序列
39，27，38，36，12，24 参考答案:48，
3、请写出下面关键字序列的第一趟和第二趟快速排序(排序是从小到大)后的序列。 参考答案:
一趟:27，38，13，49，76，97，65，49
二趟:13，27，38，49，49，65，76，97
数据结构各章复习资料
五、算法题
1、快速排序、选择法排序、冒泡法排序的算法。 void QuickSort(SqList *L){}
void BubbleSort(SqList *L){}
void SelectSort(SqList *L){}
参考答案:
//快速排序算法
void QuickSort(SqList *L)
{
QSort(L,1,L->count);
}
void QSort(SqList *L,int low,int high)
{
int pivotloc;
if(low<high)
{pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->elemword[low];
while(low<high)
{while(low<high&&L->elemword[high]>=pivotkey)
--high;
L->elemword[low]=L->elemword[high];
while(low<high&&L->elemword[low]<=pivotkey)
++low;
L->elemword[high]=L->elemword[low];
}
L->elemword[low]=pivotkey;
return low;
}
//昌泡法
void BubbleSort(SqList *L)
{
int i,j,t;
enum BOOL change;
for(i=L->count-1,change=True;i>0&&change;--i)
{change=False;
for(j=0;j<i;j++)
数据结构各章复习资料
if(L->elemword[j]>L->elemword[j+1])
{t=L->elemword[j];
L->elemword[j]=L->elemword[j+1];
L->elemword[j+1]=t;
change=True;
}
}
}
//选择法
void SelectSort(SqList *L)
{
int i,j,t;
for(i=1;i<L->count;++i)
{j=SelectMinKey(L,i);
if(i!=j)
{t=L->elemword[i];
L->elemword[i]=L->elemword[j];
L->elemword[j]=t;
}
}
}
int SelectMinKey(SqList *L,int low)
{
int i,j,t;
t=L->elemword[low];
j=low;
for(i=low+1;i<=L->count;i++)
if(L->elemword[i]<t)
{t=L->elemword[i];
j=i;
}
return j;
}
2、假定元素类型为ElemType的一维数组R[n]中保存着按关键码升序排列的n个记录，记 录的关键码域key的类型为KeyType,试按照下面的函数声明编写一个非递归的算法，从一 维数组R[n]中折半搜索出关键码等于K的记录，若搜索成功则返回记录位置(即元素的下 标)，否则返回-1。
int BinSearch(ElemType R[],int n,KeyType K){}
参考答案:
int BinSearch(ElemType R[],int n,KeyType K)
{
int mid,low=0,high=n-1;
while(low<=high)
{
数据结构各章复习资料
mid=(low+high)/2;
if(K==R[mid].key) return mid;
else if(K<R[mid].key) high=mid-1;
else low=mid+1;
}
return -1;}
3、 有一种简单的排序的算法，叫做计数排序，这种排序的算法对一个数据互不相同的表进 行排序，并将排序结果存放到另一个新表中去。针对表中的每个数据，计数算法都要扫 描一趟表，统计出表有多少个数据比它小。假设针对某个数据，统计出的计数据值为c，则这个数据在新表中合适的存放位置是c。
void countsort(ElemType src[],ElemType dest[],int size){}
参考答案:
void countsort(ElemType src[],ElemType dest[],int size)
{ int i,j,c;
for(i=0;i<size;i++)
{
c=0;
for(j=0;j<size;j++)
if(scr[i]>scr[j]) c++;
dest[c]=scr[i];
}
}
浙公网安备 33021202002483