试卷详情
-
软件设计师-数据结构
-
[单项选择]一个含有n个顶点和e条边的简单无向图,在其邻接矩阵存储结构中共有()个零元素。
A. e
B. 2e
C. n2-e
D. n2-2e
-
[单项选择]给定一个有n个元素的有序线性表。若采用顺序存储结构,则在等概率前提下,删除其中的一个元素平均需要移动()个元素。
A. (n+1)/2
B. n/2
C. (n-1)/2
D. 1
-
[单项选择]设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确()。
A. 21
B. 23
C. 41
D. 62
-
[单项选择]
对于给定的一组关键字(12,2,16,30,8,28,4,10,20,6,18),按照下列算法进行递增排序,写出每种算法第一趟排序后得到的结果:希尔排序(增量为5)得到 (67) ,快速排序(选第一个记录为基准元素)得到 (68) ,链式基数(基数为10排)序得到 (69) ,二路归并排序得到 (70) ,堆排序得到 (71) 。
(67)处填()。
A. 2,4,6,8,10,12,16,18,20,28,30
B. 6,2,10,4,8,12,28,30,20,16,18
C. 12,2,10,20,6,18,4,16,30,8,28
D. 30,10,20,12,2,4,16,6,8,28,18
-
[单项选择]循环链表的主要优点是()。
A. 不再需要头指针了
B. 已知某个节点的位置后,能很容易找到它的直接前驱节点
C. 在进行删除操作后,能保证链表不断开
D. 从表中任一节点出发都能遍历整个链表
-
[单项选择]()的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A. 树形存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
-
[单项选择]对n个元素进行快速排序时,最坏情况下的时间复杂度为()。
A. O(log2n)
B. O(n)
C. O(nlog2/t)
D. O(n2)
-
[单项选择]任何一个基于“比较”的内部排序的算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为()。
A. 10
B. 11
C. 21
D. 36
-
[单项选择]
简单无向图的邻接矩阵是对称的,可以对其进行压缩存储。若无向图G有n个节点,其邻接矩阵为A[1..n, 1..n],且压缩存储在B[1..k]中,则k的值至少为 (30) 。若按行压缩存储对称矩阵的上三角元素,则当n等于10时,边(V6,V3)的信息存储在B[ (31) ]中。
(30)处填()。
A. n(n+1)/2
B. n2/2
C. (n-1)(n+1)/2
D. n(n-1)/2
-
[单项选择]()在其最好情况下的算法时间复杂度为O(n)。
A. 插入排序
B. 归并排序
C. 快速排序
D. 堆排序
-
[单项选择]若二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则其后序遍历序列为()。
A. DEBAFC
B. DEFBCA
C. DEBCFA
D. DEBFCA
-
[单项选择]由元素序列27,16,75,38,51构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为2的节点)为()。
A. 27
B. 38
C. 51
D. 75
-
[单项选择]由权值为9,2,5,7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为()。
A. 23
B. 37
C. 44
D. 46
-
[单项选择]()从二叉树的任一节点出发到根的路径上,所经过的节点序列必按其关键字降序排列。
A. 二叉排序树
B. 大顶堆
C. 小顶堆
D. 平衡二叉树
-
[单项选择]若排序前后关键字相同的两个元素相对位置不变,则称该排序方法是稳定的。()排序是稳定的。
A. 归并
B. 快速
C. 希尔
D. 堆
-
[单项选择]已知有一维数组A(0..m*n-1],若要对应为m行、n列的矩阵,则下面的对应关系()可将元素A[k](0≤k<m*n)表示成矩阵的第i行、第j列的元素(0≤i<m,0≤j<n)。
A. i=k/n,j=k%m
B. i=k/m,j=K%m
C. i=k/n,j=k%n
D. i=k/m,j=k%n
-
[单项选择]
给定数据结构(V,E),y为节点的有限集合,V=V1,V2,V3,V4,V5,V6,V7,V8),E是V上关系的集合。
(43)处填()。
E=<V1,V2>,<V3,V4),<V5,V6>,<V5,V6>,<V1,V3>,<V4,V7>,<V4,V5>,<V2,V4>,<V4,V6>),它所对应的图形是 (42) ,这是 (43) 。
图的存储结构主要有邻接表和 (44) ,若用邻接表来存储一个图,则需要保存一个 (45) 存储的节点表和若干个 (46) 存储的关系表(又称边表)。
A. 树
B. 无向图
C. 有向图
D. 无向图
-
[单项选择]若广义表L((1,2,3)),则L的长度和深度分别为()。
A. 1和1
B. 1和2
C. 1和3
D. 2和2
-
[单项选择]已知某二叉树的中序、层序序列分别为DBAFCE,FDEBCA,则该二叉树的后序序列为()。
A. BCDEAF
B. ABDCEF
C. DBACEF
D. DABECF
-
[单项选择]已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0…6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为()。
A. 1.5
B. 1.7
C. 2.0
D. 2.3
-
[单项选择]
类比二分搜索算法,设计k分搜索算法(k为大于2的整数)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素……这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;如果未找到要搜索的元素,则继续在得到的集合上进行k分搜索;如此进行,直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为 (53) ,在最好情况下搜索失败的时间复杂度为 (54) 。
(53)处填()。
A. O(logn)
B. O(nlogn)
C. O(logkn)
D. O(nlogkn)
-
[单项选择]在一棵度为3的树中,若有2个度为3的节点,有1个度为2的节点,则有()个度为0的节点。
A. 4
B. 5
C. 6
D. 7
-
[单项选择]将两个长度为n的递增有序表归并成一个长度为2n的递增有序表,最少需要进行关键字比较()次。
A. 1
B. n-1
C. n
D. 2/9
-
[单项选择]以比较为基础的排序算法在最坏情况下的计算时间下界为()。
A. O(n)
B. O(n2)
C. O(logn)
D. O(nlogn)
-
[单项选择]若一个具有n个节点、k条边的非连通无向图是一个森林(n>k),则该森林中必有()棵树。
A. k
B. n
C. n-k
D. n+k
-
[单项选择]堆是一种数据结构,()是堆。
A. (10,50,80,30,60,20,15,18)
B. (10,18,15,20,50,80,30,60)
C. (10,15,18,50,80,30,60,20)
D. (10,30,60,20,15,18,50,80)
-
[单项选择]
一棵查找二叉树,其节点A,B,C,D,E,F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中,每个节点占4字节,前二字节存放节点值,后二字节依次放左指针、右指针。
(20)处填()。
若该查找二叉树的根节点为E,则它的一种可能的前序遍历为 (20) ,相应的层次遍历为 (21) 。在以上两种遍历情况下,节点c的左指针LC的存放地址为 (22) ,LC的内容为 (23) 。节点A的右指针RA的内容为 (24) 。
A. EAFCBD
B. EFACDB
C. EABCFD
D. EACBDF
-
[单项选择]一个具有767个节点的完全二叉树,其叶子节点个数为()。
A. 383
B. 384
C. 385
D. 386
-
[单项选择]在11个元素的有序表A[1…11)中进行折半查找[L(low+high)/2],查找元素A[11]时,被比较的元素的下标依次是()。
A. 6,8,10,11
B. 6,9,10,11
C. 6,7,9,11
D. 6,8,9,11
-
[单项选择]关键路径是指AOE(Activity On Edge)网中()。
A. 最长的回路
B. 最短的回路
C. 从源点到汇点(结束顶点)的最长路径
D. 从源点到汇点(结束顶点)的最短路径
-
[单项选择]若G是一个具有36条边的非连通无向图(不含自回路和多重边),则图G至少有()个顶点。
A. 11
B. 10
C. 9
D. 8
-
[单项选择]一个具有n(n>0)个顶点的连通无向图至少有()条边。
A. n+1
B. n
C. n/2
D. n-1
-
[单项选择]在平衡二叉树中,()。
A. 任意节点的左、右子树节点数目相同
B. 任意节点的左、右子树高度相同
C. 任意节点的左、右子树高度之差的绝对值不大于1
D. 不存在度为1的节点
-
[单项选择]在二叉树的顺序存储中,每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个节点,采用三叉链表存储时,每个节点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个节点下标为k(起始下标为1),那么()时采用顺序存储更节省空间。
A. d<12n/(k-n)
B. d>12n/(k-n)
C. d<12n/(k+n)
D. d>12n/(k+n)
-
[单项选择]若采用邻接矩阵来存储简单有向图,则其某一个顶点i的入度等于该矩阵()。
A. 第i行中值为1的元素个数
B. 所有值为1的元素总数
C. 第i行及第i列中值为1的元素总个数
D. 第i列中值为1的元素个数
-
[单项选择]在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是()。
A. 基数排序
B. 快速排序
C. 堆排序
D. 归并排序
-
[单项选择]若循环队列以数组Q[O..m-1]作为其存储结构,变量rear表示循环队列中队尾元素的实际位置,其移动按rear=(rear+1) mod m进行,变量length表示当前循环队列中的元素个数,则循环队列的队首元素的实际位置是()。
A. rear-length
B. (rear-length+m) mod m
C. (1+rear+m-length) mod m
D. m-length
-
[单项选择]无向图中一个顶点的度是指图中()。
A. 通过该顶点的简单路径数
B. 通过该顶点的回路数
C. 与该顶点相邻接的顶点数
D. 与该顶点连通的顶点数
-
[单项选择]若对27个元素只进行三趟多路归并排序,则选取的归并路数为()。
A. 2
B. 3
C. 4
D. 5
-
[单项选择]在一棵完全二叉树中,其根的序号为1,()可判定序号为p和q的两个节点是否在同一层。
A. [logp]=[log2q)
B. log2 p=log2 q
C. [log2 p]+1=[log2q)
D. [log2 p]=[log2 q)+1
-
[单项选择]设节点x和y是二叉树中任意的两个节点,在该二叉树的先根遍历序列中x在y之前,而在其后根遍历序列中x在y之后,则x和y的关系是()。
A. x是y的左兄弟
B. x是y的右兄弟
C. x是y的祖先
D. x是y的后裔
-
[单项选择]以下序列中不符合堆定义的是()。
A. (102,87,100,79,82,62,84,42,22,12,68)
B. (102,100,87,84,82,79,68,62,42,22,12)
C. (12,22,42,62,68,79,82,84,87,100,102)
D. (102,87,42,79,82,62,68,100,84,12,22)
-
[单项选择]在常用的描述二叉排序树的存储结构中,关键字值最大的节点()。
A. 左指针一定为空
B. 右指针一定为空
C. 左右指针均为空
D. 左右指针均不为空
-
[单项选择]在()存储结构中,数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A. 顺序(Sequence)
B. 链表(Link)
C. 索引(1ndex)
D. 散列(Hash)
-
[单项选择]
为在状态空间树中 (34) ,可以利用LC-检索(Least Cost Search)快速找到一个答案节点。在进行LC-检索时,为避免算法过分偏向于作纵深检查,应该 (35) 。
(34)处填()。
A. 找出任一个答案节点
B. 找出所有的答案节点
C. 找出最优的答案节点
D. 进行遍历
-
[单项选择]利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素30要进行()次元素间的比较。
A. 4
B. 5
C. 6
D. 7
-
[单项选择]若一棵哈夫曼(Huffman)树共有9个顶点,则其叶子节点的个数为()。
A. 4
B. 5
C. 6
D. 7
-
[单项选择]表达式a*(b+c)-d的后缀表达形式为()。
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
-
[单项选择]
给定节点的关键字序列(F,B,J,G,E,A,I,D,C,H),对它按字母的字典顺序进行排列。采用不同方法,其最终结果相同,但中间结果是不同的。
(72)处填()。
Shell排序的第一趟扫描(步长为5)结果应为 (72) 。
冒泡排序(大数下沉)的第一趟起泡的效果是 (73) 。
快速排序的第一趟结果是 (74) 。
二路归并排序的第一趟结果是 (75) 。
A. (B, F, G, J, A, D, I, E, H, C)
B. (B, F, G, J, A, E, D, I, C, H)
C. (A, B, D, C, E, E, I, J, G, H)
D. (C, B, D, A, E, F, I, G, J, H)