你好，该专业课是国家命题。计算机科学与工程系隶属于上海理工大学光电信息与计算机工程学院，下设计算机软件与理论和计算机应用两个专业教研室以及信息基础教研室，同时设有多媒体技术、软件工程和网络工程三个实验室。

软件工程实验室是为我系针对软件工程、软件协同设计、软件项目管理等课程建立的专业实验室。实验室提供软件工程先进的项目管理工具Microsoft Project Standard 2007、软件建模工具Sparx Enterprise Architect7.5 for windows。实验室提供的工具与平台帮助学生在掌握理论课的理论与方法基础上，熟悉并应用先进的工具进行软件开发过程管理、团队协作、设计与建模。从而使学生在走向工作岗位后，能够很快适应软件企业的开发与设计环境。

下附模拟试卷 希望能帮到你，并祝君考试高中！

数据结构模拟试卷

一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题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. O（n2）

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[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优顺序存储，元素A[6,6]的存储地址为 。

3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为 且小于n时，结点I的右兄弟是结点 ，否则结点i没有右兄弟。

4.求具有最小带权外部路径长度的扩充二叉树的算法称为 算法。堆排序中建堆的方法称作 。

5.6阶B树中，每个结点至多包含 个关键码，除根和叶结点外，每个结点至少包含 个关键码。

三、 简答题（每小题6分，共18分）

1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。

2.请简述散列法存储中处理碰撞（冲突）的两类基本方法。

3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？

四、 求解下列问题（每小题6分，共30分）

1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。

2.请画出下面的树所对应的二叉树。

3.从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。

4.请画出下面带权图的一棵最小生成树。

5.对于下面的稀疏矩阵

1）画出其三元组法存储表示。

2）画出其行—列法（十字链表法）存储表示。

五、 算法题（6分）

有一个链接方式存储的线性表，表中每个结点包括两个指针，其结点用PASCAL语言描述如下：

TYPE pointer=↑node;

node=RECORD

info:datatype;

link1,link2:pointer

END;

其中link1是指向结点的下一个结点的指针，link2是指向结点的前一个结点的指针,如图所示。

p和q都是pointer类型的变量，现要将q所指的新结点插入表中p所指结点的前面（说明：p所指的不是链表的第一个结点）。请用PASCAL语句写出该插入的关键步骤。（部要求写完整的算法，只要求用几个语句写出关键步骤。）

六、 算法填空和分析（共16分）

下面是用PASCAL语言编写的二分值插入排序算法，该算法对排序码为整数的线性表进行升序排序。

TYPE node=RECORD

key:integer;

info:datatype

End;

list=ARRAY[1..max] OF node;

PROCEDURE binarysort (VAR R: list; n: integer);

VAR temp :node ;

low,m,high,I,j: integer;

BEGIN

FOR I:=2 TO n DO

BEGIN

temp := R[ i ];

low :=1; high := i-1;

WHILE ① DO

BEGIN

m :=(low+high) DIV 2;

IF ②

THEN high :=m-1

ELSE ③

END;

FOR j := i-1 DOWNTO ④ DO

R[j+1] := R[j];

⑤

END;

END;

1.请将算法的空缺处应填入的正确内容写在下面。（10分）

①

②

③

④

⑤

2.设待排序的记录数n=7，当排序码的初始排列顺序分别为（15,25,35,45,55,65,75）和（75,65,55,45,35,25,15）时，请说出排序过程中对排序码所进行的总的比较次数分别是多少？（假定算法中取中项的整数除法采用小数截断的方法。）（6分）

本文地址： http://www.goggeous.com/f/1/958258

文章来源：天狐定制

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。