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

考 生 信 息 栏系 专业 级 班级 姓名学号装 订 线厦门理工学院试卷2012－2013学年 第 一 学期课程名称数据结构与算法试卷卷别□A■B□专业 2011 级 班级考试方式闭卷 ■开卷 □本试卷共 四 大题(4页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。一、选择题：（本题共20小题，每题2分，共40分）1、链式存储的存储结构所占存储空间（）。A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素2、已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。A．B+(i-1)*mB．B+i*m C．B-i*m D．B+(i+1)*m3、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。A．P-next==Q-next B．P-next== Q C．Q-next== P D．P==Q4、下面关于线性表的叙述中，错误的是（）关系。A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素5、等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ ）。A．nB．(n-1)/2 C． n/2 D．(n+1)/26、设数组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)%m7、下列算法的时间复杂度是（）。 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．aB．bC．1D．010、一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( )。A．EDCBA B．DECBA C．DCEAB D．ABCDE11、设某棵二叉树中有2000个站点，则该二叉树的最小高度为（ ）。 A、9 B、10 C、11 D、1212、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。A．5和1B．4和2 C．2和4 D．1和513、根据二叉树的定义，具有3个结点的二叉树有（）种树型。 A．3 B．4 C．5 D．614、如右图所示的二叉树，后序遍历的序列是（） A． A、B、C、D、E、F、G 、H、IB． A、B、D、H、I、E、C、F、GC． H、D、I、B、E、A、F、C、GD． H、I、D、E、B、F、G、C、A15、下列陈述正确的是（）。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，且有左右子树之分16、在有n个叶子结点的哈夫曼树中，非叶子结点的总数是（）。Ａ．n-1Ｂ．nＣ．2n-1Ｄ．2n17、对于一个具有n个顶点的有向图的边数最多有（ ）。 A．nB．n(n-1) C．n(n-1)/2D．2n18、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ ）。 A．n-1B．n+1 C．n D．n+e19、下面关于图的存储结构的叙述中正确的是（