2009秋-数据结构b-经0806-试卷a卷答案--武守秋、邸书灵

《2009秋-数据结构b-经0806-试卷a卷答案--武守秋、邸书灵》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、石家庄铁道学院2009-2010学年第1学期2008级本科班期末考试试卷（A）答案课程名称：数据结构B任课教师：武守秋、邸书灵考试时间：120分钟学号：姓名：班级：考试性质（学生填写）：正常考试（）缓考（）补考（）重修（）提前修读（）题号一二三四五六七总分满分20204515100得分阅卷人一、单项选择题（每小题2分，共20分）1.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为：（C）。（A)顺序表（B)用头指针表示的单循环链表（C)用尾指针表示的单循环链表（D)单链表2.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）。(A)访问第i个结点（1≤i≤n）和

2、求第i个结点的直接前驱（2≤i≤n）(B)在第i个结点后插入一个新结点（1≤i≤n）(C)删除第i个结点（1≤i≤n）(D)将n个结点从小到大排序3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以4.线性表Ｌ在（B）情况下适用于使用链式结构实现。（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂5.有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：（C）。(A)head->prior==NULL(B)head->n

3、ext==NULL(C)head->next==head(D)head->next->prior==NULL6.以下关于广义表的叙述中，正确的是：（A）。（A)广义表是由0个或多个单元素或子表构成的有限序列（B)广义表至少有一个元素是子表（C)广义表不能递归定义（D)广义表不能为空表7.具有n(n>0)个结点的完全二叉树的深度为（C）。(Ａ)élog2(n)ù(Ｂ)ëlog2(n)û(Ｃ)ëlog2(n)û+1(Ｄ)élog2(n)+1ù第1页共6页8.某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：（C）。（A）3（B

4、）2（C）4（D）59.设一棵完全二叉树具有1000个结点，则此完全二叉树有（A）个叶子结点。（A）500（B）499（C）501（D）49810.在一个无向图中，所有顶点的度数之和等于所有边数的（C）倍。（A）1/2（B）1（C）2（D）4二、填空题（每空2分，共20分）1.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。2.数据项是数据的不可分割的最小单位。3.向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。4.向栈中压入元素的操作是先移动栈顶指针，后存入元素。5.不包含任何字符（长度为0）的

5、串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。6.假设有二维数组A6×8，行列下标从0，0开始。每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A57的第一个字节地址为1282；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072。三、简答题（每小题5分，共40分）1.计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1

6、+2+……+n）=n(n+1)(n+2)/62.下面是出栈的算法，请把填上语句//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//初始分配量#defineSTACKINCREMENT10;//分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈容量}SqStack;StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，第2页共6页//用e返回其值，并返回OK；//否则返回ERRORif(S.top==

7、S.base)returnERROR;e=*--S.top;returnOK;}3.写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);w