31
试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
(一)
一、单选题(每题 2 分,共20分)
1. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素
B.都是先进后出 C.都是先进先出
D.没有共同点
2. 用链接方式存储的队列,在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改
C. 仅修改尾指针 D.头、尾指针可能都要修改
3. 以下数据结构中哪一个是非线性结构?( )
A. 队列 B. 栈 C. 线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
D. 二叉树
4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示。
A.688 B.678 C.692 D.696
5. 树最适合用来表示( )。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
6. 二叉树的第k层的结点数最多为( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. 若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( )
A. 1,2,3
B. 9,5,2,3
C. 9,5,3
D. 9,4,2,3
8. 对n个记录的文件进行快速排序,所需要的辅助存储空间大致为
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有( )个,
A.1 B.2 C.3 D.4
10. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
二、填空题(每空1分,共26分)
1. 通常从四个方面评价算法的质量:_________、_________、_________和_________。
2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为________。
3. 假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为__________个,树的深度为___________,树的度为_________。
4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3对应的后缀算式为_______________________________。
5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_______个和________个。
7. AOV网是一种___________________的图。
8. 在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边。
9. 假定一个线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10. 向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度___________。
11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中,_________排序是稳定的。
三、运算题(每题 6 分,共24分)
1. 在如下数组A中链接存储了一个线性表,表头指针为A [0].next,试写出该线性表。
A 0 1 2 3 4 5 6 7
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2. 请画出图10的邻接矩阵和邻接表。
3. 已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。
4. 画出向小根堆中加入数据4, 2, 5, 8, 3时,每加入一个数据后堆的变化。
四、阅读算法(每题7分,共14分)
1. LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L;L=L->next;p=L;
S1: while(p->next) p=p->next;
S2: p->next=q;q->next=NULL;
}
return L;
}
请回答下列问题:
(1)说明语句S1的功能;
(2)说明语句组S2的功能;
(3)设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<
data<<' ';
}
} 该算法的功能是:
五、算法填空(共8分)
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(itemdata)
return Find(______________,item);
else return Find(_______________,item);
}//if
}
六、编写算法(共8分)
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)
参考
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
(一)
一、单选题(每题2分,共20分)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
二、填空题(每空1分,共26分)
1. 正确性 易读性 强壮性 高效率
2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / -
5. 2n n-1 n+1
6. e 2e
7. 有向无回路
8. n(n-1)/2 n(n-1)
9. (12,40) ( ) (74) (23,55,63)
10. 增加1
11. O(log2n) O(nlog2n)
12. 归并
三、运算题(每题6分,共24分)
1. 线性表为:(78,50,40,60,34,90)
2. 邻接矩阵:
邻接表如图11所示:
图11
3. 用克鲁斯卡尔算法得到的最小生成树为:
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 见图12
图12
四、阅读算法(每题7分,共14分)
1. (1)查询链表的尾结点
(2)将第一个结点链接到链表的尾部,作为新的尾结点
(3)返回的线性表为(a2,a3,…,an,a1)
2. 递归地后序遍历链式存储的二叉树。
五、算法填空(每空2分,共8 分)
true BST->left BST->right
六、编写算法(8分)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时i中的值即为x结点个数
return i;
}//CountX
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
(二)
一、单选题(每小题2分,共8分)
1、在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为 ( )。
A n B n/2 C (n+1)/2 D (n-1)/2
2、在一个单链表中,若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;
3、 栈的插入和删除操作在( )进行。
A 栈顶 B 栈底 C 任意位置 D 指定位置
4、 由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )
A 24 B 71 C 48 D 53
二、填空题(每空1分,共32分)
1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。
2、一种抽象数据类型包括______________和_____________两个部分。
3、在下面的数组a中链接存储着一个线性表,表头指针为a[o].next,则该线性表为_________________________________________________
a 0 1 2 3 4 5 6 7 8
60
56
42
38
74
25
4
3
7
6
2
0
1
data
next
4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,判断链表为空的条件分别为________________和____________________。
5、用具有n个元素的一维数组存储一个循环队列,则其队首指针总是指向队首元素的___________,该循环队列的最大长度为__________。
6、当堆栈采用顺序存储结构时,栈顶元素的值可用———————表示;当堆栈采用链接存储结构时,栈顶元素的值可用_______________表示。
7、一棵高度为5的二叉树中最少含有_________个结点,最多含有________个结点;
一棵高度为5的理想平衡树中,最少含有_________个结点,最多含有_________个结点。
8、在图的邻接表中,每个结点被称为____________,通常它包含三个域:一是_____________;二是___________;三是_____________。
9、在一个索引文件的索引表中,每个索引项包含对应记录的_________和___________两项数据。
10、假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))),则树中所含的结点数为_________个,树的深度为_________,树的度为________, 结点H的双亲结点为________,孩子结点为_______________ 。
11、在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。
12、在对m阶的B_树插入元素的过程中,每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后,若该结点的索引项数等于______个,则必须把它分裂为_______个结点。
三、运算题(每小题6分,共24分)
1、已知一组记录的排序码为(46,79,56,38,40,80, 95,24),写出对其进行快速排序的每一次划分结果。
2、一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)= key % 13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。
3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。
4、已知一个图的顶点集V各边集G如下:
V = {0,1,2,3,4,5,6,7,8,9};
E = {(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3 ,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)}
当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
图
深度优先序列
广度优先序列
邻接矩阵表示时
邻接表表示时
四、阅读算法,回答问题(每小题8分,共16分)
1、假定从键盘上输入一批整数,依次为:78 63 45 30 91 34 –1,请写出输出结果。
# include < iostream.h>
# include < stdlib.h >
consst int stackmaxsize = 30;
typedef int elemtype;
struct stack {
elemtype stack [stackmaxsize];
int top;
};
# include “stack.h”
Void main ( )
{
stack a;
initstack(a);
int x;
cin >>x;
while (x! = -1) {
push (a, x );
cin >>x;
}
while (!stackempty (a))
cout < void BinTree ::
unknown (BinTreeNode*t) {
BinTreeNode< Type> *p =t, *temp;
if (p!=NULL) {
temp = p→leftchild;
p→leftchild = p→rightchild;
p→rightchild = temp;
unknown(p→leftchild);
undnown(p→rightchild);
}
}
该算法的功能是:________________________________
五、算法填空,在画有横线的地方填写合适的内容(10分)
对顺序存储的有序表进行二分查找的递归算法 。
int Binsch( ElemType A[ ],int low ,int high,KeyType K )
{
if (low <= high)
{
int mid = 1
if ( K= = A[ mid ].key )
return mid;
else if ( K < A[mid].key)
return 2
else
return 3
}
else
return 4
六、编写算法(10分)
编写算法,将一个结点类型为Lnode的单链表按逆序链接,即若原单链表中存储元素的次序为a1,……an-1,an,则逆序链接后变为, an,an-1,……a1。
Void contrary (Lnode * & HL)
试题(二答案)
一、单选题(每小题2分,共8分)
题 号
1
2
3
4
答 案
C
D
A
B
二、填空题(每空1分,共32分)
1: 集合、线性、树、图;
2: 数据描述、操作声名;
3: (38,56,25,60,42,74);
4: HL→next =NULL; HL=HL→next;
5: 前一个位置; n-1;
6: S.stack [S.top]; HS→data;
7: 5 31
8: 边结点、邻接点域、权域、链域;
9: 索引值域、开始位置域;
10: 10、3、3、B、I和J;
11: O(log2n)、O(nlog2n);
12: m 、 m - 1
三、运算题(每小题6分,共24分)
1、
划分次序
划分结果
第一次
[38 24 40] 46 [56 80 95 79]
第二次
24 [38 40] 46 [56 80 95 79]
第三次
24 38 40 46 [56 80 95 79]
第四次
24 38 40 46 56 [80 95 79]
第五次
24 38 40 46 56 79 [80 95]
第六次
24 38 40 46 56 79 80 95
2、
78
15
03
57
45
20
31
23
36
12
查找成功的平均查找长度:ASL SUCC=14/10= 1.4
3、此二叉树的后序遍历结果是:EDCBIHJGFA
4、
图
深度优先序列
广度优先序列
邻接矩阵表示时
0,1,2,8,3,4,5,6,7,9
0,1,4,2,7,3,8,6,5,9
邻接表表示时
0,4,3,8,9,5,6,7,1,2
0,4,1,3,7,2,8,6,9,5
四、阅读算法,回答问题(每小题8分,共16分)
1、 该算法的输入结果是:34 91 30 45 63 78
2、 该算法的功能是:交换二叉树的左右子树的递归算法。
五、算法填空,在画有横线的地方填写合适的内容(10分)
1是:(low + high)/2;
2是: Binsch(A,low,mid–1,K);
3是: Binsch(A,mid+1,high,K);
4是: -1;
六、编写算法(10分)
根据编程情况,酌情给分。
{
Lnode *P=HL;
HL=NULL;
While (p!=null)
{
Lnode*q=p;
P=p→next;
q→next=HL;
HL=q;
}
}
试题(3)
一、项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。
1.算法指的是( )
A.计算机程序 B.解决问题的计算方法
C.排序算法 D.解决问题的有限运算序列
2.线性表采用链式存储时,结点的存储地址( )
A.必须是不连续的
B.连续与否均可
C.必须是连续的
D.和头结点的存储地址相连续
3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( )
A.O(1) B.O(n) C.O(m) D.O(m+n)
4.由两个栈共享一个向量空间的好处是:( )
A.减少存取时间,降低下溢发生的机率
B.节省存储空间,降低上溢发生的机率
C.减少存取时间,降低上溢发生的机率
D.节省存储空间,降低下溢发生的机率
5.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为( )
A.front=front+1 B.front=(front+1)%(m-1)
C.front=(front-1)%m D.front=(front+1)%m
6.如下陈述中正确的是( )
A.串是一种特殊的线性表 B.串的长度必须大于零
C.串中元素只能是字母 D.空串就是空白串
7.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时,在最坏情况下的时间复杂度是( )
A.O() B.O(n) C.O(n2) D.O(n3)
8.一个非空广义表的表头( )
A.不可能是子表 B.只能是子表
C.只能是原子 D.可以是子表或原子
9.假设以带行表的三元组表表示稀疏矩阵,则和下列行表
0
2
3
3
5
对应的稀疏矩阵是( )
10.在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )
A.4 B.5 C.6 D.7
11.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )
A.e B.2e C.n2-e D.n2-2e
12.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )
A.O(n) B.O(e) C.O(n+e) D.O(n*e)
13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则所采用的排序方法是( )
A.选择排序 B.希尔排序 C.归并排序 D.快速排序
14.适于对动态查找表进行高效率查找的组织结构是( )
A.有序表 B.分块有序表 C.三叉排序树 D.线性链表
15.不定长文件是指( )
A.文件的长度不固定 B.记录的长度不固定 C.字段的长度不固定 D.关键字项的长度不固定
二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)。
16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的 无关,是独立于计算机的。
17.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head= 。
18.栈顶的位置是随着 操作而变化的。
19.在串S=“structure”中,以t为首字符的子串有 个。
20.假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中,其中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是 。
21.已知一棵完全二叉树中共有768结点,则该树中共有 个叶子结点。
22.已知一个图的广度优先生成树如右图所示,则与此相
应的广度优先遍历序列为 。
23.在单链表上难以实现的排序方法有 和 。
24.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为 。
25.多重表文件和倒排文件都归属于 文件。
三、解答题(本大题共4小题,每小题5分,共20分)
26.画出下列广义表的共享结构图形表示
P=(((z),(x,y)),((x,y),x),(z))
27.请画出与下列二叉树对应的森林。
28.已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示
a
b
c
d
e
(1)画出该图的图形;
(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。
29.已知一个散列表如下图所示:
35
20
33
48
59
0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法,探查序列为:
hi=(h(key)+*h1(key))%m =0,1,…,m-1
其中 h1(key)=key%11+1
回答下列问题:
(1)对表中关键字35,20,33和48进行查找时,所需进行的比较次数各为多少?
(2)该散列表在等概率查找时查找成功的平均查找长度为多少?
四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.下列算法的功能是比较两个链串的大小,其返回值为:
comstr(s1,s2)=
请在空白处填入适当的内容。
int comstr(LinkString s1,LinkString s2)
{//s1和s2为两个链串的头指针
while(s1&&s2){
if(s1->datedate)return-1;
if(s1->date>s2->date)return1;
① ;
② ;
}
if( ③ )return-1;
if( ④ )return1;
⑤ ;
}
①
②
③
④
⑤
31.阅读下面的算法
LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L;L=L->next;p=L;
S1: while(p->next) p=p->next;
S2: p->next=q;q->next=NULL;
}
return L;
}
请回答下列问题:
(1)说明语句S1的功能;
(2)说明语句组S2的功能;
(3)设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。
32.假设两个队列共享一个循环向量空间(参见右下图),
其类型Queue2定义如下:
typedef struct{
DateType data[MaxSize];
int front[2],rear[2];
}Queue2;
对于i=0或1,front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空,实现第i个队列的入队操作。
int EnQueue (Queue2*Q,int i,DateType x)
{//若第 i个队列不满,则元素x入队列,并返回1;否则返回0
if(i<0||i>1)return 0;
if(Q->rear[i]==Q->front[ ① ]return0;
Q->data[ ② ]=x;
Q->rear[i]=[ ③ ];
return1;
}
①
②
③
33.已知二叉树的存储结构为二叉链表,阅读下面算法。
typedef struct node {
DateType data;
Struct node * next;
}ListNode;
typedef ListNode * LinkList ;
LinkList Leafhead=NULL;
Void Inorder (BinTree T)
{
LinkList s;
If(T){
Inorder(T->lchild);
If ((!T->lchild)&&(!T->rchild)){
s=(ListNode*)malloc(sizeof(ListNode));
s->data=T->data;
s->next=Leafhead;
Leafhead=s;
}
Inorder(T->rchild);
}
}
对于如下所示的二叉树
(1)画出执行上述算法后所建立的结构;
(2)说明该算法的功能。
五、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题(本题共10分)
34.阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x)
{//1和h分别为数据区的下界和上界
int i,j,t;
i=1;j=h;
while(i=x)j--;
while(i=x)i++;
if(inext
②s2=s2->next
③s2(或s2!=NULL或s2&&!s1)
④s1(或s1!=NULL或s1&&!s2)
⑤return 0
31.(1)查询链表的尾结点
(2)将第一个结点链接到链表的尾部,作为新的尾结点
(3)返回的线性表为(a2,a3,…,an,a1)
32. ①(i+1)%2(或1-i)
②Q->rear[i]
③(Q->rear[i]+)%Maxsize
33.(1)Leafhead
F
H
G
D
∧
(2)中序遍历二叉树,按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表)。
五、算法设计题(本题共10分)
34.(1)该函数的功能是:调整整数数组a[]中的元素并返回分界值i,使所有<x的元素均落在a[1..i]上,使所有≥x的元素均落在a[i+1..h]上。
(2)int f(int b[],int n) 或 int f(int b[],int n)
{ {
int p,q; int p,q;
p=arrange(b,0,n-1,0); p=arrange(b,0,n-1,1);
q= arrange(b,p+1,n-1,1); q= arrange(b,0,p,0);
return q-p; return p-q;
} }
试题(4)
一、选择题(20分)
1.组成数据的基本单位是( )。
(A) 数据项
(B) 数据类型
(C) 数据元素
(D) 数据变量
2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A是( )。
(A) 线性结构
(B) 树型结构
(C) 图型结构
(D) 集合
3.数组的逻辑结构不同于下列( )的逻辑结构。
(A) 线性表
(B) 栈
(C) 队列
(D) 树
4.二叉树中第i(i≥1)层上的结点数最多有( )个。
(A) 2i
(B) 2i
(C) 2i-1
(D) 2i-1
5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为( )。
(A) p->next=p->next->next
(B) p=p->next
(C) p=p->next->next
(D) p->next=p
6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是( )。
(A) 6
(B) 4
(C) 3
(D) 2
7.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为( )。
(A) 100
(B) 40
(C) 55
(D) 80
8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为( )。
(A) 3
(B) 4
(C) 5
(D) 1
9.根据二叉树的定义可知二叉树共有( )种不同的形态。
(A) 4
(B) 5
(C) 6
(D) 7
1. 10. 设有以下四种排序方法,则( )的空间复杂度最大。
(A) 冒泡排序
(B) 快速排序
(C) 堆排序
(D) 希尔排序
二、填空题(30分)
1. 设顺序循环队列Q[0:m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;。
2. 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________。
3. 设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域。
4. 设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为______________________________________。
5. 设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点。
6. 设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。
7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________。
8. 设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________。
9. 下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。
int index(char s[ ], char t[ ])
{
i=j=0;
while(inext=p->next; s->next=s
5. n, 2e 6. m=2e 7. CBA 8. 4,16 9. i-j+1,0 10. n-1
三、应用题
1. 链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA。
2. 哈夫曼树略,WPL=78
3. (18,5,16,19,21,23),(5,16,21,19,18,23)
4. 线性探测:
链地址法:
5. 深度:125364,广度:123456,最小生成树T的边集为E={(1,4),(1,3),(3,5),(5,6),(5,6)}
四、算法设计题
1. 设计判断单链表中结点是否关于中心对称算法。
typedef struct {int s[100]; int top;} sqstack;
int lklistsymmetry(lklist *head)
{
sqstack stack; stack.top= -1; lklist *p;
for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;}
for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0);
return(1);
}
2. 设计在链式存储结构上建立一棵二叉树的算法。
typedef char datatype;
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
void createbitree(bitree *&bt)
{
char ch; scanf("%c",&ch);
if(ch=='#') {bt=0; return;}
bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch;
createbitree(bt->lchild); createbitree(bt->rchild);
}
3. 设计判断一棵二叉树是否是二叉排序树的算法。
int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void inorder(bitree *bt)
{
if (bt!=0)
{inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);}
}
试卷(五)
一、选择题(24分)
1.下面关于线性表的叙述错误的是( )。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( )个空指针域。(A) 2m-1
(B) 2m