数据结构2009_2_期中

《数据结构2009_2_期中》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、宁波大学科学技术学院2008/2009学年第2学期期中考试试卷课程名称：報倨转构鸟專佐考试性质考试试卷编号（1）姓名:学号：班级一、选择（2分X25）1.评价一个算法时间性能的主要标准是（D）。A.算法易于调试B.算法易于理解C.算法稳定性和正确性D.算法的时间复杂度2.以卜•关于链式存储的线性表的说法不正确的是（C）oA.结点除白身信息外还包括指针域，因此存储密度小于顺序存储结构。B.逻辑上相邻的结点物理上不必邻接。C.nJ以通过计算直接确定笫i个结点的存储位置。D.插入删除运算操作较方便，不必移动结点。3.从一个长度为n的顺序表中删除第i个元素（lWiWn）吋，需要向前移动（A）个元素。

2、A.n・iB.n-i+lC.D.i4.线性表采用链式存储时，结点的存储地址（B）。A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续5.在一个单链表中，若指针p所指结点不是最后结点，则删除指针p所指结点的后继结点的正确操作是（C）。A.p=p->nextB.p->next=p->nextC.p・>next=p->next->nextD・p・>next=p6.若一个栈的输入序列是1,2,3……n,则输出序列的第一个元素是n,则笫i个输出元素是（C）oA.n・iB.iC・n-i+lD.n・i・l7•顺序栈中元素的个数等于（B）oA.S.top-S.baseB.S.ba

3、se-S.topC.（S.top-S.base+l+stacksize）%stacksizeD.S.top-S.base+l8.设计一个判别表达式屮左，右括号是否配对出现的算法，采用（C）数据结构最佳。A.线性表的链式存储结构B.线性表的顺序存储结构C.栈D.队列9.设有k个空间供一个栈和队列使用，设可用空间为[1……k],初始条件为top=0；rear=front=k+l；则栈空间满的条件是（C）。A.rear==top==kB.top+rear==kC.top+(front-rear)==kD.top+(rear-front)==k+l8.以下哪一个不是队列的基本操作（B）。A.为队尾插

4、入一个新元素C.判断一个队列是否为空B.从队列屮删除第i个元素D.读取队头元素的值B）的存储结构。B.顺序存取D.散列存取p・>next=s;s・>next=p;s->next=p;s->next=q;14.-个二叉树的前序遍历序列为ABCDEFG,它的屮序遍历序列可能是（AA.ABCDEFGB.CABDEFGC.EABCDFGD.DACEFBG15.栈的操作中（D）保持不变。A.栈的顶C.栈指针B.栈中的数D.栈的底16.若进栈序列为1,2,3,4,5,6,且进栈和岀栈可以穿插进行，则不可能出现的出栈序列是（D）0A.2,4,3,1,5,6B.3,2,4,1,6,5C・4,3,2,1,5,

5、6D・2,3,5,1,6,49.线形表的链式存储是一种（A.随机存取C.索引存取10.下列有关线性表的叙述中，不止确的是（C）。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表屮包含的数据元素个数是有限的C.线性表中的每个结点都有且只有一个直接前驱和直接后继D.存在这样的线性表：表中各结点都没冇直接前驱和直接后继11.在单链表中，已知指针p所指结点是指针q所指结点的前驱结点，若在p和q之间插入s结点则执行（AD）。A.s・>next=p->next;B.p・>next=s->next;C.q・>next=s->next;D.p->next=s;17.链队列实际上是一个同时带有

6、头指针和尾指针的单链表，尾指针指向该单链表的（A）。A.最示一个结点B.第一个结点C.倒数第二个结点D.第二个结点18.引起循环队列队队头位置发牛变化的操作是（B）oA.出队B.入队19.一棵三叉树的结点数为50,则它的最小高度为（C）oA.3B.4C.5D.617.在-个具有n个结点的有序单链表中插入一个新结点并使单链表仍然有序的时间复杂度是（B）。A.0（1）B.O（n）C.O（n2）D.O（nlog2n）18.一棵完全二叉树按层次遍历（从上到下从左到右）的序列为ABCDEFGHIJK,则在后序遍历序列中结点I的直接后继是结点（C）A.BB.CC.DD.H19.定义线索二叉树的结点类型应

7、有（D）个域。A.1B.3C.4D.520.已知二叉树有n个叶子结点，则该二叉树的总结点数至少应有（3）个？A.2nB.2n+lC.2n-lD.不确定21.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为（b）A.24B.71C.48D.5322.设数组a[l-10,5-15]的元素以行为主序存放，每个元素占用4个存储单元,则数组元素a[izj]（l>i>10,5MjN15）的地