数据结构与算法考试参考题
专业：计算机科学与技术 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-1 ）
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.假定对有序表：（ 3.4.5.7.24.30.42.54.63.72.87.95 ）进行折半查，若查元素24（ 程序设定为向下取整 ），需依次与（ 30.5.7.24 ）元素进行比较。
三、解答（ 50分 ）
1. 二维数组A[10.20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[1.1]的存储地址为300，则请算A[10,10]的存储地址。
答： 300+（ 9*20+10 ）*
4=300+190*4=300
+760=1060
2. 已知树如右图所示：
（1）画出由该树转换得到的二叉树；

原图
答图：先序中序后序遍历二叉树
 

（2）写出该二叉树的后序序列：
答： 后序序列为：E B K J I H G F D C A
3. 试给出如图所示的邻接矩阵和邻接表表示。

答： 邻接矩阵

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。