数据结构试题10
一.选择题
1.在关系R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,
09>,<09,10>}中,没有后继的数据元素是〖 B 〗。
A) 05 B) 10 C) 01 D) 09
2.下面用二元组表示的数据结构,属于何种结构〖 C 〗。
A={K,R}
K={a,b,c,d,e,f}
R={r}
r={
,,,,}
A) 集合结构B) 线性结构C) 树形结构D) 图形结构
3.对数据类型有关概念的描述中,以下错误的是〖 C 〗。
A)不同的数据类型的取值范围不同
B)不同的数据类型的允许施加的操作不同
C)数据类型与数据的结构无关
D)数据类型与数据结构都是对数据的描述
4.算法是解决特定问题的方法,在其应具备的特性中,有关的叙述错误的是〖 B 〗。
A)必须有使一个算法结束的条件
B)其中的某些步骤可以不确定的含义
C)每一个步骤都必须是有效的,可完成的
D)没有输出的算法是无意义的
5.算法的空间间复杂度表示形式不包括〖 C 〗。
A)空间复杂度是一个常量是表示为O(1)
B)空间复杂度与以2为底的n的对数成正比时表示为O(log2 n)
C)以计算公式表示的空间复杂度形式
D)空间复杂度与n成线性关系时表示为O(n)
6.在对线性表的操作中,使用语句:
for(int i=0;i,,,,,,,}中,其中的叶结点是()。
2.在计算机中存储数据时,不仅要存储数据本身,而且要存储数据()。
3.线性表采用()时,结点和结点内部的存储空间可以是不连续的。
4.在具有头结点的链式存储结构中,头指针指向链表中的()。
5.在线性表的链式存储中,元素之间的逻辑关系是通过()决定的。
6.一个循环队列存在于A[M]中,假定队首和队尾指针分别为front和rear,判断队满的条
件为()。
7.用单链表表示的链式队列的队头在链表的()位置。
8.栈运算的具体实现时,栈的()不同,其算法描述也不同。
9.队列运算的具体实现时,队列的()不同,其算法描述也不同。
10.一棵有n个结点的满二叉树有()个叶子。
11.一棵有n个结点的满二叉树的深度为()。
12.设一棵树进行线索化,就是对该二叉树进行()的过程。
13.在后序线索化的线索二叉树中,在空的指针域中存放的是指向其()结点的指针。
14.有n个结点并且其高度为n的二叉树有( )个。
15.对于一棵具有n个结点的二叉树,对应二叉链表中的指针有( )个指针空闲着。
16.具有n个结点的完全二叉树若按层次从上到下、从左到右对其编号(根结点为1),则编号最小的分支结点序号是( )。
17.在一棵二叉排序树上实施()遍历后,其关键字就是一个有序表。
18.一棵深度为h的B- 树,任一个叶子结点所处的层数为()。
19.平衡二叉排序树上任一结点的平衡因子是()。
20.对n个元素进行冒泡排序时,最少的比较次数是()。
三.名词解释题
2.算法的正确性
3.线性表的顺序存储
4.栈顶元素
5.循环队列
6.树的度
四.简答题
1.说明稀疏矩阵存储结构中的十字链接存储方式。
2.给出对一个后缀算术表达式:24 8 + 3 * 4 10 7 - * /@求值过程中的数值栈的变化情况。
3.用一维数组存放一棵完全二叉树:ABCDEFGHIJKL,给出后序遍历该二叉树的结点序号。
4.以{4、5、6、7、8}作为叶子结点的权值构造哈夫曼树,画出这棵哈夫曼树。
5.说明散列查找的线性探察法的处理方法。
五.完成填空题
1.快速排序的递归算法如下:
viod QuickSort( ElemType A[], int s, int t)
{ int i = s, j = t + 1;
ElemType x = A[s];
do
{ do i++; while(〖〗 < x.stn);
do j--; while( A[j].stn > 〖〗);
if( i < j)
{ ElemType temp = A[i];
A[i] = 〖〗;
A[j] = temp;
}
}while(〖〗);
A[s] = A[j]; A[j] = x;
if( s < j-1) 〖〗( A, s, j-1);
if( j+1 < t) QuickSort( A, j+1, t);
}
2.二路归并算法:
void TwoMerge(ElemType A[], ElemType R[], int s, int m, int t)
调用二路归并算法的一趟二路归并的算法如下:
void MergePass(ElemType A[], ElemType R[], int n, int len)
{ int p = 0;
while(〖〗 <= n – 1)
{ 〖〗( A, R, p, p + len - 1, p + 2 * len -1);
p += 〖〗;
}
if(〖〗 < n – 1)
TwoMerge( A, R, p, p + len - 1, n -1);
else
for( int i = p; i <= n – 1; i++)
〖〗 = A[i];
}
3. 对二叉树进行中序线索化的算法如下:
void InThread(TtreeNode * HT)
{ static TtreeNode * pre = NULL;
if( HT != 〖〗)
{ if( HT -> ltag == 0) InThread(〖〗);
if( pre != NULL && pre -> rtag == 1)
pre -> right = 〖〗;
if( HT -> left == NULL)
{ HT -> ltag = 1;
ht -> left = pre;
}
if( HT -> right == 〖〗)
HT -> rtag = 1;
Pre = HT;
if( HT -> rtag == 0) InThread(〖〗);
}
}
六.综合应用题
1.给出线索二叉树的抽象数据类型描述,其中的操作包括:对二叉树进行中序线索化
InTread、在中序线索二叉树求结点p的中序后继InorderNext、和中序遍历ThInorder。
2.给出一个无向连通图的抽象数据类型描述,其中的操作包括:对图进行深度优先搜索
DepthFirstSch、广度优先搜索BreadthFirstSch、图的最小生成树的普里姆算法Prim。
浙公网安备 33021202002483