352098_1112B数据结果参考模板

1、四川农业大学网络教育专科考试数据结构 试卷（课程代码 352098）本试题一共二道大题，共2页，满分100分。考试时间90分钟。注意：1、答案必须填写在答题纸上，题号不清或无题号的以零分计。2、答题前，请在答题纸上准确、清楚地填写各项目；3、学号、考点名称、考室号、姓名、身份证号、课程代码、课程名称、培养层次等，不写、乱写及模糊不清者，答题纸作废；4、开卷考试，若有雷同以零分计。一、填空题（每空3分，共60分）1、数据结构在计算机中的表示称为数据的_存储结构。2、串的长度是指_串中所含字符的个数_。3、序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择_直接插入算法_排

2、序算法。4、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_33_个。5、最节省空间的串存储结构是_节点存储6、栈又称为_后进先出_的线性表。7、在图结构中，前驱元素和后继元素之间存在着_一对一，一对多，多对多的联系。8、存储地址与关键字之间存在某种映射关系的存储结构为_散列存储结构_。9、_深度优先遍历_可以判断出一个有向图中是否有环。10、若堆栈的入栈序列为1,2,3,n-1,n，输出元素i需要进行_ n-i+1_次出栈操作。11、在顺序存储的完全二叉树中，若编号为i的结点有父结点，则其父结点编号为_2i_。1 / 412、具有500个结点的二叉树，其深

3、度至少为_9_。13、线性表的链式存储结构是通过_指针_来间接反映数据元素之间逻辑关系的。14、设一个散列表的容量为M，用线性探测法解决冲突.。若要查找一个键值，至多要进行_ M _次比较。15、依次在初始为空的队列中插入元素a,b,c,d,e以后，紧接着作了三次删除操作，此时的队首元素是_ b _。16、按照二叉树的定义，具有3个结点的二叉树有_5_种形态。17、对于线性表（18,25,63,50,42,32,90,66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有_3_个。18、给两个键值K1K2，而散列函数值H(K1)=H(K2)，则K1和K2是_同义词_。

4、19、一般可以利用_为递归问题设计出非递归算法。20、假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为_55_。二、简答与应用题（共40分）1、 以下为带空头结点的链式队列，请写出该队列的入队和出队算法(10分)。参考算法：/* 设数据元素的类型为DataType */struct node DataType data; /* 存储元素 */ struct node *next; ;/*/* 入队 */*/EnQueue (struct node *real, DataType x) struct node *p; p = (struct node *)mall

5、oc(sizeof(struct node); p->data = x; p->next = NULL; /* 保证p是尾结点 */ real->next = p; real = p; /* real指向队尾 */ /*/* 出队 */*/OutQueue (struct node *front, struct node *p) if (front->next = NULL) /* 队空 */ error("Queue is Empty!"); else p = front->next; /* 保存队首结点 */ /* 队首结点脱链 */ Fr

6、ont->next = p->next; 2、 对于下面的无向网络：1) 画出表示此网络的邻接矩阵。(4分)2) 画出用克鲁斯卡尔算法构造其最小生成树的过程。(6分)3、 设有升序排列的线性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），用二分查找法进行查找。完成以下各小题：3) 画出查找关键字4的过程（5分）4) 计算该表在等概率的情况查找成功的平均查找次数为多少？（5分）参考答案：初态：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第1次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第2次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第3次：2, 4, 7, 10, 12, 1