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

系 专业 班 学号 姓名
┉┉┉┉┉┉┉┉┉┉┉密┉┉┉┉┉┉┉┉┉┉封┉┉┉┉┉┉┉┉┉┉线┉┉┉┉┉┉┉┉┉┉

苏州科技学院　数据结构 试题 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) %n
3在数据结构中，从逻辑上可将数据结构分为_____。
A 动态结构和静态结构 B 紧凑结构和非紧凑结构
C 线性结构和非线性结构 D 内部结构和外部结构
4在一个带表头结点的双向循环链表中，若要在指针p所指向的节点之后插入一个q指针所指向的节点，则需要对q->right赋值为_________。
A p->left B p->right C p->right->right D p->left->left
5 快速排序方法在__________情况下最不利于发挥其长处。
A 要排序的数据量太大 B 要排序的数据中含有多个相同的值
C 要排序的数据已基本有序 D 要排序的数据个数为奇数
6在一个非空二叉树的中序序列中，根结点的左边___。
A 只有右子树上的所有节点 B只有右子树上的部分节点
C 只有左子树上的所有节点 D只有左子树上的部分节点
7若在中序线索二叉树中某一个结点存在右孩子，则该结点的后继是__________。
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)/2-1

10 对于具有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, 72
12在具有n个单元的顺序栈中，假定以地址顶端（即下标为n-1的单元）作为栈底，以top作为栈顶指针，则当作入栈处理时，top变化为_______。
A top不变 B top=0 C top-- D top++

二 判断题（正确的请在题后的括号中写√，否则请在题后的括号中写×，共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 对一个堆，无论按二叉树的层次遍历还是先序遍历，都不一定能得到有序序列。（ ）
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分）

┉┉┉┉┉┉┉┉┉┉┉密┉┉┉┉┉┉┉┉┉┉封┉┉┉┉┉┉┉┉┉┉线┉┉┉┉┉┉┉┉┉┉

3 设一个工程有11项活动，9个事件,事件 V1表示整个工程开始,事件V9表示整个工程结束。
(1)求出每个事件的最早和最晚发生时间？（2）完成整项工程至少需要多少时间？
(3)哪些活动是影响工程进度的关键？（10分）

4 写出下图的邻接矩阵，并分别写出对下图从顶点B始进行深度优先和广度优先遍历的一个结果，并画出其对应的深度优先和广度优先生成树。（10分）
A
B
C
G
E
D

4 对数据表{44，25，88，12，75，84，-6，60}，写出：
(1) 快速排序第一趟的过程和结果。
(2) 间隔为3时第一趟希尔排序的结果。
(3) 调整为小顶堆的过程。（7分）

5已知一组元素为{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） // 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分）
A
B
C
H
G
F
E
I
D

┉┉┉┉┉┉┉┉┉┉┉密┉┉┉┉┉┉┉┉┉┉封┉┉┉┉┉┉┉┉┉┉线┉┉┉┉┉┉┉┉┉┉

9 试将树转换为相应的二叉树，并写出二叉树后序遍历的结果。（7分）
A
B
C
H
G
F
E
I
D

10 已知二叉树的前序遍历序列为DACEBHFGI，中序遍历序列为DCBEHAGIF试画出该二叉树，并简述由任意二叉树的前序遍历序列和中序遍历序列求二叉树B的思想方法。

四 算法设计（公办学生做1,2,3题27分, 民办学生做1,3题，20分）
1 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素（不设头指针），试编写相应入队列、出队列和输出队列中全部元素值的算法。（10分）

2 编写算法求二叉链表存储的二叉树的深度。（7分）

3假设一个有向图含有n个顶点和e条弧，请编写程序实现该图的邻接表存储。(10分)

第7页