资源描述：
《11-12-数据结构试卷-a+答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2011～2012学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名：卷面总分：100分考试时长：100分钟考试类别：闭卷院（系）：专业：年级：2010姓名：学号：题号第一题第二题第三题第四题总分得分阅卷教师（签字）：装订线一、单项选择题（每题2分，共10题20分）题号12345678910答案ABBBBDDCCA1．以下那一个术语与数据的存储结构无关？。A．栈B．哈希表C．线索树D．双向链表2．链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存
2、储空间D．所需空间与线性表长度成正比3．算术表达式a+b*（c+d/e）转为后缀表达式后为。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为。A．232B．234C．390D．3921．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是B。A．9B．11C．15D．不确定2．一棵二叉树中序序列为
3、FEABDC，后序序列为FBADCE，则层序序列为D。A.ABCDEFB.EFCDBAC.FECDABD.EFCDABECFDAB3．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是D。A．G中有弧B．G中有一条从Vi到Vj的路径C．G中没有弧D．G中有一条从Vj到Vi的路径4．对于二叉排序树，下面的说法C是正确的。A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合(不用移动元素的树)B．对二叉排序树进行层序遍历可得
4、到有序序列（应该是中序遍历）C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2（取决于二叉排序树的形状）5．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是。A.30,42,47,55,75,90B.42,30,47,75,55,90C.42,30,47,55,75,90D.42,30,47,90,55,756．下述文件中适合于磁带存储的
5、是。A.顺序文件B.索引文件C.散列文件D.多关键字文件顺序文件：原理是顺序表查找法索引文件：原理是线性索引查找(如最大关键码和次关键码)多关键字文件：散列文件：原理是散列函数（哈希函数）一、判断（每题1分，共10题10分）题号12345678910答案×√√××√×√×√1．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。----()（如果插入和删除次数较少时顺序存储方式为首选）2．KMP算法的特点是在模式匹配时指示主串的指针不会变小。------------()（主串在匹配过程中
6、是不会移动的，只有匹配的串在移动，所以其指针不会动）3．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.---()4．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。---------------------------------------------------------()数组不能进行插入删除等操作5．若一个广义表的表头为空表，则此广义表亦为空表。-------------------()6．完全二叉树中，若一个结点没有
7、左孩子，则它必是树叶。---------------()完全二叉树的关键之一就是：元素又是有序排列的，顺序不可间断7．一个有向图的邻接表和逆邻接表中结点的个数可能不等。---------------()必须相等8．AOE网一定是有向无环图。-----------------------------------------()AOE网的特征和定义9．对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。---()应该是中序排列10．倒排文件与多重表文件的次关键字索引结构是不同的。-----
8、--------()二、填空题（每题2分，共10题20分）1．带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L。下一个元素的后继恒为自身1．已知链队列的头尾指针分别是f和r，则将s指向的结点入队的操作是r->next=s；r=s。将插入元素赋值给原队尾指针的后继2．广义表A(((),(a,(b),c)))，head(tail(head(tail(head(A))))等于(b)。HeadA=((),(a,(b),c))tail(head(A))=(a,(b),c)
