《数据结构测验试卷》doc版.doc

一、填空题（请在每题的空格处填上正确的答案，每小题2分，共20分。）1.为了实现随机访问，线性结构应该采用 存储。2.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免 现象。3.给定一个二叉树的前序遍历序列和 ，则可以唯一确定一棵二叉树的结构。4.3个结点可以构成 种不同形状的树，可以构成 种不同形状的二叉树。5.已知链栈的结点结构如右图所示，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为_和_。datanext6.数据结构中评价算法的两个重要指标是_。7.列优先顺序表中的第13个元素，是10阶三对角矩阵中的第 行第 列元素。8.带头结点的双循环链表L为空表的条件是：_。9.若一棵满三叉树中含有121个结点，则该树的深度为_。10.若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为_。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。）1. 以下那一个术语与数据的存储结构无关？（ ）A栈 B. 哈希表 C. 线索树 D. 双向链表2算法分析的目的是（ ），算法分析的两个主要方面是（ ）。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性3判定一个循环队列QU（最多元素为m）为满队列的条件是（ ）。AQU.front=(QU.rear+1)%mBQU.front!=(QU.rear+1)%mCQU.front=QU.rearDQU.front!=QU.rear+14不带头结点的单链表head为空的判定条件是（ ）。Ahead=NULL Bhead-next=NULLChead-next=head Dhead!=NULL5在一个双链表中，在*p结点之后插入一个结点*s的操作顺序是（ ）。Ap-next=s; s-prior=p; s-next=p-next; p-next-prior=s;Bs-next=p-next; p-next-prior=s; p-next=s; s-prior=p;Cs-prior=p; p-next=s; p-next-prior=s; s-next=p-next;Dp-next-prior=s; s-next=p-next; s-prior=p; p-next=s;6.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次7.已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）8.串ababaaababaa的next数组为（ ）。A012345678999 B012121111212 C011234223456 D0123123223459.将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。A.栈 B.队列 C.循环队列 D.优先队列10.下列函数中，渐进时间最小的是（ ）。 A. T1(n)=nlog2n+100log2n B. T2(n)=n3-100log2nC. T3(n)=n2-100log2n D. T4(n)=4log2n-100log2n11.在数据压缩编码的应用中，哈夫曼（Huffman）算法可以用来构造具有（ ）的二叉树，这是一种采用了（ ）策略的算法。A. 前缀码 B. 最优前缀码 C. 后缀码 D. 最优后缀码A. 贪心 B. 分治 C. 递推 D. 回溯12.一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。A.383 B.384 C.385 D.386三、简答题（每小题10分，共20分。）1.对于给定的数组an2n-1，我们将三个顶点分别为a0n-1,an-10,an-12n-2的三角形上的所有元素按行序依次存放在一维数组bn*n中。例如，当n=3时，数组a35中用线连成的三角形如下所示：a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24若把三角形上的所有元素按行序优先依次存放在一维数组b3*3上，则有：i012345678bia02a11a12a13a20a21a22a23a24如果把位于三角形上的元素aij存放于bk中，那么请给出求得下标值k的计算公式k=f(n,i,j)。对于上例中的a21，根据计算公式可求得k=5。2对于表达式(a-b+c)*d/(e+f)，(1)画出它的中序二叉树，并标出该二叉树的前序线索；(2)给出它的前缀表达式和后缀表达式。四、程序阅读题（在空白处填上适当内容，使其完成正确的功能。每小空2分，共20分。）1.下面的函数void ftoa(double f, char s)将浮点数f转换成相应的字符串，并存放在s中，该函数最多只能转换小数点后四位，如123.45将转换成“123.45”,-123.456789将转换成123.4567。void ftoa(double f, char s) int i,j,len,c,n; double sign=f;if(f0) f=-f;n=(int)f; i=0;dosi+=n%10+48;while(n=n/10);if(sign0) ;len=i;for(i=0,j=len-1; ;i+,j-)c=si; ;sj=c;f - =(int)f; slen+=.;for(i=0;i4;i+)f*=10;slen+= ;while(slen-1=0) ;slen=0;2设T是一棵具有n个结点的二叉树，若给定二叉树T的先序序列和中序序列，并假设T的先序序列和中序序列分别放在数组PreOrder1.n和InOrder1.n中，下面是构造二叉树T的链式存储结构的算法。分析：根据先序遍历的规律可知，PreOrder1为根结点，设中序序列中InOrderi=PreOrder1,则在InOrderi的左面的InOrder1.i-1应为二叉树的左子树，则InOrderi+1.n为根的右子树。相对应的，在先序序列中根的左子树应为PreOrder2.i，而右子树为PreOrderi+1.n。而左子树的根为PreOrder2,右子树的根为PreOrderi+1。依次类推，用同样的方法确定子树的左右子树，从而逐步确定整个二叉树。typedef struct nodeTelemType data; ;BiNode, *BiTree;void create(BiTree t, TelemType PreOrder,int i1,int j1,TelemType InOrder,int i2, int j2) /* 开始时，i1=1,j1=n,i2=1,j2=n */int i=i2;if(i1data=PreOrderi1;t-lchild=NULL;t-rchild=NULL;while(InOrderi!= ;) i+;create(t-lchild,PreOrder,i1+1,i-i2+i1,InOrder, );create(t-rchild,PreOrder, ,InOrder,i+1,j2);else t=NULL;五、算法设计题（每小题16分，共16分。）请从下面的两题中，任意选做一题。若两题均做，则题号小的记入成绩。1.设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）。（1）确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列20，20，17，16，15，15，11，10，8，7，7，5，4中比10大的数有5个）。（2）将单链表中比正整数x小的偶数从单链表中删除。2.以二叉链表为存储结构，写一个算法按广义表形式ke