上海理工大学856真题
软件工程实验室是我系为软件工程、软件协同设计和软件项目管理等课程建立的专业实验室。该实验室提供Microsoft Project Standard 2007(一种用于软件工程的高级项目管理工具)和SPARX Enterprise Architect 7.5 for Windows。实验室提供的工具和平台帮助学生掌握理论课程的理论和方法，熟悉并应用软件开发过程管理、团队合作、设计和建模的先进工具。让学生走上工作岗位后能够快速适应软件企业的开发设计环境。
希望能帮到你附带的模拟试卷，祝你高中考得好！
数据结构模拟试卷
1.选择题(从每题四个备选答案中选择一个正确答案，并在题后填入数字，每题2分，***10分)。
1.一个栈的输入序列是1，2，3，4。下面哪个序列不能是这个栈的输出序列？( )
A.1,3,2,4
B.2,3,4,1
C.4,3,1,2
D.3,4,2,1
2.以下哪种排序方法与记录的初始排列无关？( )
A.直接插入排序
B.气泡分类
C.快速分类
D.直接选择排序
3.合并和排序N个记录文件的总时间开销为
A.O(nlog2n)
B.氧气(氮气)
C.O(log2n)
D.O(n)
4.如果一棵二叉树有10个度为2的节点，则该二叉树的度为0的节点数为()。
A.9
B.11
C.12
D.不确定
5.下列关于B树和B+树的说法不正确。
A.B树和B+树都是平衡多叉树。
B.B树和B+树都是可以用于文件的索引结构。
C. B树和B+树都能有效支持顺序检索。
D. B树和B+树都能有效支持随机检索。
二、填空(每空2分，***20分)
1.从逻辑结构上看，线性表比较典型，树比较典型。
2.二维数组A的存储地址为，元素A的存储地址为。
3.如果一棵有n个节点的完全二叉树的所有节点按层次顺序从1到n编号，那么当I小于n时，节点I的右兄弟是一个节点，否则节点I没有右兄弟。
4.求具有最小加权外部路径长度的扩展二叉树的算法称为算法。在堆排序中构建堆的方法称为。
在5.6阶B树中，每个节点最多包含一个键码，除了根节点和叶节点，每个节点至少包含一个键码。
三。简答题(每道小题6分，***18分)
1.请简述哈希函数在哈希存储中的作用，并举例说明哈希函数。
2.请简述哈希存储中处理碰撞(冲突)的两种基本方法。
3.请简要描述负载系数的定义。为什么加载因子是hash方法存储的重要参数？
四、解决以下问题(每道小题6分，***30分)
1.设待排序文件的键码为(512，275，908，677，503，765，612，897，154，170)，以第一个元素为划分元素进行快速排序。
请画出下列树对应的二叉树。
3.从一个空的二叉排序树开始，依次插入下一个键码值:25，13，15，31，7，20，37。请在所有插入后画出二叉排序树。
4.请用下面的加权图画一个最小生成树。
5.对于下面的稀疏矩阵
1)画出它的三重存储表示。
2)画出它的行列存储表示法(交叉链表法)。
五、算法问题(6分)
有一个线性表以链接的方式存储。表中的每个节点包括两个指针，其节点用PASCAL描述如下:
类型指针=↑节点；
节点=记录
信息:数据类型；
link1，link2:指针
结束；
其中link1是指向该节点下一个节点的指针，link2是指向该节点上一个节点的指针，如图所示。
P和Q都是指针类型的变量。现在表中Q指向的新节点要插在P指向的节点前面(注意:P不是指链表中的第一个节点)。请用PASCAL语句写出插入的关键步骤。部里要求写完整的算法，只要求用几句话写出关键步骤。)
六、填空和分析算法(***16分)
下面是用PASCAL语言写的二进制插入排序算法，用整数排序代码对线性表进行升序排序。
类型节点=记录
key:整数；
信息:数据类型
结束；
list=ARRAY[1..节点的max];
过程binary sort(VAR R:list；n:整数)；
VAR temp:节点；
low，m，high，I，j:整数；
开始
对于I:=2到n DO
开始
temp:= R[I]；
低:= 1；高:= I-1；
当①做
开始
m :=(低+高)DIV 2；
如果②
然后高:=m-1
否则③
结束；
FOR j := i-1 DOWNTO ④ DO
R[j+1]:= R[j]；
⑤
结束；
结束；
1.请在下面的算法空白处写下应该填写的正确内容。(10分)
①
②
③
④
⑤
2.假设要排序的记录数为n=7。当排序码初始顺序分别为(15，25，35，45，55，65，75)和(75，65，55，45，35，25，15)时，请说明。(假设算法中中项的整数除法采用小数截断的方法。)(6分)