电子科技大学电子科大16秋《数据结构》在线作业2
一、单选题（共 16 道试题，共 48 分。）
1. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）。 A. O(1) B. O(n) C. O(n㏒n) D. O(n2) 正确答案：
2. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。
A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表 正确答案：
3. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（ ）。
A. P=″SCIENCE″ B. P=″STUDY″ C. S=″SCIENCE″ D. S=″STUDY″ 正确答案：
4. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ ）。 A. p->next==head
B. p->next->next==head C. p->next==NULL D. p==head 正确答案：
5. 高度为5的完全二叉树中含有的结点数至少为（ ）。 A. 16 B. 17 C. 31 D. 32
正确答案：
6. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A. 插入
B. 删除 C. 排序 D. 定位 正确答案：
7. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则（ ）。 A. p指向头结点 B. p指向尾结点
C. *p的直接后继是头结点 D. *P的直接后继是尾结点 正确答案：
8. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。
A. 3，2，6，1，4，5 B. 3，4，2，1，6，5 C. 1，2，5，3，4，6 D. 5，6，4，2，3，1 正确答案：
9. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。 A. 5 B. 8 C. 11 D. 18
正确答案：
10. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。 A. 数据元素的相邻地址表示 B. 数据元素在表中的序号表示 C. 指向后继元素的指针表示 D. 数据元素的值表示 正确答案：
11. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）。 A. 栈 B. 队列 C. 树 D. 图
正确答案：
12. 下面程序段的时间复杂度为（ ）。 for (i=0; i 13. 采用两类不同存储结构的字符串可分别简称为（ ）。 A. 主串和子串 B. 顺序串和链串 C. 目标串和模式串 D. 变量串和常量串 正确答案： 14. 散列文件也称为（ ）。 A. 顺序文件 B. 索引文件 C. 直接存取文件 D. 间接存取文件 正确答案： 15. 判断两个串大小的基本准则是（ ）。 A. 两个串长度的大小 B. 两个串中首字符的大小 C. 两个串中大写字母的多少 D. 对应的第一个不等字符的大小 正确答案： 16. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。 A. 15 B. 16 C. 17 D. 18 正确答案： 16秋《数据结构》在线作业2 二、多选题（共 2 道试题，共 8 分。） 1. 构造最小生成树的两个基本算法是（ ）。 A. 普里姆算法 B. 克鲁斯卡尔算法 C. 迪杰斯特拉算法 D. 哈希算法 正确答案： 2. 通用的处理哈希冲突的方法有（ ）。 A. 开放定址法 B. 再哈希法