浙江理工大学 2013 年数据结构

贡献者： xzllxls

1. 一、单选题(在每小题的四个备选答案中选出一一个正确答案。每小题 2 分,共 20 分。)

　　 1. 链表不具备的特点是
A.可随机访问任一结点
B .插入删除不需要移动元素
C .不必事先估计存储空间
D .所需空间与其长度成正比

　　 2. 设线性表有 n 个元素,以下算法中，（）在顺序表 上实现比在链表上实现效率更高。
A.交换第 0 个元素与第 1 个元素的值
B .顺序输出这 n 个元素的值
C .输出第 i(Osisn-1)个元素值
D .输出与给定值 x 相等的元素在线性表中的序号

　　 3. 设输入序列为 a、b、C、d ,则借助栈所得到的输出序列不可能是（）。
A.a、b、c、d
B.d、c、b、a
C.a、c、d、b
D.d、a、b、c

　　 4. 为解决计算机主机与打印机之间的速度不匹配问题,通常设计一个打印数据缓冲区, 主机将要输出的数据依次写入到该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
A.栈 $\qquad$ B.队列 $\qquad$ C.树 $\qquad$ D.图

　　 5. 设哈夫曼树中的叶子结点总数为 m ,若用二叉链表作为存储结构,则该哈夫曼树中总共有（）个空指针域。
A.2m $\qquad$ B.4m $\qquad$ C . 2m+1 $\qquad$ D.2m-1

　　 6. 二叉树若用顺序存储结构表示,则下列四种运算中（）最容易实现。
A.先序遍历二叉树 $\qquad$ B.层次遍历二叉树
C.中序遍历二叉树 $\qquad$ D.后序遍历二又树

　　 7. 以下关于有向图的说法正确的是（）
A .强连通图是任何顶点到其他所有顶点都有边
B .完全有向图一定是强连通图
C .有向图中某顶点的入度等于出度
D .有向图边集的子集和顶点集的子集可构成原有向图的子图

　　 8. 若一个有向图中的顶点不能排成一一个拓扑结构序列,则可断定该有向图
A.含有多个出度为 0 的顶点
B.是个强连通图
C.含有多个入度为 0 的顶点
D.含有顶点数目大于 1 的强连通分量

　　 9. 顺序查找法适合于存储结构为的线性表。
A.哈希存储
B.压缩存储
C.顺序存储或链式存储
D.索引存储

　　 10. 在所有排序方法中,关键字比较的次数与记录地初始排列次序无关的是（）
A.shell 排序
B.冒泡排序
C.直接插入排序
D.简单选择排序

2. 二、填空题(每空 2 分,共 30 分。)

　　 1. 下面程序段的时间复杂度是

for (i=0; i<n; i++)
  for (j=0; j<m; j++)
    A[i][j]=0;

　　 2. 向一个不带头节点的栈指针为 Ist 的链式栈中插入一个*s 所指节点时,则执行（ ）和（ ）。

　　 3. 在二叉链表中判断某指针 p 所指结点为叶子结点的条件是按（）遍历一棵二叉排序树所得到的结点访问序列是一一个有序序列。

　　 5. 广义表 A=((a,b,c,d),( ))的表尾是（ ）.

　　 6. 有一个 10 阶对称矩阵 A ,采用压缩存储方式(以行序为主存储,且 A[0][0]=1) ,则 A[8][5]的地址是（ ）

　　 7. 高度为 h(>=0)的二叉树,至少有（ ）个结点,最多有（ ）个结点。

　　 8. 普里姆(PRIM)算法更适合于求边（ ）的网的最小生成树。

　　 9. 在无向图 G 的邻接矩阵 A 中,若 A[i][j]等于 1 ,则 A[j][i]等于（ ）.

　　 10. 在对一组记录(54, 38, 96, 23, 15, 72, 60, 45 , 83)进行直接插入排序时,当把第 7 个记录 60 插入到有序表时,为寻找插入位置需比较（ ）次。

　　 11. 若一组记录的排序码为( 46, 79, 56, 38, 40, 84) ,则利用堆排序的方法建立的初始堆为（）。

　　 12. 有一个长度为 10 的有序表,按折半查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（）.

　　 13. 在一棵平衡的二叉树中,每个节点的平衡因子 B 的取值范围是（）。

3. 三、判断题(每小题 2 分,共 20 分。)

　　 1. 对于数据结构,相同的逻辑结构,对应的存储结构也必相同。( )

　　 2. 哈夫曼树中没有度数为 1 的结点。( )

　　 3. 线性表中的所有元素都有一个前驱元素和后继元素。()

　　 4. 除了删除和插入操作外,数组的主要操作还有存取、修改、检索和排序。()

　　 5. 链表的每一个结点都恰好包含一个指针。( )

　　 6. 无向图的邻接矩阵一定是对称矩阵,且有向图的邻接矩阵一定是非对称矩阵。( )

　　 7. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点。( )

　　 8. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )

　　 9. 满二叉树一定是完全二叉树,完詮二叉树不一定是满二叉树。( )

　　 10. 快速排序是排序算法中平均性能最好的一种排序。( )

4. 四、应用题(共 50 分。)

　　 1. (14 分)已知一棵二叉树如右图所示:
(1)中序全线索化二叉树;
(2)写出对该二叉树进行先序遍历和后序遍历的结果;
(3)试画出其相应的树。

　　 2. (12 分)已知某有向图的邻接矩阵为:

　　 (1)画出此图的对应邻接表,要求边结点按照序号从大到小排序;
(2)写出以(1)为存储结构的、顶点 V1 为出发点的深度优先遍历次序;
(3)写出以(1)为存储结构的、顶点 V1 为出发点的广度优先遍历次序。

　　 3. (12 分)设散列表的长度 m=13,散列函数为 H(K)=K mod m ,给定的关键码序列为 20 , 11, 14 , 68 , 19, 23, 10, 1,84, 55, 27 , 79。
(1)使用线性探查再散列法来构造散列表;
(2)并求出在等概率的情况下,这种方法在搜索成功时的平均搜索长度。

　　 4. (12 分)已知序列{503 , 87 , 512 , 61, 908, 170 , 897 , 275 , 653 , 462} ,采用基数排序法对该序列作升序排序时的每一趟的结果。

5. 五、算法设计题(每小题 15 分,共 30 分)

　　 1.设有两个集合 A 和 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B 和 C 分别用链式存储结构表示。

　　 2.设有一个顺序表 L,其元素为整型数据,试编写一算法将 L 中所有小于 0 的整数放在前半部分,大于等于 0 的整数放在后半部分。