2020年春【中石油】数据结构第二次在线作业（100分）

skystar

【石油大学】数据结构-第二次在线作业
试卷总分:100    得分:100
第1题,1.（2.5分）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()
A、1和 5
B、2和4
C、4和2
D、5和1
正确答案:


第2题,2.（2.5分）栈和队列的共同点是（）
A、都是先进先出
B、都是先进后出
C、只允许在端点处插入和删除元素
D、没有共同点
正确答案:


第3题,3.（2.5分）栈和队都是（）
A、顺序存储的线性结构
B、链式存储的非线性结构
C、限制存取点的线性结构
D、限制存取点的非线性结构
正确答案:


第4题,4.（2.5分）下面关于串的的叙述中，哪一个是不正确的？（）
A、串是字符的有限序列
B、空串是由空格构成的串
C、模式匹配是串的一种重要运算
D、串既可以采用顺序存储，也可以采用链式存储
正确答案:


第5题,5.（2.5分）设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）
A、求子串
B、联接
C、匹配
D、求串长
正确答案:


第6题,6.（2.5分）串'ababaaababaa'的next数组为（）
A、ERROR 15
B、12121111212
C、11234223456
D、123012322345
正确答案:


第7题,7.（2.5分）字符串'ababaabab'的nextval为（）
A、(0,1,0,1,04,1,0,1)
B、(0,1,0,1,0,2,1,0,1)
C、(0,1,0,1,0,0,0,1,1)
D、(0,1,0,1,0,1,0,1,1 )
正确答案:


第8题,8.（2.5分）若串S='software',其子串的数目是（）
A、8
B、37
C、36
D、9
正确答案:


第9题,9.（2.5分）串的长度是指（）
A、串中所含不同字母的个数
B、串中所含字符的个数
C、串中所含不同字符的个数
D、串中所含非空格字符的个数
正确答案:


第10题,10.（2.5分）假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A、808
B、818
C、1010
D、1020
正确答案:


第11题,11.（2.5分）数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()
A、1175
B、1180
C、1205
D、1210
正确答案:


第12题,12.（2.5分）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为()
A、i*(i-1)/2+j
B、j*(j-1)/2+i
C、i*(i+1)/2+j
D、j*(j+1)/2+i
正确答案:


第13题,13.（2.5分）对稀疏矩阵进行压缩存储目的是（）
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、降低运算的时间复杂度
正确答案:


第14题,14.（2.5分）已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）
A、head（tail（tail（L）））
B、tail（head（head（tail（L））））
C、head（tail（head（tail（L））））
D、head（tail(head（tail（tail（L）））)）
正确答案:


第15题,15.（2.5分）已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()。
A、head(tail(LS))
B、tail(head(LS))
C、head(tail(head(tail(LS)))
D、head(tail(tail(head(LS))))
正确答案:


第16题,16.（2.5分）已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()
A、-A+B*C/DE
B、-A+B*CD/E
C、-+*ABC/DE
D、-+A*BC/DE
正确答案:


第17题,17.（2.5分）设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）
A、5
B、6
C、7
D、8
正确答案:


第18题,18.（2.5分）设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）
A、m-n
B、m-n-1
C、n+1
D、条件不足，无法确定
正确答案:


第19题,19.（2.5分）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A、9
B、11
C、15
D、不确定
正确答案:


第20题,20.（2.5分）具有10个叶结点的二叉树中有（）个度为2的结点
A、8
B、9
C、10
D、ll
正确答案:


第21题,21.（2.5分）设给定权值总数有n个，其哈夫曼树的结点总数为()
A、不确定
B、2n
C、2n+1
D、2n-1
正确答案:


第22题,22.（2.5分）有关二叉树下列说法正确的是（）
A、二叉树的度为2
B、一棵二叉树的度可以小于2
C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
正确答案:


第23题,23.（2.5分）一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点
A、2h
B、2h-1
C、2h+1
D、h+1
正确答案:


第24题,24.（2.5分）对于有n个结点的二叉树,其高度为（）
A、nlog₂n
B、log₂n
C、log₂n+1
D、不确定
正确答案:


第25题,25.（2.5分）利用二叉链表存储树，则根结点的右指针是（）。
A、指向最左孩子
B、指向最右孩子
C、空
D、非空
正确答案:


第26题,26.（2.5分）树的后根遍历序列等同于该树对应的二叉树的()
A、先序序列
B、中序序列
C、后序序列
正确答案:


第27题,27.（2.5分）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。
A、前序
B、中序
C、后序
D、按层次
正确答案:


第28题,28.（2.5分）在下列存储形式中，哪一个不是树的存储形式？（）
A、双亲表示法
B、孩子链表表示法
C、孩子兄弟表示法
D、顺序存储表示法
正确答案:


第29题,29.（2.5分）已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
A、CBEFDA
B、FEDCBA
C、CBEDFA
D、不定
正确答案:


第30题,30.（2.5分）已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。
A、acbed
B、decab
C、deabc
D、cedba
正确答案:


第31题,31.（2.5分）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A、空或只有一个结点
B、任一结点无左子树
C、高度等于其结点数
D、任一结点无右子树
正确答案:


第32题,32.（2.5分）一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：()
A、不确定
B、0
C、1
D、2
正确答案:


第33题,33.（2.5分）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()
A、X的双亲
B、X的右子树中最左的结点
C、.X的左子树中最右结点
D、X的左子树中最右叶结点
正确答案:


第34题,34.（2.5分）引入二叉线索树的目的是（）
A、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
C、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
正确答案:


第35题,35.（2.5分）下述编码中哪一个不是前缀码（）。
A、（00，01，10，11）
B、（0，1，00，11）
C、（0，10，110，111）
D、（1，01，000，001）
正确答案:


第36题,36.（2.5分）下面几个符号串编码集合中，不是前缀编码的是（）。
A、{0,10,110,1111}
B、{11,10,001,101,0001}
C、{00,010,0110,1000}
D、{b,c,aa,ac,aba,abb,abc}
正确答案:


第37题,37.（2.5分）图中有关路径的定义是（）。
A、由顶点和相邻顶点序偶构成的边所形成的序列
B、由不同顶点所形成的序列
C、由不同边所形成的序列
D、上述定义都不是
正确答案:


第38题,38.（2.5分）设无向图的顶点个数为n，则该图最多有（）条边。
A、n-1
B、n(n-1)/2
C、n(n+1)/2
D、0
E、n2
正确答案:


第39题,39.（2.5分）一个n个顶点的连通无向图，其边的个数至少为（）。
A、n-1
B、n
C、n+1
D、nlogn
正确答案:


第40题,40.（2.5分）若串S1='ABCDEFG',S2='9898',S3='###',S4='012345',执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,'8'),length(S2)))其结果为（）
A、ABC###G0123
B、ABCD###2345
C、ABC###G2345
D、ABC###2345
E、ABC###G1234
正确答案:E