搜索
数据结构试卷第1页（共2页）四川农业大学网络教育专科考试数据结构试卷（课程代码352098）本试题一共二道大题，共2页，满分100分。考试时间90分钟。注意：1、答案必须填写在答题纸上，题号不清或无题号的以零分计。2、答题前，请在答题纸上准确、清楚地填写各项目；3、学号、考点名称、考室号、姓名、身份证号、课程代码、课程名称、培养层次等，不写、乱写及模糊不清者，答题纸作废；4、开卷考试，若有雷同以零分计。一、填空题（每空3分，共60分）1、数据结构在计算机中的表示称为数据的__存储结构。2、串的长度是指____串中所含字符的个数_____。3、序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择___直接插入算法__排序算法。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___。12、具有500个结点的二叉树，其深度至少为______9___。13、线性表的链式存储结构是通过___指针_____来间接反映数据元素之间逻辑关系的。数据结构试卷第2页（共2页）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、给两个键值K1≠K2，而散列函数值H(K1)=H(K2)，则K1和K2是____同义词_______。19、一般可以利用__________为递归问题设计出非递归算法。20、假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为____55_______。二、简答与应用题（共40分）1、以下为带空头结点的链式队列，请写出该队列的入队和出队算法(10分)。参考算法：/*设数据元素的类型为DataType*/structnode{DataTypedata;/*存储元素*/structnode*next;};/****************************************//*入队*//****************************************/EnQueue(structnode*real,DataTypex){structnode*p;p=(structnode*)malloc(sizeof(structnode));p-data=x;p-next=NULL;/*保证p是尾结点*/real-next=p;real=p;/*real指向队尾*/数据结构试卷第3页（共2页）}/****************************************//*出队*//****************************************/OutQueue(structnode*front,structnode*p){if(front-next==NULL)/*队空*/error(QueueisEmpty!);else{p=front-next;/*保存队首结点*//*队首结点脱链*/Front-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,16,18],19,20,[24,27,29,30,35,36,40,41]查找成功。4、画出将序列(72，73，71，23，94，16，05，68，48，26)构建成堆的过程（10分）。数据结构试卷第4页（共2页）