2010湖南城市学院数据结构试卷b.doc

班级学号_ 姓名_ （第 页， 共 页）-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-密-封-线-湖 南 城 市 学 院20092010学年 第1期数据结构试卷 B 卷 时间： 120 分钟 年级专业班级：0906601-02-03 【考试】 【闭卷】题型一二三四五六七八九十总分分数1020302416得分评卷人： 合分人： 核查人：一、判断题（共10分，每小题1分）1. 用非递归方法实现递归算法时一定要使用递归工作栈。 （错 ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （ 错 ）3. 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。 （对 ）4. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。 （对 ）5. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。 （错 ）6. 栈和队列是一种非线性数据结构。 （错 ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （对）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （对）9. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。 （错 ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是21345。 （错 ）二、填空题（共20分，每空2分）1、线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。2、在无权图G的邻接矩阵A中，若(vi,vj)或vi,vj属于图G的边集合，则对应元素Aij等于_，否则等于_3、数据结构包括_逻辑结构_、_存储结构_和数据的运算三个方面。4、在顺序表中插入或删除一个元素，需要平均移动 （n+1）/2 表中一半 元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。5、数据是_信息_的载体，它能够被计算机程序识别、存储和加工处理。三、选择题（共30分，每小题2分）1、一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ b ）。A. 110 B. 108 C. 100 D. 1202、某线性表最常用的运算是存取任意指定序号的结点值和在最后进行插入删除，则采用（ a ）最节省运算时间 A、顺序表 B、双链表 C、带头结点的双循环链表 D、循环单链表3、给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ c ）。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)4、如果某个线性表最常用的运算是存取第i个元素和它的前驱的值，则采用（ b ）存储方式最节省运算时间。 A、单链表 B、顺序表 C、单循环链表 D、双链表5、数组a56的元素占5个单元，将它按照行优先存储在始址为2000的连续单元中，（ d ） A、则元素a44的首地址为2125 B、则元素a44的首地址为2110C、则元素a44的首地址为2145 D、则元素a44的首地址为21406、一个有n个顶点的无向图最多有_a_条边。A、 n B、 n(n-1) C、 n(n-1)/2 D、 2n7、任何一个无向连通图的最小生成树 b 。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在8、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（ c ）A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构9、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ c ） A、i B、n=i C、n-i+1 D、不确定10、判定一个栈ST（最多元素为m0）为空的条件是（b ） A、ST-top0 B、ST-top=0 C、ST-topm0 D、ST-top=m011、散列表的平均查找长度（ c ）A、与处理冲突方法有关而与表的长度无关B、与处理冲突方法无关而与表的长度有关C、与处理冲突方法有关而与表的长度有关D、与处理冲突方法无关而与表的长度无关12、算法的时间复杂度是指（ c ） A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数13、在数据结构中，从逻辑上可以把数据结构分成（ b ） A、动态结构和静态结构 B、线性结构和非线性结构 C、集合结构和非集合结构 D、树状结构和图状结构14、算法的有穷性是指（ a ）A、算法程序的运行时间是有限的 B、算法程序所处理的数据量是有限的C、算法程序的长度是有限的 D、算法只能被有限的用户使用15、输出一个二维数组bmn中所有元素值的时间复杂度为（ d ）。 A、O(n) B、O(m+n) C、O(n2) D、O(m*n)iaedbchHf图1 一棵二叉树i四、简答题（共24分，每小题8分）1、由如图1所示的二叉树，回答以下问题：（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树的后序线索二叉树；（3）画出该二叉树对应的森林。答：. 中序线索二叉树如图1（左）所示；后序线索二叉树如图1（右）所示；该二叉树转换后的的森林如图1所示。图1a 11dhjbkc 图 1 对应的森林iefbadce1115131412fbadcef161115151516131412212、请用克鲁斯卡尔和普里姆两种算法分别为图构造最小生成树： 答：3、已知待排序文件各记录的排序码顺序如下7273712394160568 请列出快速排序过程中每一趟的排序结果。答：各趟结果如下： 6805712316729473 160523 68 71729473 2分 05 16 23 68 71729473 2分0516 23 68 71729473 2分0516236871 729473 0516236871 7273 94 0516236871 72 7394 2分五、综合题（共16分，每小题8分）1、指定Hash函数H(k)=3*k mod 11及线性探测开地址法处理冲突，试在010的散列空间中对关键字序列（22，41，53，46，30，13，01，67）构造Hash表，并求在等查找概率下查找成功的平均查找长度。解：插入元素后的分布情况：4分0123456789102241300153461367ASL = (1+1+1+1+2+2+2+6)/8=2.0 4分2、设双链表结点结构为 llink data rlink，请设计算法将其中P所指结点与其rlink所指结点位置互换的算法。解：解：3分typedef struct DLNode ElemType data; struct DLNode *llink,*rlink;DLNode,*DLinkList;/思想：将P-rlink先从链表中删除掉，然后再插入到P前 3分Status SwapANode(DLNode *&P) /结点存在吗? if(!P | !(P-rlink)return ERROR; q = P-rlink; /删除q结点 if(!q-rlink) P-rlink = NULL; else P-rlink = q-rlink; q-rlink-