苏州科技数据结构早期的样卷

1、苏州科技学院数据结构试题A使用专业计算机04级 考试方式：开卷()闭卷(y)共包页名姓一线题号111111I111合计得分号-学一-班封业专一一密系一-一 单项选择题(每小题2分，共24分)1在一棵深度为h且具有n个节点的二叉排序树中，查找一个元素的最大查找长度(即经过比较的结点数)为。A n B log2nC h/2 D h2循环队列中数组的下标范围是0到n-1 ,头尾指针分别为front和rear ,则队列的长度为OA r-f B r-f+1 C (f-r)% n+1 D (r-f+n) %n3在数据结构中，从逻辑上可将数据结构分为 。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和

2、非线性结构D内部结构和外部结构4在一个带表头结点的双向循环链表中，若要在指针p所指向的节点之后插入一个q指针所指向的节点，则需要对 q->right赋值为。A p->left B p->right C p->right->right D p->left->left5快速排序方法在 情况下最不利于发挥其长处。A要排序的数据量太大B要排序的数据中含有多个相同的值C要排序的数据已基本有序D要排序的数据个数为奇数6在一个非空二叉树的中序序列中，根结点的左边。A只有右子树上的所有节点B只有右子树上的部分节点C只有左子树上的所有节点D只有左子树上的部分节点7若在中

3、序线索二叉树中某一个结点存在右孩子，则该结点的后继是 。A 不存在B其右子树中最左侧的结点C其左子树中最右侧的结点D其右孩子8以下关于图的叙述中，正确的是 。A用邻接矩阵存储图，占用的存储空间数只与图中结点的个数有关，而与边数无关B用邻接矩阵存储图，占用的存储空间数只与图中边数有关，而与结点的个数无关C用邻接表法存储图，占用的存储空间数只与图中结点的个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点的个数无关9将一个n行n列的对称矩阵采用下三角压缩存储方法存储在下标为0.k的一维数组b中，则k的值最少为。A n B 2n C n(n+1)/2 D n(n+1)

4、/2-1第 1 页10对于具有e条边的无向图，它的邻接表中含有 个边结点。A e B 2e C e+2 D e/211下列关键字序列中， 是堆。A 16, 72, 31,23, 94, 53B 94, 23, 31,72, 16, 53C 16, 53, 23, 94, 31,72D 16, 23, 53, 31,94, 7212在具有n个单元的顺序栈中，假定以地址顶端（即下标为 n-1的单元）作为栈底，以top作为栈 顶指针，则当作入栈处理时，top变化为。A top 不变 B top=0 C top- D top+二判断题（正确的请在题后的括号中写，否则请在题后的括号中写X,共 8分）1线

5、性表在任何情况下均可以进行二分查找。（）2设哈希表长 m=14哈希函数 H（key尸key MOD 11，假设表中已有 4个结点15, 38, 61, 84,如 果采用线性探测再散列解决冲突，关键字为49的结点的地址为9。（）3如果二叉树中某结点的度为1,则说明该结点只有一棵子树。（）4任何一个二叉树的叶子结点在其先序序列、中序序列和后序序列中的次序是不变的。（）5已知一个有向图的邻接表表示，计算第 i个结点的出度必须遍历整个邻接表。（）6如果一个串r中的字符全部包含在另一个串s中则说明r是s的一个子串。（）7对一个堆，无论按二叉树的层次遍历还是先序遍历，都不一定能得到有序序列。（）8无论是链

6、队列还是循环队列，作入队运算操作时都必须判定队列是否满。（）三解答下列各题：（公办学生作1,2,3, 5,7,8 题41分，民办学生做1,2,4,5,6,9,10 题48分）1设有6个元素A,B,C,D,E,F依次入栈，允许任何时候出栈，能否得到下列的每一个出栈序列？如能，给出出栈操作的过程，若不能，简述其理由。（6分）（1） CDBEFA （2） ABEDFC （3） DCEABF2对长度为10的顺序存储的线性表， 此表应满足什么条件才能进行折半查找？画出进行折半查找的判定树，并求其在等概率的条件下查找成功时的平均查找长度。（7分）第7页3设一个工程有11项活动，9个事件，事件V1表示整个工

7、程开始，事件V9表示整个工程结束。（1）求出每个事件的最早和最晚发生时间？ （2）完成整项工程至少需要多少时间？ 哪些活动是影响工程进度的关键？ （10分）4写出下图的邻接矩阵，并分别写出对下图从顶点B始进行深度优先和广度优先遍历的一个结果，并画出其对应的深度优先和广度优先生成树。（10分）5 已知一组元素为46, 74, 16, 53, 14, 26, 40, 86试写出:(1)将其调整为小顶堆的过程。(2)快速排序一趟的过程和结果。(6分)6说明下列算法的功能。(5分)Void insert(Linklist &L,ElemType x, ElemType y) s=new Lno

8、de;s->data=y;P=L;while(p->next&&p->next.data!=x)p=p->next; s->next=p->next; p->next=s;7说明下列算法的功能。(5分)Status A (Linklist L ) / L不含表头结点 if(L&&L->next )Q=L;L=L->next;p=L;While(p->next) p=p->next;P->next=q; q->next=NULL;(7分)8试将树转换为相应的二叉树，再画出其对应的中序线索二叉树。（7分）9试将树转换为相应的二叉树，并写出二叉树后序遍历的结果。DCBEHAG底画出该二叉树,B的思想方法。10已知二叉树的前序遍历序列为DACEBHFG中序遍历序列为并简述由任意二叉树的前序遍历序列和中序遍历序列求二叉树四 算法设计（公办学生做1,2,3题27分，民办学生做1,3题，20分）1假设以带头