北京理工大学813计算机专业基础模拟题1

本资料由理硕教育整理,理硕教育助全力您圆北理之梦

理硕教育—专注于北理工考研辅导 http://

本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校，相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率89%以上，复试通过率接近100%，理硕教育现开设初试专业课VIP一对一，假期集训营，复试VIP一对一辅导，满足学员不同的需求。因为专一所以专业，理硕教育助您圆北理之梦。详情请查阅理硕教育官网

北京理工大学数据结构模拟题 数据结构试卷（一）

一、单选题（每题2分，共20分） 1、找和队列的共同特点是（）

A.只允许在断点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点 2、用链接方式存储的队列，在进行插入运算时（）

A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改 3、以下数据结构中哪一个是非线性结构？（） A.队列B.栈C.线性表D.二叉树 4、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注（10）表示用10进制表示。 A.688B.678C.692D.696

5、树最适合用来表示（）

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

6、二叉树的第k层的结点数最多为（） A.2k-1B.2K+1C.2K-1D.2k-1

7、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放在A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（） A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3

8、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（） A.O(1)B.O(n)C.O(log2n)D.O(n2)

9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个 A.1B.2C.3D.4

10、设有6个结点的无向图，该图至少应有（）条边才能确定是一个连通图。 A.5B.6C.7D.8

二、填空题（每空1分，共26分）

1、通常从四个方面评价算法的质量：_________、__________、_________和__________。 2、一个算法的时间复杂度为（n2+n2log2n+14n）/n2，其数量级表示为________。

3、假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J))，则树中所含的结点数为________个，树的深度为_________个，树的深度为________，树的度为__________。

4、后缀算式9 2 3+-10 2/-的值为_________。中缀算式（3+4X）-2Y/3对应的后缀算式为__________________。

5、若用链表存储一棵二叉树时，每个结点除数据线外，还有指向左孩子和幼孩子的两个指针，在这种存储结构中，n个结点的二叉树共有_______个指针域，其中有__________个指针域是存放了地址，有_________个指针是空指针。

本资料由理硕教育整理,理硕教育助全力您圆北理之梦

理硕教育—专注于北理工考研辅导 http://

6、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和_________个。

7、AOV网是一个________________的网。

8、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

9、假定一个线性表为（12，23，74，55，63，40），若按Key%4条件进行划分，使得同一条数的元素成为一个子表，则得到的四个子表分别为______________________、______________________、______________________和______________________。

10、向一条B—树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度______________________。

11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为______________________，整个堆排序过程的时间复杂度为______________________。 12、在快速排序、堆排序、归并排序中，______________________排序是稳定的。 三、计算题（每题6分，共24分）

1、在如下数组A中链接存储路一个线性表，表头指针为A[0].next，试写出该线性表。

A

data next

2、请画出下图的邻接矩阵和邻接表。

3、已知一个图的顶点集V和边集E分别为：V={1，2，3，4，5，6，7}； E={（1，2）3，（1，3）5，（1，4）8，（2，5）10，（2，3）6，（3，4）15，（3，5）12，（3，6）9，（4，6），4（4，7）20，（5，6）18，（6，7）25}；用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4、画出向小根堆中加入数据4，2，5，8，3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1、LinkList mynote(LinkList)

{//是不带头结点的单链表的头指针 If(L&&L->next){

q=L;L=L—>next;p=L S1: while(p—>next)p=p—>next;

S2: P—>next=q;q—>next=NULL; }

本资料由理硕教育整理,理硕教育助全力您圆北理之梦

理硕教育—专注于北理工考研辅导 http://

return L; } 请回答下列问题：

（1）说明语句S1的功能； （2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1，a2，.......，an），写出算法执行后的返回值所表 …… 此处隐藏：1042字，全部文档内容请下载后查看。喜欢就下载吧 ……