江苏省白蒲高级中学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）基数