数据结构半期试题(4-20)

《数据结构半期试题(4-20)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2004－2005学年度数据结构半期试题答卷说明：1.本试卷共分三大题；2.本试卷共7页，满分100分；3.考试形式为闭卷考试。题目一二三四总分总分人分数得分评卷人一、单项选择题（每小题2分，共40分）1.如果要求字符串的长度不受限制，而且可以在串的任意位置进行插入、删除运算，而不导致元素移动，那么该串应采用【】方式进行存储。   A．线性表B．向量  C．可变长向量D．单链表2.设有一个足够大的栈，入栈元素的顺序为为wxyz,，则栈的不可能输出序列是【】。A．zwyxB．xyzwC．zyxwD．yz

2、xw3.在有n个结点的线性链表L中，删除第 i个结点(1≤i≤n)的算法ListDelete（&L，i，&e）的时间复杂度为【】。A．O（n）B．O(1)C．O()D．O()4.设满二叉树的深度为k，现采用顺序表示法存储该满二叉树，每个结点占L个存储单元，则共需要【】个存储单元。A.k   B.2k×L  C.(2k－1)×L   D.(2k＋1)×L5.树最适合用来表示【】。A．有序数据元素B．无序数据元素C．元素之间呈线性关系的数据D．元素之间具有分支层次关系的数据6.在数据结构中，从逻辑上可以把

3、数据结构分成【】。A．动态结构和静态结构  B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构数据结构半期试题（第6页共6页）1.程序段：for(i=0;i<=n;i++){++x;s+=x;}中，语句++x;的频度为【】。A．nB．n+1C．n+2D．n-12.下列字符串中【】是串"ABCABDEABX"的子串。A．"ABC"B．"BX"C．"AB"D．"AC"3.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是：【】A.acbedB.deca

4、bC.deabcD.cedba得分评卷人4.  串的长度是：【】A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数且字符个数大于0D.串中所含字符的个数得分评卷人一、填空题（每空1分，共15分）1.对于一棵具有n个结点的树，该树中所有结点的度数之和为____.2.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为____个，其中____个用于指向子女结点，___个指针空闲着。3.一维数组的逻辑结构是____,存储结构是____;对于二维或多维数组，分为按___和____两种不同的存

5、储方式 ，，二、简要回答题(每题5分，共10分)1.有一棵三叉树，已知度为1,2,3的结点数分别n1,n2,n3,则该三叉树的叶结点数n0为多少？简单给出推导过程。数据结构半期试题（第6页共6页）第2题. 简述以下算法的功能（栈和队列的元素类型均为int)void algo3(Queue &Q){      Stack S; int d;      InitStack(S);      while(!QueueEmpty(Q)){         DeQueue(Q,d);Push(S,d);    

6、   }      while(!StackEmpty(S)){         Pop(S,d); EnQueue(Q,d);       }__________________学院__________级___________班姓名_______________学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密封线内答题无效 }得分评卷人三、算法应用与阅读题(共35分)　1、一个带头结点的单链表如下：

7、　　　　　　head为头指针，每个结点按data字段值递增顺序链接，r指向一个新结点数据结构半期试题（第6页共6页）下面是将r所指的新结点插入链表中的算法，插入后结点仍按data字段值的递增顺序链接。请在算法的空白处填上正确的成份。（每空2分，共10分）　　TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;　　statusinsert（LinkListhead;ListListr）；　　　　{　Lin

8、klistq,pred；　　　　　　　pred＝＿＿＿＿＿＿＿＿＿＿；　　　　　　　q＝head->next；　　　　　　　while＿＿＿＿＿＿＿＿and（q->data＜＝r->data）　　　　　　　　　{　　　　　　　　　　　pred＝q；　　　　　　　　　　　＿＿＿＿＿＿＿＿＿；　　　　　　　　　}　　　　　　　r->next＝＿＿＿＿＿＿＿＿；　　　　　　　＿＿＿＿＿＿＿＿＿＿；　　　　　}//endofinsert2.阅读如下算法（7分）/