浙江理工大学 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 题图:邻接矩阵
V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
V1 0 1 1 1 0 0 0 0 0 0
V2 0 0 0 1 1 0 0 0 0 0
V3 0 0 0 1 0 1 0 0 0 0
V4 0 0 0 0 0 1 1 0 1 0
V5 0 0 0 0 0 0 1 0 0 0
V6 0 0 0 0 0 0 0 1 1 0
V7 0 0 0 0 0 0 0 0 1 0
V8 0 0 0 0 0 0 0 0 0 1
V9 0 0 0 0 0 0 0 0 0 1
V10 0 0 0 0 0 0 0 0 0 0

   (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 的整数放在后半部分.


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利