电大数据结构历年试题和答案（精）请勿转载.pdf

试卷代号:1010 座位号巨口 中央广播电视大学2007-2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题 zoos年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号(每小题2分，共18分) 1.下面程序段的时间复杂度为( )。 for(inti=0;im;i十十) for(intj=0;Jn;J++)a[i][j]=i*J; A.O(m2) B.O(nZ) C.0(m*n) D.0(m十n) 2.在二维数组中，每个数组元素同时处于( )个向量中。 A.0 B.1 C.2 D.n 3.设有两个串t和U，求p在，中首次出现的位置的运算叫做( A.求子串 I3.模式匹配 C.串替换 D.串连接 4.利用双向链表作线性表的存储结构的优点是( )。 .便于单向进行插入和删除的操作 便于双向进行插人和删除的操作 节省空间 便于销毁结构释放空间 5.设链式栈中结点的结构为(data}link)，且top是指向栈顶的指针。若想在链式栈的栈 顶插人一个由指针s所指的结点，则应执行( )操作。 A.top一link=s; B.s一link=top一link;top一link=s; C.s一link=top;top=s; D.s一link二top;top=top一link; 6.一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为一to A.5 B.6 C.7 D.8 7.向具有n个结点的堆中插人一个新元素的时间复杂度为( )。 A.O(1) B.0(n) C.O(log2n) D.O(nlogZn) 8.在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A.一1^-1 13，一2一2 C.1一2 D.0}-1 9.一个有n个顶点和n条边的无向图一定是( )的。 A.连通 B.不连通 C.无回路 D.有回路 得 分 评卷人 二、填空题，在横线处填写合适的内容(每小题2分，共 14分) 1.数据结构包括 、存储结构和对数据的运算这三个方面。 2.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 存取的。 3.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中.则该一 维数组需要至少具有 个元素。 4.对于一棵具有n个结点的树，该树中所有结点的度数之和为_