2010年数据结构期末考试试卷答案

蜗牛在线更多免费学习资料等待您的光临！数据结构期末考试试卷（A）一、选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为(A)A.数据B.数据元素D.数据类型C.数据结构2．栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构3．链栈与顺序栈相比，比较明显的优点是(DA.插入操作更加方便)B.删除操作更加方便D.不会出现上溢的情况C.不会出现下溢的情况4．采用两类不同存储结构的字符串可分别简称为(B)A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA.110C.100B.108D.1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储C.可以链接存储B.数据元素是一个字符D.数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA.2hB.2h-1D.h+1C.2h+1软件开发网8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？AA.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对9．一个有n个顶点的无向图最多有多少边？CA.nB.n(n-1)D.2nC.n(n-1)/210．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA.1/2C.2B.1D.411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点C．右子树的叶子结点B．左子树的分支结点D．右子树的分支结点软件开发网12．对于哈希函数H(key)=key%13,被称为同义词的关键字是(D)A.35和41C.15和44B.23和39D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）原理见课本128页三、有图如下，请写出从顶点；C0-C1-C3-C4-C5-C2：C0-C1-C2-C3-C4-C5c0出发的深度优先及宽度优先遍历的结果。(10分)深度优先宽度优先四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）原理见课本250页五、给定线性表（12，23，45，66，76，88，93，103，166），值12，93，166的过程。并写出二分查找的算法。（20分）012345678试写出在其上进行二分查找关键字12234566768893103166过程：mid=(0+8)/2=4high=3,low=0mid=1high=0,low=0mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8low=8mid=8算法：见课本84页上六、知单链表的结点结构为Datanext下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。(可用文字说明该算法的基本思想及执行的过程，10分)voidSelectSort(LinkedListL){LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL){min=p;q=p->next;while(q!=NULL){if(q=q->next;}(2))min=q;if((3)){rcd=p->data;p->data=min->data;min->data=rcd;}(4);}}本题不会。嘿嘿。。。。七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)输入：四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入2：输出：算法产生至少一个量作为输出3.：确定性：组成算法的每条指令是清晰的，无歧异的。4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的八、何谓队列的"假溢"现象？如何解决？（5分）队列的假溢现象是指数组实现的顺