当前位置:首页 >> IT/计算机 >>

数据结构试题2(有答案)

试题 2
一、 单选题(每题 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 10. 10. 设有 6 个结点的无向图,该图至少应有( 连通图。 A.5 B.6 C.7 D.8 D.4 )条边才能确保是一个

一、 二、 填空题(每空 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 3 60 5 2. 3. 2. 3. 50 7 78 2 90 0 34 4 40 1

图 10

请画出图 10 的邻接矩阵和邻接表。 已知一个图的顶点集 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.

画出向小根堆中加入数据 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<<BT->data<<' '; } } 该算法的功能是: 四、 五、 算法填空(共 8 分) 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item<BST->data)

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 34X*+2Y*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 ?0 ? 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0? ? 1 ? 1? ? 1? 0? ?

2. 2. 邻接矩阵: 邻接表如图 11 所示:

3. 3.

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

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 4. 见图 12
4 2 4 4 2 4 2 5 8 2 3 8 4 5 4 2 5 8 4 3 2 5

图 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资料.doc
数据结构试题及答案修2资料 - 试卷一 一、 单选题(每题 2 分,共 20 分) 1. 对一个算法的评价,不包括如下()方面的内容。 A.健壮性和可读性 2. B....
数据结构试题及答案(10套最新).doc
数据结构试题及答案(10套最新) - 一、 单选题(每题 2 分,共 20 分)
数据结构试题(含答案).doc
数据结构试题(含答案) - 数据结构试题(含答案) 1.数据逻辑结构包括 线性结
数据结构试题及答案(免费).doc
数据结构试题及答案(免费) - 数据结构试卷(十一) 一、选择题(30 分) 1
数据结构期末考试试题及答案.doc
数据结构期末考试试题及答案 - 数据结构期末考试试题及答案 一、选择题 1. 评价一个算法时间性能的主要标准是( )。 A、算法易于调试 B、算法易于理解 C、算法...
数据结构试题及答案.doc
数据结构试题及答案 - . 《数据结构》自考复习思考试题○10 一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分) 在每小题列出的四个备选项中只有...
大学数据结构期末考试试题(有答案).doc
大学数据结构期末考试试题(有答案) - 数据结构复习题 一、单选题(每小题 2 分,共 12 分) 1.在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的...
数据结构试题集(包含答案_完整版).doc
数据结构试题集(包含答案_完整版) - 第一章 概论 一、选择题 1、研究数据结
2017《数据结构》期末考试试题及答案.doc
21 第 1 页共 23 页 《数据结构》期末考试试题及答案 1 一、 单选题(每题 2 分,共 20 分) )。 1. 栈和队列的共同特点是( A.只允许在端点处插入和...
数据结构试题集(包含答案 完整版).doc
数据结构试题集(包含答案 完整版)_工学_高等教育_教育专区。数据结构试题 包含...三、综合题 1、将数量级 O(1),O(N),O(N2),O(N3),O(NLOG2N),O(...
数据结构考试试题及答案.doc
数据结构考试试题及答案 - 数据结构考试试题及答案 【篇一:数据结构试题及答案数据结构试卷(二)... 5 数据结构试卷(三)......
计算机数据结构习题2附答案..doc
计算机数据结构习题2附答案. - 第六章 图 1、填空题 一个有 n 个结点的无向图中,所有顶点的度数之和等于所有边数之和的 _2__ 倍。 一个有 n 个结点...
数据结构试题库答案.doc
数据结构试题库答案 - 数据结构试题及答案 一、单项选择题 (1) 一个算法应该是( A) 程序 C) 要满足五个基本属性 (2) 算法指的是( A) 计算机程序 C) ...
数据结构试卷2(含答案).pdf
数据结构试卷2(含答案) - 数据结构期末试卷 出卷人:09 数煤(1)班 1~
数据结构复习试题(附答案).doc
数据结构复习试题(附答案) - 单选题( 一、 一、 单选题(每题 2 分,共
数据结构考试题及答案资料.doc
2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把...D.数据 2.数据结构在计算机内存中的表示是指 A.数据的存储结构 元素之间的...
数据结构试题样题及答案.doc
数据结构试题样题及答案 - 数据结构试题样题及答案 一、单项选择题(每小题 2 分,共 30 分) 1.数据结构中,与所使用的计算机无关的是数据的( )结构。 A. ...
数据结构试题二及答案(详细).doc
数据结构试题二及答案(详细)_IT/计算机_专业资料。数据结构试题二及答案(详细
数据结构面试题(含答案).doc
数据结构试题(含答案) - 1.栈和队列的共同特点是(只允许在端点处插入和删除
数据结构期末考试试题及答案.doc
数据结构期末考试试题及答案 - 数据结构期末考试试题及答案 期末样卷参考答案 一