08年1月数据结构试题与答案.doc

中央广播电视大学2007—2008学年度第一学期“开放本科”期末考试 计算机专业?数据结构?试题 ?2008年1月 一、单项选择题，在括号内填写所选择的标号(每小题2分，共1日分) ?1．下面程序段的时间复杂度为(??? )。 ?? for(int i=0；im；i++) ??? for(int j=0;jn；j十十)?a[i][j]=i*j； ?A．O(m2)??? B，O(n2) ?C．?O(m*n)??? D．?O(m+n) ?2．在二维数组中，每个数组元素同时处于(??? )个向量中。 ??? A. 0??? B．?1 ??? C．?2??? D．?n ?3．设有两个串t和P，求p在t中自次出现的位置的运算叫做(??? )。 ??? A．求子串??? B．模式匹配 ??? C．串替换??? D．串连接 ?4．利用双向链表作线性表的存储结构的优点是(??? )。 ??? A．便于单向进行插入和删除的操作 ??? B. 便于双向进行插入和删除的操作 ??? C. 节省空间 D．便于销毁结构释放空间 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个结点的完全二叉树的高度为(??? )。假定空树的高度为一1。 ??? A．?5??? B．?6 ??? C．?7??? D．?8 7．向具有n个结点的堆中插入一个新元素的时间复杂度为(??? )。 ??? A．O(1)??? B．O(n) ??? C O(log2n)??? D．O(nlog2n) 8．在一棵AVL树中，每个结点的平衡因子的取值范围是(??? )。 ??? A．一l～1??? B．一2～2 ??? C．1～2??? D．0～1 9．一个有n个顶点和n条边的无向图一定是(??? )的。 ??? A. 连通??? B．不连通 ??? C．无回路??? D．有回路 二、填空题，在横线处填写合适的内容(每小题2分，共14分) ??? 1．数据结构包括??????? 、存储结构和对数据的运算这三个方面。 ??? 2．一维数组所占川的空间是连续的。但数组元素不一定顺序存取，通常是校元素的 ??? ????????????????存取的。 ??? 3．将一个n阶刘称矩阵的L三角部分或下三角部分压缩存放于—个??????? 维数组中，则该一维数组需要至少具有 ????????个元素。 ??? 4．对于一棵具有n个结点的树．该树中所有结点的度数之和为??????? ?。 ??? 5．在—棵高度为3的理想平衡二叉树中，最少含有??????? 个结点，假定树根结点的高度为o。 ??? 6．假定对长度n＝50的有序表进行折半有哪些信誉好的足球投注网站，则对应的判定树中最底层的结点数为 ?????????个。 7．用邻接矩阵存储图，占用的存储空间与图中的 ???????????数有关。 ? 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小 ??? 题2分，共“分) ?(??? )1．算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 ?(??? )2．用字符数组存储长度为n的字符串，数组长度至少为n+1。 ?(??? )3．在用循环单链表表示的链式队列中，可以不没队头指针，仅在链尾设置队尾指针。 ?(??? )4．邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。 ?(??? )5．对一个无向连通图进行—次深度优先有哪些信誉好的足球投注网站遍历时可以访问到图中的所有顶点。 ?(??? )6．在索引顺序结构的有哪些信誉好的足球投注网站中，对索引表只可以采取顺序有哪些信誉好的足球投注网站，不可以采用折半有哪些信誉好的足球投注网站。 ?(??? )7．图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 四、运算题(每小题6分，共30分) ??? 1．假定一棵二叉树广义表表示为a(b(c)，d(e，f))，分别写出对它进行中序、后序、按层遍历的结果。 ??? 中序： ??? 后序： ??? 按层： ??? 2．—个—维数组a[12]中存储着有序表(15，26，34，39，45，56，58，63，74，76，80，86)，根据折半有哪些信誉好的足球投注网站所刘应的判定树，写出该判定树中度为]的结点个数，并求出在等概率情况下进行成功有哪些信誉好的足球投注网站时的平均有哪些信誉好的足球投注网站长度。 ??? 度为l的结点个数： ??? 平均有哪些信誉好的足球投注网站长度： ??? 3．假定，—个线性序列为(38，42，55，15，23，44，30，74，48，26)，根据此线性序列中元素的排列次序生成—棵二