江苏省白蒲高级中学2020—2021学年信息技术竞赛数据结构与算法练习卷一(含答案与评分标准)

江苏省白蒲高级中学信息技术竞赛数据结构与算法练习一

一、单项选择题（每小题 2 分，共20分）

1．对于下面程序段的时间复杂度为（　　　）。

for(i=1;i<=n;i++)

        for(j=1;j<=i;j++)

            x=x+1;

A）O(n)   B）O(n2)   C）O(n*i)   D）O(n+i)

2. 在一个单链表中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（　　　）语句序列。

A）p=q; p->next=q;               B）p->next=q; q->next=p;

C）p->next=q->next; p=q;         D）q->next=p->next; p->next=q;

3. 采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（　　　）。

A）先序遍历  B）中序遍历  C）后序遍历  D）层次遍历

4. 设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（　　　）。

A）1、2、3、4、5、6    B）2、1、3、4、5、6

C）3、4、2、1、5、6    D）4、3、2、1、5、6

5. 设S为一个长度为 n的字符串，其中的字符各不相同，则 S中的互异的非平凡子串（非空且不同于S本身）的个数为（　　　）。

    A）   B）     C）   D）

6. 一棵深度为5的完全二叉树的结点数至少为（　　　）。

    A）16          B）15           C）32               D）31

7. 对于具有n个顶点的强连通有向图，其边条数的最小值为（　　　）。

    A）n+1         B）n            C）n-1              D）n-2

8. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（　　　）。

A）都不相同       B）完全相同

C）先序和中序相同，而与后序不同  D）中序和后序相同，而与先序不同

9. 用n个键值构造一棵二叉排序树，最低高度为（　　　）。

A）          B）         C）          D）

10. 在下列算法中，操作时间不随文件的初始状态变化的排序算法是（　　　）。

A）堆排序      B）折半插入排序     C）基数排序    D）快速排序

二、（本题10分）

有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？

三、（本题10分）

将关键字序列（7、8、11、18、9、14, 30）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：H(key)=（key * 3）% m（m为表长），处理冲突采用线性探测再散列法，要求装填（载）因子为0.7，请画出所构造的散列表；计算查找成功的平均查找长度。

四、（本题10分）

带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；

②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；

③重复步骤②，直到u是目标顶点时为止。

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。

五、（本题10分）

对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。

六、（本题10分）

有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。

七、（本题10分）

给定一组权值{3，4，7，14，15，20}，试画出相应的哈夫曼树，并计算带树路径长度WPL的值。

八、（本题10分）

编写一棵二叉树的层次遍历的算法。