北京大学数据结构与算法信科数算2007秋期末考试题

一、（本题10分）（1）简述线性表的两种存储结构的主要优缺点及各自适用的场合。

（2）在折半查找和表插入排序中，记录分别应使用哪种存储结构，并用一句话简述理由。

答：（1）顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除操作将引起元素移动，降低效率。

对于链式存储，元素存储采取动态分配，利用率高。

缺点是须增设指针域，存储数据元素不如顺序存储方便。

优点是插入与删除操作简单，只须修改指针域。

（2）在折半查找中，记录使用顺序存储，可以快速实现中点的定位；在表插入排序中，记录使用静态链表，可以降少移动记录的操作。

二、（本题15分）在带头结点的非空线性链表中，试设计一算法，将链表中数据域值最小的那个结点移到链表的最前面，其余各结点的顺序保持不变。

要求：不得额外申请新的链结点。

解：程序如下：typedef struct node {int data;struct node * next;}Node,*LinkList;void MinFirst(LinkList L){Node *p,*q,*ptrmin;if(L->next == NULL) return; //空表ptrmin = L; //ptrmin指向当前最小结点的前一个结点p = L->next;//p指向当前结点的前一个结点while(p->next!=NULL) {if( p->next->data < ptrmin->next->data ) ptrmin = p;p = p->next;}//q指向最小结点，并从链表中删除q = ptrmin->next; ptrmin->next = q->next;q->next = L->next; L->next = q; //q指向的最小结点插入到链表头}三、（本题15分）编写函数判断一棵二叉树是否不含有度为1的结点，若任何结点的度都不为1，则返回TRUE，否则返回FALSE。

山西财经大学2008—2009学年第 2学期期末算法与数据结构课程试卷（A卷）1、本卷考试形式为闭卷，考试时间为两小时。

2、考生不得将装订成册的试卷拆散，不得将试卷或答题卡带出考场。

3、考生只允许在密封线以外答题，答在密封线以内的将不予评分。

4、考生答题时一律使用蓝色、黑色钢笔或圆珠笔（制图、制表等除外）。

5、考生禁止携带手机、耳麦等通讯器材。

否则，视为作弊。

一、单项选择题（共10小题，每题 1分，共计10 分）二、判断题（共10小题，每题1 分，共计10分）三、简答题（共4小题，每题5 分，共计20分）四、应用题（共8小题，1-6小题必做，7、8任选一，1-2每小题5 分，3-8每小题6分，共计40分）五、算法设计题（1、2小题任选一，3、4小题任选一，每题10分，共计20分）一、单项选择题（共10小题，每题 1分，共计10 分）1．若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列的存储方式中最节省时间的是( )。

A．单链表B．仅有头指针的单循环链表C．双向链表D．仅有尾指针的单循环链表2. 下面给出的算法段是要把一个p所指新结点，插入到非空双向链表中，作为该双链中q所指结点的前驱结点，能正确完成要求的算法段是（）。

A．p->llink=q->llink; B．q->llink=p;p->rlink=q; p->rlink=q;q->llink->rlink=p; q->llink->rlink=p;q->llink=p; p->llink=q->llink;C．p->rlink=q; D．p->rlink=q;p->llink=q->llink; p->llink=q->llink;q->llink=p; q->rlink=p;q->llink->rlink=p; q->llink->rlink=p;3．下列选项中，（）是非线性数据结构。

试题一一、单项选择题（每小题2分，共20分）（1）以下数据结构中哪一个是线性结构？（）A）有向图B）队列C）线索二叉树D）B树（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。

A）p=q; p->next=q; B）p->next=q;q->next=p;C）p->next=q->next; p=q; D）q->next=p->next;p->next=q;（3）（）不是队列的基本运算。

A）在队列第i个元素之后插入一个元素B）从队头删除一个元素C）判断一个队列是否为空D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。

A）14 B）5 C）6D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。

A）11 B）35 C）19 D）53 以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。

A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）该二叉树结点的中序遍历的序列为（）。

A）A、B、C、D、E、G、F B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E（8）该二叉树的按层遍历的序列为（）。

A）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面关于图的存储的叙述中正确的是（）。

A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（）A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。

绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合＿、线性结构＿、树型结构＿、图状结构＿。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储＿、链式存储＿、索引存储＿、散列存储＿。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（B ）。

A、正确性B、有穷性C、确定性D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）。

A、正确性B、有穷性C、确定性D、可行性3、算法原则上都是能够有机器或人所完成的。

整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D）A、正确性B、有穷性C、确定性D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。

什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。

选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。

2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

3、数据的逻辑结构分几种？存储结构又有哪几种？数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。

有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。

线性表1、一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是( B)。

数据结构试题（C卷）学号：姓名：评分： . 一．单项选择题(30分)1.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_______次序的遍历实现编号。

a．先序 b．中序 c．后序 d．从根开始的层次遍历2.在有n个叶子结点的哈夫曼树中，其结点总数为_________。

a.不确定b. 2nc. 2n+1d. 2n-13.任何一个无向连通图的最小生成树_______。

a.只有一棵b. 有一棵或多棵c. 一定有多棵d. 可能不存在4.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_________。

a. 98b. 99c. 50d. 485.下列排序算法中，______算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

a．堆排序 b．冒泡排序 c．快速排序 d．SHELL排序6.下图为AOV网，其可能的拓扑有序序列为________。

a. CAEBDF;b. CABFED;c. CABEDFd. CEABFD7.将上图看作无向图，其从C 出发的广度优先遍历结果为_______：a. CABDEFb. CDFEBAc. CDEAFBd. CABFED则结点E在二叉树的第层。

a、1b、2c、3d、49.下列序列中，_______是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。

a. [da，ax，eb，de，bb]ff[ha，gc]b. [cd，eb，ax，da]ff[ha，gc，bb]c. [gc，ax，eb，cd，bb]ff[da，ha]d. [ax，bb，cd，da]ff[eb，gc，ha]10.二分查找法要求查找表中各元素的键值必须是________排列。

a. 递增或递减b. 递增c. 递减d. 无序二．填空作图简答题（共70分）：1.如下图已知哈希表为空，哈希函数为H（Key）= Key MOD 11, 冲突解决方法分别用线性探测再散列和二次探测再散列。

单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 36.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。

A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。

A．行号B．列号C．元素值D．非零元素个数10.从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的_联系。

当结点之间存在M对N（M：N）的联系时，称这种结构为__图__。

2.队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。

3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。

4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___O（1）__，在表尾插入元素的时间复杂度为___ O（n）___。

北京大学信息科学技术学院考试试卷考试科目：数据结构与算法A 姓名：学号：考试时间： 2016 年 1 月 6 日任课教师:以下为试题和答题纸(答案写在答题纸上)，包括本页共 6 页。

第一题填空题（每空1分，共8分）1.设无向图G = (V,E)中V={1, 2, 3, 4, 5, 6, 7}，E={(1,2), (1,3), (2,3), (4,5), (3,6),(4,7), (5,7)}。

则图G包含的不同生成森林的个数为_____9____。

注释：其中若两个生成森林的边集不同，则认为它们是不同的生成森林。

2.若对下面的无向图以1为起点运行单源最短路径的Dijkstra算法，则在Dijkstra算法的过程中，每一步依次被选出的顶点依次是_1,2,4,3,7,5,6,8,9,10___。

若忽略边权，以6为起点进行一次广度优先周游，将得到一棵广度优先搜索的生成树。

设仅包含一个结点的树高度为1，则该生成树的高度为_3_，树的最深层结点集合为_1,5,7,10__。

第一空回答2,4,3,7,5,6,8,9,10也算对3.用某种排序方法对序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序时，若序列的变化情况如下，则所采用的排序方法为__快速排序__。

25, 84, 21, 47, 15, 27, 68, 35, 2020, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 844.假设Shell排序的增量序列是(2k, 2k-1, … , 2, 1)，其中k=[log2 n]。

若待排序序列是正序的（已经排好）或逆序的，则Shell排序的时间复杂度分别是__O(nlogn)_、O(nlogn)_。

各0.5分5.设输入的关键码满足k1>k2>…>k n，缓冲区大小为m。

2. 已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散 列表长度为 15，用线性探查法解决冲突构造这组关键码的散列表。散列函 数为：h(k)= k %13。请回答： 1) 构造顺序插入上述关键码集合后的散列表；
2) 下一记录放到第 11 个槽和第 7 个槽中的概率分别是多少？ 下一条记录放在第 11 个槽中的概率是 2/13 放到第 7 个槽中的概率是 9/13
学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大 学的学术声誉。
以下为试题和答题纸，共 页。
得分 一、选择填空题（每空 1 分，共 11 分）（答案写在答题纸上）
1. G 是一个非连通无向图，共有 21 条边，则图 G 至少有 8 个顶点。 2. 对于一个包含 N（N>1）个顶点的图，假定任意两点间最多只有一条边，
7. A[N][N]是对称矩阵，现将下三角矩阵按行存储到一维数组 T[N(N+1)/2]中
（包括对角线），则对任一上三角元素 A[i][j]其对应值（0 <= i <= j < N）在
T[k]中的下标 k 是 j(j+1)/2+i
。
8. 在一棵空 AVL 树中，顺序插入如下关键码：{5, 9, 4, 2, 1, 3, 8}，请问全部 插入后，在等概率下查找成功的平均检索长度为 17/7 。
9. 已知广义表 C=(c, (d, A), B, e)，则广义表 C 的深度为 2
，
tail(head(tail(C)))的运算结果为 (A) 。
得分 二、简答辨析题（每题 3 分，共 15 分）
1. 如果要找出一个具有 n 个元素集合中的第 k (1≤k≤n)个最小元素，所学过的 排序方法中哪种最适合？给出实现的基本思想。 答案：在具有 n 个元素的集合中找第 k 个最小元素，应使用快速排序算法。 其基本思想如下：设 n 个元素的集合用一维数组表示，其第一个元素的下 标为 1，最后一个元素下标为 n。以第一个元素为“枢轴”，经过快速排序的 一次划分，找到“枢轴”的位置 i，若 i = k，则该位置的元素下标为 n；若 i > k 则在 1 至 i-1 间继续进行快速排序的划分；若 i < k 则在 i+1 至 n 间继续 进行快速排序的划分。这种划分一直进行到 i = k 为止，第 i 位置上的元素 就是第 k 个最小元素。

数据结构与算法分析—期末复习题及答案1. 简答题a) 什么是数据结构？数据结构是一种组织和存储数据的方法，它涉及到将数据元素以及它们之间的关系组织成一种特定的方式，以便于有效地访问和操作。

b) 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。

线性结构包括数组、链表、栈和队列等；非线性结构包括树和图等。

c) 什么是算法？算法指的是完成特定任务或求解特定问题的一系列步骤或指令。

算法需要满足正确性、可读性、健壮性和高效性等特性。

d) 算法的时间复杂度和空间复杂度是什么？时间复杂度是指在算法执行过程中所需的时间资源，空间复杂度是在算法执行过程中所需的存储空间资源。

2. 选择题a) 在排序算法中，如果待排序序列已经基本有序，以下哪个算法的性能最优？选项：A. 快速排序B. 冒泡排序C. 插入排序D. 归并排序正确答案：C. 插入排序b) 以下哪个数据结构通常用于实现递归算法？选项：A. 数组B. 链表C. 栈D. 队列正确答案：C. 栈3. 填空题a) 计算以下给定二叉树的前序遍历结果：A/ \B C/ \ / \D E F G正确答案：A, B, D, E, C, F, Gb) 给出选择排序算法的伪代码：```for i in range(len(arr)):min_index = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]```4. 案例题假设有一个包含100个元素的整数数组arr，对该数组进行排序后返回结果。

请使用任意一种排序算法，并给出算法的时间复杂度。

解答示例：我们可以使用快速排序算法来对数组进行排序，时间复杂度为O(nlogn)。

下面是该算法的Python代码实现：```def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)arr = [5, 3, 2, 8, 1, 4, 7, 6, 9]sorted_arr = quick_sort(arr)print(sorted_arr)```运行结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]5. 解答题请描述并给出示例说明动态规划算法的应用场景。

数据结构期末考试题及答案一、单项选择题（每题3分，共30分）1. 在数据结构中，最基本的数据结构是（）。

A. 线性结构B. 树形结构C. 图形结构D. 非线性结构答案：A2. 栈是一种特殊的线性表，其特点是（）。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C3. 在二叉树中，度为2的结点数为n，度为1的结点数为m，度为0的结点数为p，则m的值为（）。

A. n-1B. n+1C. p-1D. p+1答案：A4. 哈希表的构造方式是（）。

A. 线性结构B. 树形结构C. 链式结构D. 索引结构答案：D5. 在图的遍历过程中，深度优先搜索算法采用的是（）。

A. 队列B. 栈C. 链表D. 树答案：B6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C7. 以下哪个排序算法是不稳定的排序算法（）。

A. 冒泡排序B. 快速排序C. 归并排序D. 堆排序答案：B8. 在数据库中，索引通常采用哪种数据结构（）。

A. 线性表B. 树形结构C. 图形结构D. 散列表答案：B9. 以下哪个不是二叉搜索树的性质（）。

A. 左子树上所有结点的值都小于它的根结点的值B. 右子树上所有结点的值都大于它的根结点的值C. 左、右子树也分别为二叉搜索树D. 所有结点的值都相等答案：D10. 在图的表示方法中，邻接矩阵适用于表示（）。

A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A二、填空题（每题4分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法在执行过程中需要的___________。

答案：存储空间2. 堆排序中，调整堆的过程称为___________。

答案：堆化3. 在图的遍历中，广度优先搜索使用的辅助数据结构是___________。

答案：队列4. 一个长度为n的链表，删除第i个元素的时间复杂度是___________。

•信息学院《数据结构与算法A》期末考试1. 考试时间和地点考试时间：2018.01.03周三上午8:30 – 10:30考试地点：等通知2. 考试题型填空、选择、辨析与简答、数据结构或算法的设计和分析、数学证明注意：（1）数据结构/算法设计与分析题只要写明基本思想、无歧义即可，必要时加上足够的注释。

（2）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并简单说明算法中用到的重要函数的功能、入口参数、出口参数。

3. 考试范围和重点7-12章，以本文最后的内容为复习重点，尤其是★标出部分为重中之重。

考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。

4. 考场安排和注意事项1) 没有正式选课的旁听同学，请不要来考场。

2) 请随身带好您的学生证(或其他可以证明身份的证件)，笔和涂改工具参加考试。

3) 考试形式为闭卷，可以使用计算器。

4）考前10分钟，请大家把书包、课本、讲义、作业本、自带的草稿纸等放在教室前面的讲台和窗台上，只需要留下学生证(或其他可以证明身份的证件)，笔和涂改工具。

教室清理干净后，可以提前5分钟发放试卷(带有草稿纸和答题纸，可以撕下来)，从前排向后排发放。

注意在试卷纸和有效答题纸上写上姓名和学号，并且一定要在试卷纸的诚实答题宣言旁边的姓名和学号栏签名（否则，试卷计零分）。

5) 我们统一发草稿纸，不够可以随时举手要。

6) 请大家注意考场纪律，不要交头接耳，私下讨论。

考试时对试题有疑问，可以举手，待监考老师来到旁边时，再请向监考老师询问。

7）考试时间为120分钟，中间不休息。

提前15分钟提醒大家整理试卷，注意写好姓名和学号。

8) 监考老师宣布“考试时间到”以后，请大家停笔（不停笔的同学，监考老师有权没收试卷并宣布作废），把草稿纸和答题纸放在试卷上面，使姓名和学号朝外（诚实答题宣言旁边的姓名和学号朝向最外面），对折以后放在桌面上。

监考老师收卷清点无误，并宣布“全班同学都可以离开了”以后方可集体离开。

北京信息科技大学2007~2008学年第2学期《数据结构》课程期末考试试卷(A卷)授课系别：计算机学院_适用班级：计0601-0602考试形式：_闭卷_班级：姓名：学号：注意事项：1、试题答案全部以顺序写在答题纸上一、判断题（每小题1分，共10分）(1) 一些表面上很不相同的数据可以有相同的逻辑结构。

( )(2) 线性表的逻辑顺序与物理顺序总是一致的。

( )(3) 算法原地工作的含义是指不需要任何额外的辅助空间。

( )(4) 任何无环的有向图，其结点都可以排在一个拓扑序列里。

( )(5) 栈是一种后进先出的线性存储结构。

( )(6) 队列是一种先进先出的线性存储结构。

( )(7) 在k叉树的第i层上至少有2i-1个结点。

( )(8) 数据结构的形式定义为一个二元组Data_Structure=(D, S)。

( )(9) 在数据结构中，与所使用的计算机无关的是数据的逻辑结构。

( )(10) 二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序是不变的。

( )二、单项选择题（每小题2分，共20分）（1）链表不具备的特点是（）。

A. 不必事先估计存储空间B. 可随机访问任一节点C. 插入删除不需要移动元素D. 所需空间与其长度成正比（2）一个栈的进栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。

A. edcbaB. decbaC. dceabD. abcde（3）串可看作是一种特殊的线性表，其特殊性体现在（）A. 可以顺序存储B. 可以链式存储C. 数据元素可以是多个字符D. 数据元素是一个字符（4）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序（5）采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A. nB. n/2C. (n+1)/2D. (n-1)/2（6）一个线性表是n个（）的有限序列（n≥0）,n称为线性表的长度。

《数据结构与算法》期末考试试题及答案一、选择题A、94,32,40,90,80,46,21,691.在逻辑上可以把数据结构分A.P->NE某T=Q->NE某T;FREE(Q);B、32,40,21,46,69,94,90,80成（A）B.Q->NE某T=P;FREE(Q);C21,32,46,40,80,69,90,94A.线性结构和非线性结构D、90,69,80,46,21,32,94,40B.动态结构和静态结构C.Q->NE 某T=P->NE某T;FREE(Q);21.若用冒泡排序对关键字序C.紧凑结构和非紧凑结构D.P->NE某T=S;S->NE某T=P;列（18,16,14,12,10,8）进行从D.内部结构和外部结构2.单链表中各结点之间的地址（C）A.必须连续B.部分必须连续C.不一定连续D.以上均不对3.在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（B）个元素。

A、n-iB、n-i+1C、n-i-1D、i4.插入和删除操作只能在一端进行的线性表，称为（C）。

A.队列B.线性表C.栈D.循环队列5、队列是仅允许在（）进行插入，而在（）进行删除。

(A)A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首6.链表适合于（A）查找。

A.顺序B.二分C.随机D.顺序或二分7.数据的基本单位是（A）。

A.数据元素B.数据结构C.数据项D.数据对象8.下列哪个不是算法的特性（B）。

A.有穷性B.可数性C.可行性D.确定性9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（B）。

A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(C）。

A.311B.328C.332D.31311.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。

2014年春季北大《数据结构与算法B》期末考试模拟试卷(本试卷只是给同学们看看考题形式和范围，难度与真实考卷稍有差别)学号______________ 姓名_______________ 教师/教室_____________(注：如米标明，本试卷题屮的下标、位.胃.都从o开始计数)一、填空题(共32分)1.设有字符串变量String A = “This”，C=“just”，D=“ajest”，请计算下列表达式：(1)A+B+D= “Thisisajest” ；(2) D.IndexOf(“t’’) = _2_:(求字符在字符串中的第一个位置)(3) B.StrlengthQ = __ 2 __(4) D.SubStr(U2)= _ _________ (注：1为起始下标，2为子串长度)【4分】2.顺序査找n个元素的顺序表，若查找成功，则比较关键字的次数S多为n 次;若查找失败，则比较关键字的次数最多为_n_,最少力_次。

【3分】3.在散列函数H (key) =key%p中，p值最好取_____ 质数(或素数) _____ 。

【1分】4.对于下图邻接表所对应的有向图，试写出：【2分】(1)从顶点①出发进行深度优先遍历结果_1，2, 3, 4, 5_;(2)从顶点①出发进行广度优先遍历结果_1，2, 3, 4, 55.当图中各条边上的权值_都相等_时，宽度优先搜索算法可用来解决单源最短路径问题？【2分】6.—棵有n个结点的满二叉树有i个度为1的结点、有(n-1)/2个分支 <非终端)结点；该满二叉树的深度最大为_(n-l)/2_,最小为int(log2n)gcLlog2nJo (独根树深度为0)【4分】7.对于给定的n个元素，可以构造出的逻辑结构有线性结构，树形结构，阁形结构，_集合_四种。

【2分】8.下面程序段的时间复杂度力_O(n)_。

(n〉l)［大O表示法］【2分】sum=l；for (i=0;sum<n;i++) sum十=1;9.对于最大堆65 43 59 24 37 48 57 12 23 28 5 3,删除掉最大元素后，堆中元素为59,43,57,24,37,48,3,12,23,28,5【2 分】6510.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码｛18,73,10,5,68,99,27,41,51,32,25 ｝构造出一棵二叉搜索树，该二叉树转换为森林，则该森林的层次遍历序列为18 73 99 10 68 5 27 41 51 25 32【4分】11.用S表示入栈操作，X表示岀栈操作，若元素入栈的顺序为12345,为了得到13542出栈顺序，相应的S和X的操作串为_SXSSXSSXXX_。

《数据结构与算法》复习题一、填空题1、在树形结构中，树根结点没有，其余每个结点有且只有个前驱结点；叶子结点没有，其余每个结点的后续结点数可以任意多个。

2、在图形结构中，每个结点的前驱结点数和后续结点数可以。

3、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q = p->next;p->next= ;4、稀疏矩阵的压缩存储方式有：和。

5、n个顶点的连通图至少有边。

6、设一棵完全二叉树有700 个结点，则共有个叶子结点。

7、快速排序平均情况下的时间复杂度为。

8、数据的运算最常用的有5 种，它们分别是、、、、。

9、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6 依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1 ，则栈的容量至少应该是。

10、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为____。

11、具有n个结点的完全二叉树的深度是。

12、在具有n 个单元的循环队列中，队满时共有个元素。

13、快速排序其最坏情况下的时间复杂度为。

二、选择题1、非线性结构是数据元素之间存在一种：( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系2、数据结构中，与所使用的计算机无关的是数据的（）结构；A. 存储B. 物理C. 逻辑D. 物理和存储3、若以{4,5,6,7,8} 作为权值构造哈夫曼树，则该树的带权路径长度为（）。

A. 67B. 68C. 69D. 704、将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（）。

A. 98B. 99C. 50D. 485、在线索二叉树中， t 所指结点没有左子树的充要条件是（B ）。

A. t->left==NULLB. t->ltag==1C. t17->ltag==1&&t->left==NULLD. 以上都不对6、表达式A*(B+C)/(D-E+F) 的后缀表达式是（ C ）。

北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间： 2008年 1 月 9 日 教师: 张铭、赵海燕、王腾蛟、宋国杰以下为试题和答题纸，共 4 页。

题号 一 二 三 四 五六 七 八 总分 分数 阅卷人第 1 页一、（共30分，每空3分）填空1. 1．无向图G=(V , E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c,f), (f, d), (e, d)}，对该图进行深度优先遍历，得到的顶点序列正确的是____。

A ．a,b,e,c,d,fB ．a,c,f,e,b,dC ．a,e,b,c,f,dD ．a,e,d,f,c,b2. 下图中的强连通分量的个数为________个。

3. 设有向图G 如下:写出所有拓扑序列:___________________________________________添加一条弧________________________之后, 则仅有唯一的拓扑序列. 4. 请问下面哪些操作在已排序数据上实施比在无序的数据上快 ？A ．找最小值 B. 计算算术平均值 C. 找中位数 D. 找出现次数最多的值5. 序列{15，142，51，68，121，46，57，575，60，89，185 }按最低位优先法进行基数排序，进行一次分配和收集后得到的序列 。

6. 设输入的关键码满足k 1>k 2>…>k n ，缓冲区大小为m ，用最小值堆进行置换-选择排序方法可产生____个初始归并段。

7. 在包含n 个关键码的线性表中进行顺序检索，若检索第i 个关键码的概率为p i , 且分布如下：n n n n p p p p 21,21,....,41,211121====−−成功检索的平均检索长度是_______________。

8. 假设计算机系统有2048个字节的磁盘块，要存储的每一条记录中4个字节是关键码，磁盘指针4个字节，64个字节是数据字段。

《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（A．循环队列 B.链表 C.D ）。

哈希表 D.栈2.算法的时间复杂度取决于（ A ）A．问题的规模 B.待处理数据的初态 C. A 和 B D.计算机 cpu3.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 54 3 24.有关静态链表的叙述： (1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第 i 个元素的时间与 i 无关。

(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（ B ）A ．（1），（2）B．（1）C．（1），（2）,(3)D.（2）5．对于有 n 个结点的二叉树 , 其高度为（ D ）A．nlog 2n B．log2n C．? log2n? |+1D．不确定6．从下列有关树的叙述中, 选出正确的叙述（ C ）A．二叉树中每个结点有两个子结点, 而树无此限制 , 因此二叉树是树的特殊情况。

B．当 K≥1 时高度为 K 的二叉树至多有2k-1个结点。

C．哈夫曼树是带权路径最短的树, 路径上权值较大的结点离根较近。

D．在二叉树中插入结点, 该二叉树便不再是二叉树。

7．设无向图的顶点个数为n，则该图最多有（ B ）条边。

A． n-1 B ．n(n-1)/2 C ． n(n+1)/2D．0E．n28．已知有向图 G=(V,E)，其中 V={V1,V 2,V 3,V 4,V 5,V 6,V 7} ，E={<V1,V 2>, <V1,V 3>, <V1,V 4 >, <V2,V 5>, <V3,V 5>, <V3,V 6>, <V4,V 6>,<V5,V 7>, <V6,V 7>},G 的拓扑序列是（ A ）。