数据结构专升本模拟题及参考答案汇总.docx
- 文档编号:13720120
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:43
- 大小:217.12KB
数据结构专升本模拟题及参考答案汇总.docx
《数据结构专升本模拟题及参考答案汇总.docx》由会员分享,可在线阅读,更多相关《数据结构专升本模拟题及参考答案汇总.docx(43页珍藏版)》请在冰点文库上搜索。
数据结构专升本模拟题及参考答案汇总
、单项选择题
1.从逻辑上可以把数据结构分为(
A.动态结构、静态结构
C.线性结构、非线性结构
2.链表不具有的特点是(
A插入、删除不需要移动元素
C.不必事先估计存储空间D.
3.下面程序段的时间复杂度的量级为
For(i=1;i<=n;i++)
For(j=1;j<=I;j++)
For(k=1;k<=j;k++)
X=x+1;
A.O
(1)
C.O(n2)
4.在一个带头结点的双向循环链表中,
个指针域的值。
A.2
C.4
作业题
(一)
)两大类。
.顺序结构、链式结构
.初等结构、构造型结构
B.可随机访问任一元素
所需空间与线性长度成正比
)。
.O(n)
.O(n3)
若要在p所指向的结点之前插入一个新结点,则需要相继修改()
.3
.6
5、一个顺序存储线性表的第一个元素的存储地址是
90,每个元素的长度是2,则第6个元素的存储地址
是(
)。
A.98
.100
C.102
.106
6、判定一个栈s(最多元素为m0为空的条件是(
)。
A.s-〉top!
=0
s-
〉top==0
C.s-〉top!
=m0
s-
〉top==m0
7、循环队列用数组A[m]
(下标从0到m-1)存放其元素值,已知其头尾指针分别是
front
和rear,则当
前队列中的元素个数是(
)。
A.(rear-front+m)%m
.rear-front+1
C.rear-front-1D.rear-front
设有两个串S1与S2,求串S2在S1中首次出现位置的运算称作(
A.连接B•求子串
C.模式匹配D•判子串
设串S1='ABCDEFG;S2='PQRST',函数con(x,y)返回x和y串的连接串,
从序号i的字符开始的j个字符组成的子串,len(s)返con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是()。
8、
9、
)。
subs(s,i,j)回串S
返回串S的的长度,则
C.BCPQRST
.BCDEFEF
10、数组常用的两种基本操作是(
A.建立与查找
C.插入与索引
二、填空题
1.所谓稀疏矩阵指的是
•删除与查找
•查找与修改
且分布没有规律。
2.队列是的线性表,其运算遵循
的原则。
3.空格串是
4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有
5、设图G有n个顶点和e条边,则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度
,而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为
,图的深度或广
度优先搜索遍历时的空间复杂度均为
6、一个图的
三、算法
设二叉树采用二叉链表结构,试设计一个算法统计给定二叉树中的一度结点数目。
四、应用题
表示法是唯一的,而
表示法是不唯一的。
1对关键字无序序列(36,25,48,12,65,43,20,58)进行直接选择排序,
请写出每一趟排序的结果。
(10分)
2、对无向带权图,用克鲁斯卡尔算法构造最小生成树。
(10分)
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的顺序进栈,问下列哪一个不是合法的出栈序列?
(
A.543612
B.453126
C.346521D.234156
2.栈和队都是(
A.顺序存储的线性结构
B.
链式存储的非线性结构
C.限制存取点的线性结构
D.
限制存取点的非线性结构
3、顺序查找法适合于存储结构为(
)的线形表。
A.散列存储
B.顺序存储或链接存储
C.压缩存储
D.索引存储
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、折半查找的平均比较次数为(
)。
A.n
B.
n/2
C.log2n
D.
log2(n+1)
6、当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,
但前者比后者的
查找速度(
A.必定快
B.不一定
C.在大部分情况下要快
D.取决于表递增还是递减
7、已知一有向图的邻接表存储结构如下图如示。
根据有向图的深度优先遍历算法,从顶点
v1出发,所得
到的顶点序列是(
)。
A.v1,v2,v3,v5,v4
C.v1,v3,v4,v5,v2
1
2
A
3
4
A
S
B.v1,v2,v3,v4,v5
D.v1,v4,v3,v5,v2
B.链式存储
D.散列存储
A.s
B.
s-1
C.s+1
D.
10、如图所示,给出由7个顶点组成的无向图。
从顶点
A出发,对它进行深度优先搜索得到的顶点序列是
A.AECDBFG
B.AGBFDEC
C.ACEDBGF
D.ABDGFEC
二、填空题
1.设no为哈夫曼树的叶子结点数目
则该哈夫曼树共有
个结点。
2.有数据WG={719,2,6,32,
3,21,10},则所建Huffman树的树高是
,带权路径长度WPL
8、为了方便地对图状结构的数据进行存取操作,则其中数据存储结构宜采用(
A.顺序存储
C.索引存储
9、在一个具有n个顶点的有向图中,若所有顶点的出度之和为S,则所有顶点的入度之和为(
为。
3、设一棵完全二叉树叶子结点数为
4、采用分块查找时,若线性表中共有
k,最后一层结点数>2,则该二叉树的高度为
625个元素,查找每个元素的概率相同,假设采用顺序查找来确定
结点所在的块时,每块应分_个结点最佳。
5、设G为具有N个顶点的无向连通图,贝yG中至少有条边。
6、哈夫曼树(HuffmanTree)又称。
它是n个带权叶子结点构成的所有二叉树中,带权路径
长度WPL。
;依次先序遍历树
7、树的先序遍历过程如下:
若树为空,则进行空操作;若树非空,则访问树的的
三、应用题
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"
30
0
□C
□C
30
60
0
20
30
10
0
贋
50
1
0」
(1)
.画出逻辑图
(2).画出图的十字链表存储;
(3).基于邻接矩阵写出图的深度、
广度优先遍历序列;
(4).计算图的关键路径。
作业题(三)
一、单项选择题
1.串的长度是指(
A.串中所含不同字母的个数
B.串中所含非空格字符的个数
C.串中所含不同字符的个数
D.串中所含字符的个数
2.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首
地址BA开始顺序存放,当用以列为主存放时,
元素A[5,8]的存储首地址为()。
A.BA+141B.BA+180C.BA+222
D.BA+225
3.算法分析的两个主要方面是(
A.空间复杂性和时间复杂性
.正确性和简明性
C.可读性和文档性
.数据复杂性和程序复杂性
4.算法分析的目的是(
A.找出数据结构的合理性
.研究算法中的输入和输出的关系
c.分析算法的效率以求改进
.分析算法的易懂性和文档性
5.下面程序段的时间复杂性的量极为
Intfun(intn)
{inti=1,s=1;
While(s S+=++I; ReturnI; .O(lbn) .O() A.O(n/2) C.0(n) 6. 线性表是( A.—个有限序列, 可以为空 .一个有限序列,不能为空 7. C.一个无限序列, 可以为空 •一个无限序列,不能为空 带头结点的单链表 L为空的判定条件是( A.L==NULL .L-〉next==NULL C.L-〉next==L .I_! =NULL 8. 在一个长度为n的线性表中,删除值为 x的元素时需要比较元素和移动元素的总次数为( A.(n+1)/2 .n/2 C.n .n+1 9. 一个顺序存储线性表的第一个元素的存储地址是 90,每个元素的长度是2,则第6个元素的存储地址 A.98 .100 C.102 .106 10.如果某链表中最常用的操作是取第 i个结点及其前驱,则采用( 。 存储方式最节省时间。 A.单链表 .双向链表 C.单循环链表 二、填空题 1.高度为2的二叉树的结点数至少有 .顺序表 个,高度为3的二叉树的结点数至少有 个。 2.在顺序表(8,11,15,19,25,26,30,33,42,48,50 。 中,用折半查找关键字值20,需做的关键字比较次数为 3.在有n个顶点的无向图中,每个顶点的度最大可达 4.已知广义表A=((a,b,c),(d,e,f)),则广义表运算head(tail(tail(A)))=。 5.数组(Array)是n(n>1)个的有序组合,数组中的数据是按顺序存储在一块 存储单元中。 6.采用顺序存储结构表示三元组表(TripleTable),来实现对稀疏矩阵的一种压缩存储形式,就称 7. 为,简称表。 mxn的矩阵变成另外一个nxm的矩阵,同时 .运算是矩阵运算中最基本的一项,它是将一个 使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题 1对于下图所示的二叉树,画出二叉链表存储结构图。 2、请画出下图所示的树所对应的二叉树。 3.已知一个无向图如下图所示,要求分别用 Prim和Kruskal 算法生成最小树(假设以①为起点,试画出 构造过程)。 4.已知完全二叉树的第8层有8个结点, 则其叶子结点是多少? 5.画出如图所示中树的二叉树的表示形式。 A C 作业题(四) 1. 2. 3. 、单项选择题 将两个各有n个元素的有序表归并成一个有序表,其最少得比较次数是( A.n C.2n .2n-1 .n-1 一个有n个顶点的无向连通图,它所包含的连通分量个数为( A.0 C.n 数据文件的基本操作中最重要的操作是( A.插入 C.修改 B. D. B. D. n+1 删除 检索 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个最小元素之前的部分排序的序列,用( )方法最快。 A. 堆排序 B.快速排序 C. 插入排序 D.归并排序 6. 算法分析的目的是( A. 找出数据结构的合理性 .研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 .分析算法的易懂性和文档性 7. 二叉树的第I层上最多含有结点数为( II-1 A.2B.2-1C.2 I-1 D.2I-1 循环队列存储在数组A中,长度为m则入队时的操作为( A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1) 9.广义表满足Head(A)=Tail(A),则A为( A.() (0) C.(0,()) 10.在一棵度为3的树中,度为3的结点数为2个, (0,(),0) 度为2的结点数为 1个,度为1的结点数为2个,则度为0的 结点数为(。 个。 C.5 二、填空题 1. 在一个循环队列中,队首指针指向队首元素的数组中每一个数据通常称为, 一个图的表示法是唯一的,而_ —用下标区分,表示法是不唯一的。 其中下标的个数由数组的 决定。 个, 5. 在一个10阶的B-树上,每个数根结点中所含的关键字数目最多允许最少允许 对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后的得到结果为 个。 三判断 1.顺序存储结构属于静态结构,链式结构属于动态结构。 2.即使对不含相同元素的同一输入序列进行两组不同的、 合法的入栈和出栈组合操作,所得的输出序列 也一定相同。 3.带权无向图的最小生成树必是唯一的。 ( 4.B-树和B+树都可用于文件的索引结构。 ( 5.在用堆排序算法排序时,如果要进行增序排序,四、应用题 则需要采用 "大根堆"。 () 1.模式串p="abaabcac"的next函数值序列为多少? 2.设二维数组A[5][6]的每个元素占4个字节,已知LOC(a0,0)=1000,A共占多少个字节? A的终端结点a4,5的起始地址为多少? 按行和按列优先存储时,a2,5的起始地址分别为多少? 3.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5,并设标识符依以下次序出现: 要求用哈希(Hash)方法将它们存入具有10个位置的表中。 ac,bd,aa,be,ab,ad,cd,bc,ae,ce。 1)将上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少; 2)线性探测再散列法解 决冲突。 写出上述各关键字在表中位置。 4.给定一个关键字序列{24,19,32,43,38,6,13,22},请写出快速排序第一趟的结果;堆排序时 所建的初始堆;归并排序的全过程。 然后回答上述三中排序方法中那一种方法使用的辅助空间最少? 在最 坏情况下那种方法的时间复杂度最差? 作业题(五) 一、单项选择题 1.一组记录的关键码为(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) 广义表A=(a,b,(c,d),(e,(f,g))), D. (40,38,46,84,56,79) 则下面式子的值为( GetHead(GetTail(GetHead(GetTail(GetTail(A))))) A.(g)B.(d)C.cD.d 3. 对于有n个结点的二叉树,其高度为( A.nlog2nB.log2nC.[log2n_+1 •不确定 4. 如图所示,给出由7个顶点组成的无向图。 从顶点 1出发,对它进行深度优先搜索得到的顶点序列是 B.1347625 C. D.1247653 5. 采用邻接表存储的图,其深度优先遍历类似于二叉树的( A.中序遍历 B.先序遍历 C.后序遍历 D.按层次遍历 6. 已知有向图G=(V,E) 中V={V1,V2,V3,V4,V5,V6,V7} E={ C. 7. V1,V3,V4,V6,V2,V5,V7 V1,V3,V4,V5,V2,V6,V7 B.V1,V3,V2,V6,V4,V5,V7 D.V1,V2,V5,V3,V4,V6,V7 顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为( )。 在此假定N为线性 表中结点数,且每次查找都是成功的。 N+1 B.2log2N C. log2N D.N F面关于m阶B树说法正确的是( ①每个结点至少有两棵非空子树; ②树中每个结点至多有m—1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后,树长高一层。 A.①②③ B.②③ C.②③④ D.③ 9.已知一个线性表(38,25,74, 63,52,48),假定采用h(k)=k%7计算Hash地址进行散列存储,若利 用链地址法处理冲突,则在该Hash表上进行查找的平均查找长度为( A.1.0 B.7/6 C.4/3 D.3/2 10.在排序算法的实施过程中,使用辅助存储空间为0 (1)的有( A.简单排序法 B.快速排序法 D.基数排序法 C.归并排序法 二、填空题 1.n(n大于1)个结点的各棵树中,其中深度最大的那棵树的深度是个非叶子结点。 n,它共有 个叶子结点和 2.设一棵后序线索树的高是50,结点x是树中的一个结点,其双亲是结点 y,y的右子树咼度是60,x是y 的左孩子。 则确定x的后继最多需经过 中间结点(不含后继及 x本身) 3. 个关键字。 高度为2(第2层为叶子)的3阶B-树中,最多有 4.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为无序的表,则平均情况下最省时间的是 算法。 5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有 6.串的链式存储结构是将存储区域分成一系列大小相同的结点 每个结点有两个域 域和 域。 其中 三.判断 域用于用于存放数据, 域用于存放下一个结点的指针 1.顺序存储的线性表可以随机存取。 2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序 列也一定相同。 3. 十字链表是无向图的一种存储结构。 () 4. 折半查找方法适用于排列连续顺序文件的查找。 5. 在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳 定的。 () 四、应用题 1.用十字链表表示一个有k个非零元素的mxn的稀疏矩阵,则其总的结点数为多少? 2.G=(V,E)是一个带有权的连通图,则: (1).请回答什么是G的最小生成树; (2).G为下图所示,请找出G的所有最小生成树。 3.请分别叙述在一个连续顺序文件中采用顺序查找法,折半查找法和分块查找法查找一个记录,该文件中记录应该满足什么条件? 4.设待排序文件之排序码为(88,33,22,55,99,11,66),采用顺序存储。 请用直接选择排序算法对上述文件进行排序,用图示说明排序过程。 作业题一参考答案: 一、单项选择题1、C2、B3、D4、C5、B6、B7、A8、C9、D10、D 二、填空题 1、非零元很少 先进先出(或 2、操作受限(或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊)后进后出) 3、简单选择排序 4、0(n2),0(e),0(n) 5、邻阵矩阵,邻接表 三、算法 答: intcount=0; voidonechild(Btreet){if(t! =NULL) {onechild(t->lchild); onechild(t->rchild); if(t->lchild! =NULL&&(t->rchild! =NULL||t->lchild! =NULL&&t->rchild==NULL) count++; } } 四、应用题1、答: (0) [33 t 25 <0 12t 65 43 20 53] (1) 12 吟 43 36 es 43 20t 53] ⑵ 12 20 [43t 36 65 43 25t 53] ⑶ 12 20 25 [36 65 43 48 53] ⑷ 12 20 25 36 [65 t 43t 48 53] ⑸ 12 20 25 36 43 ES5t 48+ 53] ⑹ 12 20 25 36 43 1 43 J [35 53]t (T) 12 20 25 30 43 43 L 58 1 es 2、答: 散列地址 100 101 102 103 104 105 106 107 10S 109 关键字 98 63 79 17 53 19 61 75 46 49 比较次数 1 1 1 1 1 3 5 10 由于地址空间为10,且从100开始,故散列函数选为H(key)=key%7+100。 3、答: 用线性探测再散列解决冲突,ASLsucc=27/10 4、答: 成功查找平均比较查找长度为: (n+1)/n[log2(n+1)]-1。 作业题二参考答案: 一、单项选择题 1、 C2、C3、 B4、C5、D 6、 C7、C8、 B9、A10、C 二> 填空题 1、 2n0-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 模拟 参考答案 汇总