数据结构试题
一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号
内。错选、多选或未选均无分。
)
1.数据结构是(
A.一种数据类型
B.数据的存储结构
C.一组性质相同的数据元素的集合
D.相互之间存在一种或多种特定关系的数据元素的集合
2.算法分析的目的是(
A.辨别数据结构的合理性
B.评价算法的效率
C.研究算法中输入与输出的关系
D.鉴别算法的可读性
3.在线性表的下列运算中,不.改变数据元素之间结构关系的运算是(
)
)
B.删除
D.定位
A.插入
C.排序
4.若进栈序列为 1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为(
A.3,2,6,1,4,5
C.1,2,5,3,4,6
5.设串 sl=″Data Structures with Java″,s2=″it″,则子串定位函数 index(s1,s2)的值为()
A.15
C.17
6.二维数组 A[8][9]按行优先顺序存储,若数组元素 A[2][3]的存储地址为 1087,A[4][7]的存储地址为 1153,
B.3,4,2,1,6,5
D.5,6,4,2,3,1
B.16
D.18
)
则数组元素 A[6][7]的存储地址为(
)
B.1209
D.1213
A.1207
C.1211
7.在按层次遍历二叉树的算法中,需要借助的辅助数据结构是(
A.队列
C.线性表
8.在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系(
A.不一定相同
C.都不相同
B.都相同
D.互为逆序
B.栈
D.有序表
)
)
)
)
B.前序遍历算法
D.后序遍历算法
9.若采用孩子兄弟链表作为树的存储结构,则树的后序遍历应采用二叉树的(
A.层次遍历算法
C.中序遍历算法
10.若用邻接矩阵表示一个有向图,则其中每一列包含的″1″的个数为(
A.图中每个顶点的入度
C.图中弧的条数
11.图的邻接矩阵表示法适用于表示(
A.无向图
C.稠密图
12.在对 n 个关键字进行直接选择排序的过程中,每一趟都要从无序区选出最小关键字元素,则在进行第 i
B.图中每个顶点的出度
D.图中连通分量的数目
B.有向图
D.稀疏图
)
趟排序之前,无序区中关键字元素的个数为(
)
B.i+1
D.n-i+1
A.i
C.n-i
13.下列排序算法中,其时间复杂度和记录的初始排列无关的是(
A.插入排序
C.快速排序
14.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t),则在二分查找关键字 b 的过程中,先后进行比较的关键字
B.堆排序
D.冒泡排序
)
依次为(
)
B.f,d,b
D.g,d,b
A.f,c,b
C.g,c,b
15.若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录,则查询条件为(
A.(性别=“男”)OR(年龄> 60)OR(性别=“女”)OR(年龄>55)
B.(性别=“男”)OR(年龄> 60)AND(性别=“女”)OR(年龄>55)
C.(性别=“男”)AND(年龄> 60)OR(性别=“女”)AND(年龄>55)
D.(性别=“男”)AND(年龄> 60)AND(性别=“女”)AND(年龄>55)
二、填空题(本大题共 10 小题,每小题 2 分,共 20 分)
请在每小题的空格中填上正确答案。错填、不填均无分。
)
16.称算法的时间复杂度为 O(f(n)),其含义是指算法的执行时间和_______的数量级相同。
17.在一个长度为 n 的单链表 L 中,删除链表中*p 的前驱结点的时间复杂度为_________。
18.假设为循环队列分配的向量空间为 Q[20],若队列的长度和队头指针值分别为 13 和 17,则当前尾指针的
值为______。
19.设 s=″I AM A ATHLETE″,t=″GOOD″,则执行下列串操作序列之后得到的 sub1 为________。
substr (sub1,s,5,2);substr(sub2,s,6,8); strcpy(t1,t);
strcat(t1,sub2); strcat(sub1,t1);
20.广义表的深度是指_______。
21.一棵含 999 个结点的完全二叉树的深度为_______。
22.含 n 个顶点的无向连通图中至少含有______条边。
23.对表长为 9000 的索引顺序表进行分块查找,假设每一块的长度均为 15,且以顺序查找确定块,则在各
记录的查找概率均相等的情况下,其查找成功的平均查找长度为_____。
24.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序,则
得到的结果为______。
25.ISAM 文件由主索引、______、______和主文件组成。
三、解答题(本大题共 4 小题,每小题 5 分,共 20 分)
26.某广义表的表头和表尾均为(a,(b,c)),画出该广义表的图形表示。
27.已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。
(1)画出该二叉树;
(2)画出与(1)求得的二叉树对应的森林。
(1)
(2)
28.已知带权图的邻接表如下所示,其中边表结点的结构为:
依此邻接表从顶点 C 出发进行深度优先遍历。
(1)画出由此得到的深度优先生成树;
(2)写出遍历过程中得到的从顶点 C 到其它各顶点的带权路径及其长度。
(1)
(2)
29.从空树起,依次插入关键字 37,50,42,18,48,12,56,30,23,构造一棵二叉排序树。
(1)画出该二叉排序树;
(2)画出从(1)所得树中删除关键字为 37 的结点之后的二叉排序树。
(1)
(2)
四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分)
30.已知用有序链表存储整数集合的元素。阅读算法 f30,并回答下列问题:
(1)写出执行 f30(a,b)的返回值,其中 a 和 b 分别为指向存储集合{2,4,5,7,9,12}和{2,4,5,7,
9}的链表的头指针;
(2)简述算法 f30 的功能;
(3)写出算法 f30 的时间复杂度。
int f30(LinkList ha,LinkList hb)
{
//LinkList 是带有头结点的单链表
//ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针
LinkList pa,pb;
pa=ha->next;
pb=hb->next;
while(pa && pb && pa->data==pb->data)
{
pa=pa->next;
pb=pb->next;
}
if(pa==NULL && pb==NULL) return 1;
else return 0;
}
(1)
(2)
(3)
31.已知稀疏矩阵采用带行表的三元组表表示,其形式说明如下:
#define MaxRow 100
//稀疏矩阵的最大行数
typedef struct {
int
i,j,v;
}TriTupleNode;
typedef struct{
//行号、列号、元素值
TriTupleNode data[MaxSize];
int RowTab[MaxRow+1];
int m,n,t;
//行表
//矩阵的行数、列数和非零元个数
}RTriTupleTable;
下列算法 f31 的功能是,以行优先的顺序输入稀疏矩阵的非零元(行号、列号、元素值),建立稀疏矩阵
的带行表的三元组表存储结构。请在空缺处填入合适内容,使其成为一个完整的算法。(注:矩阵的行、
列下标均从 1 起计)
void f31(RTriTupleTable *R)
{ int i,k;
scanf(″%d %d %d″,&R->m,&R->n,&R->t);
//k 指示当前输入的非零元的行号
①
;i++)
②
;
,
③
,&R->data[i].v);
R->RowTab[1]=0;
k=1;
for(i=0;
{
scanf(″%d %d %d″,
while(kdata[i].i)
{
④
R->RowTab[k]=i;
}
}
}
①
②
③
④
32.已知二叉树的存储结构为二叉链表,其类型定义如下:
typedef struct NodeType {
DataType data;
struct NodeType *lchild,*rchild;
}BinTNode,*BinTree;
阅读算法 F32,并回答下列问题:
(1)对于如图所示的二叉树,画出执行算法 f32 的结果;
(2)简述算法 f32 的功能。
BinTree f32(BinTree bt1)
{
BinTree bt2;
if(bt1==NULL)
bt2=NULL;
else {
bt2=(BinTNode *)malloc(sizeof(BinTNode));
bt2->data=bt1->data;
bt2->rchild=f32(bt1->lchild);
bt2->lchild=f32(bt1->rchild);
}
return bt2;
}
(1)
(2)
33.假设有向图采用邻接表表示法,其定义如下:
typedef
struct {
VertexNode
int
n,e;
} ALGraph;
adjlist[MaxVertexNum];
//图的当前顶点数和弧数
//邻接表类型
其中顶点表结点 VertexNode 结构为:
vertex
firstedge
边表结点 EdgeNode 结构为:
adjvex
next
下列算法 f33 的功能是,对以邻接表表示的有向图进行拓扑排序。
(1)阅读算法 f33,并在空缺处填入
合适的内容,使其成为一个完
整的算法;
(2)对于如图所示的邻接表,将执
行算法 f33 后的 topo[ ]结果填入
给定的数组中。
void
f33(ALGraph G,
int topo [ ]){
int i,j,k,count=0;
int indegree[MaxVertexNum];
EdgeNode *p;
Queue Q;
FindIndegree(G, indegree);
InitQueue(&Q);
for(i=0;inext){
k=p->adjvex;
if(!(--indegree[k]))
②
;
}
}
if(count