黑龙江大学信息科学与技术学院第二学历自学考试考试试卷数据结构与算法 课程（形式：闭卷）一、选择题（共20题，每题1分，共20分）1． 在关系R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}中，数据元素05，06的前驱是〖 〗。
A) 01 B) 02 C) 03 D) 042．下面用二元组表示的数据结构，属于何种结构〖 〗。
A={K,R}K={a,b,c,d,e,f}R={r}r={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<f,e>,<f ,d>,<f,c>,<f,b>,<f,a>}A) 集合结构B) 线性结构 C) 树形结构 D) 图形结构3．在数据类型概念的定义中，数据类型是一种对数据的各方面的描述。
其中包括〖 〗。
A) 数据的来源 B) 数据的排列顺序C) 允许对数据施加的操作 D) 数据的应用4． 顺序存储的线性表L=(a 1,a 2,……,a n )，下列说法正确的是〖 〗。
A) 每个元素都有一个直接前驱和一个直接后继B) 线性表中至少要有一个元素C) 表中元素的排列顺序必须是由小到大或由大到小D) 元素的存储顺序与逻辑顺序相同5．计算一个算法的时间复杂度是指〖 〗。
A)统计一个算法执行时，实际占用的计算机时间B)计算一个算法中的循环步骤的次数C)统计算法中进行简单操作的次数D)一个算法运行时间的相对量度6．在一个长度为n的顺序表中，删除第i个元素(1≤i≤n+1)时，须向前移动的元素的个数是〖〗。
A) n-i B) n-i+1 C) n-i-1 D) i7．对顺序存储的线性表进行排序的有关叙述中，错误的是〖〗。
A) 排序是按照元素的值或某个域的值排列元素，使之成为有序表B)线性表的排序不改变表中元素及其各个域的值C)插入排序算法的时间复杂度的数量级是O(n2)D)对线性表排序不改变元素的存储顺序8．对单链表表示法，以下说法错误的是〖〗。
A)数据域用于存储线性表的一个数据元素B)指针域用于存放一个指向本结点所含数据元素的直接后继所在的节点的指针C)所有数据通过指针的链接而组织成单链表D)NULL称为空指针，他不指向任何节点只起标志作用9．以下有关双链表的叙述中，说法错误的是〖〗。
A)从表中任一结点出发都能通过前后移动操作扫描整个链表B)只有从头结点开始才能扫描链表中全部结点C)双链表的特点是查找结点的前趋和后继都很容易D)某一结点的存储位置同时存放在其前趋结点的后继指针域中，及后继结点的前趋指针域中10．在有关稀疏矩阵的存储结构的叙述中，以下错误的是〖〗。
A)稀疏矩阵的顺序存储是对其相应的三元组线性表进行顺序存储B)稀疏矩阵的链接存储是对其相应的三元组线性表进行链接存储C)稀疏矩阵的存储是对其非零元素构成的线形表进行顺序存储D)稀疏矩阵的十字链接存储是对其相应的三元组线性表进行十字链接存储11．对于栈的入栈和出栈操作，假定同一输入序列中不含相同的元素，以下叙述中正确的是〖〗。
A)不同的入栈和出栈组合，将得到不同的输出序列B)输出序列的排列顺序可以是输入序列中元素的全排列C)输出序列的排列顺序只能是与输入序列完全相反的D)输出序列的排列顺序只能是与输入序列完全相同的12．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为A B C * + D E / -，其前缀形式为〖〗。
A) – A + B * C / D E B) – A + B * C D / EC) - + * A B C / D E D) - + A * B C / D E13．一个输入序列abcd经过一个栈到达输出序列，则下面错误的输出序列的是〖〗。
A) bcad B) cbda C) dabc D) acbd14．已知队列Q的输入序列为0,1,2,3,4,5,6，执行插入和删除元素的顺序是：Qinsert(Q,0)，Qinsert(Q,1)，Qinsert(Q,2)，Qdelete(Q)，Qinsert(Q,4)，Qdelete(Q)，Qinsert(Q,5)，Qdelete(Q)，Qinsert(Q,6)，此时队头和队尾指针分别指向〖〗。
A) 3，4 B) 4，5 C) 3，6 D) 2，615．在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为〖〗。
A) (n+1)/2 B) (n-1)/2 C) [n/2」D] n/216．在一棵哈夫曼树中，带权叶子结点的权值分别为4,8,6,7,4，其中离根结点最近的结点的权值是〖〗。
A) 8 B) 7 C) 6 D) 517．在一棵具有n个结点的二叉树第i层上，最多具有〖〗。
A) 2 i个结点B) 2 i-1个结点C) 2 i-1个结点 D. 2 n个结点18．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是〖〗。
A)空或只有一个结点的二叉树B)任意结点无左子树的二叉树C)高度等于其结点数的二叉树D)任意结点无右子树的二叉树19．对给出的一组关键字{14，5，19，20，11，19}。
若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，则采用的排序算法是〖〗。
A) 快速排序B) 二路归并排序C) 简单选择排序D) 希尔排序20．一组记录的关键字为{45，80，55，40，42，85}，利用快速排序法并以第一个记录为基准得到的第一趟划分结果是〖〗。
A) 40，42，45，55，80，85 B) 42，40，45，80，55，85C) 42，40，45，55，80，85 D) 42，40，45，85，55，80二、填空题（共20题，每空1分，共20分）21．在关系r={<a1,a2>,<a1,a3>,<a2,a4>,<a2,a5>,<a3,a6>,<a3,a7>,<a4,a8>,<a4,a9>}中，其中除叶结点外，每一个结点都有（）后继结点。
22．数据的存储结构，即数据在计算机中的存储方式通常有：顺序、（）、索引、散列等多种形式。
23．求单链表长度的时间复杂性的数量级为（）。
24．在线性表的顺序存储中，元素之间的逻辑关系是通过（）决定的。
25．顺序存储结构属于（），链式结构属于动态结构。
26．在一个广义表中，其数据元素有（）和子表之分。
27．用循环链表表示的队列长度为n，则入队的时间复杂度是（）。
28．向栈中插入一个元素时，首先应判断栈是否（）。
29．中缀表达式转换成后缀表达式的规则是：把每个运算符都移到它的两个（）的后面，并删除所有括号。
30．一棵有n个结点的满二叉树有（）个度为1的结点。
31．某二叉树的后序遍历的结点顺序是C,D,B,G,F,E,A，则该二叉树的根结点是（）。
32．一棵二叉树的深度等于左子树和右子树中的（）加1。
33．一棵具有n个结点的二叉树，若有m个叶子结点，则该二叉树上度为1的结点有（）个。
34．对于一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其结点的编号为（）。
35．具有n个结点的完全二叉树若按层次从上到下、从左到右对其编号（根结点为1），则编号最小的叶子结点序号是( )。
36．哈夫曼树的带权路径长度( )的树，通常权值较大的结点离根最近。
37．一个无序序列可以通过构造一棵（）树而变成一个有序序列，构造树的过程就是对无序序列进行排序的过程。
38．在一棵有n个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为（）。
39．在二叉排序树插入新结点时，不必移动其它结点，仅需使树叶结点的指针由（）指向新结点即可。
40．二分查找的存储结构仅限于（）的顺序存储结构。
41．数据元素42．表头结点43．中缀表达式44．二叉树的线索化45．连通图46．用文字给出遍历一个单链表的算法描述。
47．简述队列的结构及操作。
48．画出一个具有16个结点的完全二叉树49．已知一个后缀算术表达式为：25 x a a b + * b + * @ 写出对应的中缀表达式。
50．索引查找是在线性表的索引存储结构的基础上进行的，请说明索引存储的基本思想。
51．索引项的类型定义：struct IndexItem{ IndexKeyType index;int start;int length;};顺序存储的索引表的类型定义：typedef IndexItem indexlist[ILMSize];数组的类型定义：typedef ElemType manlist[MaxSize];分块查找的算法如下：int Block(manlist A, indexlist B, int m, keyType K){ int i,j;for( i =0; i<m; i++)if( K1 == 〖〗)break;if( i == m )return –1;j = 〖〗;while( j < B[i].start + 〖〗)if( K ==〖〗)break;elsej++;if( j <〖〗+ B[i].length)return j;elsereturn –1;}52．散列表的类型定义如下：typedef ElemType hashlist1[HashMaxSize];采用开放定址法，向散列表插入一个元素的算法如下：int Insert( hashlist1 HT, int m, ElemType item){ int d = H(item.key, m);int temp = d;while(〖〗!= NullTag){ d =〖〗;if(〖〗) return 0;}〖〗= item;〖〗;}53．假定一个线性表为：A=（18,75,60,43,54,90,46,66,29,84），给出直接选择排序的过程中的每次选择并交换后的变动情况示意图。