内容发布更新时间 : 2024/5/16 2:57:17星期一 下面是文章的全部内容请认真阅读。

谋学网www.mouxue.com

一、单选题（共 16 道试题，共 48 分。） V 1. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）。 A. Dout B. Dout-1 C. Dout+1 D. n

2. 对于哈希函数H(key)=key,被称为同义词的关键字是（ ）。 A. 35和41 B. 23和39 C. 15和44 D. 25和51

3. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）。 A. O(1) B. O(n) C. O(n㏒n) D. O(n2)

4. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A. 插入 B. 删除 C. 排序 D. 定位

5. 已知函数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″

6. 二叉树中第5层上的结点个数最多为（ ）。 A. 8 B. 15 C. 16 D. 32

7. 若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（ ）。 A. O(㏒n) B. O(n) C. O(n㏒n)

谋学网www.mouxue.com

D. O(㏒2n)

8. 采用两类不同存储结构的字符串可分别简称为（ ）。 A. 主串和子串 B. 顺序串和链串 C. 目标串和模式串 D. 变量串和常量串

9. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）。 A. 10 B. 11 C. 12

D. 不确定的

10. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。 A. 0 B. 2 C. 3 D. 5

11. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。

A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表

12. 下面程序段的时间复杂度为（ ）。 for (i=0; i

13. 高度为5的完全二叉树中含有的结点数至少为（ ）。 A. 16 B. 17 C. 31 D. 32

14. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。 A. 0

谋学网www.mouxue.com

B. 1 C. 48 D. 49

15. 设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）。 A. 联接 B. 求子串 C. 字符定位 D. 子串定位

16. 若进栈序列为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

二、多选题（共 2 道试题，共 8 分。） V 1. 由于排序过程中涉及的存储器不同，可以将排序方法分为（ ）。 A. 稳定排序 B. 不稳定排序 C. 内部排序 D. 外部排序 D

2. 假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。 A. 12345 B. 54321 C. 43215 D. 14325 BCD

三、判断题（共 22 道试题，共 44 分。） V 1. 在对链队列作出队操作时，不会改变front指针的值。 A. 错误 B. 正确

2. 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。 A. 错误 B. 正确