宁波大学数据结构试题.pdf

宁波大学 学年 数据结构与算法上机测试题 学号：_姓名：_ 课号： 课名：数据结构与算法 阅卷教师：_成绩:_ 第 1 页 共 1 页 学号 姓名 注 意 事 项： 注 意 事 项： 1. 考试时间： 3 小时 2. 题目完成后以本人“学号”为目录名存放在本机的 D 盘上, 例如 “D:074100101” 。 3. 请勿随意重启或关闭机器! 4. 请在以下题目中任选一题作答 考题一 考题一 如果将“大顶堆”的定义扩展为如下完全三叉树: (1)空树为堆; (2)根结点的值不小于所有 子树根的值,且所有子树均为堆。 要求用 C/C+编程实现采用这种三阶堆的堆排序算法。 考题二 考题二 利用静态三元组表示稀疏矩阵， 用 C/C+编程实现两个稀疏矩阵的相加运算。 输入包括两个稀 疏矩阵的大小、非零元素个数、元素值，输出为两个矩阵的和。 考题三 考题三 假设 K1，Kn 是 n 个关键词，试解答： (1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为 K1，K2， Kn 时，用算法建立一棵以 LLINK / RLINK 链接表示的二叉查找树。 (2) 设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D， K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为： 该二叉查找树的嵌套括号表示结构为：B（A，D（C，E） ） 。 宁波大学 学年 第 学期期中考试卷（1） 学号：_姓名：_ 课号： 课名：数据结构与算法 阅卷教师：_成绩:_ 第 1 页 共 2 页 学号 姓名 答案写在答题纸上答案写在答题纸上 一、单选题：（每小题 2 分，10 小题，共 20 分） 一、单选题：（每小题 2 分，10 小题，共 20 分） （1）一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 10 个元素的地址是 _。 A、100 B、108 C、110 D、118 （2） 一个数组 a10, 指针 p, 如果 p 指向 a，那么 *(p+1)+2 是_ A、a3 B、a5 C、a2+1 D、a1+2 （3）已知一个推入堆栈的字符序列顺序是 a,b,c,d,e, 下列哪个字符序列是不能得到的字符 序列_。 A、e,d,c,b,a B、d,e,c,b,a C、d,c,e,a,b D、a,b,c,d,e （4）如果推入一个队列的字符序列是 a,b,c,d,e, 那么队列的输出序列是 _。 A、a,b,c,d,e; B、a,c,d,b,e; C、e,d,c,b,a ; D、d,c,e,a,b; （5）下列是 4 个二叉树，请指出哪个是完全二叉树_。 A B C D （6）下图是一个二叉树 后序遍历的结果是 _。 A、 abcdef B、 cfabde C、 dbaecf D、 cbfade (7)、线性表采用链式存储时，结点的存储地址_。 A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续 (8)、从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均 比较_个结点。 A. n B. n/2 C. (n1 ) / 2 D. (n+1) /2 (9)、设计一个判别表达式中左右括号是否配对的算法，采用_数据结构最佳。 A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 (10)、在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是_。 Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 二、填空题（每空二、填空题（每空 2 分分, 共共 26 分）分） 1. 分析下面算法（程序段） ，给出最大语句频度 ，该算法的时间复杂度是_ _。 for (i=1; i=n; i+) for (j=1; j=i ; j+) coutlch; else p = q; q = q-rch; if(flag = 0) coutn 查找失败，无此结点！查找失败，无此结点！n; else coutn 查找成功，找到：查找成功，找到：keyrear BQU-front！=QU-rear CQU-front=（QU-rear+1）m0 DQU-front!=（QU-rear+1）m0 （8） 串是一种特殊的线性表，其特殊性体现在_。 A可以顺序存储 B.数据元素是一个字符 C可以链接存储 D.数据元素可以是多个字符 （9） 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 _。 A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶子结点 D. 是任意一棵二叉树 二、填空题（每题 1 分，共 10 分）二、填空题（每题 1 分，共 10 分） 1、在数据结构中，从逻辑上可以把数据结构分成_ 和 _。 2、在一个单链表中删除 p 所指结点时，应执行以下操作： (1)q=p-next; (2)p-data=p-next-data; (3)p-next=_; (4)_; 3、一个 k 层的完全二叉树最多有_个结点，最少有_个结点。 4、对电文 “dodoesdoordoors”进行哈夫曼编码，其哈夫曼树的结点个数为_，该电 文的总编码长度为_。 5、B+树有两个查找的入口指针，其中一个指向_，另一个指向_。 三、简答题三、简答题:（50 分）分） 1、 已知二叉树已知二叉树 T 如右所示：如右所示： （10 分） （1） 画出 T 的先序线索二叉树； （4 分） 宁波大学 学年 第 学期期中考试卷（2） 学号：_姓名：_ 课号： 课名：数据结构与算法 阅卷教师：_成绩:_ 第 2 页 共 2 页 学号 姓名 （2） 画出 T 对应的森林。 （4 分） 2简述以下算法的功能（5 分） 。 Status A(LinkedList L) /L 是无表头结点的单链表 if ( L L=L-next; P=L; While ( P-next ) P=P-next; P-next=Q; Q-next=NULL; return OK; /A 3简述以下算法的功能（5 分） 。 status algo2 (Stack S，int e) Stack T； int d； InitStack (T)； while ( !StackEmpty (S) ) Pop ( S，d)； if (d!=e) Push (T，d )； while ( !StackEmpty (S) ) Pop ( S，d)； Push ( S，d)； 4设给定权集 w =2，3，4，7，8，9，试构造关于 w 的一棵哈夫曼树，并求其加权路径长 度 WPL。 （10 分） 5已知一个单链表 L, 函数 converse 倒置链表的结点.请在空白处正确填写代码。(10 分) Struct SLNode DateType date; ; ; void converse(SLNode * head) SLNode *q,*p= head-next; head-next=NULL; while(_) _; p=p-next; _; head-next=q; 6、已知关键字值序列（53， 27， 58，36，22，42，80， 77， 72，25） 。 （共 12 分，每小题 6 分） （1） 关键字值序列是否为堆？若不是则将它调整为小顶堆； （2） 按上述关键字值次序构造一棵初始状态为空的二叉排序树； 四、算法设计题四、算法设计题（20 分） 1请构造函数 int full(btree *bt),该函数判断一颗二叉树是否为满二叉树: （10 分） Struct btree DateType date; btree * left; btree * right; 2以二叉链表作为存储结构，写出求二叉树中叶子结点数目的算法。（10 分） 宁波大学 2008/2009 学年第二学期考试卷（A） 学号：_姓名：_ 课号： 102J07A03 课名：数据结构与算法 阅卷教师：_成绩:_ 第 1 页 共 4 页 学号 姓名 答案写在答题纸上答案写在答题纸上 一、一、 选择题（共选择题（共 21 分，每题分，每题 1.5 分）分） 1、下列几个符号串编码集合中，不是前缀编码的是： （ ） A. （ 0，10，110，1111 ） B. （ 11，10，001，101，0001 ） C. （ 00，010，0110，1000 ） D. （ b，c，aa，ac，aba，abb，abc ） 2、深度为 h 的满二叉树的第 i 层有 ( ) 个结点。 A. 2i-1 B.2 i -1 C. 2 h-1 D. 2 h -1 3、在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是（ ） 。 Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 4、归并排序中，归并的趟数为：( ) A. O(n) B. O(n*log(n) C. O(n2) D. O(log(n) 5、假设元素 a，b，c，d，e 依次进入一个栈后出栈，下列序列中不可能出现的是（ ） 。 （A）a，b，c，d，e （B） b，c，d，e，a （C）e，a，b，c，d （D） e，d，c，b，a 6、输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（ ） 。 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 7、在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是： （ ） A. O(log(n) B. O(n*log(n) C. O(n) D. O(1) 8、下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序（9） 一棵非空的二叉树的先序遍 历序列与后序遍历序列正好相反，则该二叉树一定满足_。 A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶子结点 D. 是任意一棵二叉树 9、下面关于 m 阶 B 树说法正确的是: ( ) A. 每个结点至少有两棵非空子树； B. 树中每个结点至多有 m 一 1 个关键字; C. 所有叶子在同一层上; D. 当插入一个数据项引起 B 树结点分裂后，树长高一层。 10、根据堆的定义，以下序列不是堆的是：( ) A. （ 99，84，97，75，80，65，83，35，20，15，50 ） B. （ 99，97，84，83，80，75，50，65，35，20，15 ） C. （ 15，20，35，65，50，75，80，83，85，97，99 ） D. （ 99，84，35，75，80，65，50，97，83，15，20 ） 11、关键路径是事件结点网络中：( ) A. 从源点到终点的最长路径 B. 从源点到终点的最短路径 C. 最长的回路 D. 最短的回路 12、在一棵度为 3 的树中, 度为 3 的结点个数为 2, 度为 2 的结点个数为 1, 则 度为 0 的结点个数为 ( ). A4 B5 C6 D7 13、设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。 A链式线性表 B. 队列 C. 堆 D. 栈 14、下面哪一方法可以判断出一个有向图是否有环（回路）：（ ） A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 二、填空题（共 21 分，每空 1.5 分）二、填空题（共 21 分，每空 1.5 分） 1、引入循环队列的目的是为了克服： 。 2、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则其带权路径长度 WPL 的值为_ _。 3、以下算法对不带头结点的单链表进行就地逆置(指针反转)，L 返回逆置后的链表的头指针， 宁波大学 2008/2009 学年第二学期考试卷（A） 学号：_姓名：_ 课号： 102J07A03 课名：数据结构与算法 阅卷教师：_成绩:_ 第 2 页 共 4 页 学号 姓名 试在空缺处填入适当的语句。 void reverse（linklist q-next=p； p=q； _ _ ; _ _; 4、二叉树的遍历可以有_ _、_ _、_ _三种。 5、已知一棵度为 3 的树有 1 个度为 1 的结点，2 个度为 2 的结点，3 个度为 3 的结点，则 该树有_ _个叶子结点。 6、高度为 8 的完全二叉树至少有_ _个结点；拥有 100 个结点的完全二叉树的层数为 _。 7、LZW 算法的基本思想 8、快速排序在_ _ 的情况下最易发挥其长处。 9、哈希表处理冲突的常见方法有(写出两种)： 、 。 三、简答题（共 40 分，每题 5 分）三、简答题（共 40 分，每题 5 分） 1. Two stacks S1 and S2 are used to store the operand and operator in the evaluation of the following expression. Please draw the change of stack configuration. A B * C / D + E / F 2. Draw an expression tree for the following arithmetic expression （ （ a + b ）+ c * ( d + e ) + f ）* ( g + h ) 3. Perform a Big-O analysis for each function (a) nnn 35 7 (b) 3/2 6log7nnn (c) 2 3*2log2* ! n nnn 4. Please draw a B-tree of order 3 for the following key numbers： （20，54，69，84，71，30，78，25，93，41，7，76，51，66，68，53，3，79，35，12，15，65） 宁波大学 2008/2009 学年第二学期考试卷（A） 学号：_姓名：_ 课号： 102J07A03 课名：数据结构与算法 阅卷教师：_成绩:_ 第 3 页 共 4 页 学号 姓名 5、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写 完整下示给出各步排序步骤的结果： 建立堆结构：_ _ 交换与调整： （1）87 70 26 61 45 12 3 97; （2）_ _; （3）61 45 26 3 12 70 87 97; （4）_ _ _; （5）26 12 3 45 61 70 87 97; （6）_ _; （7）3 12 26 45 61 70 87 97; 6、Please draw the residual graph (剩余图) for the following network and flows: 7、设散列表的长度=13；散列函数为 H(K)=K mod m，给定的关