微信小程序东北林业大学2020—2021学年第2学期
《数据结构》考试试卷（A卷）
考试范围：《数据结构》；满分：100分；考试时间：120分钟
院/系：__________专业：__________姓名：__________ 考号：__________
| 题号 | 一 | 二 | 三 | 四 | 总分 |
| 得分 |
注意事项：
1．答题前填写好自己的姓名、班级、考号等信息
2．请将答案正确填写在答题卡上
第I卷（选择题）
|
一、单项选择题：1～20小题。下列每题给出的选项中，只有一个选项是符合题目要求的。请在答题卡上将所选项的字母涂黑。 |
1．将10个元素散列到100000个单元的哈希表中，（ ）产生冲突?
A．一定会
B．一定不会
C．仍可能会
D．可能不会
2．下列关于IP路由器功能的描述中，正确的是（ ）。
Ⅰ．运行路由协议，设置路由表；
Ⅱ．监测到拥塞时，合理丢弃IP分组；
Ⅲ．对收到的IP分组头进行差错校验，确保传输的IP分组不丢失；
Ⅳ．根据收到的IP分组的目的IP地址，将其转发到合适的输出线路上。
A．仅Ⅲ、Ⅳ
B．仅Ⅰ、Ⅱ、Ⅲ
C．仅Ⅰ、Ⅱ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ、Ⅳ
3．下面程序段中，执行S语句的次数为（ ）。
for(int i=1；i＜=n；i＋＋)
for(int j=1；j＜=i；j＋＋)
S；
A．n2
B．n2/2
C．n(n＋1)
D．n(n＋1)/2
4．数据的存储结构是指（ ）。
A．数组类型
B．指针类型
C．数据之间的逻辑关系
D．数据之间的物理关系
5．在单链表中，指针p指向结点A，若要删除A之后的结点（存在），则指针的操作方式为（ ）。
A．p－>next＝p－>next－>next
B．p＝p－>next
C．p＝p－>next－>next
D．p－>next＝p
6．循环队列用数组A[0．．．m—1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（ ）。
A．（rear－front＋m）mod m
B．rear－front＋1
C．rear－front－1
D．rear－front
7．已知10个数据元素为（54，28，16，34，73，62，95，60，23，43），按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为（ ）。
A．2
B．3
C．4
D．5
8．按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A．3
B．4
C．5
D．6
9．设有向图G＝（V，E），顶点集V＝v0，v1，v2，v3}，边集E＝<v0, v1>，<v0, v2>，<v0, v3>，<v1, v3>}，若从顶点v0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（ ）。
A．2
B．3
C．4
D．5
10．串′ababaaababaa′的next数组值为（ ）。
A．01234567899
B．012121111212
C．011234223456
D．0123012322345
11．一个UDP用户数据报的数据字段为8192字节。在链路层要使用以太网来传输，那么应该分成（ ）IP数据片。
A．3个
B．4个
C．5个
D．6个
12．已知一个线性表为（38，25，74，63，52，48），假定采用H（K）＝K mod 7计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为（ ）；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为（ ）。
A．1.5，1
B．1.7，3/2
C．2，4/3
D．2.3，7/6
13．下列叙述正确的个数是（ ）。
（1）m＝2的平衡m路查找树是AVL树
（2）m＝3的平衡m路查找树是2-3树
（3）m＝2的平衡m路查找树的叶结点不一定在同一层
（4）m阶B-树的叶结点必须在同一层
（5）m阶B-树是平衡m路查找树
（6）平衡m路查找树不一定是B-树
A．3
B．4
C．5
D．6
14．有n个记录的文件，若关键字位数为d，基数为r，则基数排序共需进行（ ）遍分配与收集。
A．n
B．r
C．d
D．d＋r
15．用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1，6）进行排序，关键字比较次数（ ）。
A．相同
B．前者大于后者
C．前者小于后者
D．无法比较
16．若对序列（tang，deng，an，wang，shi，bai，fang，liu）采用选择排序法按字典顺序进行排序，下面给出的四个序列中，（ ）是第三趟的结果。
A．an，bai，deng，wang，tang，fang，shi，hu
B．an，bai，deng，wang，shi，tang，fang，liu
C．an，bai，deng，wang，shi，fang，tang，liu
D．an，bai，deng，wang，shi，liu，tang，fang
17．信道速率为4kbps，采用停止-等待协议。传播时延t＝20ms，确认帧长度和处理时间均可忽略。问帧长（ ）才能使信道的利用率达到至少50%。
A．40bit
B．80bit
C．160bit
D．320bit
18．下面关于算法说法正确的是（ ）。
A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的
C．算法的可行性是指指令不能有二义性
D．以上几个都是错误的
19．在DNS的递归查询中，由（ ）给客户端返回地址。
A．最开始连接的服务器
B．最后连接的服务器
C．目的地址所在的服务器
D．不确定
20．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。
A．1／2
B．2
C．1
D．4
|
二、判断题：21～28小题。下列每题给出的选项中，至少有两个选项是符合题目要求的。请在答题卡上将所选项的字母涂黑。 |
21．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
22．强连通分量是无向图的极大强连通子图。( )
23．若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。（ ）
24．折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树。（ ）
25．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
26．静态链表就是一直不发生变化的链表。（ ）
27．在链队列中，即使不设置尾指针也能进行入队操作。（ ）
28．文件系统采用索引结构是为了节省存储空间。（ ）
第II卷（非选择题）
|
三、编写算法题：29～30小题。请将答案写在答题纸指定位置上。 |
29．对于下列for循环语句，请将其改写为功能完全相同的while循环语句。
int i,j,count=0;
for(i=0;i<100;i++)
for(j=100;j>=i;j-=2)
count+=j-i;
}
}
30．有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。
|
四、综合应用题：31～33小题。请将答案写在答题纸指定位置上。 |
31．已知有5个顶点的图G如图所示。
请回答下列问题。
（1）写出图G的邻接矩阵A（行、列下标从0开始）。
（2）求A2，矩阵A2中位于0行3列元素值的含义是什么？
（3）若已知具有n（n≥2）个顶点的邻接矩阵为B，则Bm（2≤m≤n）中非零元素的含义是什么？
32．下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
33．设一个散列表含13个表项（hashsize=13），其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键码10，100，32，45，58，126，3，29，200，400，0}散列到表中。
（1）散列函数采用除留余数法，用％hashsize（取余运算）将各关键码映象到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。
（2）散列函数采用先将关键码各位数字折叠相加，再用％hashsize将相加的结果映象到表中的办法请指出每一个产生冲突的关键字码可能产生多少次冲突。
请先 ！