大学专业试卷《数据结构》A.doc

院系：—————— 专业班级：——————— 姓名：——————— 学号：——————
装 订 线
《数据结构》课程考试试卷A
适用专业： 考试日期： 闭卷
所需时间：120分钟 总分：100分
一、单项选择题（共15小题，每小题2分，总共 30分）
1. 一种抽象数据类型包括数据和( )两个部分。
A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明 
2. 在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(n2) D. O(log2n) 
3. 已知L是带表头结点的单链表, 删除第一个结点的语句是（ ）。
A. L = L->next; B. L-> next = L-> next -> next;
C. L = L; D. L-> next = L; 
4. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　　　）
A．插入 B．删除 C．排序 D．查找 
5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　　　）
A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1
6. 设串sl="Data Structures with Java",s2="it"，则子串定位函数index(s1,s2)的值为（　　　）。
A．15 B．16 C．17 D．18 
7. 在一个n个结点有向图的邻接矩阵表示中，删除一条边<vi,vj>需要的时间复杂度为 ( )。
A．O(1) B．O(i) C．O(j) D．O(n) 
8. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（　　　）
A．1207 B．1209 C．1211 D．1213 
9. 对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与（ ）有关。
A. n B. m C. n/m D. n*m 
10. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（　　　）
A．图中每个顶点的入度 B．图中每个顶点的出度
C．图中弧的条数 D．图中连通分量的数目
11. 下列排序算法中，其时间复杂度和记录的初始排列无关的是（　　　）
A．插入排序 B．堆排序
C．快速排序 D．冒泡排序
12. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（　　　）
A．f,c,b B．f,d,b C．g,c,b D．g,d,b
13. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )
A．4 B．5 C．6 D．7
14. 具有10个叶结点的二叉树中有（ ）个度为2的结点。
A．8 B．9 C．10 D．ll。
15. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定

二、填空题（共10小题，每小题2分，共20分）
1. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。 
2. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_ _。 
3. 在单链表中逻辑上相邻的结点而在物理位置上 相邻。 
4. 在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。
5. 迷宫问题是一个回溯控制的问题，最好使用 的方法来解决。 
6. 含n个顶点的无向连通图中至少含有 条边。
7. 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为 。
8. 已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。 
9. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 上，才会被加入到生成树中。
10. 在堆排序中，对n个记录建立初始堆需要调用 次调整算法。 

三、运算题（5小题，每小题6分，共30分）
1. 一个一维数组a[10]中存储着有序表(15,26,34,39,45,56,58,63,74,76)，根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。

度为1的结点个数：
平均搜索长度：

2. 已知一个图的顶点集V和边集G分别为：
V={1,2,3,4,5,6};
E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,<6,5>};
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从小到大的次序链接的，试写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答：
(1) (2)

3. 已知一个数据序列为{6,45,27,23,41,5,56,64}，把它调整为大根堆的结果。

最大堆：
  4. 已知带权图的邻接表如下所示，其中边表结点的结构为：
2
6
4
5
1
2
3
4
5
6
邻接点
权值
指针域
1
6
5
3
1
1
2
5
4
7
6
4
3
1
^
3
5
^
5
5
^
1
5
6
2
3
7
^
2
3
6
6
3
5
^
4
2
5
6
3
4
^

依此邻接表存储的图，采用Prim算法画出其最小生成树的生成过程。

5. 绘制出叶子结点权值为 w={5, 29, 7, 8, 14, 23, 3, 11}对应的哈夫曼树。

四、算法分析题（2小题，每小题6分，共12分）
1. 该算法功能为：将十进制整数转换成二进制数输出。阅读算法，按标号填写空缺的内容，要求统一填写在算法后面的标记处。
其中所用函数原型说明如下：
void Pop(SeqStack *S,DataType *x)；//出栈
void Push(SeqStack *S,DataType x)；//进栈
int StackEmpty(SeqStack S)；//判栈空
void StackInit(SeqStack *S)；//栈初始化

typedef int DataType;
#include"SeqStack.h"
void conversion(int n,int r)
{
SeqStack s;
DataType x;
char ch;
StackInit(&s);
while (n>0)
{
（1）
n=n/r;
}
while ( （2） )
{
（3）
printf(“%d”,x);
}
}
(1)
(2)
(3)

2. 已知二叉树中的结点类型BinTreeNode定义为:
typedef struct Node {
Datatype data;
struct Node *lchild, *rchild;
} BinTreeNode;
其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域。下面递归函数完成的功能是从二叉排序树BST中查找值为X的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。

BinTreeNode *SearchBST(BiTreeNode *T，DataType x)
  {
if(T==NULL||x==T->key)
      return （1） ；
    if(x<T->key)
      return （2） ；
    else
      return （3） ；
   }

(1)
(2)
(3)

五、算法设计题（1小题，每小题8分，共8分）
1. 阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x)
{//1和h分别为数据区的下界和上界
int i,j,t；
i=1；j=h；
while(i<j){
while(i<j && a[j]>=x)j--；
while(i<j && a[j]>=x)i++；
if(i<j)
{ t=a[j]；a[j]=a[i]；a[i]=t；}
}
if(a[i]<x) return i；
else return i-1；
}
（1）写出该函数的功能；
（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。