数据结构

xiaoxiao2021-02-28  15

第一章一、选择题   1、数据结构的研究的3大方面内容是逻辑结构、存储结构、数据间的运算。  2、数据间的逻辑结构包括线性结构、和非线性结构两大类。3、数据的存储结构分为顺序结构、链式存储结构、索引存储结构、散列存储结构。

二、填空题  1、数据的逻辑结构正确的是 数据的逻辑结构是数据间的关系的描述。

2、以下术语与数据的存储结构无关的是  队列。

3、下列算法的时间复杂度是   O( n)         For (i=1;I<=n;i++)           c[i]=I;

第二章一、选择题   1、在一个长度为n的顺序表中第i个元素(1≦i≦n+1)之前插入一个元素时,需向后移动n-i+1个元素

2、线性表a的数据元素的长度为2,在顺序存储结构下LOC(a0)=100,则LOC(a5)=110

3、线性表由(a1,a2,a3,……,an)组成,a1 称为首节点,an称为尾节点,a3称为,a2的直接后继,,a2称为a3的直接前驱。

二、填空题  1、在表长为n的顺序表上做插入运算,平均要移动的节点数为n/2

2、在单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行

s-next=p->next;p->next=s

3、线性表采用链式存储时,结点的地址  连续与否均可

4、下列有关线性表的叙述正确的是  线性表中的元素之间是线性关系

5、指针变量指向的结点变量并未开辟空间,节点空间开辟需要执行的语句是

p=(LinkList*)malloc(sizeof(LinkList));

第三章一、填空题  1、栈的操作原则是  先进后出 ,队列的操作原则是先进先出

2、循环队列用数组data[max]存放其元素值,已知其头、尾指针分别是font和rear,则当前队列中元素的个数是 (rear-front+max)%max

3、假设以S和X分别表示进栈和出栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到输出的序列为bceda

二、选择题  1、循环队列是空队列的条件是      Q->REAR==Q->front

2、链栈与顺序栈相比,比较明显的优点是       不会出现上溢的情况

3、设数组Data[n]作为循环队列Q的存储空间,front为对头指针,raer为队尾指针,则执行入队操作的语句为       Q->rear=(Q->rear+1)%n

4、数据元素进栈次序为1,2,3,进栈过程中允许出栈,出栈顺序   123 132 213 231 321

5、循环队列的优点  用数组实现队列时,如果不移动,随着数据的不断读写,会出现假满队列的情况。即尾数组已满但头数组还是空的;循环队列也是一种数组,只是它在逻辑上把数组的头和尾相连,形成循环队列,当数组尾满的时候,要判断数组头是否为空,不为空继续存放数据;可以有效的利用资源;

第四章一、填空题  1.空串是含有零个字符的字符串,长度为    0

2.两个串相等的充分必要条件是     串的长度和相对应的字符均相同

3.串的两种最基本的存储方式是   顺序串 和   链串

二、选择题 1、空串与空白串     不相同

2、若串s1=”hello”,s2=”world“,那么执行strlen(strcat(s1,s2))后的结果是     10

第五章一、填空题 1.、假设以列优先顺序存储二维数组A[5][8],其中元素A[0][0]的存储地址为LOC(a00),且每个元素占4个存储单元,则数组元素A[i][j]的存储地址为                                       LOC(a00)+(j×5+i)×4 

2、已知广义表LS=((a,x,y,z),(b,c)),用head和tail函数取出原子c的运算是head(tail(head(tail(LS))))

3、设广义表L((),()),则Head(L)是 () ;Tail(L)是(());L的长度是2

4、设对称矩阵A压缩存储在一维数组B中,其中矩阵的第一个元素a11存储在B[0],元素a52存储在吧B[11],则矩阵元素a36存储在        B[17]

三、选择题   1、二维数组A[20][10]采用列优先的存储方法,若每个元素占2个存储单位,且第一个元素的首地址为200,则元素A[][]的存储地址为      576

2、稀疏矩阵的压缩存储方法通常采用      三元组

第六章一、填空题   1、若一个结点的度为0,则称该结点为       叶子

2、深度为3的二叉树最多有     7      个结点

3、一棵含有50个结点的二叉树,度为0的结点个数为5个,度为1的结点个数为     41

4、已知完全二叉树的第4层有2个结点,则其叶子结点数是     5

5、一棵哈夫曼树有19个结点,则其叶子结点数是     10

6、假设用<x,y>表示树的边(其中X是Y的双亲),已知一棵树的边集为{<b,d><a,b><c,g><c,f><c,h>,<a,c>},该树的度是     3

二、选择题   1、以二叉树表作为二叉树的存储结构,在具有n个结点的二叉链表中(n>0),空链域的个数为 n+1  2、下列陈述正确的是   二叉树最多只有两棵子树,并且有左右之分

3、将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为  98

4、已知一棵二叉树的先序遍历为EFHIGJK,中序列为HFIEJGK,则该二叉树根的右子树的根G

5、若由树转化得到的二叉树是非空的二叉树,则二叉树形状是  根结点无右子树的二叉树

6、哈夫曼树是访问叶结点的带权路径长度    最短    的二叉树

第七章一、填空题   1、n个顶点的无向完全图含有       n(n-1)/2条边

2、连通分量是无向图中的  极大连通子图

3、图的两种遍历 深度优先 和   广度优先

4、最小生成树的两种方法是 普里姆方法 和 克鲁斯卡尔方法

二、填空题  1、若m个顶点的无向图采用邻接矩阵存储方法,则该邻接矩阵是一个 对称矩阵     2、最小生成树指的是        连通图的所有生成树中权值之和最小的生成树

3、设有向图G有n个顶点,它的邻接矩阵为A,G中第i个顶点Vi的度为  (A[i,j]+A[j,i])

4、在具有n个顶点的有向图中,所有顶点的出度之和为dout,所有顶点的入度之和为 dout

5、n个顶点的强连通图中至少含有        n条有向边

第七章一、填空题 1、采用二分法查找,要求线性表必须是   顺序  存储的   有序表

2、对于二叉排序树的查找,若根结点元素的值大于被查找元素的键值,则应该在该二叉树的     左子树     上继续查找

3、在查找过程中,若同时还要做增删工作,这种查找则称为 动态查找

4、分块查找的主表被分成若干块,各块之间 有序,块内无序。

二选择题 1、顺序查找法适合于存储结构为        顺序存储或链接存储

2、在散列函数H(K)=K%m中,一般来讲,m应取    素数

3、散列表的地址区间为0~16,散列函数为h(k)=k,采用线性探查法解决冲突,将关键字序列26,25,72,38,1,18,59依次存储到散列表中。元素59存放在散列中的地址为10

4、设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,,71,78,84,92,99},当用二分查找法查找键值为84的结点时,经    4    次比较后查找成功

第八章 一、填空题

1.采用二分法查找,要求线性表必须是顺序存储的有序表。

2.对于二叉排序树的查找,若根节点元素的键值大于被查找元素的键值,则应该在该二叉树的左子树上继续查找。

3.在查找过程中,若同时还要做增删工作,这种查找则称为 动态查找

4.分块查找的主表被分成若干块,各块之间有序,块内无序

二、选择题  1.顺序查找法适合于存储结构为 顺序存储或链式存储的线性表

2.在散列函数H(K)=K%m中,一般来讲,m应取 素数

3.散列表的地址区间为0~16,散列函数为h(k) =k,采用线性探查法解决冲突,将关键字序列26,25,72,38,1,18,59依次存储到散列表中。元素59存放在散列表中的地址为  10

4设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法查找键值为84的结点时,经 4 次比较后查找成功

查找的分析与应用   应用题

1、

0

1

2

3

4

5

6

7

8

9

10

11

12

77

01

14

55

27

68

19

20

84

 

23

11

10

  2、 (1*1+2*2+3*3+4*1)/7=18/7 图的结构分析与应用

三、应用题

1、邻接矩阵存储法

2、邻接表存储法

 

3、最小生成树生成过程 第六章 树和二叉树的结构分析与应用

1、

先序:ABCDEFGHI  中序:BCDAFEHIG  后序:DCBFIHGEA

2、

 

编码:A:11   B:10   C:00   D:010    E:011 3、  

第三章栈和队列的结构分析与应用

1、123 132 213 231 321

2、循环队列的优点   用数组实现队列时,如果不移动,随着数据的不断读写,会出现假满队列的情况。即尾数组已满但头数组还是空的;循环队列也是一种数组,只是它在逻辑上把数组的头和尾相连,形成循环队列,当数组尾满的时候,要判断数组头是否为空,不为空继续存放数据;可以有效的利用资源; 3、将栈中元素逆序 4、将队列中的元素分开,大于等于0的放到一个队列中,小于0的放到另一个队列中。

指针结点空间开辟执行语句1、p=(LinkList *)malloc(sizeof(LinkList));

图2.13单链表的q结点执行语句2、p->next=q->next;

free(q);

 

转载请注明原文地址: https://www.6miu.com/read-1100074.html

最新回复(0)