数据结构面试题及答案

① 数据结构笔试题

本文出自数据结构十套笔试题之第一套，本站为原创作品，转载请注明出处，谢谢！

• 一、选择题

• 1、栈和队列的共同特点是( )。
  A.只允许在端点处插入和删除元素
  B.都是先进后出
  C.都是先进先出
  D.没有共同点

参考答案是：

归并

② 面试常问的数据库问题及答案

目前在职场中很难找到非常合格的数据库开发人员。有人说:“SQL开发是一门语言，它很容易学，但是很难掌握。”
在面试应聘的SQL Server数据库开发人员时，我运用了一套标准的基准技术问题。下面这些问题是我觉得能够真正有助于淘汰不合格应聘者的问题。它们按照从易到难的顺序排列。当你问到关于主键和外键的问题时，后面的问题都十分有难度，因为答案可能会更难解释和说明，尤其是在面试的情形下。
你能向我简要叙述一下SQL Server 2000中使用的一些数据库对象吗?
你希望听到的答案包括这样一些对象:表格、视图、用户定义的函数，以及存储过程;如果他们还能够提到像触发器这样的对象就更好了。如果应聘者不能回答这个基本的问题，那么这不是一个好兆头。
NULL是什么意思?
NULL(空)这个值是数据库世界里一个非常难缠的东西，所以有不少应聘者会在这个问题上跌跟头您也不要觉得意外。
NULL这个值表示UNKNOWN(未知):它不表示“”(空字符串)。假设您的SQL Server数据库里有ANSI_NULLS，当然在默认情况下会有，对NULL这个值的任何比较都会生产一个NULL值。您不能把任何值与一个 UNKNOWN值进行比较，并在逻辑上希望获得一个答案。您必须使用IS NULL操作符。

什么是索引?SQL Server 2000里有什么类型的索引?
任何有经验的数据库开发人员都应该能够很轻易地回答这个问题。一些经验不太多的开发人员能够回答这个问题，但是有些地方会说不清楚。
简单地说，索引是一个数据结构，用来快速访问数据库表格或者视图里的数据。在SQL Server里，它们有两种形式:聚集索引和非聚集索引。聚集索引在索引的叶级保存数据。这意味着不论聚集索引里有表格的哪个(或哪些)字段，这些字段都会按顺序被保存在表格。由于存在这种排序，所以每个表格只会有一个聚集索引。非聚集索引在索引的叶级有一个行标识符。这个行标识符是一个指向磁盘上数据的指针。它允许每个表格有多个非聚集索引。
什么是主键?什么是外键?
主键是表格里的(一个或多个)字段，只用来定义表格里的行;主键里的值总是唯一的。外键是一个用来建立两个表格之间关系的约束。这种关系一般都涉及一个表格里的主键字段与另外一个表格(尽管可能是同一个表格)里的一系列相连的字段。那么这些相连的字段就是外键。
什么是触发器?SQL Server 2000有什么不同类型的触发器?
让未来的数据库开发人员知道可用的触发器类型以及如何实现它们是非常有益的

触发器是一种专用类型的存储过程，它被捆绑到SQL Server 2000的表格或者视图上。在SQL Server 2000里，有INSTEAD-OF和AFTER两种触发器。INSTEAD-OF触发器是替代数据操控语言(Data Manipulation Language，DML)语句对表格执行语句的存储过程。例如，如果我有一个用于TableA的INSTEAD-OF-UPDATE触发器，同时对这个表格执行一个更新语句，那么INSTEAD-OF-UPDATE触发器里的代码会执行，而不是我执行的更新语句则不会执行操作。
AFTER触发器要在DML语句在数据库里使用之后才执行。这些类型的触发器对于监视发生在数据库表格里的数据变化十分好用。
您如何确一个带有名为Fld1字段的TableB表格里只具有Fld1字段里的那些值，而这些值同时在名为TableA的表格的Fld1字段里?
这个与关系相关的问题有两个可能的答案。第一个答案(而且是您希望听到的答案)是使用外键限制。外键限制用来维护引用的完整性。它被用来确保表格里的字段只保存有已经在不同的(或者相同的)表格里的另一个字段里定义了的值。这个字段就是候选键(通常是另外一个表格的主键)。
另外一种答案是触发器。触发器可以被用来保证以另外一种方式实现与限制相同的作用，但是它非常难设置与维护，而且性能一般都很糟糕。由于这个原因，微软建议开发人员使用外键限制而不是触发器来维护引用的完整性。
对一个投入使用的在线事务处理表格有过多索引需要有什么样的性能考虑?
你正在寻找进行与数据操控有关的应聘人员。对一个表格的索引越多，数据库引擎用来更新、插入或者删除数据所需要的时间就越多，因为在数据操控发生的时候索引也必须要维护。
你可以用什么来确保表格里的字段只接受特定范围里的值?
这个问题可以用多种方式来回答，但是只有一个答案是“好”答案。您希望听到的回答是Check限制，它在数据库表格里被定义，用来限制输入该列的值。
触发器也可以被用来限制数据库表格里的字段能够接受的值，但是这种办法要求触发器在表格里被定义，这可能会在某些情况下影响到性能。因此，微软建议使用Check限制而不是其他的方式来限制域的完整性。
<b?返回参数和output参数之间的区别是什么?>如果应聘者能够正确地回答这个问题，那么他的机会就非常大了，因为这表明他们具有使用存储过程的经验。
返回参数总是由存储过程返回，它用来表示存储过程是成功还是失败。返回参数总是INT数据类型。
OUTPUT参数明确要求由开发人员来指定，它可以返回其他类型的数据，例如字符型和数值型的值。(可以用作输出参数的数据类型是有一些限制的。)您可以在一个存储过程里使用多个OUTPUT参数，而您只能够使用一个返回参数。
什么是相关子查询?如何使用这些查询?
经验更加丰富的开发人员将能够准确地描述这种类型的查询。
相关子查询是一种包含子查询的特殊类型的查询。查询里包含的子查询会真正请求外部查询的值，从而形成一个类似于循环的状况。</b?返回参数和output参数之间的区别是什么?>

③ 数据结构（C#语言版）笔试试题与答案

《数据结构》期末考试试卷（ A ）

一、 选择题（每小题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，则第5个元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一种特殊的线性表，其特殊性体现在：B
A.可以顺序存储 B .数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
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 B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
软件开发网 www.mscto.com
12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）
原理见课本128页

三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)
深度优先；C0-C1-C3-C4-C5-C2
宽度优先：C0-C1-C2-C3-C4-C5
四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）
原理见课本250页

五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，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
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
算法：见课本84页上

六、知单链表的结点结构为
Data next
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本题不会。嘿嘿。。。。
七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)
输入：
四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入
2：输出：算法产生至少一个量作为输出
3.：确定性：组成算法的每条指令是清晰的，无歧异的。
4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

八、何谓队列的"假溢"现象？如何解决？（5分）
队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。

九、说明并比较文件的各种物理结构。（6分）