下载文档原格式
一、算法（每 15 分，共 60 分）答要求：①用自然言明所采用算法的思想；② 出每个算法所需的数据构定，并做必要明；③写出的算法程序，并做必要的注。
1、有一个点的表，每个点包括两个域，一个是整型域 info ，另一个是指向下一个点的指域next 。
假表已建立，算法除表中所有重复出的点，使得 info 域相等的点只保留一个。
3、瑟夫（Josephus）是指号1、 2、⋯， n 的 n（ n>0）个人按方向坐成一圈，从第s 个人开始按方向数，数到第m 个人出列，然后从出列的下一个人重新开始数，数到第m 的人又出列，⋯，如此重复直到所有的人全部出列止。
要求采用循表构一个算法，模此程。
4、程表的就地逆置。
23．在数A[1..n]中有n个数据，建立一个有点的循表，指h，要求中数据从小到大排列，重复的数据在中只保存一个.5、一个尽可能的高效算法出表的倒数第K 个元素。
3、假以I 和 O 分表示入和出操作。
的初和均空，入和出的操作序列可表示由I 和 O 成的序列，称可以操作的序列合法序列，否称非法序列。
（15 分）（ 1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（ 2）通（ 1）的分析，写出一个算法，判定所的操作序列是否合法。
若合法，返回true，否返回false（假定被判定的操作序列已存入一数中）。
5、从入一整数的序列： a1, a2, a3，⋯， an, 写算法：用构存入的整数，当 ai ≠-1 ，将 ai ；当 ai=-1 ，出整数并出。
算法异常情况（入等）出相的信息。
有一个背包可以放入的物品重量S，有 n 件物品，重量分W1， W2， ... ，W n。
能否从 n 件物品中若干件放入背包，使得放入的重量之和正好是S。
布函数 Knap(S，n) 表示背包的解， W i(i=1,2,... ，n) 均正整数，并已序存地在数 W中。
西交11秋学期《数据结构》考试复习题数据结构-学习指南一、单项选择题1. 算法指的是（）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（）A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点4.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B.头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改5.以下数据结构中哪一个是非线性结构？( d )A. 队列B. 栈C. 线性表D. 二叉树6.二叉树的第k层的结点数最多为( )A．2k-1 B.2K+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的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )A.nB.n/2C.(n+1)/2D.(n-1)/29.在一个单链表中,若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;10.栈的插入和删除操作在（）进行。
A.栈顶B.栈底C.任意位置D.指定位置11. 组成数据的基本单位是（）。
A.数据项B.数据类型C.数据元素D.数据变量12．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。
习题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() C.O(n)D.O( )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.1953 C.1964 D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
其他系统西安交通大学--数据结构所有答案3,栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。
,A 正确 B错误,答案是：A3,在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。
,A正确 B错误,答案是：A3,具有n个结点的完全二叉树的高度为┖log2n┘1。
,A正确 B错误,答案是：B3,为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。
,A正确 B错误,答案是：A3,闭散列法通常比开散列法时间效率更高。
,A正确 B错误,答案是：B3,一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。
,A 正确 B错误,答案是：B3,有向图的邻接表和逆邻接表中表结点的个数不一定相等。
,A正确 B错误,答案是：B3,对链表进行插入和删除操作时不必移动链表中结点。
,A正确 B错误,答案是：A3,希尔排序算法的时间复杂度为On2。
,A正确 B错误,答案是：B3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
,A正确 B错误,答案是：B3,通常使用两个类来协同表示单链表，即链表的结点类和链表类。
,A正答案是：A3,顺序表用一维数组作为存储结构，因此顺序表是一维数组。
,A正确 B 错误,答案是：B3,二维数组是数组元素为一维数组的线性表，因此它是线性结构。
,A正确 B错误,答案是：B3,算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。
要想准确地计算总运算时间是不可行的。
,A正确 B错误,答案是：A3,堆是完全二叉树，完全二叉树不一定是堆。
（）,A正确 B错误,答案是：A3,顺序表查找指的是在顺序存储结构上进行查找。
（）,A正确 B错误,答案是：B3,入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。
,A正确 B错误,答案是：A3,中序遍历一棵二叉排序树可以得到一个有序的序列。
,A正确 B错误,答案是：A3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
一．填空题（每空1分）1.在线性表的顺序存储中，元素之间的逻辑关系是通过元素在存储器中的相对位置确定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针确定的。
2.若长度为n的线性表采用顺序存储结构，则在其第i个位置插入一个新元素算法的时间复杂度为O(n)。
3.线性表、栈和队列都是线性结构，可以在线性表的任意位置位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队头删除元素。
4.深度为K的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若按自上而下、从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2k-1二．选择题（每题2分）1.线性表的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种B的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取2.若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为B。
A．1和5 B．2和4C．4和2 D．5和13.设栈的输入序列为123…..n，输出序列为a1,a2,a3,……,a n，若存在1<=k<=n，使得a k=n，则当k<=i<=n时，a i为D。
A．n-i+1 B．n-(i-k)C．i D．不确定4.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法__ _ B _。
A 正确B 错误5.在一非空二叉树的中序遍历序列中，根结点的右边__ A ___。
A 只有右子树上的所有结点B 只有右子树上的部分结点C 只有左子树上的部分结点D只有左子树上的所有结点三改错题：阅读下列算法，若有错，则改正之。
BiTree InSucc(BiTree q){//已知q是指向中序线索二叉树上某个结点的指针，本函数返回指向*q的前驱的指针r=q->lchild;if(!r->ltag) //改为：if(!q->ltag)while(!r->ltag) r=r->lchild; //改为：while(!r-r>rtag) r=r->rchild;return r;}//InSucc四、已知二叉树BT各结点的先序和中序序列分别是A、B、C、D、E、F、I、J、K、L和C、B、A、E、D、I、F、L、K、J，请画出该二叉树，并写出其后序序列。
《数据结构》复习题一.选择题:3. 如果某数据结构的数据元素的集合为S={A,BCD,E,F,G},元素二间的关系为R 二{V A,D>,V A,G 〉,<D,B>,<D,C>,<GE>,<GF>},则该数据结构是一种（ ）11. 将一个元素进入队列的时间复杂度是（ ）1. 数据结构是研究数据的（A. 理想结构，物理结构 C.物理结构，逻辑结构2. 纟R 成数据的基木单位是）以及它们之间的相互关系B. 理想结构，抽象结构 D.抽彖结构，逻辑结构A.数据项B.数据类型C.数据元素D.数据变量A.线性结构 B.树结构4. 线性表的链接实现有利于( )运算A.插入 B.读表元5. 设一数列的输入顺序为1, 2, 3, 4, 5, A. 3, 2, 5, 6, 4, 1 C. 2, 4, 3, 5, 1, 66. 设字符串 Sl= 'ABCDEFG', S2= 'PQRST' Sub(Sl, Length(S2), 2))后结果为(A. 'BCQR'B. 'BCDEF'C.图结构D.链表结构C. 杳找D.定位6通过栈操作不可能排成的输出序列为( )B. 1, 5, 4, 6, 2, 3 D. 4, 5, 3, 6, 2, 1则运算 S=Concat (Sub(Sl, 2, Length (S2))>)C. 'BCDEFG'D. 'BCDEFEF'7. 设单链表中指针P 指向结点A,若要删除A 之后的结点（若存在），则修改指针的操作为（）A. p->next= pf next —next C ・ p= pf next —next8. 线性表采用链式存储时，其地址（ A.必须是连续的 C. —•定是不连续的9. 在内部排序时，排序不稳定的有（ B. p= pf next D. pf next = pB.部分地址必须是连续的 D.连续与否均可以A •插入排序 B.冒泡排序 C •快速排序D •归并排序10.设有1000个元索，用折半法查找时，最小比较次数为（ ） A.O B. 1 C.10 D. 500A.O(l)B. O (n)C. O (n 2)D. O (log 2n)12. 在一个具有n 个结点的单链表中查找其值等x 的结点, 在查找成功的情况卜,需要比较（）个元素结点二•填充题：1. 循环链表的主要优点是 ________________________________________________ O2. 一个n 切的对称矩阵，如果以行列为主序存入内存，其容量为 __________________ o3. 在双向循环链表中，在指针P 所指的结点Z 后插入指针f 所指的结点,其操作为 _____________________________________________________________________ O4. 设有一个空栈，现输入序列为 1, 2, 3, 4, 5 经过 push, push, pop, push, pop, push, pop, push输出序歹lJ 为 ________________________________________ >5. 一个算法，如果不论问题规模大小运行所需时间都一样，则算法的时间复朵度是 ________ o6. 数据结构有线性结构，树结构 __________ 和 _________ 等几种逻辑结构。
数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。
每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。
下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。
2. 在二叉搜索树中，中序遍历的结果是________。
编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。
2. 二叉树每个节点最多有______个子节点。
编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。
每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。
西安交大数据结构习题及答案西安交大数据结构习题及答案1：栈和队列1.1 栈1.1.1 基本概念栈是一种后进先出（Last-In-First-Out, LIFO）的数据结构，即最后进入的元素最先被访问。
1.1.2 基本操作- push(x): 元素x入栈- pop(): 弹出栈顶元素- top(): 返回栈顶元素- isEmpty(): 判断栈是否为空1.2 队列1.2.1 基本概念队列是一种先进先出（First-In-First-Out, FIFO）的数据结构，即最先进入的元素最先被访问。
1.2.2 基本操作- enqueue(x): 元素x入队- dequeue(): 移除队首元素- front(): 返回队首元素- rear(): 返回队尾元素- isEmpty(): 判断队列是否为空2：链表2.1 单链表2.1.1 基本概念单链表是一种线性结构，每个节点含有数据和指向下一个节点的指针。
2.1.2 基本操作- 初始化链表- 在链表头插入节点- 在链表尾插入节点- 在指定位置插入节点- 删除节点- 查找节点- 遍历链表2.2 双向链表2.2.1 基本概念双向链表是一种线性结构，每个节点含有数据、指向前一个节点的指针和指向后一个节点的指针。
2.2.2 基本操作- 初始化双向链表- 在链表头插入节点- 在链表尾插入节点- 在指定位置插入节点- 删除节点- 查找节点- 遍历链表3：树3.1 二叉树3.1.1 基本概念二叉树是一种数据结构，每个节点最多有两个子节点：左子节点和右子节点。
3.1.2 基本操作- 创建二叉树- 先序遍历- 中序遍历- 后序遍历- 层次遍历3.2 AVL树3.2.1 基本概念AVL树是一种自平衡的二叉搜索树，保证任意节点的左子树和右子树的高度差最多为1：3.2.2 基本操作- 插入节点- 删除节点- 查找节点- 遍历树4.1 图的表示4.1.1 邻接矩阵表示法4.1.2 邻接表表示法4.2 图的遍历4.2.1 深度优先搜索（DFS）4.2.2 广度优先搜索（BFS）4.3 最短路径算法4.3.1 Dijkstra算法4.3.2 Floyd-Warshall算法5：排序算法5.1 冒泡排序5.2 插入排序5.3 选择排序5.4 快速排序5.5 归并排序5.6 堆排序本文档涉及附件，请查看附件文件以获取更详细的信息。
数据结构复习题（精⼼整理）.docx数据结构复习题(打星号内容可以不考虑)习题1 绪论1.1单项选择题1. 数据结构是⼀门研究⾮数值计算的课程，它研究程序设计问题中数据元素的①、数据信息在计算机中的②以及⼀组相关的运算等的课程。
① A.操作对象 B ?计算⽅法 C.逻辑结构 D.数据映象② A.存储结构B.关系C.运算D.算法2. 数据结构DS(Data Struct)可以被形式地定义为DS= (D, R),其中D 是①的有限集合,R 是D 上的②有限集合。
① A.算法B.数据元素C.数据操作D.数据对象② A.操作B.映象C.存储D.关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A. 动态结构和静态结构B.紧凑结构和⾮紧凑结构C.线性结构和⾮线性结构D.内部结构和外部结构4. 算法分析的⽬的是①，算法分析的两个主要⽅⽽是②。
5. 计算机算法指的是①，它必具备输⼊、输出和②等五个特性。
①A.计算⽅法C. 解决问题的有限运算序列②A.可⾏性、可移植性和可扩充性 C. 确定性、有穷性和稳定性1.2填空题(将正确的答案填在相应的空中)1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构⼬，第⼀个结点前驱结点，其余每个结点有且只有个前驱结点；最后⼀个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没冇结点，其余每个结点冇仇只冇个直接前驱结点，叶⼦结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素Z 间存在关系，树形结构中元素之间存在关系，图形结构中元素Z① A.找出数据结构的合理性C.分析算法的效率以求改进② A.空间复杂性和时间复杂性C.可读性和⽂档性B. 研究算法⼬的输⼊和输出的关系D.分析算法的易懂性和⽂档性B. 」E 确性和简明性 B.排序⽅法D.调度⽅法B.可⾏性、确定性和有穷性 D.易读性、稳定性和安全性间存在关系。
数据结构-学习指南一、单项选择题1. 算法指的是（）A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（）A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点4.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B.头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改5.以下数据结构中哪一个是非线性结构？( d )A. 队列B. 栈C. 线性表D. 二叉树6.二叉树的第k层的结点数最多为( )A．2k-1 B.2K+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的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )A.nB.n/2C.(n+1)/2D.(n-1)/29.在一个单链表中,若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;10.栈的插入和删除操作在（）进行。
A.栈顶B.栈底C.任意位置D.指定位置11. 组成数据的基本单位是（）。
A.数据项B.数据类型C.数据元素D.数据变量12．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。
A.线性结构B.树型结构C.图型结构D.集合13．数组的逻辑结构不同于下列（）的逻辑结构。
A.线性表B.栈C.队列D.树14．二叉树中第i(i≥1)层上的结点数最多有（）个。
A.2iB.2iC.2i-1D.2i-115．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。
A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p16. 设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）A.6B.4C.3D.217.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。
A.100B.40C.55D.8018.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，8519.根据二叉树的定义可知二叉树共有（）种不同的形态。
A.4B.5C.6D.720.设有以下四种排序方法，则（）的空间复杂度最大。
A.冒泡排序B.快速排序C.堆排序D.希尔排序21. 数据结构是（）A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合22. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点23. 以下数据结构中哪一个是非线性结构？( )A.队列B.栈C.线性表D.二叉树24. 二叉树的第k层的结点数最多为( ).A.2k-1B.2K+1C.2K-1D. 2k-125. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。
A.nB.n/2C.(n+1)/2D.(n-1)/226. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个A.1B.2C.3D.427. 当待排序列基本有序时，下列排序方法中( )最好A.直接插入排序B.快速排序C.堆排序D.归并排序28. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）A.3B.4C.5D.129, 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。
A.O(log2n)B.O(1)C.O(n2)D.O(n)30, 设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。
A.abedfcB.acfebdC.aebdfcD.aedfcb二、填空题1. 在串S=“structure”中，以t为首字符的子串有个。
2．设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列3．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
4．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________ 5．深度为k的完全二叉树中最少有____________个结点。
6向量、栈和队列都是__ __结构，可以在向量的任意位置插入和删除元素；对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素和在_______删除元素。
7.数据的物理结构主要包括_____________和______________两种情况。
8.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
9.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
10.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________11.设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为__________________________________________________（设结点中的两个指针域分别为llink和rlink）。
（此题3分）12.通常从四个方面评价算法的质量：_________、_________、_________和_________。
13.称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同14.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有________个空指针域15.在快速排序、堆排序、归并排序中，_________排序是稳定的16.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
三、判断题1.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状( )2.层次遍历初始堆可以得到一个有序的序列。
( )3.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
( )4.线性表的顺序存储结构比链式存储结构更好。
( )5.快速排序是排序算法中平均性能最好的一种排序。
( )6.散列法存储的基本思想是由关键码的值决定数据的存储地址。
( )7.对于单链表形式的队列，其空队列的front指针和rear指针不相同。
( )8.一般树和二叉树的结点数目都不可以为0。
( )9.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据运算三个方面。
( )10.多维数组元素之间的关系，既不是线性的，也不是树形的。
( )11.线性表的顺序存储表示优于链式存储表示( )12.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续( )13.线性表的插入和删除总是伴随着大量数据的移动( )14.队列在程序调用是必不可少，因此递归离不开队列( )15.字符串’aababaaaba’的改进函数nextval数组值是0020200320 ( )16.若有向图有n个顶点，则其强连通分量最多有n个( )17.平衡二叉树一定是一棵完全二叉树( )18.若某内部排序算法不稳定，则该算法没有使用价值( )19.倒排文件的目的是为了多关键字查找( )20.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
( )21.抽象数据类型与计算机内部表示和实现无关( )22.线性表的逻辑顺序与物理顺序总是一致的( )23.每种数据结构都应具备三种基本运算：插入、删除和搜索( )24.二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点( )25.不用递归就不能实现二叉树的前序遍历( )26.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树( )27.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多( )28.中序遍历二叉排序树可以得到一个有序的序列( )29.调用一次深度优先遍历可以访问到图中的所有顶点( )30.二维数组是其数组元素为线性表的线性表( )四、简答题1. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。
2.画出下图所示的无向图的邻接表（顶点由A到H排列），并根据所得邻接表给出深度优先和广度优先搜索遍历该图所的顶点序列。
ABHCGFDE3. 已知L是带表头结点的非空单链表，且P结点既不是首结点，也不是尾结点，如下图所示：试从下表提供的语句中选择合适的条目组合到一起形成一个序列，完成题目要求的功能（例如：(1)(2)(3)(4)就是一个序列）a. 删除P结点的直接后继结点的语句序列是_________b. 删除P结点的直接前驱结点的语句序列是__________c. 删除P结点的语句序列是__________d. 删除首结点的语句序列是___________e. 删除尾结点的语句序列是__________注：Q是预先声明的指向链表节点的指针4. 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。
