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

1、 系 专业 班 学号 姓名 密封线苏州科技学院数据结构 试题 A使用专业 计算机04级 考试方式：开卷（ ）闭卷（y） 共 6 页题号合计得分一 单项选择题（每小题2分，共24分）1在一棵深度为h且具有n个节点的二叉排序树中，查找一个元素的最大查找长度（即经过比较的结点数）为_。 A n B log2n C h/2 D h 2循环队列中数组的下标范围是0到n-1，头尾指针分别为front和rear，则队列的长度为_。 A 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 只有左子树上的所有

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

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

5、在题后的括号中写，否则请在题后的括号中写×，共8分）1 线性表在任何情况下均可以进行二分查找。( )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

6、对一个堆，无论按二叉树的层次遍历还是先序遍历，都不一定能得到有序序列。（ ）8 无论是链队列还是循环队列，作入队运算操作时都必须判定队列是否满。（ ）三 解答下列各题：(公办学生作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) DCEABF 2 对长度为10 的顺序存储的线性表，此表应满足什么条件才能进行折半查找？画出进行折半查找的判定树，并求其在等概率的条件

7、下查找成功时的平均查找长度。（7分）密封线3 设一个工程有11项活动，9个事件,事件 V1表示整个工程开始,事件V9表示整个工程结束。(1)求出每个事件的最早和最晚发生时间？（2）完成整项工程至少需要多少时间？ (3)哪些活动是影响工程进度的关键？（10分）4 写出下图的邻接矩阵，并分别写出对下图从顶点B始进行深度优先和广度优先遍历的一个结果，并画出其对应的深度优先和广度优先生成树。（10分）ABCGED4 对数据表44，25，88，12，75，84，-6，60，写出： (1) 快速排序第一趟的过程和结果。(2) 间隔为3时第一趟希尔排序的结果。(3) 调整为小顶堆的过程。（7分）5已知一组元

8、素为46，74，16，53，14，26，40， 86试写出： （1）将其调整为小顶堆的过程。 （2）快速排序一趟的过程和结果。（6分）6 说明下列算法的功能。（5分）Void insert(Linklist &L,ElemType x, ElemType y) s=new Lnode; 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）

9、/ L不含表头结点 if(L&&L->next ) Q=L;L=L->next;p=L;While(p->next) p=p->next;P->next=q; q->next=NULL;8 试将树转换为相应的二叉树，再画出其对应的中序线索二叉树。（7分）ABCHGFEID 密封线9 试将树转换为相应的二叉树，并写出二叉树后序遍历的结果。（7分）ABCHGFEID 10 已知二叉树的前序遍历序列为DACEBHFGI，中序遍历序列为DCBEHAGIF试画出该二叉树，并简述由任意二叉树的前序遍历序列和中序遍历序列求二叉树B的思想方法。 四 算法设计（公办学生做1,2,3题27分, 民办学生做1,3题