级算法与数据结构试题A.doc
- 文档编号:18678586
- 上传时间:2023-08-30
- 格式:DOC
- 页数:10
- 大小:106.50KB
级算法与数据结构试题A.doc
《级算法与数据结构试题A.doc》由会员分享,可在线阅读,更多相关《级算法与数据结构试题A.doc(10页珍藏版)》请在冰点文库上搜索。
山西财经大学
2008—2009学年第2学期期末
算法与数据结构课程试卷(A卷)
题号
一
二
三
四
五
总分
分数
评卷人
复核人
1、本卷考试形式为闭卷,考试时间为两小时。
2、考生不得将装订成册的试卷拆散,不得将试卷或答题卡带出考场。
3、考生只允许在密封线以外答题,答在密封线以内的将不予评分。
4、考生答题时一律使用蓝色、黑色钢笔或圆珠笔(制图、制表等除外)。
5、考生禁止携带手机、耳麦等通讯器材。
否则,视为作弊。
一、单项选择题(共10小题,每题1分,共计10分)
二、判断题(共10小题,每题1分,共计10分)
三、简答题(共4小题,每题5分,共计20分)
四、应用题(共8小题,1-6小题必做,7、8任选一,1-2每小题5分,3-8每小题6分,共计40分)
五、算法设计题(1、2小题任选一,3、4小题任选一,
每题10分,共计20分)
本题
得分
一、单项选择题(共10小题,每题1分,共计10分)
答题要求:
(请将正确的选项填在题后的括号中)
1.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则下列的存储方式中最节省时间的是()。
A.单链表B.仅有头指针的单循环链表
C.双向链表D.仅有尾指针的单循环链表
2.下面给出的算法段是要把一个p所指新结点,插入到非空双向链表中,作为该双链中q所指结点的前驱结点,能正确完成要求的算法段是()。
A.p->llink=q->llink;B.q->llink=p;
p->rlink=q;p->rlink=q;
q->llink->rlink=p;q->llink->rlink=p;
q->llink=p;p->llink=q->llink;
C.p->rlink=q;D.p->rlink=q;
p->llink=q->llink;p->llink=q->llink;
q->llink=p;q->rlink=p;
q->llink->rlink=p;q->llink->rlink=p;
3.下列选项中,()是非线性数据结构。
A.栈B.队列C.完全二叉树D.堆
4.判定一个循环队列Q(最多元素为m0)为满队列的条件是()。
A.Q.front!
=Q.rearB.Q.front==Q.rear
C.Q.front!
=(Q.rear+1)%m0D.Q.front==(Q.rear+1)%m0
5.串的长度是()。
A.串中不同字母的个数 B.串中不同字符的个数
C.串中所含字符的个数,且大于0D.串中所含字符的个数
6.数组A中,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][5]的起始地址为()。
A.SA+192 B.SA+195
C.SA+222 D.SA+225
7.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()
A.m-nB.m-n-1C.n+1D.条件不足,无法确定
8.有向网G用邻接矩阵A存储,则顶点i的入度等于A中()。
A.第i行非∞元素之和
B.第i列非∞的元素之和
C.第i行非∞且非0的元素个数
D.第i列非∞且非0的元素个数
9.对线性表进行二分查找时,要求线性表必须()。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储,且结点按关键字有序排列
D.以链接方式存储,且结点按关键字有序排列
10.下列排序算法中,在某趟结束后不一定能选出一个元素放到其最终的位置上的是()。
本题
得分
A.堆B.归并C.起泡D.选择
二、判断题(共10小题,每题1分,共计10分)
答题要求:
(正确的请在题后的括号内打“√”,错误的请打“x”)
1.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
()
2.在链表中,逻辑上相邻的两个元素在物理上不一定相邻。
()
3.栈和队列的存储方式,可以采用顺序方式,也可以采用链式方式。
()
4.数组可以看成是线性结构的一种推广,因此可以对它进行插入、删除。
()
5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
()
6.删除二叉排序树中的一个结点,再重新插入进去,一定能得到原来的二叉排序树。
()
7.采用散列法存储,负载因子越大,发生碰撞的可能性也越大。
()
8.若一棵树中某结点的度为1,则该结点仅有一棵子树。
()
9.如果一个串中的所有字符均在另一串中出现,则说前者是后者的子串。
()
10.对任意一个图,从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
()
本题
得分
三、简答题(共4小题,每题5分,共计20分)
答题要求:
(第2、3题请写出中间过程,只写结果不得分)
1.请简述栈和队列的相同和不同之处。
2.已知完全二叉树的第8层有10个结点,则整个二叉树的结点数最多为?
3.什么是二叉排序树?
如何在二叉排序树上实施查找操作?
4.直接插入排序和快速排序两种算法的稳定性如何?
请写出原因。
本题
得分
三、应用题(1-6小题必做,7、8任选一,1-2每小题5分,3-8每小题6分,共计40分)
四、答题要求:
(请尽量写出中间过程)
1.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对上三角部分的任一元素ai,j(i b a c f d e h g 2.如右图所示的一棵二叉树, (1)请画出它的顺序存储表示 (2)写出它的中序遍历序列 (3)画出它的后序线索二叉树。 3.某二叉树的前序遍历结点访问顺序是abdcefgh,中序遍历的结点访问顺序是cbdagfeh,请画出该二叉树。 4.以数据集{3,5,9,14,16,25,33}为结点权值 (1)请构造的哈夫曼树。 (2)并求出它的带权路径长度。 5.哈希表长为11,请给出对序列{7,18,40,35,9,33,28,37,90}进行散列,按照哈希函数H(key)=keyMOD11,及线性线性探测再散列处理冲突,请给出处理的过程及结果。 6.已知序列{30,8,25,15,78,97,65,43,72},采用堆排序法对该序列作升序排序。 (1)建立的初始堆应是大顶堆还是小顶堆? (2)建初始堆时应从哪一个位置开始筛选? (3)请画出建成的初始堆。 7.求出下面AOE网中的关键路径。 要求标明每个顶点的最早和最迟发生时间,并画出关键路径。 10 4 9 9 7 a1 b c d e g f 6 5 132 6 8.求出下图的一棵最小生成树,要求给出过程和所依据的是哪一种算法。 8 10 6 5 9 6 1 4 2 5 3 8 7 6 3 4 3 7 5 1 2 本题 得分 五、算法设计题(1、2小题任选一,3、4小题 任选一,每题10分,共计20分) 答题要求: (在写出算法之前先简要写出算法思想; 在算法中尽可能写一些注释信息。 不按要求只写算法不得分。 ) 单链表存储结构如下: typedefstructLnode{ Elemtypedata; StructLnode*next; }Lnode,*Linklist; 1.试编写在带头结点的单链表中删除最小值结点的算法。 voiddelete(Linklist&L) 2.请编写对不带头结点的单链表进行就地逆置的算法,要求算法用L返回逆置后的链表的头指针。 二叉链表存储表示定义如下: typedefstructBiTNode{ TelemTypedata; StructBiTNode*lchild,*rchild; }BiTNode,*BiTree; 3.假设二叉树采用二叉链表作为存储结构,请编写算法求二叉树中度为2的结点数。 4.设一棵二叉树以二叉链表为存贮结构,设计一个算法将二叉树中所有结点的左,右子树相互交换。 第10页共10页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 试题