2012贵州大学数据结构A卷

数据结构

注意事项：

1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

1．不是四类基本逻辑结构之一的是                                            （     ）

A、集合        B、链表结构

C、树形结构        D、网状结构

2．关于队列的描述，错误的是                                                （     ）

A、队列的头指针指下一个入队的位置

B、普通队列要求满足“先进先出”    

C、使用一个队列可以模拟一个银行的多个同性质服务窗口的排队状况

    D、循环队列可以采用顺序表实现

3．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是                （     ）

A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B、在第i个结点后插入一个新结点（1≤i≤n）    

C、删除第i个结点（1≤i≤n）

    D、将n个结点从小到大排序

4．下列关于串的叙述中，正确的是                                            （     ）

A、一个串的字符个数即该串的长度

B、一个串的长度至少是1　　

C、空串是由一个空格字符组成的串

D、两个串S1和S2若长度相同，则这两个串相等

5．稀疏矩阵一般的压缩存储方法有两种，即                                    （     ）

A、二维数组和三维数组                B、三元组和散列

C、三元组和十字链表                    D、散列和十字链表

6．按照二叉树的定义,具有3个结点的二叉树有                                （     ）

A、3种            B、4种            C、5种            B、6种

7．不是图的存储结构的是                                                 （     ）

A、邻接多重表    B、十字链表        C、关联矩阵     D、可利用空间表    

8．在关于动态存储管理，错误的说法是                                        （     ）

A、未被占用的连续地址空间称为空闲块

B、可利用空间表一般采用链表

C、针对内存申请块的大小范围较广时，应该采用首次拟合法

D、针对内存申请块的大小较均匀时，应该采用最差拟合法

9．理想情况下，速度最快的查找结构的是                                    （     ）

A、分块索引            B、二叉排序树            C、二叉平衡树            D、哈希表

10. 关于各种排序方法，错误的说法是                                        （     ）

A、关键字大小相同的记录，排序后先后顺序不改变，则称为此排序为稳定的

B、内部排序算法的性能由关键字比较次数和记录移动次数决定

C、冒泡排序的时间复杂度为O(nlogn)

D、堆排序使用的堆对应一棵完全二叉树

1．若使用伙伴系统进行动态存储管理，若申请32个字，选中的空闲块有128个字，则这个空闲块会被为__________个块（最小块大小可以为4）。

2．在逻辑上相关的元素，在物理存储地址上不一定相邻，两种不同的存储结构分别称为：________存储结构和________存储结构。

3．快速排序在最坏情况下算法复杂度为__________；在哈希表中，不同关键字得到相同哈希地址称为________。

4．数据结构可以形式化定义为一个二元组，Data_Structure=(D，S)，其中D是__________的集合，S是__________的集合。

5．进行深度优先搜索需要用到辅助数据结构是__________。 

6．已知中缀表达式为(a+b)/(c-d)，对应的前缀表达式为__________。

7．稀疏矩阵的行链表存储中，每行单链表的结点具有相同的__________。

1．设待排序记录集合的关键字为（45,27,18,67,13,76,38,90,27,25），采用希尔排序算法，间隔增量d分别取5、3、1，请写出第一趟和第二趟希尔排序之后的结果。

2．从一棵空的平衡二叉树开始，将以下关键码值依次插入：41,27,10,65,45,36,29，请画出插入每一个元素且调整平衡之后的平衡二叉树。

3. 画出用Prim算法求出下图的最小生成树

4．画出下面稀疏矩阵的三元存储法表示

。（行列下标从1开始）

5．顺序栈初始状态如下左图所示，经过入下入队和出队操作之后，请在右图中画出栈内容、top和base所指。操作顺序为：

元素A、B相继压栈；然后出栈一个元素；又有元素C、 D、E入栈；然后出栈两个元素；

6．已知一棵二叉树的先序遍历为：A  B    D      C  E  F      G      

，其中表示叶子结点，请画出这棵二叉树。

7．假定一组记录的关键字为{50,27,16,67,14,36,38,29,26,24}，采用HASH表存储，HASH地址空间为HT[15]，若采用除留余数法构造HASH函数h(key)=key mod 13，用线性再探测法处理冲突，线性再探测序列为1,2,3,4,5…n，请画出最后得到的HASH表，求出平均查找长度。

8. 使用Floyd算法求出下图中顶点之间的最短路径，请填写求解过程邻接矩阵和路径矩阵。

1．请完成如下函数：

void BInsertSort(SqList &L){

    //对顺序表L作折半插入排序

for (i=2;i<=L.length;++i){

        _________________;                //设置观察哨L.r[0]

        left=1;_right=_________;            //设置搜索范围

        while(left <=right){

            _______________;                //计算折半位置

            if (LT(L.r[0].key, L.r[m].key)) 

_________;                //向左折半

            else

                left=m+1;                //向右折半

        }

        for (j=i-1;j>=right+1;--j) ___________;    //向后移动记录

        L.r[right+1]=L.r[0];                    //插入

}

}

2. 请用代码定义出有向图的邻接矩阵的有关数据结构，然后此基础上实现图的广度优先遍历（注意：不要求实现图的输入和输出，只需实现遍历函数,访问结点时输出该结点的顶点编号即可）。