DS试题10套001

第一部分选择题

一、单项选择题（本大题共20小题，每小题1分，共20分）

1．计算机算法指的是，它必须具备输入、输出和【】

A．计算方法 B．排序方法

C．解决问题的有限运算步骤 D．程序设计方法

2．下列算法的时间复杂度是【】

for（i=0；i<n； i++）

c[i][j]＝i＋j；

A .O（l） B.O（n） C.O（log2n） D.O（n2）

3．在单链表的一个节点中有【】

A．l个指针 B．2个指针 C．0个指针 D。3个指针

4．在具有n个节点的单链表中做插入、删除运算，平均时间复杂度为【】

A．O（l） B。 O（n） C．O（log2n） D．O（n2）

5．向一个栈顶指针top的链栈中插入一个S所指节点时，执行【】

A． top－＞next＝ s；

B． s－＞next＝ top－＞next；top一＞next＝ s；

C． s－＞next＝ top；top＝ s；

D． s－＞next＝ top；top＝ top－＞next；

6．栈结构通常采用的两种存储结构是【】

A．散列方式和索引方式

B．顺序存储结构和链表存储结构

C．链表存储结构和数组

D．线性存储结构和非线性存储结构

7．设s1＝” ”，则strlen(s1)＝【】

A．0 B．1 C。2 D．3

8．设目标串T＝”aabbccddbbaa”，模式P=”bb”，则该模式匹配的有效位移为【】

A．1 B．2 C．3 D．4

9．数组与一般线性表的区别主要在【】

A．存储方面 B．元素类型一致

C．逻辑结构方面 D．不能进行插入、删除运算

10设二线数组A［0。。。m-l］[0。。。n-1]按行优先顺序存储在内存中，每个元素占d个字

节，则元素 A[i][j]的地址为【】

A．LOC（A[1][1]）＋［（i-1）*n＋j-l］*d

B．LOC（A[0][0]）＋［（i-l）*n＋j-1］*d

C．LOC（A[1][1]）＋［(j-l)* n＋i–1］*d

D．LOC（A[0][0]）＋［（j-l）*n＋i-1］*d

11具有n个节点的完全二叉树的深度为【】

A．log2n +1 B．log2n＋l

C．log2n D．log2n

12在具有n（n>l）个节点的完全二叉树中，节点i（2i＞n）的左孩子节点是【】

A．2i B．2i＋l

C．不存在 D．是2i-l

13．在一个图中，所有顶点的度数之和等于图的边数的几倍。【】

A．1/2 B．1 C．2 D．4

14在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是【】

A．希尔排序 B．冒泡排序

C．插入排序 D．选择排序

15．设有1000个无序的元素，希望以最快的速度挑选出其中前10个最大的元素，最好选用

的排序法是【】

A．起泡排序 B．快速排序

C．堆排序 D．基数排序

16．二分查找要求节点【】

A．有序、顺序存储 B．有序、链接存储

C．无序、顺序存储 D．无序、链接存储

17．VSAM文件采用哪种索引结构【】

A．多级 B．动态

C．随机 D。静态

18．散列文件中的记录通常是成组存放的，存放一组数据的存储单位称为【】

A．扇区 B．柱面

C．磁道 D．桶

19．索引表是指示逻辑记录和什么之间对应关系的表【】

A．物理记录 B．元素

C．关键字 D．结构

20．有8个节点的无向连通图最少有多少条边【】

A．14 B。28 C．56 D．112

第二部分非选择题

二、填空题（本大题共15小题，每空1分，井20分）

l．数据结构的实质一般包括三个方面的内容：数据的＿＿＿＿，数据的＿＿＿＿及数据的

运算。

2．在双链表中每个节点有两个指针域，一个指向＿＿＿＿，另一个指向＿＿＿＿。

3．当链满时再做进栈运算将产生＿＿＿＿。

4栈S经过运算InitStake(S); Push(S,a); Push(S,b); 后StakeTop(S)的值是＿＿＿＿。

5．通常在程序中使用的串可分为两种，即＿＿＿＿和＿＿＿＿。

6广义表（（a），((b), J, (((d))))的表头是＿＿＿＿，表尾是＿＿＿＿。

7．由一棵二叉树的前序序列和＿＿＿＿可唯一确定这棵二叉树。

8高度为k的完全二叉树至少有＿＿＿＿个节点。

9．如果n个顶点的图是一个环，则它有＿＿＿＿棵生成树。

10．n个顶点e条边的图若采用邻接表存储，则空间复杂度为＿＿＿＿。

11．在排序前，关键字值相等的不同记录间的前后相对位置保持＿＿＿＿的排序方法称为稳

定的排序方法。

12．对于n个记录的集合进行归并排序，所需要的平均时间为＿＿＿＿。

13．文件有四种基本的存储结构组织方式：顺序组织、索引组织、＿＿＿＿和＿＿＿＿。

14．对二叉排序树进行的查找方法是用待查的值与根节点的键值相比，若比根小则继续在＿

＿＿＿子树中找。

15．两个不同的元素存入同一个散列表，当这两个元素的散列函数值相同时，称为＿＿＿＿。

三、名词解释（本大题共5小题，每题3分，共15分）

l．循环链表

2．队列

3．三角矩阵

4．有序树

5．生成树

四、简答题（本大题共5小题，每题5分，共25分）

l．简述线形结构与非线形结构的不同点。

2．对于一个栈，如果输入项序列由A，B，C所组成，试给出全部可能的输出序列。

3．简述静态分配的顺序串与动态分配的顺序串的区别。

4．写出下列二叉树的前根、中根、后根排序顺序。

5．给出如下图所示的无向图G的邻接矩阵和邻接表两种存储结构。

五、应用题（本大题共2小题，每题10分，共20分）

1．设有链式存储结构的二叉树，计算其中有双后继节点的节点的个数。

2．以先查找插入位置，后插入的方法，在静态链表上实现直接插入排序。

设静态链表是用一维结构数组实现的。

数据结构模拟试题（一）参考答案

一、单项选择题

1．C 2。B 3．A 4。B 5。C 6。B 7。A

8． C 9。D 10。A 11。A 12。 C 13。A 14。D

15．C 16。A 17．B 18。D 19。A 20。C

二、填空题

1．逻辑结构 存储结构 2。前趋节点 后续节点 3。上溢 4。B

5．串变量 串常量 6。（a）(((b)), J, (((d)))) 7。中序序列

8．2k-1 9。n 10．O（n＋e） 11。不变 12。O（log2n）

13．散列组织 链组织 14。左 15。冲突

三、名词解释

1．循环链表：是一种首位相连的链表。单循环链表形成一个next环，而双循环链表形

成next链环和prior链环。

2．队列：是一种运算受限的单链表。它只允许在表的一端进行插入，而在另一端进行

删除。允许删除的一端称为队头，允许插入的一端称为队尾。

3．三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的矩阵。

4．有序树：树中节点的各子树看成是从左至有依次有序且不能交换。

5．生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G

的生成树。

四、简答题

1．线形结构的逻辑特征是除开始节点和终端节点外，其余每个节点只有一个直接前趋

和一个直接后继，即节点间存在一对一的关系；而非线形结构的逻辑特征是一个节点可以有

多个直接前趋和直接后继，即节点间存在多对多的关系。

2．本题利用栈的“后进先出”特点，有如下几种情况：

A进 A出 B进 B出 C进 C出 产生输出序列ABC

A进 A出 B进 C进 C出 B出 产生输出序列ACB

A进 B进 B出 A出 C进 C出 产生输出序列BAC

A进 B进 B出 C进 C出 A出 产生输出序列BCA

A进 B进 C迸 C出 B出 A出 产生输出序列CBA

不可能产生输出序列CAB。

3．程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串。在程序运

行过程中，动态分配空间可以链表形式存在的顺序串称为动态顺序串，静态串存在于内存一

片连续的数据区中，动态串存在与内存堆中。

4．前根排序：ABDEHCFI

中根排序：DBHEACIF

后根排序：DHEBIFCA

5．邻接矩阵如下；

邻接表如下：

五、应用题

l．int twochild（bt tree）

{

int numl，num2；

if (tree==null) return(0);

else

if（tree一＞left != null && tree一＞right != null）

else

{

numl＝twochild（tree一＞left）；

num2= twochild（free一＞right）；

return（numl＋num2）；

}

}

2．设静态链表是用一维结构数组实现的：

struct element{

int data；

int curs；

｝

statiin（element r[]）

{

int I, p；

element *p；

r[0].curs=0；

r[0].data=0；

for(I=1；I<=n；I++)

{ p=r[0].curs； return(1);

Pre=0;

scanf（”%d”，r[I].data）；

while（（r[I].data＞r[p].data）＆＆（r[pre].curs＜＞0＝））

{

pre=p； p=r[p].curs;

}

r[I].curs=p；；

r[pre].curs=I;

}

}

数据结构模拟试题（二）

本试卷分两部分，第一部分为选择题，第二部分为非选择题；选择题20分，非选择题80

分，满分100分。考试时间150分钟。

第一部分选择题

一、单项选择题（本大题共20小题，每小题1分，共20分）

在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填

在题后的括号内。

1．一个存储节点存放一个【】

A．数据项

B．数据元素

C．数据结构

D．数据类型

2．下列时间复杂度中最好的是【】

A．O（1）

B．O（n）

C．O（log2n）

D．O（n2）

3．非空的线性表中，有且只有一个直接前趋和一个直接后继的节点是【】

A．开始节点 B。内部节点

C．终端节点 D．所有节点

4．在一个单链表中，已知Q所指节点是P所指节点的前趋节点，若在Q和P之间插入S

节点，则执行【】

A．S－＞next = P－＞next; P－＞next = S;

B．P－＞next = S－＞next; S－＞next = P;

C．Q－＞next = S; S－＞next = P;

D。P－＞next = S; S－＞next = Q;

5．一个队列的入队序列是1，2，3，4，则队列的输出序列是【】

A．1，2，3，4

B．4，3，2，1

C．1，4，3，2

D．3，2，4，1

6．一个顺序栈一旦被说明，其占用空间的大小【】

B．可以改变

C．不能固定

D．动态变化

7．经过下列运算后，X的值是【】

InitQueue（Q）；EnQueue（Q，a）；EnQueue（Q，a）；DeQueue（Q，X）；

A．a

B．b

C．l

D．2

8．下列广义表是线性表的有【】

A．E＝（a，（b，c）） B。E＝（a，E）

C．E＝（a，b） D．E＝（a，L）；L＝（）

9．数组A中，每个元素A的长度为 3个字节，行下标i从 1到 8，列下标j从1到 10，

从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A［8］［5］的起始地址

为【】

A．SA+140 B．SA+144

C．SA＋222 D．SA＋225

10．设 s3=”I AM”，s4=”A TERCHER”，则strcat（s3，s4）=【】

A．”I AM”

B．”I AM A TERCHER”

C．”I AMA TERCHER”

D．”A TERCHER”

11．完全二叉树＿＿＿＿二叉树。【】

A一定是满B．可能是满

C不是D一定不是满

12．在具有n个节点的完全二叉树中，节点i（i＞l）的父节点是【】

A．2i B．不存在

C．2i＋I D。 i/2

13．强连通分量是＿＿＿＿的极大连通子图。【】

A．无向图 B。有向图

C．树 D。图

14．在一个图中，所有节点的度数之和与图的边数的比是【】

A．1：2 B．1：1

C．2：1 D．3：l

15．若一组记录的关键码为（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

16．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行

比较，将其放入已排序序列的正确位置上的方法称为【】

A．希尔排序 B．冒泡排序

C．插入排序 D。选择排序

17顺序查找法适合于存储结构为＿＿＿＿的线性表。【】

B．顺序存储或链接存储

C．压缩存储

D．索引存储

18．在查找过程中，若同时还要做增、删工作，这种查找则称为【】

A．静态查找

B．动态查找．

C．内查找 l

D．外查找

19．存放在外存中的数据的组织结构是【】

A．数组

B．表

C．文件

D．链表

20．顺序文件的缺点是【】

A．不利于修改 B．读取速度慢

C．只能写不能读 D。写文件慢

第二部分非选择题

二、填空题（本大题共17小题，每空1分，共20分）

l．一个算法的空间复杂度是指该算法所耗费的＿＿＿＿，它是该算法求解问题＿＿＿＿的

函数。

2．链式存储方式中，指针域中只有一个指针的线性表称为＿＿＿＿。

3．在具有n个节点的双链表中做插入、删除运算，平均时间复杂度为＿＿＿＿。

4．当栈空时再做退栈运算时将产生＿＿＿＿。

5．顺序队列为空的条件是＿＿＿＿。

6．串按存储方式可分为＿＿＿＿和＿＿＿＿。

7．对称矩阵的下三角元素a[i,j]，存放在一维数组 V的元素 V[k]仲， k与 i，j的关系是：

＿＿＿＿。

8．稀疏矩阵的三元组中，第1列存储的是稀疏数组中非零元素所在的＿＿＿＿。

9．霍夫曼树是带权路径长度＿＿＿＿的二叉树。

10．已知完全二叉树的第8层有8个节点，则其叶子节点数是＿＿＿＿。

11．图的深度优先遍历序列的＿＿＿＿是惟一的。

12．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为＿＿＿＿。

13．排序是将一组任意排列的数据元素按＿＿＿＿的值从小到大或从大到小重新排列成有序

的序列。

14．对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间为＿＿＿＿。

15．散列表的查找效率主要取决于散列表造表时选取的＿＿＿＿和＿＿＿＿。

16．可以对索引表建立一个索引，称为＿＿＿＿。

17．散列文件中的记录通常是成组存放的，存放散列数据的存储单位称为＿＿＿＿。

三、名词解释（本大题共5小题，每题3分，共15分）

l．顺序表

2．链队列

3．行表

4．二叉树

5．完全图

四、简答题（本大题共5小题，每题5分，共25分）

l．说明头指针和头节点的作用。

2．简述栈的逻辑特点，栈与线性表的异同。

3．简述有效位移与无效位移的区别。

4．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出一些

二叉树。

5．写出使用归并排序法对下列数据进行从小到大排序的中间过程和最后结果。

［83，40，63，13，84，35，96，57，39，79，61，15］

五、应用题（本大题共2小题，每题10分，共20分）

1．有两个具有相同节点数的单链表 S1＝{A1，A2，A3，A4，A5， ，An}，S2＝{B1，B2，

B3，B4， ，Bn}，将S1与S2合并成单链表S={ A1，B1，A2，B2，A3，B3， ，An，Bn}。

使用new（C）复制与S1中节点相同的节点，连接到S中。

2．设计用递归法从大到小输出二叉树中所有值为偶数的关键字。

数据结构模拟试题（二）参考答案

一、单项选择题

1．B 2。A 3。B 4。C 5．A

6．A 7。A 8。C 9。C 10．B

11．B 12。D 13。B 14。C 15．C

16．C 17。B 18．B 19。C 20．A

二、填空题

1．存储空间 规模n

2．单链表

3．O（l）

4．下溢

5．头尾指针相等

6．顺序串 链串

7．i*(i-1)/2＋j

8．行数

9．最小

10．68

11．不是

12．O（n2）

13．关键字

14．O（n2）

15．散列函数 处理冲突的方法

16．查找表

17．桶

三、名词解释

1．顺序表：

把线性表的节点按逻辑次序依次存放在一组地址连续的存储单元里。

2．链队列：

队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。

3．行表：

记录稀疏矩阵中每行非零元素在三元表组中的起始位置的表。

4．二叉树：

是一种特殊的树。在二叉树中，每个节点最多只有两棵子树，并且子树有左右之分。（它

与度数为2的树有区别，在一般树中若某节点只有一个孩子，就无需区分其左右次序，而在

二叉树中即使是一个孩子也有左右之分。）

5、完全图：

图G中任意两个顶点都有一条边相连接，称该图为完全图。

四、简答题

1．头指针是指向链表表头节点的指针，只要链表存在，该指针始终不会改变，己知该

指针便已知该链表。头节点是在链表的开始节点之前附加的一个节点，是链表的表头，当链

表不空时，其内的指针指向链表的第一个节点，当链表是空链表时，该指针为空指针。这样

在链表的第一个位置上的操作就和在表的其他位置上操作一样，无须进行特殊处理。当链表

是空链表时，该指针为空指针。因此空表和非空表的处理也就统一了。

2．栈是先进后出表。栈的插入和删除都从称为栈顶的一端进行，一般线性表可以在线

性表的中间及两端进行插入、删除操作。

3．模式匹配中，所找到的与模式匹配的子串，其开始字符离开目标串首字符的位移称

为有效位移。目标串除有效位移以外，其他字符的位移称为无效位移。

4．

5．［83，40，63，13，84，35，96，57，39，79，61，15］

［40，83，13，63，35，84，57，96，39，79，15，61］

［13，40，63，83，35，57，84，96，15，39，61，79］

［13，35，40，57，63，83，84，96，15，39，61，79］

［13，15，35，39，40，57，61，63，79．83，84，96］

五、应用题

1．node *sum(node s1,s2)

{

node r,c,*p,*q,*s；

s=(node*)malloc(sizeof(node));

r=s; p=s1; q=s2;

while (p!=null)

{c=(node * )malloc(size(node));

c->data=p->data;

r->next=c;

p=p->next;

r=c;

new(c);

c->data=p->data;

r->next=c;

q=q->next;

r=c;

}

r->next=null;

s=s->next;

return（s）；

｝

2．void passbtree（bstree root）

｛

if（!root） return；

if（root->rchild） passbtree（root->rchild）；

printf（root->data）；

if（root->lchild） passbtree（root->lchild）；

}

本文来源：https://www.bwwdw.com/article/ostj.html