试题(张艳玲)-6

《试题(张艳玲)-6》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学院领导审批并签名广州大学学年第学期考试卷课程考试形式（闭卷，考试）信息学院系专业级班学号：姓名：题次—二三四五/、总分评卷人分数201010302010100评分一、填空题：（每空2分，共20分）1、抽象数据类型的特点是使用与实现分离。2、算法的一个特性是，即算法必须执行有限步就结束。3、一维数组所占用的空间是连续的。但数组元素不一定顺序存放，而是按元素的存放的。4、将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储个矩阵元素。5、在单链表中设置表头结点的作用是在插入和删除表中第一个元素时不必对逬行特殊处理。6、中缀表达式3*（x+2）-5所对应

2、的后缀表达式为。7、广义表A（（a，b，c），（d，e，f））的表尾为。8、假定一棵三叉树（即度为3的树）的结点个数为50,则它的最小高度为o假定根结点的高度为0。9、101个顶点的连通网络N有100条边，其中权值为1，2,3,4,5,6,7,8,9,10的边各10条，则网络N的最小生成树各边的权值之和为。二、单项选择题（每空1分，共10分）1.一个数组元素a[i]与（）的表示等价。A.*（a+i）B.a+iC.*a+iD.&a+i2.—种抽象数据类型包括数据和（）两个部分。A.数据类型B.操作C.数据抽象D.类型说明3.以下说法错误的是（）。A.抽象数据类型具有封装性。B.抽象数据

3、类型具有信息隐蔽性。C.抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。D.抽象数据类型的一个特点是使用与实现分离。4、在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功的数据平均比较次数为（）。A.nB.n/2C.（n+l）/2D.（n-l）/25、在一个长度为n的顺序表中向第i个元素（0link==NULL;C.first->link==

4、first;D.first!=NULL;7、桟的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置8、在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。A.空间B.地址C.返回地址D.副本9、在一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.根结点D.空结点10、在一个带权连通图G中，权值最小的边一定包含在0的（）生成树中。A.某个最小B.任何最小C.广度优先D.深度优先三、判断题（在括号内填上“v”或“X”，每题1分，共

5、io分，做错不倒扣）1、（）数据结构是具有结构的数据对象。2、（）数据结构是指相互之间存在一种或多种关系的数据元素的全体。3、（）数组是一种静态的存储空间配置，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时逬行配置。4、（）n阶三对角矩阵总共n2个矩阵元素中最多只有3n-2个非零元素，因此它是稀疏矩阵。5、（）链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻辑顺序。6、（）若让元素1,2,3依次进桟，则出栈次序3,1，2是不可能出现的情况。7、（）递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需

6、要分配额外的空间和传递数据和控制，所以时间与空间幵销都比较大。8、（）在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别逬行前序遍历和后序遍历，则具有相同的遍历结果。9、（）如果无向图中各个顶点的度都大于2,则该圄中必有回路。10、（）当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。四、计算题/画图题/证明题(30分)1.指出算法的功能并求出其时阎复杂度。voidmatrimult(inta[][],intb[][],intc[][],intM,intN,intL){//数组a[M][N]、b[N][L]、c[M][L]均为整型数组inti，j，k;for

7、(i=0;i

8、j];}}2、对于一个nxn的矩阵A的任意矩阵元素a[i]U]，按行存储时和按列存储时的地址之差是多少。(若设两种存储的幵$台存储地址LOC(0,0)及元素所占存储单元数d相同)3、设散列表的长度m=13;散列函数为H(K)=K%m，给定的关键码序列为19,14,23,01，68,20,84,27,55,