《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研仿真模拟题一、填空题1 设有两个算法在同一机器上运行，其执行时闻分别为_。【答案】15【解析】当时，而，时，2 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为 3 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 4 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，
2、栈2空时， 要使前者快于后者，n 至少为表示，两栈顶指针为则为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。5 实现字符串拷贝的函数strcpy 为： 【答案】 6 当广义表中的每个元素都是原子时，广义表便成了_。【答案】线性表【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。 7 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 【答案】 【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序
3、放到一个字符数组中。8 设有一个10阶对称矩阵A 采用压缩存储方式 ，（以行为主序存储：）则的地址为_。【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则则的地址为若的地址为将代入得33。 9 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储10已知如下程序段： 语句1执行的时间复杂度为_；语句2执行的时间复杂度为_；语句3执行的时间复杂度为_；语句4执行的时间复杂度为_。【答案】（1）n 1 （2）n（3）n （n 3）/2 （
4、4）n （n l ）/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. （n l ）加起来就是n （n 3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了123. n 即n （n l ）/2。 11设二维数组A 的行和列的下标范围分别为【答案】 和每个元素占2个单元，按行优先顺处的元素为_。当其值为序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。12有五个数据依次入栈：1，
5、2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 二、选择题13将一个（即该元素下标A.198 B.195 C.197【答案】B的三对角矩阵，按行优先存入一维数组在B 数组中的位置K 为（ ）。中，A 中元素【解析】将对角矩阵存入三对角矩阵压缩地址计算公式如下： 14下列排序算法中，其中（ ）是稳定的。A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D15已知程序如下： 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。A. B.一、填空题考研试题
