厦门理工学院12级数据结构期末试卷与答案.docxVIP

第 PAGE 5 页 共 5 页 PAGE 考 生 信 息 栏 系 专业 级 班级 姓名 学号 装 订 线 厦门理工学院试卷 2012－2013学年 第 一 学期 课程名称 数据结构与算法 试卷 卷别 □A □ B □ 专业 2011 级 班级 考试 方式 闭卷 ■ 开卷 □ 本试卷共 四 大题(4页)，满分100分，考试时间120分钟。 请在答题纸上作答，在试卷上作答无效。 一、选择题：（本题共20小题，每题2分，共40分） 1、链式存储的存储结构所占存储空间（ ）。 A． 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B． 只有一部分，存放结点的值 C． 只有一部分，存储表示结点间关系的指针 D． 分两部分，一部分存放结点的值，另一部分存放结点所占单元素 2、已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ ）。 A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m 3、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。 A．P-next==Q-next B．P-next== Q C．Q-next== P D．P==Q 4、下面关于线性表的叙述中，错误的是（ ）关系。 A．顺序表必须占一片地址连续的存储单元 B．顺序表可以随机存取任一元素 C．链表不必占用一片地址连续的存储单元 D．链表可以随机存取任一元素 5、等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ ）。 A．n B．(n-1)/2 C． n/2 D．(n+1)/2 6、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）。 A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 7、下列算法的时间复杂度是（ ）。 for (i=0;in;i++) for (j=0;jn;j++) c[i][j]=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2） 8、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点的值，应执行下列 ( )命令。 A．x=top; top=top-next; B．top=top-next; x=top-data; C．x=top-data; D．x=top-data; top=top-next; 9、经过下列栈的运算后，x的值是（ ）。 InitStack(s) （初始化栈）; Push(s, a); Push(s, b); ReadTop(s); Pop(s, x); A．a B．b C．1 D．0 10、一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( )。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 11、设某棵二叉树中有2000个站点，则该二叉树的最小高度为（ ）。 A、9 B、10 C、11 D、12 12、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A．5和1 B．4和2 C．2和4 D．1和5 13、根据二叉树的定义，具有3个结点的二叉树有（ ）种树型。 A．3 B．4 C．5 D．6 14、如