搜索
试卷A第1页共9页A卷中国石油大学（北京）2010—2011学年第2学期《数据结构》期末考试试卷考试方式（闭卷考试）班级：姓名：学号：题号一二三四五总分得分（试卷不得拆开，所有答案均写在题后相应位置）试卷A第2页共9页一、选择题（本大题共15小题，每题2分，共30分）1、可以用（）定义一个完整的数据结构。A．数据元素B．数据对象C．数据关系D．抽象数据类型2、对于顺序存储结构的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n),O(n)B．O(n),O(1)C．O(1),O(n)D．O(1),O(1)3、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B．队列C．线性表的链式存储结构D．栈4、串“abcaabbcabcaabdab”的next数组为（）A．01112211123456712B．01112121123456112C．01110013101100701D．011122311234567125、将一个A[1．．100，1．．100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。A．198B．197C．195D．1966、若元素1、2、3、4、5、6依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）。A．435261B.324156C.231564D.1654327、广义表A=(a,b,(c,d),(e,(f,g)))，则表达式Head(Tail(head(Tail(Tail(A)))))的值为（）。A．(g)B．(d)C．cD．d8、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。NullacbdNullacbdNullacbdNullacbdNullABCD试卷A第3页共9页9、将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是()。I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A．只有IIB．I和IIC．I和IIID．I、II和III10、已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字1，调整后得到的小根堆是（）。A．1，5，12，8，28，20，15，22，19B．1，5，12，19，20，15，22，8，28C．1，12，5，8，28，20，15，22，19D．1，8，12，5，20，15，22，28，1911、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点保存的关键字分别是（）。A.13，48B.24，48C.24，53D.24，9012、比较次数与排序的初始状态无关的排序方法是（）A．直接插入排序B．起泡排序C．快速排序D．简单选择排序12、下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成14、在下列排序方法中，（）方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。A．快速排序B．起泡排序C．堆排序D．插入排序15、下列叙述中，不符合m阶B树定义要求的是()A．根节点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接2453139037试卷A第4页共9页二、判断题（本大题共10小题，每题1分，共10分）1、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）2、任何一个递归过程都可以转换成非递归过程。（）3、栈和队列都是限制存取点的线性结构。（）4、串是一种数据对象和操作都特殊的线性表。（）5、广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（）6、一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（）7、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）8、在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。（）9、直接选择排序算法在最好情况下的时间复杂度为O（N）。（）10、对一个AOV网，从源点到终点的路径最长的路径称作关键路径。（）三、填空题（本大题共5小题，每空2分，共10分）1、数据结构中评价算法的两个重要指标是时间复杂度和________________________________。2、在单链表p结点之后插入s结点的操作是___________________________________________。3、表达式((12*3-2*3)/4+34*5/7)+108/9+28的后缀表达式是_______________________________。4、对关键字序列(59，78，11，33，21,65，10)进行一趟快速排序之后得到的结果为。（其中以59作为枢纽）5、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是。edacb试卷A第5页共9页四、求解下列问题（本大题共5小题，共42分）1、已知广义表A=（（（a）），（b），（a，（c）），（（（d，e））））。（5分）（1）画出其一种存储结构图；（2）用求头部、尾部的方式求出e。试卷A第6页共9页2、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABCDFGJEHKLIM中序遍历序列：BAFDJGCKHLEIM。（7分）（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。3、将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组散列函数：H(key)=(key×3)MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。（10分）问题：（1）请画出所构造的散列表；（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。试卷A第7页共9页4、请利用Dijkstra算法求图1中从顶点1到其他个顶点间的最短路径。（10分）（注：写出执行算法过程中各步的状态）图1187654323262201578106101531663试卷A第8页共9页5、如图2所示的AOE网，计算每个活动（弧）的最早开始时间e和最迟开始时间l，每个事件（顶点）的最早开始时间Ve和最迟开始时间Vl，并给出关键路径。(10分)ABECDFG124225313563图2试卷A第9页共9页五、程序题（本大题共1小题，共8分）1、已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想（2）描述算法的详细实现步骤（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C语言实现），关键之处请给出简要注释。