数据结构考试题_1.pdf
《数据结构考试题_1.pdf》由会员分享,可在线阅读,更多相关《数据结构考试题_1.pdf(9页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、要求:所有的题目的解答均写在答题纸上,需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题(每小题 1.5 分,共计 30 分)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 的元素时,在查找元素 x 时采用二分查找,此时的时间复杂度为 。A.O(n)B.O(nlog2
2、n)C.O(n2)D.O(n)4.在一个带头结点的循环单链表 L 中,删除元素值为 x 的结点,算法的时间复杂度为 。A.O(n)B.O(n)C.O(nlog2n)D.O(n2)5.若一个栈采用数组 s0.n-1存放其元素,初始时栈顶指针为 n,则以下元素 x 进栈的正确操作是 。A.top+;stop=x;B.stop=x;top+;C.top-;stop=x;B.stop=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.设环形队列中数组的
3、下标为 0N-1,其队头、队尾指针分别为 front 和 rear(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 的值分别为 。欢迎下载 2 A.1 和 5 B
4、.2 和 4 C.4 和 2 D.5 和 1 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 条边,若满足 ,则图中一定有回路。A.en
5、B.e1)个元素的线性表的运算只有 4 种:删除第一个元素;删除最后一个元素;在第一个元素前面插入新元素;在最后一个元素的后面插入新元素,则最好使用以下哪种存储结构,并简要说明理由。(1)只有尾结点指针没有头结点指针的循环单链表(2)只有尾结点指针没有头结点指针的非循环双链表(3)只有头结点指针没有尾结点指针的循环双链表(4)既有头结点指针也有尾结点指针的循环单链表 2.已知一棵度为 4 的树中,其度为 0、1、2、3 的结点数分别为 14、4、3、2,求该树的结点总数 n 和度为 4 的结点个数,并给出推导过程。3.有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法:假设 G=
6、(V,E)是一个具有 n 个顶点的带权连通无向图,T=(U,TE)是 G 的最小生成树,其中 U 是 T 的顶点集,TE 是 T 的边集,则由 G 构造从起始顶点 u 出发的最小生成树 T 的步骤如下:(1)初始化 U=u。以 u 到其他顶点的所有边为候选边。(2)重复以下步骤 n-1 次,使得其他 n-1 个顶点被加入到 U 中。从候选边中挑选权值最小的边加入到TE,设该边在V-U中的顶点是v,将v加入U中。考查顶点 v,将 v 与 V-U 顶点集中的所有边作为新的候选边。若此方法求得的 T 是最小生成树,请予以证明。若不能求得最小边,请举出反例。4.有一棵二叉排序树按先序遍历得到的序列为:
7、(12,5,2,8,6,10,16,15,18,20)。回答以下问题:(1)画出该二叉排序树。(2)给出该二叉排序树的中序遍历序列。(3)求在等概率下的查找成功和不成功情况下的平均查找长度。三、算法设计题(每小题 10 分,共计 30 分)1.设 A 和 B 是两个结点个数分别为 m 和 n 的单链表(带头结点),其中元素递增有序。欢迎下载 4 设计一个尽可能高效的算法求 A 和 B 的交集,要求不破坏 A、B 的结点,将交集存放在单链表 C 中。给出你所设计的算法的时间复杂度和空间复杂度。2.假设二叉树 b 采用二叉链存储结构,设计一个算法 void findparent(BTNode*b,
8、ElemType x,BTNode*&p)求指定值为 x 的结点的双亲结点 p,提示,根结点的双亲为NULL,若在 b 中未找到值为 x 的结点,p 亦为 NULL。3.假设一个连通图采用邻接表 G 存储结构表示。设计一个算法,求起点 u 到终点 v 的经过顶点 k 的所有路径。四、附加题(10 分)说明:附加题不计入期未考试总分,但计入本课程的总分。假设某专业有若干个班,每个班有若干学生,每个学生包含姓名和分数,这样构成一棵树,如图 1 所示。假设树中每个结点的 name 域均不相同,该树采用孩子兄弟链存储结构,其结点类型定义如下:typedef struct node char name5
9、0;/专业、班号或姓名 float score;/分数 struct node*child;/指向最左边的孩子结点 struct node*brother;/指向下一个兄弟结点 TNode;完成以下算法:(1)设计一个算法求所有的学生人数。(2)求指定某班的平均分。name:计算机专业 score:0 name:计科 1 score:0 name:王华 score:86 name:李明score:79 name:张兵score:79 name:计科 n score:0 name:陈强 score:85 name:许源score:92 name:张山score:69 图 1 一棵学生成绩树 欢迎
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考试题 _1
限制150内