南昌大学 数据结构 2010～2011学年第一学期期末试卷与答案a

南昌大学 20102011 学年第一学期期末考试试卷 试卷编号： ( A )卷 课程编号： 课程名称： 数据结构 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题号 一 二 三 四 五 六 七 八 九 十 总分 题分 20 30 30 20 100 累分人 签名 得分 考生注意事项：1、本试卷共 8 页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更 换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一、 选择题(每题 1 分，共 20 分) 得分 评阅人 1. 算法必须具备输入、输出和 _。 A. 计算方法 B. 排序方法 C解决问题的有限运算步骤 D. 程序设计方法 2. 设将整数 1,2,3,4,5 依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空） 进行，则出栈序列不可能是 _。 A23415 B. 54132 C23145 D. 15432 3. 用链表表示线性表的优点是 _。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4. 若某线性表的常用操作是取第 i 个元素及其前趋元素，则采用_。存储方 式最节省时间 A.顺序表 B.单链表 C.双链表 D. 单向循环 5. 串是任意有限个_。 A.符号构成的序列 B.字符构成的序列 C.符号构成的集合 D. 字符构成的集合 6. 设有一个对称矩阵 A，采用压缩存储方式，以行序为主序存储 a11 为第一个元素， 其存储地址为 1，每个元素占一个地址空间，则 a85 地址为_。 A.23 B.33 C.18 D. 40 7在一个单链表中，若 p 结点不是最后一结点。在 p 结点之后插入 s 结点的正确是 。 A. s-next=p; p-next=s; B. s-next=p; p=p C. s-next=p-next ; p-next=s; D. p-next=s; s-next=p; 8. 将含 100 个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号， 根结点的编号为 1。编号为 47 的结点 X 的双亲的编号为 。 A.24 B.25 C.23 D.无法确定 9. 在一棵二叉树中有 30 个叶子结点，仅有一个孩子的结点有 20 个，则该二叉树共 有 个结点 A、79 B、76 C、56 D、81 10. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C. 31 D. 10 11对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施 加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 _。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12二分查找要求节点 。 A有序、顺序存储 B. 有序、链接存储 C无序、顺序存储 D. 无序、链接存储 13在一个无向图中，所有顶点的度数之和等于图的边数的 倍 A1/2 B. 1 C. 2 D. 4 14. 已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进 行排序时，前两趟排序的结果为 （35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93） 所采用的排序方法是_ A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序 15一棵二叉树有 67 个结点，这些结点的度要么是 0，要么是 2。这棵二叉树中度为 2 的结点有_个 A. 33 B. 34 C. 32 D. 30 第 3 页 共 11 页 16由五个分别带权值为 9，2，3，5，14 的叶子结点构成的一棵哈夫曼树，该树的带 权路径长度为_。 A. 60 B. 66 C. 67 D. 50 17.对一棵二叉排序树进行_遍历得到的结点序列是一个有序序列。 A.前序 B.中序 C.后序 D.层序 18有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100, 当二分查找值 82 为的结点 时，_次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 19就平均查找速度而言，下列几种查找速度从慢至快的关系是_。 A.顺序 折半 哈希 分块 B.顺序 分块 折半 哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半 20. 设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最 好选用_排序法。 A. 冒泡排序 B. 快速排序 C. 堆排序 D. 选择排序 二、填空题 (每空 2 分，共 30 分) 得分 评阅人 1.设 r 指向单链表最后一个结点，要在最后一个结点之后插入 s 所指的结点，需执行 的三条语句是 r-next=s ; r=s; _【1】_ 。 2.数据的逻辑结构分为两大类，它们是线性结构和_【2】_。 3已知循环队列用数组 datan存储元素值，用 front,rear 分别作为头尾指针，则 当前元素个数为_【3】_。 4. 一棵二叉树有 30 个叶子结点，仅有一个孩子的结点有 20 个，则该二叉树共有 【4】 个结点；若完全二叉树共有 100 个结点，则其叶子结点数为 【5】 。 5.在带头结点单链表 L 中，表空的条件是_【6】_。 6. 在一个长度为 n 的顺序表中的第 i 个元素（1in）之前插入一个元素时，需向 后 移_【7】_个元素。 7.设一个链栈的栈顶指针为 ls，栈中结点格式为 infolink ，栈空的条件是 _【8】_。若栈不空，则退栈操作为 p=ls；_【9】_；free(p)。 8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归 并排序方法对其进行排序(按递增顺序)，_【10】_最省时间，_【11】_最 费时间。 9.图的遍历方式通常有 【12】 遍历和 【13】 遍历两种。 10.下面是将键值为 X 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct node *pnode struct node int key; pnode left,right; void searchinsert(int x; pnode t); /t 为二叉排序树根结点的指针/ if(_【14】_) p=malloc(size); p-key=x; p-left=null; p-right=null; t=p; else if (xkey) searchinsert(x,t-left) else _【15】_; 三、应用题 (每小题 5 分，共 30 分) 得分 评阅人 1. 对于下面的稀疏矩阵，画出其三元组法存储表示(假设下标从 0 开始)。 0 0 14 0 0 0 0 0 0 0 -6 0 7 0 0 0 0 24 0 0 0 18 0 0 0 15 0 0 0 0 27. 2.已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。 中序序列：D I G J L K B A E C H F 后序序列：I L K J G D B E H F C A 第 5 页 共 11 页 3.给定权值5,10,12,15,30,40,构造相应的哈夫曼树，并写出他的带权路径长度。 4.已知一个无向图的邻接表为: 画出这个图，并以 V1 为出发点，对图进行广度优先搜索，写出遍历序列。 5. 已知一组元素为（46，25，78，62，12，37，70，29） ，试画出按元素排列次序 插入生成的一棵二叉排序树。 6.有一组键值 27,84,21,47,15,25,68,35,24,采用快速排序方法由小到大进行排序， 请写出每趟的结果。 四、算法设计题 (每小题 10 分，共 20 分) 得分 评阅人 1.试写出逆转线形单链表的算法，单链表节点的类型定义如下。 Typedef struct node elemtype data; /数据域 struct node *next; /指针域 第 7 页 共 11 页 2.采用顺序结构存储串，设计一个算法 strcmp(s,t)实现串的比较，串的比较以词典方 式进行，当 s 大于 t 时，返回 1，当 s 等于 t 时，返回 0，当 s 小于 t 时，返回-1，顺 序串的类型定义如下： #define Maxsize Typedef struct sqstring char chMaxsize; /存放串字符； int len; /存放串的实际长度； 数据结构 A 卷答案 一、 选择题（每小题 1 分，共 20 分） 得分 评阅人 二、 填空题（每空 2 分，共 30 分） 得分 评阅人 【1】 rnext=null【2】 非线性结构 【3】 （rear-front+n）%n【4】 79 【5】 51 【6】lnext=null 【7】n-i+1 【8】 ls=null 【9】ls=lslink 【10】 冒泡 【11】 快速 【12】 深度 【13】 广度 【14】t=null 【15】 searchinsert(x,tright) 三、应用题 (每小题 5 分，共 30 分) 得分 评阅人 1. 1 C 2 B 3 C 4 A 5 B 6 B 7 C 8 C 9 A 10 C 11 C 12 A 13 C 14 B 15 A 16 C 17 B 18 C 19 B 20 C 0 2 14 1 4 -6 2 0 7 2 5 24 3 3 18 4 1 15 第 9 页 共 11 页 2. 3. 30 40 5 10 0 0 0 1512 2 2 2Wpl=5*3+10*3+12*3+15*3+30*2+40*2=266 4. V1 V2 V5 V4 V3 以 V1 为出发点，对图进行广度优先搜索 V1-V2-V4-V5-V3 A B C D E F HG J K I L 5. 46 25 78 37 29 62 70 12 6. 24，25，21，15， 【27】 ，47，68，35，84 15，21， 【24】 ，25， 【27】 ，35， 【47】68，84 四、算法设计题 (每小题 10 分，共 20 分) 得分 评阅人 1. node *Revers ( node *head ) node *p , *q ; p=head-next ; head-next=NULL ; while (p != NULL ) q