资源描述
第 1 页 ，共 4 页 浙 江 理 工 大 学 2017年硕士研究生招生考试初试试题 考试科目：数据结构 代码： 991 （请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题： (每小题 2分，共 30分 ) 1. 不带头结点的单链表 simpleList为空的判定条件是 。 A. simpleList = null B. simpleList-next = null C. simpleList-next = simpleList D. simpleList! = 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. 前者长度固定，后者长度可变 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 =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的线性表时，每个元素的平均查找长度为 _。 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的拓扑序列是（ ）。 A V1,V3,V4,V6,V2,V5,V7 B V1,V3,V2,V6,V4,V5,V7 C V1,V3,V4,V5,V2,V6,V7 D V1,V2,V5,V3,V4,V6,V7 13采用邻接表存储的图的广度优先遍历算法类似于二叉树的 ( )。 A先序遍历 B按层遍历 C后序遍历 D中序遍历 14设有一组记录的关键字为 19， 14， 23， 1， 68， 20， 84， 27， 55， 11， 10， 79，用链地址法构造散列表，散列函数为 H（ key） =key MOD 13，散列地址为 1 的链中有（ ）个记录。 A 1 B 2 C 3 D 4 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， 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 (k0且 n1) 则 Knapfalse 否则若 Knap (1) =true 则 print(Wn)； Knap true 否则 KnapKnap (2) 5 下列程序判断字符串 s 是否对称，对称则返回 1，否则返回 0； 如 f(“abba“)返回 1，f(“abab“)返回 0； int f( (1)_) int i=0, j=0; while (sj) (2)_; for (j-; ij i+,j-); return ( (3)_) 6. 一个有 n个顶点的无向图最多有 _条边。 7. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 _比较好。 三、简答题 ： (每 题 15分，共 30分 ) 1. 已知如图所示的有向图，请给出该图的： （ 1） 每个顶点的入度、出度； （ 2） 邻接矩阵； （ 3） 邻接表； （ 4） 逆邻接表； （ 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) 画出二叉树 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.用线性探测开放定址法处理冲突 (散列地址空间为 0 16); b.用链地址法处理 ， 然后分别求出这两个 Hash 表在等概率查找情况下，查找成功的平均查找长度。 2、一个整数队列中有 n个元素， 请问： 是否存在与 n无关的方法 ， 来 删除 这个队列 中 的 一个特定的 元素 。如果可能，请给出你的数据结构和删除算法 ，算法 用函数表示 ，函数的定义如下 ；如果不可能，请说明你的理由。 函数定义： void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted) / 加入你的代码，如果你认为这样的方法存在的话
展开阅读全文