数据结构习题（含参考答案）.docx
数据结构习题（含参考答案）
一、单选题（共100题，每题1分，共100分）
1.for（i=0；im；i++）for（j=0；jt；j++）c［i][j］=0；for（i=0；im；i++）for（j=0；jt；j++）for（k=0；kn；k++）c［i][j］=c［i][j］+a［i][k］*b［k][j］；上列程序的时间复杂度为（）
A、O（m×n×t）
B、O（m+n×t）
C、O（m×t+n）
D、O（m+n+t）
正确答案：A
2.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。
A、rear=rear-next
B、front=front-next
C、rear=front-next
D、front=rear-next
正确答案：B
3.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为()
A、236
B、239
C、245
D、242
正确答案：B
4.有个顶点e条边的无向图G，它的邻接表中的表结点总数是()。
A、e
B、2n
C、n
D、2e
正确答案：D
5.下列四种排序中（）的空间复杂度最大。
A、快速排序
B、冒泡排序
C、堆
D、希尔排序
正确答案：A
6.数据结构的定义为(D，S)，其中D是()的集合。
A、算法
B、数据元素
C、数据操作
D、逻辑结构
正确答案：B
7.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是()
A、108
B、100
C、120
D、110
正确答案：A
8.深度为k的二叉树至多有()
A、2^(k-1)-1个结点
B、2^k-1个结点
C、2^k个结点
D、2^(k-1)个结点
正确答案：B
9.可以唯一地转化成一棵一般树的二叉树的特点是（）
A、根结点无左孩子
B、根结点有两个孩子
C、根结点没有孩子
D、根结点无右孩子
正确答案：D
10.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。
A、O(1)
B、O(n)
C、O(m+n)
D、O(m)
正确答案：D
11.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;n=i;i++)for(j=1;n=j;j++)x=x+1;
A、O(log2n)
B、O(n)
C、O(2^n)
D、O(n^2)
正确答案：D
12.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为()
A、(rear-length+m+1)％m
B、(rear-length+m)％m
C、(rear-length+m-1)％m
D、(rear-length)％m
正确答案：B
13.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加()。
A、2
B、1
C、0
D、-1
正确答案：A
14.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）
A、顺序表
B、双链表
C、单链表
D、单循环链表
正确答案：A
15.衡量查找算法效率的主要标准是（）。
A、元素的个数
B、所需的存储量
C、平均查找长度
D、算法难易程度
正确答案：C
16.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
A、栈
B、图
C、队列
D、树
正确答案：D
17.下列排序方法中，稳定的排序方法为（）
A、希尔排序
B、堆排序
C、快速排序
D、直接插入排序
正确答案：D
18.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为()
A、top=top
B、top=n-1
C、top=top+1
D、top=top-1
正确答案：C
19.由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。
A、n-1
B、n
C、n+1
D、2′n
正确答案：A
20.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
A、2i+1
B、2i
C、i/2
D、2i-1
正确答案：B
21.G是一个非连通无向图，共有28条边，则该图至少有()个顶点。
A、7
B、8
C、6
D、9
正确答案：D
22.采用线性链表表示一个向量时，要求占用的存储空间地址（）。
A、部分地址必须是连续的
B、一定是不连续的
C、必须是连续的
D、可连续可不连续
正确答案：D
23.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）
A、删除
B、排序
C、插入