资源描述：
《《算法与数据结构》a卷》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、A.q->next=s~>next；s~>next=p；C.p->next=s->next；s->next=q；3.队和栈的主要区别是（）A.逻辑结构不同C.所包含的运算个数不同4.己知广义表的表头为a,表尾为（b,A.（a,（b,c））2011-2012学年第一学期期末考试试题（A）卷课程名称《算法与数据结构》任课教师签名出题教师签名2011计算机合作联盟命题组审题教师签名考试方式考试时间（闭）卷（110）分钟适用专业10计科1-2题号—二三四五%7七总分得分评卷人（注：判断题和选择题的答案写在答题纸上）一、单项选择题（每小题2分，共30分）1.与数据元素本身
2、的形式、内容、相对位置、个数无关的是数据的（）八.存储结构B.储存实现C.逻辑结构D.运算实现2.已知指针p和q分别指向某单链表中第一个结点和S后一个结点。假设指针s指向另一个单链表中某个结点，则在3所指结点之后插入上述链表应执行的语句为（）B.s->next=p；q->next=s->next；D.s-〉next=q;p->next=s->next；B.存储结构不同D.限定插入和删除的位置不同,则此广义表为（）B.（a,b,c）C.（（a）,b,c）D.（（a,b,c））5.二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3]
3、[4]的存储地址为1000,则元素A[4][3]的存储地址为（）A.1020B.1024C.1036D.12406.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（）A.n-1B.n+1C.nD.2n7.二叉树中第5层上的结点个数最多为（）A.8B.16C.15D.328.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A.250B.500C.254D.5019.若非连通无向图G含有21条边，则G的顶点个数至少为（）•••A.7B.8C.21D.2210.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（hA.上三角矩阵B.稀疏
4、矩阵C.对角矩阵D.对称矩阵11.以vl为起始结点对下图进行深度优先遍历，正确的遍历序列是（）5.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，杏找成功的平均查找长度为（）n-1nn+1A.B.-C.1）.n22213.在长度为32的有序表中进行二分查找，当查找成功时和给定位进行比较的关键字个数最多为（）A.4B.5C.6D.714.对关键字序列（6,1,4,3,基准的一次划分的结果为（A.（5，1,4,3,6，2,8，7）2,8,5）进行快速升序排序时，以笫1个元素为）B.（5,1，4,3，2,6,7,8）C.（5,1,4,3,2,6,8,7）15.下
5、列排序方法中稳定的为（A.冒泡排序B.堆排序D.(8,7,6,C.希尔排序4,3，2,1)D.快速排序二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每个空格中填上正确答案。错填、不填均无分。1.数裾元素及其关系在计算机存储器內的表示称为。2.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结朿时，指针q指向结点郎的结点。q=P；while（q->next!=p）q=q->next;3.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+
6、c7d”得到“ab*cd/+”的操作序列为。4.假设以行优先顺序将一个n阶的3对角矩阵压缩存储到一维数组Q屮，则数组Q的大小至少为O5.森林的中根遍历序列正是相应二叉树的遍历序列，森林的先根遍历序列正是相应二叉树的遍历序列。6.一棵含999个结点的完全二叉树的深度为。7.Prim（普里姆）算法适用于求网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求网的最小生成树。1.在一个无向图中，所有顶点的度数之和等于所有边数的倍。2.对于关键字序列{49,38,65,97,76，13},进行2-路归并升序排序，则第一趟归并排序的结果为。1.若在线性表屮采用二分查找法査
7、找元素，该线性表应该元素按值有序，且采用存储结构。三、解答题（本大题共4小题，每小题7分，共28分）1.假设通信电文使用的字符集为{a,b，c,d,e,f,g},字符的哈夫曼编码依次为:0110,10，110,111,00,0111和010。（约定左分支编码为0,右分支编码为1）（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点屮标注相应字符；（5分）（2）若这些字符在电文中出现的频度分别为：3,35,13,15,20,5和9,求该哈夫曼树的带权路径长度WPU（2分）2.用Prim算法（从顶点B出发）求如下连通图的最小生成树，要求：画山最小生成树，并给出树中每条边
8、的生成顺序
