《数据结构试题A200711答案.doc》由会员分享，可在线阅读，更多相关《数据结构试题A200711答案.doc（5页珍藏版）》请在金锄头文库上搜索。
1、陕西科技大学 试题纸（A参考答案及评分标准）课程 数据结构 班级 信息、数学05 学号 姓名 题号一二三四五六七八九十总分得分阅卷人一、 选择题（每小题1分，共15分）请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。1. 设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。A1，2，3，4 B4，3，2，1C1，3，4，2 D4，1，2，32. 设有80行的二维数组A8060，其元素长度为4字节，按行优先顺序存储，基地址为300，则元素A1825的存储地址为（D）。A3800 B4376 C3900 D47203. 将一棵有100个节点的完全二叉
2、树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为0，则编号为49的结点的左孩子编号为（B）。A98 B99 C50 D494. 在长度为n的顺序存储的线性表中，删除第i个元素（1i n）时，需要从前向后依次前移（A）个元素。An-iBn-i+1Cn-i-1Di5. 栈的插入和删除操作在（A）进行。A栈顶B栈底C任意位置D指定位置6. 链表适用于（A）查找。A顺序B二分法C二分法、顺序D随机7. 深度为6(根结点的层次为1)的二叉树至多有（D）个结点。A64B32C31D638. 用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。A栈B队列C树D图9. 设有两个
3、串和，求在中首次出现的位置的运算称作（B）。A连接B模式匹配C求子串D求串长 10.若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。A单链表 B双链表 C单向循环 D顺序表11.三个结点可构成（D）个不同形态的二叉树。A2 B3 C4 D512.下列关键字序列中，（D）是堆。A16,72,31,23,94,53B94,23,31,72,16,53 C16,53,23,94,31,72D16,23,53,31,94,7213.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A唯一的B有多种，但根结点都没有左孩子C有多种D有多种，但根结点都没有右孩子14.串是任意有限
4、个（C）。A符号构成的序列B符号构成的集合C字符构成的序列D字符构成的集合15.在一个链队列中，假定front和rear分别为队首和队尾指针，则进行插入s结点的操作时应执行（C）操作。Afront next =s ; front =s ;Bs next = rear ; rear = s ;Crear next = s ; rear = s ;Ds next = front ; front = s ;二、填空题（每空1分，共15分）1. n为整型变量且为正整数，下列算法中加下划线语句的执行次数为 n-2 ，算法的时间复杂度T（n）= O(n) 。 int i=1, k=0; while(in-
5、1) k=k+10*i; i+;2. 数据的逻辑结构被分为 集合结构 、 线性结构 、 树结构 和 图结构 四种。3. 用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的 前一个位置 ，该循环队列的最大长度为 n-1 。4. 一棵高度为5的二叉树中最少含有 5 个结点，最多含有 31 个结点。5. 线性表的顺序存储结构特点是，表中逻辑上相邻的元素在机器内的 位置 也是相邻的。6. 当堆栈采用顺序存储结构时，栈顶元素的值可用 sstackstop-1或s.stacks.top-1 表示；当堆栈采用链表存储结构时，栈顶元素的值可用 Hs data或HL data或Headne
6、xtdata 表示。7. 采用冒泡排序对有n个记录的表A按关键字递增排序，若A的初始状态是按关键字递增，则排序过程中记录的比较次数为 n-1 。若A的初始状态是按关键字递减，则排序过程中记录的交换次数为 n(n-1)/2 。三、简答题（每小题6分，共30分）1. 什么叫类型？什么叫抽象数据类型？/每问3分答：类型是具有相同特征的数据元素的集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。2. 什么叫运行时栈？什么叫运行时栈中的活动记录？/每问3分答：运行时栈是系统用于保存递归函数调用信息的堆栈。信息包括两个方面：一是调用函数的返回地址；二是调用函数的局部变量值。每一层递归调用所
7、需保存的信息构成运行时栈的一个工作记录，运行时栈的栈顶工作记录称为运行时栈中的活动记录。3. 比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：（1）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。 /2分（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放节点值；另一部分存放表示节点间关系的指针。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。 /2分顺序表适宜于做查找等静态操作；链表适宜于做插入
8、、删除等动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除等操作，则采用链表。 /2分4. 动态数组和静态数组在使用方法上有什么不同？答：（1）从使用方法上来说，动态数组和静态数组除向系统申请内存空间的方法不同外，数组的使用方法完全相同。 /3分（2）从性能上来说，静态数组必须确切指定数组元素个数，这样的指定在程序运行后不能改变；动态数组虽然也要确切指定数组元素个数，但因为这样的指定是在程序运行时通过调用函数实现的，一方面，可以利用malloc()函数或calloc()函数根据实际问题的需要申请动态数组的元素个数，另一方面，当所
9、申请的动态数组空间不足时，还可以通过realloc()函数来重新指定动态数组元素的个数。 /3分5. 适宜于递归算法求解的问题的充分必要条件是什么？什么叫递归出口？答：充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一有限步的子问题（也称作本原问题）有直接的解存在。 /3分递归到某一步时的子问题有直接的解存在，这个子问题就是递归出口。或者说递归出口就是递归结束的条件。 /3分四、算法思想题（每小题7分，共28分）1. 假设用于通信的电文由字符集A,B,C,D,E,F,G,H构成，各字符在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.0
10、3,0.21,0.10。为这8个字母设计哈夫曼编码（要求画出哈夫曼树）。解：哈夫曼树如下：1.0000.400.210.190.280.320.110.170.100.070.060.030.050.020.600000001111111 /4分根据上图可得编码表： /3分A:1001B:01C:10111D:1010E:11F:10110G:00H:10002. 设有数据元素序列11，23，35，47，51，60，75，88，90，102，113，126，用除留余数法构造哈希表，要求：（1） 设计哈希表的长度取值m；（2） 画出用开放地址法的线性探查法解决哈希冲突的哈希表结构；解：（1）要存
11、放的数据元素个数为n=12，m最好取1.1n1.7n之间的一个素数，所以设计哈希表的长度m1.5n=19。（也可取17）/2分（若取其它大于12的值最多得1分）（2）用哈希函数h(k)=k mod m=k mod 19，哈希冲突函数 d0=h(k) di=( di +1) mod 19, (1i 18) /2分依次对数据元素进行映射，得到的哈希地址分别为： /1分h(11)=11h(23)=4h(35)=16h(47)=9h(51)=13h(60)=3 h(75)=18h(88)=12h(90)=14h(102)=7h(113)=18(冲突)h1(113)=（18+1）mod 19=0h(12
12、6)=12(冲突)h1(126)=（12+1）mod 19=13 (冲突)h2(126)=（13+1）mod 19=14 (冲突)h3(126)=（14+1）mod 19=15最后得哈希表结构如下： /2分11360231024711885190126357501234567891011121314151617183. 已知一棵二叉树中序遍历序列为DBGEAFHC，后序遍历序列为DGEBHFCA请画出此二叉树。解：此二叉树如下： /错一个扣1分CABDGEFH4. 设数据元素关键字序列为475，137，481，219，382，674，350，326，815，506，写出执行希尔排序（增量d=5
13、，3，1）算法时，各趟排序后的关键字序列。解：各趟排序后的关键字序列如下：初始关键字475137481219382674350326815506 增量为5时475137326219382674350481815506 /2分增量为3时219137326350382674475481815506 /3分增量为1时137219326350382475481506674815 /2分五、编程题（共12分）编写算法实现顺序表的就地逆置，即要求利用原顺序表的存储单元，请使用抽象数据类型，把数据元素序列（a0,a1,an-1）逆置为（an-1,a2,a1）。附：顺序表的抽象数据类型定义如下：typedef struct DataType listMaxSize;int size; SeqList;解：typedef struct DataType listMaxSize;int size; SeqList
