数据结构考试题.pdf
《数据结构考试题.pdf》由会员分享,可在线阅读,更多相关《数据结构考试题.pdf(7页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、百学须先立志。朱熹非淡泊无以明志,非宁静无以致远。诸葛亮一、单项选择题(每小题 2 分,共计 40 分)1.数据结构是指 。A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合 2.以下算法的时间复杂度为 。void fun(int n)int i=1;while(i=n)i+;A.O(n)B.O(n)C.O(nlog2n)D.O(log2n)3.现要设计一个高效的算法,在一个长度为n的有序顺序表中删除所有元素值为x的元素(假设这样的元素是不唯一的),这样的算法时间复杂度为 。A.O(n)B.O(nlog2n)C.O(n2)
2、D.O(n)4.在一个带头结点的循环双链表 L 中,要删除p所指结点,算法的时间复杂度为 。A.O(n)B.O(n)C.O(1)D.O(n2)5.若一个栈采用数组 s0.n-1存放其元素,初始时栈顶指针 top 为n,则以下元素x进栈的正确操作是 。+;stop=x;top=x;top+;stop=x;top=x;top-;6.中缀表达式“2*(3+4)-1”的后缀表达式是 ,其中#表示一个数值的结束。A.2#3#4#1#*+-B.2#3#4#+*1#-C.2#3#4#*+1#-D.-+*2#3#4#1#7.设循环队列中数组的下标为 0N-1,其队头、队尾指针分别为 front 和 rear(
3、front指向队列中队头元素的前一个位置,rear 指向队尾元素的位置),则其元素个数为 。A.rear-front B.rear-front-1 C.(rear-front)N+1 D.(rear-front+N)N 8.若用一个大小为 6 的数组来实现循环队列,队头指针 front 指向队列中队头元素的前一个位置,队尾指针 rear 指向队尾元素的位置。若当前 rear 和 front 的值分别为 0 和3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为 。A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1 宠辱不惊,看庭前花开花落;去留无意,望
4、天上云卷云舒。洪应明我尽一杯,与君发三愿:一愿世清平,二愿身强健,三愿临老头,数与君相见。白居易9.一棵高度为h(h1)的完全二叉树至少有 个结点。A.2h-1 B.2h C.2h+1 D.2h-1+1 10.一棵含有n个结点的线索二叉树中,其线索个数为 。A.2n B.n-1 C.n+1 D.n 11.设一棵哈夫曼树中有 1999 个结点,该哈夫曼树用于对 个字符进行编码。A.999 B.998 C.1000 D.1001 12.一个含有n个顶点的无向连通图采用邻接矩阵存储,则该矩阵一定是 。A.对称矩阵 B.非对称矩阵 C.稀疏矩阵 D.稠密矩阵 13.设无向连通图有n个顶点 e 条边,若
5、满足 ,则图中一定有回路。A.en B.e1)个元素的线性表的运算只有 4 种:删除第一个元素;删除最后一个元素;在第一个元素前面插入新元素;在最后一个元素的后面插入新元素,则最好使用以下哪种存储结构(所有链表均带有头结点),并简要说明理由。(1)只有尾结点指针没有头结点指针的循环单链表(2)只有尾结点指针没有头结点指针的非循环双链表(3)只有头结点指针没有尾结点指针的循环双链表(4)既有头结点指针也有尾结点指针的循环单链表 2.对于图 1 所示的带权有向图,采用 Dijkstra 算法求从顶点 0 到其他顶点的最短路径,要求给出求解过程,包括每一步的 S 集合、dist 和 path 数组元
6、素。9 1 2 3 6 2 7 2 0 3 1 4 2 图 1 一个有向图 3.有一棵二叉排序树按先序遍历得到的序列为:(12,5,2,8,6,10,16,15,18,20)。回答以下问题:(1)画出该二叉排序树。(2)给出该二叉排序树的中序遍历序列。(3)求在等概率下的查找成功和不成功情况下的平均查找长度。4.一个含有n个互不相同的整数的数组 R1.n,其中所有元素是递减有序的,将其看成是一棵完全二叉树,该树构成一个大根堆吗?若不是,请给一个反例,若是,请说明理由。三、算法设计题(每小题 10 分,共计 20 分)1.设 A 和 B 是两个结点个数分别为m和n的单链表(带头结点),其中元素递
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考试题
限制150内