2007年电子科技大学计算机专业基础试题及答案(2007年电子科技大学计算机专业基础试题答案)
第1部分数据结构(共75分)
1.多项选择题(每题2分,共10分)
1、表头空尾的广义表是( )。
() (()) ((), ()) ((()))
2. 根据第一个关键字使用快速排序算法对以下4 个序列进行排序。第一遍移动次数最多的记录是()
92、96、100、110、42、35、30、88
92、96、88、42、30、35、110、100
100、96、92、35、30、110、88、42
42、30、35、92、100、96、88、110
3在实现图的广度优先搜索算法时,使用的数据结构是( )
堆栈
队列
交叉链表
三重
4. 有向图G的邻接矩阵中,顶点Vi的度为( )。
邻接矩阵第i行元素之和
邻接矩阵第i列元素之和
邻接矩阵中第i行第i列元素之和
邻接矩阵中第i行元素之和与第i列元素之和的最大值
5、能够有效缩短关键路径长度的方法是( )
缩短任何活动的持续时间
缩短关键路径上任何关键活动的持续时间
缩短多个关键路径共享的任何关键活动的持续时间
缩短所有关键路径共有的任何关键活动的持续时间
2.填空(每空2分,共8分)
1、二叉树可以由其后序序列之和唯一确定。
2. 二叉树的节点数n 与边数e 的关系为。
3在各种搜索算法中,平均搜索长度与关键词数量n无关的方法是。
4、如果想要获得树高较短的生成树,可以使用图遍历算法。
3.判断题(正确用表示,错误用表示。每题得分2分,共12分)
1、循环队列不存在队列满的问题。 ( )
2. 当一个新节点插入到二叉排序树中时,该节点必须成为叶子节点。 ( )
3单链表示的有序列表可以使用二分查找的方法来提高查找速度。 ( )
4、如果有向图中每个顶点的入度和出度都为1,则有向图一定有环。 ( )
5、二叉排序树的前序序列已知,可以唯一确定二叉排序树。 ( )
6、通过交换完全二叉树所有节点的左右子树,得到的二叉树仍然是完全二叉树。 ( )
4.简答题(每题6分,共30分)
1、如果一个有向图的邻接矩阵中主对角线以下的元素全为0,那么该图中一定不存在环。这个说法正确吗?为什么?
2.在一棵完全二叉树中,假设节点数为n,
(1) 如何确定完全二叉树中度数为1的节点数n1?
(2)给定节点x的编号m,如何根据该编号判断x是否为叶子节点?
3当查找表需要能够快速查找并适应动态变化时,什么查找方式最合适?并简要说明原因。
4、在某通信系统中,消息字符集为a、b、c、d、e、f、g、h,其出现频率为6、28、8、9、13、22、4、1尝试为每个字符设计一个二进制编码,以最小化消息编码长度。给出每个字符的二进制编码和消息编码长度。
5、设L为无头节点的单向链表的头指针,P为指向链表中某个节点的指针,该节点既不是第一个节点也不是最后一个节点,S为指向新节点的指针被插入。单击指针,使用以下——选项完成功能A和B。
A、将S指向的节点插入到P指向的节点之前的语句顺序是( );
B、将S指向的节点插入到第一个节点之前的语句顺序是( );
P.next:=S;
Q:=P;
L:=S;
P:=L;
WHILE ( P.next Q ) DO P:=P.next;
S.next:=P.next;
S.next:=L.next;
5.算法题(共15分)
1、假设p和q分别指向两个没有头节点的单链表中的一个节点。尝试编写一种算法,在O(1) 时间内将两个单链表合并为一个,并让p 指向p,q 为数据域值较小的节点。 (5分)
PROC xyz( p, q );
{ p 和q 分别指向两个没有头节点的单循环链表中的一个节点。节点结构是数据域data和指针域next}
恩德普;
2、假设二叉树存储为二叉链表,节点结构为lchild、data、rchild。尝试编写一个算法,输出从根节点到二叉树中每个叶节点的路径。假设二叉树最长路径上的节点数小于m,可以使用队列S[1:m],初始时S.rear=S.front=1。 (10分)
PROC RootToLeaf(bt:bitreptr);
{ bt 是二叉树根指针,S[1:m] 是队列,最初S.rear=S.front=1}
恩德普; { 根到叶}
[1][2][3]下一页
相关文章:
第1篇 减法的四种算法(减法的四个运算定律) 作者:admin
8月底,考研大纲即将公布。预注册将于9月进行,正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归,努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多,考研成功的概率就越大呢?并非如此。考研,你要学
第2篇 mpa管理类联考考什么(管理类mpa联考过国家线难吗) 作者:admin
1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似,但附加课程却明显不同,具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如,对外经济贸易学校有以海关为主的课程,农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声
第3篇 考研政治真题试卷pdf(考研政治真题试卷2022) 作者:admin
摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先,研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次,通过分析真题,可以了解考研政治的考点和命题思路,有助于提高备考效果。第三,通过分析真题,可
第4篇 云南大学2021年硕士研究生拟录取(2020年云南大学研究生) 作者:admin
云南大学研究生2023录取摘要云南大学是云南省重点大学之一,以优良的学风和丰富的研究资源而闻名。随着时间的流逝,云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整,以更好地适应当今社会的需求。2023年招生
第5篇 南京大学的新闻传播研究生好考吗(南京大学新闻传播专业考研) 作者:admin
南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点,包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识,希望对即将考