下载文档原格式
山东大学数据结构（一）一、单选题（每题2 分，共20分）1.栈和队列的一路特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有一路点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]寄存位置在644(10)，A[2][2]寄存位置在676(10)，每一个元素占一个空间，问A[3][3](10)寄存在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 +1 C.2K-1 D. 2k-17.如有18个元素的有序表寄存在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
.6 C二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时刻复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
山东大学计算机学院计算机信息管理2006级夜大专科数据结构复习题一、填空题1、数据结构可以定义为一个两元组（D，S），其中 D 是数据元素的有限集，S 是的有限集。
2、在线性表中，线性表的长度指的是。
3、栈中元素的进出原则为 ____________。
4、深度为 k 的二叉树其结点数至多有个。
5、一棵深度为6的满二叉树有______个非终端结点。
6、若一棵二叉树中有8个度为2的结点,则它有_____个叶子。
7、设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序8、为主序顺序存储,则元素A[4,5]的存储地址为_____；若以列序为主序顺序存储,则元素A[4,5]的存储地址为______。
9、哈希表是一种查找表，可以根据哈希函数直接获得。
10、在单链表中，删除指针 P 所指结点的后继结点的语句是：。
11、有向图 G 用邻接矩阵 A[1..n，1..n] 存储表示，其第 i 行的所有元素之和等于顶点 i 的。
12、在一个单链表p所指结点之后插入一个s所指结点时，应执行s→next=____和p→next=_____的操作。
13、设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有____个结点。
14、设需将一组数据按升序排序。
在无序区中依次比较相邻两个元素a i和a i+1的值，若a i的值大于a i+1的值，则交换a i和a i+1。
如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。
15、数据结构在计算机中的表示称为数据的。
16、一棵含999个结点的完全二叉树的深度为_______。
17、广义表的深度是指_______。
18、称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。
19、在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_________。
20、在队列中，允许插入元素的一端称为_________。
山东大学2019级数据结构与程序设计专业试题数据结构部分（75分）一、单选题：（每小题2分，10小题，共20分）1、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，12、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目3、下列二叉树中，( )可用于实现符号的不等长高效编码。
A. 最优二叉树B. B-树C. 平衡二叉树D. 二叉排序树4、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（）A．i B．i+1C．n-i D．n-i+15、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A．f,c,b B．f,d,bC．g,c,b D．g,d,b6、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
A．快速排序 B. 堆排序 C. 归并排序 D. 插入排序7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）A. 选择排序B. 快速排序C. 冒泡排序D. 插入排序8、有n个结点的有向完全图的弧数是（）A. n2B. 2nC. n(n-1)D. 2n(n+1)9、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）A．求关键路径的方法 B. 求最短路径的Dijkstra方法C. 深度优先遍历算法D.广度优先遍历算法10、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A. s→link = p→link; p→link = s;B. p→link = s; s→link = q;C. p→link = s→link; s→link = p;D. q→link = s; s→link = p;二、简答题（每题5分, 5题，共25分）1. 一颗二叉树的前序遍历的结果是1，2，3，4，5，6, 中序遍历的结果是3，2，4，6，5，1。
………………………………………………密………………………………封………………………………线………………………………山东大学 2018-2019 学年 一 学期 数据结构 课程试卷A题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷人得分学院 专业 级 学号 姓名一、线性结构（30分）。
1、已知线性表：（8，9，2，13，0，7，1，6，5），请完成以下题目。
⑴请描述公式化描述及链表描述的空间需求。
如果需要删除元素13，请描述各自的时间复杂度。
⑵ 请分别进行选择排序、插入排序、快速排序（以8为轴），并给出第一轮排序结束后各自的结果。
⑶ 设计散列表，散列函数为H （k)=k%7，散列表长度为11，请给出线性开型寻址的散列表。
⑷ 基于以上散列表，查找元素1，给出需要的查找次数。
⑸若使用单链表存储上述线性表，请阅读以下程序，并给出程序运行结果及其时间复杂度。
二、层次结构（35分）。
1. 二叉树的层次遍历序列为ABCDEFGHIJ ，中序遍历序列为DBGEHJACIF ，写出该二叉树的前序遍历序列。
2. 一个最大堆为（66，37，41，30，25，40，35，18），依次从中删除两个元素，写出最后得到的堆。
3. 有一份电文中共使用6个字符：A 、B 、C 、D 、E 、F ，它们的出现频率依次为10、6、5、2、15、4，试画出对应的赫夫曼树（请按左子树根节点的权小于等于右子树根节点的权的次序构造，左0右1），并求出每个字符的赫夫曼编码。
4. 对给定输入序列{ 19, 5, 7, 11, 26, 18, 16, 17 },构建AVL 树。
5. 在下列5阶B-树中首先插入关键字85，然后删除关键字70，画出插入元素和删除元素后的B-树。
三、网状结构（35分）。
1. 请给出从加权无向图中生成最小耗费生成树的两种方法，请分别描述其算法思想，并给出各自的时间复杂度。
2. 下面是某有向加权图(顶点A,B,C,D,E)的耗费邻接矩阵，先给出一个拓扑序列，然后，使用Dijkstra算法依次计算出顶点A 至其它各顶点的最短路径和最短路径长度。
《数据结构》试卷（B卷）一、单项选择题1. 线性表是__A___。
A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 A 个元素。
A．n-i B．n-i+l C．n-i-1 D．i3. 线性表采用链式存储时，其地址_D___。
A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较___C_个元素结点。
A．n/2 B．n C．（n+1）/2 D．（n-1）/25. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是_A D 。
A． p->next=s; s->prior=p;p->next->prior=s; s->next=p->next;B． s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C． p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;D． s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为__A___。
A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7. 在一个长度为n的顺序表中向第i个元素(0< i<n+l )之前插入一个新元素时，需向后移动__B_个元素。
第3章数据结构3．1数据结构的基本概念一、部分例题及解题思路选择题1.数据结构是指（）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)5.算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。
年级________；层次________；专业________；姓名________复习资料，自我完善，仅供参考，考完上交！ 《数据结构》试卷（A 卷）一、选择题1. 数据结构是指（A ）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C ）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ D ）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（B ）。
for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n )C.O(n)D.O(3n ) 5. 算法分析的目的是（1） C ，算法分析的两个主要方面是（2） A 。
（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6. 计算机算法指的是（1） C ，它具备输入，输出和（2） B 等五个特性。
（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ）。
A.低B.高C.相同D.不好说。
山东大学计算机试题及答案山东大学计算机试题一、选择题（每题2分，共20分）1. 下面关于计算机的描述中，不正确的是（）。
A.计算机能够进行高速运算B.计算机只能执行用户明确要求的任务C.计算机能够存储和处理大量信息D.计算机可以通过网络进行通信2. 下列设备中，属于输出设备的是（）。
A.鼠标B.显示器C.键盘D.内存条3. 在计算机领域，RAM是指（）。
A.随机访问存储器B.只读存储器C.外部存储器D.主控存储器4. 下列哪个是计算机网络的功能之一（）。
A.数据存储B.数据处理C.数据传输D.数据加密5. 在Windows操作系统中，Ctrl+C的快捷键代表的操作是（）。
A.复制选中的内容B.剪切选中的内容C.粘贴剪切板中的内容D.关闭当前窗口二、填空题（每题2分，共20分）1. 操作系统的主要功能之一是管理和控制计算机的________ 资源。
2. 在二进制中，4个位用 ________ 表示一个数字。
3. 在计算机网络中，IP地址是用来标识 ________ 的。
4. 在Excel中，公式的开头需要添加 ________ 符号。
5. 在HTML中，用于添加链接的标签是 ________。
三、简答题（每题10分，共20分）1. 请简要解释什么是算法，并举例说明。
2. 解释什么是数据库，列举一个常见的数据库软件。
四、编程题（共40分）请编写一个Python程序，实现以下功能：给定一个整数列表，要求对列表进行排序，并输出排序后的列表。
例如，给定列表[4, 2, 7, 11, 5]，经过排序后的输出结果为[2, 4, 5, 7, 11]。
山东大学计算机答案一、选择题1. B2. B3. A4. C5. A二、填空题1. 硬件2. 83. 主机4. =5. <a>三、简答题1. 算法是解决问题或执行任务的一系列步骤或指令的数学描述。
例如，冒泡排序算法通过比较相邻元素的大小并交换位置来完成排序。
树结构总结及习题一、概述树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，象自然界中的树那样。
树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。
树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序的语法结构。
又如在数据库系统中，树型结构也是信息的重要组织形式之一。
一切具有层次关系的问题都可用树来描述。
二、树结构定义及基本概念（一）定义一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：（1）每个元素称为结点（node）；（2）有一个特定的结点，称为根结点或根（root）；（3）除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）（二）基本概念度树的度——也即是宽度，简单地说，就是结点的分支数。
以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。
树中度不为零的结点称为分枝结点或非终端结点。
除根结点外的分枝结点统称为内部结点。
深度树的深度——组成该树各结点的最大层次层次根结点的层次为1，其他结点的层次等于它的父结点的层次数加1.路径对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。
可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1.森林指若干棵互不相交的树的集合三、各种树结构特性、基本操作及特性（一）二叉树1、定义二叉树（binary tree）t 是有限个元素的集合（可以为空）。
当二叉树非空时，其中有一个称为根(root)的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树.2、特性●包含n (n> 0 )个元素的二叉树边数为n-1●若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h-1 个元素。
计算机系统结构本科山大20年考试题库及答案一.问答题（15分）1、cache存储器中为什么会产生替换？请列举3种常用的替换算法。
学生答案：2、什么是虚拟存储器中的段页式管理？采用分段和分页结合的方法。
程序按模块分段，段内再分页，进入主存仍以页为基本信息传送单位，用段表和页表进行两级定位管理。
3、多处理机系统与机群系统有什么差别？答：多处理机系统由若干台独立的计算机组成，每台计算机能够独立执行自己的程序，彼此之间通过互连网络连接，实现程序之间的数据交换和同步。
机群系统是一组完整的计算机互连，它们作为一个统一的计算资源一起工作，并能产生一台机器的印象。
二、名词解释（36分）1.4、SIMD:单指令多数据流计算机5、资源共享：是一种软件方法，它使多个任务按一定的时间顺序轮流使用同一套硬件设备。
6、Cache：位于CPU与主存之间的高速缓存，用来存放当前频繁访问的内容7.模拟:用机器语言程序解释实现软件移植的方法称为模拟.1.8、RISC：精简指令系统计算机，它是指按照通过减少指令总数和简化指令功能来降低硬件设想的复杂度，来提高指令履行速度的途径设想成CPU的计算机2.9、实页冲突:指虚页调入时，根据地址映像方式划定的实空间范围内已没有空闲实页的状况。
10、地址映像：地址映像就是将每一个主存块按什么规则装入Cache中。
1.11、资源重复：通太重复设置资源，特别是硬件资源，大幅度提高计算机系统的性能。
2.12、系统结构：计算机系统结构也叫计算机体系结构，指的是传统机器级的系统结构。
三计算题（50分）13、某模型机由8条指令，使用频度为30.30.20.10.050.020.020.01试划分用Huffmann编码和扩大编码对其操纵码进行编码，限定扩大编码只能做两种长度，则它们的编码长度比定长操纵码的长度削减多少？1111110.0310.010.020.020.050.10.20.0510.30.30.40.20.10.01I8 I7 I6 I5 I4 I3 I2 I1Huffman频度长度扩展长度I10.I20.I30.I40.I50.I60.I70.I80.定长编码长度：3Huffman长度：(0.3+0.3+0.2)*2 + 0.1*3 + 0.05*4 + 0.02*5 + 0.02*6 + 0.01*6 = 2.38长度减少3-2.38=0.62扩展编码长度：(0.3+0.3+0.2)*2 + (0.1 + 0.05 + 0.02 + 0.02 +0.01) * 5 = 2.6长度减少3-2.6=0.414、在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表为：分别写出延迟禁止表、冲突向量，画出流水线状态图，并给出平均延迟最小的调度方案。
2022年山东大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、下述说法中正确的是（）。
I.半导体RAM信息可读可写，且断电后仍能保持记忆Ⅱ.动态RAM是易失性RAM，而静态RAM中的存储信息是不易失的Ⅲ.半导体RAM是易失性RAM，但只要电源不断电，所存信息是不丢失的IV.半导体RAM是非易失性的RAMA.I、ⅢB.只有ⅢC.Ⅱ、IVD.全错2、下列关于Cache和虚拟存储器的说法中，错误的有（）。
I.当Cache失效（即不命中）时，处理器将会切换进程，以更新Cache中的内容II.当虚拟存储器失效（如缺页）时，处理器将会切换进程，以更新主存中的内容III.Cache 和虚拟存储器由硬件和OS共同实现，对应用程序员均是透明的IV.虚拟存储器的容量等于主存和辅存的容量之和A.I、IⅣB.Ⅲ、VC. I、Ⅱ、ⅢD. I、Ⅲ、Ⅳ3、设x为整数，[x]补=1.x1x2x3x4x5，若要x<-16，x1~ x5应满足的条件是（）。
A. x1~ x5至少有一个为1B.x1必须为1，x2~x5至少有一个为1C.x1必须为0，x2~x5至少有一个为1D.x1必须为0，x2~x5任意4、并行加法器中，每位全和的形成除与本位相加两数数值位有关外，还与（）有A.低位数值大小B.低位数的全和C.高位数值大小D.低位数送来的进位5、在浮点机中，（）是隐藏的。
A.阶码B.数符C.尾数D.基数6、内部总线（又称片内总线）是指（）。
A.CPU内部连接各寄存器及运算部件之间的总线B.CPU和计算机系统的其他高速功能部件之间互相连接的总线C.多个计算机系统之间互相连接的总线D.计算机系统和其他系统之间互相连接的总线7、在下列各种情况中，最应采用异步传输方式的是（）.A.I/O接口与打印机交换信息B.CPU与主存交换信息C.CPU和PCI总线交换信息D.由统一时序信号控制方式下的设备8、下列关于计算机操作的单位时间的关系中，正确的是（）。
2012年山东大学计算机学院数据结构真题共13大题150分1、分析下列函数，描述函数功能，并求函数的时间复杂度。
S=0For (int i=1;i<=n;i++){Int p=1;For (int j=1;j<=I;j++)P*=j:S+=p;}2、对于含有n个元素的有序数组，查找各个元素的概率相等，采取折半查找时，最少要比较多少次，最多要比较多少次，平均要比较多少次。
当n个元素无序时，采取折半查找，最多需要多少次，最少需要多少次。
3、描述栈与队列的相同点和不同点。
4、二叉树，先序遍历得到abdfceg，中序遍历得到fdbaceg，该二叉树的叶节点是什么。
5、有5000个无序元素，公式化描述（数组），要求最快速度选取最大的10个元素，请问，在快速排序，堆排序，基数排序，归并排序四种方法中，采取哪种方法最好，为什么？6、构建散列表，散列函数为hashf（k）=k%11.已知关键字序列为（8,15,27,2,13,31,19）（具体数字记不清了，我写的数字性质是一样的），请画图表示采取线性开放式寻址和链表地址法存贮。
7、（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边，最少有多少条边？（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边，最少有多少条边？8、在一篇电码中，由abcde字母组成，其分别出现的次数为4,8,25,37,6（具体数字记不清了，我写的数字性质是一样的）。
构造huffman树，给出各个字母的huffman编码，该篇电码的总电码数是多少。
9、有一图，顶点为v1，v2，v3，v4，v5，边的集合为（v2，v1），（v5，v3），（v1，v4）（v3，v2），（v1，v3），（v3，v4），（v4，v5），画出该图，该图是强连通有向图吗？10、有一函数fun的功能是将字符串中每个单词的最后一个字母改成大写，例如I am a student to exam.改成I aM A studenT tO exaM.请将该函数补全。
Void fun(char *P){Int k=0;For (;p;p++)If (k=1){If (*p= =‘’ ){【1】；【2】=upper(*(p-1));}}ElseK=1;}11、编写算法，求出二叉树中节点的度数为1的个数，并以n返回。
（要求不能使用递归），写出算法思想，并写出程序。
12、编写程序，给一正整数m，求出在1至m之间（包括m）中，能够被11或7整除的数字，保存在数组a中，函数返回在1至m之间（包括m）中，能够被11或7整除的数字的个数，例如m为,30，则将（7,11,14,22,21，28）保存在数组a中，函数返回5.13、有向图和无向图，分别采取邻接矩阵和邻接链表的方法存储。
（1）怎样求出图中的边的数目？（2）怎样判断在顶点i，j之间是否存在边？山东大学07计算机真题（回忆整理）1.（8分）（1）for(int i=1;i<=n;i++){int p=1;for(int j=1;j<=I;j++)p*=j;s+=p;}描述功能，并分析时间复杂度。
（2）对于1个n元素顺序表，用折半查找，成功查找时，最大最小比较次数各是多少？2.（8分） n阶三对角矩阵A，按行保存到一个数组B中，其中A[1][1]存入B[0]，问：（1）B中有多少元素（2）用i,j表示矩阵元素在B中的索引k（3）用k表示i,j3.（10分）（1）.一个中缀表达式为3*y-a/y↑2，求其后缀表达式（2）描述堆栈在处理后缀表达式中的作用（3）对于（1）中后缀式写出栈的变化 ]4.（12分）写出用数组实现字符串类String的类定义，并实现IsSym函数。
其中IsSym表示该字符串是中心对称的，例如xyzzyx，xyzyx，若是返回true，否则返回false5.（12分）写出单链表类chain的类定义，并实现BubbleSort函数，不能创建新节点，也不能删除旧节点，其他函数省略。
BubbleSort表示将原链表按非递减顺序冒泡排序。
6.（10分）一个二叉搜索树，设任一条从根到叶子的路径包含的节点集合为S2，这条路经所有左边的点的集合为S1，右边所有点集合为S3 ，设a,b,c分别为S1，S2，S3中的任意元素，是否有a<b<c？为什么？7.（20分）（1）写出最小堆的类声明。
（2）写出用最小堆实现Huffman编码的思想，并给出算法。
8.（10分）一个8key值的3阶B树最多有多少节点？最少有多少？并画出图表示。
9.（10分）如下图所示的AVL搜索树若先后插入70和60两个数后，树的最小不平衡树各是哪个？怎样旋转能使其达到平衡？画出树的形态。
为什么仅调整最小不平衡树就不存在其他不平衡点？10.（20分）加权有向图的邻接矩阵类为AdjacencyWDigraph（1）举出一个至少包括5个节点的例子，并写出他的邻接矩阵。
（2）写出AdjacencyWDigraph的类定义。
（3）在此基础上写出宽度优先搜索算法BFS，可以使用队列类Queue。
11.（20分）（1）从一点S出发对一个有向连通图求最短路径，按照如下贪婪准则：每次选择一个节点，该节点是与已选节点最近的尚未被选到的节点，直到到达目的节点。
问：这种方法得到的是最短路径吗？（2）若不是，举一反例，并写出你认为正确的一种方法。
12（10分）.什么是分治法？有什么原则？有哪些算法用了这种思想？举出一例，写出算法思想。
祝以后的学弟学妹们考个好成绩，在考研中这个论坛给了我很大的帮助，现在我将我的考研经验分享一下山东计算机的自主命题比较简单，建议（1）将05年以后的真题，回忆版好好做一下，有重复，并且出题重点一脉相承。
（2）对照考研大纲将原书看一遍，时间少也要将大纲标明“掌握”的内容精读，时间多将标明“了解”的内容通读，时间再多也不用去读未明确的内，或许山东本校都不学习。
（3）买一本复习资料（算法与数据结构考研试题精析），机械工业出版社，一定要看，有原题，有解题方法。
只要做好以上三点，考研130+在等你。
相信你自己，你行的。
写于2012年考研结束第二天，为我自己留个mark，也希望看到的你能够将它流传下去。
（为我家子洋求祝福，都快成孩他爹了，我容易吗我）2002年考研试题一、回答下列问题：（24分）1，如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
1）编写实现队列的基本运算：判空、入队、出队（3分）2）队列中能容纳元素的最多个数是多少？（1分）2、设有对角矩阵a[1..n,1..n]把非零元素按列存储在向量b[1..3*n-2]中，使得b[k]=a[I,j].求：（1）用I,j表示k的下标变换公式（2分）（2）用k表示I,j的下标变换公式（2分）3、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述评关键字序列哪一个不可能是在二叉排序树中找到的序列？说明原因。
（4分）（1）51，250，501，390，320，340，382，363（2）24，877，125，342，501，623，421，3634、设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？（2分）如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？（3分）5、在B-树和B+树中查找关键字时有什么不同？（2分）6、写出对关键字序列{503，087，512，061，908，124，897，275，653，426}建立一棵平衡二叉树的过程，并写出调整平衡时的指针变化。
（5分）二、解答下列问题：（10分）1、画出对长度为10的有序表进行二分查找的判定树并求其等概率时查找成功的平均查找长度（5分）。
2、设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法H i=(H(key)+di)mod10(di=1*1,2*2,3*3….)解决冲突。
要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度（5分）。
三、已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。
（要求用最少的时间和最少的空间）（15分）四、对以二叉链表存储的非空二叉树，从右向左依次释放所有的叶子结点，释放的同时把结点值存放到一个向量中要求：（1）用文字写出实现上述过程的基本思想（3分）（2）写出算法（12分）五、设二叉排序树已经以二叉链表的形式存储在内存中，使用递归方法，求各结点的平衡因子并输出。
要求：（1）用文字写出实现上述过程的基本思想（3分）（2）写出算法（12分）六、假设一个有向图g已经以右图所示的逆邻接表形式存储在内存中，要求：（1）写出逆邻接表的存储结构定义（3分）（2）用文字写出在逆邻接表上实现拓扑排序的基本思想（3分）（3）写出在逆邻接表上实现拓扑排序的算法（15分）。
