1 / 20
文档名称:

数据结构专升本模拟题及参考答案.docx

格式:docx   大小:313KB   页数:20页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构专升本模拟题及参考答案.docx

上传人:森林书屋 2022/12/7 文件大小:313 KB

下载得到文件列表

数据结构专升本模拟题及参考答案.docx

文档介绍

文档介绍:该【数据结构专升本模拟题及参考答案 】是由【森林书屋】上传分享,文档一共【20】页,该文档可以免费在线阅读,需要了解更多关于【数据结构专升本模拟题及参考答案 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。东北农业大学网络教育学院
数据结构专升本作业题
作业题(一)
一、单项选择题
( )两大类。
、静态结构 、链式结构
、非线性结构 、构造型结构
( )
、删除不需要移动元素

( )。
For(i=1;i<=n;i++)
For(j=1;j<=I;j++)
For(k=1;k<=j;k++)
X=x+1;
(1)

(n)
(n2)

(n3)
,

若要在

p所指向的结点之前插入一个新结点,

则需要相继修改(

)
个指针域的值。






5、一个顺序存储线性表的第一个元素的存储地址是

90,每个元素的长度是

2,则第

6个元素的存储地址
是(

)。






6、判定一个栈

s(最多元素为

m0)为空的条件是(

)。
-〉top!=-〉top!=m07、循环队列用数组

A[m](下标从

0到

-〉top==0
-〉top==m0
m-1)存放其元素值,已知其头尾指针分别是

front

和rear,则当前
队列中的元素个数是(

)。
A.(rear-front+m

)%m

-front+1
-front-1

D.

rear-front
8、设有两个串

S1与

S2,求串

S2在

S1中首次出现位置的运算称作(

)。






9、设串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))
的结果是(

)。






10、数组常用的两种基本操作是(

)。






二、填空题
所谓稀疏矩阵指的是________且分布没有规律。
队列是________的线性表,其运算遵循________的原则。
空格串是________________________________。


________。
5、设图

G有

n个顶点和

e条边,则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度


,而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为

,图的深度或广
度优先搜索遍历时的空间复杂度均为


6、一个图的 表示法是唯一的,而 表示法是不唯一的。
三、算法
设二叉树采用二叉链表结构,试设计一个算法统计给定二叉树中的一度结点数目。
四、应用题
1、对关键字无序序列 (36,25,48,12,65,43,20,58)进行直接选择排序,请写出每一趟排序的结果。
10分)
2、对无向带权图,用克鲁斯卡尔算法构造最小生成树。
(10分)
9
A
3
C
20
8
D
B
5
E
1
6
4
2
G
F
3、已知记录关键字集合为(53,17,19,61,98,75,79,63,46,49 )要求散列到地址区间
100,101,102,103,104,105,106,107,108,109)内,若产生冲突用开型寻址法的线性探测法解决。要求写出
选用的散列函数;形成的散列表;计算出查找成功时平均查找长度与查找不成功的平均查找长度。 (设等
概率情况)
4、设被查找文件有 4095个记录,对每个记录查找记录概率相等,若采用顺序查找,成功查找平均比较次
数为多少
作业题(二)
、单项选择题
1.
有六个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列(
)



2.
栈和队都是(
)




3、顺序查找法适合于存储结构为(
)的线形表。




4、分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是
()。
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)
5、折半查找的平均比较次数为(
)。



(n+1)
6、当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的
查找速度(

)






7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法,从顶点

v1

出发,所得
到的顶点序列是( )。
,v2,v3,v5,v4 ,v2,v3,v4,v5
,v3,v4,v5,v2 ,v4,v3,v5,v2
8、为了方便地对图状结构的数据进行存取操作,则其中数据存储结构宜采用( )。




9、在一个具有n个顶点的有向图中,若所有顶点的出度之和为
s,则所有顶点的入度之和为(
)。

-1
+1

10、如图所示,给出由
7个顶点组成的无向图。从顶点
A出发,对它进行深度优先搜索得到的顶点序列是
(
)。




二、填空题
1.
设n0为哈夫曼树的叶子结点数目,则该哈夫曼树共有
________个结点。
2.
有数据WG={7,19,2,6,32,3,21,10},则所建Huffman树的树高是________,带权路径长度WPL
为________。


k,最后一层结点数

>2,则该二叉树的高度为

________________。
,若线性表中共有625个元素,查找每个元素的概率相同,点所在的块时,每块应分个结点最佳。

假设采用顺序查找来确定结
5、设G为具有
6、哈夫曼树(

N个顶点的无向连通图,则HuffmanTree)又称

G中至少有 条边。
。它是n个带权叶子结点构成的所有二叉树中,带权路径长


WPL


7、树的先序遍历过程如下:若树为空,则进行空操作;若树非空,则访问树的 ;依次先序遍历树
的 。
三、应用题
1、给定权值集合 {1,4,2,6,9,},构造相应的哈夫曼树 ,并计算它的带权路径长度。
2、对关键字序列 {10,6,3,2,5,4},构造一棵平衡二叉(排序)树并画图(要求画出建树过程) 。
3、设有一个有序文件,其中各记录的关键字为( 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15),
当用折半查找算法查找关键字为 3,8,19时,其比较次数分别为多少
4、对有五个结点 {A,B,C,D,E}的图的邻接矩阵,
0 100 30 10
0
60 0 20
10 0
0
1).画出逻辑图;
2).画出图的十字链表存储;
3).基于邻接矩阵写出图的深度、广度优先遍历序列;
4).计算图的关键路径。
作业题(三)
一、单项选择题
( )








A[i,j],数组的每个元素长度为

3字节,

i的值为

1到

8

,j

的值为

1到

10,数组从内存首地
址BA开始顺序存放,当用以列为主存放时,元素

A[5,8]的存储首地址为

(

)。
+141

+180

+222

+225
( )。


( )。


( )。
Intfun(intn)
{inti=1,s=1;While(s<n)S+=++I;
ReturnI;
}
(n/2)

(lbn)
(n)

()
(

)。
,可以为空 ,不能为空
,可以为空 ,不能为空
带头结点的单链表L为空的判定条件是()。
==NULL

-〉next==NULL
-〉next==L

!=NULL


n的线性表中,删除值为

x的元素时需要比较元素和移动元素的总次数为(

)。
A.(n+1)/2




+1
一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址是()。








i个结点及其前驱,则采用(

)存储方式最节省时间。






二、填空题


2的二叉树的结点数至少有

________个,高度为

3的二叉树的结点数至少有

________个。
(

8,11,15,19,25,26,30,33,42,48,50

)中,用折半查找关键字值

20,需做的关键字比较次数为
________。


n个顶点的无向图中,每个顶点的度最大可达

________。
A=((a,b,c),(d,e,f)),则广义表运算 head(tail(tail(A)))= 。
5、数组(Array)是n(n≥1)个 的有序组合,数组中的数据是按顺序存储在一块
存储单元中。


采用顺序存储结构表示三元组表(TripleTable),来实现对稀疏矩阵的一种压缩存储形式,就称
为 ,简称 表。
运算是矩阵运算中最基本的一项,

它是将一个

的矩阵变成另外一个

的矩阵,同时使
原来矩阵中元素的行和列的位置互换而值保持不变。
三、应用题
1、对于下图所示的二叉树,画出二叉链表存储结构图。
2、请画出下图所示的树所对应的二叉树。
A
B C D
E
已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小树(假设以①为起点,试画出构造过程)。
已知完全二叉树的第8层有8个结点,则其叶子结点是多少
画出如图所示中树的二叉树的表示形式。
作业题(四)
一、单项选择题
1.
将两个各有n个元素的有序表归并成一个有序表,其最少得比较次数是(
)。

-1

-1
2.
一个有n个顶点的无向连通图,它所包含的连通分量个数为(
)。



+1
3.
数据文件的基本操作中最重要的操作是(
)。




4.
对关键码序列28,16,32,12,60,2,5,72快速排序,从小到大一次划分结果为(
)。
A.(2,5,12,16)26(60,32,72)
B.(5,16,2,12)28(60,32,72)
C.(2,16,12,5)28(60,32,72)
D.(5,16,2,12)28(32,60,72)
5.
如果只想得到1000
个元素组成的序列中第
5个最小元素之前的部分排序的序列,
用(
)方法最快。




(
)。


7.
二叉树的第I层上最多含有结点数为(
)

-1--1

-1
,长度为m,则入队时的操作为(
)。
=rear+1
=(rear+1)mod(m-1)
=(rear+1)=(rear+1)mod(m+1)
9.
广义表满足Head(A)=Tail(A),则A为(
)。
A.()
B.(())
C.((),())
D.((),(),())
在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的
结点数为()个。




二、填空题
在一个循环队列中,队首指针指向队首元素的_________。
2.
数组中每一个数据通常称为
,
用下标区分,其中下标的个数由数组的
决定。
3.
一个图的
表示法是唯一的,而
表示法是不唯一的。
4.
在一个10阶的B-树上,每个数根结点中所含的关键字数目最多允许
个,最少允许

5.
对关键字序列(
52,80,63,44,48,91)进行一趟快速排序之后的得到结果为


的平衡二叉树的结点数至少有
________个,高度为2
的平衡二叉树的结点数至少有
________
个。
三判断
1.
顺序存储结构属于静态结构,链式结构属于动态结构。
(
)
2.
即使对不含相同元素的同一输入序列进行两组不同的、
合法的入栈和出栈组合操作,
所得的输出序列
也一定相同。
(
)
3.
带权无向图的最小生成树必是唯一的。
(
)
4.
B-树和B+树都可用于文件的索引结构。
(
)
5.
在用堆排序算法排序时,如果要进行增序排序,则需要采用
"大根堆"。(
)
四、应用题
1.
模式串p="abaabcac"的next函数值序列为多少
设二维数组A[5][6]的每个元素占4个字节,已知LOC(a0,0)=1000,A共占多少个字节A的终端结点
a4,5的起始地址为多少按行和按列优先存储时, a2,5的起始地址分别为多少
,b,c,d,e五个字符的编码分别为

1,2,3,4,5,并设标识符依以下次序出现:

ac,bd,aa,be,ab,ad,cd,bc,ae,ce。
要求用哈希( Hash)方法将它们存入具有 10个位置的表中。
(1)将上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少;
决冲突。写出上述各关键字在表中位置。

(2)线性探测再散列法解
给定一个关键字序列{24,19,32,43,38,6,13,22},请写出快速排序第一趟的结果;堆排序时所建的初始堆;归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少在最坏
情况下那种方法的时间复杂度最差
作业题(五)
一、单项选择题
一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到
的一次划分结果为()。
A.(38,40,46,56,79,84)

B.(40,38,46,79,56,84)
C.(40,38,46,56,79,84)

D.(40,38,46,84,56,79)


A=(a,b,(c,d),(e,(f,g))),则下面式子的值为(

)。GetHead(GetTail(GetHead(GetTail(GetTail(A)))))
A.(g)

B.(d)






n个结点的二叉树

,其高度为(

)




+1


如图所示,给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先搜索得到的顶点序列是
()。




,其深度优先遍历类似于二叉树的(

)。






6.





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>,<V5,V7>,<V6,V7>},G的拓扑序列是(
)。
,V,V,V,V,V,V
,V,V,V,V,V,V
1
3
4
6
2
5
7
1
3
2
6
4
5
7
,V,V,V,V,V,V
,V,V,V,V,V,V
1
3
4
5
2
6
7
1
2
5
3
4
6
7
,平均比较次数为( )。在此假定N为线性
表中结点数,且每次查找都是成功的。