浙江理工大学考研专业课试题991数据结构2017.pdf

1、第 1 页 ，共 4 页 浙浙 江江 理理 工工 大大 学学 2017 年硕士研究生招生考试初试试题年硕士研究生招生考试初试试题 考试科目：数据结构考试科目：数据结构 代码：代码：991 （请考生在答题纸上答题，在此试题纸上答题无效）（请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题：一、单选题：(每小题每小题 2 分，共分，共 30 分分) 1. 不带头结点的单链表 simpleList 为空的判定条件是 。 A. simpleList = null B. simpleList-next = null C. simpleList-next = simpleList D. simple

2、List! = null 2. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。 A. 单链表 B. 仅有头结点的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 3. 向 一 个 栈 顶 指 针 为top的 链 栈 中 插 入 一 个S所 指 结 点 时 ， 则 执 行_。 A. top-next = S; B. S-next = top-next; top-next = S; C. S-next = top; top = S; D. S-next = top; top = top-next; 4. 一维数组和线性表的区别是_。 A

3、. 前者长度固定，后者长度可变 B. 后者长度固定，前者长度可变 C. 两者长度均固定 D. 两者长度均可变 5. 设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组 B1, n(n-1)/2中，对任一下三角部分中任一元素 aij(ij),在一组数组 B 的下标位置 K 的值是_。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 6.在线索化二叉树中，P 所指的结点没有左子树的充要条件是_。 A. P-left = null B. P-ltag =1 C. P-ltag =1 且 P-left =

4、null D. 以上都不对 7. 如果 Tree2 是由有序树 Tree1 转换而来的二叉树，那么 Tree1 中结点的后序就是 Tree2中结点的_。 A. 先序 B.中序 C. 后序 D. 层次序 8. 判定一个有向图上是否存在回路除了可以利用拓扑排序方法外， 还可以用_。 A. 求关键路径的方法 B. 求最短路径的 Dijkstra 方法 C. 广度优先遍历算法 D. 深度优先遍历算法 第 2 页 ，共 4 页 9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 10.采用折半查找法查找长度为 n 的线性表时，每个元

5、素的平均查找长度为_。 A. O(n2) B.O(nlog2n) C. O(n) D.O(log2n) 11二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是： A E B F C G D H 12已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V7， E=,G 的拓扑序列是（ ） 。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7 13采用邻接表存储的图的广度优先遍历算法类似于二叉

6、树的( )。 A先序遍历 B按层遍历 C后序遍历 D中序遍历 14设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为 H（key）=key MOD 13，散列地址为 1 的链中有（ ）个记录。 A1 B2 C3 D4 15对数列25，84，21，47，15，27，68，35，20进行排序，元素序列的变化情况如下： 第一趟 25，84，21，47，15，27，68，35，20，第二趟 20，15，21，25，47，27，68，35，84，第三趟 15，20，21，25，35，27，47，68，84，第四趟 15，20，21

7、，25，27，35，47，68，84，则采用的排序方法是（ ） 。 A希尔排序 B简单选择排序 C快速排序 D归并排序 二、填空题：二、填空题：(每空每空 3 分，共分，共 30 分分) 1. 在循环双链表的 P 所指结点之前插入 S 所指结点的操作如下： S-next = P; S-prior = ; P-prior-next = S; P-prior = S; 2. 分析以下程序段的时间复杂度为_。 k=1; While (k=n) k = k*2; 623074155648第 3 页 ，共 4 页 1532463. 向一个长度为 n 的顺序表中的第 i 个元素(01in )之前插入一个元

8、素时，需向后移动_个元素。 4设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 W1，W2，.，Wn。问能否从这 n 件物品中选择若干件放入背包， 使得放入的重量之和正好是 S。 设布尔函数 Knap(S，n)表示背包问题的解，Wi(i=1，2，.，n)均为正整数，并已顺序存储地在数组 W 中。请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若 S=0 则 Knaptrue 否则若（S0 且 n1) 则 Knapfalse 否则若 Knap (1) =true 则 print(Wn)；Knap true 否则 KnapKnap (2) 5下列程序判断字

9、符串 s 是否对称，对称则返回 1，否则返回 0；如 f(abba)返回 1，f(abab)返回 0； int f( (1)_) int i=0, j=0; while (sj) (2)_; for (j-; ij & si=sj; i+,j-); return ( (3)_) 6. 一个有 n 个顶点的无向图最多有_条边。 7. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用_比较好。 三、简答题三、简答题：(每每题题 15 分，共分，共 30 分分) 1. 已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；

10、 （5） 强连通分量。 第 4 页 ，共 4 页 2. 设二叉树 BTree 的存储结构如下： 1 2 3 4 5 6 7 8 9 10 left 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i right 0 0 0 9 4 0 0 0 0 0 其中，BTree 为树根结点指针，left、right 分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0 表示指针域值为空；data 为结点的数据域。请完成如下问题： (1) 画出二叉树 BTree 的逻辑结构； (2) 写出按先序、中序和后序遍历二叉树 BTree 所得到的结点序列； (3

11、) 画出二叉树 BTree 的后线索化树。 四、应用题四、应用题：(每每题题 30 分，共分，共 60 分分) 1、已知长度为 12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec) (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树， 试画出插入完成之后的二叉排序树并计算其在等概率查找情况下，查找成功的平均查找长度。 (2)试用以下两种方法构造两个 Hash 表，Hash 函数 H(K)=i/2,其中 i 为关键字 K 中第一个字母在字母表中的序号，x表示取整数。 a.用线性探测开放定址法处理冲突(散列地址空间为 016); b.用链地址法处理，然后分别求出这两个 Hash 表在等概率查找情况下，查找成功的平均查找长度。 2、一个整数队列中有 n 个元素，请问：是否存在与 n 无关的方法，来删除这个队列中的一个特定的元素。如果可能，请给出你的数据结构和删除算法，算法用函数表示，函数的定义如下；如果不可能，请说明你的理由。 函数定义： void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted) / 加入你的代码，如果你认为这样的方法存在的话