数据结构期末复习题及答案2

更新时间:2024-01-06 03:47:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

一、 一、 单选题(每题 2 分,共20分)

1. 1. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

2. 2. 用链接方式存储的队列,在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改

3. 3. 以下数据结构中哪一个是非线性结构?( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

4. 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. 5. 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 6. 二叉树的第k层的结点数最多为( ).

A.2k-1 B.2K+1 C.2K-1 D. 2k-1

7. 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. 8. 对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O(1) B. O(n) C. O(1og2n) D. O(n2)

9. 9. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有( )个,

A.1 B.2 C.3 D.4

10. 10. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。

A.5 B.6 C.7 D.8 二、

二、 填空题(每空1分,共26分)

1. 1. 通常从四个方面评价算法的质量:_________、_________、_________

和_________。

2. 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为

________。

3. 3. 假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中

所含的结点数为__________个,树的深度为___________,树的度为_________。

4. 4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3

对应的后缀算式为_______________________________。

5. 5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和

右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。

6. 6. 对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_______个和________个。 7. 7. AOV网是一种___________________的图。

8. 8. 在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边。

9. 9. 假定一个线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分,使

得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。

10. 10. 向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度___________。

11. 11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为

________,整个堆排序过程的时间复杂度为________。

12. 12. 在快速排序、堆排序、归并排序中,_________排序是稳定的。 三、 三、 运算题(每题 6 分,共24分)

1. 1. 在如下数组A中链接存储了一个线性表,表头指针为A [0].next,试写

出该线性表。

A 0 1 2 3 4 5 6 7

data next

60 5 50 7 78 2 90 0 34 4 40 1 3 2. 2. 请画出图10的邻接矩阵和邻接表。

3. 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}; 图10

用克鲁斯卡尔算法得到最小生成树,试写出

在最小生成树中依次得到的各条边。

4. 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时,每加入一个数据后堆的变化。 四、 四、 阅读算法(每题7分,共14分)

1. 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. 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)

参考答案

一、 一、 单选题(每题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. 1. 正确性 易读性 强壮性 高效率 2. 2. O(n)

3. 3. 9 3 3

4. 4. -1 3 4 X * + 2 Y * 3 / - 5. 5. 2n n-1 n+1 6. 6. e 2e 7. 7. 有向无回路

8. 8. n(n-1)/2 n(n-1)

9. 9. (12,40) ( ) (74) (23,55,63) 10. 10. 增加1

11. 11. O(log2n) O(nlog2n) 12. 12. 归并 三、 三、 运算题(每题6分,共24分)

1. 1. 线性表为:(78,50,40,60,34,90)

?0?1??1??1?2. 2. 邻接矩阵:?01110?0101??1011??0101?1110??

邻接表如图11所示:

图11

3. 3. 用克鲁斯卡尔算法得到的最小生成树为:

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 4. 见图12

2 4 4 2 2

2 4 4 5 4 5

8 2

3 5

4 8 图12

四、 四、 阅读算法(每题7分,共14分) 1. 1. (1)查询链表的尾结点

(2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,…,an,a1) 2. 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

2 4 8 3 5

一、 选择题(每小题2分,共24分)

1.计算机识别、存储和加工处理的对象被统称为( A ) A.数据 B.数据元素 C.数据结构 D.数据类型 2.栈和队列都是( A )

A.限制存取位置的线性结构 B.顺序存储的线性结构 C.链式存储的线性结构 D.限制存取位置的非线性结构 3.链栈与顺序栈相比,比较明显的优点是( D )

A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 4.采用两类不同存储结构的字符串可分别简称为( B ) A.主串和子串 B.顺序串和链串

C.目标串和模式串 D.变量串和常量串

5. 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是:B

A. 110 B .108 C. 100 D. 120

6.串是一种特殊的线性表,其特殊性体现在:B A.可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符

7.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为: C

A. 2h B .2h-1 C. 2h+1 D. h+1 软件开发网 www.mscto.com

8.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确? A

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对

9.一个有n个顶点的无向图最多有多少边?C A. n B .n(n-1) C. n(n-1)/2 D. 2n

10.在一个图中,所有顶点的度数之和等于所有边数的多少倍?C A. 1/2 B .1 C. 2 D. 4

11.当在二叉排序树中插入一个新结点时,若树中不存在与待插入结点的关键字相同的结点,且新结点的关键字小于根结点的关键字,则新结点将成为( A ) A.左子树的叶子结点 B.左子树的分支结点 C.右子树的叶子结点 D.右子树的分支结点 软件开发网 www.mscto.com

12.对于哈希函数H(key)=key,被称为同义词的关键字是( D ) A.35和41 B.23和39

C.15和44 D.25和51

二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J,其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。(注意要写出具体步骤)(10分) 原理见课本128页

三、有图如下,请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先;C0-C1-C3-C4-C5-C2 宽度优先:C0-C1-C2-C3-C4-C5

四、有图如下,按Kruskal算法求出其最小生成树。要求写出完整的步骤。(10分) 原理见课本250页

五、给定线性表(12,23,45,66,76,88,93,103,166),试写出在其上进行二分查找关键字值12,93,166的过程。并写出二分查找的算法。(20分) 0 1 2 3 4 5 6 7 8

12 23 45 66 76 88 93 103 166 过程: mid=(0+8)/2=4 high=3,low=0 mid=1

high=0,low=0 mid=0(找到12) high=8,low=5,mid=6(找到93) high=8,low=7,mid=7 high=8 low=8 mid=8 算法:见课本84页上

六、知单链表的结点结构为 Data next

下列算法对带头结点的单链表L进行简单选择排序,使得L中的元素按值从小到大排列。 请在空缺处填入合适的内容,使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程,10分)

void SelectSort(LinkedList L) {

LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p->next; while(q!=NULL){ if( (2) )min=q; q=q->next; }

if( (3) ){ rcd=p->data; p->data=min->data; min->data=rcd; }

(4) ; } }

本题不会。嘿嘿。。。。

七、一个完整的算法应该具有哪几个基本性质?分别简要说明每一性质的含意。(5分) 输入:

四个基本性质:1.输入:有零个或多个有外部提供的量作为算法的输入 2:输出:算法产生至少一个量作为输出

3.:确定性:组成算法的每条指令是清晰的,无歧异的。

4.:有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的

八、何谓队列的\假溢\现象?如何解决?(5分)

队列的假溢现象是指数组实现的顺序队列中,队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。

九、说明并比较文件的各种物理结构。(6分) 顺序结构,链接结构,索引结构

本文来源:https://www.bwwdw.com/article/e2px.html

Top