国开大学2015年01月1252《数据结构（本）》期末考试参考答案

试卷代号：1252国家开放大学(中央广播电视大学)2014年秋季学期“开放本科”期末考试数据结构(本)试题2015年1月题号二三四分数D.只要存储数据元素的值5.元素2,4,6,8按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是()(进栈出栈可以交替进行)。6.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为()。A.x=r→data;r=r→next;nextdataC.x=f→data;f=nextnextdata7.设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则数组中第38号元素对应于矩阵中的元素是()。(矩阵中的第1个元素是a,i)A.一个和两个B.两个C.一个D.两个和一个9.一棵有n个结点，采用链式存储的二叉树中，共有()个指针域被有效使用(即指针域为非空)。10.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为()。A.i/2.0B.i/2向下取整11.设一棵哈夫曼树共有2n+1个结点，则该树有()个非叶结点。12.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有()个非叶子结点(根为第一层)。二、填空题(每小题2分，共24分)二、填空题(每小题2分，共24分)13.如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。C.aebcdfD.aebcfd14.一组记录的关键字序列为(56,30,89,66,48,50,94,87,100),利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为()。A.30,50,48,56,66,89,94,100,B.50,30,48,56,66,89,94,87C.48,30,50,56,66,89,9D.50,30,48,66,56,89,94,87,15.线性表以()方式存储，能进行折半查找。A.关键字有序的链接B.顺序C.关键字有序的顺序D.数组16.数据的逻辑结构在计算机中的表示称为结构。17.求两个n阶矩阵的乘积，算法的基本操作为,时间复杂度为18.设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为8,9,10,11,…25,某人想要在第8个元素前插入1个元素7(也就是插入元素作为新表的第8个元素),他的做法是从第8号元素开始，直到第25号元素依次向后移动1个位置，然后把7存放在8号位置，其结果是新表中第25号元素的值为 指向q。 22458928.(1)对给定权值3,1,4,4,5,6,构造深度为5的哈夫曼树。(设根为第1层)A7A9四、程序填空题(每空2分，共16分)四、程序填空题(每空2分，共16分)31.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{if(a[i].key<a[k].32.设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同),写出相关语句(1)使该单向链表成为单向循环链表(2)删去a结点2015年1月