《数据结构》期中试卷-2015-2016学年第一学期.doc

北京理工大学珠海学院 2015～2016学年第一学期《数据结构》期中试卷 诚信声明 考场是严肃的，作弊是可耻的，对作弊人的处分是严厉的。 我承诺遵守考场纪律，不存在抄袭及其它违纪行为。 考生（承诺人）签字： 专业： 班级： 学号： 适用年级专业：14级计科，网工，数媒专业 试卷说明：闭卷，考试时间90分钟 题号 一 二 三 四 总分 得分 一、单项选择题（每小题2分，共30分）【得分： 】 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 1、设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。 A. 线性表的顺序存储结构 B. 栈 C. 队列 D. 线性表的链式存储结构 2、以下算法的时间复杂度为( ) 。 void fun(int n) { int i=l; while (i=n) i=i*2; } A. O(n) B. O(n2) C. O(nlog2n) D. O(log2n) 3、带头结点的单链表为空的判定条件是（ ）。 A. head==NULL B. head-next==NULL C. head-next==head D. head!=NULL 4. 在一个具有n个单元的顺序栈中，假设栈底是存储地址的端，现以top作为栈顶指针，操作时，top的变化是()。 A. top=top+1 B. top=top-1 C. top不变D. top不确定 b，c，d则出栈序列不可能的是( )。 A. a，b，c，d B、c，b，a，d C. d，c，b，a D、d，b，c，a 6、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A[6][8]的起始地址为（ ）。 A. SA+210 B. SA+171 C. SA+204 D. 以上都不对 7、以下关于单链表的叙述中，错误的是（ ） 。 A. 在单链表中插入一个节点必须先找到其前趋节点 B. 在单链表中删除一个节点必须先找到其前趋节点 ^ C. 在单链表中只能通过节点的next指针向后查找节点 D. 在单链表中查找第i个节点的时间复杂度为0(1) 8. 链表不具有的特点是（ ）。 A　 B C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 9. 在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（ ）。 Ａ. s-next=p-next; p-next=s; Ｂ. p-next=s-next; s-next=p; Ｃ. q-next=s; s-next=p; Ｄ. p-next=s; s-next=q; 10. 若某线性表中最常用的操作是取第个元素和找第个元素的前趋元素，则采用（ ）存储方式最节省时间。 顺序表 单链表 双链表 循环链表 13、与单链表相比，双链表的优点之一是（ ）。 A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.前后访问相邻节点更灵活 14.循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空和为满的条件分别是（ ） A. Q.front!=Q.rear, Q.front==Q.rear B. Q.front==Q.rear , Q.front!=Q.rear C.Q.front==Q.rear, Q.front==(Q.rear+1)%n D.Q.front==Q.rear , Q.front!=(Q.rear+1)%n 15. 利用栈求表达式的值时数栈PND，有两个存储单元下列表达式中发生溢出的是 ）。 A. A-B*(C-D) B. (A-B)*C-D C. (A-B*C)-D D. (A-B)*(C-D) 二、填空题（每空2分，共10分 ）【得分： 】 1. 若一个算法中的语句频度之和为T（n）=3n+n*log2n+4，则算法的时间复杂度为 __ _ __ _。 2. 对于n阶对称矩阵，进行压缩存储，