数据结构(本) 期末考试试题及参考答案

四川农业大学网络教育专升本考试

数据结构试卷

（课程代码252259）

一、填空题（每空2分，共50分）

数据结构在计算机中的表示称为数据的_（映像）称为数据的物理（存储）结构。

串的长度是指一串中所含不同字母的个数o

序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数最少原则而言，应选

择_采用二分法查找元素A[4]的过程中比较元素的顺序排序算法。

一棵二叉树有67个结点，这些结点的度要么是0,要么是2。这棵二叉树中度为2的结点

有—55个。

最节省空间的串存储结构是一编址方式。

栈又称为一先进后出____________的线性表。

在图结构中，前驱元素和后继元素之间存在着一是一对i的联系。

存储地址与关键字之间存在某种映射关系的存储结构为—树形存储结构

DFS可以判断出一个有向图中是否有环。

若堆栈的入栈序列为123,…输出元素i需要进行—n,n=n-l+l次出栈操

作。

在顺序存储的完全二叉树中，若编号为i的结点有父结点，则其父结点编号为

具有500个结点的二叉树，其深度至少为_（log2n）+1o

线性表的链式存储结构是通过一指针来间接反映数据元素之间逻辑关系的。

设一个散列表的容量为M,用线性探测法解决冲突若要查找一个键值，至多需要进行

_、（n-1）/2次比较。

依次在初始为空的队列中插入元素a,b,cde以后，紧接着作了三次删除操作，此时的队首

元素是—按照a、b、c、d、e的次序进入栈S,当一个元素从栈中出来后立即进入队

列Q。

按照二叉树的定义，具有3个结点的二叉树有_5种形态。

对于线性表(18,25,63,50,42,32,90.66)进行散列存储时，若选用H(K)=K%9作为散列函数,

则散列地址为0的元素有9个。

给两个键值K1WK2,而散列函数值H(K1)=H(K2),则K1和K2是24。

一般可以利用一已知后序前中序求先序的算法为递归问题设计出非递归算法。

假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应

为b63。

带权路径最小的二叉树称为—最优二叉树或哈夫曼树o

在一个无向图的邻接表中，若表结点的个数是m,则图中边的条数是一为从m中取2的组

合数，为m(m-l)/2条。

在有序表(12,24,36,48,60,72,84)中二分查找关键字24成功时需要进行_2

次关键字比较。

生成树是图的极小连通子图，如果在生成树中增加一条边就会出现——个连通图的生成

树是一个极小连通子图；如果去掉生成树的一条边就会变成非连通图。

n个顶点的有向完全图中含有向边的数目最多为_23o

二、简答与应用题(共50分)

以下为带空头结点的链式队列，请写出该队列的入队和出队算法(10分)。

rearD

/*设数据元素的类型为DaiaType*/

structnode

DataTypedata;/*存储元素*/

structnode*ncxl;

};

/****************************************/

入队*/

/****************************************/

EnQueue(structnode*reakDataTypex)

{

structnode*p;

p=(structnode*)nialloc(sizeof(structnode));

p->data=x;

p->next=NULL;/*保证p是尾结点*/

real->next=p;

real=p;/*real指向队尾*/

/****************************************/

出队*/

/****************************************/

OutQueue(structnode*front,structnode*p)

if(fronl->next==NULL)/*队空*/

crror("QueueisEmpty!");

else

{

p=front->next;/*保存队首结点*/

/*队首结点脱链*/

Front->next=p->ncxt;

对于下面的无向网络:

画出表示此网络的邻接矩阵。（3分）

画出用克鲁斯卡尔算法构造其最小生成树的过程。（6分）

画出用普里姆算法构造其最小生成树的过程。（6分）

设有升序排列的线性表（2.4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41）,用二分查找法进

行查找。完成以下各小题：

画出查找关键字4的过程（5分）

画出查找关键了35的过程（6分）

计算该表在等概率的情况查找成功的平均查找次数为多少？（4分）

画出将序列（72,73,71,23,94,16,05,68,48,26）构建成堆的过程（10分）。

a

参考答案比较次数交换沙

）初始：72,73,71,23,94,16,05,68

第1趟：72,73,71,23,94,16,05,6810

第2趟:71,72,73,23,94,16,05,6822

第3趟：23,71,72,73,94,16,05,6833

第4趟：23,71,72,73,94,16,05,6810

第5趟：16,23,71,72