数据结构部分习题
数据结构部分习题
一、问答题
1、简述下列术语：线性表，顺序表，链表。
2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?
3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?
4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?
二、单选题
1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。
A. 查找单链表中第i个结点
B. 在p结点之后插入一个结点
C. 删除表中第一个结点
D. 删除p结点的直接后继结点
2、在下列链表中不能从当前结点出发访问到其余各结点的是( )。
A. 单链表
B. 单循环链表
C. 双向链表
D. 双向循环链表
3、线性表采用顺序存储时，其地址( )
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续与否均可以
4、线性表采用链式存储结构时，其地址( )
A．必须是连续的B．部分地址必须是连续的
C.一定是不连续的D．连续与否均可以
5、在长度为n的顺序表的第i个数据元素(1≤i≤n)之前插入一个数据元素,元素的移动次数为( )。
A. n-i+1
B. n-i
C. i
D. i-1
6、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。
A．单链表B．双向链表
C．单循环链表D．循环链表
8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（）。 A．p = q->next ; p->next = q->next;
B．p = q->next ; q->next = p;
C．p = q->next ; q->next = p->next;
D．q->next = q->next->next; q->next = q;9、
9、链表不具有的特点是（）。
A．可随机访问任一元素
B．插入删除不需要移动元素
C．不必事先估计存储空间
D．所需空间与线性表长度成正比
10、对于一个头指针为h的带表头结点单链表，判定其为空表的条件是( )。
A. h==NULL；B．h->next==NULL；
C．h!=NULL；D．h->next== h；
11、在非空单链表中，在p结点后插入一个q结点依次执行操作是( )。
A. q->link=p; p->link=q；
B. q->link=p->link; p->link=q；
C. q->link=p->link；p=q；
D. p->link=q；q->link=p；
12、以下关于线性表的叙述中，正确的是( )。
A. 顺序表可以随机存取
B. 链表可以随机存取
C. 顺序表便于动态处理
D. 顺序表便于插入或删除数据元素
13、在非空的单循环链表h中，某个p结点为尾结点的条件是( )。
A. p==NULL；B．p->link==NULL；
C．h!=NULL；D．p->link== h；
14. 设p结点是带表头结点双向循环链表的表中结点,在p结点后插入s结点语句序列中正确的是( )
A. s->next=p->next；p->next->prior=s；
p->next=s；s->prior=p；
B. p->next=s；s->next=p->next；
p->next->prior=s；s->next=p；
C. p->next=s；p->next->prior=s；
s->next=p->next；s->next=p；
D. p->next->prior=s；p->next=s；
s->next=p->next；s->next=p；
15、设p结点是带表头结点的双循环链表的表中结点，在p结点之前插入s结点的语句序列中正确的是( )。
A. s->prior=p->prior；p->prior->next=s；
p->prior=s；s->next=p；
B. p->prior=s；p->prior->next=s；
s->prior=p->prior；s->next=p；
C. p->prior->next=s；p->prior=s；
s->prior=p->prior；s->next=p；
D. p->prior=s；s->next=p；
p->prior->next=s；s->prior=p->prior；
16、以下关于静态链表的叙述中，错误的是( )。
Ⅰ静态链表既有顺序存储的优点又有动态链表的优点，所以它存取表中第i个元素的时间与i无关。
Ⅱ.静态链表能容纳的最多元素个数在表定义时就确定了，以后不能增加。
Ⅲ.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A.只有Ⅰ
B.只有Ⅱ
C. Ⅰ和Ⅱ
D. Ⅰ、Ⅱ和Ⅲ
17、在具有n个结点的单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )。
A. O(1)
B. O(n)
C. O(nlog2n)
D. O(n2)
三、算法题
1、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。
2、写一求单链表的结点数目ListLength(L)的算法。
3、写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。
4、写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定
的参数，可以和表中的元素相同，也可以不同)。
一、问答题
1、设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？
2、循环队列的优点是什么?如何判断它的空和满？
3、利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说
明S为何不作为引用参数的算法?
4、一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i 为0或1 ，用以表示栈号。
5、假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头
尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。
a.d, e, b, g, h入队
b.d, e出队
c.i , j , k , l , m入队
d.b出队
e.n, o, p, q, r入队
二、选择题
1、在栈中存取数据遵守的原则是（）
A．先进先出B．后进先出
C．后进后出D．随机进出
2、设S是顺序栈,元素a,b,c,d,e,f依次栈,如果出栈顺序为b,c,d,f,e,a,则顺序栈的容量至少应为
( )个元素。
A. 2
B. 3
C. 4
D. 5
3、用一个大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向栈中插
入一个元素时,首先应执行( )语句修改top指针。
A．top++ B．top-- C．top=0 D．top==0
4、设有一个空栈，栈顶指针为1000H,每个元素占一个单位的存储空间，则执行
Push,Push,Pop,Push,Pop,Push,Pop,Push操作以后，栈顶指针的位置是（）。
A. 1000
B. 1001
C. 1002
D. 1003
5、表达式a*(b+c)-d的后缀表达式是( ) 。
A．abcd *+- B. abc+*d - C. abc*+d - D. -+ * abcd
6、一个初始输入序列a、b、c、d，顺序进入栈S，然后依次从栈S中出栈并进入队列Q中，
再从队列Q中出队进入栈S，则在栈S中从栈顶到栈底的序列是( ) 。
A. abcd
B. dcba
C. badc
D. adcb
7、用一个大小为6的数组来实现循环队列，元素依次按照0,1,2,3,4,5的位置顺序循环存放,
当前front和rear的值分别为4和0，现在从队列中删除一个元素,再加入2个元素后,front 和rear的值分别是( )。
A．5和2 B．6和1 C．2和4 D．3和1
8、设一个循环队列Q[maxsize]的队头指针为front 、队尾指针为rear,队列的最大容量为
maxsize , 除此之外该队列没有其他数据成员，则该队列的队满条件是( )。
A. Q.rear==Q.front
B. Q.rear+Q.front >=maxsize
C. (Q.rear+1)% maxsize ==Q.front
D. (Q.front+1)% maxsize ==Q.rear
一、选择题
（1）关于二叉树下列说法正确的是（B ）。
A.二叉树的度为2
B.二叉树的度可以小于2
C.每一个结点的度都为2
D.至少有一个结点的度为2
（2）设高度为h的二叉树只有度为0和度为2的节点，则此二叉树中结点总数至少为（B ）。
A.2h
B.2h-1
C. 2h+1
D.h+1
（3）在树种，结点A有4个兄弟，B是A的双亲，则B的度为（ C ）。
A.3
B.4
C. 5
D. 6
（4）若一棵完全二叉树中，某节点无左孩子，则该结点一定是（D ）。
A.度为1的结点
B.度为2的结点
C.分支节点
D.叶子结点
（5）高度为k的完全二叉树至多有（C ）个结点，至少有（ B ）个结点。
A.2K-1-1
B. 2K-1
C.2K-1
D.2K
（6）先序序列为ABC的二叉树有（C ）棵。
A. 3
B.4
C.5
D.6
（7）在有200个结点的完全二叉树中，根的编号为1，则编号为60的结点左孩子编号是（），右孩子的编号是（ D ）。
A.30
B.60
C.120
D.121
（8）遍历一棵具有n个结点的完全二叉树，在先序，中序和后序序列中，叶子结点的相对次序（B ）。
A.都不同
B.完全相同
C.先序和中序相同
D.中序与后序相同
（9）在由4棵树组成的森林中，1，2，3，4棵树，树中结点的个数分别为30，10，20，5，当把森林转化成为二叉树后，对应的二叉树中根结点的左子树中结点的个数是（B ），右子树中结点的个数是（D ）。
A.20
B.29
C.30
D.35
（10）有n（n>1）个结点的二叉树的先序序列与后序序列相反，则二叉树中除了叶子外，每个结（C ）。
A.仅有左孩子
B.仅有右孩子
C.仅有一个孩子
D.都有两个孩子
（11）判断线索二叉树中p有右孩子的条件是（C ）。
A.p！=NULL
B.p->rchild!=NULL
C.p->rtag==0
D.p->rtag==1
（12）每棵树都能唯一的转化为对应的二叉树，由树所转化的二叉树中，一个结点p的左孩子是它在原树中对应结点的（A ），右孩子是它在原树中对应结点的（C ）。
A.最左孩子
B.最右孩子
C.右临兄弟
D.左邻兄弟
（13）一棵具有124个叶子的完全二叉树，最多有（B ）结点，最少有（A ）结点。
A.247
B.248
C.249
D.250
二、填空题
（1）树中每个结点有（）个孩子，除根之外，每个结点有（）个双亲。
（2）若树中度为1，2，3，4的结点的个数为4，3，2，2，则叶子结点的个数是（14 ）。（3）一棵具有n个结点的二叉树，若叶子结点的个数为m,则度为1的结点的个数是（n-2m+1 ）。
（4）高度为k的二叉树至多有（）个结点，第i层有（）个结点；高度为k的二叉树至少有（K ）个结点。
（5）已知二叉树中有30个叶子，则二叉树中结点个数最少为（59 ）。
（6）一个含有68个结点的完全二叉树，它的高度是（）。
（7）已知一棵完全二叉树第6层有6个叶子结点，则总结点数至少是（），其中叶子结点个数是（）；则总结点数至多是（），其中叶子结点个数是（）。（8）一棵树转化成二叉树后，这棵二叉树的根节点一定没有（右）孩子，若树中有m 个分支结点，则对应二叉树中（m+1 ）个结点没有右孩子。
（9）若用二叉链表表示具有n个结点的二叉树，则有（n+1 ）个空链域。
（10）具有m个叶子结点的赫夫曼树，共有（2m-1 ）个结点。
（11）树的后序序列与对应二叉树的（）遍历序列相同。
（12）线索二叉树的左线索指针指向（），右线索指向（）。
三、简答题
（1）具有n个结点的满二叉树的叶子结点的个数是多少？
（2）已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。
（3）设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。
（4）一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：
①各层的结点数是多少?
②编号为i的结点的双亲结点(若存在)的编号是多少?
③编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
（6）已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索二叉树。
（9）设给定权值集合w={3,5,7,8,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。
（10）假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。
①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构
造)。
②求出每个字符的huffman编码。
一、选择题
（1）有n个顶点的无向完全图具有( A )条边.
A、n(n-1)/2
B、n-1
C、n
D、n(n-1)
（2）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。
A、1/2
B、1
C、2
D、 4
（3）有8个结点的连通图最少有( C )条边。
A、5
B、6
C、7
D、8
（4）有8个结点的强连通图最少有( D )条边。
A、5
B、6
C、7
D、8
（5）下面关于图的存储结构正确的是（）。
A.用邻接矩阵存储图占用的空间大小只与图中的顶点数相关，与边数无关。
B.用邻接矩阵存储图占用的空间大小只与图中的边数相关，与顶点数无关。
C.用邻接表存储图占用的空间大小只与图中的顶点数相关，与边数无关。
D.用邻接矩阵存储图占用的空间大小只与图中的边数相关，与顶点数无关。
（6）下面哪种图的邻接矩阵是对称的（）。
A.AOE
B. AOV
C.无向图
D.有向图
（7）设有向无权图G中有n个顶点，它的邻接矩阵存在于二维数组A中，则顶点i的度为（）。
（8）深度优先遍历类似于二叉树的( )
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
（9）广度优先遍历类似于二叉树的( )
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
（10）连通图的生成树（）。
A.可能不存在
B.只有一棵
C.一棵或多棵
D.一定有多棵
（11）下列关于BFS和DFS生成树论述正确的是（）。
A.BFS生成树的高度 B.BFS生成树的高度<=DFS生成树的高度 C.BFS生成树的高度>DFS生成树的高度 D.BFS生成树的高度>=DFS生成树的高度 （12）G是一个非连通无向图，共有28条边，则该图至少应该有（）个顶点。 A.7 B.8 C.9 D.10 （13）下面关于关键路径叙述是正确的（）。 A.从开始顶点到完成顶点具有最大长度路径，关键路径的长度是完成工期的最短时间。 B.从开始顶点到完成顶点具有最小长度路径，关键路径的长度是完成工期的最短时间。 C.从开始顶点到完成顶点具有最大长度路径，关键路径的长度是完成工期的最长时间。 D.从开始顶点到完成顶点具有最小长度路径，关键路径的长度是完成工期的最长时间。 二、填空题 （1）有n个顶点和e条边的有向图和无向图用邻接表表示，则邻接表边结点的个数分别是（）和（）。 （2）图的邻接表存储顶点的（）邻接点，逆邻接表存储顶点的（）邻接点。 （3）设有一稀疏图G，则G采用（）存储较省空间；设有一稠密图G，则G采用（）存储较省空间。 （4）已知一个图的邻接矩阵，删除所有从第i个顶点出发的方法是（）。 （5）n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（）；若采用邻接表存储时，该算法的时间复杂度为（）。 三、判断题 （1）图的邻接矩阵表示是唯一的。 （2）图的邻接表表示是唯一的。 （3）无向图的邻接矩阵一定是对称的。 （4）有向图的邻接矩阵一定是不对称的。 （5）有向图用邻接表表示，顶点i的出度是对应顶点i链表中结点的个数。 （6）有向图用邻接表表示，顶点i的度是对应顶点i链表中结点的个数。 （7）若从无向图的任意顶点出发，进行一次深度优先搜索，可以访问图中全部顶点，则该图一定是连通的。 （8）在非连通图的遍历中，调用深度优先遍历算法的次数等于连通分量的个数。 （9）在具有n个顶点的强连通图邻接矩阵中，至少有n个小于∞的非零元素。 （10）连通图的生成树一个极小连通子图。 （11）带权连通图的最小生成树是唯一的。 （12）在AOE网中仅存在一条关键路径。 （13）在有向图的邻接矩阵中，主对角线以下的元素均为0，则该图一定有拓扑序列。（14）在图的邻接表表示中，表中有奇数个边结点，则该图一定是有向图。 （15）在AOE网中，任何一个关键活动提前完成，则整个工程的工期都会提前。 （16）图的深度优先遍历序列一定是唯一的。 （17）拓扑排序输出的顶点个数小于图中的顶点个数，则该图一定存在环。 四、简答题 （1）已知图G=(V,E),其中V={a,b,c,d,e} ,E={ 要求： a.画出图； b.给出图的邻接矩阵和邻接表； c.给出图的所有拓扑序列。 （2）已知带权无向图的如下图所示，要求。 a.给出从0点出发深度优先和广度优先的遍历序列； b.画出从0点出发的深度优先生成树和广度优先生成树； c.给出普利姆算法构造最小生成树的过程； d.给出克鲁斯卡尔算法构造最小生成树的过程。 （3）已知有向带权图如下图所示，要求 a.各处图的邻接矩阵； b.利用迪杰斯特拉（Dijkstra）算法求从1到其余各顶点的最短路径； c.利用弗洛伊德（Floyed）算法求任意两顶点间的最小路径。 （4）已知AOE 网如下图所示，要求 a.每个顶点的最早和最晚发生时间； b.工程的最短工期； c.关键路径。 （1）二维数组A[0…5,0…6]的每个元素占有5字节，按列优先存储在起始地址为1000的单元中，则A[5,5]的地址是（）. （2）在三维数组A[8,8,10]采用行优先存储从A[0,0,0]初开始存储，若每个元素的大小为L,则A[3,2,8]的存储地址是（）。 A.A[0,0,0]+198*L B. A[0,0,0]+108*L C.A[0,0,0]+268*L D. A[0,0,0]+13*L （3）n阶矩阵A，采用压缩存储方式，用一维数组F[m]存放该矩阵的下三角元素，则m为（） A.n(n-1) B.n(n-1)/2 C.n(n+1) D.n(n+1)/2 （4）若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组F[n(n+1)/2]中，第一个非零元素a11存于F[0]中，非零元素aij应存放到F[k]中, 则k是( )。 A.(2n-j+1)j/2+i-j B.(2n-j+2)(j-1)/2+i-j C.(2n-i+1)i/2+j-i D. (2n-i+2)i/2+j-I 一、选择题 1．下面哪些操作不属于静态查找表（）。 A）查询某个特定元素是否在表中。 B）检索某个特定元素的属性。 C）插入一个数据元素。 D）建立一个查找表。 2．下面描述不正确的是（） A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。 B）静态查找表中关键字有序时，可用二分查找。 C）分块查找也是一种静态查找表。 D）经常进行插入和删除操作时可以采用二分查找。 3．对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（）。 A）11/8 B）7/4 C）9/4 D）11/42． 4．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（）。 A）R[1]，R[2]，R[3]，R[4] B）R[1]，R[13]，R[2]，R[3] C）R[7]，R[3]，R[5]，R[4] D）R[7]，R[4]，R[2]，R[3] 5．分块查找时确定块的查找可以用顺序查找，也可以用（），而在块中只能是（）。A）静态查找，顺序查找B）二分查找，顺序查找 C）二分查找，二分查找D）散列查找，顺序查找 6．对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（） A）小于B）大于 C）等于 D）不小于 7．设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列（）不可能是在二叉排序树上查找到的序列。 A）2,252,401,398,330, 344,397,363 B）924, 220, 911, 244, 898, 258, 362, 363 C）2, 399, 387, 219, 266, 382, 381, 278, 363 D）925, 202, 911, 240, 912, 245, 363 8．若根据查找表建立长度为m 的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则下一次的散列地址为( ) 。 A）d B）(d+1)%m C）(d+1)/m D）d+19． 9.设哈希表长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 二、简答题 10．已知已下元素序列:{10,18,3,12,6,4,2}要求： a.构造二叉排序树 b.查找6需要比较那些关键字 c.求其平均查找长度 d.画出删除10后的结果 11. 已知散列表的表长为12（0～11），散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。 12．设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。 13. 输入关键字序列为{ 16,3,7,11,9,26,18 }，构造平衡二叉树。 14. 画出长度是10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 15. 设关键字为字符，一组关键字的插入顺序为{C,S,M,T,A,E,P,U,K,N,B},要求： (1)给出从空树开始,顺序插入构造3阶B-树。 (2)分别给出在该树上删除E、P后的结果。 数据结构课后练习题汇总 chapter 4 string 1，multiple choice 1，set string S1 =‘ abcdefg ‘，S2 =‘ pqrst ‘，函数Concat(x，y)返回x 和y字符串的连接字符串，Substr(s，I，J) if length(s)返回字符串256的长度+9 s ，结果字符串 9 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、空字符串和空格相同()A.更正错误 3。如果字符串S1 =‘ABCDEFG ‘，S2 =‘ 9898 ‘，S3 =‘ # # # ‘，S4 =‘ 012345 ‘， replace (S1，SUBSTRA(S1，4，长度(S3))，S3)，CONCAT (S1，SUBSTRA(S4，索引(S2，’ 8 ‘))被执行，结果是() A，ABC###G0123 B，ABCD###2345 C，ABC###G2345 D，ABC # # # # 2345e，ABC###G1234 F，ABCD###1234 G，ABC # # 01234 4 4，字符串是特殊的线性表，其特殊性如(d)所示 A，可以顺序存储b，数据元素是字符c，可以存储d链接，数据元素可以是多个字符 5，并且具有两个字符串p和q。用于寻找q在p中首先出现的位置 的操作被称为() A，连接b，模式匹配c，子字符串d，字符串长度6，下列关于字符串的陈述中哪一项不正确？() a。字符串是字符b的有限序列，空字符串是由空格 c组成的字符串。模式匹配是字符串的一个重要操作。字符串可以顺序存储，也可以使用链存储。字符串的长度引用了() a。字符串中包含的不同字母的数量b .字符串中包含的字符的数量c .字符串中包含的不同字符的数量d .字符串中包含的非空格字符的数量 2，判断问题 1，并且在最坏的情况下子串定位函数的时间复杂度是O(n*m ),因此子串定位函数没有实用价值2.有两个字符串P和Q，其中Q是P的子串。 算法将P中第一个出现的Q作为子串Q在P中的位置，称为匹配。3和KMP算法的最大特点是不需要检索指示主字符串的指针 3，填写问题 1，集S =‘ I _ AM _ A _ TEACHER ‘，其长度为()2、空字符串为(零字符串)，其长度为() 3，集合S1 = ‘好’，S2 =‘ ︼’，S3 = ‘再见！，S1、S2和S3连接的结果是() 20 数据结构试题及答案 一、单项选择题 (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=０；s＝０; wｈｉlｅ(s 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 .没有共同点 1.以下与数据的存储结构无关的术语是（ c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C ） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（D ） D、8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 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＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；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。 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 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.以顺序方式存储，且数据元素有序 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 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、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】 第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={ D 一、单项选择题 1、在以下的叙述中，正确的是( B )。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。 A. qu->front==qu->rear B. qu->front!=qu->rear C. qu->front=(qu->rear+1)%m0 D. qu->front!=(qu->rear+1)%m0 3、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行( C )。 A. hs->next=s; B. s->next=hs->next;hs->next=s; C. s->next=hs;hs=s; D. s->next=hs;hs=sh->next 4、串是一种特殊的线性表，其特殊性体现在（ B ）。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 5、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素a i,j(i≥j), 在一维数组B的下标位置k的值是（ B ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 6、将递归算法转换成对应的非递归算法时，通常需要使用( A )。 A. 栈 B. 队列 C. 链表 D. 树 7、树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论___A_是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以下都不对 8、对一个满二叉树，m个树叶，n个结点，深度为h，则( D )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 9、具有7个顶点的无向图至少应有( A )条边才能确保是一个连通图。数据结构课后练习题汇总
数据结构试题库答案
2017年数据结构期末考试题及答案A
《数据结构》期末复习题答案
数据结构题库教材
数据结构复习资料,java数据结构期末考试
数据结构习题与答案
数据结构期末考试题及标准答案
数据结构相关题库及答案
《数据结构》期末考试题及答案
数据结构习题库汇总
《数据结构》期末考试试卷
数据结构期末考试试题含答案
数据结构题库汇总
数据结构期末考试试题及答案
数据结构期末考试试题及答案
数据结构考试题库含参考答案
数据结构课后习题详解(超完整,超经典)
数据结构期末试题及答案
相关文档
- (完整word版)数据结构期末复习题
- 数据结构期末考试复习试题(整理完的)
- 数据结构期末习题答案
- 数据结构期末考试试题
- 西安电子科技大学期末数据结构试题及详细答案
- 2017《数据结构》期末考试试题及答案
- 数据结构期末复习题及答案3剖析
- 数据结构期末考试试题及答案
- 数据结构期末复习题
- 大学数据结构期末考试试题(有答案)
- 数据结构期末考试试题及答案
- 数据结构学生期末复习卷习题答案
- 数据结构期末考试试题及答案
- 《数据结构》期末考试复习题及参考答案
- 大学数据结构期末考试试题(有答案)
- 2017《数据结构》期末考试试题及答案
- 数据结构期末考试复习题及答案(20210228233329)
- 2017数据结构期末考试试题及答案
- (完整版)数据结构期末考试试题及答案
- 数据结构期末测试题及答案