河北工业大学考研资料数据结构习题1答案.docx
《河北工业大学考研资料数据结构习题1答案.docx》由会员分享，可在线阅读，更多相关《河北工业大学考研资料数据结构习题1答案.docx（29页珍藏版）》请在冰点文库上搜索。
河北工业大学考研资料数据结构习题1答案
一填空
1.衡量算法效率的两个重要指标称为算法的______时间复杂度_和___空间复杂度
2.一个算法应具有有穷性，确定性，可行性，输入和输出这五个特性。
3.线性表的长度是指___表中元素的个数___。
4.在线性表的顺序存储中，元素之间的逻辑关系是通过元素存储的相对位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过相关元素的存储位置决定的。
5在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向其直接后继结点。
二、判断题
1．线性表的逻辑顺序与存储顺序总是一致的。
（FALSE）
2．顺序存储的线性表可以按序号随机存取。
（TRUE）
3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（FALSE）
4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（TRUE）
5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
（TRUE）
6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（TRUE）
三、单选题（请从下列A，B，C，D选项中选择一项）
1．线性表是（）。
（A）一个有限序列，可以为空；（B）一个有限序列，不能为空；
（C）一个无限序列，可以为空；（D）一个无序序列，不能为空。
答：
A
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（）个元素。
（A）n/2（B）（n+1）/2（C）（n–1）/2（D）n
答：
A
3．线性表采用链式存储时，其地址（）。
（A）必须是连续的；（B）部分地址必须是连续的；
（C）一定是不连续的；（D）连续与否均可以。
答：
D
4．用链表表示线性表的优点是（）。
（A）便于随机存取
（B）花费的存储空间较顺序存储少
（C）便于插入和删除
（D）数据元素的物理顺序与逻辑顺序相同
答：
C
5.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。
（A）单链表
（B）双链表
（C）单循环链表
（D）带头结点的双循环链表
答：
D
6.循环链表的主要优点是（）。
（A）不再需要头指针了
（B）已知某个结点的位置后，能够容易找到他的直接前趋
（C）在进行插入、删除运算时，能更好的保证链表不断开
（D）从表中的任意结点出发都能扫描到整个链表
答：
D
7.单链表中，增加一个头结点的目的是为了（）。
（A）使单链表至少有一个结点（B）标识表结点中首结点的位置
（C）方便运算的实现（D）说明单链表是线性表的链式存储
答：
C
8.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。
（A）单链表（B）顺序表（C）双链表（D）单循环链表
答：
B
四、简答题
1何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
2在顺序表中插入和删除一个结点需平均移动多少个结点?
具体的移动次数取决于哪两个因素?
答：
在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。
删除一个结点需平均移动（n-1）/2个结点。
具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。
i越接近n则所需移动的结点数越少。
3为什么在单循环链表中设置尾指针比设置头指针更好?
答：
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O
（1）。
若用头指针来表示该链表，则查找终端结点的时间为O（n）。
五、分别设计算法，实现线性表的顺序存储结构和链式存储结构的原地置逆。
顺序存储结构的原地置逆
typedefstruct{
ElemType*elem;//存储空间基址
intlength;//线性表的实际长度
intlistsize；//当前分配的存储容量，
//（以sizeof（ElemType）为单位
}sqList;
voidreverse（SqList&A）{
//顺序表的就地逆置
inti;intj;
for（i=1,j=A.length;i A.elem[i]<->A.elem[j];
}//reverse
链式存储结构的原地置逆。
算法：
ＴypedefstructLNode{
ElemTypedata;//结点值
structLNode*next;//指针域，存储下一个结点的地址
}LNode,*LinkList;
voidReverseList（LinkList&L）
{//将L所指的带头结点的单链表逆置
if（L->next&&L->next->next）{//当链表不是空表或单结点时
p=L->next;q=p->next;p->next=NULL;
//将开始结点变成终端结点
while（q）{//每次循环将后一个结点变成开始结点
p=q;q=q->next;p->next=L->next;L->next=p;}
}
}
作业
2.1,2.2答案见习题册后面答案
2.6答案：
解答：
a.（4）
（1）
b.（7）（11）（8）（4）
（1）
c.（5）（12）
d.（11）（9）
（1）（6）或（11）（9）（4）
（1）
2.7答案：
解答：
a.（11）（3）（4）
b.（10）（12）（8）（10）（3）（4）
c.（10）（12）（7）（3）（4）
d.（12）（11）（3）（14）
e.（9）（11）（3）（14）
2.8
已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列是-----------。
b．在P结点前插入S结点的语句序列是-----------。
c．删除P结点的直接后继结点的语句序列是----------。
d．删除P结点的直接前驱结点的语句序列是----------。
e．删除P结点的语句序列是------------。
（1）P->next=P->next->next;（10）P->prior->next=P;
（2）P->prior=P->prior->prior;（11）P->next->prior=P;
（3）P->next=S;（12）P->next->prior=S;
（4）P->prior=S;（13）P->prior->next=S;
（5）S->next=P;（14）P->next->prior=P->prior
（6）S->prior=P;（15）Q=P->next;
（7）S->next=P->next;（16）Q=P->prior;
（8）S->prior=P->prior;（17）free（P）;
（9）P->prior->next=p->next;（18）free（Q）;
解答：
a.（12）（7）（3）（6）3必须在12和7的后面，其余的顺序可变
b.（13）（8）（4）（5）同上
c.（15）
（1）（11）（18）不可变
d.（16）
（2）（10）（18）不可变
e.（9）（14）（17）
2.31答案：
ＴypedefstructLNode{
ElemTypedata;//结点值
structLNode*next;//指针域，存储下一个结点的地址
}LNode,*LinkList;
StatusDelete_Pre（linklistsElemType＆e）
//删除单循环链表中结点s的直接前驱
{
p=s;
while（p->next->next!
=s）p=p->next;
//找到s的前驱的前驱p
q=p->next;p->next=s;
e=q->data;
free（q）;
returnOK;
}//Delete_Pre
4章
一、填充题
1、一个串中任意个的字符组成的子序列称为该串的子串。
连续
2、串的静态存储结构中的两种不同的存储方式分别是格式和格式。
非紧缩紧缩
3、两个串的相等，是指两个两串的相等，相同。
长度对应位置的字符
4、已知二维数组A有m行n列，采用行优先方式存储，每个数据元素占k个存储单元，并且第一个元素的存储地址是LOC（A[1,1]），则数据元素A[i,j]的地址是。
LOC（A[1,1]）+（n（i-1）+（j-1））k
5、有一个10阶的对称矩阵，采用以行优先的压缩存储方式，已知元素A[1,1]的地址为1，则元素A[8,5]的地址是，元素A[5,8]的地址是。
3333
6、广义表（a,（a,b）,d,e,（（i,j）,k））的长度是，深度是。
53
二、单选题
1、给出字符串A=’abcd’，它的子串个数是。
A、10B、9
C、11D、14
C
2、给出两个串A=’ABCDE’，B=’ABCdE’，它们的关系是不是。
A、B串大于A串B、B串等于A串
C、B串小于A串D、B串是A串的子串
A
3、设有两个串A和B，求B在A中首次出现的位置的操作称作。
A、连接B、求串长
C、模式匹配D、求子串
C
4、设串S1=’ABCDEFG’，串S2=’PQRST’，函数con（x,y）返回x和y串的连接串，函数subs（s,i,j）返回串s的从序号i的字符开始的j个字符组成的子串，而函数len（s）则返回串s的长度。
那么，表达式con（subs（S1,2,len（S2））,subs（S1,len（S2）,2））的结果串是。
A、BCDEFB、BCDEFG
C、BCPQRSTD、BCDEFEF
D
5、数组通常具有的两种基本操作是。
A、建立与删除B、索引与修改
C、查找与修改D、查找与索引
C
6、在数组A中，每个数据元素A[i,j]的长度为3个字节，数组A的行下标i从1到8，而列下标j从1到10，从首地址SA开始连续存放在存储器中，若该数组按行优先存放时，数据元素A[8,5]的起始地址为。
A、SA+141B、SA+144
C、SA+225D、SA+222
D
7.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（E）。
A.13B.33C.18D.40E.12
8.将一个A[100][100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（A）。
A.198B.195C.197
9.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B［1..（n（n+1））/2］中，则在B中确定aij（iA.i*（i-1）/2+jB.j*（j-1）/2+iC.i*（i+1）/2+jD.j*（j+1）/2+i
10.对稀疏矩阵进行压缩存储目的是（C）。
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
11.已知广义表LS＝（（a,b,c）,（d,e,f））,运用head和tail函数取出LS中原子e的运算是（C）。
A.head（tail（LS））B.tail（head（LS））
C.head（tail（head（tail（LS）））D.head（tail（tail（head（LS））））
12.广义表（a,（b,c）,d,e）的表头为（A）。
A.aB.a,（b,c）C.（a,（b,c））D.（a）
4.24
voidHString_Concat（HString&t,HStrings1,HStrings2）
//将堆结构表示的串s1和s2连接为新串t
{
if（t.ch）free（t.ch）;
if（!
（t.ch=（char*）malloc（（s1.length+s2.length）*sizeof（char））））;
exit（OVERFLOW）;
for（i=1;i<=s1.length;i++）t.ch[i-1]=s1.ch[i-1];
for（j=1;j<=s2.length;j++,i++）t.ch[i-1]=s2.ch[j-1];
t.length=s1.length+s2.length;
}//HString_Concat
5.23
typedefstruct{
intj;
inte;
}DSElem;typedefstruct{
DSElemdata[MAXSIZE];
intcpot[MAXROW];//这个向量存储每一行在二元组中的起始位置
intmu,nu,tu;
}DSMatrix;//二元组矩阵类型
StatusDSMatrix_Locate（DSMatrixA,inti,intj,int&e）
//求二元组矩阵的元素A[i][j]的值e
{
for（s=A.cpot[i];s=j;s++）;//注意查找范围
if（s {
e=A.data[s];
returnOK;
}
returnERROR;
}//DSMatrix_Locate
第7章图
一、选择题
1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A）O（n）B）O（n+e）C）O（n*n）D）O（n*n*n）
【答案】B
2．设无向图的顶点个数为n，则该图最多有（ ）条边。
A）n-1B）n（n-1）/2C）n（n+1）/2D）n2
【答案】B
3．连通分量指的是（ ）
A）无向图中的极小连通子图
B）无向图中的极大连通子图
C）有向图中的极小连通子图
D）有向图中的极大连通子图
【答案】B
4．n个结点的完全有向图含有边的数目（ ）
A）n*nB）n（n+1）C）n/2D）n*（n-1）
【答案】D
5．关键路径是（ ）
A）AOE网中从源点到汇点的最长路径
B）AOE网中从源点到汇点的最短路径
C）AOV网中从源点到汇点的最长路径
D）AOV网中从源点到汇点的最短路径
【答案】A
6．有向图中一个顶点的度是该顶点的（ ）
A）入度B）出度C）入度与出度之和D）（入度+出度）/2
【答案】C
7．有e条边的无向图，若用邻接表存储，表中有（ ）边结点。
A）eB）2eC）e-1D）2（e-1）
【答案】B
8．实现图的广度优先搜索算法需使用的辅助数据结构为（ ）
A）栈B）队列C）二叉树D）树
【答案】B
9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（ ）
A）栈B）队列C）二叉树D）树
【答案】A
10．存储无向图的邻接矩阵一定是一个（ ）
A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵
【答案】C
11．在一个有向图中所有顶点的入度之和等于出度之和的（ ）倍
A）1/2B）1C）2D）4
【答案】B
12．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）
A）O（n）B）O（n+e）C）O（n2）D）O（n3）
【答案】B
13．下列关于AOE网的叙述中，不正确的是（ ）
A）关键活动不按期完成就会影响整个工程的完成时间
B）任何一个关键活动提前完成，那么整个工程将会提前完成
C）所有的关键活动提前完成，那么整个工程将会提前完成
D）某些关键活动提前完成，那么整个工程将会提前完成
【答案】B
14．具有10个顶点的无向图至少有多少条边才能保证连通（ ）
A）9B）10C）11D）12
【答案】A
15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）
A）eB）2eC）n2-eD）n2-2e
【答案】D
16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表头向量的大小为。
A、nB、n+1
C、n-1D、n+e
【答案】A
二、填空题
1．无向图中所有顶点的度数之和等于所有边数的_____________倍。
【答案】2
2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。
【答案】
（1）n（n-1）/2
（2）n（n-1）
3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。
【答案】n-1
5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。
【答案】
（1）O（n2）
（2）O（n+e）
6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。
【答案】
（1）e
（2）2e
7．在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。
【答案】
（1）出边
（2）入边
8．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。
【答案】
（1）O（n）
（2）O（e）
9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。
【答案】
（1）n
（2）n-1
10．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。
【答案】
（1）O（n2）
（2）O（eloge）
11.假设图G中含有n个顶点，e条边，且知每个顶点的度数为di，则它们三者之间满足的关系为：
。
【答案】e=1/2∑di
12.我们把图中所有顶点加上遍历时经过的所有边构成的子图称为。
【答案】生成树
13、有n个顶点的无向图，其边数最大可达，像这样的有最大边数的无向图通常被称为。
【答案】n（n-1）/2完全无向图
14、树被定义为连通而不具有的（无向）图。
【答案】回路
15、对于一个图G的遍历，通常有两种方法，它们分别是和。
【答案】深度优先法广度优先法
16.AOV网中，结点表示活动，边表示活动的先后顺序，AOE网中，结点表示事件，边表示活动.
7-16试对右图所示的AOE网络，解答下列问题。
（1）这个工程最早可能在什么时间结束。
（2）求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。
（3）求每个活动的最早开始时间e（）和最迟开始时间l（）。
（4）确定哪些活动是关键活动。
画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。
【解答】
按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。
然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?
来确定关键活动，从而确定关键路径。
1
2
3
4
5
6
Ve
0
19
15
29
38
43
Vl
0
19
15
37
38
43
<1,2>
<1,3>
<3,2>
<2,4>
<2,5>
<3,5>
<4,6>
<5,6>
e
0
0
15
19
19
15
29
38
l
17
0
15
27
19
27
37
38
l-e
17
0
0
8
0
12
8
0
此工程最早完成时间为43。
关键路径为<1,3><3,2><2,5><5,6>
9章
一、填充题
1、折半查找法适合于的数据序列。
有序
2、查找表的两种基本类型分别是和。
静态查找表动态查找表
3、Hash表查找要研究的两个主要问题分别是和。
均匀性冲突的解决
4、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。
哈希表查找法
5、折半查找的存储结构仅限于，而且是。
顺序存储结构有序的
6、在哈希函数H（key）=keyMODp中，p应取。
素数
7、假设我们在有20个数据元素的有序线性表上实施折半查找，则比较五次查找成功的结点数为，平均查找长度为。
53.7（可以画出折半查找判定树）
8、在哈希表存储中，装填因子的值越大，则，反之装填因子的值越小，则。
存取元素时发生冲突的可能性就越大存取元素时发生冲突的可能性就越小
二、单选题
1、对个结点的线性表进行查找，用顺序查
升级会员 