琼州学院生物科学与技术学院

《琼州学院生物科学与技术学院》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、班级姓名学号密封装订线电子信息工程学院11级数字媒体专业《数据结构》试卷2012——2013学年度第2学期期末考试（A）卷注意事项：1、考前请将密封线内填写清楚2、所有答案请直接答在试卷上（或答题纸上）3、考试形式：闭卷4、本试卷共5大题，满分100分。考试时间120分钟5、评分一律加分，不写减分题号一二三四五总分评卷人复查人得分得分一、单项选择题（本题共15小题，每小题2分，共30分）1、算法的时间复杂度取决于（）。　　A．问题的规模B．待处理数据的初态C．A和B　　D．都不是2、下面的叙述不正确的是（）。A．线性

2、表在链式存储时，查找第i个元素的时间同i的值成正比B．线性表采用链式存储比采用顺序存储浪费更多的空间C．线性表在顺序存储时，查找第i个元素的时间同i的值成正比D．线性表在顺序存储时，查找第i个元素的时间同i的值无关3、(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上说法错误的是（）。A．（1），（2）　B．（1）　　C．（1）

3、，（2），（3）　D．（2）4、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A．O(0)B．O(1)C．O(n)D．O(n2)5、用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改6、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表7、假设以数组A[

4、m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m8、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储9、若串S1=‘ABCDEFG’，S2=‘9898’，S3=‘###’，S4=‘012345’，执行Concat(Replace(

5、S1,Substring(S1,length(S2),length(S3)),S3),Substring(S4,Index(S2,‘8’),length(S2)))其结果为（　）。A．ABC###G0123　　　　B．ABCD###2345C．ABC###G2345　　　　D．ABC###G123410、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+

6、222D.BA+22511、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.4012、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（　）。A．CABDEFG　B．ABCDEFG　　C．DACEFBGD．BADCFEG13、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（　　）。A、E　B、F　　C、G　　D、H14、

7、某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（　）编号的。A.中序遍历序列　　　　　B.前序遍历序列C.后序遍历序列　　　　　D.层次顺序15、一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定得分二、填空题（每小题2分，共30分）1、抽象数据类型的定义仅取决于它的一组_，而与　　　　　　　_无关，即不论其内部结构如何变化，只要它的_

8、不变，都不影响其外部使用。2、数据结构中评价算法的两个重要指标是　　　　　　　　　　　　　　　　　。3、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：___________________；________