下载文档原格式
国开期末考试《数据结构与算法》机考试题及答案(第10套)一、选择题（每题2分，共20分）1. 数据的逻辑结构是指（）。
A. 数据元素之间的逻辑关系B. 数据元素本身的特点C. 数据的存储结构D. 数据的加工处理过程答案：A. 数据元素之间的逻辑关系二、填空题（每题2分，共20分）2. 在栈中，最后进入的数据元素总是首先被（）。
答案：弹出三、判断题（每题2分，共20分）3. 线性表是一种线性结构。
（）答案：正确四、简答题（每题10分，共30分）4. 简述顺序存储结构和链式存储结构的特点。
答案：顺序存储结构：数据元素在物理位置上连续存储，可以通过下标快速访问。
五、编程题（共50分）5. 编写一个函数，实现单链表的排序。
（20分）答案：class ListNode:def __init__(self, value):self.value = valueself.next = Nonedef sort_linked_list(head):if not head or not head.next:return headpivot = head.valueless = less_head = ListNode(None) equal = equal_head = ListNode(None) greater = greater_head = ListNode(None)current = headwhile current:if current.value < pivot:less.next = currentless = less.nextelif current.value == pivot:equal.next = currentequal = equal.nextelse:greater.next = currentgreater = greater.nextcurrent = current.nextless.next = less_head.nextequal.next = equal_head.next greater.next = greater_head.nextreturn merge_sorted_lists(sort_linked_list(less_head.next),sort_linked_list(equal_head.next), sort_linked_list(greater_head.next))def merge_sorted_lists(l1, l2, l3):dummy = ListNode(None)current = dummywhile l1 and l2 and l3:if l1.value < l2.value and l1.value < l3.value:current.next = l1l1 = l1.nextelif l2.value < l1.value and l2.value < l3.value:current.next = l2l2 = l2.nextelse:current.next = l3l3 = l3.nextcurrent = current.nextif l1:current.next = l1 elif l2:current.next = l2 else:current.next = l3 return dummy.next。
数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 编写代码的时间B. 代码的长度C. 执行代码所需的时间D. 执行代码所需的指令条数2. 下列关于队列的描述，错误的是（）。
A. 队列是先进先出（FIFO）的线性表B. 队列允许在一端进行插入操作C. 队列的插入操作称为入队D. 队列的删除操作称为出栈3. 对于长度为n的有序数组，使用二分查找法查找一个元素的平均时间复杂度是（）。
A. O(n)B. O(n^2)C. O(log n)D. O(1)4. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是（）。
A. 栈B. 队列C. 链表D. 数组5. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决冲突的方法？（）A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法6. 一个完全二叉树共有700个节点，它的最大节点数是（）。
A. 700B. 701C. 1400D. 14017. 快速排序算法的最坏情况发生在（）。
A. 每次选择的基准都是最大值B. 数据已经有序C. 数据已经完全逆序D. 所有数据元素相等8. 在一个具有n个节点的二叉搜索树中，最坏情况下查找一个元素的时间复杂度是（）。
A. O(n)B. O(log n)C. O(n^2)D. O(1)9. 堆排序算法中，将一个堆调整为最大堆或最小堆的过程称为（）。
A. 堆调整B. 堆构建C. 堆分解D. 堆维护10. 以下哪个不是B树的特性？（）A. 所有键值都存储在内部节点和叶子节点中B. 所有叶子节点都在同一层上C. 每个内部节点至多有m个子节点D. 每个内部节点的非叶子子节点都至少有m/2个子节点二、简答题（每题5分，共30分）1. 什么是递归？请举例说明递归算法的应用场景。
2. 请简述图的邻接矩阵和邻接表两种存储方式的优缺点。
3. 解释什么是平衡二叉树，并说明它为什么在实际应用中很重要。
【期末复习】数据结构期末综合练习及参考答案四（算法分析题）数据结构（本科）期末综合练习四（算法分析题）1. 指出算法的功能并求出其时间复杂度。
int fun(int n){int i =1,s=1;while(s< bdsfid="67" p=""><>return i;}功能为：时间复杂度为：2. 指出算法的功能并求出其时间复杂度。
void matrimult(int a[M][N], int b[N][L], int c[M][L]){ //M、N、L均为全局整型常量int i, j, k;for ( i = 0; i < M; i++ )for ( j = 0; j < L; j++ )c[i][j] = 0;for( i =0; i <m;i++)< bdsfid="79" p=""></m;i++)<>for(j=0;j<l;j++)< bdsfid="81" p=""></l;j++)<>for(k=0;k<n;k++)< bdsfid="83" p=""></n;k++)<>c[i][j]+=a[i][k]*b[k][j];}功能为：时间复杂性为：3. 针对如下算法，回答问题：若数组A[n] = {12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0}, n = 12，给出算法执行后数组A[n]的状态。
templatevoid unknown ( T A[ ], int n ) {int free = 0;for ( int i = 0; i < n; i++ )if ( A[i] != 0 ) {if ( i != free ) {A[free] = A[i];A[i] = 0;}free++;}}算法执行的结果4. 设顺序表SeqList具有下列操作：int Length( ) const; //计算表长度并返回，若表为空则返回0T Remove( ); //删除当前表项并返回其值，置下一表项为当前表项T First( ); //取表中第一个表项的值并返回，并置为当前表项T Next( ); //取当前表项后继表项的值并返回，//并把此后继表项置为当前表项若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26}，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的变化。
数据结构复习题第一章概论一、选择题1、研究数据结构就是研究( D )。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是( A )。
A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是( D )。
A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。
A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是( C )。
fori0;im;i++forj0;jn;j++a[i][j]i*j;A. Om2B. On2C. Om*nD. Om+n6、算法是( D )。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。
A. OnB. Onlog2nC. On2D. Olog2n8、下面程序段的时间复杂度为( C )。
i1;whileinii*3;A. OnB. O3nC. Olog3nD. On39、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。
A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是( A )。
is0;whilesni++;s+i;A. OnB. On2C. Olog2nD. On311、抽象数据类型的三个组成部分分别为( A )。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。
数据结构与算法期末考试题及答案一、选择题1. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）A. 最小生成树算法B. 广度优先搜索算法C. 最大流算法D. 关键路径算法2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）A. 公司拥有的资源B. 公司所面对的决策选择C. 公司内部的组织结构D. 公司的竞争对手3. 算法的计算时间复杂度O(log2n)中的n表示（A）A. 求解问题规模B. 求解算法所处理的数据量C. 求解问题中所涉及的参数量D. 求解算法所进行的求解步骤4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）A. O(1)B. O(n)C. O(log2n)D. O(n2)5. 以下关于贝尔曼-福特算法的描述错误的是（A）A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离D. 贝尔曼-福特算法可以解决单源最短路径问题二、简答题1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。
拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。
拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。
计算机学院数据结构与算法分析期末试题答案一、单项选择题（每小题2 分，共20分）1．在下面给出的链式存储结构中，能在O(1)时间内完成在指定结点p之前插入元素x 的结构是为（）。
A）单向链表B）单向循环链表C）带表头的单向链表D）双向循环链表参考答案：D）2．栈应用的典型事例是（）。
A）排队B）查找C）归并D）用“算符优先法”进行表达式求值参考答案：D）3．一般情况下，将递归算法转换成等价的非递归算法应该设置（）。
A）栈B）队列C）堆栈或队列D）数组参考答案：A）4．（）是C语言中"abcd32lABCD"的子串。
A）abed B）d2lAB C）"abcABC" D）"21AB"参考答案：D）5．有一矩阵为A[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a-1,4的地址为（）。
A）111 B）112 C）113 D）125参考答案：B）6．从L=((apple,pear),(banana,orange))中，取出pear元素的表达式为（）。
A）head(tail(L)) B）head(head(tail(L)))C）tail(head(tail(L))) D）head (tail (head(L)))参考答案：D）7．若一个具有N个顶点，K条边的无向图是一个森林（N＞K），则该森林中必有（）棵树。
A）K B）N C）N-K D）1【分析】因为一棵具有n个顶点的树有n-1条边，因此设此森林中有m棵树，每棵树具有的顶点数为v i（l≤i≤m），则：v1+v2+…+v m=N (1)(v1-1)+(v2-1)+…+(v m-1)=K (2)由(1)-(2)可知N-K为森林所含树的棵数。
参考答案：C）8．采用分块查找时，如某线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块，则每块包含（）个结点时，平均查找长度最小。
《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（ D ）。
A．循环队列 B. 链表 C. 哈希表 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 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（ B ）A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）5．对于有n 个结点的二叉树, 其高度为（ D ）A．nlog2n B．log2n C．⎣log2n⎦|+1 D．不确定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)/2 D．0 E．n28．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>},G的拓扑序列是（ A ）。
试题一一、单项选择题〔每小题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〕6 D〕8〔5〕由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为〔〕。
A〕11B〕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、BC〕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,zD〕h,g,m,p,a,n,q,x,z二、〔本题8分〕对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 算法程序的长度B. 算法执行时所需要的基本运算次数C. 算法程序中的语句数D. 算法程序中的指令数答案：B2. 线性表的顺序存储结构和链式存储结构相比，其主要优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态申请D. 存储空间可以预先分配答案：D3. 在一个长度为n的顺序表中，采用二分查找法查找第k小的元素，最坏情况下需要比较的次数是（）。
A. nB. n/2C. log2(n+1)D. log2n答案：D4. 一个栈的入栈序列为1, 2, 3, 4, 5，下列序列中哪一个不可能是栈的输出序列（）。
A. 5, 4, 3, 2, 1B. 3, 2, 4, 1, 5C. 5, 4, 2, 3, 1D. 1, 2, 5, 3, 4答案：D5. 在二叉树的前序遍历、中序遍历和后序遍历中，根节点总是（）。
A. 第一个被访问B. 第二个被访问C. 第三个被访问D. 最后一个被访问答案：A6. 在一个有n个顶点的无向图中，其边的最大数量是（）。
A. n(n-1)/2B. n(n+1)/2C. n^2D. 2n答案：A7. 哈夫曼编码是一种（）。
A. 静态编码B. 动态编码C. 无损编码D. 有损编码答案：C8. 一个图的邻接矩阵表示法中，若顶点i到顶点j有一条边，则矩阵的第i行第j列的元素为（）。
A. 1B. 0C. 边的权重D. 顶点j的度数答案：C9. 在数据库中，关系模式R(U, F)，其中U={A, B, C, D}，F={(A, B)→C, C→D}，下列哪个关系模式是R的候选键（）。
A. {A, B}B. {A, C}C. {B, C}D. {C, D}答案：A10. 快速排序算法的平均时间复杂度是（）。
A. O(n^2)B. O(nlogn)C. O(n^3)D. O(n)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，递归算法的时间复杂度通常可以用______来描述。
3、试分析稀疏矩阵的存储方式，应该采用什么方式存储，为什么？并说明如下稀疏矩阵应该如何存储，并给出行优先的存储组表。
4、对关键码序列：43,21,68,7,35,49,85,31。
请给出二叉排序树的构建过程。
参考答案一、单项选择题（每小题2分）C B C B A //D D A B C二、简答题（每小题10分）1、答案：1）将顺序队列的存储区假想为是一个头尾相连的圆环，通常把这种特殊结构的队列称为循环队列。
队头、队尾指针加1时从MaxSize-1直接进到0，可用取模(余数)运算实现。
2）在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量为MaxSize。
当有元素要加入队列时，若rear=MaxSize-1（初始时rear=0），但front不为0 ，即指队列中还有空余的空间，但元素不能进队列，则发生队列的假溢出现象，为解决此问题，引入循环队列。
2、答案：完全二叉树是指叶子结点只能出现在最下一层和次下一层，并且最下一层的叶子结点只分布在左边。
完全二叉树一般采用顺序存储结构，因为顺序存储结构可以节约存储空间，也能够表示出完全二叉树的逻辑关系。
三、算法分析和设计（共20分）1）（8分）答案：将num由十进制转换为r进制，由低到高依次进栈，然后再出栈。
2）定义其结点类public class Node<T> { }(12分)；public class Node<T> {T xingming,phone,address;Node<T> next;public Node( ){ next=null; }public Node(T obj1,T obj2,T obj3, Node<T> n){ xingming =obj1; phone =obj2; address =obj3; next=n; }public T getXingming (){ return xingming; }public Node<T> getNext(){ return next; }}四、综合题（每小题10，共40分）1、答案：（15）（48，26，32，73，25，36，45，12，68）初态（15，48）（26，32，73，25，36，45，12，68）（15，26，48）（32，73，25，36，45，12，68）（15，26，32，48）（73，25，36，45，12，68）（15，26，32，48，73）（25，36，45，12，68）（15，25，26，32，48，73）（36，45，12，68）（15，25，26，32，36，48，73）（45，12，68）（15，25，26，32，36，45，48，73）（12，68）（12，15，25，26，32，36，45，48，73）（68）（12，15，25，26，32，36，45，48，68，73）2、参考答案（其中一种答案）3、（10分）答案：1）如果采用二维数组存储稀疏矩阵，浪费大量存储空间存放零元素。
单选题（每题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. 一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是( C )A.231 C.312B.321 D.1236. 若需要利用形参直接访问实参时，应将形参变量说明为（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）___。
5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0到3，则二维数组W的数据元素共占用＿128__个字节。
W中第6行的元素和第4列的元素共占用__44_个字节。
若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址__108_。
7. 二叉树是指度为2的___有序___树。
一棵结点数为N的二叉树，其所有结点的度的总和是___n-1____。
8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_有序序列__。
对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__后缀表达式____。
9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。
10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。
其余类推，则A[i]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。
11.在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。
12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。
三、运算题（每题6分，共24分）0 0 0 0 1 1. 1. 已知一个0 0 0 0 065稀疏0 1 0 0 0矩阵如下0 0 0 0 2所示5 0 0 0 0试：0 0 7 0 0（1）写出它的三元组线性表；（2）给出三元组线性表的顺序存储表示。
2. 2. 设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
3. 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；4. 4.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
图6四、阅读算法（每题7分，共14分）1. 1. intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)(1) 指出该算法的功能；(2)(2) 该算法的时间复杂度是多少？2. 2. 写出下述算法的功能：voidAJ(adjlistGL,inti,intn){QueueQ; InitQueue(Q); cout<<i<<''; visited[i]=true;QInsert(Q,i);while(!QueueEmpty(Q)){intk=QDelete(Q);edgenode*p=GL[k];while(p!=NULL){intj=p->adjvex;if(!visited[j]){cout<<j<<'';visited[j]=true;QInsert(Q,j);}p=p->next;}}}五、算法填空（共8分）如下为二分查找的非递归算法，试将其填写完整。
IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key) returnmid; //查找成功，返回元素的下标elseif(K<[mid].key)______________________________________; //在左子表上继续查找else__________________________________; //在右子表上继续查找}return-1; //查找失败，返回-1}六、编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法。
ElemTypeDeleFront(LNode*&HL)参考答案6 5 5 1. 7. 有序n-11 5 1 2. 8. 有序序列后缀表达式（或逆波兰式）3 2 -1 3. 9. 2nn-1 n+14. 10. 2i+1 2i+2 (i-1)/24 5 -2 5. 11. 开放定址法链接法5 1 5 6. 12. 快速归并6 3 7图7一、1.1. 三、（1）运算题（每题 6分，共24分）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)图 8（2） 三元组线性表的顺序存储表示如图 7示。
2. 2.如图8所示。
3. 3.DFS ：BFS ： 4. 4.二、 拓朴排序为： 4 3 6 5 7 四、 阅读算法（每题 2 1 7分，共14分）1. 1.(1)判断n 是否是素数（或质数）（2）O （n） GL 所表示的图。
2.2. 功能为：从初始点v i 出发广度优先搜索由邻接表 三、 五、算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1四、 六、 编写算法（8分）ElemTypeDeleFront(LNode*&HL) {if(HL==NULL){cerr<<"空表"<<endl;exit(1);}LNode*p=HL;HL=HL->next;ElemType temp=p->data;deletep;returntemp; }单选题（每题 2分，共20分）1. 栈和队列的共同特点是 ( A )。
A. 只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时(D). A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？(D)A.队列B.栈C. 线性表D.二叉树4.设有一个二维数组 A[m][n]，假设A[0][0] 存放位置在 644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间， 问A[3][3](10)存放在什么位置？脚注 (10)表示用 10进制表示。
C A ．688B ．678C ．692D ．6965.树最适合用来表示(C)。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k 层的结点数最多为(D).A ．2k-1B.2K+1C.2K-1D.2k-17. 若有18个元素的有序表存放在一维数组 A[19] 中，第一个元素放 A[1]中，现进行二分查找，则查找 A ［3］的 比较序列的下标依次为 ( D ) A.1，2，3 B.9，5，2，3C.9，5，3D.9，4，2，39. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H （K ）=K%9作为散列函数，则 散列地址为1的元素有（ D ）个，A ．1B ．2C ．3D ．410. 设有6个结点的无向图，该图至少应有 ( A )条边才能确保是一个连通图。
A.5B.6C.7D.8填空题1. 通常从四个方面评价算法的质量： 正确性 易读性 强壮性 高效率2. 一个算法的时间复杂度为 3 2 2，其数量级表示为 O(n) (n+nlog2n+14n)/n 4. 后缀算式923+-102/-的值为___-1_。
中缀算式（3+4X ）-2Y/3 对应的后缀算式为___34X*+2Y*3/-__。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
