资源描述：
《计算机水平考试-软件设计师分类模拟题数据结构(二)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、软件设计师分类模拟题数据结构(-)一、综合知识试题1>某双向链表屮的节点如下图所示，删除匸所指节点的操作为。A.t->prior->next=t->next;t->next->prior=t->prior；B・t->prior->prior=t->prior,t->next->next=t->next,C-t->prior->next=t->prior；t->next->prior=t->next；D.t->prior->prior=t->next；t->next->prior=t->prior；2、给定一个有n个元素的有序线性表。若采用顺序存储
2、结构，则在等概率前提下，删除其中的一个元素平均需要移动个元素。A・(n+：L)/2B・n/2C・(n-：L)/2D・13、设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的运算是oA.head(tail(tail(L)))B・tail(head(head(L)))C.head(tail(head(L)))D・tail(tail(head(L)))4、广义表中的元素可以是原了，也可以是表，因此广义
3、表的适用存储结构是oA.链表B.静态数组C.动态数组D.散列表5、若有数组声明a[0..3,0..2,1..4],设编译时为a分配的存储空间首地址为base_a,且每个数组元素占据一个存储单元。当元素以行为序存放(即按a[0,0,1],a[0z0,2],a[0,0,3],a[0,0,4],a[0,1,1],a[0zl,2],a[3,2,4]顺序存储)，则数组元索W[2,2,2]在其存储空间中相对的偏移量是oA.8B.12C・33D・48一个具有m个节点的二叉树，其二叉链表节点(左、右孩子指针分别用left^llright表示)中的空指针总数必定为
4、丄个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有节点进行如下操作：若节点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱节点;若p的右孩了指针为空，则将该右指针改为指向p在中序(先序、后序)遍丿力序列的后继节点。假设指针s指向中序(先序、后序)线索二叉树中的某节点，则7°6、A・m+2B.m+1C.mD.m-17、A.s—right指向的节点定是s所指节点的直接后继节点B.s^left指向的节点一定是s所指节点的直接前驱节点C.从s所指节点出发的right链可能构成环D・s所指节点的：Left和right指
5、针一定指向不同的节点8、若将某有序树T转换为二叉树匚，则T中节点的后根序列就是匚中节点的(8)遍历序列。例如，下图(a)所示的有序树转化为二叉树后如图(b)所示。'丄；1SJL4；.A.先序B.中序C.后序D.层序9、的邻接矩阵是一个对称矩阵。A.无向图B.AOV网C・AOE网D.冇向图10.具有n个顶点、0条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为OA・O(r?)B・O(M)C・(n*e)D・D(n+e)设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元索A[
6、i][j]等于丄/0分别表示顶点i与顶点jZ间有/无弧)，则该矩阵的元素数目为11,其中非零元素数目为12。llxA・E2B.N2C・N2-E2D.N2+E212^A・NB・N+EC・ED.N-E13、将一个无序序列屮的元素依次插入到一棵,并进行屮序遍历，可得到一个有序序列。A.完全二叉树B.最小生成树C.二叉排序树D.最优叉二树14、某一维数组中依次存放了数据元素12,23,30,38,41,52,54,76,85,在用折半(二分)查找方法(向上取整)查找元素54时，所经丿力''比较〃运算的数据元素依次为oA.41,52,54B.41,76,5
7、4C・41,76,52,54D・41,30z76,54已知一个线性表(16,25,35,43,51,62,87,93),采用散列函数H(Key)二Keymod7将元索散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为15,在该散列表上进行等概率成功杳找的平均杳找长度为_丄(确定为记录在查找表屮的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。15、A.16、A・(5*1+2+3+6)/8B・(5*丄+2+3+6)/9C・(8*1)/8D.(8*1)/917
8、、设循坏队列Q的定义中有rear^lllen两个域变量，其中rear表示队尾元素的指针，表示队列的长度，如下图所示(队列长度为3,队头元
