卷号：7004（A） 浙江广播电视大学2006年1月期末考试 计算机各专.doc

卷号：7004（A） 浙江广播电视大学2006年1月期末考试 计算机各专科专业数据结构试题 2006年1月 一、单选题 （每空2分，共20分） 1．一个数组元素a[i]与的表示等价。 *(a+i) B． a+i C． *a+i D．a+i 2．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 3．队列的删除操作是在（ ）进行。 A．队首 B．队尾 C．队前 D．对后 4．二叉树上叶结点数等于（ ）。 A．分支结点数加1 B．单分支结点数加1 C．双分支结点数加1 D．双分支结点数 减1 5．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序 A．插入 B．交换 C．选择 D．归并 6．由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A．51 B．23 C．53 D．74 7．某程序的时间复杂度为（3n+100×log2n+ nlog2n）, 其数量级表示为（ ）。 A．O（n） B．O（nlog2n） C．O（100） D．O（log2n） 8. 从二叉有哪些信誉好的足球投注网站树中查找一个元素时，其时间复杂度大致为（ ）。 A O(n) B O(1) C O(log2n) D O(n2) 9．在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子(等于（ ）。 A．n/m B．m/n C．n/(n+m) D．m/(n+m) 10．在一棵二叉有哪些信誉好的足球投注网站树中，每个分支结点的左子树上所有结点的值一定（ ）该结点的值。 A．小于 B．大于 C．不小于 D．大于等于 二、填空题（每空2分，共30分） 1．一种抽象数据类型包括 和 两个部分。 ________元素和________元素两类。 3．从一个链栈中删除一个结点时，需要把栈顶结点的_________域的值赋给________。 4．在进行函数调用时，需要把每个实参的值和调用后的________传送给被调用的函数中。 5．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 6．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为________和________条。 7．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为________。 8．若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为________，右孩子元素为________，双亲元素(i0)为________。 三、运算题（每小题5分，共20分） 1．已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 ________, ________, ________, ________, ________, ________, ________。 2. 假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分的结果为______