资源描述：
《数据结构模拟试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、若某线性表中最常用的操作是在最后一个元素之前插入和删除元素，则采用_C__最节省运算时间。A、单链表B、仅有头指针的单循环链表C、仅有尾指针的单循环链表D、双链表2、哈夫曼树的带权路径长度WPL等于___C___。A、除根以外的所有结点的权植之和B、所有结点权值之和C、各叶子结点的带权路径长度之和D、根结点的值3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___C_____。A．1,2,3,4,5B．1,4,3,2,5C．4,1,3,2,5D．1,3,2,5,44、对于下面二叉树，按后序遍历所得的结点序列
2、为____D____。A．1234567B．1245367C．4251637D．45267315、栈和队列都是___C____。A．顺序存储的线性结构B．链式存储的线性结构C．操作受限制的线性结构D．操作受限制的非线性结构6、已知完全二叉树有30个结点，则整个二叉树有__B____个度为1的结点。A．0B．1C．2D．不确定7、若长度为n的线性表采用顺序存储结构，将其第i个位置的元素删除算法的时间复杂度为AA．B．C．O(logn)D．8、设有二维数组A(1..12，1..10)，其每个元素占4个字节，数据按列优先顺序存储，第一个
3、元素的存储地址为100。则元素A(5，5)的存储地址为D。A．176B．276C．208D．3089、算法分析的两个主要方面是A。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性10、设栈的输入序列是（1、2、3、4），则D不可能是其出栈序列。A．1243B．2134C．1432D．431211、在单链表中，指针p指向链表某结点，现将指针s所指结点插到p所指结点之后，则其实现语句应为DA．s->next=p+1;p->next=s;B．p->next=s;s->next=p->next;C．
4、s→next=p→next;p→next=s→next;D．s→next=p→next;p→next=s;12、栈和队列的共同点是C。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点13、假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是A。A．front+1==rearB．front==rear+1C．front==0D．front==rear14、若串S=’AND’，其子串的数目是C。A．3B．6C．7D．8二、填空题1、数据的存储结构主要包括顺序和链式两种基本结
5、构。2、表达式求值是棧应用的一个典型例子。3、在有n（n>0）个结点的二叉链表中，非空链域的个数为____n-1_______。4、下面程序段的时间复杂度是O(n^2)。for(j=0;j＜n;j++)for(i=0;i＜n;i++)p*=2;6、单链表表示法的基本思想是用指针或地址表示结点间的逻辑关系。7、在下列树中，结点G的子孙结点有⑧。8、深度为6（根的层次号为1）的完全二叉树至多有______2^6-1_____个结点。至少2^4-11.线性表采用链表存储时，结点内部的存储空间一定是连续的。(F)2．队列只能采用链式存储方
6、式。(F)3.消除递归必须使用栈。（F）4．由二叉树的先序序列和中序序列能唯一确定一棵二叉树。（T）5．存在有偶数个结点的满二叉树。（F）6．将一个森林转换成二叉树后，根结点一定没有左子树。（F）1、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE。要求：（1）构造此二叉树；（2）写出二叉树的后序遍历序列；EACBDGF（3）画出把此二叉树还原成森林的图示；（4）画出对二叉树的中序线索化。2、有一份电文中共使用六个字符：A、B、C、D、E、F，它们的出现频数依次为4、7、17、16、19、27，试画出对应的Huff
7、man树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的Huffman编码。1、写出链队列的入队、出队的算法。入队算法linklistin_queue(linklistrear,datatypex){s=newlnode;s->data=x;s->next=rear->next;rear->next=s;rear=s;return(rear);}出队算法linklistout_queue(linklistrear,datatype*x){if(rear->next==rear)return(NULL);
8、q=rear->next->next;if(q==rear){rear=rear->next;rear->next=rear;}else{rear->next->next=q->next;}*x=q->data;deleteq;return(rea
