苏州科技学院数据结构试题（A）.docx

苏州科技学院数据结构试题A使用专业计算机04级考试方式：开卷（）闭卷（y）共9页题号合计得分一单项选择题（每小题2分，共24分）1在一棵深度为h且具有n个节点的二叉排序树中，查找一个元素的最大查找长度（即经过比较的结点数）为OA n B l0g2nC h/2DP料2循环队列中数组的下标范围是。到n-1头尾指针分别为front和rear则队列的长度为一。Ar-fBr-f+1C（f-r）%n+1D（r-f+n）%n3在数据结构中，从逻辑上可将数据结构分为oA动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4在一个带表头结点的双向循环链表中，若要在指针p所指向的节点之后插入一个q指针所指向的节点，则需要对q->right赋值为oAp->leftBp->rightCp->right->rightDp->left->left5快速排序方法在情况下最不利于发挥其长处。A要排序的数据量太大B要排序的数据中含有多个相同的值C要排序的数据已基本有序D要排序的数据个数为奇数6在一个非空二叉树的中序序列中，根结点的左边A只有右子树上的所有节点B只有右子树上的部分节点10对于具有e条边的无向图，它的邻接表中含有个边结点。AeB2eCe+2De/211下列关键字序列中，是堆。A16,72,31,23,94,53B94,23,31,72,16,53C16,53,23,94,31,72D16,23,53,31,94,7212在具有n个单元的顺序栈中，假定以地址顶端（即下标为n-1的单元）作为栈底，以top作为栈顶指针，则当作入栈处理时，top变化为oAtop不变Btop=0Ctop-Dtop+二判断题（正确的请在题后的括号中写J,否则请在题后的括号中写X,共8分）1线性表在任何情况下均可以进行二分查找。（）2设哈希表长m:14,哈希函数H（key）:keyMOD11,假设表中已有4个结点15,38,61,84,如果采用线性探测再散列解决冲突，关键字为49的结点的地址为9o（）3如果二叉树中某结点的度为1,则说明该结点只有一棵子树。（）4任何一个二叉树的叶子结点在其先序序列、中序序列和后序序列中的次序是不变的。（）5已知一个有向图的邻接表表示，计算第i个结点的出度必须遍历整个邻接表。（）6如果一个串r中的字符全部包含在另一个串s中则说明r是s的一个子串。（）7对一个堆，无论按二叉树的层次遍历还是先序遍历，都不一定能得到有序序列。（）8无论是链队列还是循环队列，作入队运算操作时都必须判定队列是否满。（）三解答下列各题：（公办学生作1,2,3,5,7,8H41分，民办学生做1,2,4,5,6,9,10H48分）1设有6个元素AjBiCjD1E1F依次入栈，允许任何时候出栈，能否得到下列的每一个出栈序列？加能给出山栉最作的过程容不能僭沐苴理由C/6分,3设一个工程有11项活动，9个事件,事件VI表示整个工程开始,事件V9表示整个工程结束O+s(1)求出每个事件的最早和最晚发生时间？(2)完成整项工程至少需要多少时间？(3)哪些活动是影响工程进度的关键？(10分)5已知一组元素为46,74,16,53,14,26,40,86试写出：(1)将其调整为小顶堆的过程。(2)快速排序一趟的过程和结果。(6分)6说明下列算法的功能。(5分)Voidinsert(Linklist&L,EIemTypexlEIemTypey)s=newLnode;s->data=y;P=L;while(p->next&&p->next.data!=x)p=p->next;s->next=p->next;p->next=s;9试将树转换为相应的二叉树，并写出二叉树后序遍历的结果。（7分）10已知二叉树的前序遍历序列为Dacebhfgi,中序通历序列为DCBEHAGIF试画出该二叉树，并简述由任意二叉树的前序遍历序列和中序遍历序列求二叉树B的思想方法。2编写算法求二叉链表存储的二叉树的深度。（7分）3假设一个有向图含有n个顶点和e条弧，清编写程序实现该图的邻接表存储。（10分）