2023级算法与数据结构试题A

1、山 西 财 经 大 学20232023学年第 2学期期末算法与数据结构课程试卷A卷题 号一二三四五总分分 数评卷人复核人 1、本卷考试形式为闭卷，考试时间为两小时。2、考生不得将装订成册的试卷拆散，不得将试卷或答题卡带出考场。3、考生只允许在密封线以外答题，答在密封线以内的将不予评分。4、考生答题时一律使用蓝色、黑色钢笔或圆珠笔制图、制表等除外。5、考生禁止携带 、耳麦等通讯器材。否那么，视为作弊。一、单项选择题共10小题，每题 1分，共计10 分二、判断题共10小题，每题1 分，共计10分三、简答题共4小题，每题5 分，共计20分四、应用题共8小题，1-6小题必做，7、8任选一，1-2每题5

2、 分，3-8每题6分，共计40分五、算法设计题1、2小题任选一，3、4小题任选一，每题10分，共计20分此题得分单项选择题共10小题，每题 1分，共计10此题得分答题要求：请将正确的选项填在题后的括号中1假设某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么以下的存储方式中最节省时间的是( )。A单链表 B仅有头指针的单循环链表C双向链表 D仅有尾指针的单循环链表2.下面给出的算法段是要把一个p所指新结点，插入到非空双向链表中，作为该双链中q所指结点的前驱结点，能正确完成要求的算法段是 。Ap-llink=q-llink; B q-llink=p;p-rlink=q;p

3、-rlink=q;q-llink-rlink=p;q-llink-rlink=p;q-llink=p;p-llink=q-llink;Cp-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)为满队列的条件是( )。AQ.front !=Q.rearBQ.front=Q.rearCQ.front !=(Q.rear+

4、1)%m0DQ.front=(Q.rear+1)%m05串的长度是( )。A串中不同字母的个数B串中不同字符的个数C串中所含字符的个数，且大于0 D串中所含字符的个数6数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A75的起始地址为 。ASA+192 BSA+195CSA+222 DSA+2257设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是 Am-n Bm-n-1 Cn+1 D条件缺乏，无法确定8有向网G用邻接矩阵A存储，那么顶点i的入度等于A中(

5、)。A第i行非元素之和B第i列非的元素之和C第i行非且非0的元素个数D第i列非且非0的元素个数9对线性表进行二分查找时，要求线性表必须 。A以顺序方式存储 B以链接方式存储C以顺序方式存储，且结点按关键字有序排列D以链接方式存储，且结点按关键字有序排列10以下排序算法中，在某趟结束后不一定能选出一个元素放到其最终的位置上的是()。此题得分A堆 B归并C起泡 D此题得分判断题共10小题，每题1 分，共计10分答题要求：正确的请在题后的括号内打“，错误的请打“x1顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()2在链表中，逻辑上相邻的两个元素在物理上不一定相邻。( )3栈和队列的存储方

6、式，可以采用顺序方式，也可以采用链式方式。( )4数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除。 5一棵树中的叶子数一定等于与其对应的二叉树的叶子数。()6删除二叉排序树中的一个结点，再重新插入进去，一定能得到原来的二叉排序树。 ( )7采用散列法存储，负载因子越大，发生碰撞的可能性也越大。 ( )8假设一棵树中某结点的度为1，那么该结点仅有一棵子树。 ()9如果一个串中的所有字符均在另一串中出现，那么说前者是后者的子串。( )10对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。( )此题得分三、简答题共4小题，每题5 分，共计20此题

7、得分答题要求：第2、3题请写出中间过程，只写结果不得分1.请简述栈和队列的相同和不同之处。2.完全二叉树的第8层有10个结点，那么整个二叉树的结点数最多为？3.什么是二叉排序树？如何在二叉排序树上实施查找操作？4.直接插入排序和快速排序两种算法的稳定性如何?请写出原因。此题得分应用题1-6小题必做，7、8任选一，1-2每题5 分，3-8每题6分，共计40此题得分答题要求：请尽量写出中间过程1.设矩阵A是一个对称矩阵，为了节省存储，将其下三角局部按行序存放在一维数组B1，n(n-1)/2中，对上三角局部的任一元素ai,j(ij)，求它在一组数组B中的下标位置k的值？bacfdebacfdehg(

8、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)key MOD 11，及线性线性探测再散列处理冲突，请给出处理的过程及结果。6序列30，8，25，15，78，97，65，43，72，采用堆排序法对该序列作升序排序。建立的初始堆应是

9、大顶堆还是小顶堆？建初始堆时应从哪一个位置开始筛选？请画出建成的初始堆。7求出下面AOE网中的关键路径。要求标明每个顶点的最早和最迟发生时间，并画出关键路径。10104997a1bcdegf6513268求出以下图的一棵最小生成树，要求给出过程和所依据的是哪一种算法。88106596142538763437512此题得分五、算法设计题此题得分任选一，每题10分，共计20分答题要求：在写出算法之前先简要写出算法思想；在算法中尽可能写一些注释信息。不按要求只写算法不得分。单链表存储结构如下：typedef struct Lnode Elemtype data; Struct Lnode *next;Lnode,*Linklist;试编写在带头结点的单链表中删除最小值结点的算法。void deleteLinklist &L请编写对不带头结点的单链表进行就地逆置的算法，要求算法用L返回逆置后的链表的头指针。二叉链表存储表示定义如下：typedef struct BiTNo