《数据结构》2010期考试卷(A)1.doc

教务处填写：XXXX学院（全日制）课程考试试卷（A） 2010 2011 学年度上 学期 系别：信科系 班级名称 09A 网络 课程名称：数据结构 . 考试时间： 120 分钟 闭 卷题 号一二三四五六七八九十总分应得分303040100实得分评卷人 第1页（共 页） 20 年 月 日考试用专业：学号：姓名：装订线（答题不得超过此线）一、选择题:（本大题共10小题,每题3分，共30分） 1. 树最适合用来表示( )。A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据2. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A.5 B.6 C.7 D.83. 对n个记录的文件进行快速排序，需要的辅助存储空间大致为（） A. O（1）B. O（n） C. O（1og2n） D. O（n2）4.算法的计算量的大小称为计算的（ ）A效率 B. 复杂性 C. 现实性 D.难度5. 二叉树的第k层的结点数最多为( D ). A2k-1 B.2K+1 C.2K-1 D. 2k-16以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树7 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点8. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( ) A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，39. 计算机的算法是指（）A.计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法10. 以下那个术语与数据的存储结构无关？（ ）A.栈 B.哈希表 C.线索表 D.双向链表二、填空题（每空1分，共30分） 1数据的逻辑结构分为 、 、 、 四种。2.函数重载要求 、 或 有所不同。3在带附加表头的循环双向链表中，表头附加结点 的 指针域指向最后一个结点，最后一个结点的 指针域指向 结点。4在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。5在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 、 。6在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点，并将被删除的结点的下标赋给i的时候，所进行的操作（需要用一个临时变量p）应描述为 和 。7在稀疏矩阵的十字链接存储中，每个结点的down指针域指向 相同的下一个结点，right指针域指向 相同的下一个结点。8一个广义表中的元素分为 元素和 元素两类。9广义表A=(a,(b,(),c),(d),e)的长度为 ，深度为 。10向一个顺序栈插入一个元素时，首先应 ，然后再将待插入元素 放入栈顶位置 。11对于队列，应在 进行插入，在 进行删除。 12中缀表达式2+7/(4-1)所对应的后缀表达式为 。 13后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 。14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g),则e结点的双亲结点为 ，孩子结点为 ，树的深度为 。三、算法阅读题（本大题共2小题，每小题20分，共40分）1下列算法的功能是比较两个链串的大小，其返回值为： comstr(s1,s2)= 请在空白处填入适当的内容。int comstr(LinkString s1,LinkString s2) /s1和s2为两个链串的头指针 while(s1&s2)if(s1datedate)return1；if(s1dates2date)return1； if( )return1； if( )return1； ； 答：2. 阅读下面的算法 LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next)q=L；L=Lnext；p=L；S1： while(pnext) p=pnext；S2： pnext=q；qnext=NULL； ret