2016年江苏扬州大学程序设计与数据结构考研真题A卷.doc

发布时间：2022-10-14 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

第1页 / 共4页

2016年江苏扬州大学程序设计与数据结构考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共4页

2016年江苏扬州大学程序设计与数据结构考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共4页

2016年江苏扬州大学程序设计与数据结构考研真题A卷.doc.pdf-第4页.jpg

第4页 / 共4页

文本预览

2016 年江苏扬州大学程序设计与数据结构考研真题 A 卷一、单项选择题（本大题共 10 小题，每小题 2 分，共 20 分） 1.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（）。 A.索引存储方法 B.顺序存储方法 C.链式存储方法 D.散列存储方法 2.在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（）。 A.直接前趋 B.直接后继 C.开始结点 D.终端结点 3.在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）。 A.0(1) B.O（Ign） C.O(n) D.O(n2) 4.在链队列执行入队操作（）。 A.需判别队是否空 B.需判别队是否满 C.限制在链表头 p 进行

D.限制在链表尾 p 进行 5.广义表（()）的长度为（）。 A.0 B.1 C.2 D.不确定 6.在一个图中,所有顶点的度数之和与图的边数的比是（）。 A.1：2 B.1：1 C.2：1 D.4：1 7.n 个顶点的无向图若釆用邻接矩阵存储，则该矩阵的大小是 A. N B.（n-1） 2 C.n+1 D.n2 8.栈的插入和删除操作在（）进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置 9.循环队列存储在数组 A[0..m］中，则入队时的操作为（）。

A.rear=rear+l B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1) 10.下面关于串的的叙述中，哪一个是不正确的？( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D. 串既可以釆用顺序存储，也可以釆用链式存储二、简答题(本大题共 6 小题，第 1 一 5 题每小题 12 分，第 6 小题 10 分，共 70 分) 1.什么是数据结构？有关数据结构的讨论涉及哪三个方面？ 2.何时选用顺序表、何时选用链表作为线性表的存储结构为宜？在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？ 3.试分别找出满足以下条件的所有二叉树： (1)二叉树的前序序列与中序序列相同;’ (2)二叉树的中序序列与后序序列相同； (3)二叉树的前序序列与后序序列相同。 4.画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。并证明在 n 个顶点的无向完全图中，边的条数为 n(n-l)/2。 5.试对下图所示的 AOE 网络，解答下列问题： (1)这个工程最早可能在什么时间结束； (2)求每个事件的最早开始时间 Ve[i]和最迟允许开始时间 Vl[i]； (3)求每个活动的最早开始时间 e()和最迟允许开始时间 l()；

(4)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 6.每次从无序表中取岀一个元素，把它插入到有序表中的适当位置，此种排序方法叫做什么排序？每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做什么排序？每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做什么排序？每次使两个相邻的有序表合并成一个有序表的排序方法叫做什么排序？三、算法设计题(本大题共 5 小题，每小题 12 分，共 60 分) 1.有顺序表 A 和 B,其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表 C,要求 C 的元素也是从小到大的升序排列。 2.数制转换问题，将十进制数 N 转换为 r 进制的数。 3.若矩阵 Amxn”中存在某个元素 aij 满足：aij 是第 i 行中诚小值且是第 j 列中的最大值，则称该元素为矩阵 A 的一个鞍点。试编写一个算法，找出 A 中的所有鞍点。 4.假设哈希表长为 m,哈希函数为 H(x),用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。 5.试以单链表为存储结构实现简单选择排序的算法。

分享到：

赞收藏

资料库

2016年江苏扬州大学程序设计与数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料