算法与数据结构试题A

山 西 财 经 大 学第 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)为满队列的条件是( )。AQ.front !=Q.rear BQ.front=Q.rearCQ.front !=(Q.rear+1)% m0 DQ.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中( )。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是一种对称矩阵，为了节省存储，将其下三角部分按行序寄存在一维数组B1，n(n-1)/2中，对上三角部分的任一元素ai,j(ij)，求它在一组数组B中的下标位置k的值？ bacfdehg2. 如右图所示的一棵二叉树，(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，采用堆排序法对该序列作升序排序。(1) 建立的初始堆应是大顶堆还是小顶堆？(2) 建初始堆时应从哪一种位置开始筛选？(3) 请画出建成的初始堆。7求出下面AOE网中的核心途径。规定标明每个顶点的最早和最迟发生时间，并画出核心途径。104997a1bcdegf6513268求出下图的一棵最小生成树，规定给出过程和所根据的是哪一种算法。8106596142538763437512 本题得分五、算法设计题（1、2小题任选一，3、4小题任选一，每题10分，合计20分）答题规定：（在写出算法之前先简要写出算法思想；在算法中尽量写某些注释信息。不按规定只写算法不得分。）单链表存储构造如下：typedef struct Lnode Elemtype data; Struct Lnode *next;Lnode,*Linklist;1 试编写在带头结点的单链表中删除最小值结点的算法。void delete（Linklist &L）2 请编写对不带头结点的单链表进行就地逆置的算法，规定算法用L返回逆置后的链表的头指针。 二叉链表存储表达定义如下：typedef struct BiTNode TelemType data; Struct BiTNode *lchild,*rchild; BiTNode,* BiTree;3假设二叉树采用二叉链表作为存储构造，请编写算法求二叉树中度为2的结点数。4设一棵二叉树以二叉链表为存贮构造，设计一种算法将二叉树中所有结点的左，右子树互相互换。