数据结构有关练习题

2013年12月26日 作者： 来源：

第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