数据结构0章习题文档格式.docx
《数据结构0章习题文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构0章习题文档格式.docx（25页珍藏版）》请在冰点文库上搜索。
i<
n;
i++）
for（j=0;
j<
m;
j++）
a[i][j]=0;
（3）s=0;
fori=0;
for（j=0;
s+=B[i][j];
sum=s;
（4）i=1;
while（i<
=n）
i=i*3;
（5）x=0;
for（i=1;
for（j=1;
=n-i;
x++;
（6）x=n;
//n>
1
y=0;
while（x≥（y+1）*（y+1））
y++;
第2章线性表
1．选择题
（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110B．108C．100D．120
（2）在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8B．63.5C．63D．7
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续或不连续都可以
（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂
（7）单链表的存储密度（）。
A．大于1B．等于1C．小于1D．不能确定
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．nB．2n-1C．2nD．n-1
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。
A．n-iB．n-i+1C．n-i-1D．i
（10）线性表L=（a1，a2,……an），下列说法正确的是（）。
A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
（11）若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。
A．O
（1）B．O（n）C．O（n2）D．O（nlog2n）
（12）以下说法错误的是（）。
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
（13）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。
A．s->
next=p+1;
p->
next=s;
B．（*p）.next=s;
（*s）.next=（*p）.next;
C．s->
next=p->
next;
next=s->
D．s->
（14）在双向链表存储结构中，删除p所指的结点时须修改指针（）。
A．p->
next->
prior=p->
prior;
prior->
B．p->
prior=p;
C．p->
next=p;
D．p->
（15）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。
next=q;
q->
prior=q;
q->
C．q->
D．q->
2．算法设计题
（1）将两个递增的有序链表合并为一个递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
表中不允许有重复的数据。
（4）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
（5）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
（7）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O（n）、空间复杂度为O
（1）的算法，该算法删除线性表中所有值为item的数据元素。
第3章栈和队列
（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．iB．n-iC．n-i+1D．不确定
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-fB．（n+f-r）%nC．n+r-fD．（n+r-f）%n
（4）链式栈结点为：
（data,link），top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->
data;
top=top->
link；
B．top=top->
link;
x=top->
C．x=top;
D．x=top->
（5）设有一个递归算法如下
intfact（intn）{
//n大于等于0
if（n<
=0）return1;
elsereturnn*fact（n-1）;
}
则计算fact（n）需要调用该函数的次数为（）。
A．
n+1
B．
n-1
C．n
D．n+2
（6）栈在
（）中有所应用。
A．递归调用B．函数调用C．表达式求值D．前三个选项都有
（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）。
A．队列B．栈C．线性表D．有序表
（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A．2B．3C．4D．6
（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（ ）。
A．top不变B．top=0C．top--D．top++
（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构B．队列
C.线性表的链式存储结构D.栈
（11）用链接方式存储的队列，在进行删除运算时（ ）。
A.仅修改头指针B.仅修改尾指针
C.头、尾指针都要修改D.头、尾指针可能都要修改
（12）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear=rear+1B.rear=（rear+1）%（m-1）
C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）
（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A.（rear+1）%n==frontB.rear==front
C．rear+1==frontD.（rear-l）%n==front
（14）栈和队列的共同点是（ ）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
（15）一个递归算法必须包括（ ）。
A.递归部分B.终止条件和递归部分
C.迭代部分D.终止条件和迭代部分
2.算法设计
（1）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。
试写一个算法判定给定的字符向量是否为回文。
（提示：
将一半字符入栈）
（2）设从键盘输入一整数的序列：
a1,a2,a3，…，an，试编写算法实现：
用栈结构存储输入的整数，当ai≠-1时，将ai进栈；
当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
（3）假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
①下面所示的序列中哪些是合法的？
A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO
②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
（4）已知Ackermann函数定义如下:
①写出计算Ack（m,n）的递归算法，并根据此算法给出出Ack（2,1）的计算过程。
（5）已知f为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的算法：
①求链表中的最大整数；
②求链表的结点个数；
③求所有整数的平均值。
第4章串
（1）串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符
C．可以链式存储D．数据元素可以是多个字符若
（2）串下面关于串的的叙述中，（）是不正确的？
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
（3）串“ababaaababaa”的next数组为（）。
A．0B．0C．0D．02345
（4）串“ababaabab”的nextval为（）。
A．0B．0C．0D．0
（5）串的长度是指（）。
A．串中所含不同字母的个数B．串中所含字符的个数
C．串中所含不同字符的个数D．串中所含非空格字符的个数
2．简答题
（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next函数值。
第5章数组与广义表
一、选择题
（1）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。
A．808B．818C．1010D．1020
（2）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225
（3）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40
（4）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[1..（n（n+1））/2]中，则在B中确定aij（i<
j）的位置k的关系为（）。
A．i*（i-1）/2+jB．j*（j-1）/2+iC．i*（i+1）/2+jD．j*（j+1）/2+i
（5）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A．i（i-1）/2+jB．j（j-1）/2+iC．i（j-i）/2+1D．j（i-1）/2+1
（6）设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（）。
A．（i-1）*n+jB．（i-1）*n+j-1C．i*（j-1）D．j*m+i-1
（7）数组A[0..4,-1..-3,5..7]中含有元素的个数（）。
A．55B．45C．36D．16
（8）广义表A=（a,b,（c,d）,（e,（f,g））），则Head（Tail（Head（Tail（Tail（A）））））的值为（）。
A．（g）B．（d）C．cD．d
（9）广义表（（a,b,c,d））的表头是（），表尾是（）。
A．aB．（）C．（a,b,c,d）D．（b,c,d）
（10）设广义表L=（（a,b,c）），则L的长度和深度分别为（）。
A．1和1B．1和3C．1和2D．2和3
二、问答题
（1）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。
求：
①存放该数组所需多少单元？
②存放数组第4列所有元素至少需多少单元？
③数组按行存放时，元素A[7,4]的起始地址是多少？
④数组按列存放时，元素A[4,7]的起始地址是多少？
（2）请将香蕉banana用工具H（）—Head（），T（）—Tail（）从L中取出。
L=（apple,（orange,（strawberry,（banana））,peach）,pear）
第6章树和二叉树
（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A．唯一的Ｂ．有多种
C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子
（2）由3个结点可以构造出多少种不同的二叉树？
（）
A．2B．3C．4D．5
（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。
A．250B．500C．254D．501
（4）一个具有1025个结点的二叉树的高h为（）。
A．11B．10C．11至1025之间D．10至1024之间
（5）深度为h的满m叉树的第k层有（）个结点。
（1=<
k=<
h）
A．mk-1B．mk-1C．mh-1D．mh-1
（6）利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子C．空D．非空
（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序B．中序C．后序D．按层次
（9）在下列存储形式中，（）不是树的存储形式？
A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法
（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
A．所有的结点均无左孩子B．所有的结点均无右孩子
C．只有一个叶子结点D．是任意一棵二叉树
（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A．空或只有一个结点B．任一结点无左子树
C．高度等于其结点数D．任一结点无右子树
（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。
A．X的双亲B．X的右子树中最左的结点
C．X的左子树中最右结点D．X的左子树中最右叶结点
（13）引入二叉线索树的目的是（）。
A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲D．使二叉树的遍历结果唯一
（14）线索二叉树是一种（）结构。
A．逻辑B．逻辑和存储C．物理D．线性
（15）设F是一个森林，B是由F变换得的二叉树。
若F中有n个非终端结点，则B中右指针域为空的结点有（）个。
A．n-1B．nC．n+1D．n+2
2．应用题
（1）试找出满足下列条件的二叉树
①先序序列与后序序列相同②中序序列与后序序列相同
③先序序列与中序序列相同④中序序列与层次遍历序列相同
（2）设一棵二叉树的先序序列：
ABDFCEGH，中序序列：
BFDAGEHC
①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
①试为这8个字母设计赫夫曼编码。
②试设计另一种由二进制表示的等长编码方案。
③对于上述实例，比较两种方案的优缺点。
第7章 图
（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A．1/2B．1C．2D．4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1/2B．1C．2D．4
（3）具有n个顶点的有向图最多有（）条边。
A．nB．n（n-1）C．n（n+1）D．n2
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。
A．nB．2（n-1）C．n/2D．n2
（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A．7B．8C．9D．10
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向
（7）下面（ ）算法适合构造一个稠密图G的最小生成树。
A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法
（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A．栈B.队列C.树D．图
（9）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。
A．栈B.队列C.树D．图
（10）深度优先遍历类似于二叉树的（）。
A．先序遍历B．中序遍历C．后序遍历D．层次遍历
（11）广度优先遍历类似于二叉树的（）。
（12）图的BFS生成树的树高比DFS生成树的树高（）。
A．小B．相等C．小或相等D．大或相等
A．0243156
B．0136542
C．0134256
D．0361542
（13）已知图的邻接矩阵如图7.1所示，则从顶点0出发按深度优先遍历的结果是（）。
图7.1邻接矩阵
（14）已知图的邻接表如图7.2所示，则从顶点0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。
A．0132B．0231
C．0321D．0123
图7.2邻接表
（15）下面（）方法可以判断出一个有向图是否有环。
A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径
（1）已知如图7.3所示的有向图，请给出：
①每个顶点的入度和出度；
②邻接矩阵；
③邻接表；
④逆邻接表。
图7.3有向图
（2）已知如图7.4所示的无向网，请给出：
①邻接矩阵；
②邻接表；
③最小生成树
图7.4无向网
（3）已知图的邻接矩阵如7.5所示。
试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
图7.5邻接矩阵
（4）有向网如图7.6所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表7.1。
图7.6有向网
终点
i=1
i=2
i=3
i=4
i=5
i=6
b
c
d
e
f
g
vj
S
终点集
（5）试对图7.7所示的AOE-网：
①求这个工程最早可能在什么时间结束；
②求每个活动的最早开始时间和最迟开始时间；
图7.7AOE-网
③确定哪些活动是关键活动
第9章查找
（1）对n个元素的表做
升级会员 