数据结构(C#语言版)笔试试题及答案
一、选择题(每小题2分，***24分)
1.由计算机识别、存储和处理的对象统称为(A)。
A.数据b .数据元素
C.数据结构d .数据类型
2.堆栈和队列都是(A)
A.受限访问位置的线性结构b .顺序存储的线性结构
C.链式存储的线性结构d .受限访问位置的非线性结构
3.与顺序堆栈相比，链式堆栈具有明显的优势(D)。
A.插入操作更方便。b .删除操作更方便。
C.不会有下溢。d .不会有溢出。
4.两种不同存储结构的字符串可以分别缩写为(B)。
A.主串和子串b .顺序串和链串
C.目标字符串和模式字符串d .变量字符串和常量字符串
5.向量的第一个元素的存储地址是100，每个元素的长度是2，所以第五个元素的地址是b。
A.110
C.100
6.字符串是一种特殊的线性表，其特殊性体现在:b
A.它可以顺序存储。数据元素是一个字符。
C.链接存储数据元素可以是多个字符。
7.假设一棵高度为h的二叉树上只有度为0和度为2的节点，那么这样一棵二叉树包含的节点数至少为:c。
A.2h B .2h-1
C.2h+1 D. h+1
www.mscto.com软件开发网络
8.树的基本遍历策略可以分为第一根遍历和第二根遍历；二叉树的基本遍历策略可以分为前遍历、中遍历和后遍历。在这里，我们把一棵树转化成的二叉树叫做这棵树对应的二叉树。以下哪个结论是正确的？A
A.树的先行遍历序列与其对应的二叉树相同。
b .树的后根的遍历顺序与其对应的二叉树的后序的遍历顺序相同。
C.树的第一个根的遍历顺序与其对应的二叉树的中间顺序的遍历顺序相同。
D.以上都不是真的
9.n个顶点的无向图最多有几条边？C
A.注意:n(n-1)
C.n(n-1)/2 D. 2n
10.在一个图中，所有顶点之和等于所有边的多少倍？C
A.1/2 B
C.2 D. 4
11.在二叉排序树中插入新节点时，如果树中没有与待插入节点关键字相同的节点，且新节点的关键字小于根节点的关键字，则新节点将成为(a)。
A.左子树的叶节点b .左子树的分支节点
C.右侧子树的叶节点d .右侧子树的分支节点
www.mscto.com软件开发网络
12.对于哈希函数H(key)=key%13，称为同义词的关键字是(d)。
35和41
C.15和44 D.25和51
2.已知二叉树的前序遍历结果为A，B，D，E，G，C，F，H，I，J，前序遍历结果为D，B，G，E，A，H，F，I，J，C..请画出二进制的具体结构。(注意具体步骤)(10分)
原理见教材128页。
3.有一个图表如下。请写下从顶点c0开始的深度优先和宽度优先遍历的结果。(10分)
深度第一；C0-C1-C3-C4-C5-C2
宽度优先:C0-C1-C2-C3-C4-C5
四、有如下图，根据Kruskal算法得到最小生成树。要求写出完整的步骤。(10分)
原理见教材第250页。
5.给出线性表(12，23，45，66，76，88，93，103，166)，试着把二分搜索法的过程写在上面。并写出二分搜索法的算法。(20分)
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
流程:
mid=(0+8)/2=4
高=3，低=0，中=1
高=0，低=0中=0(找到12)
高=8，低=5，中=6(找到93个)
高=8，低=7，中=7
高=8低=8中=8
算法:见教材第84页。
六、知识列表的节点结构如下
下一个数据
下面的算法只是简单的对带有前导节点的单链表L进行选择和排序，使L中的元素从小到大排列。
请在空白处填入适当的内容，使之成为一个完整的算法。(算法的基本思路和执行过程可以用文字说明，10分)
void SelectSort(LinkedList L)
{
LinkedList p，q，min
数据类型rcd
p =(1)；
而(p！=NULL) {
min = p；
q = p->；接下来；
而(q！=NULL){
如果((2))min = q；
q = q-& gt；接下来；
}
如果((3) ){
rcd = p-& gt；数据；
p->；data = min-& gt；数据；
min->；数据= rcd
}
(4) ;
}
}
这个问题不会。嘿嘿。。。。
7.一个完整算法的基本性质是什么？分别简要说明每个属性的含义。(5分)
输入:
四个基本属性:1。输入:有零个或多个外部提供的量作为算法的输入。
2.输出:算法至少生成一个量作为输出。
3.确定性:构成算法的每一条指令都是清晰明确的。
4.:有限性:算法中每条指令执行的次数是有限的，执行每条指令的时间也是有限的。
8.队列“假溢出”是什么现象？怎么解决？(5分)
队列的假溢出现象是指在指数群实现的顺序队列中，队列尾指针已经达到数组表的上界而溢出，但在队列头指针之前还有一些空间空闲的现象。解决方案之一是使用循环队列技术来连接数组空间的末端。
9.解释和比较文件的各种物理结构。(6分)