《数据结构》模拟题(补)
一.单项选择题
1.在线性表的下列存储结构中,读取元素花费时间最少的是【】。
A.单链表B.双链表C.顺序表D.循环链表
2.设计一个判定表达式中左、右括号是否配对出现的算法,采用【】数据结构最佳。
A.集合B.线性表C.队列D.栈
3.n个结点的线索二叉树上含有的线索数为【】。
A.2n B.n-1 C.n D.n+1
4.设广义表D=(a,(b,c)),则tail(D)=【】。
A.b,c B.(b,c) C.((b,c)) D.c
5.由4个结点可以构造出【】种不同的二叉树。
A.12 B.13 C.14 D.15
6.在栈中,出栈操作的时间复杂度为【】。
A.O(1) B.O(n) C.O(log2n) D.O(n2)
7.假设Q[0..len-1]表示循环队列,f为队头指针,r为队尾指针,则进队操作语句是【】。
A.f=f+1 B.r=r+1 C.f=(f+1)%len D.r=(r+1)%len
8.一个n*n的对称矩阵,如果以行或列为主序放入内存,则其容量为【】。
A.n*n B.n*n/2 C.n*(n+1)/2 D.(n+1)*(n+1)/2
9.队列操作的原则是【】。
A.进优于出B.出优于进C.先进先出D.后进先出
10.下列数据结构中,【】是非线性数据结构。
A.栈B.串C.队列D.树
11.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱,则【】。
A.p==q B.q->next=p C.p->next=q D.p->next=q->next
12.数组A中,每个元素的长度为4个字节,行下标i从1到5,列下标j从1到4,从首
地址SA开始连续存放在存储器内,该数组按行存放时,元素A[3][2]的起始地址为【】。
A.SA+20 B.SA+36 C.SA+40 D.SA+45
13.已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为d1,
则第i个结点的地址为【】。
A.d1+(i-1)*m B.d1+i*m C.d1+(i+1)m D.d1-i*m
14.分析下列算法suanfa1(n)的时间复杂度是【】。
void suanfa1(int n)
{ int i,j,x=1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x=x*2;
}
A.O(2n) B.O(2n) C.O(n2) D.O(n2+2)
15.将一个A[1..10,1..10]的三对角矩阵,按行优先存入一维数组B[1,30]中,A中元素
a[6,5]在B数组中的位置i为【】。
A.15 B.16 C.55 D.65
16.深度为6的二叉树最多有【】个结点。
A.62 B.63 C.64 C.65
17.由3个结点可以构造出【】种不同的二叉树。
A.2 B.3 C.4 D.5
18.栈的插入和删除操作在【】进行。
A.栈顶B.栈底C.指定位置D.随机位置
19.数组A中,每个元素的长度为3个字节,行下标i从1到5,列下标j从1到4,从首
地址SA开始连续存放在存储器内,该数组占用的字节数为【】。
A.20 B.60 C.80 D.120
20.下面语句的时间复杂度为【】。
s=0;
for(i=1;i<=n;i++)
s=s+i;
A.O(n) B.O(n5) C.O(5n) D.O(n2)
21.二叉树中,叶子的数组等于【】。
A.度为2的结点数加1 B.度为2的结点数减1
C.度为2的结点数D.度为2的结点数的两倍
22.数制转换的算法,采用【】数据结构最佳。
A.集合B.线性表C.队列D.栈
23.线性表采用链式存储时,其地址是【】。
A.必须是连续的B.一定是不连续的
C.部分地址必须是连续的D.连续或不连续都可以
24.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为【】。
A.物理结构B.逻辑结构
C.顺序存储结构D.链式存储结构
25.两个指针p和q,分别指向单链表的两个元素,p所指元素是q所指元素的前驱,则【】。
A.p==q B.q->next=p
C.p->next=q->next D.p->next=q
26.线性表在【】时, 宜用顺序表作存储结构。
A.经常随机存取B.经常作插入、删除
C.无足够连续存储空间D.经常作动态增减
二、判断题
1.【】二叉排序树中每个结点的关键字值大于其左非空孩子(若存在的话)的关键
字值,且小于其右非空孩子(若存在的话)结点的关键字值。
2.【】算法必须具备的5个特征是:有穷性、确定性、可行性、有0或多个输入量,
至少有1个输出量。
3.【】完全二叉树的某结点若没有左孩子,则它必是叶子结点。
4.【】哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
5.【】空栈就是所有元素都为0的栈。
6.【】在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表
是一种随机存取结构。
7.【】n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。
8.【】一个栈的输入序列是12345,则栈的输出序列可以是54312。
9.【】对于一个非空二叉树,它的根节点作为第一层,则第i层上最多能有2i-1个
结点。
10.【】稀疏矩阵压缩存储后,必会失去随机存取功能。
11.【】完全二叉树中,若一个结点没有左孩子,则它必是树叶。
12.【】用带表头结点的单链表表示队列,则判断队列为空的标准是头指针和尾指针
均指向同一个结点。
13.【】做进栈运算时应先判别,栈是否为空。
14.【】广义表中原子个数即为广义表的长度。
三、填空题
1.数据结构包含四种基本结构,它们是集合、【 1 】、树形结构、【 2 】。
2.二叉树的深度为k的二叉树最多有【 3 】个结点,其中第i层最多有【 4 】个结点。
3.n个结点的完全二叉树,使用一维数组t存储结点元素的值,假设t[i]存储第i个结点,
那么t[i]的双亲是【 5 】,左小孩是【 6 】,右小孩是t[2*i+1]。
4.由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树,它的带权路径长度为【 7 】。
5.若串s="hello",其子串个数是【 8 】。
6.将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次对结点编号,根结
点的编号为1。
编号为24的结点X的左孩子编号为【 9 】,右孩子编号为【 10 】。
7.长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为【 11 】。
8.WPL(T)指的是树的【 12 】,即每个叶子的权与根到该叶子的路径长度的乘积之和。
9.深度为k且有【 13 】个结点的二叉树称为满二叉树。
10.3层完全二叉树至少有【 14 】个结点。
四、简答题
1.画出二叉树的5种基本形态。
2.线性表的顺序存储结构相比链式存储结构,有什么优缺点?适用于什么情况的存储?
3.已知一颗非空二叉树,按前序遍历的结果是ACBGDEHFJI,按中序遍历的结果是
CGBAHEDJFI,请画出该二叉树,并写出后序遍历的序列结果。
4.若比较频繁的对一个线性表进行插入和删除操作,该线性表适合采用哪种存储结构?为
5.简述二叉排序树(二叉查找树)的定义及特点。
参考答案:
一.单项选择题
二.判断题
三.填空题
四、简答题
1. 画出二叉树的5种基本形态。
2. 线性表的顺序存储结构相比链式存储结构,有什么优缺点?适用于什么情况的存储?
优点:1)是一种随机存储结构,存取任何元素的时间是一个常数,速度快;2)结构简单,逻辑上相邻的元素在物理上也是相邻的;3)不使用指针,节省存储空间。
缺点:1)插入和删除元素要移动大量元素,消耗大量时间;2)需要一个连续的存储空
间;3)插入元素可能发生“溢出”;4)自由区中的存储空间不能被其他数据占用(共享)。
适用于经常用于检索、存取元素,但是插入和删除元素操作较少的情况。
3. 已知一颗非空二叉树,按前序遍历的结果是ACBGDEHFJI ,按中序遍历的结果是
CGBAHEDJFI ,请画出该二叉树,并写出后序遍历的序列结果。
二叉树:
后序遍历的结果是GBCHEJIFDA
4.若比较频繁的对一个线性表进行插入和删除操作,该线性表适合采用哪种存储结构?为什
么?时间复杂度是多少?
链式存储结构。
因为链式存储的线性表,插入和删除操作只需要改变指针,时间复杂度为O(1),而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动,时间复杂度为O(n)。
5.简述二叉排序树(二叉查找树)的定义及特点。
定义:如果二叉树的任一结点大于其非空左子树的所有节点,而小于等于其非空右子树的所有结点,则这棵二叉树称为二叉排序树。
特点:对一颗二叉排序树进行中序排序,所得的结点序列一定是递增有序的。