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

班级 姓名 学号密 封 装 订 线 电子信息工程 学院 11 级 数字媒体 专业数据结构试卷2012 2013 学年度第 2 学期期末考试 （ A ）卷注意事项： 1、考前请将密封线内填写清楚 2、所有答案请直接答在试卷上（或答题纸上） 3、考试形式：闭 卷 4、本试卷共 5 大题，满分100分。考试时间 120 分钟5、评分一律加分，不写减分题号一二三四五总分评卷人复查人得分 得 分一、单项选择题（本题共 15 小题，每小题 2 分，共 30 分）1、算法的时间复杂度取决于（ ）。A问题的规模 B待处理数据的初态 CA和BD都不是2、下面的叙述不正确的是（ ）。A线性表在链式存储时，查找第i个元素的时间同i的值成正比B线性表采用链式存储比采用顺序存储浪费更多的空间C线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D线性表在顺序存储时，查找第i个元素的时间同i的值无关3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上说法错误的是（ ）。A（1），（2） B（1） C（1），（2），（3） D（2）4、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。AO(0) BO(1) CO(n) DO(n2) 5、用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头、队尾指针都可能要修改6、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D. 线性表7、假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m8、下面关于串的的叙述中，哪一个是不正确的？（ ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储9、若串S1=ABCDEFG，S2=9898，S3=#，S4=012345，执行Concat(Replace(S1, Substring(S1, length(S2), length(S3), S3), Substring(S4, Index(S2, 8), length(S2)其结果为（ ）。AABC#G0123 BABCD#2345 CABC#G2345 DABC#G123410、设有数组Ai, j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+22511、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A.13 B. 33 C. 18 D. 4012、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。ACABDEFG BABCDEFG CDACEFBG DBADCFEG13、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）。A、 E B、 F C、 G D、 H14、某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ ）编号的。A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 15、一个有向无环图的拓扑排序序列（ ）是唯一的。A一定 B不一定得 分二、填空题（每小题 2 分，共 30 分）1、抽象数据类型的定义仅取决于它的一组_ ，而与 _无关，即不论其内部结构如何变化，只要它的_ 不变，都不影响其外部使用。2、数据结构中评价算法的两个重要指标是 。3、设单链表的结点结构为(data, next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：_；_；4、在一个长度为n的顺序表中第i个元素（1=ilink-datalink-data ) (B)_; if ( r-link-dataq-link-data ) s= (C)_ ; (D)_ =s-link; s-link= (E)_ ; (F)_ _=s; (G) _; else (H)_ _; s:=q.link; (I)_ _; free(s); free(q);2、假设按低下标优先存储整型数组A（-3:8，3:5，-4:0，0:7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？得 分五、算法设计题（本题共 1 小题，共 10 分）111、设有一链队列的结点结构和队列结构分别为：typedef struct QNode /队列的链式存储结构 QElemType data; struct Q