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

《《数据结构测验试卷》doc版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空题（请在每题的空格处填上正确的答案，每小题2分，共20分。）1.为了实现随机访问，线性结构应该采用存储。2.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免现象。3.给定一个二叉树的前序遍历序列和，则可以唯一确定一棵二叉树的结构。4.3个结点可以构成种不同形状的树，可以构成种不同形状的二叉树。5.已知链栈的结点结构如右图所示，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为_______________和_______________。datanext6.数据结构中评价算法的两个重要指标是__________________

2、_______。7.列优先顺序表中的第13个元素，是10阶三对角矩阵中的第行第列元素。8.带头结点的双循环链表L为空表的条件是：________。9.若一棵满三叉树中含有121个结点，则该树的深度为_________。10.若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为_____________。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。）1.以下那一个术语与数据的存储结构无关？（）A．栈B.哈希表C.线索树D.双向链表2．算法分析的目的

3、是（①），算法分析的两个主要方面是（②）。 ①A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性3．判定一个循环队列QU（最多元素为m）为满队列的条件是（）。A．QU.front==(QU.rear+1)%mB．QU.front!=(QU.rear+1)%mC．QU.front==QU.rearD．QU.front!=QU.rear+14．不带头结点的单链表head为空的判定条件是（）。A．head==NULLB．he

4、ad->next=NULLC．head->next=headD．head!=NULL5．在一个双链表中，在*p结点之后插入一个结点*s的操作顺序是（）。A．p->next=s;s->prior=p;s->next=p->next;p->next->prior=s;B．s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;C．s->prior=p;p->next=s;p->next->prior=s;s->next=p->next;D．p->next->prior=s;s->next=p->next;s->prior=p

5、;p->next=s;6.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用(【第4页共4页】)遍历方法最合适。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数组为（）。A．012345678999B．01212111

6、1212C．011234223456D．0123123223459.将一个递归算法改为对应的非递归算法时，通常需要使用（）。A.栈B.队列C.循环队列D.优先队列10.下列函数中，渐进时间最小的是（）。A.T1(n)=nlog2n+100log2nB.T2(n)=n3-100log2nC.T3(n)=n2-100log2nD.T4(n)=4log2n-100log2n11.在数据压缩编码的应用中，哈夫曼（Huffman）算法可以用来构造具有（①）的二叉树，这是一种采用了（②）策略的算法。①A.前缀码B.最优前缀码C.后缀码D.最优后缀码②A.贪心B.分治C.递推D.回溯1

7、2.一个具有767个结点的完全二叉树，其叶子结点个数为（）。A.383B.384C.385D.386三、简答题（每小题10分，共20分。）1.对于给定的数组a[n][2n-1]，我们将三个顶点分别为a[0][n-1],a[n-1][0],a[n-1][2n-2]的三角形上的所有元素按行序依次存放在一维数组b[n*n]中。例如，当n=3时，数组a[3][5]中用线连成的三角形如下所示：a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24若把三角形上的所有元素按行序优先依次存放在一维数组b[3