《宁波大学数据结构试题》由会员分享，可在线阅读，更多相关《宁波大学数据结构试题（9页珍藏版）》请在金锄头文库上搜索。
1、宁波大学 学年 数据结构与算法上机测试题 学号：_姓名：_ 课号： 课名：数据结构与算法 阅卷教师：_成绩:_ 第 1 页 共 1 页 学号 姓名 注 意 事 项： 注 意 事 项： 1. 考试时间： 3 小时 2. 题目完成后以本人“学号”为目录名存放在本机的 D 盘上, 例如 “D:074100101” 。 3. 请勿随意重启或关闭机器! 4. 请在以下题目中任选一题作答 考题一 考题一 如果将“大顶堆”的定义扩展为如下完全三叉树: (1)空树为堆; (2)根结点的值不小于所有 子树根的值,且所有子树均为堆。 要求用 C/C+编程实现采用这种三阶堆的堆排序算法。 考题二 考题二 利用静态三
2、元组表示稀疏矩阵， 用 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） ） 。
3、宁波大学 学年 第 学期期中考试卷（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）已知一个
4、推入堆栈的字符序列顺序是 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)、线性表采用链
5、式存储时，结点的存储地址_。 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-nex
6、t;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 二、填空题（每空二、填空题（每空 2 分分, 共共 26 分）分） 1. 分析下面算法（程序段） ，给出最大语句频度 ，该算法的时间复杂度是_ _。 for (i=1; ikey=K) flag = 1; else if ( Kkey) p = q; q = q-lch; else p = q; q = q-rch; if(flag = 0) coutkeyfront=QU-rear BQU-front！=QU-rear CQU-front=（QU-rear+1）m0
7、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;
8、(2)p-data=p-next-data; (3)p-next=_; (4)_; 3、一个 k 层的完全二叉树最多有_个结点，最少有_个结点。 4、对电文 “dodoesdoordoors”进行哈夫曼编码，其哈夫曼树的结点个数为_，该电 文的总编码长度为_。 5、B+树有两个查找的入口指针，其中一个指向_，另一个指向_。 三、简答题三、简答题:（50 分）分） 1、 已知二叉树已知二叉树 T 如右所示：如右所示： （10 分） （1） 画出 T 的先序线索二叉树； （4 分） 宁波大学 学年 第 学期期中考试卷（2） 学号：_姓名：_ 课号： 课名：数据结构与算法 阅卷教师：_成绩:_ 第
9、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
10、!=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-
11、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以二叉链表作为存储结构，写出求二叉树中叶子
12、结点数目的算法。（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 的满二
13、叉树的第 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、在对
