数据结构题库及参考答案.docx
数据结构题库及参考答案
一、单选题（共100题，每题1分，共100分）
1.设有n个结点的二叉树上只有度为0和度为2的结点，则此二叉树中叶子结点数()。
A、n/2
B、（n+1)/2
C、不能确定
D、(n-1)/2
正确答案：B
2.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。
A、front-next=s；front=s；
B、s-next=front；front=s；
C、rear-next=s；rear=s；
D、s-next=rear；rear=s；
正确答案：C
3.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A、7
B、4
C、6
D、5
正确答案：C
4.采用顺序存储结构存储的线性表，其首地址为100，每个元素的长度为2，则第5个元素的地址为()。
A、120
B、108
C、110
D、100
正确答案：B
5.下列关于线性表的叙述中，不正确的是()
A、线性表的每一个结点有且仅有一个前趋和一个后继
B、线性表可以为空表
C、线性表结点间的逻辑关系是1:1的联系
D、线性表是n个结点的有穷序列
正确答案：A
6.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
A、n，2e
B、e，n
C、n，e
D、2n，e
正确答案：A
7.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。
A、p→link=s;s→link=q;
B、s→link=p→link;p→link=s;
C、p→link=s→link;s→link=p;
D、q→link=s;s→link=p;
正确答案：D
8.图的深度、广度优先遍历算法分别类似于二叉树的()。
A、先序遍历和层序遍历
B、后序遍历和中序遍历
C、层序遍历和先序遍历
D、先序遍历和中序遍历
正确答案：A
9.若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。
A、O(n2)
B、O(1)
C、O(n)
D、O(log2n)
正确答案：C
10.下面关于生成树的描述中，不正确的是()
A、生成树是树的一种表现形式
B、生成树一定是连通的
C、生成树一定不含有环
D、若生成树顶点个数为n，则其边数一定为n-1
正确答案：A
11.连通图G中有n个顶点，G的生成树是()的连通子图。
A、包含G的所有顶点
B、不必包含G的所有顶点
C、包含G的所有边
D、包含G的所有顶点和所有边
正确答案：A
12.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
A、队列
B、图
C、树
D、栈
正确答案：C
13.在索引顺序表中查找一个元素，可用的且最快的方法是（）。
A、用顺序查找方法确定元素所在块，再用二分查找在相应块中查找
B、用顺序查找方法确定元素所在块，再用顺序查找在相应块中查找
C、用二分查找方法确定元素所在块，再用顺序查找在相应块中查找
D、用二分查找方法确定元素所在块，再用二分查找在相应块中查找
正确答案：C
14.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。
A、e
B、n
C、2n
D、2e
正确答案：B
15.设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。
A、2n-1
B、n-1
C、n
D、2n
正确答案：B
16.具有4个顶点的无向完全图有()条边。
A、16
B、6
C、20
D、12
正确答案：B
17.设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）
A、1
B、2
C、4
D、3
正确答案：A
18.高度为h的完全二叉树中，结点数最多为（）
A、2^h
B、2^h+1
C、2^h-1
D、2^(h-1)
正确答案：C
19.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）
A、n-1
B、2n
C、n
D、n+1
正确答案：A
20.有8个结点的无向连通图最少有（）条边。
A、8
B、6
C、5
D、7
正确答案：D
21.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。
A、入边数
B、出边数
C、度数减1
D、度数
正确答案：B
22.栈和队列共同具有的特点是（）
A、都是先进后出
B、都是先进先出
C、只允许在端点进行操作运算
D、既能先进