2024年数据结构专升本模拟试题及参考答案

东北农业大学网络教育学院

数据结构专升本作业题

作业题(一)

一、单项选择题

1.从逻辑上能够把数据结构分为(C)两大类。

A.动态结构、静态结构B.次序结构、链式结构

C.线性结构、非线性结构D.初等结构、结构型结构

2.链表不具备的特点是(B)

A,插入、删除不需要移动元素B.可随机访问任一元素

C.无须事先估量存储空间D.所需空间与线性长度成正比

3.下面程序段的时间复杂度的量级为(D)o

For(i=l:i<=n;i++)

For(j=l;j<=I;j++)

For(k=l;k<=J;k++)

X=x+1;

A.0(1)B.0(n)

C.0(n2)D.0(n3)

4.在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点，则需要相继修改(B)

个指针域的值。

A.2B3

C.4D.6

5、一个次序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址

是(【))。

A.98B.100

C.102D.106

6、判定一个栈s(最多元素为m0)为空的条件是(B)。

A.s->top!=0B.s->top==0

C.s-)top!二mOD.s-)top==m0

7、循环队列用数组A[m](下标从0到m-D存储其元素值，已知其头尾指针分别是front和rear,则目

前队列中的元素个数是()。

A.(rcar-front+m)%mB.rcar-front+1

C.rear-front-1I),rear-front

8、设有两个串SI与S2,求串S2在SI中初次出现位置的运算称作()。

A.连接B.求子串

C.模式匹配D.判子串

9、设串S1='ABCDEFG',S2='PQRST,函数con(x.y)返回x和y串的连接串，subs(s,i,j)返回串S的

的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则

con：subs(Sl,2,len(S2)),subs(Sl,len(S2),2))的成果是().»

A.BCDEEB.BCDEFG

C.BCPQRSTD.BCDEFEF

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

A.建立与查找B.删除与查找

C.插入与索引D.查找与修改

二、填空题

1.所谓稀疏矩阵指的是旦分布没有规律。

2.队列是的线性表，其运算遵照的标准。

3.空格串是.

4.简单项选择择排序和起泡排序中比较次数与序列初态无关的算法有。

5、设图G有n个顶点和c条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度

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

度优先搜索遍历时的空间复杂度均为。

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.543612B.453126C.346521D.234156

2.找和队都是（）

A.次序存储的线性结构B.链式存储的非线性结构

C.限制存取点的线性结构D.限制存取点的非线性结构

3、次序查找法适合于存储结构为（）的线形表。

A.散列存储B.次序存储或链接存储

C.压缩存储I）.索引存储

4、分别如卜.列序列结构二叉排序树，与用其他三个序列所结构的成果不一样的是（）。

A.(100,80,90,60,120,110,130)B.(100,120,11C,130,80,60,90)

C.(100,60,80,90,120,110,130)D.(100,80,6C,90,120,130,110)

5、圻半查找的平均比较次数为（

A.nB.n/2

C.Iog2nD.Iog2(n+1)

6、当在一个有序的次序存储表上查找一个数据时，即可用折半查找，也可用次序查找，但前者比后者的

有找速度（）

A.必然快B.不一定

C.在大部分情况下要快D.取决于表递增还是递减

7、已知一有向图的邻接表存储结构如下图如示。依照有向图的深度优先遍历算:法，从顶点vl出发，所得

到的顶点序列是（）o

A.vl,v2,v3,v5,v4B.vl,v2,v3,v4,v5

C.vl,v3,v4»v5,v2D.vl,v4,v3»v5,v2

8、为了以便地对图状结构的数据进行存取操作，则其中数据存储结构宜采取（）。

A.次序存储B.链式存储

C.索引存储D.散列存储

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

A.sB.s-1

C.s+1I),n

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

()0

A.AECDBFGB.AGBFDEC

C.ACEDBGFD.ABDGFEC

二、填空题

1.没n。为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。

2.有数据WG={7,19,2,6,32,3,21,10),则所建Huffman树的树高是，带权途径长度WPL

为。

3.设一棵完全二叉树叶子结点数为k,最后一层结点数＞2,则该二叉树的高度为o

4.采取分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采取次序查找来确定

结点所在的块时，每块应分一个结点最佳。

5、及G为具备N个顶点的无向连通图，则G中最少有条边。

6、哈夫曼树(HuffmanTree)又称,它是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｝的图的邻接矩阵,

0100300010~

□008<30□0

006002()00

001000000

0000oo500

（1）.画出逻辑图：

（2）.画出图的十字链表存储;

（3）.基于邻接矩阵写出图的深度、广度优先遍历序列;

（4）.计算图的核心途径。

作业题（三）

一、单项选择题

1.串的长度是指（）

A.串中所含不一样字母的个数B.串中所含非空格字符的个数

C.串中所含不一样字符的个数D.串中所含字符的个数

2.设有数组数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首

地址BA开始次序存储，当用以列为主存储时，元素A[5,8]的存储首地址为（）。

A.BA+141B.BA+180C.BA+222D.BA+225

3.算法分析的两个重要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性

C,可读性和文档性D.数据复杂性和程序复杂性

4.算法分析的目标是（

A,找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

5.下面程序段的时间复杂性的量极为（

Intfun（intn）

{inti=l,s=l;

While（s<n）

S+=++I;

ReturnI;

）

A.O（n/2）B.O(lbn)

C.0(n)D.0()

6.线性表是（）。

A.一个有限序列，能够为空B.一个有限序列，不能为空

C.一个无限序列，能够为空D.一个无限序列，不能为空

7.带头结点的单链表L为空的判定条件是（）0

A.L==NULLB.L-）next==NULL

C.L->next==LD.L!=NULL

8.在•个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）0

A.（n+1）/2B.n/2

C.nD.n+1

9.一个次序存储线性表的第一个元素的存储地址是90,用个元素的长度是2,则第6个元素的存储地址

是（）o

A.98B.100

C.102D.106

10.假如某链表中最常用的操作是取第i个结点及其前驱，则采取（）存储方式最节约时间。

A.单链表B.双向链表

C.单循环链表D.次序表

二、填空题

1.高度为2的二叉树的结点数最少有个，高度为3的二叉树的结点数最少有______个。

2.在次序表1,15,19,25,26,3043,42,48小）中,用折半查找核心字值20.需做的核心字比蛟次数

为________。

3.在有n个顶点的无向图中，每个顶点的度最大可达o

4.已知广义表A=((a,b,c),(d,e,f)),则广义表运算head(tail(tail(A)))=

5、数组(Away)是n(n21)个的有序组合，数组中的数据是按次序存储在一块的

存储单元中。

6.采取次序存储结构表示三元组表(TripleTable),来实现对稀疏矩阵的一个压缩存储形式，就称

为，简称表。

7.运算是矩阵运算中最基本的一项，它是将一个mxn的矩阵变成另外一个nxm的矩阵，同时

使木来矩阵中元素的行利列的位置互换而值保持不变。

三、应用题

1、对于下图所示的二叉树，画出二叉链表存储结构图。

2、请画出下图所示的树所对应的二叉树。

3.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树(假设以①为起点，试画出

结构过程)。

4.己知完全二叉树的第8层有8个结点，则其叶子结点是多少?

5.画出如图所示中树的二叉树的表示形式。

作业题（四）

一、单项选择题

1.洛两个各有n个元素的有序表归并成一个有序表,其最少得比较次数是)

A.nB.2n-l

C.2nD.n-1

2.一个有n个顶点的无向连通图，它所包括的连通分量个数为（）0

A.0B.1

C.nD.n+1

3.数据文献的基本操作中最重要的操作是（

A.插入B.删除

C.修改I）.检索

4.对核心码序列28,16,32,12,60,2,5,72迅速排序，从小到大一次划提成果为（)»

A.25,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)

C.X16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)

5.假如只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用(，措施最快。

A.堆排序B.迅速排序

C.插入排序D.归并排序

6.嵬法分析的目标是()。

A.我出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

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

A.21B.C.21-'D.2'-1

8.循环队列存储在数组A中，长度为m,则入队时的操作为()。

A.rcar=rcar+1B.rcar=(rear+l)mod(m-1)

C.rear=(rear+l)modmI).rear=(rear+1)mod(m+1)

9.广义表满足Head(A)=Tail(A),则A为()。

A.()B.(())

C.((),())D.((),(),())

10.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的

结点数为()个。

A.3B.4

C.5D.6

二、填空题

1.在一个循环队列中，队首指针指向队首元素的。

2.数组中每一个数据一般称为，用下标辨别，其中下标的个数由数组的—决定。

3.一个图的表示法是唯一的，而表示法是不唯一的。

4.在一个10阶的B-树上，每个数根结点中所含的核心字数目最多允许

个，最少允许个

5.对核心字序列(52,80,63,44,48,91)进行一趟迅速排序之后的得到成果为。

10.高度为1的平衡二叉树的结点数最少有________个，高度为2的平衡二叉树的结点数最少有

个。

三判断

1.次序存储结构属于静态结构，链式结构属于动态结构。()

2.虽然对不含相同元素的同一输入序列进行两组不一样的、合法的入栈和出栈组合操作，所得的输出序

列也一定相同。()

3.带权无向图的最小生成树必是唯一的。()

4.B-树和B+树都可用于文献的索引结构。()

5.在用堆排序算法排序时，假如要进行增序排序，则需要采取“大根堆”。()

四、应用题

1.模式串p="abaabcac"l'l'Jnext函数值序列为多少？

2.设二维数组A[5]⑹的每个元素占4个字节，已知LOC(aO.O)=10C0,A共占多少个字节？A的终端结

点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？

3.设a.b,c,d,e五个字符的编码分别为123,4,5,并设标识符依如下次序出现：ac,bd.aa,be,ab,ad,cd.bc,ae,ce,>

要求用哈希（Hash）措施将它们存入X备10个位置的表中。

（I）将上述核心字（标识符）结构一个哈希函数，使得发生冲突尽也许地少；（2）线性探测再散列法处

理冲突。写出上述各核心字在表中位置。

4,给定一个核心字序列｛24,19,32,43,38,6,13,22）,请写田迅速排序第一趟的成果；堆排序时

所建的初始堆；归并排序的全过程。状后回答上述三中排序措施中那一个措施使用的辅助空间最少？在最

坏情况下那种措施的时间复杂度最差？

作业题(五)

一、单项选择题

1.一组统计的核心码为(46,79,55,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)

2.广义表A=(a,b,(c,d),(e,(f,g))),则下而式子的值为()。

GetHead(GetTail(GetHead(GetTai1(GetTai1(A)))))

A.(g)B.(d)C.cD.d

3.对于有n个结点的二叉树，其高度为()

A.nlogjnB.log2nC.Llog2nJ+lD.不确定

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

(

A.1354267B.1347625

C.1534276D.1247653

D

无向图

5.采取邻接表存储的图，其深度优先遍历类似于二叉树的()。

A.中序遍历B.先序遍历

C.后序遍历D.按层次遍历

6.已知有向图G=(V,E),其中V={VI,V2,V3,V4,V5,V6,V7},

,<V6,V?>}.G的拓扑序列是

E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>

()o

A.V|,V3,V4,V6,V2,V5,V7B.V|,V3,V2,V6,V4,V5,V^

C.V1,V3,V4,V5,V2,V6,V7D.V|,V2,Vs,V3,V4,V6,V?

7.次序查找法适合用于查找次序存储或链式存储的线性表，平均比较次数为（工在此假定N为线

性衣中结点数，且每次查找都是成功的。

A.N+lB.21og2N

C.log2ND.N

8.下面有关m阶B树说法正确的是（）。

①每个结点最少有两棵非空子树；②树中每个结点至多有m—1个核心字；

③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层

A.①②®B.②③

C.②③④D.③

9.已知一个线性表（38,25,74,63,52,48）,假定采取h（k）=k%7计算Hash地址进行散列存储,若利

用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（）。

A.1.0B.7/6

C.4/3D.3/2

10.在排序算法的实行过程中，使用辅助存储空间为O（1）的有（）。

A.简单排序法B.迅速排序法

C.归并排序法D.基数排序法

二、填空题

I.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,1L,66),采取次序存储。请用直接选择排序算法

对上述文献进行排序，用图示阐明排序过程。

东北农业大学网络教育学院

数据结构专升本作业题参考答案

作业题一参考答案：

一、单项选择题

1、C2、B3、D4、C5、B

6、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、

答：

2、

答:

(1)(2)

⑶(4)

(5)

3、答：因为地址空间为10,且从100开始，故散列函数选为H(key)=key%7+IOOo

散列地址100101102103104105106107108109

关键字98637917531961754649

比较次数12111123510

用线性探测再散列处理冲突.ASI^ncc=27/10

4、答:成功查找平均比较查找长度为：(n+1)/n[log2(n+1)]-U

作业题二参考答案：

一、单项选择题

1、C2、C3、B4、C5、D

6、C7、C8、B9、A10、C

二、填空题

1、2n(i-l

2、6,261

3、Flogikl+l

4、25

5、N-l

6、最优二叉树，最小的二叉树

7、艰结点，各子树

三、应用题

1、

答：不唯一，型对即可

此树的带权途径长度WPL=9*1+6*2+4*3+(1+2)*4=45

2、

答:

(1)插入10(2)插入6(3)插入3(4)

(5)插入2(6)插入5(7)插入4(8)

3、答：当核心字为3时，比较次数为4；

当核心字为8时，比较次数为1：

当核心字为19时，查找不成功;

(3)深度优先遍历序列：ABCDE广度优先遍历序列：ABCED(4)核心途径A-B(长100)

作业题三参考答案:

一、单项选择题

1、D2、B3、A4、C5、D

6、A7、B8、C9、B10、D

二、填空题

1、2,3

2,4

3、n-1

4、e

5、相同类型数据，地址连续

6.三元组次序表，三元组

7.矩阵转置

三、应用题

1、

答：

二叉链表

2、答:

3.答：Prim算法结构最小生成树的步骤如24题所示，为节约篇幅，这里仅用Kruskal算法，结构最小生成

树过程如下：(卜图也可选(2,4)替代(3,4),(5,6)替代(1,5))

4.答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，贝!除

最后一层外各层的结点个数分别为：1,2,4,8,16,32,…，即第i层的结点个数为2iT。这里第8层有

8个结点，显然第8/层是最后的一层，那么第7层的结点个数为277=64个，其中的4个结点有8个叶子结点,

余下的为叶子结点，个数为64-4=60,因此该完全二叉树的叶子结点个数为60+8=68个。

5.答：对应的二叉树形式如图所示：

作业题四参考答案:

一、单项选择题

1.A2.B3.D4.B5.D

6、C7、C8、C9、B10、D

二、填空题

1.答：前一个位置

2.答：数组元素，数组元素，维数

3.答：邻阵矩阵，邻接表

4.答:9,4

5.答：[4844]52|648091]

6、：，2

三.判断

1.答：V

2.答：x

3.答：x

4.答：V

5.孥V

四、应用题

1.答：模式p的nexl函数值如下:

:触图QAYI自选smqp・\、口。口」4。面吊|&•<,A•三奇三」

Al五笔型IH,，II*W8新侑量獗5.2i厘ns米*steliiCs6t行ring30*列s,Im一tiniJ）中文（中国）。

5；

采用监序结构存储率s,编写一个函数删除s中笫字符开始的j上字符.

算法设计题（9+。

next.-1C011201

模式串।aIaabcac

ji01234567

答，不含任何字符的坐嬲交串，其更长度为零；仅含有空格字符的量恢空费串，它的长度

为中空格符的个数。空格符在字符串中可用来分隔一般的字符,便于阅谀和识别,空格符会

占用食姓率长。篁中在处埋过程中可用于作为任彩字符半的于电。I

•文科g根039»A.a)格式9)IAa)素珞Q)®nct)tffth

者基里的.长度小于一个常数，则采用何种存佬方式，最节省空间？

。”快语匡英中回日中田中英也取侑田设造-

答，采用暇序串最节省空间,因为顺序串与维母代比,不需要指针域，

II21I41I$•Is।1*)1IUIIMI!«■I120112211241m>>28«i3)(，凝।iMi13G'i38<夕，i42>U4«i4«i，的

模式串尸“飒M啦”峋next函数值序列为多少？

否，模式p的next函数值如下

简述一个字符串中子串的构成。

香：一个字符串中任意连续:t字符组成的子序列称为字符串的子串.

空串和空格串有何区别］字符串中空格符有何意义？空串在串的处理中有何作用？