文档介绍：模拟试卷九
一、单项选择题(每小杨2分,共20分)
素,则采用存储方式最节省运算时间。
(l)单链表(2)仅有头指针的单循环链表
(3)双链表(4)仅有尾指针的单循环链表
2. 串的长度是。
(1)串中不同字母的个数(2)串中不同字符的个数
(3)串中所含字符的个数,且大于0 (4)串中所含字符的个数
[l..n]作为两个栈S1和S2的共用存储结构,对任何一个钱,只有当
s[l..n]全满时才木能作入栈操作。为这两个栈分配空间的最佳方案是。
(1)S1的栈底位置为0, S2的栈底位置为n+1
(2)S1的栈底位置为0, S2的栈底位置为n/2
(3)S1的栈底位置为l, S2的栈底位置为n
(4)S1的栈底位置为1, S2的残底位置为n/2
4. 队列操作的原则是。
(1)先进先出(2)后进先出
(3)只能进行插入(4)只能进行删除
64个结点的完全二叉树的深度为(根的层次为 1)。
(1)8 (2)7 (3)6 (4)5
6. 在有n个结点的二叉链表中,值为非空的链域的个数为。
(1)n-l (2)2n-l (3)n+l (4)2n+1
,则顶点i的人度等于A中。
(1)第i行非∞的元素之和(2)第i列非∞的元素之和
(3)第i行非∞且非0的元素个数(4)第i列非∞且非O的元素个数
8. 在有n个结点且为完全二叉树的二叉排序树中查找一个键值,其平均比较次数
的数量级为。
(1) O(n) (2) O(log2n)
(3) O(nlog2n) (4) O(n2)
,则算法的比较次数最少。
(1)直接插入排序(2)快速排序
(3)归并排序(4)选择排序
, 排序在某趟结束后不一定能选出一个元素放到其最
终的位置上。
(l)选择(2)冒泡
(3)归并(4)堆
二、判断题(每小题1分,共10分)
1.( )在带头结点的单循环链表中,任一结点的后继指针均不空。
2.( )线性表采用链表方式和顺序表方式存储,执行插入和删除运算的时间
复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时
间相同。
3.( )在栈为空的情况下,不能作出栈操作,否则产生下溢出。
4.( )对矩阵压缩存储的方法是用三元组表存储矩阵元素。
5.( )在一个有向图的邻接表或逆邻接表中,如果某个顶点的链表为空,则
该顶点的度一定为o。
6.( )如果有向图G =(V,E)的拓扑序列唯一,则图中必定仅有一个顶点
的人度为O,一个顶点的出度为0。
7.( )向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序
树的高度。
8.( )在索引顺序表的查找中,对索引表既可采用顺序查找方法,也可采用
二分查找方法。
9.( )在快速排序算法中,以待排序的n个记录中的第一个记录的键值为基
准,将所有记录分为两组,该记录就在这两组的中间,这也是该记录
的最终位置。
10.( )在一个大根堆中,最小元素不一定在最