数据库系统工程师：数据结构精选单选题练习

第1题. 下面程序段的执行次数为：
 for(i=0;i
   for(j=n;j
     state;  
A. n(n+2)/2
B .(n-1)(n+2)/2
C. n(n+1)/2
D. (n-1)(n+2)
第2题.  一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： 
A. 110
B .108
C. 100
D. 120
第3题.  一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是： 
A. edcba
B .decba
C. dceab
D. abcde
第4题.  判定一个栈ST（最多元素为m0）为空的条件是： 
A. ST->top<>0
B .ST->top＝0
C. ST->top<>m0
D. ST->top＝m0
第5题.  循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是： 
A. (rear-front+m)%m
B .read-front+1
C. read-front-1
D. read-front
第6题.  不带头结点的单链表head为空的判定条件是： 
A. head=NULL
B .head->next=NULL
C. head->next=head
D. head!=NULL
第7题.  在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行： 
A. s->next=p;p->next=s;
B .s->next=p->next;p->next=s;
C. s->next=p->next;p=s;
D. p->next=s;s->next=p;
第8题.  从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点？ 
A. n
B .n/2
C. (n-1)/2
D. (n+1)/2
第9题.  从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行： 
A. x=HS;HS=HS->next;
B .x=HS->data;
C. HS=HS->next;x=HS->data;
D. x=HS->data;HS=HS->next;
第10题.  在一个连队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时: 
A. r=f->next;
B .r=r->next;
C. f=f->next;
D. f=r->next;
第11题.  串是一种特殊的线性表，其特殊性体现在：
 A. 可以顺序存储
B .数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
第12题.  设有两个串p和q，求q在p中首次出现的位置的运算称作： 
A. 连接
B .模式匹配
C. 求子串
D. 求串长
第13题.  二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时下列哪一元素的起始地址相同。 
A. M[2][4]
B .M[3][4]
C. M[3][5]
D. M[4][4]
第14题.  数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为： 
A. SA+144
B .SA+180
C. SA+222
D. SA+225
第15题.  稀疏矩阵一般的压缩方法有两种，即： 
A. 二维数组和三维数组
B .三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
第16题.  递归函数f(n)=f(n-1)+n(n>1)的递归出口是： 
A. f(1)=0
B .f(1)=1
C. f(0)=1
D. f(n)=n
第17题.  将递归算法转换成对应的非递归算法时，通常需要使用： 
A. 栈
B .队列
C. 链表
D. 树
第18题.  广义表((a),a)的表头和表尾分别是： 
A. a , ((a))
B .(a) , (a)
C. b, (a)
D. ((a)) , a
第19题.  在线索化二叉树中，t所指结点没有左子树的充要条件是： 
A. t->left=NULL
B .t->ltag=1
C. t->ltag=1且t->left=NULL
D. 以上都不对
第20题.  设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： 
A. 2h
B .2h-1
C. 2h+1
D. h+1

第21题.  已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是： 
A. acbed
B .decab
C. deabc
D. cedba
第22题.  如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点： 
A. 前序
B .中序
C. 后序
D. 层次序
第23题.  按照二叉树的定义，具有3个结点的二叉树有几种？ 
A. 3
B .4
C. 5
D. 6
第24题.  树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ 
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
第25题.  在一非空二叉树的中序遍历序列中，根结点的右边 
A. 只有右子树上的所有结点
B .只有右子树上的部分结点
C. 只有左子树上的部分结点
D. 只有左子树上的所有结点
第26题.  树最适合用来表示： A. 有序数据元素
B .无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
第27题.  具有五层结点的二叉树平衡树至少有几个结点? 
A. 10
B .12
C. 15
D. 17
第28题.  设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是： 
A. n在m右方
B .n是m祖先
C. n在m左方
D. n是m子孙
第29题.  线索二叉树是一种什么结构? A. 逻辑
B .逻辑和存储
C. 物理
D. 线性
第30题.  在一个图中，所有顶点的度数之和等于所有边数的多少倍? 
A. 1/2
B .1
C. 2
D. 4
第31题.  一个有n个顶点的无向图最多有多少边？ A. n
B .n(n-1)
C. n(n-1)/2
D. 2n
第32题.  具有6个顶点的无向图至少应有多少条边才能确保是一个连通图？ 
A. 5
B .6
C. 7
D. 8
第33题.  采用邻接表存储的图的深度优先遍历算法类似于二叉树的： 
A. 先序遍历
B .中序遍历
C. 后序遍历
D. 按层遍历
第34题.  判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用： 
A. 求关键路径的方法
B .求最短路径的Dijkstra方法
C. 宽度优先遍历算法
D. 深度优先遍历算法
第35题.  顺序查找法适合于存储结构为__的线性表。 A. 散列存储
B .顺序存储或链接存储
C. 压缩存储
D. 索引存储
第36题.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为： 
A. n
B .n/2
C. (n+1)/2
D. (n-1)/2
第37题.  有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，几次比较后查找成功？
A. 1
B .2
C. 4
D. 8
第38题.  设哈希表长m＝14，哈希函数H（key）＝key％11。表中已有4个结点：
    addr(15)=4
    addr(38)=5
    addr(61)=6
    addr(84)=7
 其余地址为空
 如果用二次探测再散列处理冲突，关键字为49的结点的地址是： 
A. 8
B .3
C. 5
D. 9
第39题.  有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为： 
A. 35/12
B .37/12
C. 39/12
D. 43/12
第40题.  采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分__个结点最佳。 
A. 10
B .25
C. 6
D. 625
第41题.  有组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为： 
A. 79，46，56，38，40，80
B .84，79，56，38，40，46
C. 84，79，56，46，40，38
D. 84，56，79，40，46，38
第42题.  下列程序段的时间复杂度为：
    i=1; k=0; n=100;
    do {
           k=k+10*i;
           i=i++;
          } while (i!=n); 
A. O(1)
B .O(n)
C. O(i×n)
D. O(i)
第43题.  设关键字序列为（3，7，6，9，7，1，4，5，20），堆其进行排序的最小交换次数是： 
A. 6
B .7
C. 8
D. 20
第44题.  索引无序文件是指：  
A. 主文件无序，索引表有序
B .主文件有序，索引表无序
C. 主文件有序，索引表有序
D. 主文件无序，索引表有序
第45题.  倒排文件的主要优点是： 
A. 便于进行插入和删除运算
B .便于进行文件的合并
C. 能大大提高次关键字的查找速度
D. 能大大节省存储空间
第46题.  外排序是指：
A. 在外存上进行的排序方法
B .不需要使用内存的排序方法
C. 数据里很大，需要人工干预的排序方法
D. 排序前后数据在外存，排序时数据调入内存的排序方法
第47题.  在内部排序中，排序不稳定的有： 
A. 插入排序
B .冒泡排序
C. 快速排序
D. 归并排序
第48题.  以二叉链表作为二叉树存储结构，在具有n结点的二叉链表中（n>0），空链域的个数为： 
A. 2n-1
B .n-1
C. n+1
D. 2n+1
第49题.  采用链结构存储线性表时，其地址： 
A. 必须是连续的
B .连续不连续都可以
C. 部分地址必须是连续的
D. 必须是不连续的
第50题.  串的长度是： 
A. 串中不同字符的个数
B .串中不同字母的个数
C. 串中所含字符的个数且字符个数大于0
D. 串中所含字符的个数
第51题.  若数组S[1…n]作为两个栈S1和S2的存储空间，对任何一个栈，只有当[1…n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是： 
A. S1的栈底位置为0，S2的栈底位置为n＋1
B .S1的栈底位置为0，S2的栈底位置为n/2
C. S1的栈底位置为1，S2的栈底位置为n
D. S1的栈底位置为1，S2的栈底位置为1