内蒙古大学2007～2008 学年第一学期算法与数据结构试卷(A卷)及参考答案

第 1页共 8 页计算机软件学院计算机软件学院 2006 级级 2007200720082008 学年第一学期学年第一学期算法与数据结构试卷算法与数据结构试卷(A(A 卷卷) )（闭卷 120 分钟）班级姓名学号重修标记总分题号一二三四五核分人得分复查人得分一、一、填空题（本大题共填空题（本大题共 1010 小题，每空小题，每空 1 1 分，共分，共 1616 分分）1.1. 数据结构所讨论的三个方面为、和。2.2. 将下三角矩阵A108的下三角部分按行优先存储到起始地址为1000的内存单元中，已知每个元素占 4 个单元，则 A75的地址是。3.3. 广义表( a ,b ),c ,d,( e ,( f,g ) 的表头是，表尾是，表的长度为，表的深度为。4.4. 在串 S=student 中，以 u 为首字符的子串有个。5.5. 假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a , b , c , d 进行一系列操作 SSXSXSXX 之后，得到的输出序列为。6.6. 快速排序在排序码有序的状态下， 其时间复杂度为。 平均情况下快速排序的时间复杂度为。7.7. 已知完全二叉树的第 10 层上有 7 个结点，则其结点总数为。8.8. 含有 n 个顶结点， e 条边的无向图的邻接矩阵中， 零元素的个数为。9.9. 在图的深度优先遍历算法中，用到的重要的数据结构是,10.10. 3 个结点可构成棵不同形态的树。得分得分评卷人评卷人装订线第 2页共 8 页二、二、选择题选择题（在每小题的四个备选答案中在每小题的四个备选答案中，选出一个正选出一个正确的答案，并将其号码填在题干中的括号内，本大题确的答案，并将其号码填在题干中的括号内，本大题共共 1010 小题，每小题小题，每小题 2 2 分，共分，共 2020 分）分）1111下列说法中不正确的是()A. 数据元素是数据的基本单位B. 数据项是数据中不可分割的最小可标识单位C. 数据可由若干个数据元素构成D. 数据项可由若干个数据元素构成1212. 线性表是（）A. 一个有限序列，可以为空B. 一个有限序列，不可以为空C. 一个无限序列，可以为空D. 一个无限序列，不可以为空1313. 栈和队列的共同点是（）A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点1414. 串是一种特殊的线性表，其特殊性体现在（）A. 可以顺序存储B. 数据元素可以是一个字符C. 可以链式存储D. 数据元素可以是多个字符1515. 对稀疏矩阵采用压缩存储，其缺点之一是（）A. 无法判断矩阵有多少行多少列B. 无法根据列号查找某个矩阵元素C. 无法根据行列号计算矩阵元素的存储地址D. 使矩阵元素之间的逻辑关系更加复杂1616. 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）A. 250B. 501C. 254D. 5051717. 在一个无向图中，所有顶点的度之和等于边数的（）倍A. 1/2B. 1C. 2D. 41818. 一个无向连通图的生成树是含有该连通图的全部顶点的（）A. 极小连通子图B. 极小子图C. 极大连通子图D. 极大子图1919. 散列表的平均查找长度（）A. 与处理冲突的方法有关而与表的长度无关B. 与处理冲突的方法无关而与表的长度有关C. 与处理冲突的方法有关而与表的长度有关D. 与处理冲突的方法无关而与表的长度无关2020.快速排序方法在（）情况下最不利于发挥其长处A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序D. 要排序的数据个数为奇数得分得分评卷人评卷人第 3页共 8 页三、三、简答题简答题( (本大题共本大题共 5 5 小题，每小题小题，每小题 4 4 分，共分，共 2020 分分) )21.21. 数据结构中研究的逻辑结构有哪些？各有什么特点？2222阅读下列算法，说明下面递归过程的功能。int exam (BinTreeNode *root) /指针 root 指向二叉树的根指针if (t=NULL) return 0;else if (t-leftChild=NULL & t-rightChild=NULL) return 1;else return exam (t-leftChild)+exam (t-rightChild);得分得分评卷人评卷人装订线第 4页共 8 页23.23. 已知一棵二叉树的前序遍历序列为 ABDEHCG, 中序遍历序列为 DBHEACG,请画出此二叉树。24.24. 设哈希表 HT13，采用线性探测再散列解决冲突。哈希函数为：H(key)=key % 13;注：%是求余数运算(=mod)。若插入的关键码序列为2，8，31，20，19，18，53，27。试画出插入这 8 个关键码后的哈希表。25.25. 已知有向图：G= V= a , b , c , d , e , f , g E=,(1) 用图画出该有向图； （2 分）(2) 写出该有向图的一个拓扑序列。 （2 分）26.26.请写出下列稀疏矩阵顺序存储的行主序的三元组表示。 008000000000507202900017000000032000780022A0123456789101112第 5页共 8 页四、四、算法应用题算法应用题( (本大题共本大题共 3 3 小题，每小题小题，每小题 8 8 分，分，共共 2424 分分) )2626. 给出从顶点 1 到顶点 8 的关键路径及关键路径长度。得分得分评卷人评卷人装订线第 6页共 8 页2727. 给出对输入的元素85,50,35,100,65,20,45,30,50,5进行归并排序的示意图。并28.28. 输入一个正整数序列40,28,6,72,100,3,54,1,80,91,38，建立一棵二叉查找树。并对该二叉查找树进行中序遍历。第 7页共 8 页五、算法设计题五、算法设计题( (本大题共本大题共 2 2 小题，每小题小题，每小题 1010 分，分，第第 3030 题中每空题中每空 2 2 分，共分，共 2020 分分) )2929.对带头结点的单链表，给出进行直接插入排序的算法。单链表类定义如下：class LinkList;class Node /链表结点类friend class LinkList;/声明链表类为其友元类private:intdata;/结点数据类型,整型Node *next;/结点指针;class LinkList /链表类private:Node *head；/头指针public:Node*MaxValue(Node *head);/*求以 head 为头指针的单链表中值最大的数据元素，函数返回该最大值所在结点的指针。*/;得分得分评卷人评卷人装订线第 8页共 8 页3030. 下面给出的是对以二叉链表存储的二叉查找树进行查找关键字 key 的算法， 该算法在查找成功时，函数返回关键字 key 所在结点的指针，否则返回空指针。请阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。BinaryTreeNode *Search(keyType key,BinaryTreeNode *&root) p=root;while ()if(key=p-key)return;else if ()p=p-leftChild;else；/while; / search第 9页共 8 页 本科课程考试试题参考答案及评分标准开开课课单单位位: :计计算算机机学学院院学学生生所所在在学学院院：软软件件学学院院（2008 2009 年年第第一一学学期期）课程编号01332340学分/总学时4/64课程名称算法与数据结构课程类别公共课 专专业/年级计算机科学与技术/2006 级修读方式必修课选修出题教师赵玉兰、刘玉林是否主干是考试方式闭卷开1. 逻辑结构，存储结构，基本操作(或算法)2.11323. ( a ,b ) ,(c ,d,( e ,( f,g )，4，34.45. bcda6. 0(n2), O(nlog2n)7.10308. n2-2e9. 栈10. 211121314151617181920DACDDCCAAC21. 线性结构、集合、树型结构、图型或网状结构线性结构的特点：结构中的数据元素具有“一对一”的关系集合特点：结构中的数据元素只具有“同属于一个集合”的关系树型结构的特点：结构中的数据元素存在一对多的关系图型结构的特点：结构中的数据元素存在多对多的关系22. 统计二叉树中叶结点数23. 见手工画24. 散列表2753231192081825.见手工画26. 见手工画0123456789101112第 10页共 8 页27（1）初始序列35，74，59，50，06，38，47，10，50*，12，0535745059063810471250*053550597406103847051250*0610353847505974051250*050610123538475050*5974（2）进行了 4 趟归并排序。28.29.30. high=n-1low xmid