数据结构习题解答

习题一

1 填空题

(1) (数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。

(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。

(3)从逻辑关系上讲，数据结构主要分为(集合)、(线性结构)、(树结构)和(图)。

(4)数据的存储结构主要有（顺序存储结构）和（链式存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（它们之间的关系）。

(5) 算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。

(6) 算法的描述方法通常有(自然语言)、(流程图)、(程序设计语言)、(伪代码)4种，其中，(伪代码)被称为算法语言。

(7) 一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。

(8) 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为(O(1))，若为n*log25n, 则表示成数量级的形式为(O(n*log2n))。

2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E

习题二

1. 填空题

(1) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)有关。

(2) 一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。

(3) 设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=(p->next)->next, 或者q=p->next; p->next=q->next）。

(4) 单链表中设置头结点的作用是(方便运算,减少程序的复杂性，使得空表和非空表处理统一)。

(5) 非空的循环单链表由头指针head指示，则其尾结点(由指针p所指)满足(p->next=head)。

(6) 在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是（s->next=rear->next; rear->next=s; rear=s），删除开始结点的操作序列是（q=rear->next->next; rear->next->next=q->next; delete q;）。

注：假设此循环单链表有表头结点

(7) 一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（O(1)）；在给定值x的结点后插入一个新结点的时间复杂性为( O(n) ）。

(8) 可由一个尾指针惟一确定的链表有(循环链表)、(双链表)、(双循环链表)。

2. 选择题: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10) B (11) B (12) D (13) A (14) A

5. 算法设计

(1)设计一个时间复杂度为O(n)的算法。实现将数组A[n]中所有元素循环左移k个位置。

算法思想：要使a1…a k a k+1…a n -> a k+1…a n a1…a k,可以先让a1…a k a k+1…a n->a k…a1a n…a k+1,再让a k… a1 a n…a k+1 -> a k+1…a n a1…a k，参见第1章16页的思想火花

算法：void converse(T a[], int i, int j){

for(s=i; s<=(i+j)/2;s++) //将数组a中从i到j中的元素倒置

{temp=a[s];a[s]=a[j-s+i];a[j-s+i]=temp;} }

void move(T a[ ], k)

{converse(a,0,k-1);//3次调用函数converse

converse(a,k,n-1);

converse(a,0,n-1);

}

(2) 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n).

解法1：void tiaozhen(T A[],int n)

{ s=0; t=n-1;

while(s

{ while( A[s]%2!=0) s++;//s=s+1

while ( A[t]%2==0) t--;

if(s

}}

或void tiaozhen(T A[],int n)

{ s=0; t=n-1;

while(s

{ if(A[s]%2!=0) s++;//s=s+1

else if(A[t]%2==0) t--;

else {temp=A[s];A[s]=A[t];A[t]=temp; s++;t--;}

}}

(3) 试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较

void LinkList_1::Insert(int i, T x){

if(i<=0) throw "输入的插入位置值小于1";

if(i==1){s=new Node; s->data=x; s->next=first; first=s; }

else{ p=first ; j=0;

while (p && jnext; j++; }

if (!p) thr ow “插入位置值太大";

else { s=new Node; s->data=x; s->next=p->next; p->next=s; }

}

}

(4) 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

算法思想：顺序表的程序参见题（1）的converse.单链表的程序如下，设单链表有表头结点.

void LinkList::converse()

{ p=first->next;

first->next=NULL;

while(p){

q=p->next; p->next=first->next;

first->next=p;p=q;

}

}

(5) 假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。

void LinkList::deleteS(Node *s)

{p=s;

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

{ q=p->next; p->next=q->next;

delete q;

}

(6) 已知一单链表中的数据元素含有三类字符：字母、数字和其它字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。

2）遍历单链表，按单链表中的当前数据元素的分类插入相应的链表

void fl(Node* zifu, Node *shuzi, Node *qita)

{ s=new Node; s->next=s; zifu=s;

s=new Node; s->next=s; shuzi=s;

s=new Node; s->next=s; qita=s;

a=zifu; b=shuzi; c=qita;

p=first->next; //设单链表带头结点

while(p) { q=p; p=p->next;

if((q->data>='a'&&q->data<='z') ||(q->data>='A'&& q->data<='A'))

{ q->next=a->next; a->next=q; a=q;}

else if(q->data>='0' && q->data<='9')

{q->next=b->next; b->next=q; b=q;}

else {q->next=c->next; c->next=q; c=q;}

}

delete first;

}

(7) 设单链表以非递减有序排列，设计算法实现在单链表中删除相同的多余结点。

解：void LinkList::deleteALL()

{ p=first->next; //假设单链表带表头结点。

while(p)

{if(p->next!=NULL && p->next->data==p->data)

{q=p->next; p->next=q->next; delete q;}

else p=p->next;}

}

(8) 判断带头结点的双循环链表是否对称。

解bool LinkList::equal(DulNode *first)

{ p=first->next; q=first->prior;

while(p!=q&&p->prior!=q)

if(p->data==q->data)

{p=p->next; q=q->prior;}

else {return 0;}

return 1;

}

----------------------------------------------------------------------------------------------------------------------------------------

习题三

1 填空题

(1) 设有一个空栈，栈顶指针为1000H，经过push、push、pop、push、pop、push、push后，栈顶指针为(1003H)。

(2) 栈结构通常采用的两种存储结构是(顺序存储结构和链接存储结构\顺序栈和链栈)，其判定栈空的条件分别是(top=-1, top=NULL), 判断栈满的条件分别是(top=MaxSize-1, 内存满/内存无可用空间)。

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

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

(5) 栈和队列是两种特殊的线性表，栈的操作特性是(后进先出)，队列的操作特性是(先进先出)，栈和队列的主要区别在于(插入、删除运算的限定不一样)。

(6) 循环队列的引入是为了克服( 假溢出)。

(7) 一维数组Data[n]用来表示循环队，队头指针front和队尾指针rear定义为整型变量，计算队中元

(8) 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是( O(1) )和( O(n) )。

2. 选择题: (1) C (2) D (3) C (4) B (5) B (6) B (7) D (8) A (9) C

4.解答下列问题

(1)①不可以, 因为有序列C, A, B.

② 可以, push, push, push, pop, pop, pop, push, pop, push, pop.

(2)见书本

(3)栈顶元素是6, 栈底元素是1.

(4)队尾元素是9, 队头元素是5.

(5)①③④合法, ②不合法.

习题四

1. 填空题

(1) 串是一种特殊的线性表，其特殊性体现在( 数据元素的类型为字符型)。

(2) 两个串相等的充分必要条件是( 它们的长度相等且对应位置的字符相同)。

(3) 数组通常只有两种运算，分别是( 存取)和( 修改)，这决定了数组通常采用（顺序存储）结构来实现存储。

(4) (1140)

(5)设有一个10阶的对称矩阵A采用压缩存储，第一个元素A[0][0]的存储地址为d，每个元素占用1个地址空间，则元素A[8][5]的存储地址为( d+41 )。

(6) 稀疏矩阵一般压缩存储方法有两种，分别是( 三元组顺序表)和( 十字链表)。

2. 选择题: (1) B (2) D, E, K (3) B (4) XXX (5) D (6) C (7) D

5(2). 设计一个求矩阵A=(a ij)nXm所有鞍点的算法，并分析最坏情况下的时间复杂度。

算法思想2：附加两个数组B[n]和C[m]，B[i]用来存第i行的最小值，C[j]用来存第j列的最小元素值。如果A[i][j]= B[i]=C[j]，则A[i][j]一定为马鞍点。

viod maandian2(A[ ][ ],int m,int n){

int B[n],C[m],i,j;

for(i=0;i

B[i]=A[i][0];

for(j=1;jA[i][j]) B[i]=A[i][j];}

for(j=0;j

C[j]=A[0][j];

for(i=1;i

for(i=0;i

for(j=0;j

if (B[i]==A[i][j]&&C[j]==A[i][j])

cout<

}

算法复杂度：O(mn)。从时间复杂度的幂的角度来说这个算法是最好的，因为你求马鞍点必须要搜索所有的A[i][j]。

习题五

1 填空题

(1)树是n（n≥0）个结点的有限集合。在一棵非空树中，有（且仅有一个）根结点，其余结点分成m （m>=0）个(互不相交)的有限集合，每个集合又是一棵树。

(2) 树中某结点的子树的个数称为该结点的（度），子树的根结点称为这个结点的( 孩子结点),该结点称为其子树根结点的（双亲结点）.

(3) 一棵二叉树的第i（i≥1）层上最多有( 2i-1)个结点,一棵有n(n>0)个结点的满二叉树共有( (n+1)/2 )个叶子结点和( (n-1)/2 )个非终端结点。

(4) 设高度为h的二叉树只有度为0的和度为2的结点，该二叉树的结点数可能达到的最大值是( 2h-1 ),最小值是（2 h -1）。

(5)深度为k的二叉树中，所含叶子的个数最多为(2k-1).

(6)具有100个结点的完全二叉树的叶子结点数为(50)。

(7) 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树有(12)个叶子结点。

(8) 某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是( CDBGFEA )。

(9)在具有n个结点的二叉链表中，共有（2n)个指针域，其中( n-1)个指针域用于指向其左右孩子，剩下的( n+1)个指针域则是空的。

(10)在有n个叶子的哈夫曼树中，叶子结点总数为( n ),分支结点总数为（n-1）。

2. 选择题: (1) D (2) D (3) B (4) C (5) B,C (6) D (7) A (8) A,B (9) D,A (10) B (11) B (12) C (13) D (14) C

4. 解答下列问题

(3) 已知一棵度为m的树中：n1个度为1的结点，n2个度为2的结点，…，n m个度为m的结点，问该树中共有多少个叶子结点？

解：设该树中共有n0个叶子结点。则该树中总结点个数为

n= n0+ n1+…+ n m.

而分支数为n-1= n1 +2n2 +3n3+…+ mn m,所以

n0 =1+n2 +2n3+…+ (m-1)n m

(4) 已知一棵二叉树的中序和后序序列为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。

(5) 给出叶子结点的权值集合为W={5,2,9,11, 8,3,7}的哈夫曼树的构造过程。

(1) 设计算法求二叉树的结点个数.

注：本算法可以用二叉树遍历的所有算法，只要把cout语句换成结点的计数就可以了，但是要注意递归中的计数变量应该是外部变量。如

int num=0;

int BiTree::count(BiNode *rt) { countsub(rt); return num;}

void BiTree::countSub(BiNode *rt) {

if (rt !=NULL) { num++; countSub (rt->lchild); countSub (rt->rchild); }

}

其他解法二：用前序遍历的非递归算法

int BiTree::CountPreOrder(BiNode *rt)

{top= -1; p=rt; num=0;//采用顺序栈s，并假定不会发生上溢

while (p!=NULL | | top!= -1) {

while (p!= NULL) //找此结点的最左边的后代

{ num++; //访问

s[++top]=p; //此结点进栈

p=p->lchild; //转移到左儿子子树

}

if (top!= -1) {p=s[top--]; p=p->rchild; }}

return num; // cout<

}

(2) 设计算法按照前序次序打印二叉树中的叶子结点.

注:其实按照“选择题”的(7)知:任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改变

解法思想: 使用任何遍历算法，把“cout<data”改成判断此结点是否为叶子结点。

void BiTree::leaf(BiNode *rt){

if (rt==NULL) return;

else

{ if(rt->lchild==NULL &&!rt->rchild)

cout<data;

PostOrder(rt->lchild);

PostOrder(rt->rchild);

} }

(3) 设计算法求二叉树的深度.

注：本算法也可以用二叉树遍历的所有算法。但是在用前序和中序算法时要注意深度如何来确定。int BiTree::depth(BiNode *rt)

{ if (rt ==NULL) return 0;

else {

hl= depth(rt->lchild);

hr= depth(rt->rchild);

return (hl>hr)?hl+1:hr+1;

}

(4) 设计算法:输出二叉树后序遍历的逆序.

解法思想: 太简单啦！！！前序遍历是先遍历右子树即可.

void BiTree::PostOrder_1(BiNode *rt){

if (rt==NULL) return;

else {

cout<data;

} }

(5) 以二叉链表为存储结构，编写算法求二叉树中值x的结点的双亲.

void BiTree::PreOrder_Parent(BiNode *rt){

{top= -1; p=rt;//采用顺序栈s，并假定不会发生上溢

while (p!=NULL | | top!= -1) {

while (p!= NULL)

{ if(rt->lchild!=NULL &&rt->lchild->data==x)

cout<data;

if(rt->rchild!=NULL &&rt->rchild->data==x)

cout<data;

s[++top]=p; //此结点进栈

p=p->lchild; //转移到左儿子子树

}

if (top!= -1) {p=s[top--]; p=p->rchild; }}

}

(6) 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树.

void BiTree::DeleteX(BiNode *rt, T x)

{ if(rt==NULL) return;

if(rt->data==x) {Release(rt);}

else{

DeleteX(rt->lchild, x);

DeleteX(rt->rchild, x);

} }

(7) 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历.

算法思想: 套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法。注：根结点的下标是1。

void BiTree::PreOrder_Seq(int rt)

{top= -1; p=rt; //采用顺序栈s，并假定不会发生上溢

while ((p<=length)&&(A[p]!=“ ”)) | | top!= -1) {

while ((p<=length)&&( A[p]!=“ ”)){

//找此结点的最左边的后代

cout<

s[++top]=p; //此结点进栈

p=2*p; //转移到左儿子子树

}

if (top!= -1) {p=s[top--]; p=2*p+1; }

}

}

(8) 编写算法交换二叉树中所有结点的左右子树.

解法思想: 使用任何遍历算法，把“cout<data”改成左右孩子指针交换即可。

void BiTree::PostOrderChange(BiNode *rt)

{

if (rt==NULL) return;

else

{ PostOrder(rt->lchild);

PostOrder(rt->rchild);

rt->rchild=temp;

} }

习题6

1.填空题

⑴设无向图G中顶点数为ｎ，则图G至少有（0 ）条边，至多有（n(n-1)/2）条边；若G为有向图，则至少有（0）条边，至多有（n(n-1)）条边。

⑵任何连通图的连通分量只有一个，即是（它本身）。

⑶图的存储结构主要有两种，分别是（邻接矩阵）和（邻接表）。

⑷已知无向图Ｇ的顶点数为ｎ，边数为ｅ，其邻接表表示的空间复杂度为（O(n+e)）。

⑸已知一个图的邻接矩阵表示，计算第ｊ个顶点的入度的方法是（矩阵中第j-1列的非0元素个数）。

⑹有向图Ｇ用邻接矩阵Ａ[ｎ][ｎ]存储，其第ｉ行的所有元素之和等于顶点ｉ的（出度）。

⑺图的深度优先遍历类似于树的（前序）遍历，它所用的数据结构是（栈）；图的广度优先遍历类似于树的（层序）遍历，它所用的数据结构是（队列）。

⑻对于含有ｎ个顶点ｅ条边的连通图，利用Ｐrim算法求最小生成树的时间复杂度为（O(n2)），利用Kruscal算法求最小生成树的时间复杂度为（O(elog2e)）。

⑼如果一个有向图不存在（有向回路），则该图的全部顶点可以排成一个拓扑序列。

⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点v i ,v j , v k的相对次序为（v i ,v j , v k）。

2. 选择题: (1) C (2) A,G (3) C (4) B (5) D (6) C,F (7) B (8) D (9) A (10) A (11) A (12) C (13) A (14) C,C,F (15) B

4. 解答下列问题

(1) n个顶点的无向图,采用邻接表存储,回答下列问题:

①图中有多少条边?

答: 邻接表中所有边表结点的个数的一半.

②任意两个顶点i和j是否有边相连?

答: 查找第i个边表的结点中是否有邻接点域值为j的结点. 如果有,则它们之间有边;否则,无边.

③任意一个顶点的度是多少?

答: 此顶点对应的边表中结点的个数.

(2) n个顶点的无向图,采用邻接矩阵存储,回答下列问题:

①图中有多少条边?

答: 邻接矩阵中所有元素和的一半.

②任意两个顶点i和j是否有边相连?

答: 如果第i行第j列的元素值为1,则它们之间有边;否则,无边.

③任意一个顶点的度是多少?

答: 此顶点对应的行中元素之和.

(3) 证明：生成树中最长路径的起点和终点的度均为1.

证明：设一棵树的最长路径P=v1v2…v k。若v1的度至少为2，不妨设u(≠v2)是它的另外一个邻点。若u ∈{v1, v2, …, v k}, 则此树中包含圈，矛盾；否则uv1v2…v k是一条更长的路，同样矛盾。所以v1的度为1. 类似可以证明v k的度为1.

(5) 图6-50所示是一个无向带权图，请分别用Ｐrim算法和Ｋruscal算法求最小生成树。

习题7

1. 填空题

(1)顺序查找技术适合于存储结构为（各种形式）的线性表，而折半查找技术适合于存储结构为（顺序存储）的线性表，并且表中的元素必须是（有序的）。

(2) 设有一个已按各元素值排好序的线性表，长度为125，用折半查找法查找与给定值相等的元素，若查找成功，则至少需要比较(1 )次，至多需要比较(7)次。

(3) 对于数列{25, 30, 8, 5, 1, 27, 24, 10, 20, 21, 9, 28, 7, 13, 15},假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（8 ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（59/15）。

(4)长度为20的有序表采用折半查找，共有（4）个元素的查找长度为3。

(5) 假设数列{25, 43, 62, 31, 48, 56},采用散列函数为H(k)=k mod 7, 则元素48的同义词是（62）。

(6) 在散列技术中，处理冲突的主要方法是（开放地址法）和（拉链法）。

(7) 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（散列查找）。

(8) 与其他方法比较，散列查找法的特点是（记录的存储位置与关键码之间建立了一个确定的对应关系，平均查找长度与结点个数无关）。

2. 选择题: (1) B (2) D,D (3) A,B (4) D (5) A (6) C (7) C (8) B (9) D (10) A (11) C (12) C 4．解答下列问题

(1) 分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码e和g的过程。

解：d->f->e和d->f->g

(2) 画出长度为10的折半查找判定树，并求出等概率时查找成功和不成功的平均查找长度。

等概率时查找成功平均查找长度=(1*1+2*2+4*3+3*4)/10=29/10

等概率时不成功的平均查找长度=(5*4+6*5)/11=50/11

(3) 将数列(24,15,38,27,76,130,121)的各个元素依次插入一颗初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。

AVL=(1+2*2+3*3+4+5)/7

(4) 已知一棵二叉排序树的结构如图7-30所示，结点的值为1~8，请标出各点的值。

答：见题上图

习题8

1.填空题

(1) 排序的主要目的是为了以后对已排序的数据元素进行( 查找)。

(2) 对n个元素进行起泡排序，在(关键码有序)的情况下比较的次数最少，其比较次数为(O(n))。在(关键码逆序)情况下比较次数最多，其比较次数为(O(n2))。

(3) 对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序，当把第7个记录60插入到有序表时, 为寻找插入位置需比较( 3 )次。

(4) 对一组记录(54,38,96,23,15,72,60,45,83) 进行快速排序，在递归调用中使用的栈所能达到的最大深度为( 4 )。

(5) 对n个待排序记录序列进行快速排序，所需要的最好时间是(O(nlog2n )，最坏时间是(O(n2))。

(6) 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为(n-1)

(7) 如果要将序列(50,16,23,68,94,70,73)建成堆，只需把16与( 50 )交换。

(8) 对于键值序列(12,13,11,18,60,15,7,18, 25, 100)，用筛选法建堆，必须从键值为( 60)的结点开始。

2. 选择题：(1) C (2) C (3) C (4) B (5) A (6) A (7) B,D,B (8) C (9) D (10) A,D (11) B (12)

D,B,E,A,C (13) C (14) D (15) C

数据结构习题及答案——严蔚敏_课后习题答案 精品

第一章绪论 选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案： 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B

经典数据结构面试题(含答案)

栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构习题及参考答案

习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对

数据结构模拟卷(含答案)经典习题培训讲学

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )

数据结构课后参考答案

单元练习1 一．判断题（下列各题，正确的请在前面的括号打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。（4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。（7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n）。

数据结构习题及答案精编版

第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。

数据结构课后习题及解析第二章

第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2

数据结构课后习题及答案

填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

经典数据结构上机题_答案解析

数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #include

#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i

数据结构习题及答案——严蔚敏

第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法

② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、

数据结构例题解析(1)

I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by .

a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search

数据结构经典题目c语言代码

《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include #include // 链表节点 typedef struct _RingNode { int pos; struct _RingNode *next; }RingNode, *RingNodePtr; // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0)

{ pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr;

数据结构习题与答案

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

(完整版)数据结构练习题(含答案)

数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i

数据结构第一章课后习题与答案

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

2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性

数据结构经典例题

数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (countlink; p=p->link; } if (count