当前位置：问答库＞考研试题

二 O 一四年招收硕士研究生入学考试试题 考试科目代码及科目名称： 考试时间 3 小时，总分值 150 856 数据结构(C 语言版) 分。 答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。 一、选择题（10 小题，每题 2 分，共 20 分） 1. 算法分析的主要内容是（ ） 。 A）正确性 B）可读性和稳定性 C）简单性 D）空间复杂性和时间复杂性 2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） 。 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续或不连续都可以 3. 设有 6 个元素按 1、2、3、4、5、6 的顺序进栈，下列不合法的出栈序列是（ ） 。 A）234165 B）324651 C）431256 D）546321 4. 设有二维数组 A[1..12,1..10]，其每个元素占 4 个字节，数据按行优先顺序存储，第一个 元素的存储地址为 100，那么元素 A[5,5]的存储地址为（ ） 。 A）76 B）176 C）276 D）376 5. 已知一棵二叉树的先序序列为 ABDGCFK，中序序列为 DGBAFCK，则后序序列为（ ） 。 A）ACFKDBG B）GDBFKCA C）KCFAGDB D）ABCDFKG 6. 在二叉树结点的先序，中序和后序序列中，所有叶子结点的先后顺序（ ） 。 A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 7. 图的深度优先遍历类似于二叉树的（ ） 。 A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历 8. 下面（ ）算法适合构造一个稠密图 G 的最小生成树。 A） Prim 算法 B）Kruskal 算法 C）Floyd 算法 D）Dijkstra 算法 9. 对关键码{46,79,56,38,40,84}采用堆排序,则初始化堆(小堆)后最后一个元素是 （ ） 。 A）84 B）46 C）56 D）38 10.在 Hash 函数 H(k)=k MOD m 中，一般来讲 m 应取（ ） 。 A）奇数 B）偶数 C）素数 D）充分大的数 准考证号码： 报考专业： 密 封 线 内 不 要 写 题 二、填空题（10 小题，每题 2 分，共 20 分） 1. 在单向链表某 P 结点之后插入 S 结点的操作是（ ） 。 2. 线性表Ｌ用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动 元素的个数是（ ） 。 3. 一个栈的输入序列是：1，2，3 则不可能的栈输出序列是（ ） 。 4. 一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则该二叉树最少有（ ）结点。 5. 在完全二叉树中，编号为 i 和 j 的两个结点处于同一层的条件是（ ） 。 第 1 页 共 3 页 姓名：

6. 若无向图 G=（V,E） ，其中 V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}，现采 用图的（ ）遍历方法从顶点 a 开始遍历图，得到的序列为 abecd。 7. 求最短路径的 Dijkstra 算法的时间复杂度为（ ） 。 8. 假定有 k 个关键字互为同义词， 若用线性探测再散列法把这 k 个关键字存入散列表中， 至 少要进行（ ）次探测。 9. 设在已排序的线性表中共有元素 n 个，若用二分法查找表中的元素。若查找成功，至少要 比较（ ）次 10.对一组记录（54,38,96,23,15,2,60,45,83）进行直接插入排序，当把第 7 个记录 60 插入 到有序表时，为寻找插入位置需比较（ ）次。 三、综合应用题（7 小题，每题 10 分，共 70 分） 1. 已知 A[1..N]是一棵顺序存储的完全二叉树，如何求出 A[i]和 A[j]的最近的共同祖先？ 2. 请给出一棵哈夫曼树中分支数 B 与叶子节点数 n0 所满足关系式，并证明你的结论。 3. 下面的排序算法的思想是： 第一趟比较将最小的元素放在 r[0]中， 最大的元素放在 r[n-1] 中，第二趟比较将次小的放在 r[1]中，将次大的放在 r[n-2]中，…,依次下去，直到待排 序列为递增序。 （注：<--> 代表两个变量的数据交换） 。 void sort(SqList &r,int n) { i=0; while( (1) ) { min=max=i; for (j=i+1; (2) ;++j) { if( (3) ) min=j; else if(r[j].key>r[max].key) max=j; } if( (4) ) r[min]<-->r[i]; if(max!=n-i-1) { if( (5) ) r[min]<-->r[n-i-1]; else r[max]<-->r[n-i-1]; } i++; } }//sort 4. 如下图所示的AOE网 （1）写出所有的拓扑序列 （2）求各顶点代表的事件的最早发生时间和最迟发生时间 （3）求各条弧代表的活动的最早开始时间和最迟开始时间 （4）给出其关键路径 5. 设哈希函数 H（K）=3 K mod 11，哈希地址空间为 0～10，对关键字序列（32，13，49， 24，38，21，4，10） ，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找 成功时和查找失败时的平均查找长度 ASLsucc 和 ASLunsucc。 （1）线性探测法 （2）链地址法 第 2 页 共 3 页

6. 全国有 10000 人参加竞赛，只录取成绩优异的前 10 名，并将他们从高分到低分输出。而 对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？ 7. 假定对有序表(3,4,5,17,24,35,40,54,58,72,80,123)进行折半查找，试回答问题： （1）画出描述折半查找过程的判定树； （2）若查找元素 54，需依次与那些元素比较? （3）若查找元素 20，需依次与那些元素比较? （4）分别求等概率情况下查找成功和不成功时的平均查找长度。 四、算法设计与编程（4 小题，每题 10 分，共 40 分） 1. 设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred（前驱指 针） ，data（数据）和 next（后继指针）域外，还有一个访问频度域 freq。在链表被启用 前，其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时，令元素值为 x 的结 点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同 时最近访问的结点排在频度相同的结点的最后， 以便使频繁访问的结点总是靠近表头。 试 编写符合上述要求的 Locate(L,x)运算的算法， 该运算为函数过程， 返回找到结点的地址， 类型为指针型。 2. 已知二叉树用下面的顺序存储结构，写出先序遍历该二叉树的算法。 1 data Lc Rc A 2 3 2 B 4 5 3 C 0 6 4 D 0 0 5 E 0 7 6 F 8 9 7 G 0 0 8 H 0 0 9 I 0 0 3. 编写在后序线索二叉树中求任一结点直接前驱的算法（结点结构包括数据域 data、左孩 子域 left、 右孩子域 right、 左标志域 ltag 和右标志域 rtag， 标志域为 0 表示没有孩子， 孩子域为线索） 。 4. 有 n 个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序， 请写出这种排序的算法。 （注：双向冒泡排序即相邻两趟排序向相反方向冒泡） 。 第 3 页 共 3 页