数据结构及算法-考试范围题及答案解析

数据结构与算法考试参考题

专业：计算机科学与技术13年

一、单选（30分

1.在数据结构中，数据的逻辑结构可分（B.线性结构和非线性结构

2.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用（C.指向后继元素的指针表示

3.设p指向单链表中的一个结点。S指向待插入的结点，则下述程序段的功能是（D.在结点*p之前插入结点*s

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

t=p->data;p->data=s->data;s->data=t;

B.在p所指结点的元素之前插入元素D.在结点*p之前插入结点*s

4.栈和队列都是（C:链式存储的线性结构

A:限制存取位置的线性结构B:顺序存储的线性结构

C:链式存储的线性结构D:限制存取位置的非线性结构

5.下列关于线性表的基本操作中,属于加工型的操作是（B初始化、插入、删除操作

6.根据定义,树的叶子结点其度数（B.必等于0

7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（A.数组的元素处在行和列两个关系中

8.从广义表LS=（（p,q,r,s中分解出原子q的运算是<B.head<tall<head<LS»>

9.在具有n个叶子结点的满二叉树中，结点总数为（C.2n-l

10.若<Vi,Vj>是有向图的一条边，则称（D.Vi与Vj不相邻接

11.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（B.2n个指针域其中n+1个指针为NULL

12.在一个无向图中，所有顶点的度数之和等于边数的（B.2倍

13.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为

（A.O<n>

14.散列法存储中出现的碰撞（冲突现象指的是（B.不同关键码值对应到相同的存储地址

15.循环链表适合的查找方式是（A.顺序

二、填空（20分

1.若一棵完全二叉树中含有121个结点，则该树的深度为（7

2.若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的

3.二叉树的遍历主要有先序遍历、后序遍历和（中序遍历三种。

4.深度为3的完全二叉树至少有（4个结点。

5.若图的邻接矩阵是一个对称矩阵，则该图一定是一个

6.若某无向图G的邻接表如下图所示，试给出以顶点V3为出发点.按广度优先搜索所产生的结点序列（V3-2V1-V4-V5

7.在无向图中，若从顶点a到顶点b存在（路径，则称a与b之间是连通的。

8.我们通常把队列中允许删除的一端称为（队头

9.表头和表尾均为（a,<b,c>的广义表L=」_

10.假定对有序表：（进行折半查找，若查找元素24（程序设定为向下取整，需依次与（元素进行比较。

三、解答（50分

1.二维数组A[10.20]采用按行为主序的存储方式，每个元素占4个存储单元，若的存储地址为300,则请算A[10,10]的

存储地址。

答：300+（9*20+10*

4=300+190*4=300

+760=1060

2.已知树如右图所示：

(1画出由该树转换得到的二叉树；

原图答图：

(2写出该二叉树的后序序列：

答：后序序列为：EBKJIHGFDCA

3.试给出如图所示的邻接矩阵和邻接表表示。

答：邻接矩阵

4.己知某二叉排序树10个结点的值依次为1-10,其结构如图所示,试标出该二叉排序树各结点

所对应的具体值。

5.试构造下图的最小生成树，要求分步给出构造过程。

原图:

6.从一个空的二叉排序树开始，依次插入关键字试画出插入关键字后的二叉排序树，并计算查

找成功时的平均查找长度。averagesearchlength平均查找长度

答：ASL=<l*l+2*2+3*3+4*l>/7=l§<7

主要思想是以第一个数为标准，将比此数小的放在左边,大的放在右边,再一一插入,通过比较,找到末端为止。如

13比25小,便在左边,后15小于25,又在25左端,但是比13大,故放在了13的右边,每个数都是这样找到自己的

位置的。

7.为关键字(构造一个长度为7的散列表,设散列函数为h<key>=key%7,用开放定址法解决

冲突的探查序列是

Hi=<h<key>+<key%5+l»%70WiW6

<1>画出构造所得的散列表；

〈2〉求出在等概率情况下查找成功时的平均查找长度。

答：

ASL=<l+l+3+2+4>/5=ll/5

H<17>=17%7=3

H<33>=33%7=5

H<31>=31%7=3冲突

?%=(3+1(31%5+1%7

=5%7=5冲突

Hi=<3+2<31%5+1»%7

=<3+4>%7=0

H<40>=40%7=5冲突

Hi=<5+l<40%5+0»%7

=6%7=6

H<48>=48%7=6冲突

Hi=<6+1<48%5+1»%7

=<6+4>%7=3冲突

Hi=<6+2<48%5+l»%7

=<6+8>%7=0冲突

Hi=<6+3<48%5+l»%7

=<6+12>%7

=18%7

=4

0123456

3117483340

8.……顶点C出发进行深度优先遍历的序列。

原图：

答：CDABFE

完

1.已知一棵树边的集合为

{<i,m>,<i,n>,<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,1>,<c,h>,<a,c>},

请画出这棵树,并回答下列问题：

(1哪个是根结点？(2哪些是叶子结点？(3哪个是结点g的双亲？(4哪些是结点g

的祖先？(5哪些是结点g的孩子？(6哪些是结点e的孩子？

(7哪些是结点e的兄弟？哪些是结点f的兄弟？(8结点b和n的层次号分别是什么？

(9树的深度是多少？

(10以结点c为根的子树深度是多少？1.解答：

根据给定的边确定的树如图5-15所示。其中根结点为a；叶子结点有：d、m、n、j、k、f、

1;

c是结点g的双亲；

a、c是结点g的祖先；

j、k是结点g的孩子；m>n是结点e的子孙；e是结点d的兄弟；

g、h是结点f的兄弟；

结点b和n的层次号分别是2和5；树的深度为5。

4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后

序遍历序列。

4.解答：

先序序列：ABDHIEJKCFLG中序序列：1IDIBJEKALFCG后序序列：HIDJKEBLFGCA

数据结构：在一棵空的二叉查找树中依次插入关键字学列为54,18,66,87,36,12请画出所

得到的二叉排序树

数据结构题：二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A

[0][0]的存储地址是200

则A[6][12]的地址是326。

还有这题：二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且

A[10][5]的存储地址是1000,则A[18][9]的地址是1208。

答案

第一题: